L-BFGS法はだからメモリが節約できるのか!

L-BFGS法 は limited memory BFGS ということで,準ニュートン法をBFGS法に基づいて省メモリで実現する方法です.(その程度の理解度です…)

BFGS法による準ニュートン法の簡単な説明

準ニュートン法では,kステップ目のヘッセ行列の逆行列の近似行列を ,勾配を とおくと,更新式は次のようになります.

ここで, は1次元探索によって決定するステップ幅です.
BFGS法では とおくと を次のように更新します.

この更新には を保持しておく必要があるので, の次元数をnとすると のメモリ領域を必要とします.

L-BFGS法による準ニュートン法

とおくと,先ほどの更新式は

と表され, を再帰的に展開すると

となります.この更新式はヘッセ行列の逆行列の近似行列の初期値(普通は単位行列などのスパースな行列) と,現在と過去全てのステップの から算出できるベクトルから構成されているので,これらを保持しておくための のメモリ領域しか必要としません.
これだとBFGS法をちょっと工夫しただけなのですが,L-BFGS法では過去のmステップ分の しか保持しておきません.(m は普通10以下だとか)
よって,

とします.これで必要なメモリ領域は となります.ちなみにこれはある程度更新を繰り返した k > m の場合です.
ここで注意しなければならないのは,上の更新式は そのものを計算するためのものではなく,探索方向 を求めるための の定義だということです.結局求めたいのは探索方向 であり,上式に右から を掛けることで次のように逐次的に求めることができます.

20100622111457

上記の逐次計算では を除いてn次元ベクトルしか出てこないのがポイントです.そして がスパースな行列であるということが前提です.

最初にL-BFGS法を見たときは,結局 を計算したら のメモリ領域が必要じゃん!と思ったのですが, を求めることなく探索方向をこんな鮮やかに計算できるんですね….
上記逐次計算の巧妙さに感動しました.
しかしBFGS法ではどういう過程で の更新式が導出されたのかが気になる…

参考文献

  • Dong C. Liu, Jorge Nocedal, Dong C. Liu, Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, Vol 45, pp. 503-528, 1989
  • L-BFGS, Wikipedia
広告
HMM, MEMM, CRF まとめ 索引語の重要度の指標TDVの定義って…
※このエントリーははてなダイアリーから移行したものです。過去のコメントなどはそちらを参照してください