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の論文でした。個人的には、勾配の時と同じように上の式から直接きれいな形で再帰式を導き出せると思っています。実は別の導出もあるんですが、それも含めて再帰式の導出はまた今度。

Newton-CG法とは

先日、@sleepy_yoshiさんがCRFの目的関数の導関数を求める記事を書いていました。ここに便乗して、@yuutatさんたちとやっていたNewton-CG法について解説を書きます。・・・、と思ってたのですが引っ越してから未だにネットにつながらなくてなかなか更新できませんでした。今、マックで書いてますｗ

まず、Newton法のおさらいから。Newton法は、目的関数を２次関数で近似して、その最小値（放物線の頂点）に更新する方法です。２次関数による近似は現在のパラメータx₀の周りでテーラー展開すればよいです。



これが最小値を取るのはxで微分した値が0になる時で、それは



に更新すればよいことがわかります。xがベクトルの場合も同様で、この場合、１階微分がベクトル（勾配）g、２階微分が行列（ヘシアン）Hになることに気をつけます。



さて、CRFの目的関数に関してこれを適用することを考えます。勾配は@sleepy_yoshiさんの日記のとおり計算できます。問題はヘシアンの逆行列です。この計算には２つの難しさがあります。ひとつは、xの次元が大きすぎるため、ヘシアン自体を陽に計算できません。もうひとつは、その逆行列は尚更計算できません。

この問題を解決するために、ヘシアンの逆行列を近似するのが擬ニュートン法でした。よく知られたL-BFGSは、反復の直近の勾配を使ってこれを近似します。しかし、実はもっと正確に計算できます。欲しいのはヘシアンでもヘシアンの逆行列でもなく、ヘシアンの逆行列を勾配に掛けた値です。つまり、欲しいのはベクトルです。ヘシアンもヘシアンの逆行列も陽に計算しないで、ヘシアンの逆行列と勾配との積を直接計算できないか、というアイデアが生まれます。実はこれが数値解析的に計算できます。すなわち、共役勾配法（CG法）を利用してこれを計算してしまう方法、これがNewton-CG法です。

ここでCG法を思い出してみましょう。CG法は連立一次方程式Ax=bを数値的に解く手法です。この解というのは、すなわちx=A^-1bを求めるということです。ところで先ほど求めたかったのは、H^-1gでした。すなわち、Hx=gという連立一次方程式をCG法でといてやれば、求めたかった更新式を計算できるという寸法です。ようやく道が開けてきました。CG法の更新式にAの逆行列は出てきません。これでヘシアンの逆行列を計算する必要がなくなりました。代わりにAとベクトルとの積が出てきます。この、ヘシアン・ベクトル積（Hessian-vector product）を計算できるか否かがポイントに成ります。そして、CRFの目的関数に対するヘシアン・ベクトル積が、動的計画法によって効率的に計算できるよ、ということを示したのが言語処理学会での@yuutatさんの論文なのでした。肝心のCRFのヘシアン・ベクトル積の計算方法ですが、これは導出が結構めんどくさい。言語処理学会の論文でもほとんど省略、発表では完全に省略（笑）しています。ところで、Newton-CG法自体は既存手法だったので、ひょっとすると機械学習やあるいは最適化の人にとってはよく知られた手法なのかもしれません。



言語処理ではベクトルの次元が巨大になるのでヘシアンを陽に計算できないよね、だから大雑把な近似しかできないよね、だからL-BFGSを使うんだよ、というのが教科書的な説明でした（だったと思う）。ちょうど、機械学習アルゴリズムを実装しようと思ってこの辺りの最適化アルゴリズムを勉強していて、ほうほうだから近似するんだね、ひとつ賢くなったよ、と思ってたときにNewton-CG法を教えてもらいました。せっかくできないことを知った直後に、実はできるよと言われたものだから結構衝撃的だったのを覚えています。ヘシアンもヘシアンの逆行列も陽に求まらないけど、それらをすっ飛ばしてヘシアン・ベクトル積なら計算できる。この辺りは全系列を列挙はできないけど、周辺確率なら計算できる、分配関数なら計算できるというのに似ていて、DPスキーとしてはニヤリとしてしまいます。
ところで時はオンライン学習大全盛の時代。L-BFGSに劇的勝利を果たしたあと、SGDの驚異的な学習の速さにあ然とするのでした。

「私は人生の岐路に立ったとき、常に困難な方の道を選んできた」

twitter上で書いたとおり、３月末をもちまして日本アイ・ビー・エムを退社いたしまして、4月から株式会社Preferred Infrastructureの研究開発部門で働きます。ここに戻ってくることは無いだろうと思った本郷に、たった3年で戻ってくることになるとは思っても見ませんでした。

内外いろんな人から、なんで転職するんだという質問をいただきます。別に前職に大きな不満があるわけでもなかったし（小さな不満はどこに行ってもあると思います）、ちょうど自分がやり始めた研究、開発が成果を上げ始めて、まさにこれからという微妙なタイミングでもありました。
昨年末あたりから@hillbigさんに声をかけてもらって、悩んだ末での決断でした。これから研究開発を強化する、その過程を体験するというのは非常にチャレンジングで貴重な体験になるだろうと考えたのが主要な理由です。また、特に心に響いたのが、「変わらないこともリスクだよ」という言葉でした。自分の人生を考えたときに、どこかでチャレンジをするのなら若いウチの方がよかろうし、今のタイミングを逃したらもっと転職に対してハードルが上がるだろうということを思いました。今なら、例えば会社がうまくいかなくなったとしても、またやり直せるだろうということも考えました。いろいろな形でチャレンジをしている友人がたくさんいるのですが、彼らもやはりそうしたリスクを許容して、また失敗したとしてもそこからどんどん成長しているのを思ったりもしました。
最後に自分を奮い立たせたのが、タイトルの岡本太郎の言葉です。これからは今まで以上にチャレンジングな環境で、いろんな意味で尖った人間に囲まれることになります。短いながら３年間大企業で培った経験を活かして、常に成長していくことを目指し、腐らずに頑張っていこうと思います。