半構造化テキストの分類のための ブースティングアルゴリズム 工藤 拓 松本　裕治 奈良先端科学技術大学院大学情報科学研究科

機械学習アルゴリズム (SVM, Boosting) 背景 ~ テキスト分類の多様化 メッツ松井、２１打席目オープン戦初本塁　 →スポーツ 大腸がんは細胞増殖制御遺伝子の異常　札幌医大など発表 →科学 自民、森山参院議員を公認へ　衆院鹿児島５区補選 →政治 「単語」を素性 (Bag of Words) 機械学習アルゴリズム　(SVM, Boosting) メールを送受信した日付、時間が表示されるのも結構ありがたいです→良い点 なんとなく、レスポンスが悪いように思います →悪い点 その論議を詰め、国民に青写真を示す時期ではないのか　　　　　→主観的 バブル崩壊で会社神話が崩れ、教育を取り巻く環境も変わった 　→客観的 「単語」を素性 ??? → 直感的にうまくいきそうにない 単語のつながり/関係, テキストの部分構造

半構造化テキストの分類 単語の集合としてのテキスト v.s 半構造化テキスト 構造を考慮した学習/分類 学習事例は木 単語ベクトルではない 単語の並び, 係り受け木, XML (→ラベル付き順序木) 構造を考慮した学習/分類 学習事例は木 単語ベクトルではない 部分構造 (部分木) を素性, サイズに制限を設けない 最適な素性集合を自動的に選択 テキストマイニングのツール

提案手法

順序木分類問題 ラベル付き順序木 順序木学習データ: 順序木: 各接点の兄弟間に順序が定義された木 ラベル付き木: 各節点にラベルが付与された木 ラベル: 単語, 文節, HTML XMLのタグなど 順序木学習データ: 順序木 x　と　クラス y (+1 or –1) のペアの集合 +1 d -1 a +1 d -1 d c d c T= b a , , , a a c a b c

部分木 ある順序木 B が 順序木 A の部分木 マッチング関数 φが存在 順序木 A 順序木 B e f φは単射 φは親子関係を保存 φは兄弟関係を保存 φはラベルを保存 c d e d c a d c c b c

Decision Stumps for Tree (1/3) 部分木の有無に基づく分類器 <t, y>: 分類器のパラメータ(ルール) c d 例 d <t1, y>=< , +1> <t2, y>=< , -1> a b x = c a b h <t1, y>(x) = 1 h <t2, y>(x) = 1

Decision Stumps for Tree (2/3) 学習: gain (~精度)が最大のルールを選択 F: 素性集合 (すべての部分木の集合)

Decision Stumps for Tree (3/3) +1 d -1 a +1 d -1 d c d c b a a a a b <t,y> c c gain a, +1 +1 a, -1 -1 b, +1 -1 +1 c b d a -1 +1 2 … a c d +1 -1 4 Gain が 最大になる <t,y>を選択

Boosting の適用 Decision Stumps だけでは精度が悪い Boosting [Schapire97] を適用 Weak Leaner (Decision Stumps) を構築: Hj Hj　が誤って/正しく分類した事例の重み(頻度)を　　　　　増やす/減らす 1, 2 を T 回繰り返す H1 ~ HT　の重み付き多数決を最終的な学習器とする gain: 重み(頻度) di を導入

実装

弱学習器の構築 (再考) 素性集合 F は巨大 効率よく最適ルールを発見する必要がある 分枝限定法 (Branch-and-Bound) 部分木を列挙する探索空間 を定義 (最右拡張) 探索空間を辿りながら, gain を最大にする部分木を発見 gain の上限値を見積もり, 探索空間を枝刈り

最右拡張 [Asai02, Zaki02] 部分木を 完全に, 重複なく 枚挙する方法 部分木を 完全に, 重複なく　枚挙する方法 サイズ k の木に 1ノード追加し k+1 の木を構築 最右の枝に末弟として追加 再帰的に適用→探索空間

探索空間の枝刈り すべての について なる上限値を見積もる 準最適 gain が分かっているとき, ならば、t から先は枝刈り可能 枝刈り すべての について 　　　　　　 　なる上限値を見積もる　 準最適 gain が分かっているとき, 　　　　　　ならば、t から先は枝刈り可能　　　 枝刈り - 準最適 gain: 0.5 - 0.4 以上の解はこの先の空間に存在しない

上限値の見積もり [Morishita02] の拡張

分類関数 - 単純な線形分類器 　wt : 木 t に対する重み b : バイアス (デフォルトクラス)

SVM との関連性

SVM と Tree Kernel [Collins 02] モデルの形, 素性空間は同一 重み w の導出原理, 方法が異なる a {0,…,1,…1,…,1,…,1,…,1,…,1,…,0,…} b c a b c a a a b c b c SVM: Boosting:

SVM v.s Boosting 精度という観点では比較困難(タスク依存) Boosting の利点 解釈のしやすさ 素性集合がスパース 分類に有効な素性(部分木)が陽に抽出できる 分類が陽に実行され,　分析しやすい 素性集合がスパース 必要最小限の素性が選択され、冗長なものは排除 分類が高速 少数の素性でモデルが表現でき, 分類が高速 Kernel Methods は非常に遅い

実験

文の分類問題 評判分類: PHS (5741文) 文のモダリティ判定 [田村ら96]: mod (1710文) カテゴリ: 良い点, 悪い点 文のモダリティ判定 [田村ら96]: mod (1710文) ドメイン: 新聞記事(社説) カテゴリ: 断定, 意見, 叙述 良い点: メールを送受信した日付、時間が表示されるのも結構ありがたいです。 悪い点: なんとなく、レスポンスが悪いように思います。 断定: 「ポケモン」の米国での成功を単純に喜んでいてはいけない。 意見: その論議を詰め、国民に青写真を示す時期ではないのか。 叙述: バブル崩壊で会社神話が崩れ、教育を取り巻く環境も変わった。

文の表現方法 N-グラム (ngram) 係り受け木 (dep) 単語の集合 (bow) ベースライン 直後の単語に係る木 文節内は直後に係け, 文節内の最後の形態素は, 係り先の文節の head に係ける 　単語の集合 (bow) ベースライン BOS/レスポンス/が/とても/悪い/。/EOS BOS/レスポンス/が/とても/悪い/。/EOS すべて単語の表層ではなく、原型を用いた

結果 Boosting bow 76.0 59.6 70.0 82.2 dep 78.7 86.7 91.7 n-gram 79.3 PHS MOD opinion assertion description Boosting bow 76.0 59.6 70.0 82.2 dep 78.7 86.7 91.7 n-gram 79.3 76.7 87.2 91.6 SVM + Tree Kernel dep 77.0 24.2 81.7 87.6 n-gram 78.9 57.5 84.1 90.1 ベースライン (bow) より高精度 dep v.s n-gram: 有意差は認められない SVM はカテゴリによって極端に精度が悪い

解釈のしやすさ (1/2) PHS データセット (dep) の例 「にくい」を含む素性 0.004024 切れる にくい 0.004024 切れる　にくい -0.000177 にくい 。 -0.000552 にくい なる た -0.000696 読む にくい -0.000738 にくい なる -0.000760 使う にくい -0.001702 にくい　 「使う」を含む素性 0.00273 使う たい 0.00015 使う 0.00013 使う てる 0.00007 使う やすい -0.00010 使う やすい た -0.00076 使う にくい -0.00085 は 使う づらい -0.00188 方 が 使う やすい -0.00233 を 使う てる た 「充電」を含む素性 0.0028 充電 時間 が 短い -0.0041 充電 時間 が 長い

解釈のしやすさ (2/2) PHS データセット (dep) の例 木 t と重み wt 事例 分類結果

その他の利点 素性集合がスパース 分類が高速 PHS データセット (dep) の例 Boosting: 1,783 ルール 1-gram, 2-gram, 3-gram の異なり数がそれぞれ 4,211, 24,206, 43,658 SVM: おそらく 数十~百万 分類が高速 Boosting: 0.135秒 / 1149 事例 SVM: 57.91秒 / 1149 事例 400 倍程度 高速

まとめと今後の課題 部分木を素性とする Decision Stumps Boosting の適用, SVM との関連性 利点 分枝限定法 Boosting の適用, SVM との関連性 利点 解釈のしやすさ 素性集合がスパース 分類が高速 グラフ構造への拡張 部分グラフの枚挙アルゴリズム G-span [Yan et al. 02]

Kernel 法に基づく SVMs との関連性 Decision Stumps に基づく Boosting Tree Kernel に基づく SVM 　　　　　　　　　本質的に同一 類似点 学習に使われる素性 マージン最大化に基づく学習 相違点 マージンのノルム モデルのスパース性

分類の高速化 (1/3) - 単純な線形分類器 R : 分類に必要な素性集合 |R|<<|F|

分類の高速化 (2/3) 単純な方法 分類のコストは, 入力 x に対し を導出するコストと同一 - R 中のそれぞれの木が x の部分木になるか チェック → O(|R|) - x 中の部分木を列挙して R 中にあるかチェック → O(exp(|x|))

分類の高速化 (3/3) - 文字列表現のノードの出現順 = RME の適用順 - TRIE = RME が作る探索空間 a d b -1 0.2 b c -0.3 b d –1 e 0.1 a d 0.5 a b –1 c -0.2 a b d 0.3 a b c subtrees root c e R TRIE 木の文字列表現 a b c d e a b c –1 d e a b i c d a b c –1 –d –1 –1 i - 文字列表現のノードの出現順 = RME の適用順 - TRIE = RME が作る探索空間 - 分類: TRIE を辿ることで実現, コスト ~ O(|x|)

SVM v.s Boosting (2/4) q ノルムマージンの最大化 Boosting: SVM: ∞ノルム→冗長な次元を削除

最右拡張 [Asai02, Zaki02] サイズ k の木に 1 つのノードを追加し サイズ k+1 の木を構築 - 最右枝に追加 - 最右枝に追加 - 末弟として追加 A 1 B C 2 4 7 A A 1 最右枝 1 C A B 3 5 6 B C B C 2 2 4 4 A 1 C A B C A B 3 5 6 3 5 6 B C 2 4 の位置 x ラベルの種類 {A,B,C} の木が構築される 7 C A B 3 5 6 7

Boosting

SVM v.s Boosting (1/3) 1. 1つめの制約は、本質的に同一 - Tree Kernel → すべての部分木を素性 1. 1つめの制約は、本質的に同一 - Tree Kernel → すべての部分木を素性 - Boosting → すべての部分木を弱学習器 2. 相違点は、wのノルム (1-norm, 2-norm)

Tree Kernel [Collins 02][Kashima 03] 全部分木を素性 a {0,…,1,…1,…,1,…,1,…,1,…,1,…,0,…} b c a b c a a a b c b c SVM (Kernel Methods) は, 事例間の内積しか使わない → 陽に素性展開せず, 陰に内積のみを効率よく計算 → 素性抽出を, Kernel (一般化された内積) として実現

上限値の見積もり [Morishita 02] の拡張 - + +1 -1 -1 +1 T y=+1 y=-1 t t’ - = 2・( ) + 定数 =C 2・( ) + C 2・( ) + C 2 ・( ) - C max( , ) 2・( ) – C 2・( ) + C