部分木に基づくマルコフ確率場と言語解析への適用 工藤 拓 松本裕治 奈良先端科学技術大学院大学

統計的言語解析 (背景) History-based Methods から Global discriminative models へ I ate a cake I ate a cake PRP VBD DT NN I ate a cake NP VP NP VBD ate PRP NN I DT a cake S NP VP X Y Part of Speech Tagging Dependency Parsing Text Chunking (Shallow Parsing) Phrase Structure Parsing History-based Methods から Global discriminative models へ 方法論の変化 木から木への変換　　X: 入力木, Y:　解析木　 学習データ : 統計的言語解析: P(Y|X) を最大にする Y を導出

History-based Methods (HM) 言語処理 (品詞タグ付け, 構文解析) を 分類問題の順次適用として実現 事例 (=履歴) クラス 正準的な構築順序を定義 過去の履歴を元に, 現在　　のクラスを決定 既知の学習アルゴリズム 　　を直接適用可能 I had an apple Input: PRP PRP VBD PRP VBD DT PRP VBD DT NN

History-based Methods の問題点 履歴に依存 いったん間違えると, 伝播 ラベルバイアス問題 [Lafferty 01] 最適な構築順序とは? 品詞タグ付け (前向き/後ろ向き) 構文解析 (トップダウン/ボトムアップ/左隅/右隅) 一意に決定困難 (タスク依存, 入力文依存) 発見的に対処 前向き, 後ろ向きの多数決 [Kudo 01]

Global discriminative models 解析結果 1 つを学習事例とみなす 解析木そのものが正しいか正しくないか学習 構築順序という概念は存在しない 順序に関係せず, 唯一の確率値 P(Y|X)を算出 … I bought a car with this money +1 -1 事例 クラス MRF/CRF [Lafferty 01] Tree Kernel [Collins 02] HMM-SVM [Altun 03]

Global discriminative models の論点 負例の構築方法 HM の N-best 解で近似 陰に構築 (動的計画法) 学習アルゴリズム側で動的に生成 学習方法 MRF (線形対数モデル/最大エントロピー) Boosting SVM 素性 人手で発見的に定義 Tree Kernel - 全部分木の候補から素性選択

概要 手法 実験 考察, 従来研究との比較 まとめと今後の課題 負例の構築方法 (N-best 解) 学習方法 (MRF) 素性 (全部分木候補から素性選択) 実験 考察, 従来研究との比較 まとめと今後の課題

1. 手法 負例の構築方法 学習方法 素性

負例の構築方法 History-based Methods の N-best 解 Viterbi + A* ビーム探索 N-best 解に正解が存在すると仮定 入力木 X に対する N-best 解の集合を 　H(X) と表記

学習方法 (1/2) マルコフ確率場 　　　　　　　　　　　　　　　　(a.k.a. 線形対数モデル / 最大エントロピーモデル) : 素性関数 : パラメータ

学習方法 (2/2) パラメータの導出 最尤推定 (最大エントロピー原理) 正規分布による正則化 (過学習の抑制) [Chen99] : ハイパーパラメータ (交差検定等で設定)

素性関数 の設計 (1/3) 解析木の 構造 を考慮したい 解析木 Y 中の 部分木 を素性 各部分木にパラメータ が対応 a b c d 素性関数 の設計 (1/3) 解析木の 構造 を考慮したい 解析木 Y 中の 部分木 を素性 各部分木にパラメータ　　　が対応 a b c d a b c d Y 0.2 0.1 -1.0 0.3 0.4 0.5 -0.1

素性関数 の設計 (2/3) X: a – b – c a b c Y1 Y2 Y3 H(X): n-best (n=3) 素性関数 の設計 (2/3) X: a – b – c a b c Y1 Y2 Y3 H(X): n-best (n=3) a b c 0.2 0.1 -0.1 0.3 -0.3 P(Y1|X)=exp(0.8)/Z P(Y2|X)=exp(-0.1)/Z P(Y3|X)=exp(0.4)/Z 正解の解析木の対数確率尤度を最大にするようλを設定

素性関数 の設計 (3/3) 素性集合: (全部分木) (部分木 t の有無) 素性関数:

素性選択 (1/2) 素性集合 F は 巨大 全部分木を使用→ 過学習, 学習困難 素性選択 1,2,3 を全て満たす部分木のみを使う 頻度: ξ回以上出現する部分木のみ 部分木のサイズ: サイズが L 以上 M以下 クラスと素性の相関性: カイ二乗値が χ以上 1,2,3 を全て満たす部分木のみを使う Σ=<ξ,L,M,χ>: 素性選択パラメータ

素性選択 (2/2) クラスと素性の統計的な相関性 「良い」部分木 t : 正例/負例に偏って出現する t chi(t) がχ以上の部分木 t を素性 正例: N-best 解 負例:

実装 頻出部分木マイニングの適用 最右拡張を用いた高速な解析 木の集合から頻出する部分木を効率よく列挙するアルゴリズム 最右拡張 (木の枚挙手法) FREQT [Asai02], TreeMinerV [Zaki02] 最右拡張を用いた高速な解析 ～O(|Y|) リランキングのコストは問題になりにくい

2. 実験

設定 英語品詞タグ付け 英語基本句同定 PTB 15 – 18: 学習, 20: テスト, 21: dev HM: 最大エントロピー法に基づく Tagger, N=20 ☆ 英語基本句同定 PTB 15 – 18: 学習, 20: テスト, 交差検定: dev HM: 最大エントロピー法に基づく Chunker , N=20 ☆ X Y PRP VBD DT NN I ate a cake I ate a cake Part of Speech Tagging X Y NP VP NP PRP VBD DT NN I ate a cake PRP VBD DT NN I ate a cake Text Chunking (Shallow Parsing) ☆ [Ratnaparkhi 98] の拡張, 正則化付き最大エントロピー

解析木 Y の表現方法 品詞タグ付け 基本句同定 NP VP NP VP PP NP O BOS PRP VP DT JJ NN NN MD VP TO RB # CD NN . EOS He reckons the current account deficit will narrow to only # 1.8 billon . 基本句同定 BOS NP VP NP VP PP NP O EOS PRP VP DT JJ NN NN MD VP TO RB # CD NN . He reckons the current account deficit will narrow to only # 1.8 billon .

実験結果 (品詞付与) モデル 精度 History-based ME Tagger (n-best 出力用) 95.98% 修正学習法 [Nakagawa et al. 02] 95.87% 提案手法 96.10%

実験結果 (基本句同定) モデル 精度(F値) History-based ME Chunker (n-best 出力用) 93.40 History-based SVM Chunker [Kudo et al. 00] 93.46 History-based SVM Chunker の 8システムの多数決 [Kudo et al. 01] 93.91 History-based RW Chunker [Zhang et al. 02] 93.57 History-based RW Chunker + syntactic role 素性 [Zhang et al. 02] 94.17 提案手法 94.13

考察 両タスクとも、従来手法に比べ高性能 恣意的な素性選択ではなく, 一般的, 統一的な選択 恣意的な素性選択ではなく, 一般的, 統一的な選択 素性選択パラメータ: Σ=<ξ,L,M,χ> L = 2 に固定したときの最適な M 品詞タグ付け: M=4 基本句同定: M=5 大きな部分木は過学習の原因

関連研究との比較 負例 学習 素性 欠点 CRF/FF DP MRF SVM 本手法 [Collins01] N-best MRF/Boosting Heuristics 素性の恣意性 [Collins02] N-Best Perceptron Kernel 解析コスト大 CRF/FF [Lafferty01] [Miyao 03] DP 陰に列挙 MRF (マルコフ性を満　　　たす必要) 学習コスト大 HMM-SVM [Altun 03] 〃 SVM 　　　〃 本手法 部分木　+ 　　　素性選択

まとめ 部分木を素性とする MRF の提案 一般的な手法, タスク非依存 従来手法に比べ高精度 統計的相関性に基づく素性選択 頻出部分木マイニングアルゴリズムの適用 一般的な手法, タスク非依存 英語品詞タグ付け 英語基本句同定 従来手法に比べ高精度

今後の課題 他のタスク グラフ構造への拡張 (部分グラフ) 負例の構築 学習アルゴリズム 係り受け解析, 構文解析 係り受け解析, 構文解析 グラフ構造への拡張 (部分グラフ) 頻出部分グラフマイニングアルゴリズム 負例の構築 N-best に変わる新しい手法 マルコフ連鎖モンテカルロ 学習アルゴリズム HMM-SVM