Conditional Random Fields（CRF）入門その3 -CRFの新しい論文とViterbiアルゴリズムについて-

Conditional Random Fields（CRF）入門その2 -ブログ資料と勾配について-の続きです。少し手抜きになっていますがご了承ください。
感動の最終章です。間違っている場合は訂正して頂けますと助かります。

Viterbiアルゴリズムは動的計画法です。直前の状態からどの遷移の確率が一番高いかを計算します。それだけです。

例えば赤い線の遷移の対象としているノードへの一番高い確率を計算すると、直前の状態としてあり得るノードからの確率を計算します。以下の例だと0.5の遷移確率が一番高いので対象としているノードまでの経路の確率は0.5となります。

あとCRFについて重要な補足ですが、CRFは「最大エントロピー法（対数線形モデル）を系列ラベリングに適用したモデル」です。最大エントロピー法の利点の一つは「互いに依存している素性も素性として入れられる」ことにあります。Linear-Chain CRFの場合、素性関数の引数として直前の状態と現在の状態が入っているので系列となっていることがわかります。

注意点としましてはどこかで読んだ資料でViterbiアルゴリズムは局所最適解に陥りやすい、と読んだ覚えがあります。まあ前のノードしか見てないのでそうなりますね。。。
2014年3月30日訂正：
linear chain CRFの目的関数は凹関数なので、局所最適解は存在しません。ただ素性の設計次第で大域的最適解がViterbiアルゴリズムによる求まらない可能性はあります。

最後に最近僕が面白そうだなと思うCRFの一種を紹介します。
DCRFと呼ばれる複数の系列を同時に推定するCRFです。これはパイプラインを通さずに同時にできる、というParsingの分野でやられていたDual Decomposition？（自信ないです。。。）と似たような考え方、と僕は捉えております。

Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data
Mining Informal Language from Chinese Microtext:Joint Word Recognition and Segmentation

２番目の論文で提案されたFactorial CRFは１番目の論文にて提案されたDCRFの一種で中国語の崩れ検出と単語分割を同時にやっています。１番目の論文曰く、DCRFはLinear-chain CRFと比べて同じ性能を発揮するまでに必要な学習データが少ないみたいです。

あとSHDCRFというのもあるみたいですね。今知りました。

CRFは約10年前に提案された手法ですが未だに現役の手法＝ブレイクスルーがないと言えるんでしょうか？今後も系列ラベリングモデルの変遷には注目しいきます