こんにちは。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\)を乗じて進んでいきます。分かりやすいですが、収束が遅く、適切な学習率の調整が難しいなど、実際の性能はあまりよくありません。

勾配降下法の学習率が0.1の場合。激しく飛んだり、振動しています。

勾配降下法の学習率が0.01の場合。理想的進んでいるように見えますが、特に右側では極小値に到るには反復回数が足りていません。

ニュートン法

ニュートン法は\(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法

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

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

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

Levenberg-Marquardt法の場合。鞍点に到った場合、周辺の値が小さいので移動することができます。

 

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

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

Posted by Hataya