lbfgsはL-BFGS algorithm [1]の実装であり、
限定メモリ準ニュートン(BFGS)アルゴリズムによって無制約な最小化問題を解きます。
Hessian行列の逆元全体の代わりに低ランク近似が保存されるので、限定メモリと呼ばれます。
プログラムは、
Jorge Nocedalによって、
Jorge J. MoréとDavid J. Thuenteが最初に書いたいくつかの関数を組み入れて
最初、Fortranで書かれ、
プログラムf2clによってLispに自動翻訳されました。
Maximaパッケージlbfgsは翻訳されたコードと
いくつかの詳細を扱うインターフェース関数からなります。
参考文献:
[1] D. Liu and J. Nocedal. "On the limited memory BFGS method for large scale optimization". Mathematical Programming B 45:503–528 (1989)
[2] http://netlib.org/opt/lbfgs_um.shar
Previous: Introduction to lbfgs [Contents][Index]
性能指標FOMの、 初期見積もりX0から始めて 変数リストX上での、 norm(grad(FOM)) < epsilon*max(1, norm(X))のような 無制約最小化の近似解を見つけます。
もし与えられたなら、gradはFOMの多変数Xに関する勾配です。 gradはXの要素それぞれに対して1つの要素を持つリストです。 もし与えられなかったら、勾配は記号微分で自動的に計算されます。
適用されるアルゴリズムは限定メモリ準Newton(BFGS)アルゴリズム [1]です。 Hessian行列の逆元全体の代わりに低ランク近似が保存されるので、限定メモリと呼ばれます。 アルゴリズムのそれぞれの繰り返しは直線探索です。 すなわち、変数Xに関して、近似Hessian逆元から計算される探索方向の線(ray)に沿っての探索です。 FOMはいつも直線探索でうまく減少します。 普通(しかしいつもではありません)FOMの勾配のノルムも減少します。
iprintはlbfgsが印字する進捗メッセージを制御します。
iprint[1]iprint[1] controls the frequency of progress messages.
iprint[1] < 0進捗メッセージなし。
iprint[1] = 0最初と最後の繰り返しでメッセージ。
iprint[1] > 0毎iprint[1]回の繰り返してメッセージを印字する。
iprint[2]iprint[2]は進捗メッセージの量を制御します。
iprint[2] = 0繰り返し回数、FOMの評価回数、FOMの値、FOMの勾配のノルム、ステップ長 を印字します。
iprint[2] = 1iprint[2] = 0に加えて、
X0とX0で評価されたFOMの勾配を印字します。
iprint[2] = 2iprint[2] = 1に加えて、
繰り返しそれぞれでXの値を印字します。
iprint[2] = 3iprint[2] = 2に加えて、
繰り返しそれぞれでFOMの勾配を印字します。
lbfgsが印字する列は以下の通りです。
I繰り返し関数。それぞれの直線探索で増えます。
NFN性能指標の評価回数。
FUNC最も最近の直線探索の最後での性能指標の値。
GNORM最も最近の直線探索の最後での性能指標の勾配のノルム。
STEPLENGTH探索アルゴリズムの内部パラメータ。
アルゴリズムの詳細に関係する付加情報は、元々のFortranコード[2]のコメントに見つけられます。
lbfgs_nfeval_maxとlbfgs_ncorrectionsも参照してください。
参考文献:
[1] D. Liu and J. Nocedal. "On the limited memory BFGS method for large scale optimization". Mathematical Programming B 45:503–528 (1989)
[2] http://netlib.org/opt/lbfgs_um.shar
例:
NetlibからのLBFGSパッケージの中で、プログラムsdrive.f中、 FGCOMPUTEが計算したのと同じFOM。 問題の変数が添字付き変数であることに注意してください。 FOMはu[k] = 1(k = 1, ..., 8)で0に等しい厳密な最小を持ちます。
(%i1) load ("lbfgs");
(%o1) /usr/share/maxima/5.10.0cvs/share/lbfgs/lbfgs.mac
(%i2) t1[j] := 1 - u[j];
(%o2) t1 := 1 - u
j j
(%i3) t2[j] := 10*(u[j + 1] - u[j]^2);
2
(%o3) t2 := 10 (u - u )
j j + 1 j
(%i4) n : 8;
(%o4) 8
(%i5) FOM : sum (t1[2*j - 1]^2 + t2[2*j - 1]^2, j, 1, n/2);
2 2 2 2 2 2
(%o5) 100 (u - u ) + (1 - u ) + 100 (u - u ) + (1 - u )
8 7 7 6 5 5
2 2 2 2 2 2
+ 100 (u - u ) + (1 - u ) + 100 (u - u ) + (1 - u )
4 3 3 2 1 1
(%i6) lbfgs (FOM, '[u[1],u[2],u[3],u[4],u[5],u[6],u[7],u[8]],
[-1.2, 1, -1.2, 1, -1.2, 1, -1.2, 1], 1e-3, [1, 0]);
*************************************************
N= 8 NUMBER OF CORRECTIONS=25
INITIAL VALUES
F= 9.680000000000000D+01 GNORM= 4.657353755084532D+02
*************************************************
I NFN FUNC GNORM STEPLENGTH 1 3 1.651479526340304D+01 4.324359291335977D+00 7.926153934390631D-04 2 4 1.650209316638371D+01 3.575788161060007D+00 1.000000000000000D+00 3 5 1.645461701312851D+01 6.230869903601577D+00 1.000000000000000D+00 4 6 1.636867301275588D+01 1.177589920974980D+01 1.000000000000000D+00 5 7 1.612153014409201D+01 2.292797147151288D+01 1.000000000000000D+00 6 8 1.569118407390628D+01 3.687447158775571D+01 1.000000000000000D+00 7 9 1.510361958398942D+01 4.501931728123680D+01 1.000000000000000D+00 8 10 1.391077875774294D+01 4.526061463810632D+01 1.000000000000000D+00 9 11 1.165625686278198D+01 2.748348965356917D+01 1.000000000000000D+00 10 12 9.859422687859137D+00 2.111494974231644D+01 1.000000000000000D+00 11 13 7.815442521732281D+00 6.110762325766556D+00 1.000000000000000D+00 12 15 7.346380905773160D+00 2.165281166714631D+01 1.285316401779533D-01 13 16 6.330460634066370D+00 1.401220851762050D+01 1.000000000000000D+00 14 17 5.238763939851439D+00 1.702473787613255D+01 1.000000000000000D+00 15 18 3.754016790406701D+00 7.981845727704576D+00 1.000000000000000D+00 16 20 3.001238402309352D+00 3.925482944716691D+00 2.333129631296807D-01 17 22 2.794390709718290D+00 8.243329982546473D+00 2.503577283782332D-01 18 23 2.563783562918759D+00 1.035413426521790D+01 1.000000000000000D+00 19 24 2.019429976377856D+00 1.065187312346769D+01 1.000000000000000D+00 20 25 1.428003167670903D+00 2.475962450826961D+00 1.000000000000000D+00 21 27 1.197874264861340D+00 8.441707983493810D+00 4.303451060808756D-01 22 28 9.023848941942773D-01 1.113189216635162D+01 1.000000000000000D+00 23 29 5.508226405863770D-01 2.380830600326308D+00 1.000000000000000D+00 24 31 3.902893258815567D-01 5.625595816584421D+00 4.834988416524465D-01 25 32 3.207542206990315D-01 1.149444645416472D+01 1.000000000000000D+00 26 33 1.874468266362791D-01 3.632482152880997D+00 1.000000000000000D+00 27 34 9.575763380706598D-02 4.816497446154354D+00 1.000000000000000D+00 28 35 4.085145107543406D-02 2.087009350166495D+00 1.000000000000000D+00 29 36 1.931106001379290D-02 3.886818608498966D+00 1.000000000000000D+00 30 37 6.894000721499670D-03 3.198505796342214D+00 1.000000000000000D+00 31 38 1.443296033051864D-03 1.590265471025043D+00 1.000000000000000D+00 32 39 1.571766603154336D-04 3.098257063980634D-01 1.000000000000000D+00 33 40 1.288011776581970D-05 1.207784183577257D-02 1.000000000000000D+00 34 41 1.806140173752971D-06 4.587890233385193D-02 1.000000000000000D+00 35 42 1.769004645459358D-07 1.790537375052208D-02 1.000000000000000D+00 36 43 3.312164100763217D-10 6.782068426119681D-04 1.000000000000000D+00
THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS.
IFLAG = 0
(%o6) [u = 1.000005339815974, u = 1.000009942839805,
1 2
u = 1.000005339815974, u = 1.000009942839805,
3 4
u = 1.000005339815974, u = 1.000009942839805,
5 6
u = 1.000005339815974, u = 1.000009942839805]
7 8
回帰問題。
FOMは、予言値F(X[i])と観測値Y[i]の二乗平均差です。
関数Fは有界な単調関数(いわゆる「シグモイド」函数)です。
この例では、Fのパラメータに関してlbfgsは近似値を計算し、
plot2dはFの観測データとの比較を表示します。
(%i1) load ("lbfgs");
(%o1) /usr/share/maxima/5.10.0cvs/share/lbfgs/lbfgs.mac
(%i2) FOM : '((1/length(X))*sum((F(X[i]) - Y[i])^2, i, 1,
length(X)));
2
sum((F(X ) - Y ) , i, 1, length(X))
i i
(%o2) -----------------------------------
length(X)
(%i3) X : [1, 2, 3, 4, 5];
(%o3) [1, 2, 3, 4, 5]
(%i4) Y : [0, 0.5, 1, 1.25, 1.5];
(%o4) [0, 0.5, 1, 1.25, 1.5]
(%i5) F(x) := A/(1 + exp(-B*(x - C)));
A
(%o5) F(x) := ----------------------
1 + exp((- B) (x - C))
(%i6) ''FOM;
A 2 A 2
(%o6) ((----------------- - 1.5) + (----------------- - 1.25)
- B (5 - C) - B (4 - C)
%e + 1 %e + 1
A 2 A 2
+ (----------------- - 1) + (----------------- - 0.5)
- B (3 - C) - B (2 - C)
%e + 1 %e + 1
2
A
+ --------------------)/5
- B (1 - C) 2
(%e + 1)
(%i7) estimates : lbfgs (FOM, '[A, B, C], [1, 1, 1], 1e-4, [1, 0]);
*************************************************
N= 3 NUMBER OF CORRECTIONS=25
INITIAL VALUES
F= 1.348738534246918D-01 GNORM= 2.000215531936760D-01
*************************************************
I NFN FUNC GNORM STEPLENGTH 1 3 1.177820636622582D-01 9.893138394953992D-02 8.554435968992371D-01 2 6 2.302653892214013D-02 1.180098521565904D-01 2.100000000000000D+01 3 8 1.496348495303005D-02 9.611201567691633D-02 5.257340567840707D-01 4 9 7.900460841091139D-03 1.325041647391314D-02 1.000000000000000D+00 5 10 7.314495451266917D-03 1.510670810312237D-02 1.000000000000000D+00 6 11 6.750147275936680D-03 1.914964958023047D-02 1.000000000000000D+00 7 12 5.850716021108205D-03 1.028089194579363D-02 1.000000000000000D+00 8 13 5.778664230657791D-03 3.676866074530332D-04 1.000000000000000D+00 9 14 5.777818823650782D-03 3.010740179797255D-04 1.000000000000000D+00
THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS.
IFLAG = 0
(%o7) [A = 1.461933911464101, B = 1.601593973254802,
C = 2.528933072164854]
(%i8) plot2d ([F(x), [discrete, X, Y]], [x, -1, 6]), ''estimates;
(%o8)
FOMの勾配が(自動的に計算される代わりに)指定されます。
(%i1) load ("lbfgs")$
(%i2) F(a, b, c) := (a - 5)^2 + (b - 3)^4 + (c - 2)^6;
2 4 6
(%o2) F(a, b, c) := (a - 5) + (b - 3) + (c - 2)
(%i3) F_grad : map (lambda ([x], diff (F(a, b, c), x)), [a, b, c]);
3 5
(%o3) [2 (a - 5), 4 (b - 3) , 6 (c - 2) ]
(%i4) estimates : lbfgs ([F(a, b, c), F_grad],
[a, b, c], [0, 0, 0], 1e-4, [1, 0]);
*************************************************
N= 3 NUMBER OF CORRECTIONS=25
INITIAL VALUES
F= 1.700000000000000D+02 GNORM= 2.205175729958953D+02
*************************************************
I NFN FUNC GNORM STEPLENGTH 1 2 6.632967565917638D+01 6.498411132518770D+01 4.534785987412505D-03 2 3 4.368890936228036D+01 3.784147651974131D+01 1.000000000000000D+00 3 4 2.685298972775190D+01 1.640262125898521D+01 1.000000000000000D+00 4 5 1.909064767659852D+01 9.733664001790506D+00 1.000000000000000D+00 5 6 1.006493272061515D+01 6.344808151880209D+00 1.000000000000000D+00 6 7 1.215263596054294D+00 2.204727876126879D+00 1.000000000000000D+00 7 8 1.080252896385334D-02 1.431637116951849D-01 1.000000000000000D+00 8 9 8.407195124830908D-03 1.126344579730013D-01 1.000000000000000D+00 9 10 5.022091686198527D-03 7.750731829225274D-02 1.000000000000000D+00 10 11 2.277152808939775D-03 5.032810859286795D-02 1.000000000000000D+00 11 12 6.489384688303218D-04 1.932007150271008D-02 1.000000000000000D+00 12 13 2.075791943844548D-04 6.964319310814364D-03 1.000000000000000D+00 13 14 7.349472666162257D-05 4.017449067849554D-03 1.000000000000000D+00 14 15 2.293617477985237D-05 1.334590390856715D-03 1.000000000000000D+00 15 16 7.683645404048675D-06 6.011057038099201D-04 1.000000000000000D+00
THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS.
IFLAG = 0
(%o4) [a = 5.000086823042934, b = 3.05239542970518,
c = 1.927980629919583]
デフォルト値: 100
lbfgs_nfeval_maxは、lbfgsがする性能指標(FOM)の評価の最大回数です。
lbfgs_nfeval_maxに届いた時、
lbfgsは最後に成功した直線探索の結果を返します。
デフォルト値: 25
lbfgs_ncorrectionsはlbfgsが保つ近似逆Hessian行列に適用された修正回数です。