部分木を素性とする Decision Stumps と Boosting Algorithm の適用工藤拓松本裕治奈良先端科学技術大学院大学情報科学研究科 SIGNL 158 1 背景 (1/2) 機械学習を用いたテキスト分類    素性: Bag-of-Words (BOW) 学習アルゴリズム: SVM, Boosting, Naïve Bayes 単語がカテゴリ(政治,スポーツ)を当てる手がかりカテゴリの変化  意見性, 主観性, モダリティテキストの単位の変化  文書 → パッセージ, 文直感: BOW ではうまくいきそうにない 2 背景 (2/2) 有効そうな素性を発見的に利用   固定長の N-gram 部分的な係り受け関係 (係り元/先, 部分木) しかし…    N-gram の N, 部分木のサイズをいくつにするか? 小さい(N=1) と, BOW と変わらないいたずらに大きくすると…  汎化能力の低下, 過学習  素性の候補が指数的に増え, 分析が困難 3 問題の定式化 (一般化) 単語の集合としてのテキスト v.s 半構造化テキスト  単語の並び, 係り受け木, XML (→ラベル付き順序木) 構造の部分構造を発見的に利用するより, 構造を直接考慮できるアルゴリズムを提案するほうが, 一般的で, 見通しが良い構造を考慮した学習/分類     学習事例は木単語ベクトルではない部分構造 (部分木) を素性部分木のサイズに制限を設けない最適な素性集合を自動的に選択 4 提案手法 5 順序木分類問題ラベル付き順序木    順序木: 各接点の兄弟間に順序が定義された木ラベル付き木: 各節点にラベルが付与された木ラベル: 単語, 文節, 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 6 部分木 AB ある順序木 B が順序木 A の部分木順序木 A 順序木 B e f c d e c c a b d d c c マッチング関数 φが存在     φは単射 φは親子関係を保存 φは兄弟関係を保存 φはラベルを保存 7 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> 8 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 9 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 選択 10 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 11 実装 12 弱学習器の構築 (再考) 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 の上限値を見積もり, 探索空間を枝刈り 13 最右拡張 [Asai02, Zaki02] 部分木を完全に, 重複なく枚挙する方法サイズ k の木に 1ノード追加し k+1 の木を構築  最右の枝に末弟として追加再帰的に適用→探索空間 14 探索空間の枝刈りすべての 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 ( ) 15 上限値の見積もり [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 )16 分類関数   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 : バイアス (デフォルトクラス) 17 SVM との関連性 18 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 19 SVM v.s Boosting [Rätsch 01] マージン最大化アルゴリズム, マージンの定義の違いモデルのスパース性 1 1 素性(弱学習器) J …0,0,0,1,0,0,1,0,0… SVM: 2-norm マージン -少数の事例で w を表現 - サポートベクター K w   i (xi ) i 1 - 事例スパース事例 K 事例スパース ≄ 素性スパース Boosting: ∞-norm マージン - 少数の素性で w を表現 - 素性スパース 20 SVM v.s Boosting 精度という観点では比較困難(タスク依存) Boosting の利点  解釈のしやすさ  分類に有効な素性(部分木)が陽に抽出できる  分類が陽に実行され, 分析しやすい  素性集合がスパース  必要最小限の素性が選択され、冗長なものは排除  分類が高速  少数の素性でモデルが表現でき, 分類が高速  Kernel Methods は非常に遅い 21 その他準最適解の事前計算   0 に初期化するかわりに… 前回の Iteration までに得られた全ルール集合の中から、準最適解を計算しておく分類の高速化   最右拡張を利用 ~ O(|x|) : |x| は分類する木のノード数 22 実験 23 文の分類問題評判分類: PHS (5741文)   ドメイン: PHS の批評掲示板カテゴリ: 良い点, 悪い点良い点: メールを送受信した日付、時間が表示されるのも結構ありがたいです。悪い点: なんとなく、レスポンスが悪いように思います。文のモダリティ判定文) [田村ら96]: mod (1710 ドメイン: 新聞記事(社説) カテゴリ: 断定, 意見, 叙述断定: 「ポケモン」の米国での成功を単純に喜んでいてはいけない。  意見: その論議を詰め、国民に青写真を示す時期ではないのか。叙述: バブル崩壊で会社神話が崩れ、教育を取り巻く環境も変わった。 24 文の表現方法 N-グラム (ngram)   直後の単語に係る木部分木は N-グラム BOS/レスポンス/が/とても/悪い/。/EOS 係り受け木 (dep)  文節内は直後に係け, 文節内の最後の形態素は, 係り先の文節の head に係ける BOS/レスポンス/が/とても/悪い/。/EOS 単語の集合 (bow) ベースラインすべて単語の表層ではなく、原型を用いた 25 B: Boosting S: SVMs (Tree Kernel) 結果 PHS MOD F値断定意見叙述 B: bow 76.6 B: bow 76.6 62.0 83.0 B: ngram 79.3 B: ngram 87.6 78.5 91.9 bow < ngram ～ dep  SVM ～ Boosting  B: dep 79.0 B: dep 87.5 80.5 91.9 S: bow 77.2 S: bow 72.2 59.2 82.5 79.4 S: ngram 77.2 S: dep S: ngram S: dep 81.7 26.1 88.1 81.7 26.1 88.1 ngram v.s dep: タスク依存 Tree Kernel を使い全部分木を用いると極端に悪くなる場合がある利点    解釈のしやすさ素性集合がスパース分類が高速 26 解釈のしやすさ (1/2) 「にくい」を含む素性 0.004024 -0.000177 -0.000552 -0.000696 -0.000738 -0.000760 -0.001702 切れるにくいにくい EOS 。にくいなるた読むにくいにくいなる使うにくいにくい「充電」を含む素性 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 使うたい使う使うてる使うやすい使うやすいた使うにくいは使うづらい方が使うやすいを使うてるた 27 解釈のしやすさ (2/2) PHS データセット (dep) の例   f (x)  sgn  wt  I (t  x)  b tF  木 t と重みλt 分類結果事例 28 その他の利点 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 倍程度高速 29 まとめと今後の課題部分木を素性とする Decision Stumps  分枝限定法 Boosting の適用, SVM との関連性利点    解釈のしやすさ素性集合がスパース分類が高速グラフ構造への拡張   部分グラフの枚挙アルゴリズム G-span [Yan et al. 02] 30 Kernel 法に基づく SVMs との関連性 Decision Stumps に基づく Boosting Tree Kernel に基づく SVM 本質的に同一類似点   学習に使われる素性マージン最大化に基づく学習相違点   マージンのノルムモデルのスパース性 31 分類の高速化 (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| 32 分類の高速化 (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|)) 33 分類の高速化 (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|) 34 -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 ∞ノルム→冗長な次元を削除 35 最右拡張 [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 36 B Boosting 37 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) 38 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 ) 39 上限値の見積もり [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 40