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)やその発展した手法を用いるのが一般的です。

Back to Index