[ < ] | [ > ] | [ << ] | [上] | [ >> ] | [冒頭] | [目次] | [見出し] | [ ? ] |
61.1 Introduction to lbfgs | ||
61.2 Functions and Variables for lbfgs |
[ < ] | [ > ] | [ << ] | [上] | [ >> ] | [冒頭] | [目次] | [見出し] | [ ? ] |
lbfgs
は L-BFGS algorithm [1]の実装であり、
限定メモリ準Newton (BFGS)アルゴリズムによって無制約な最小化問題を解きます。
Hessian行列の逆元全体の代わりに低ランク近似が保存されるので、限定メモリと呼ばれます。
最初、
Jorge J. MoréとDavid J. Thuenteが最初に書いたいくつかの関数を組み入れて
Jorge Nocedalがプログラムを 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
Categories: Numerical methods ·Optimization ·Share packages ·Package lbfgs
[ < ] | [ > ] | [ << ] | [上] | [ >> ] | [冒頭] | [目次] | [見出し] | [ ? ] |
初期見積もり X0から始めて 変数リスト X上での、 norm(grad(FOM)) < epsilon*max(1, norm(X))のような性能指標 FOMの無制約最小化の近似解を見つけます。
もし与えられたなら、 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] = 1
iprint[2] = 0
に加えて、
X0と X0で評価された FOMの勾配を印字します。
iprint[2] = 2
iprint[2] = 1
に加えて、
繰り返しそれぞれで Xの値を印字します。
iprint[2] = 3
iprint[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] |
Categories: Package lbfgs
デフォルト値: 100
lbfgs_nfeval_max
は、lbfgs
がする性能指標 (FOM)の評価の最大回数です。
lbfgs_nfeval_max
に届いた時、
lbfgs
は最後に成功した直線探索の結果を返します。
Categories: Package lbfgs
デフォルト値: 25
lbfgs_ncorrections
は lbfgs
が保つ近似逆
Hessian行列に適用された修正回数です。
Categories: Package lbfgs
[ << ] | [ >> ] | [冒頭] | [目次] | [見出し] | [ ? ] |
この文書は市川 雄二によって2012年1月月7日にtexi2html 1.82を用いて生成されました。