メモリ制限BFGS

限定メモリBFGS（L-BFGSまたはLM-BFGS）は、限られた量のコンピュータメモリを使用してBroyden-Fletcher-Goldfarb-Shannoアルゴリズム（BFGS）を近似する準ニュートン法ファミリーの最適化 アルゴリズムです。^{[1]これは、}機械学習におけるパラメータ推定のための一般的なアルゴリズムです。^{[2] [3]}このアルゴリズムの目標問題は、微分可能なスカラー関数である実数ベクトルの制約のない値を最小化することです。 ${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x} }$${\displaystyle f}$

オリジナルの BFGS と同様に、L-BFGS は逆ヘッセ行列の推定値を使用して変数空間の検索を誘導しますが、BFGS が逆ヘッセ行列の密な近似値を格納するのに対し ( nは問題内の変数の数)、L-BFGS は暗黙的に近似値を表す少数のベクトルのみを格納します。その結果生じる線形メモリ要件のため、L-BFGS メソッドは多くの変数を持つ最適化問題に特に適しています。逆ヘッセ行列H _kの代わりに、L-BFGS は位置xと勾配 ∇ f ( x ) の過去m回の更新の履歴を保持します。通常、履歴サイズm は小さくなります (多くの場合)。これらの更新は、 H _kベクトル積を必要とする操作を暗黙的に実行するために使用されます。 ${\displaystyle n\times n}$${\displaystyle m<10}$

アルゴリズムは、最適値 の初期推定値から開始し、一連のより良い推定値 を繰り返し使用してその推定値を改良していきます。関数 の導関数は、アルゴリズムの主要な駆動力として使用され、最急降下方向を識別したり、 のヘッセ行列 (2 次導関数) の推定値を形成したりします。 ${\displaystyle \mathbf {x} _{0}}$${\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\ldots }$${\displaystyle g_{k}:=\nabla f(\mathbf {x} _{k})}$${\displaystyle f(\mathbf {x} )}$

L-BFGS は他の準ニュートン アルゴリズムと多くの特徴を共有していますが、行列ベクトル乗算の実行方法が大きく異なります。ここで、は近似ニュートン方向、 は現在の勾配、はヘッセ行列の逆です。この方向ベクトルを形成するために更新履歴を使用する複数のアプローチが公開されています。ここでは、いわゆる「2 ループ再帰」という一般的なアプローチを示します。^{[4] [5]}${\displaystyle d_{k}=-H_{k}g_{k}}$${\displaystyle d_{k}}$${\displaystyle g_{k}}$${\displaystyle H_{k}}$

k回目の反復での位置をとし、最小化される関数を とし、すべてのベクトルを列ベクトルとする。また、最後のm 個の更新をフォーム に格納したと仮定する。${\displaystyle x_{k}}$${\displaystyle g_{k}\equiv \nabla f(x_{k})}$${\displaystyle f}$

${\displaystyle s_{k}=x_{k+1}-x_{k}}$

${\displaystyle y_{k}=g_{k+1}-g_{k}}$。

を定義し、これは反復kでの推定が始まる逆ヘッセ行列の「初期」近似値になります。 ${\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}}$${\displaystyle H_{k}^{0}}$

このアルゴリズムは、逆ヘッセ行列のBFGS再帰に基づいている。

${\displaystyle H_{k+1}=(I-\rho _{k}s_{k}y_{k}^{\top })H_{k}(I-\rho _{k}y_{k}s_{k}^{\top })+\rho _{k}s_{k}s_{k}^{\top }.}$

固定されたkに対して、ベクトルのシーケンスをおよびとして定義します。次に、から を計算するための再帰アルゴリズムは、および を定義することです。また、別のベクトルのシーケンスを として定義します。これらのベクトルを計算するための別の再帰アルゴリズムは、 を定義してから、 および を再帰的に定義することです。 の値は、上昇方向です。 ${\displaystyle q_{km},\ldots ,q_{k}}$${\displaystyle q_{k}:=g_{k}}$${\displaystyle q_{i}:=(I-\rho _{i}y_{i}s_{i}^{\top })q_{i+1}}$${\displaystyle q_{i}}$${\displaystyle q_{i+1}}$${\displaystyle \alpha_{i}:=\rho_{i}s_{i}^{\top}q_{i+1}}$${\displaystyle q_{i}=q_{i+1}-\alpha _{i}y_{i}}$${\displaystyle z_{km},\ldots ,z_{k}}$${\displaystyle z_{i}:=H_{i}q_{i}}$${\displaystyle z_{km}=H_{k}^{0}q_{km}}$${\displaystyle \beta _{i}:=\rho _{i}y_{i}^{\top }z_{i}}$${\displaystyle z_{i+1}=z_{i}+(\alpha _{i}-\beta _{i})s_{i}}$${\displaystyle z_{k}}$

したがって、降下方向は次のように計算できます。

${\displaystyle {\begin{array}{l}q=g_{k}\\{\mathtt {For}}\ i=k-1,k-2,\ldots ,km\\\qquad \alpha _{i}=\rho _{i}s_{i}^{\top }q\\\qquad q=q-\alpha _{i}y_{i}\\\gamma _{k}={\frac {s_{km}^{\top }y_{km}}{y_{km}^{\top }y_{km}}}\\H_{k}^{0}=\gamma _{k}I\\z=H_{k}^{0}q\\{\mathtt {For}}\ i=km,k-m+1,\ldots ,k-1\\\qquad \beta _{i}=\rho _{i}y_{i}^{\top }z\\\qquad z=z+s_{i}(\alpha _{i}-\beta _{i})\\z=-z\end{array}}}$

この定式化は、最小化問題の検索方向、すなわち を与えます。したがって、最大化問題の場合は、代わりに-zを取る必要があります。初期の近似逆ヘッセ行列は、数値的に効率的であるため、対角行列または単位行列の倍数として選択される ことに注意してください。${\displaystyle z=-H_{k}g_{k}}$${\displaystyle H_{k}^{0}}$

初期行列のスケーリングにより、探索方向が適切にスケーリングされ、ほとんどの反復で単位ステップ長が受け入れられることが保証されます。曲率条件が満たされ、BFGS 更新が安定していることを保証するために、Wolfe 直線探索が使用されます。一部のソフトウェア実装では、Armijoバックトラッキング直線探索を使用しますが、この条件を満たすには よりも長いステップ長が必要になる可能性があるため、選択したステップで曲率条件が満たされることを保証できないことに注意してください。一部の実装では、が負またはゼロに近すぎる場合に BFGS 更新をスキップすることでこの問題に対処していますが、更新がスキップされすぎてヘッセ近似で重要な曲率情報を取得できなくなる可能性があるため、この方法は一般に推奨されません。一部のソルバーでは、曲率条件を満たすために 量とを変更する、いわゆる減衰 (L)BFGS 更新を使用します。${\displaystyle \gamma_{k}}$${\displaystyle y_{k}^{\top }s_{k}>0}$${\displaystyle 1}$${\displaystyle y_{k}^{\top }s_{k}}$${\displaystyle H_{k}}$${\displaystyle s_{k}}$${\displaystyle y_{k}}$

2ループ再帰式は、逆ヘッセ行列を乗算する際の効率性から、制約のない最適化プログラムで広く使用されています。ただし、直接ヘッセ行列または逆ヘッセ行列の明示的な形成は許可されておらず、非ボックス制約とは互換性がありません。代わりのアプローチは、直接ヘッセ行列および/または逆ヘッセ行列の低ランク表現を伴うコンパクト表現です。 ^[6]これは、ヘッセ行列を対角行列と低ランク更新の合計として表します。このような表現により、たとえばSQP法の一部として、制約付き設定でL-BFGSを使用できるようになります。

L-BFGSは、対数線形（MaxEnt）モデルと条件付きランダムフィールドを-正規化してフィッティングするための「最適なアルゴリズム」と呼ばれています。^{[2] [3]}${\displaystyle \ell _{2}}$

BFGS (および L-BFGS) は制約のない滑らかな関数を最小化するように設計されているため、微分不可能なコンポーネントまたは制約を含む関数を処理するには、L-BFGS アルゴリズムを変更する必要があります。一般的な変更のクラスは、アクティブ セットの概念に基づくアクティブ セット メソッドと呼ばれます。現在の反復の小さな近傍に制限すると、関数と制約を簡略化できるという考え方です。

L-BFGS-Bアルゴリズムは、L-BFGS を拡張して、変数に対する単純なボックス制約 (境界制約とも呼ばれる) を処理します。つまり、l _i ≤ x _i ≤ u _iという形式の制約です。ここで、 l _iとu _{i は}、それぞれ変数ごとの定数の下限と上限です (各x _iについて、いずれかまたは両方の境界を省略できます)。^{[7] [8]}この方法は、各ステップで固定変数と自由変数を識別し (単純な勾配法を使用)、次に自由変数に対してのみ L-BFGS 法を使用して精度を高め、このプロセスを繰り返すことによって機能します。

オーサントワイズ限定メモリ準ニュートン法（OWL-QN ）は、正規化モデルをフィッティングするためのL-BFGSの変種であり、そのようなモデルの固有のスパース性を活用します。^[3] これは、次の形式の関数を最小化します。 ${\displaystyle \ell _{1}}$

${\displaystyle f({\vec {x}})=g({\vec {x}})+C\|{\vec {x}}\|_{1}}$

ここで、 は微分可能な凸損失関数です。この方法はアクティブセット型の方法です。各反復で、変数の各コンポーネントの符号を推定し、後続のステップが同じ符号を持つように制限します。符号が固定されると、微分不可能な項は L-BFGS で処理できる滑らかな線形項になります。L-BFGS ステップの後、この方法では一部の変数の符号を変更し、プロセスを繰り返します。 ${\displaystyle g}$ ${\displaystyle \|{\vec {x}}\|_{1}}$

Schraudolphらは、 BFGSとL-BFGSの両方に対するオンライン近似を提示している。 ^[9]確率的勾配降下法と同様に、これは各反復でデータセット全体のランダムに抽出されたサブセットの誤差関数と勾配を評価することで計算の複雑さを軽減するために使用できる。O-LBFGSは全体的にほぼ確実に収束することが示されている^[10]が、BFGSのオンライン近似（O-BFGS）は必ずしも収束するわけではない。^[11]

注目すべきオープンソース実装には以下のものがあります。

• ALGLIB は、 C++ および C# で L-BFGS を実装し、別のボックス/線形制約バージョンである BLEIC も実装します。
• Rのoptim汎用最適化ルーチンは L-BFGS-B メソッドを使用します。
• SciPyの最適化モジュールの最小化メソッドには、L-BFGS-B を使用するオプションも含まれています。

注目すべき非オープンソース実装には以下のものがあります。

• L-BFGS-Bの変種は、ACM TOMSアルゴリズム778としても存在します。^{[8] [12]} 2011年2月、オリジナルのL-BFGS-Bコードの作者の一部がメジャーアップデート（バージョン3.0）を投稿しました。
• Fortran 77（およびFortran 90インターフェース付き）のリファレンス実装。 ^{[13] [14]}このバージョンは、古いバージョンと同様に、他の多くの言語に変換されています。
• 設計者によるOWL-QN C++実装。^{[3] [15]}

• Liu, DC; Nocedal, J. (1989). 「大規模最適化のための限定メモリ法について」.数学プログラミング B. 45 ( 3): 503–528. CiteSeerX  10.1.1.110.6443 . doi :10.1007/BF01589116. S2CID  5681609.
• Haghighi, Aria (2014 年 12 月 2 日)。「数値最適化: L-BFGS の理解」。
• Pytlak, Radoslaw (2009)。「限られたメモリの準ニュートンアルゴリズム」。非凸最適化における共役勾配アルゴリズム。Springer。pp. 159–190。ISBN 978-3-540-85633-7。