Conditional Random Fields(CRF)入門その2 -ブログ資料と勾配について-

CRFが未だに実装かつフルに理解できていないです。CRFは一筋縄ではいかないことがブログ資料の多さからもわかります。ただ(一部の?)構造予測問題においては今流行りの多層Neural NetworkよりF1値が高いことが伺えますので、未だに重要な手法の一つなので、頑張って理解します。IME本に沿って書いており、ただでさえ無い行間を更にしつこく埋めていこう、という試みです。不適切だったら消しますのでご連絡ください。また、間違いがあった場合も指摘して頂けるとありがたいです。

前回(Conditional Random Fields(CRF)入門その1 -主な参考資料と目的関数-)の続きで、今回は勾配gに関してです。

は素性関数の集合、が学習データの一入力系列であり、が学習データの一ラベル系列です。添字がありますが、ここでは一変数ではなく、ベクトルの一例を示しています。添字がないものはベクトルの集合として認識してください。第一項が正解の系列に対して重みを足す、第二項で正解の系列と間違っている系列全ての重みをその系列の現在の確率と掛けあわせてから引きます。

勾配に関しては主に実際に計算(実装)するときにいかに効率良く実装するか、という話がメインです。SGDを用いて最適化する際は、重みの更新回数だけ勾配を計算するので、より効率が良い方がより早く学習が終わります。

HMMでも利用されている前向き後ろ向きアルゴリズムが一番効率が良く勾配を計算できます。効率を重視しなければ他の方法でもできます。勾配のどの部分がそんなにネックになっているんでしょうか?答えはの部分です。の定義をもう一回思い出してみましょう。


ただし、

このZは『すべての経路に対して「その経路で有効になる素性の重みの和に対するexp」』(IME本、p.201)なので、愚直な実装ならラベル列が取り得る全ての経路に関して計算する必要があります。これをできるだけ簡単にする試みが前向き後ろ向きアルゴリズムです。

前向き後ろ向きアルゴリズム

を前向きアルゴリズムによって算出された変数、
を後ろ向きアルゴリズムによって算出された変数とするのが通例みたいです。

前節で出てきた「ある経路で有効になる素性」をここでは「ある経路」=「ある経路にある一ノード」と読み換えて進めていきます。その為、ここでは(あとIME本では)を「ノードNに対する」と定義します。

ではとはなんでしょう?は「前向きにグラフを辿ってきて、ノードNに行き着く全ての経路のの和」であります。まだ少し曖昧に感じるので、IME本p.202に出てくる

  1. スタートからゴールに進む経路においては積を取る
  2. 合流する経路はそれらの経路に対する確率の和を取る

の2点をポイントととして補足しておきます。

は以上の説明における「前向き」を「後ろ向き」に置き換えたものです。

これらを利用してはノードNに対する素性関数として、


or

とすれば効率よく勾配が計算できます(途中ちょっと端折りました)。後は更新式が収束するまで重みwを更新していけば学習したモデルが構築できます。

次回はいよいよ学習したモデルを用いて、Viteribiアルゴリズムによる予測について書きます。

雑記

IME本に関するすごい方々の議論で出てきた「生成モデルと識別モデルの比較」に関する論文は面白そうなんで今度読んでみたいですね。

参考資料

IME

日本語入力を支える技術 ?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

日本語入力を支える技術 ?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

L-BFGSを使う理由(CRFのライブラリの一つであるCRFsuiteでは使っていますね)

http://blog.unnono.net/2011/04/newton-cg.html