L-BFGS法

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

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

L-BFGS法は、所与の初期推定x₀から、反復的により良い推定値x₁, x₂, …を算出する。目的関数の微分値g_k := ∇f(x_k)を降下の方向の算出だけでなく、ヘッセ行列（2次微分）の推定値の更新にも用いる。

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

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

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

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

ここで、${\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}}$とし、H0
kをk回目の反復での逆ヘッセ行列の初期推定値とする。

L-BFGS法の基となる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を一定として、ベクトル列q_k−m, …, q_kをq_k := g_kおよびq_i := (I − ρ_iy_is_i^⊤)q_i+1により定義する。α_i :=ρ_is_i^⊤q_i+1と定義すると、q_i = q_i+1 − α_iy_iによりq_iをq_i+1から再帰的に計算することができる。別のベクトル列z_k−m, …, z_kをz_i := H_iz_iにより定義する。このベクトル列はz_k−m = H0
kq_k−m、β_i :=ρ_is_i^⊤z_i+1と定義することによりz_i+1 = (α_i − β_i)s_iのように再帰的に計算でき、z_kにより上昇方向を推定できる。

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

${\displaystyle {\begin{array}{l}q=g_{k}\\{\mathtt {For}}\ i=k-1,k-2,\ldots ,k-m\\\qquad \alpha _{i}=\rho _{i}s_{i}^{\top }q\\\qquad q=q-\alpha _{i}y_{i}\\\gamma _{k}={\frac {s_{k-1}^{\top }y_{k-1}}{y_{k-1}^{\top }y_{k-1}}}\\H_{k}^{0}=\gamma _{k}I\\z=H_{k}^{0}q\\{\mathtt {For}}\ i=k-m,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 = −H_kg_kを推定する。最大化問題を解く際は代わりに−zを使えばよい。逆ヘッセ行列の初期推定値H0
kは、数値的効率性のために、対角行列または単位行列の実数倍とされる。

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

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

L-BFGS法は、多項ロジスティック回帰（英語版）やℓ²正則化つき条件付き確率場のフィッティング向けに"the algorithm of choice"^{[訳語疑問点]}とされる^[2][3]

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

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

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

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

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

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

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として実装されている^[8][12]。2011年2月、L-BFGS-Bコードの原著者の一部によりメジャー アップデート（バージョン 3.0）が投稿された。
• Fortran 77による参照実装（Fortran 90インターフェイスもある）^[13][14]。このバージョンもより古いバージョンも、他の多くの言語で再実装されている。
• OWL-QN法の設計者自信によるC++実装^[3][15]

1. ^ Liu, D. C.; Nocedal, J. (1989). “On the Limited Memory Method for Large Scale Optimization”. Mathematical Programming B 45 (3): 503–528. doi:10.1007/BF01589116. http://www.ece.northwestern.edu/~nocedal/PSfiles/limited-memory.ps.gz. 
2. ^ ^{a b} Malouf, Robert (2002). "A comparison of algorithms for maximum entropy parameter estimation". Proceedings of the Sixth Conference on Natural Language Learning (CoNLL-2002). pp. 49–55. doi:10.3115/1118853.1118871。
3. ^ ^{a b c d} Andrew, Galen; Gao, Jianfeng (2007). “Scalable training of L₁-regularized log-linear models”. Proceedings of the 24th International Conference on Machine Learning. doi:10.1145/1273496.1273501. ISBN 9781595937933. http://research.microsoft.com/apps/pubs/default.aspx?id=78900 
4. ^ Matthies, H.; Strang, G. (1979). “The solution of non linear finite element equations”. International Journal for Numerical Methods in Engineering 14 (11): 1613–1626. Bibcode: 1979IJNME..14.1613M. doi:10.1002/nme.1620141104. 
5. ^ Nocedal, J. (1980). “Updating Quasi-Newton Matrices with Limited Storage”. Mathematics of Computation 35 (151): 773–782. doi:10.1090/S0025-5718-1980-0572855-7. 
6. ^ Byrd, R. H.; Nocedal, J.; Schnabel, R. B. (1994). “Representations of Quasi-Newton Matrices and their use in Limited Memory Methods”. Mathematical Programming 63 (4): 129–156. doi:10.1007/BF01582063. 
7. ^ Byrd, R. H.; Lu, P.; Nocedal, J.; Zhu, C. (1995). “A Limited Memory Algorithm for Bound Constrained Optimization”. SIAM J. Sci. Comput. 16 (5): 1190–1208. doi:10.1137/0916069. https://digital.library.unt.edu/ark:/67531/metadc666315/. 
8. ^ ^{a b} Zhu, C.; Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge (1997). “L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization”. ACM Transactions on Mathematical Software 23 (4): 550–560. doi:10.1145/279232.279236. 
9. ^ Schraudolph, N.; Yu, J.; Günter, S. (2007). A stochastic quasi-Newton method for online convex optimization. AISTATS.
10. ^ Mokhtari, A.; Ribeiro, A. (2015). “Global convergence of online limited memory BFGS”. Journal of Machine Learning Research 16: 3151–3181. arXiv:1409.2045. http://www.jmlr.org/papers/volume16/mokhtari15a/mokhtari15a.pdf. 
11. ^ Mokhtari, A.; Ribeiro, A. (2014). “RES: Regularized Stochastic BFGS Algorithm”. IEEE Transactions on Signal Processing 62 (23): 6089–6104. arXiv:1401.7625. Bibcode: 2014ITSP...62.6089M. doi:10.1109/TSP.2014.2357775. 
12. ^ “TOMS Home”. toms.acm.org. 2022年11月3日閲覧。
13. ^ Morales, J. L.; Nocedal, J. (2011). “Remark on "algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization"”. ACM Transactions on Mathematical Software 38: 1–4. doi:10.1145/2049662.2049669. 
14. ^ “L-BFGS-B Nonlinear Optimization Code”. users.iems.northwestern.edu. 2022年11月3日閲覧。
15. ^ “Orthant-Wise Limited-memory Quasi-Newton Optimizer for L1-regularized Objectives”. Microsoft Download Center. 2022年11月3日閲覧。

• Liu, D. C.; Nocedal, J. (1989). “On the Limited Memory Method for Large Scale Optimization”. Mathematical Programming B 45 (3): 503–528. doi:10.1007/BF01589116. http://www.ece.northwestern.edu/~nocedal/PSfiles/limited-memory.ps.gz. 
• Haghighi (2014年12月2日). “Numerical Optimization: Understanding L-BFGS”. 2022年11月3日閲覧。
• Pytlak, Radoslaw (2009). “Limited Memory Quasi-Newton Algorithms”. Conjugate Gradient Algorithms in Nonconvex Optimization. Springer. pp. 159–190. ISBN 978-3-540-85633-7. https://www.google.com/books/edition/Conjugate_Gradient_Algorithms_in_Nonconv/RhRkaDPmwVoC?hl=en&gbpv=1&pg=PA159 

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤンの楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂単体法（英語版） 十文字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 分枝カット法) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）