3分でわかるL-BFGS - Kotaro's blog

L-BFGSは凸最適化問題を効率よく解くことができ、scikit-learnやsparkの線形モデル(logistic回帰など)のパラメータ推定など、広く用いられている。この記事では、L-BFGSがどのような手続きによって最適解を得ているのか簡単にまとめる。

Newton法

L-BFGSなどは準Newton法と呼ばれており、Newton法を元に作られている。まずはNewton法について説明する。

最急降下法と何が違うのか？

上の図の赤い線はNewton法、緑の線は最急降下法の$x$の更新を表す。見てわかる通りNewton法のほうが初期値から最適解$x^{ * }$まで短い距離で到達している。最急降下法では１次の勾配のみを考慮するのに対してNewton法では2次の勾配まで考慮しているため、最急降下法に比べて大域的最適解に効率よく到達することができる。

ニュートン法の仕組み

点 $x_n$ の次の点を $x_{n+1}=x_n + \Delta x$ として最適な解を逐次的に求める。
は以下のように決める
1. 勾配方向$d$を決定
2. $f(x-\alpha d)$を最小にする$\alpha$を決める
3. $x_{n}+\alpha d$ を$x_{n+1}$とする

最適化したい関数を $f(x)$ とする。この関数を二次のTaylor展開で近似すると

$f(x+\Delta x) \approx f(x) + \Delta x^{\rm{T}} \nabla f(x) + \frac{1}{2} \Delta x^{\rm{T}} (\nabla^2 f(x)) \Delta x$

ここで $g_n=\nabla f(x_n)$ は点 $x$ における勾配で、 $H_n=\nabla^2 f(x_n)$ は点 $x$ におけるヘッセ行列である。

上の展開式を書き直すと、

$h(\Delta x) \approx \Delta x^{\rm{T}} {\mathbf g_n} + \frac{1}{2} \Delta x^{\rm{T}} {\bf H}_\rm{n} \Delta x$

この式を最小化する $\Delta x$ を求めたいので、両辺を $\Delta x$ で微分すると

$\frac{\partial h_n(\Delta x)}{\partial \Delta x} = {\mathbf g_n} + {\mathbf H_n} \Delta x$

上の式が0になるとき $h_n(\Delta x)$ は最小値をとるので、その時の $\Delta x$ を求めると、

$\Delta x = -{\bf H}_n^{-1} {\bf g}_n$

ここで求めた $\Delta x$ を探索方向とする。

アルゴリズムをまとめると以下のようになる

アルゴリズム:Newton法

while no convergence
   ${\bf H}_n^{-1}, {\bf g}_n$を計算
   d $\leftarrow -{\bf H}_n^{-1} {\bf g}_n$ %探索方向dを決定
   $\alpha^* = \mathop{\rm arg~min}\limits_{\alpha} f(x_n - \alpha d)$ % line searchでステップ幅を決定
   $x_{n+1} \leftarrow x_n + \alpha^* d$

Newton法の問題点

上の方法では${\bf H}_n^{-1}$を計算する必要があるが、 $x$ の次元が$\sim 10^8$になった時にその行列の要素数は$\sim 10^{16}$になってしまい、値がメモリに載らなくなってしまう。

準Newton法(L-BFGS)

準Newton法とはNewton法におけるヘッセ行列を別の方法で置き換えた方法のこと。準Newton法は様々な種類があるが、ここではL-BFGSについて説明する。

セカント条件

ヘッセ行列の逆行列 ${\bf H}_n^{-1}$ が、正定値対称行列 ${\bf B}_{n}$ で近似できたとする。すると、

$d = - B_n g_n$

は降下方向を向いていることが保証される。ここで、$g_n$の1次のテイラー展開を考えると

$\frac{g_{n+1}- g_n}{x_{n+1}-x_n} \approx {\bf H}_n$

なので、$B_{n}$も上の条件を満たすとすると、

$B_{n} (x_n - x_{n-1}) = (g_n - g_{n-1})\\ B_{n} s_n = y_n$

ここで、

$y_n = g_n - g_{n-1}\\ s_n = x_n - x_{n-1}$

とする。

$B_n$をどのように更新するか？

$B_n$を更新するとき、以下の２つの条件に従うとする

$B_n$は$B_{n-1}$に対してあまり変化しない。
$B_{n} s_n = y_n$を満たす

つまり、

$B = \mathop{\rm arg~min}\limits_{B} \left \| B - B_{n-1}\right \|^2\\ s.t. ~ B_{n} s_n = y_n\\ B:正定値対称行列$

上の条件を満たす${\bf H}_n^{-1}=B$の更新式はBFGS更新式と呼ばれており、以下の式で表すことができる

$B_{n+1} = (I-\rho_n y_n s_n^{\mathrm T})B_{n}(I-\rho_n s_n y_n^{\mathrm T}) + \rho_n s_n s_n^{\mathrm T}$

ただし

$\rho={y_n s_n^{\mathrm T}}^{-1}$