高村本でCRFのお勉強をしたのでメモ

計算機科学

「言語処理のための機械学習入門」通称高村本でCRF(Conditional Random Fields, 条件付き確率場)のお勉強をしたのでメモしておく。


まず最初に世界には単純な線形識別関数があった。

y = wx

この線形識別関数で、素性はxそのもの。人々はよりリッチな素性が欲しくなったので事例xと正解ラベルtによって定まる素性φ(x, t)を思いついた。つまり

y = wφ(x, t)

である。さらにこれを確率化したくなった。確率とはつまり

1: P(x) >= 0
2: ΣP(x) = 1

を満たす関数のこと。まずは1:を考える。つねにゼロ以上の値をとればよいのでyをexp(y)とする。こうすると

y = -∞  =>  exp(y) = 0
y =  ∞  =>  exp(y) = ∞

となりゼロ以上になることが保障される。つぎに2:を考える。足して1にするには全てのexp(y)の和で各exp(y)を割ってやれば良い。つまり

P(y) = exp(y) / Z
Z = Σexp(y)

となる。このP(y)が確率化された線形識別関数。その名も対数線形モデル(log linear model)。またの名を最大エントロピーモデル。さらに素性φ(x, t)のxとtが構造化されていて{x1, x2, ... , xn, t1, t2, ... , tn}とかなるとCRFになる。


さて無事確率モデルができたので、このモデルの重みwを導出したくなった。それには損失関数を定義することから始める。といってもこれは単純で、折角確率化したので負の対数尤度を損失関数とすれば良い。つまり

Loss(w) = -Σ_xlogP(y)
        = Σ_x{logZ - y}
        = Σ_x{logZ - wφ(x, t)}

である。損失関数が決まったので学習を始める。これには定番のSGD(stochastic gradient decend, 確率的勾配法)を使う。SGDとはつまり

w += ∂Loss(w) / ∂w

∂Loss(w) / ∂w = ∂Σ_x{logZ - wφ(x, t)} / ∂w
                = Σ_x{Σ_y{P(y)φ(x, t)} - φ(x, t)}

とすること。さてここで大問題なのがΣ_y{P(y)φ(x, t)}。これはlogZをwで微分した結果でてきた産物。線形識別関数の時はZで正規化しなかったのでこの項はなかった。が確率化の際にZで割ってしまったのでこの項がある。
この項のなにがヤバイかというとP(y)をΣ_yで足しあわせている。つまり考えうるすべてのyについて確率を計算しろと言っている。これが単純にyはAからZの値をとりますよー、とかだと平和。だがCRFのように構造学習をする場合「B, I, I, O」とか「B, I, B, I」とかtのとりうる値が膨大な組み合わせになる。


そこでこの問題を解決するためにForward-Backwardアルゴリズムを使うのだ！ということらしい。とここまで読んで識別モデルめんどくせー。もう構造化パーセプトロン(Structured Perceptron)でいいじゃん。などと思ったのだった。
ちなみに識別時にはかの有名なViterbiアルゴリズムを使えばOKだよ。