L-BFGS法

記憶制限BFGS法（きおくせいげんBFGSほう）またはL-BFGS法（テンプレート:Lang-en-short）とは、準ニュートン法に分類される最適化アルゴリズムであり、BFGS法をより小さな記憶容量を用いて近似的に実行する。機械学習におけるパラメーター推定に広く用いられる。L-BFGS法が解く対象は、実数ベクトルテンプレート:Mvarの関数テンプレート:Mathの非制約最適化問題である。

元になったBFGS法と同様、L-BFGS法は逆ヘッセ行列の推定値を使用して変数空間を探索するが、BFGS法では逆ヘッセ行列の近似値をテンプレート:Math密行列（テンプレート:Mvarは対象問題の変数の数）として記憶するのに対し、L-BFGS法では少数のベクトルのみを記憶し逆ヘッセ行列の近似値はこれらにより暗黙的に表現される。結果としてメモリ使用量のスケーリングは問題サイズの2乗から1乗ヘ低下するため、多くの変数が関わる最適化問題に特に適する。L-BFGS法では逆ヘッセ行列テンプレート:Mathの代わりに、位置テンプレート:Mvarと勾配テンプレート:Mathの過去テンプレート:Mvar回の更新の履歴を記憶する（多くの場合テンプレート:Math）。これらの情報から、テンプレート:Mathとのベクトル積を必要とする操作を暗黙的に実行する。

アルゴリズム

L-BFGS法は、所与の初期推定テンプレート:Mathから、反復的により良い推定値テンプレート:Mathを算出する。目的関数の微分値テンプレート:Mathを降下の方向の算出だけでなく、ヘッセ行列（2次微分）の推定値の更新にも用いる。

L-BFGS法は他の準ニュートン法アルゴリズムと多くの部分は共通だが、行列とベクトルの乗算テンプレート:Mathの実行方法が大きく異なる。ここで、テンプレート:Mathはニュートン方向の近似値、テンプレート:Mathは現在の勾配であり、テンプレート:Mathはヘッセ行列の逆行列である。これまでの履歴を使用してこの方向ベクトルを算出する複数のアプローチが発表されているが、ここでは、「2ループ再帰」と呼ばれる一般的なアプローチを示す。

テンプレート:Mvar回目の反復における位置テンプレート:Mathおよび勾配テンプレート:Mathを所与とする。また、すべてのベクトルは列ベクトルとし、直近テンプレート:Mvar回の更新履歴を次の形式で記憶していることを仮定する。

$s_k=x_{k+1}-x_k$

$y_k=g_{k+1}-g_k$

ここで、${\rho }_k=\frac{1}{y_k^{\mathrm{\top }}{s}_k}$とし、テンプレート:Mathをテンプレート:Mvar回目の反復での逆ヘッセ行列の初期推定値とする。

L-BFGS法の基となるBFGS法では、逆ヘッセ行列は以下のような漸化式で推定される。

$H_{k+1}=(I-{\rho }_k{s}_k{y}_k^{\mathrm{\top }})H_k(I-{\rho }_k{y}_k{s}_k^{\mathrm{\top }})+{\rho }_k{s}_k{s}_k^{\mathrm{\top }}$

テンプレート:Mvarを一定として、ベクトル列テンプレート:Mathをテンプレート:Mathおよびテンプレート:Mathにより定義する。テンプレート:Mathと定義すると、テンプレート:Mathによりテンプレート:Mathをテンプレート:Mathから再帰的に計算することができる。別のベクトル列テンプレート:Mathをテンプレート:Mathにより定義する。このベクトル列はテンプレート:Math、テンプレート:Mathと定義することによりテンプレート:Mathのように再帰的に計算でき、テンプレート:Mathにより上昇方向を推定できる。

したがって、下降方向は次の疑似コードのようにして計算できる。

$\begin{array}{c}q=g_k\\ 𝙵𝚘𝚛i=k-1,k-2,\dots ,k-m\\ {\alpha }_i={\rho }_i{s}_i^{\mathrm{\top }}q\\ q=q-{\alpha }_i{y}_i\\ {\gamma }_k=\frac{s_{k-1}^{\mathrm{\top }}{y}_{k-1}}{y_{k-1}^{\mathrm{\top }}{y}_{k-1}}\\ H_k^0={\gamma }_{k}I\\ z=H_k^{0}q\\ 𝙵𝚘𝚛i=k-m,k-m+1,\dots ,k-1\\ {\beta }_i={\rho }_i{y}_i^{\mathrm{\top }}z\\ z=z+s_i({\alpha }_i-{\beta }_i)\\ z=-z\end{array}$

上の疑似コードは、最小化問題の探索方向、テンプレート:Mathを推定する。最大化問題を解く際は代わりにテンプレート:Mvarを使えばよい。逆ヘッセ行列の初期推定値テンプレート:Mathは、数値的効率性のために、対角行列または単位行列の実数倍とされる。

逆ヘッセ行列の初期推定値をテンプレート:Mvarにより適切にスケールすることにより、探索方向がwell scaledテンプレート:訳語疑問点であることが保証されるため、ほとんどの反復でステップ長は1としてよい。曲率条件が満たされておりBFGS更新が安定であることを保証するためには、ウルフの直線探索が用いられる。一部のソフトウェア実装では、アルミホのテンプレート:仮リンクが用いられるが、曲率条件テンプレート:Mathが満たされるためのステップ長が1以上となる場合があるため曲率条件が保証されないことに注意が必要である。テンプレート:Mathが負かゼロに近すぎる場合はBFGS更新を行わない実装もあるが、更新が頻繁にスキップされてヘッセ行列の近似が重要な曲率情報を捉えられない可能性があるため、一般的には推奨されない。

この2ループ更新法は、逆ヘッセ行列の推定にのみ対応できる。逆ヘッセ行列を近似する他のアプローチも開発されている他、ヘッセ行列テンプレート:Mathを直接近似するアプローチも開発されている。

応用

L-BFGS法は、テンプレート:仮リンクや[[正則化|テンプレート:Math正則化]]つき条件付き確率場のフィッティング向けに"the algorithm of choice"テンプレート:訳語疑問点とされる。

亜種

BFGS法は（したがってL-BFGSも）、滑らかな関数の非制約最小化問題のために設計されているため、微分不可能な成分が含まれる場合や制約を含む関数を扱うためには、アルゴリズムを一部変更する必要がある。よく用いられる変更として有効制約法と呼ばれる種のものがあり、これらは現ステップの小さな近傍に制約すれば関数や制約を単純化することができるという考えに基く。

L-BFGS-B

L-BFGS-B法は、テンプレート:Mathの不等式で表わせる制約、いわゆるsimple box constraints (aka bound constraints)テンプレート:訳語疑問点を変数に課すことができるようL-BFGS法を拡張したものである。ここで、テンプレート:Mvarおよびテンプレート:Mvarは各テンプレート:Mvarごとの下限と上限を表わす定数である（変数によっては片方、もしくは両方がない場合もある）。このアルゴリズムは、（単純な勾配法を用いて）すべてのステップで固定変数と自由変数を分け、自由変数に対してのみ L-BFGS法を適用し、これを繰り返すことで問題を解く。

OWL-QN

Orthant-wise limited-memory quasi-Newton (OWL-QN) 法テンプレート:訳語疑問点は、テンプレート:Math正則化モデルのフィッティング向けの亜種L-BFGS法であり、テンプレート:Math正則化モデル固有のスパース性を利用する手法である。このアルゴリズムは以下の形式で表わされる関数を最小化する。

$f(\overrightarrow{x})=g(\overrightarrow{x})+C\Vert \overrightarrow{x}{\Vert }_1$

ここで、テンプレート:Mvarは微分可能かつ上に凸な損失関数である。このアルゴリズムは有効制約法の一種であり、各反復において変数の各成分の符号を推定し、次のステップでも同一の符号が保たれるような制約を課す。微分不可能な$\Vert \overrightarrow{x}{\Vert }_1$項が符号を固定することにより、L-BFGS 法で扱える滑らかな線形項に置き換わる。L-BFGSステップの実行後、いくつかの変数の符号を変更した上で、反復を続行する。

O-LBFGS

シュラウドルフらによりBFGS法とL-BFGS法それぞれをテンプレート:仮リンク近似した手法が提示されている。これらの手法は、確率的勾配降下法と同様に、各反復ごとにデータセット全体を評価することなく、ランダム抽出された部分データセットを用いてエラー関数と勾配を評価することにより、計算複雑度を軽減できる。 BFGS法のオンライン近似（O-BFGS)は必ずしも収束しないのに対し、O-LBFGS法はほぼ確実に大域的に収束することが示されている。

亜種の実装

L-BFGS法の亜種を実装した注目すべきオープンソースソフトウェアとしては、次のものが挙げられる。

• ALGLIB: C++およびC#でL-BFGS法を実装しており、ボックス/線形制約バージョンであるBLEICも実装されている。
• R言語: optim汎用オプティマイザ ルーチンは、L-BFGS-B法を利用している。
• Scipy: scipy.optimize モジュールにはL-BFGS-B法も実装されている。

非オープンソースの実装としては、次のものが挙げられる。

• L-BFGS-B法は、ACM TOMS アルゴリズム 778として実装されている。2011年2月、L-BFGS-Bコードの原著者の一部によりメジャー アップデート（バージョン 3.0）が投稿された。
• Fortran 77による参照実装（Fortran 90インターフェイスもある）。このバージョンもより古いバージョンも、他の多くの言語で再実装されている。
• OWL-QN法の設計者自信によるC++実装

参考文献

• テンプレート:Cite journal
• テンプレート:Cite web
• テンプレート:Cite book