部分木を素性とする Decision Stumps と Boosting Algorithm の適用 工藤 拓 松本　裕治 奈良先端科学技術大学院大学情報科学研究科 SIGNL 158

背景 (1/2) 機械学習を用いたテキスト分類 カテゴリの変化 テキストの単位の変化 素性: Bag-of-Words (BOW) 　機械学習を用いたテキスト分類 素性: Bag-of-Words (BOW) 学習アルゴリズム: SVM, Boosting, Naïve Bayes 単語がカテゴリ(政治,スポーツ)を当てる手がかり カテゴリの変化 意見性, 主観性, モダリティ テキストの単位の変化 文書 → パッセージ, 文 直感: BOW では　うまくいきそうにない

背景 (2/2) 有効そうな素性を発見的に利用 しかし… 固定長の N-gram 部分的な係り受け関係 (係り元/先, 部分木) N-gram の N, 部分木のサイズをいくつにするか? 小さい(N=1) と, BOW と変わらない いたずらに大きくすると… 汎化能力の低下, 過学習 素性の候補が指数的に増え, 分析が困難 タスク依存性が強い

問題の定式化 (一般化) 単語の集合としてのテキスト 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 以上の解はこの先の空間に存在しない

上限値の見積もり [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

分類関数 - 単純な線形分類器 　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 [Rätsch 01] マージン最大化アルゴリズム, マージンの定義の違い モデルのスパース性 SVM: 2-norm　マージン 少数の事例で　w を表現 サポートベクター 事例スパース 素性(弱学習器) 1 J 1 Boosting: ∞-norm　マージン - 少数の素性で w を表現 - 素性スパース …0,0,0,1,0,0,1,0,0… 事例 K 事例スパース ≄ 素性スパース

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

その他 準最適解の事前計算 分類の高速化 0 に初期化するかわりに… 前回の Iteration までに得られた全ルール集合の中から、準最適解を計算しておく 分類の高速化 最右拡張を利用 ~ O(|x|) : |x| は分類する木のノード数

実験

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

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

結果 PHS MOD bow < ngram ～ dep SVM ～ Boosting 利点 B: Boosting S: SVMs (Tree Kernel) PHS MOD bow < ngram ～ 　　　　　 dep ngram v.s dep: タスク依存 SVM ～ Boosting Tree Kernel を使い全部分木を用いると極端に悪くなる場合がある 利点 解釈のしやすさ 素性集合がスパース 分類が高速 F値 B: bow 76.6 B: ngram 79.3 B: dep 79.0 S: bow 77.2 S: ngram 79.4 S: dep 断定 意見 叙述 B: bow 76.6 62.0 83.0 B: ngram 87.6 78.5 91.9 B: dep 87.5 80.5 S: bow 72.2 59.2 82.5 S: ngram 81.7 26.1 88.1 S: dep

解釈のしやすさ (1/2) PHS データセット (dep) の例 「にくい」を含む素性 0.004024 切れる にくい 0.004024 切れる　にくい -0.000177 にくい EOS 。 -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 と重みλt 事例 分類結果

その他の利点 素性集合がスパース 分類が高速 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 (一般化された内積) として実現

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