Conditional Random Fields を用いた日本語形態素解析 NAIST (4月よりNTT CS研 PD) CREST 東京工業大学 NAIST 工藤拓山本薫松本裕治 1 背景  Conditional Random Fields [Lafferty 01]  Markov Random Fields の特殊系  各種系列ラベル付与問題に適用され高精度を示す品詞タグ付け[Lafferty01], テキストチャンキング[Sha 03], 固有表現抽出 [McCallum 03], HTML からのテーブル抽出[Pinto 03], 書誌情報の解析 [Peng 04]  日本語形態素解析に適用  拙作の MeCab (形態素解析器)をもっと賢くしたい  日本語形態素解析に固有の Length bias に着目  いままで問題にされることはなかった 2 日本語形態素解析 (1/2) 入力文: 東京都に住むトウキョウトニスム東京都に住む東京都に住む名詞-固有名詞-地域-一般名詞-接尾-地域助詞-格助詞-一般動詞-自立五段・マ行基本形  単語に区切る  品詞 (+ 付加情報) を付与する  活用処理 (原形を出力) 3 日本語形態素解析 (2/2)  辞書 (単語 → 品詞の写像)の存在を前提  形態素ラティス  出力系列の全候補を表現  TRIEを用いることで O(n) (n:文長) で構築可能  未知語処理  辞書引きに失敗した時に起動  字種 (ひらがな, カタカナ, 数字 etc.) によるヒューリスティックスいかなる入力に対しても形態素ラティスが生成可能 4 形態素ラティス辞書に京都 Lattice: 京都に [名詞] BOS 東名詞京名詞東京名詞 “東京都に住む” Input: 助詞, 動詞東京都 [名詞] [名詞] [接尾辞] 東京 [助詞] に名詞 … 住む [動詞] EOS [動詞] [名詞] 形態素解析=形態素ラティスから正しい系列を１つ選ぶタスク入力文出力系列 X Y  ( w1 , t1 ,, w#Y , t#Y ) 出力形態素数が系列によって変わる 5 従来手法コスト最小法から HMM, MEMM へ… 6 コスト最小法 10 京都 10 BOS 10 10 東 [名詞] 20 [名詞] 10 5 京都 20 [名詞] [接尾辞] 5 東京 [名詞] 0 20 10 30 に 20 [助詞] 住む 20 5 に [動詞] [動詞] 5 5 EOS 10 5 30 連接コスト: つながりやすさのコスト生起コスト: 出現しやすさのコスト - これらのコストの和が最大になるような系列を選択する - Viterbi Algorithm: O(n) で計算可能 (n:文長) 7 Hidden Markov Model (HMM)  コストをタグ付与済みコーパスから推定できないか?  品詞を HMM の隠れクラスとみなせば… P(Y , X )  P(T ,W )  P(W | T ) P(T )   P( wi | ti ) P(ti | ti 1 ) i 対数化 [logP(w | t )  log P(t i i i | ti 1 )] i 生起コスト連接コスト P(wi | ti )  f (wi , ti ) / f (ti ) 8 HMM の問題点その1  品詞 = 隠れクラス?  品詞は階層構造を持つ  何を隠れクラスにすればいのか? 京都名詞固有名詞地域一般京都  名詞,動詞ぐらいの浅い階層→細かい違いを区別できない  深い階層 (名詞-固有名詞-人名-姓) →データスパースネス  助詞(は,が,を) は語彙そのものを品詞としたい (語彙化)  機械処理と辞書定義のギャップ  最適階層の半自動決定 (ChaSen) [Asahara 00] 9 HMM の問題点その2  複数の情報を統合しにくいオーバラップする素性京都に住む名詞固有名詞地域一般京都助詞格助詞一般 φ に動詞自立 φ φ 住む階層間スムージング字種: (ひらがな、漢字) 部分文字列活用五段・カ行促音便基本形 HMM はモデルの制約上、これらの多種多様な情報を同時にとらえにくい10 Maximum Entropy Markov Model [McCallum 00]  複数の素性が柔軟に使える汎用的な識別モデル (discriminative model) を使おう  Maximum Entropy Model の順次適用 P(に、助詞|都,接尾) > P(に,動詞|都,接尾) に P(東|BOS) < P(東京|BOS) BOS 東都 [助詞] [名詞] [接尾辞] に東京 [動詞] [名詞] P(Y | X )   p( wi , ti | wi 1 , ti 1 ) i 別名: History-based method 11 P(Y | X )   p( wi , ti | wi 1 , ti 1 ) i MEMM の問題点 (1/2)  Label bias [Lafferty 01] 0.4 C D 0.6 A BOS 0.4 0.6 B 1.0 1.0 1.0 E EOS 1.0 P(A, D | x) = 0.6 * 0.6 * 1.0 = 0.36 P(A,D|x) < P(B,E|x) P(B, E | x) = 0.4 * 1.0 * 1.0 = 0.4 分岐数の少ない経路が優先される 12 P(Y | X )   p( wi , ti | wi 1 , ti 1 ) i MEMM の問題点 (2/2)  Length bias 0.4 C D 0.6 A BOS 0.4 0.6 B 1.0 1.0 EOS 1.0 P(A, D | x) = 0.6 * 0.6 * 1.0 = 0.36 P(A,D|x) < P(B|x) P(B | x) = 0.4 * 1.0 = 0.4 分割数の少ない経路(小分割)が優先される (最長一致のヒューリスティクスが有効なため, 無視されてきた) 13 Bias の影響を受ける原因  正解の系列のみを用いて学習  学習されなかった系列の確率値は均一に分布しやすい  エンコードとデコードの処理のギャップ京都に [名詞] BOS 京東 [名詞] [名詞] 都 [助詞] [接尾辞] に東京 [動詞] [名詞] BOS EOS 14 Conditional Random Fields [Lafferty et al. 01]  HMM, MEMM の問題点を解決  コスト最小法を一般化  識別モデルによる統計的コスト推定 15 コスト最小法 = 線形モデル京都 10 BOS 10 10 東 [名詞] [名詞] 10 5 京 [名詞] 東京 20 [接尾辞] 5 20 に 0 都 20 30 20 10 [助詞] 住むに [動詞] 20 5 [動詞] [名詞] 20 .. 30 EOS 10 名詞-固有名詞-東京 … 名詞-接尾大域素性ベクトル F(Y,X) = (… Λ 5 5 5 BOS-名詞コストベクトル 20 = (… <名詞-固有名詞>-接尾名詞-東京 …1 … … 1 … … 1 … 1 … …1 … … 1 … ) …0 … …20 … …20 … 20… … 30… …30 …) コスト値 = Λ・ F(Y,X) (内積) 素性ベクトルとして定式化 = 複数の情報を表現字（漢)-名詞 16  1 : ti 1  名詞, ti  助詞, f1234 ( wi 1 , ti 1 , wi , ti )   それ以外 0 : Conditional Random Fields  P(Y|X) を単一の指数分布モデルで表現 Y のコスト exp(Λ  F(Y , X )) P(Y | X )  ZX exp( k  f k ( wi 1 , ti 1 , wi , ti ) i k  大域素性ベクトル ZX ZX   exp(Λ  F(Y ' , X )) コスト Y ' ( X ) ( X ) : 出力経路の候補集合 ~ 非常に大きいすべての候補を考慮して, 条件付き確率を計算 17 CRF のエンコード (1/3)  最尤推定 ˆ  arg max L Λ Λ Λ LΛ   学習データ: T  Y , X  N j K ||  ||1 log(P(Y j | X j ))  C   j 1 ||  ||2 N j j 1 MAP推定過学習の低減   expΛ  F(Y j , X j )  Λ  F (Y ' , X j )  j log Y '   ( X ) j   正解のコストと残り全候補のコスト差を大きくする 18 正解を他と識別する＝識別モデル CRF のエンコード (2/3) LΛ  k  F (Y , X k j j  )  EP (Y | X j ) Fk (Y , X j )  j  Ok  Ek  0 素性 k の出現頻度素性 k のモデル分布での期待値期待値の計算: 単純には全候補 Y を列挙すればよいが, 文長に対し指数的に増えるので事実上困難 19 CRF のエンコード (3/3)  Forward-Backward (Baum-Welch) の変種 E P (Y | X ) Fk (Y , X )   BOS  w ',t ' , w,t α  f k  w' , t ' , w, t  w’,t’ exp() ZX w,t  w ',t ' β    exp  k ' f k '  w' , t ' , w, t     k'  ZX EOS α’ w’,t’ α’ w’,t’ α’ w’,t’ w ,t α w,t      ' exp  k  f k  w' , t ' , w, t   k  20 bos  eos  1, Z X  eos  bos CRF のデコード Yˆ  arg max P(Y | X ) Y  ( X )  arg max Λ  F(Y , X ) Y  ( X )  コストを最大にする系列 Y を選択  Viterbi Algorithm をそのまま適用可能  コスト最小法と同一技術 (これまでデコーダがそのまま使える) 21 CRF まとめ  HMM, MEMM の問題点を解決  コスト最小法を一般化  識別モデルによる統計的コスト推定柔軟な素性設計が可能 Bias に強い HMM × MEMM ○ CRF ○ △ × ○ 22 実験  HMM, MEMM, CRF の精度の比較  Length bias の影響調査 23 実験データ KC (JUMAN) RWCP (ChaSen) 毎日新聞 95 毎日新聞 94 JUMAN 3.61 (190万) 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 ソース辞書 (size) 学習形態素数テスト文数テスト形態素数素性数 24 C++にて実装, XEON 2.8Ghz, 4.0Gbyte 主記憶, L-BFGS-B (最適化アルゴリズム) 素性 f1234 ( wi 1 , ti 1 字種: (数字,漢字..) 部分文字列文字列長  1 : ti 1  名詞, ti  助詞, , wi , ti )   0 : それ以外京都に住む名詞固有名詞地域一般京都助詞格助詞一般 φ に動詞自立 φ φ 住む活用五段・カ行促音便基本形階層間スムージング語彙化助詞、助動詞、一部の動詞オーバラップする素性 25 予稿集 p.94 表2参照評価 F = 2・再現率・精度再現率 + 精度再現率= 正解数コーパス中の形態素数精度 = 正解数システムの形態素数  3基準  seg: 単語区切りが合えば正解  top: 単語区切り＋品詞のトップ階層が合えば正解  all: 全情報が合えば正解 26 結果 KC RWCP seg top all seg top all CRF 98.96 98.31 96.75 CRF 99.11 98.72 97.65 HMM 96.22 94.99 91.85 HMM 98.82 98.10 95.90 MEMM 96.44 95.81 94.28 ChaSen 98.86 98.38 97.00 98.70 98.09 94.35 [Uchimoto01] JUMAN [Asahara00] HMM: 一番細かい品詞階層を隠れクラスとみなした HMM JUMAN: 人手によりコスト付けられた最小コスト法 ChaSen: 同コーパスで学習、テストした ChaSen 27 Length bias の影響調査 (1/2) （KC データ) 小分割 HMM CRF MEMM 306 (44%) 79 (40%) 416 (70%) 過分割 387 (56%) 120 (60%) 183 (30%)  HMM, CRF: 誤り数の比に大差はない  MEMM: 小分割の誤り数が絶対的, 相対的に多い → Length Bias の影響注: 予稿集にこの結果は記載されておりません 28 Length-bias の影響調査 (2/2) MEMMの出力（KC データ) ロマン派ロマンは海にかけたロマンは内心ない心荒波に負けない心  辞書中の表記の不整合がエラーの原因とされていた  Length Bias と考えるのがむしろ自然ではないか [Uchimoto 01]  CRF では正しく解析できる  MEMM では小分割が選ばれやすい 29 考察: CRF v.s ChaSen (拡張 HMM)  ChaSen (拡張 HMM) [Asahara00]  文脈毎に異なる品詞階層  単語-品詞間スムージング  語彙化人手の介在が多い  これらの拡張は CRF では素性関数の設計に還元され, 直接的に実現可能 30 まとめ  CRFを日本語形態素解析に適用  HMM, MEMM の問題点を解決  柔軟な素性設計が可能  Label bias / Length bias に強い  Label bias は無視できない問題  デコード時の技術はコスト最小法と同一 HMM MEMM CRF 柔軟な素性設計が可能 × ○ ○ Bias に強い △ × ○ 31 今後の課題  詳細な調査  Bias の存在を(もっと)定量的に調査  素性を一致させたうえでの精度やbias の影響を調査  tri-gram 素性  全 tri-gram は速度, 空間的に難しい  現実的な素性選択手法により, 必要な tri-gram のみを選択, 適用  中国語, タイ語 … etc.  CRFに基づく次期 MeCab をリリース 32 系列ラベリングのための線形識別モデル  線形モデル → ロス関数の定義から多種多様なモデル     CRF  -  log  expΛ  F (Y j , X j )  Λ  F (Y ' , X j )   Y ' ( X )  j j      SVM  -  max 0, 1   Λ  F (Y j , X j )  Λ  F (Y ' , X j )    j Y ' ( X j )    Boo  -   expΛ  F (Y j , X j )  Λ  F (Y ' , X j )  j Y ' ( X j )  HM-SVM, Seq.-Labeling AdaBoost [Altun 03]  HM-SVM が経験的に高精度  CRF の利点: Forward-Backward による高効率な学習 33 CRF の学習 (エンコード) (4/4)  MAP 推定 (過学習の低減) LΛ   1 ||  ||1 C log(P(Y j | X j ))   2 ||  ||2 j 1 N L1-CRF (Laplacian prior)  多くのλに 0 の値を与え決定的な素性選択, コンパクトなモデル  素性の大半が irrelevant 場合に良い結果  L2-CRF (Gaussian prior)  全λに非ゼロの値  素性の大半が relevant な場合に良い結果  C: 2つの項のバランス（交差検定等で決定) 34 結果 KC RWCP seg top all seg top all L1-CRF (C=3.0) 98.80 98.14 96.55 L1-CRF (C=3.0) 99.00 98.58 97.30 L2-CRF (C=1.2) 98.96 98.31 96.75 L2-CRF (C=1.2) 99.11 98.72 97.65 HMMbigram 96.22 94.99 91.85 HMMbigram 98.82 98.10 95.90 MEMM 96.44 95.81 94.28 E-HMM 98.86 98.38 97.00 98.70 98.09 94.35 [Uchimoto01] JUMAN [Asahara00] 35 考察: L1-CRF v.s L2-CRF  L2-CRF が若干高精度  L1-CRF はコンパクトな素性を構築  アクティブな素性数  L1: 90,163 (KC) 101,757 (RWCP)  L2: 791,798 (KC) 580,032 (RWCP) 36