CRFの更新式の導出

機械学習
  • (2011-03-29追記) 訂正版を書きました．もっとシンプルに導出できます．

昨晩，Twitterで@tkngさんがCRFの更新式の導出の計算をしていたことを知る．実は僕も時を同じくして計算していた．しかし，なかなか答えが合わない．そうこうしているうちに@tkngさんはちゃんと答えが出せたことを知る．「やぁ，奇遇ですね．僕も今夜なんだかCRFの更新式を計算したくなって，ね．」なんてことをかっこよくつぶやきたかったのだけれど，その前に朝日がのぼりそうだったのであきらめて寝た．

さて今朝起きてから見直してみたら，ゆとりもびっくり! の計算間違いをしていたことを知って，あわてて再計算．ちゃんと導出できたのでうれしくなってブログに書くことにした．


ここまでtexソースが激しくなるとは思わず，途中でちょっと後悔したけれど，達成感でいっぱい．それにしても，はてなでtex記法記述するとキレイじゃないなぁ．．


求めたい更新式は対数尤度の勾配．
CRFが訓練データが与えられた際の尤度は，

L(D; \mathbf{w}) = \prod_{\mathbf{x}_i, \mathbf{y}_i \in D} P(\mathbf{y}_i | \mathbf{x}_i)

なので，対数尤度は，

\log L(D; \mathbf{w}) = \sum_{\mathbf{x}_i, \mathbf{y}_i \in D} \log P(\mathbf{y}_i | \mathbf{x}_i).

CRFではP(\mathbf{y}|\mathbf{x})を

P(\mathbf{y}|\mathbf{x}) = \frac{\exp\{\mathbf{w}^T \Phi(\mathbf{x},\mathbf{y}\}}{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x},\mathbf{y}_j)\}

としていた．これを代入すると，

L(D; \mathbf{w}) = \sum_{\mathbf{x}_i, \mathbf{y}_i \in D} \log \frac{\exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_i\}}{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}

が得られる．これの勾配を得るために\mathbf{w}で偏微分する．自分はここでlog(A/B) = log(A)/log(B) = log(A) - log(B)log(A+B) = logA+logB (2011-03-29修正．@nokunoさんご指摘ありがとうございます．)という阿呆な勘違いをしていたため，ここで一晩ハマっていた．．．


頑張って微分をしてみる．使う道具は，

だけ．


まずは，合成関数の微分法を使って

\frac{\partial}{\partial \mathbf{w}} L(D; \mathbf{w}) = \sum_{\mathbf{x}_i, \mathbf{y}_i \in D} \frac{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}}{\exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_i\}} \left{ \frac{\partial}{\partial \mathbf{w}} \frac{\exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_i\}}{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}} \right}

後ろの部分は商の微分法で求める．

\frac{\partial}{\partial \mathbf{w}} L(D; \mathbf{w}) = \sum_{\mathbf{x}_i, \mathbf{y}_i \in D} \frac{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}}{\exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_i\}} \cdot \left{ \frac{ \Phi(\mathbf{x}_i,\mathbf{y}_j) \exp \{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} \sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} - \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} \sum_{\mathbf{y}_j \in \mathbf{Y}} \Phi(\mathbf{x}_i,\mathbf{y}_j) \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} }{\left{ \sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} \right}^2} \right}


(画面に収まり切らない方はズームダウンしてください．)


ぎょっとするけれど，ここまで来れば後は簡単．分子分母で打消し合いまくるので，心行くまで斜線を入れる．


\frac{\partial}{\partial \mathbf{w}} L(D; \mathbf{w}) = \sum_{\mathbf{x}_i, \mathbf{y}_i \in D} \left{\Phi(\mathbf{x}_i,\mathbf{y}_j) - \frac{\sum_{\mathbf{y}_j \in \mathbf{Y}} \Phi(\mathbf{x}_i,\mathbf{y}_j) \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}}{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}} \right}


括弧の中の第二項について式変換する．ふたたび
P(\mathbf{y}|\mathbf{x}) = \frac{\exp\{\mathbf{w}^T \Phi(\mathbf{x},\mathbf{y}\}}{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x},\mathbf{y}_j)\}
が出現しているので，これを置き換えるだけ．

\frac{\sum_{\mathbf{y}_j \in \mathbf{Y}} \Phi(\mathbf{x}_i,\mathbf{y}_j) \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}}{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}} = \sum_{\mathbf{y}_j \in \mathbf{Y}} \Phi(\mathbf{x}_i,\mathbf{y}_j) P(\mathbf{y}_j | \mathbf{x}_i)


以上の結果を併せて，

\frac{\partial}{\partial \mathbf{w}} L(D; \mathbf{w}) = \sum_{\mathbf{x}_i, \mathbf{y}_i \in D} \left{\Phi(\mathbf{x}_i,\mathbf{y}_j) - \sum_{\mathbf{y}_j \in \mathbf{Y}} \Phi(\mathbf{x}_i,\mathbf{y}_j) P(\mathbf{y}_j | \mathbf{x}_i) \right}


できた!! 多分合ってるはず．

勾配が求まったので，後は最急降下法でも良いし，みんな大好きL-BFGS法とかで解きましょう．どうやら最近は共役勾配法を使う[2]のが玄人の間で流行っているとか．．．

ただ，実は第二項の \sum_{y_j} ... の計算を工夫しなければいけないのだけれど，今日の目的は勾配の計算だったので，詳しくは高村本[1]などをご参照のこと．

一部コピペを使ったとはいえ，以下の数式を一発で書けたときにはめちゃくちゃ気持ちよかった．．．何やってるんだろ．．．

[tex: \frac{\partial}{\partial \mathbf{w}} L(D; \mathbf{w}) = \sum_{\mathbf{x}_i, \mathbf{y}_i \in D} \frac{\sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\}}{\exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_i\}} \cdot \left{ \frac{ \Phi(\mathbf{x}_i,\mathbf{y}_j) \exp \{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} \sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} - \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} \sum_{\mathbf{y}_j \in \mathbf{Y}} \Phi(\mathbf{x}_i,\mathbf{y}_j) \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} }{\left{ \sum_{\mathbf{y}_j \in \mathbf{Y}} \exp\{\mathbf{w}^T \Phi(\mathbf{x}_i,\mathbf{y}_j)\} \right}^2} \right}]

参考文献