2017年7月11日

Hessianを使った最適化手法について

サマーインターン

こんにちは。4月からエンジニアインターンをしている幡谷です。

LeapMindでは月に数回Goodfellow et al.の“Deep Learning”本の勉強会をしています。今回の勉強会では最適化を扱ったので、Hessianを使う最適化手法について書くことにしました。

微分を用いる最適化手法は反復法と呼ばれます。反復法は函数(f(x))について、

\begin{aligned} d_k &= -H_k\nabla f(x_k) \\ \\ x_{k+1} &= x_{k}+\alpha_{k}d_{k} \end{aligned}

によって位置を更新しながら列((x_k)_{k\in\mathscr{N}})を局所解(x^{\star})に近づけていく手法です。(-\nabla f(x))は(f(x))の値が最も変化する方向です。

勾配降下法

勾配降下法は(H_k=I)とする手法です。すなわち

$x_{k+1}=x_{k}-\alpha_k\nabla f(x_{k})$

によって更新していきます。最急方向に適当な学習率(\alpha_k)を乗じて進んでいきます。分かりやすいですが、収束が遅く、適切な学習率の調整が難しいなど、実際の性能はあまりよくありません。

ニュートン法は(H_k)に((\nabla^2 f(x))^{-1})、つまりHessianの逆行列を用いた手法です。これはニュートンの近似法によって(f(x))の極値を求めていると見ることができます。ニュートンの近似法は函数(g(t)=0)の根を

$t_{k+1}=t_{k}-(\nabla g(t_{k}))^{-1}g(t_{k})$

によって求めますが、ニュートン法では極値が(0)となる点を求めたいので、(g(t)=\nabla f(t))、(\nabla g(t)=\nabla^2 f(t))としているわけです。

この手法は非常に高速に収束（二次収束）しますが、上で見たように極値が(0)となる点を求めているだけですので、容易に鞍点に収束します。

Levenberg-Marquardt法では(H_k=(\nabla^2f(x)+\lambda_k I)^{-1})とします。そして、(\delta x=x_{k}-H_k \nabla f(x_k))について

(f(x_{k}+\delta x)\le f(x_{k}))、つまり(\delta x)方向に移動すると更に減少するのであれば移動して(\lambda_{k+1})を小さくする逆に移動しても減少しないのであれば移動せずに(\lambda_k)を大きくする

を反復することで解に到ります。Newton法と異なり鞍点に到った場合も周辺の値が小さいため、より適切な位置に移動することができます。

上で見たようにHessianを用いる最適化手法は非常に強力ですが、(\nabla^2 f(x))^{-1})の計算は特に高次元においては困難です。Hessianを近似する手法も存在しますが、同様に高次元においては計算が困難となります。

そのためディープラーニングのように非常に多くのパラメータを最適化する際には、勾配降下法の亜種である、確率的勾配降下法(SGD)やその発展した手法を用いるのが一般的です。