66. lbfgs

66.1 Introduction to 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

66.2 Functions and Variables for lbfgs

関数: lbfgs  
    lbfgs (FOM, X, X0, epsilon, iprint)  
    lbfgs ([FOM, grad] X, X0, epsilon, iprint)

初期見積もり X0から始めて 変数リスト X上での、 norm(grad(FOM)) < epsilon*max(1, norm(X))のような性能指標 FOMの無制約最小化の近似解を見つけます。

もし与えられたなら、 gradは FOMの多変数 Xに関する勾配です。 gradは Xの要素それぞれに対して要素を1つ持つリストかリストを返す関数です。 もし与えられなかったら、勾配を記号微分で自動的に計算します。 もし FOMが関数なら、勾配 gradを共有しなければいけません。

適用されるアルゴリズムは限定メモリ準 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)$ (%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.657353755084533D+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.501931728123679D+01 1.000000000000000D+00 8 10 1.391077875774293D+01 4.526061463810630D+01 1.000000000000000D+00 9 11 1.165625686278198D+01 2.748348965356907D+01 1.000000000000000D+00 10 12 9.859422687859144D+00 2.111494974231706D+01 1.000000000000000D+00 11 13 7.815442521732282D+00 6.110762325764183D+00 1.000000000000000D+00 12 15 7.346380905773044D+00 2.165281166715009D+01 1.285316401779678D-01 13 16 6.330460634066464D+00 1.401220851761508D+01 1.000000000000000D+00 14 17 5.238763939854303D+00 1.702473787619218D+01 1.000000000000000D+00 15 18 3.754016790406625D+00 7.981845727632704D+00 1.000000000000000D+00 16 20 3.001238402313225D+00 3.925482944745832D+00 2.333129631316462D-01 17 22 2.794390709722064D+00 8.243329982586480D+00 2.503577283802312D-01 18 23 2.563783562920545D+00 1.035413426522664D+01 1.000000000000000D+00 19 24 2.019429976373283D+00 1.065187312340952D+01 1.000000000000000D+00 20 25 1.428003167668592D+00 2.475962450735100D+00 1.000000000000000D+00 21 27 1.197874264859232D+00 8.441707983339661D+00 4.303451060697367D-01 22 28 9.023848942003913D-01 1.113189216665625D+01 1.000000000000000D+00 23 29 5.508226405855795D-01 2.380830599637816D+00 1.000000000000000D+00 24 31 3.902893258879521D-01 5.625595817143044D+00 4.834988416747262D-01 25 32 3.207542206881058D-01 1.149444645298493D+01 1.000000000000000D+00 26 33 1.874468266118200D-01 3.632482152347445D+00 1.000000000000000D+00 27 34 9.575763380282112D-02 4.816497449000391D+00 1.000000000000000D+00 28 35 4.085145106760390D-02 2.087009347116811D+00 1.000000000000000D+00 29 36 1.931106005512628D-02 3.886818624052740D+00 1.000000000000000D+00 30 37 6.894000636920714D-03 3.198505769992936D+00 1.000000000000000D+00 31 38 1.443296008850287D-03 1.590265460381961D+00 1.000000000000000D+00 32 39 1.571766574930155D-04 3.098257002223532D-01 1.000000000000000D+00 33 40 1.288011779655132D-05 1.207784334505595D-02 1.000000000000000D+00 34 41 1.806140190993455D-06 4.587890258846915D-02 1.000000000000000D+00 35 42 1.769004612050548D-07 1.790537363138099D-02 1.000000000000000D+00 36 43 3.312164244118216D-10 6.782068546986653D-04 1.000000000000000D+00

THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS. IFLAG = 0 (%o6) [u = 1.000005339816132, u = 1.000009942840108, 1 2 u = 1.000005339816132, u = 1.000009942840108, 3 4 u = 1.000005339816132, u = 1.000009942840108, 5 6 u = 1.000005339816132, u = 1.000009942840108] 7 8

回帰問題。 FOMは予言値 F(X[i])と観測値 Y[i]の二乗平均差です。 関数 Fは有界な単調関数(いわゆる「シグモイド」函数)です。 この例では、 Fのパラメータに関して lbfgsは近似値を計算し、 plot2dは Fの観測データとの比較を表示します。

(%i1) load (lbfgs)$ (%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.496348495303004D-02 9.611201567691624D-02 5.257340567840710D-01 4 9 7.900460841091138D-03 1.325041647391314D-02 1.000000000000000D+00 5 10 7.314495451266914D-03 1.510670810312226D-02 1.000000000000000D+00 6 11 6.750147275936668D-03 1.914964958023037D-02 1.000000000000000D+00 7 12 5.850716021108202D-03 1.028089194579382D-02 1.000000000000000D+00 8 13 5.778664230657800D-03 3.676866074532179D-04 1.000000000000000D+00 9 14 5.777818823650780D-03 3.010740179797108D-04 1.000000000000000D+00

THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS. IFLAG = 0 (%o7) [A = 1.461933911464101, B = 1.601593973254801, C = 2.528933072164855] (%i8) plot2d ([F(x), [discrete, X, Y]], [x, -1, 6]), ''estimates; (%o8)

FOMの勾配が(自動的に計算される代わりに)指定されます。 FOMとその勾配の両方を関数として lbfgsに渡します。

(%i1) load (lbfgs)$ (%i2) F(a, b, c) := (a - 5)^2 + (b - 3)^4 + (c - 2)^6$ (%i3) define(F_grad(a, b, c), map (lambda ([x], diff (F(a, b, c), x)), [a, b, c]))$ (%i4) estimates : lbfgs ([F, 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.632967565917637D+01 6.498411132518770D+01 4.534785987412505D-03 2 3 4.368890936228036D+01 3.784147651974131D+01 1.000000000000000D+00 3 4 2.685298972775191D+01 1.640262125898520D+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.215263596054292D+00 2.204727876126877D+00 1.000000000000000D+00 7 8 1.080252896385329D-02 1.431637116951845D-01 1.000000000000000D+00 8 9 8.407195124830860D-03 1.126344579730008D-01 1.000000000000000D+00 9 10 5.022091686198525D-03 7.750731829225275D-02 1.000000000000000D+00 10 11 2.277152808939775D-03 5.032810859286796D-02 1.000000000000000D+00 11 12 6.489384688303218D-04 1.932007150271009D-02 1.000000000000000D+00 12 13 2.075791943844547D-04 6.964319310814365D-03 1.000000000000000D+00 13 14 7.349472666162258D-05 4.017449067849554D-03 1.000000000000000D+00 14 15 2.293617477985238D-05 1.334590390856715D-03 1.000000000000000D+00 15 16 7.683645404048675D-06 6.011057038099202D-04 1.000000000000000D+00

THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS. IFLAG = 0 (%o4) [a = 5.000086823042934, b = 3.052395429705181, c = 1.927980629919583]

Categories:  Package lbfgs

変数: lbfgs_nfeval_max

デフォルト値: 100

lbfgs_nfeval_maxは、lbfgsがする性能指標 (FOM)の評価の最大回数です。 lbfgs_nfeval_maxに届いた時、 lbfgsは最後に成功した直線探索の結果を返します。

Categories:  Package lbfgs

変数: lbfgs_ncorrections

デフォルト値: 25

lbfgs_ncorrectionsは lbfgsが保つ近似逆 Hessian行列に適用された修正回数です。

Categories:  Package lbfgs

This document was generated by 市川雄二 on June, 21 2016 using texi2html 1.76.