部分木に基づくマルコフ確率場と言語解析への適用

Presentation on theme: "部分木に基づくマルコフ確率場と言語解析への適用"— Presentation transcript:

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

2 統計的言語解析 (背景) 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 を導出

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

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

5 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]

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

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

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

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

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

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

12 素性関数 の設計 (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

13 素性関数 の設計 (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 正解の解析木の対数確率尤度を最大にするようλを設定

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

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

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

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

18 2. 実験

19 設定 英語品詞タグ付け 英語基本句同定 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] の拡張, 正則化付き最大エントロピー

20 解析木 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 # 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 # billon .

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

22 実験結果 (基本句同定) モデル 精度(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

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

24 関連研究との比較 負例 学習 素性 欠点 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 　　　〃 本手法 部分木　+ 　　　素性選択

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

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