Conditional Random Fields を用いた 日本語形態素解析 NAIST (4月よりNTT CS研 PD) 工藤 拓 CREST 東京工業大学 山本 薫 NAIST 松本　裕治

背景 Conditional Random Fields [Lafferty 01] 日本語形態素解析に適用 Markov Random Fields の特殊系 各種系列ラベル付与問題に適用され高精度を示す 品詞タグ付け[Lafferty01], テキストチャンキング[Sha 03], 固有表現抽出[McCallum 03], HTML からのテーブル抽出[Pinto 03], 書誌情報の解析[Peng 04] 日本語形態素解析に適用 拙作の MeCab (形態素解析器)をもっと賢くしたい 日本語形態素解析に固有の Length bias に着目 いままで問題にされることはなかった

日本語形態素解析 (1/2) 単語に区切る 品詞 (+ 付加情報) を付与する 活用処理 (原形を出力) 入力文: 東京都に住む 入力文: 東京都に住む 東京 トウキョウ 東京 名詞-固有名詞-地域-一般 都 ト 都 名詞-接尾-地域 に ニ に 助詞-格助詞-一般 住む スム 住む 動詞-自立 五段・マ行 基本形 単語に区切る 品詞 (+ 付加情報) を付与する 活用処理 (原形を出力)

日本語形態素解析 (2/2) 辞書 (単語 → 品詞の写像)の存在を前提 形態素ラティス 未知語処理 出力系列の全候補を表現 TRIEを用いることで O(n) (n:文長) で構築可能 未知語処理 辞書引きに失敗した時に起動 字種 (ひらがな, カタカナ, 数字 etc.) によるヒューリスティックス いかなる入力に対しても形態素ラティスが生成可能

形態素ラティス BOS EOS 形態素解析=形態素ラティスから正しい系列を１つ選ぶタスク 入力文 出力系列 京都 に 東 京 都 住む に 辞書 に 助詞, 動詞 東 名詞 京　 名詞 東京　名詞 京都 名詞 … Input: “東京都に住む” Lattice: 京都 [名詞] に [助詞] 東 [名詞] 京 [名詞] 都 [接尾辞] 住む [動詞] BOS EOS に [動詞] 東京 [名詞] 形態素解析=形態素ラティスから正しい系列を１つ選ぶタスク 入力文 出力系列 出力形態素数が系列によって変わる

従来手法 コスト最小法から HMM, MEMM へ…

コスト最小法 生起コスト: 出現しやすさのコスト 連接コスト: つながりやすさのコスト BOS EOS 30 5 10 生起コスト: 出現しやすさのコスト 京都 [名詞] 10 20 5 連接コスト: つながりやすさのコスト に [助詞] 東 [名詞] 京 [名詞] 都 [接尾辞] 住む [動詞] BOS EOS に [動詞] 東京 [名詞] - これらのコストの和が最大になるような系列を選択する - Viterbi Algorithm: O(n) で計算可能 (n:文長)

Hidden Markov Model (HMM) コストをタグ付与済みコーパスから推定できないか? 品詞を HMM の隠れクラスとみなせば… 対数化 生起コスト 連接コスト

HMM の問題点 その1 品詞 = 隠れクラス? 品詞は階層構造を持つ 何を隠れクラスにすればいのか? 機械処理と辞書定義のギャップ 京都 名詞 固有名詞 地域 一般 品詞 = 隠れクラス? 品詞は階層構造を持つ 何を隠れクラスにすればいのか? 名詞,動詞ぐらいの浅い階層→細かい違いを区別できない 深い階層 (名詞-固有名詞-人名-姓) →データスパースネス 助詞(は,が,を) は語彙そのものを品詞としたい (語彙化) 機械処理と辞書定義のギャップ 最適階層の半自動決定 (ChaSen) [Asahara 00]

HMM の問題点 その2 複数の情報を統合しにくい 京都 に 住む HMM はモデルの制約上、これらの多種多様な情報を同時にとらえにくい オーバラップする素性 京都 名詞 固有名詞 地域 一般 に 助詞 格助詞 一般 φ 住む 動詞 自立 φ 五段・カ行促音便 基本形 階層間 スムージング 活用 字種: (ひらがな、漢字) 部分文字列 HMM はモデルの制約上、これらの多種多様な情報を同時にとらえにくい

Maximum Entropy Markov Model [McCallum 00] 複数の素性が柔軟に使える汎用的な 識別モデル (discriminative model) を使おう Maximum Entropy Model の順次適用 に [助詞] [動詞] P(に、助詞|都,接尾) > P(に,動詞|都,接尾) BOS 東 [名詞] 東京 P(東|BOS) < P(東京|BOS) 都 [接尾辞] 別名: History-based method

MEMM の問題点 (1/2) C A D B E BOS EOS P(A, D | x) = 0.6 * 0.6 * 1.0 = 0.36 Label bias [Lafferty 01] 0.4 C 1.0 0.6 BOS A D EOS 1.0 0.6 0.4 1.0 B E 1.0 P(A, D | x) = 0.6 * 0.6 * 1.0 = 0.36 P(B, E | x) = 0.4 * 1.0 * 1.0 = 0.4 P(A,D|x) < P(B,E|x) 分岐数の少ない経路が優先される

MEMM の問題点 (2/2) C A D B BOS EOS P(A, D | x) = 0.6 * 0.6 * 1.0 = 0.36 Length bias 0.4 C 1.0 0.6 BOS A D EOS 0.6 1.0 0.4 1.0 B P(A, D | x) = 0.6 * 0.6 * 1.0 = 0.36 P(B 　　| x) = 0.4 * 1.0 = 0.4 P(A,D|x) < P(B|x) 　　　　　分割数の少ない経路(小分割)が優先される (最長一致のヒューリスティクスが有効なため, 無視されてきた)

Bias の影響を受ける原因 正解の系列のみを用いて学習 学習されなかった系列の確率値は均一に分布しやすい エンコードとデコードの処理のギャップ 京都 [名詞] 京 BOS 東 [名詞] 東京 都 [接尾辞] に [助詞] [動詞] BOS EOS

Conditional Random Fields [Lafferty et al. 01] HMM, MEMM の問題点を解決 コスト最小法を一般化 識別モデルによる統計的コスト推定

コスト最小法 = 線形モデル BOS EOS 素性ベクトルとして定式化 = 複数の情報を表現 コスト値 = Λ・ F(Y,X) (内積) 京都 [名詞] 30 20 10 に [助詞] 20 10 東 [名詞] 京 [名詞] BOS 20 都 [接尾辞] 住む [動詞] 20 EOS 10 5 に [動詞] 5 5 5 素性ベクトルとして定式化 = 複数の情報を表現 <名詞-固有名詞>-接尾 名詞-固有名詞-東京 20 .. 30 … 　1 … …1 … … 1 … 20… … 30… …30 … 字（漢)-名詞 10 10 5 10 東京 [名詞] 20 5 20 BOS-名詞 名詞-接尾 名詞-東京 大域素性ベクトル F(Y,X) = (… …1 … … 1 … … 1 … ) コストベクトル　 Λ = (… …0 … …20 … …20 … ) コスト値 = Λ・ F(Y,X)　　(内積)

Conditional Random Fields 大域素性ベクトル コスト Conditional Random Fields P(Y|X) を単一の指数分布モデルで表現 Y のコスト : 出力経路の候補集合 ~ 非常に大きい すべての候補を考慮して, 条件付き確率を計算

CRF のエンコード (1/3) 最尤推定 正解を他と識別する＝識別モデル 正解のコストと残り全候補のコスト差を大きくする 学習データ: MAP推定 過学習の低減 正解のコストと残り全候補のコスト差を大きくする 正解を他と識別する＝識別モデル

CRF のエンコード (2/3) 期待値の計算: 単純には全候補 Y を列挙すればよいが, 文長に対し指数的に増えるので事実上困難 素性 k の出現頻度 素性 k のモデル分布での期待値 期待値の計算: 単純には全候補 Y を列挙すればよいが, 文長に対し指数的に増えるので事実上困難

CRF のエンコード (3/3) Forward-Backward (Baum-Welch) の変種 α β w’,t’ w,t w,t BOS w’,t’ w,t EOS α β exp() w,t w’,t’ α’ α

CRF のデコード コストを最大にする系列 Y を選択 Viterbi Algorithm をそのまま適用可能 　コスト最小法と同一技術 (これまでデコーダがそのまま使える)

CRF まとめ HMM, MEMM の問題点を解決 コスト最小法を一般化 識別モデルによる統計的コスト推定 HMM MEMM CRF × ○ 柔軟な素性設計が可能 × ○ Bias に強い △

実験 HMM, MEMM, CRF の精度の比較 Length bias の影響調査

実験データ KC (JUMAN) RWCP (ChaSen) ソース 毎日新聞 95 毎日新聞 94 辞書 (size) 品詞体系 学習文数 IPADIC 2.70 (38万) 品詞体系 2階層品詞, 活用型,活用形, 基本形 4階層品詞, 活用型,活用形, 基本形 学習文数 7,958 10,000 学習形態素数 198,514 265,631 テスト文数 1,246 25,743 テスト形態素数 31,302 655,710 素性数 791,798 580,032 C++にて実装, XEON 2.8Ghz, 4.0Gbyte 主記憶, L-BFGS-B (最適化アルゴリズム)

素性 京都 に 住む 名詞 固有名詞 地域 一般 助詞 格助詞 一般 φ 動詞 自立 φ 五段・カ行促音便 基本形 字種: (数字,漢字..) 部分文字列 文字列長 活用 階層間 スムージング 語彙化 助詞、助動詞、 一部の動詞 オーバラップする素性 予稿集 p.94 表2参照

評価 3基準 2・再現率・精度 F = 再現率 + 精度 正解数 再現率= コーパス中の形態素数 正解数 精度 = システムの形態素数 再現率 + 精度 正解数 再現率= コーパス中の形態素数 正解数 精度 = システムの形態素数 3基準 seg: 単語区切りが合えば正解 top: 単語区切り＋品詞のトップ階層が合えば正解 all: 全情報が合えば正解

結果 KC RWCP seg top all seg top all 98.96 98.31 96.75 96.22 94.99 91.85 CRF 98.96 98.31 96.75 HMM 96.22 94.99 91.85 MEMM [Uchimoto01] 96.44 95.81 94.28 JUMAN 98.70 98.09 94.35 seg top all CRF 99.11 98.72 97.65 HMM 98.82 98.10 95.90 ChaSen [Asahara00] 98.86 98.38 97.00 HMM: 一番細かい品詞階層を隠れクラスとみなした HMM JUMAN:　人手によりコスト付けられた最小コスト法 ChaSen: 同コーパスで学習、テストした ChaSen

Length bias の影響調査 (1/2) 小分割 過分割 HMM 306 (44%) 387 (56%) CRF 79 (40%) （KC データ) 小分割 過分割 HMM 306 (44%) 387 (56%) CRF 79 (40%) 120 (60%) MEMM 416 (70%) 183 (30%) HMM, CRF: 誤り数の比に大差はない MEMM: 小分割の誤り数が絶対的, 相対的に多い → Length Bias の影響 注: 予稿集にこの結果は記載されておりません

Length-bias の影響調査 (2/2) 辞書中の表記の不整合がエラーの原因とされていた [Uchimoto 01] （KC データ) MEMMの出力 ロマン派 内心 ロマンは 海 に かけた ロマン は ない心 荒波 に 負け ない 心 　辞書中の表記の不整合がエラーの原因とされていた [Uchimoto 01] 　Length Bias と考えるのがむしろ自然ではないか CRF では正しく解析できる MEMM では小分割が選ばれやすい

考察: CRF v.s ChaSen (拡張 HMM) ChaSen (拡張 HMM) [Asahara00] 文脈毎に異なる品詞階層 単語-品詞間スムージング 語彙化 これらの拡張は CRF では素性関数の設計に還元され, 直接的に実現可能 人手の介在が多い

まとめ CRFを日本語形態素解析に適用 HMM MEMM CRF × ○ △ HMM, MEMM の問題点を解決 柔軟な素性設計が可能 Label bias / Length bias に強い Label bias は無視できない問題 デコード時の技術はコスト最小法と同一 HMM MEMM CRF 柔軟な素性設計が可能 × ○ Bias に強い △

今後の課題 詳細な調査 tri-gram 素性 中国語, タイ語 … etc. CRFに基づく 次期 MeCab をリリース Bias の存在を(もっと)定量的に調査 素性を一致させたうえでの精度やbias の影響を調査 tri-gram 素性 全 tri-gram は速度, 空間的に難しい 現実的な素性選択手法により, 必要な tri-gram のみを選択, 適用 中国語, タイ語 … etc. CRFに基づく 次期 MeCab をリリース

系列ラベリングのための線形識別モデル 線形モデル → ロス関数の定義から多種多様なモデル HM-SVM, Seq.-Labeling AdaBoost [Altun 03] HM-SVM が経験的に高精度 CRF の利点: Forward-Backward による高効率な学習

CRF の学習 (エンコード) (4/4) MAP 推定 (過学習の低減) L1-CRF (Laplacian prior) 多くのλに 0 の値を与え決定的な素性選択,　コンパクトなモデル 素性の大半が irrelevant 場合に良い結果 L2-CRF (Gaussian prior) 全λに非ゼロの値 素性の大半が relevant な場合に良い結果 C: 2つの項のバランス　（交差検定等で決定)

結果 KC RWCP seg top all seg top all 98.80 98.14 96.55 98.96 98.31 96.75 L1-CRF (C=3.0) 98.80 98.14 96.55 L2-CRF (C=1.2) 98.96 98.31 96.75 HMM-bigram 96.22 94.99 91.85 MEMM [Uchimoto01] 96.44 95.81 94.28 JUMAN 98.70 98.09 94.35 seg top all L1-CRF (C=3.0) 99.00 98.58 97.30 L2-CRF (C=1.2) 99.11 98.72 97.65 HMM-bigram 98.82 98.10 95.90 E-HMM [Asahara00] 98.86 98.38 97.00

考察: L1-CRF v.s L2-CRF L2-CRF が若干高精度 L1-CRF はコンパクトな素性を構築 アクティブな素性数 L1: 90,163 (KC) 101,757 (RWCP) L2: 791,798 (KC) 580,032 (RWCP)