L-BFGS法

記憶制限BFGS法またはL-BFGS法とは、準ニュートン法に分類される最適化アルゴリズムであり、BFGS法をより小さな記憶容量を用いて近似的に実行する。機械学習におけるパラメーター推定に広く用いられる。L-BFGS法が解く対象は、実数ベクトルx}}の関数//f//}}の非制約最適化問題である。

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

1. アルゴリズム
---------

L-BFGS法は、所与の初期推定//0}}から、反復的により良い推定値//1, //2, …}}を算出する。目的関数の微分値1=//g////k// := ∇//f//}}を降下の方向の算出だけでなく、ヘッセ行列の推定値の更新にも用いる。

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

k}}回目の反復における位置//x////k//}}および勾配//g////k// ≡ ∇//f//}}を所与とする。また、すべてのベクトルは列ベクトルとし、直近m}}回の更新履歴を次の形式で記憶していることを仮定する。

ここで、とし、Hsuをk}}回目の反復での逆ヘッセ行列の初期推定値とする。

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

k}}を一定として、ベクトル列//q////k//−//m//, …, //q////k//}}を1=//q////k// := //g////k//}}および1=//q////i// := //q////i//+1}}により定義する。1=//α////i// :=//ρ////i////s////i//&top;//q////i//+1}}と定義すると、1=//q////i// = //q////i//+1 − //α////i////y////i//}}により//q////i//}}を//q////i//+1}}から再帰的に計算することができる。別のベクトル列//z////k//−//m//, …, //z////k//}}を1=//z////i// := H//i////z////i//}}により定義する。このベクトル列は1=//z////k//−//m// = Hsu、1=//β////i// :=//ρ////i////s////i//&top;//z////i//+1}}と定義することにより1=//z////i//+1 = //s////i//}}のように再帰的に計算でき、//z////k//}}により上昇方向を推定できる。

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

上の疑似コードは、最小化問題の探索方向、1=//z// = −H//k////g////k//}}を推定する。最大化問題を解く際は代わりに−z}}を使えばよい。逆ヘッセ行列の初期推定値Hsuは、数値的効率性のために、対角行列または単位行列の実数倍とされる。

逆ヘッセ行列の初期推定値をγ//k//}}により適切にスケールすることにより、探索方向がwell scaleddate=2022年11月}}であることが保証されるため、ほとんどの反復でステップ長は1としてよい。曲率条件が満たされておりBFGS更新が安定であることを保証するためには、ウルフ条件が用いられる。一部のソフトウェア実装では、Armijoバックトラッキング直線探索が用いられるが、曲率条件//y////k//&top;//s////k// > 0}}が満たされるためのステップ長が1以上となる場合があるため曲率条件が保証されないことに注意が必要である。//y////k//&top;//s////k//}}が負かゼロに近すぎる場合はBFGS更新を行わない実装もあるが、更新が頻繁にスキップされてヘッセ行列の近似が重要な曲率情報を捉えられない可能性があるため、一般的には推奨されない。

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

2. 応用
-----

L-BFGS法は、多項ロジスティック回帰や//&ell;//2}}正則化つき条件付き確率場のフィッティング向けに"the algorithm of choice"date=2022年11月とされる

3. 亜種
-----

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

3.1. L-BFGS-B
-------------

L-BFGS-B法は、//li// ≤ //xi// ≤ //ui//}}の不等式で表わせる制約、いわゆるsimple box constraints date=2022年11月}}を変数に課すことができるようL-BFGS法を拡張したものである。ここで、li}}およびui}}は各xi}}ごとの下限と上限を表わす定数である。このアルゴリズムは、すべてのステップで固定変数と自由変数を分け、自由変数に対してのみ L-BFGS法を適用し、これを繰り返すことで問題を解く。

3.2. OWL-QN
-----------

Orthant-wise limited-memory quasi-Newton  法象限別記憶制限準ニュートン法は、//&ell;//sub正則化モデルのフィッティング向けの亜種L-BFGS法であり、//&ell;//sub正則化モデル固有のスパース性を利用する手法である。このアルゴリズムは以下の形式で表わされる関数を最小化する。

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

3.3. O-LBFGS
------------

シュラウドルフらによりBFGS法とL-BFGS法それぞれをオンライン学習近似した手法が提示されている。これらの手法は、確率的勾配降下法と同様に、各反復ごとにデータセット全体を評価することなく、ランダム抽出された部分データセットを用いてエラー関数と勾配を評価することにより、計算複雑度を軽減できる。 BFGS法のオンライン近似