[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

66. lbfgs


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

Categories:  Numerical methods · Optimization · Share packages · Package lbfgs


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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の無制約最小化の近似解を見つけます。

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

適用されるアルゴリズムは限定メモリ準 Newton(BFGS)アルゴリズム [1]です。 Hessian行列の逆元全体の代わりに低ランク近似が保存されるので、限定メモリと呼ばれます。 アルゴリズムのそれぞれの繰り返しは直線探索です。 すなわち、変数 Xに関して、近似 Hessian逆元から計算される探索方向の線 (ray)に沿っての探索です。 FOMはいつも直線探索でうまく減少します。 (いつもではありませんが)普通 FOMの勾配のノルムも減少します。

iprintlbfgsが印字する進捗メッセージを制御します。

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に加えて、 X0X0で評価された 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_maxlbfgs_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は近似値を計算し、 plot2dFの観測データとの比較を表示します。

 
(%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_ncorrectionslbfgsが保つ近似逆 Hessian行列に適用された修正回数です。

Categories:  Package lbfgs


[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by 市川雄二 on October, 5 2017 using texi2html 1.76.