半構造化テキストの分類のためのブースティングアルゴリズム工藤拓松本裕治奈良先端科学技術大学院大学情報科学研究科 1 背景 ~ テキスト分類の多様化メッツ松井、２１打席目オープン戦初本塁 →スポーツ「単語」を素性 (Bag札幌医大など発表 of Words) 大腸がんは細胞増殖制御遺伝子の異常 →科学機械学習アルゴリズム (SVM, Boosting)→政治自民、森山参院議員を公認へ衆院鹿児島５区補選メールを送受信した日付、時間が表示されるのも結構ありがたいです→良い点なんとなく、レスポンスが悪いように思います →悪い点「単語」を素性 ??? → 直感的にうまくいきそうにないその論議を詰め、国民に青写真を示す時期ではないのか単語のつながり/関係, テキストの部分構造 →主観的バブル崩壊で会社神話が崩れ、教育を取り巻く環境も変わった →客観的 2 半構造化テキストの分類単語の集合としてのテキスト v.s 半構造化テキスト  単語の並び, 係り受け木, XML (→ラベル付き順序木) 構造を考慮した学習/分類     学習事例は木単語ベクトルではない部分構造 (部分木) を素性, サイズに制限を設けない最適な素性集合を自動的に選択テキストマイニングのツール 3 提案手法 4 順序木分類問題ラベル付き順序木    順序木: 各接点の兄弟間に順序が定義された木ラベル付き木: 各節点にラベルが付与された木ラベル: 単語, 文節, HTML XMLのタグなど順序木学習データ: T  順序木 x とクラス y (+1 or –1) のペアの集合 T  {x1 , y1 , x2 , y2 ,, x K , yK } +1 T= c a d -1 a , c d a +1 , a c d -1 b , c b d a 5 部分木 AB ある順序木 B が順序木 A の部分木順序木 A 順序木 B e f c d e c c a b d d c c マッチング関数 φが存在     φは単射 φは親子関係を保存 φは兄弟関係を保存 φはラベルを保存 6 Decision Stumps for Tree (1/3) 部分木の有無に基づく分類器  y　if t  x h t , y  (x)   otherwise  y  y  (2  I (t  x)  1) <t, y>: 分類器のパラメータ(ルール) 例 x = c a d b c <t1, y>=< a , +1> h (x) = 1 <t1, y> d <t2, y>=< b , -1> h (x) = 1 <t2, y> 7 Decision Stumps for Tree (2/3) 学習: gain (~精度)が最大のルールを選択 tˆ, yˆ   arg max gain(t , y ) tF , y{1, 1} K gain(t , y )   yi  h t , y  (xi ) i 1 T  {x1 , y1 , x2 , y2 ,, x K , yK } F: 素性集合 (すべての部分木の集合) K F  {t ' | t '  xi } i 1 8 Decision Stumps for Tree (3/3) +1 c <t,y> a, +1 a, -1 b, +1 a d a -1 d a +1 c d -1 b b d a c a +1 -1 +1 -1 +1 -1 +1 -1 0 0 -1 -1 +1 +1 -1 +1 -1 +1 -1 4 -1 2 c gain … d c +1 a … d b c a -1 Gain が最大になる <t,y>を +1 +1 +1 選択 9 Boosting の適用 Decision Stumps だけでは精度が悪い Boosting [Schapire97] を適用 1. 2. 3. 4. Weak Leaner (Decision Stumps) を構築: Hj Hj が誤って/正しく分類した事例の重み(頻度)を増やす/減らす 1, 2 を T 回繰り返す H1 ~ HT の重み付き多数決を最終的な学習器とする gain: 重み(頻度) di を導入 K gain(t , y )   di  yi  h t , y  (xi ), i 1 K di  0,  di  1 i 1 10 実装 11 弱学習器の構築 (再考) tˆ, yˆ   arg max K d  y h tF , y{1, 1} i 1 i i t , y (xi ) K F  {t ' | t '  xi } i 1  素性集合 F は巨大  効率よく最適ルールを発見する必要がある • • • 分枝限定法 (Branch-and-Bound) 部分木を列挙する探索空間を定義 (最右拡張) 探索空間を辿りながら, gain を最大にする部分木を発見 gain の上限値を見積もり, 探索空間を枝刈り 12 最右拡張 [Asai02, Zaki02] 部分木を完全に, 重複なく枚挙する方法サイズ k の木に 1ノード追加し k+1 の木を構築  最右の枝に末弟として追加再帰的に適用→探索空間 13 探索空間の枝刈り t '  t , y {1,1} について gain(t ' , y )   (t ) なる上限値を見積もるすべての準最適 gain  が分かっているとき,  (t )   ならば、t から先は枝刈り可能 gain  0.1 ( ) gain  0.4   0.4   0.7 枝刈り - 準最適 gain: 0.5 - 0.4 以上の解はこの先の空間に存在しない t '  t, gain  0.3( )   0.6 gain(t ' , y )   (t ) gain  0.4 ( )   0.5 gain  0.5 ( ) gain  0.4 ( ) 14 上限値の見積もり [Morishita02] の拡張  t '  t , y {1,1} gain(t ' , y )   (t )    2  d i   yi d i ,  i 1  {i| yi  1,t  x}   (t )  max  K 　 2 d  y d  i i i   {i| y  i 1 i 1,t  x}   K 15 分類関数   f (x)  sgn     t , y  h t , y  (x) tF , y{1, 1}  ht , y (x)  y  (2  I (t  x) 1)    sgn     t , y  y  (2  I (t  x)  1)  tF , y{1, 1}    wt  2(   t , 1  t , 1)  sgn  wt  I (t  x)  b   tF  b   (   t , 1  t , 1 )   tR - 単純な線形分類器 - wt : 木 t に対する重み - b : バイアス (デフォルトクラス) 16 SVM との関連性 17 SVM と Tree Kernel [Collins 02] Tree Kernel: 全部分木を素性 x   (x)  {I (t1  x),, I (t J  x)} a モデルの形, 素性空間は同一 {0,…,1,…1,…,1,…,1,…,1,…,1,…,0,…} b c 重み w の導出原理, 方法が異なる a SVM: Boosting: b c a a a b c b c f (x)  sgn{w   (x)  b}  sgn  wt  I (t  x)  b f (x)  sgn w  I (t  x)  b t 18 SVM v.s Boosting 精度という観点では比較困難(タスク依存) Boosting の利点  解釈のしやすさ  分類に有効な素性(部分木)が陽に抽出できる  分類が陽に実行され, 分析しやすい  素性集合がスパース  必要最小限の素性が選択され、冗長なものは排除  分類が高速  少数の素性でモデルが表現でき, 分類が高速  Kernel Methods は非常に遅い 19 実験 20 文の分類問題評判分類: PHS (5741文)   ドメイン: PHS の批評掲示板カテゴリ: 良い点, 悪い点良い点: メールを送受信した日付、時間が表示されるのも結構ありがたいです。悪い点: なんとなく、レスポンスが悪いように思います。文のモダリティ判定   [田村ら96]: mod (1710文) ドメイン: 新聞記事(社説) カテゴリ: 断定, 意見, 叙述断定: 「ポケモン」の米国での成功を単純に喜んでいてはいけない。意見: その論議を詰め、国民に青写真を示す時期ではないのか。叙述: バブル崩壊で会社神話が崩れ、教育を取り巻く環境も変わった。 21 文の表現方法 N-グラム (ngram)   直後の単語に係る木部分木は N-グラム BOS/レスポンス/が/とても/悪い/。/EOS 係り受け木 (dep)  文節内は直後に係け, 文節内の最後の形態素は, 係り先の文節の head に係ける BOS/レスポンス/が/とても/悪い/。/EOS 単語の集合 (bow) ベースラインすべて単語の表層ではなく、原型を用いた 22 結果 PHS Boosting SVM + Tree Kernel MOD opinion assertion description bow 76.0 59.6 70.0 82.2 dep 78.7 78.7 86.7 91.7 n-gram 79.3 76.7 87.2 91.6 dep n-gram 77.0 78.9 24.2 57.5 81.7 84.1 87.6 90.1  ベースライン (bow) より高精度  dep v.s n-gram: 有意差は認められない  SVM はカテゴリによって極端に精度が悪い 23 解釈のしやすさ (1/2) 「にくい」を含む素性 0.004024 -0.000177 -0.000552 -0.000696 -0.000738 -0.000760 -0.001702 切れるにくいにくい。にくいなるた読むにくいにくいなる使うにくいにくい「充電」を含む素性 0.0028 充電時間が短い -0.0041 充電時間が長い PHS データセット (dep) の例   f (x)  sgn  wt  I (t  x)  b tF  「使う」を含む素性 0.00273 0.00015 0.00013 0.00007 -0.00010 -0.00076 -0.00085 -0.00188 -0.00233 使うたい使う使うてる使うやすい使うやすいた使うにくいは使うづらい方が使うやすいを使うてるた 24 解釈のしやすさ (2/2) PHS データセット (dep) の例   f (x)  sgn  wt  I (t  x)  b tF  木 t と重み wt 分類結果事例 25 その他の利点 PHS データセット (dep) の例素性集合がスパース  Boosting: 1,783 ルール  1-gram, 2-gram, 3-gram の異なり数がそれぞれ 4,211, 24,206, 43,658  SVM: おそらく数十~百万分類が高速    Boosting: 0.135秒 / 1149 事例 57.91秒 / 1149 事例 SVM: 400 倍程度高速 26 まとめと今後の課題部分木を素性とする Decision Stumps  分枝限定法 Boosting の適用, SVM との関連性利点    解釈のしやすさ素性集合がスパース分類が高速グラフ構造への拡張   部分グラフの枚挙アルゴリズム G-span [Yan et al. 02] 27 Kernel 法に基づく SVMs との関連性 Decision Stumps に基づく Boosting Tree Kernel に基づく SVM 本質的に同一類似点   学習に使われる素性マージン最大化に基づく学習相違点   マージンのノルムモデルのスパース性 28 分類の高速化 (1/3)   f (x)  sgn   w t , y  h t , y  (x) tF , y{1, 1}  ht , y (x)  y  (2  I (t  x) 1)    sgn   w t , y  y  (2  I (t  x)  1)  tF , y{1, 1}    R  {t | t  F , (wt ,1 w t , 1 )  0}  sgn   t  I (t  x)  b  t  2(wt ,1 w t , 1 )  tR    b   ( w t , 1  w t , 1 ) tR - 単純な線形分類器 -R : 分類に必要な素性集合 |R|<<|F| 29 分類の高速化 (2/3)   f (x)  sgn   t  I (t  x)  b  tR  分類のコストは, 入力 x に対し R  {t | t  x} を導出するコストと同一単純な方法 - R 中のそれぞれの木が x の部分木になるかチェック → O(|R|) - x 中の部分木を列挙して R 中にあるかチェック → O(exp(|x|)) 30 分類の高速化 (3/3) R 木の文字列表現 a subtrees b c d e a b c –1 d e a b c i d a b c –1 –d –1 –1 i TRIE root  abc 0.3 abd -0.2 a b –1 c 0.5 ad 0.1 bc 0.2 b d –1 e -0.3 a b c d 0.3 -0.2 b d c 0.1 0.2 d -1 -1 c e 0.5 - 文字列表現のノードの出現順 = RME の適用順 - TRIE = RME が作る探索空間 - 分類: TRIE を辿ることで実現, コスト ~ O(|x|) 31 -0.3 SVM v.s Boosting (2/4) || w || p  1, 1/ p 1/ q  1 SVM: || w ||2 , d q2 q ノルムマージンの最大化 Boosting: || w ||1 , q d ∞ノルム→冗長な次元を削除 32 最右拡張 [Asai02, Zaki02] サイズ k の木に 1 つのノードを追加しサイズ k+1 の木を構築 - 最右枝に追加 - 末弟として追加 1 2 3 C 2 A B A B 4 最右枝 4 5 1 A 6 C 5 1 B の位置 x ラベルの種類 {A,B,C} の木が構築される 7 1 3 C C A 6 B 2 B 3 C A 2 B 4 3 C A 5 A 4 5 A C 6 C 6 B 7 7 33 B Boosting 34 SVM v.s Boosting (1/3) SVM: Boosting: w arg max  w J s.t. yi (w   (x i ))   , || w ||2  1 w arg max  w J J s.t. yi ( w j h j (x i ))   , j 1 || w ||1  1 1. 1つめの制約は、本質的に同一 - Tree Kernel → すべての部分木を素性 - Boosting → すべての部分木を弱学習器 2. 相違点は、wのノルム (1-norm, 2-norm) 35 Tree Kernel [Collins 02][Kashima 03] 全部分木を素性 x   (x)  {I (t1  x),, I (t J  x)} a b c {0,…,1,…1,…,1,…,1,…,1,…,1,…,0,…} a b c a a a b c b c SVM (Kernel Methods) は, 事例間の内積しか使わない → 陽に素性展開せず, 陰に内積のみを効率よく計算 → 素性抽出を, Kernel (一般化された内積) として実現  (x1 )  (x2 )  K (x1 , x2 ) 36 上限値の見積もり [Morishita 02] の拡張 T y=+1 y=-1 K gain(t , y )   yi  di  h t , y  (xi ) i 1 - gain(t ' ,1)  t +1 t’ = 2・( - -1 )+ + -1 +1 定数 =C t  t'  2・( )+C  2・( )+C gain(t ' ,1)  2 ・( gain(t ' , y )  max( 2・( - ) + C , 2・( )-C ) – C )   (t )37