CRFのヘシアン

坪井さんの論文がAAAIに通りました。おめでとうございます。AAAI記念ということで、宣伝その２。今回はCRFのヘシアンを具体的に計算してみます。

入力文x、ラベル系列y、重みベクトルwに対して、CRFの対数尤度関数は



です。fは特徴ベクトルで、普通f(x, y)と書きますが省略します。Zは分配関数です。正則化項を無視すれば、学習データに対するこの値の総和、



が目的関数でした。この勾配はきれいな形をしていて、



という形でかけます。NLP屋さん的にはここでおしまいですが、実はもう１回微分した形、つまりヘシアンもきれいな形で求まります。では頑張って微分しましょうというのが今回の主旨。

まず、第１項のΣ_yfの項はwで微分すると消えます。考えないといけないのは第２項のE[f]の部分だけです。ベクトルの微分なのでちょっとめんどくさいです。もとの式に戻しましょう。



ではwで微分しましょう。まずは積の微分公式です。



第１項は簡単ですね。



第２項は1/Zの微分ですが、これも勾配の時と同じように落ち着いて計算すれば綺麗に消えていきます。



結果的に、全体では



になりました。なんともシンプル。ところで、勾配を求める時もものすごくキレイに期待値が出てきますよね。何回か手を動かしていると、その心がなんとなく分かってきます。イメージで言うと、expの微分がexpである（自分自身である）ということ、そしてexpの中のfwが微分されて、fが外に出てくるというのが結構ポイントのように思います。前者の特徴がP(y|x)を生み出し、後者がfを生み出し、全体でEを生み出している、そういう風に感じられます。

さて、この式から具体的な再帰式（DPの式）を導くことが出来るでしょうか。実はここまでの式変形にCRFのCRFたる特徴は使っていません。使っているのは対数線形モデルであるという特徴だけです。したがって、MEもsemi-CRFもparsingの対数線形モデルも同じ式で表せます。CRFの特徴、すなわち特徴ベクトルfがグラフィカルモデル上でのクリークに対する特徴関数の和で表せるという性質を使うのはここからです。



だとします。iはクリークにつけられたインデックスです。すると、期待値の線形性から



に分解できます。P(f_i)は各クリークが選ばれる周辺確率です。これは一般のCRFでは必ずしも効率的に計算できませんが、例えば直鎖CRF（linear-chain CRF)の場合は前向きスコアと後ろ向きスコアの積で簡単に表せることが知られています。すなわち、



です。細かいノーテーションは省略します。雰囲気で察してください（ぉ　αとβの値は動的計画法を使えば多項式時間で計算できますから、予め計算してあげれば上記のE[f]も多項式時間で計算できる、という寸法でした。lnear-chain CRFだと効率的に勾配を計算できるのは、このあたりが絡んでいます。先の@sleepy_yoshiさんの日記で省略されていたのがこの部分です。もちろん、前向き後ろ向きを内側外側にすれば構文解析ができます。


同じことを先のヘシアンに対しても適応できないか考えてみます。ところが、E[ff^T]を分解しようとしたところで詰まってしまいます。実は私は先ほど求めた式から動的計画法の式を導き出す方法をまだ編み出していません。しかし再帰式自体はもとまっていて、それが最初に紹介した坪井さんの言語処理学会の論文、及びAAAIの論文でした。個人的には、勾配の時と同じように上の式から直接きれいな形で再帰式を導き出せると思っています。実は別の導出もあるんですが、それも含めて再帰式の導出はまた今度。