L-BFGS法

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

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

アルゴリズム[編集]

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

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

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

s_{k}=x_{k+1}-x_{k}

y_{k}=g_{k+1}-g_{k}

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

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

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, \dots, q k$ を $q k := g k$ および $q i := (I - ρ i y i s i ⊤) q i +1$ により定義する。 $α i := ρ i s i ⊤ q i +1$ と定義すると、 $q i = q i +1 - α i y i$ により $q i$ を $q i +1$ から再帰的に計算することができる。別のベクトル列 $z k - m, \dots, z k$ を $z i := H i z i$ により定義する。このベクトル列は $z k - m = H 0 k q k - m$ 、 $β i := ρ i s i ⊤ z i +1$ と定義することにより $z i +1 = (α i - β i) s i$ のように再帰的に計算でき、 $z k$ により上昇方向を推定できる。

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

{\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 0 k$ は、数値的効率性のために、対角行列または単位行列の実数倍とされる。

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

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

応用[編集]

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

亜種[編集]

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

L-BFGS-B[編集]

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

OWL-QN[編集]

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

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

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

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]。2011年2月、L-BFGS-Bコードの原著者の一部によりメジャーアップデート（バージョン 3.0）が投稿された。
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.
^ ^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
^ 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.
^ ^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.
^ 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日閲覧。