最適化手法についてー勾配法,ニュートン法,準ニュートン法などー | moskomule log

最適化手法についてー勾配法,ニュートン法,準ニュートン法などー

以前Eve optimizer実装を行ったのですが,肝心の非線型函数の最適化手法について知らなかったので調べました.

はじめに

最適化に関して,微分を用いない手法としてはランダム法やシンプレックス法がありますが,今回は微分を用いて反復的に解に近づく方法である反復法について述べます.

なお今回可視化に際して利用した函数は$(x+1)x(x-1)(x-3)+y^2+xy$で,2つの局所解と1つの鞍点を持ちます.

反復法

反復法は函数$f(x)$について,

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

によって位置を更新しながら列$(x_k)_{k\in\mathscr{N}}$を局所解または大局解$x^{\star}$に近づけていく手法です.

実際は$k$は有限なので,適当な回数で打ち切ったり,$|x_{k+1}-x_{k}|<\epsilon$で中止したりします.

$x$から$x+\delta x$へと移動した際の$f$の変化$\delta f(x)$とします.$\delta f(x)=\delta x\nabla f(x)$は$\delta x$と$\nabla f(x)$とが並行の時に最大となりますので,$\nabla f(x)$は$x$において$f(x)$の値が最も変化する方向です.そのため局所的には$-\nabla f(x)$に進むのが望ましいですが,それが全体として望ましいとは必ずしもいえません.反復法ではこの方向に適当な$H_k$をかけて調整した上で,順次移動していきます.

$a_k$は学習率,ステップ幅などと呼ばれ一回の更新で進む量を表します.$\alpha_k$にはヒューリスティックな更新方法もありますが($\alpha_k \sim \frac{1}{\sqrt{k}}$など),Armijoの基準やWolfeの基準といったより客観的な指標もあります.

\[\begin{aligned} f(x_k+\alpha_k d_k) &\le f(x_k)+c_1\alpha_k\nabla f(x_k)^{\top}d_k \cr\cr \nabla f(x_k+\alpha_k d_k)^{\top}d_k &\ge c_2\nabla f(x_k)d_k \end{aligned}\]

上の式がArmijoの基準で,2つ合わせるとWolfeの基準となります.$\alpha_k$がこの範囲に収まるように変化させていきます(line search method1).

勾配降下法

勾配降下法(gradient descent method),または最急降下法(steepest descent method)は$H_k=I$とする手法です.すなわち

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

によって更新していきます.最急方向に適当な学習率$\alpha_k$を乗じて進んでいくので「直感的には合理的」2ですが,収束が遅く,適切な学習率の調整が難しいなど,実際の性能はあまりよくありません.

$\alpha_k=0.1$で100回の更新を行った際の$x_k$の軌跡

$\alpha_k=0.01$で100回の更新を行った際の$x_k$の軌跡

$\alpha_k=0.001$で100回の更新を行った際の$x_k$の軌跡

最急降下法に対してWolfe基準を用いて学習率を調整した際の$x_k$の軌跡

ニュートン法

ニュートン法,またはニュートン・ラフソン法(Newton-Raphson method)は$H_k$に$(\nabla^2 f(x))^{-1}$,つまりHessianの逆行列を用いた手法です.これはニュートンの近似法3によって$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$となる点を求めているだけですので,容易に鞍点に収束します.

ニュートン法によって更新を行った際の$x_k$の軌跡,鞍点に収束しているものもある.

準ニュートン法

ニュートン法は強力ですが,Hessianの逆行列計算は$x$の次元が大きくなると困難になります.そこで$x,\nabla f(x)$によって$\nabla^2 f(x)$を近似するのが準ニュートン法(quasi Newton method)です.いま

\[\nabla f(x_{k+1})-\nabla f(x_k)\sim \nabla^2 f(x_{k+1})(x_{k+1}-x_k)\]

ですが,$y_k=\nabla f(x_{k+1})-\nabla f(x_k)$,$s_k=x_{k+1}-x_k$として$H_{k+1}y_k=s_k$(secant条件)を満たす$H_k$を考えます.この条件を満たす$H_k$は無数にありますが,特にDFP公式

\[H_{k+1}=H_{k}-\frac{H_ky_ky_k^{\top}H_k}{y_k^{\top}H_ky_k}+\frac{s_ks_k^{\top}}{s_k^{\top}s_k}\]

やBFGS公式

\[H_{k+1}=(I-\frac{y_ks_k^{\top}}{s_k^{\top}y_k})^{\top}H_k(I-\frac{y_ks_k^{\top}}{s_k^{\top}y_k})-\frac{s_ks_k^{\top}}{s_k^{\top}y_k}\]

によって効率的に求めることができます.これらはHessianを必要としないものの,依然として$H$という巨大となり得る行列を必要とします.L-BFGS(limited memory BFGS)では$H_{k}$の更新に$((x_i,\nabla f(x_i)))_{i=1,\cdots,k}$を用いることでこの問題を解決しています.

Wolfe基準を用いて学習率の調整を行い,BFGS公式によって更新を行った際の$x_k$の軌跡

Levenberg-Marquardt法

Levenberg-Marquardt法は非線型函数$g(t)$に対して$(g(t)-\xi)^2$を最小化する,非線型最小二乗法に対する手法です.

$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$を大きくする.

という規則を適用し更新していきます(trust region methodの例).$\lambda$はdampingと呼ばれます.評判もよいですが,$(\nabla^2f(x)+\lambda_k I)^{-1}$のコストは大きそうです.

Levenberg-Marquardt法によって更新を行った際の$x_k$の軌跡

まとめ

最急降下法,ニュートン法,準ニュートン法およびLevenberg-Marquardt法による最適化を概説しました.性能の良さと計算コストは相反するところが大きいようで,問題に合わせて適当なものを調節しながら使うのが良さそうです.また,今回は扱わなかった確率的最急降下法など,確率的な手法を用いるとまた様子が変わってくるかもしれません.

この記事を書くに当たっては脚注の参考文献のほかにStuttgart大学の最適化の授業のスライドおよびOR学会の資料を参考にしました.1は数理最適化の本ですが,非常に分かりやすく網羅的に書かれています.23は落ち着いたらゆっくり読み返したいです.


  1. Nocedal, J., & Wright, S. J. (2006). Numerical optimization (2nd ed). Springer. [return]
  2. Bishop, C. M., 元田浩, 栗田多喜夫, 樋口知之, 松本裕治, & 村田昇. (2012). パターン認識と機械学習 : ベイズ理論による統計的予測. 丸善出版. [return]
  3. 高木貞治. (2010). 定本解析概論. 岩波書店. [return]
comments powered by Disqus