半構造化テキストの分類のための ブースティングアルゴリズム

Presentation on theme: "半構造化テキストの分類のための ブースティングアルゴリズム"— Presentation transcript:

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

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

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

4 提案手法

5 順序木分類問題 ラベル付き順序木 順序木学習データ: 順序木: 各接点の兄弟間に順序が定義された木
ラベル付き木: 各節点にラベルが付与された木 ラベル: 単語, 文節, 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

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

7 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

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

9 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>を選択

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

11 実装

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

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

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

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

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

17 SVM との関連性

18 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:

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

20 実験

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

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

23 結果 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 はカテゴリによって極端に精度が悪い

24 解釈のしやすさ (1/2) PHS データセット (dep) の例 「にくい」を含む素性 0.004024 切れる にくい
切れる　にくい にくい 。 にくい なる た 読む にくい にくい なる 使う にくい にくい　 「使う」を含む素性 使う たい 使う 使う てる 使う やすい 使う やすい た 使う にくい は 使う づらい 方 が 使う やすい を 使う てる た 「充電」を含む素性 充電 時間 が 短い 充電 時間 が 長い

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

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

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

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

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

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

31 分類の高速化 (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|)

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

33 最右拡張 [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

34 Boosting

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

36 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 (一般化された内積) として実現

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