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の驚異的な学習の速さにあ然とするのでした。