この項目「
L-BFGS法 」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：
en: Limited-memory BFGS ）
修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。
ノートページ や
履歴 も参照してください。
（2022年11月 ）
記憶制限BFGS法 （きおくせいげんBFGSほう）またはL-BFGS法 （英 : Limited-memory BFGS method ）とは、準ニュートン法 に分類される最適化 アルゴリズム であり、BFGS法 をより小さな記憶容量 を用いて近似的に実行する[ 1] 機械学習 におけるパラメーター推定に広く用いられる[ 2] [ 3] x f (x
元になったBFGS法と同様、L-BFGS法は逆ヘッセ行列 の推定値を使用して変数空間を探索するが、BFGS法では逆ヘッセ行列の近似値をn ×n n は対象問題の変数の数）として記憶するのに対し、L-BFGS法では少数のベクトルのみを記憶し逆ヘッセ行列の近似値はこれらにより暗黙的に表現される。結果としてメモリ使用量のスケーリングは問題サイズの2乗から1乗ヘ低下するため、多くの変数が関わる最適化問題に特に適する。L-BFGS法では逆ヘッセ行列H k x ∇f (x の 過去m 回の更新の履歴を記憶する（多くの場合m < 10H k
L-BFGS法は、所与の初期推定x 0 x 1 , x 2 , …g k f (x k
L-BFGS法は他の準ニュートン法アルゴリズムと多くの部分は共通だが、行列とベクトルの乗算d k H k g k d k g k H k [ 4] [ 5]
k 回目の反復における位置x k g k f (x k m 回の更新履歴を次の形式で記憶していることを仮定する。
s
k
=
x
k
+
1
− − -->
x
k
{\displaystyle s_{k}=x_{k+1}-x_{k}}
y
k
=
g
k
+
1
− − -->
g
k
{\displaystyle y_{k}=g_{k+1}-g_{k}}
ここで、
ρ ρ -->
k
=
1
y
k
⊤ ⊤ -->
s
k
{\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}}
H 0k k 回目の反復での逆ヘッセ行列の初期推定値とする。
L-BFGS法の基となるBFGS法では、逆ヘッセ行列は以下のような漸化式で推定される。
H
k
+
1
=
(
I
− − -->
ρ ρ -->
k
s
k
y
k
⊤ ⊤ -->
)
H
k
(
I
− − -->
ρ ρ -->
k
y
k
s
k
⊤ ⊤ -->
)
+
ρ ρ -->
k
s
k
s
k
⊤ ⊤ -->
{\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 − ρ i y i s i ⊤ )q i +1α i ρ i s i ⊤ q i +1q i q i +1α i y i q i q i +1z k −m z k z i H i q i z k −m H 0k q k −m β i ρ i s i ⊤ z i z i +1z i α i β i s i z k
したがって、下降方向は次の疑似コードのようにして計算できる。
q
=
g
k
F
o
r
i
=
k
− − -->
1
,
k
− − -->
2
,
… … -->
,
k
− − -->
m
α α -->
i
=
ρ ρ -->
i
s
i
⊤ ⊤ -->
q
q
=
q
− − -->
α α -->
i
y
i
γ γ -->
k
=
s
k
− − -->
1
⊤ ⊤ -->
y
k
− − -->
1
y
k
− − -->
1
⊤ ⊤ -->
y
k
− − -->
1
H
k
0
=
γ γ -->
k
I
z
=
H
k
0
q
F
o
r
i
=
k
− − -->
m
,
k
− − -->
m
+
1
,
… … -->
,
k
− − -->
1
β β -->
i
=
ρ ρ -->
i
y
i
⊤ ⊤ -->
z
z
=
z
+
s
i
(
α α -->
i
− − -->
β β -->
i
)
z
=
− − -->
z
{\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 k g k −z を使えばよい。逆ヘッセ行列の初期推定値H 0k
逆ヘッセ行列の初期推定値をγk により適切にスケールすることにより、探索方向がwell scaled[訳語疑問点 であることが保証されるため、ほとんどの反復でステップ長は1としてよい。曲率条件が満たされておりBFGS更新が安定であることを保証するためには、ウルフの直線探索 が用いられる。一部のソフトウェア実装では、Armijoバックトラッキング直線探索 （英語版 ） y k ⊤ s k y k ⊤ s k
この2ループ更新法は、逆ヘッセ行列の推定にのみ対応できる。逆ヘッセ行列を近似する他のアプローチも開発されている他、ヘッセ行列B k [ 6]
L-BFGS法は、多項ロジスティック回帰 （英語版 ） ℓ 2 条件付き確率場 のフィッティング向けに"the algorithm of choice"[訳語疑問点 とされる[ 2] [ 3]
BFGS法は（したがってL-BFGSも）、滑らかな 関数の非制約最小化問題のために設計されているため、微分 不可能な成分が含まれる場合や制約を含む関数を扱うためには、アルゴリズムを 一部変更する必要がある。よく用いられる変更として有効制約法 （英語版 ）
L-BFGS-B
L-BFGS-B法 は、li ≤ xi ≤ ui [訳語疑問点 を変数に課すことができるようL-BFGS法を拡張したものである。ここで、li およびui は各xi ごとの下限と上限を表わす定数である（変数によっては片方、もしくは両方がない場合もある）[ 7] [ 8]
OWL-QN
Orthant -wise limited-memory quasi-NewtonOWL-QN ) 法[訳語疑問点 は、ℓ 1 正則化 モデルのフィッティング向けの亜種L-BFGS法であり、ℓ 1 正則化 モデル固有のスパース性 を利用する手法である。[ 3]
f
(
x
→ → -->
)
=
g
(
x
→ → -->
)
+
C
‖ ‖ -->
x
→ → -->
‖ ‖ -->
1
{\displaystyle f({\vec {x}})=g({\vec {x}})+C\|{\vec {x}}\|_{1}}
ここで、g は微分可能 かつ上に凸 な損失関数 である。このアルゴリズムは有効制約法の一種であり、各反復において変数の各成分の符号 を推定し、次のステップでも同一の符号が保たれるような制約を課す。微分不可能な
‖ ‖ -->
x
→ → -->
‖ ‖ -->
1
{\displaystyle \|{\vec {x}}\|_{1}}
O-LBFGS
シュラウドルフらにより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]
Fortran 77 による参照実装（Fortran 90 インターフェイスもある）[ 13] [ 14] OWL-QN法の設計者自信によるC++実装[ 3] [ 15]
^ 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 . ^ 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 。
^ 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
^ 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 . ^ 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 . ^ 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 . ^ 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/ . ^ 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 .
^ Schraudolph, N.; Yu, J.; Günter, S. (2007). A stochastic quasi-Newton method for online convex optimization . AISTATS. ^ 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 . ^ 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 . ^ “TOMS Home ”. toms.acm.org . 2022年11月3日 閲覧。 ^ 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 . ^ “L-BFGS-B Nonlinear Optimization Code ”. users.iems.northwestern.edu . 2022年11月3日 閲覧。 ^ “Orthant-Wise Limited-memory Quasi-Newton Optimizer for L1-regularized Objectives ”. Microsoft Download Center . 2022年11月3日 閲覧。
