アルゴリズム このアルゴリズムは、最適値の初期推定値から始まり、x 0 \displaystyle \mathbf {x} _{0}} x 1 、 x 2 、 … {\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\ldots } g k := ∇ f （ x k ） {\displaystyle g_{k}:=\nabla f(\mathbf {x} _{k})} f （ x ） {\displaystyle f(\mathbf {x} )}
L-BFGSは他の準ニュートン法と多くの特徴を共有しているが、行列とベクトルの乗算の方法が大きく異なる。d k = − H k g k {\displaystyle d_{k}=-H_{k}g_{k}} d k d_k g k {\displaystyle g_{k}} H k {\displaystyle H_{k}} [ 4 ] [ 5 ]
我々はそれを所与のものとするx k {\displaystyle x_{k}} 、 k 回目の反復における位置、g k ≡ ∇ f （ x k ） {\displaystyle g_{k}\equiv \nabla f(x_{k})} f {\displaystyle f} 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 k 0 {\displaystyle H_{k}^{0}} これは、反復k における推定の開始点となる逆ヘッセ行列の「初期」近似値になります。
このアルゴリズムは、逆ヘッセ行列に対するBFGS再帰に基づいており、
H k + 1 = （ 私 − ρ k s k y k ⊤ ） H k （ 私 − ρ 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 {\displaystyle q_{k-m},\ldots ,q_{k}} q k := g k {\displaystyle q_{k}:=g_{k}} q 私 := （ 私 − ρ 私 y 私 s 私 ⊤ ） q 私 + 1 {\displaystyle q_{i}:=(I-\rho _{i}y_{i}s_{i}^{\top })q_{i+1}} q 私 {\displaystyle q_{i}} q 私 + 1 {\displaystyle q_{i+1}} α 私 := ρ 私 s 私 ⊤ q 私 + 1 {\displaystyle \alpha _{i}:=\rho _{i}s_{i}^{\top }q_{i+1}} q 私 = q 私 + 1 − α 私 y 私 {\displaystyle q_{i}=q_{i+1}-\alpha _{i}y_{i}} z k − m 、 … 、 z k {\displaystyle z_{k-m},\ldots ,z_{k}} z 私 := H 私 q 私 {\displaystyle z_{i}:=H_{i}q_{i}} z k − m = H k 0 q k − m {\displaystyle z_{k-m}=H_{k}^{0}q_{k-m}} β 私 := ρ 私 y 私 ⊤ z 私 {\displaystyle \beta _{i}:=\rho _{i}y_{i}^{\top }z_{i}} z 私 + 1 = z 私 + （ α 私 − β 私 ） s 私 {\displaystyle z_{i+1}=z_{i}+(\alpha _{i}-\beta _{i})s_{i}} z k {\displaystyle z_{k}}
したがって、降下方向は 次のように計算できます。
q = g k F o r 私 = k − 1 、 k − 2 、 … 、 k − m α 私 = ρ 私 s 私 ⊤ q q = q − α 私 y 私 γ k = s k − m ⊤ y k − m y k − m ⊤ y k − m H k 0 = γ k 私 z = H k 0 q F o r 私 = k − m 、 k − m + 1 、 … 、 k − 1 β 私 = ρ 私 y 私 ⊤ z z = z + s 私 （ α 私 − β 私 ） 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-m}^{\top }y_{k-m}}{y_{k-m}^{\top }y_{k-m}}}\\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 {\displaystyle z=-H_{k}g_{k}} -z を取るべきである。初期の近似逆ヘッセ行列に注意する。H k 0 {\displaystyle H_{k}^{0}} は、数値的に効率的であるため、対角行列 または単位行列の倍数として選択されます。
初期行列のスケーリングγ k {\displaystyle \gamma _{k}} 、Wolfe線探索が使用されます。一部のソフトウェア実装ではArmijo バックトラッキング線探索 が使用されていますが、曲率条件が満たされることを保証できないことに注意してください。y k ⊤ s k > 0 {\displaystyle y_{k}^{\top }s_{k}>0} 1 {\displaystyle 1} y k ⊤ s k {\displaystyle y_{k}^{\top }s_{k}} H k {\displaystyle H_{k}} s k {\displaystyle s_{k}} y k {\displaystyle y_{k}}
2 ループ再帰式は、逆ヘッセ行列を乗算する際の効率性から、制約のない最適化ツールで広く使用されています。ただし、直接ヘッセ行列または逆ヘッセ行列の明示的な形成はできず、非ボックス制約とは互換性がありません。代替アプローチとして、直接ヘッセ行列および/または逆ヘッセ行列の低ランク表現を含むコンパクト表現があります。 [ 6 ]
バリエーション BFGS（およびL-BFGS）は制約のない 滑らかな 関数を最小化するように設計されているため、微分不可能 な要素や制約を含む関数を扱うには、L-BFGSアルゴリズムを修正する必要があります。よく用いられる修正方法の一つに、アクティブセット の概念に基づいたアクティブセット法があります。この方法は、現在の反復点の近傍に限定することで、関数と制約を単純化できるという考え方に基づいています。
L-BFGS-B L -BFGS-B アルゴリズムは、L-BFGS を拡張して、変数に対する単純なボックス制約 (境界制約とも呼ばれる) を処理できるようにします。つまり、 l i ≤ x i ≤ u i l i とu i はそれぞれ変数ごとの定数の下限と上限です (各x i に対して、境界の 1 つまたは両方を省略できます)。[ 7 ] [ 8 ]
OWL-QN 直交座標系限定メモリ準ニュートン法 （OWL-QN ）は、フィッティングのためのL-BFGSの変種である。ℓ 1 {\displaystyle \ell _{1}} 正則化 モデル、そのようなモデルの固有の疎性 を利用する。[ 3 ]
f （ x → ） = g （ x → ） + C ‖ x → ‖ 1 {\displaystyle f({\vec {x}})=g({\vec {x}})+C\|{\vec {x}}\|_{1}} どこg {\displaystyle g} は微分可能な 凸 損失関数 です。この方法はアクティブセット型の方法であり、各反復で変数の各成分の符号を 推定し、次のステップで同じ符号になるように制限します。符号が固定されると、微分不可能な‖ x → ‖ 1 {\displaystyle \|{\vec {x}}\|_{1}}
O-LBFGS Schraudolphらは、 BFGS と L-BFGS の両方に対するオンライン 近似法を提示している。 [ 9 ] 確率的勾配降下法 と同様に、これは、各反復で全体のデータセットからランダムに抽出されたサブセットで誤差関数 と勾配を評価することにより、計算複雑度を低減するために使用できる。O-LBFGS はグローバルにほぼ確実に収束することが示されているが[ 10 ] [ 11 ]
バリアントの実装 注目すべきオープンソース実装には以下のようなものがある。
ALGLIBは 、C++とC#でL-BFGSを実装しているほか、ボックス/線形制約版であるBLEICも別途提供しています。R のoptim汎用最適化ルーチンは、L-BFGS-B法を使用します。SciPy の最適化モジュールの最小化メソッドには、L-BFGS-Bを使用するオプションも含まれています。Julia はOptim.jlL-BFGS および L-BFGS-B アルゴリズムも実装しています。[ 12 ] Stanは 、最尤推定問題 と最大事後確率推定 問題を解決するためのオプションとして、L-BFGSと自動微分を 併用して実装しています。 注目すべき非オープンソースの実装例は以下のとおりです。
参考文献 ↑ Liu, DC; Nocedal, J. (1989). "大規模最適化のための限定メモリ法について" . Mathematical Programming B . 45 (3): 503– 528. CiteSeerX 10.1.1.110.6443 . doi : 10.1007/BF01589116 . S2CID 5681609 . 1 2 Malouf, Robert (2002). "最大エントロピーパラメータ推定のためのアルゴリズムの比較" . Proceedings of the Sixth Conference on Natural Language Learning (CoNLL-2002) . pp. 49–55 . doi : 10.3115/1118853.1118871 . 1 2 3 4 Andrew, Galen; Gao, Jianfeng (2007). "L₁正則化対数線形モデルのスケーラブルなトレーニング" . 第24回国際機械学習会議議事録 . doi : 10.1145/1273496.1273501 . ISBN 9781595937933 . S2CID 5853259 . ↑ Matthies, H.; Strang, G. (1979). "非線形有限要素方程式の解法". International Journal for Numerical Methods in Engineering . 14 (11): 1613– 1626. Bibcode : 1979IJNME..14.1613M . doi : 10.1002/nme.1620141104 . ↑ Nocedal, J. (1980). "限られたストレージでの準ニュートン行列の更新" . Mathematics of Computation . 35 (151): 773– 782. doi : 10.1090/S0025-5718-1980-0572855-7 . ↑ Byrd, RH; Nocedal, J.; Schnabel, RB (1994). "準ニュートン行列の表現と限定メモリ法におけるその使用". Mathematical Programming . 63 (4): 129– 156. doi : 10.1007/BF01582063 . S2CID 5581219 . ↑ Byrd, RH; Lu, P.; Nocedal, J.; Zhu, C. (1995). "境界制約付き最適化のための限定メモリアルゴリズム" . SIAM J. Sci. Comput. 16 (5): 1190– 1208. Bibcode : 1995SJSC...16.1190B . doi : 10.1137/0916069 . S2CID 6398414 . 1 2 Zhu, C.; Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge (1997). "L-BFGS-B: アルゴリズム 778: L-BFGS-B、大規模境界制約付き最適化のための FORTRAN ルーチン" . ACM Transactions on Mathematical Software . 23 (4): 550– 560. doi : 10.1145/279232.279236 . S2CID 207228122 . ↑ Schraudolph, N.; Yu, J.; Günter, S. (2007). オンライン凸最適化のための確率的準ニュートン法 . AISTATS. ↑ Mokhtari, A.; Ribeiro, A. (2015). "Global convergence of online limited memory BFGS" (PDF) . 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 . CiteSeerX 10.1.1.756.3003 . doi : 10.1109/TSP.2014.2357775 . S2CID 15214938 . ↑ "Optim.jl の公式ドキュメント" . ドキュメント Optim.jl . ↑ 「TOMS ホーム」 . toms.acm.org . ↑ Morales, JL; Nocedal, J. (2011). 「アルゴリズム778：L-BFGS-B：大規模境界制約付き最適化のためのFortranサブルーチン」に関する考察 ACM Transactions on Mathematical Software 38 : 1– 4. doi : 10.1145 / 2049662.2049669 . S2CID 16742561 . ↑ 「L-BFGS-B 非線形最適化コード 」 。users.iems.northwestern.edu 。 ↑ 「L1 正則化目的関数のための Orthant-Wise 限定メモリ準ニュートン最適化ツール」 。Microsoft ダウンロード センター 。
さらに読む Liu, DC; Nocedal, J. (1989). "大規模最適化のための限定メモリ法について" . Mathematical Programming 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 。
