function hello() {
  alert("Javascript");
}
  1. aaaa
  2. bbbb
  3. cccc
  • aaa
  • bbb
  • ccc

aaa bbb

$a=y^2$

$ a=x^2 $

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

Newton法

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

wikipedia

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

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

ニュートン法の仕組み

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

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

ここでは点における勾配で、は点におけるヘッセ行列である。

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

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

上の式が0になるときは最小値をとるので、その時のを求めると、

ここで求めたを探索方向とする。

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

アルゴリズム: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}$を計算する必要があるが、の次元が$\sim 10^8$になった時にその行列の要素数は$\sim 10^{16}$になってしまい、値がメモリに載らなくなってしまう。

準Newton法(L-BFGS)

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

セカント条件

ヘッセ行列の逆行列が、正定値対称行列で近似できたとする。すると、

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

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

ここで、

とする。

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

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

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

つまり、

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

ただし