webentwicklung-frage-antwort-db.com.de

scipy.optimize.fmin_l_bfgs_b gibt 'ABNORMAL_TERMINATION_IN_LNSRCH' zurück

Ich benutze scipy.optimize.fmin_l_bfgs_b, um ein Gaußscher Mischungsproblem zu lösen. Die Mittel der Gemischverteilungen werden durch Regressionen modelliert, deren Gewichte mit dem EM-Algorithmus optimiert werden müssen.

sigma_sp_new, func_val, info_dict = fmin_l_bfgs_b(func_to_minimize, self.sigma_vector[si][pj], 
                       args=(self.w_vectors[si][pj], Y, X, E_step_results[si][pj]),
                       approx_grad=True, bounds=[(1e-8, 0.5)], factr=1e02, pgtol=1e-05, epsilon=1e-08)

Aber manchmal bekam ich im Informationswörterbuch die Warnung 'ABNORMAL_TERMINATION_IN_LNSRCH': 

func_to_minimize value = 1.14462324063e-07
information dictionary: {'task': b'ABNORMAL_TERMINATION_IN_LNSRCH', 'funcalls': 147, 'grad': array([  1.77635684e-05,   2.87769808e-05,   3.51718654e-05,
         6.75015599e-06,  -4.97379915e-06,  -1.06581410e-06]), 'nit': 0, 'warnflag': 2}

RUNNING THE L-BFGS-B CODE

           * * *

Machine precision = 2.220D-16
 N =            6     M =           10
 This problem is unconstrained.

At X0         0 variables are exactly at the bounds

At iterate    0    f=  1.14462D-07    |proj g|=  3.51719D-05

           * * *

Tit   = total number of iterations
Tnf   = total number of function evaluations
Tnint = total number of segments explored during Cauchy searches
Skip  = number of BFGS updates skipped
Nact  = number of active bounds at final generalized Cauchy point
Projg = norm of the final projected gradient
F     = final function value

           * * *

   N    Tit     Tnf  Tnint  Skip  Nact     Projg        F
    6      1     21      1     0     0   3.517D-05   1.145D-07
  F =  1.144619474757747E-007

ABNORMAL_TERMINATION_IN_LNSRCH                              

 Line search cannot locate an adequate point after 20 function
  and gradient evaluations.  Previous x, f and g restored.
 Possible causes: 1 error in function or gradient evaluation;
                  2 rounding error dominate computation.

 Cauchy                time 0.000E+00 seconds.
 Subspace minimization time 0.000E+00 seconds.
 Line search           time 0.000E+00 seconds.

 Total User time 0.000E+00 seconds.

Ich bekomme diese Warnung nicht jedes Mal, aber manchmal. (Die meisten erhalten 'CONVERGENCE: NORM_OF_PROJECTED_GRADIENT _ <= _ PGTOL' oder 'CONVERGENCE: REL_REDUCTION_OF_F _ <= _ FACTR * EPSMCH').

Ich weiß, dass in dieser Iteration das Minimum erreicht werden kann. Ich habe dieses Problem gegoogelt. Jemand sagte, es kommt häufig vor, weil die Ziel- und die Gradientenfunktion nicht übereinstimmen. Aber hier habe ich keine Gradientenfunktion, weil ich 'approx_grad' verwende.

Welche möglichen Gründe sollte ich untersuchen? Was bedeutet "Rundungsfehler beherrschen die Berechnung"?

======

Ich finde auch, dass die log-Wahrscheinlichkeit nicht monoton steigt:

########## Convergence !!! ##########
log_likelihood_history: [-28659.725891322563, 220.49993177669558, 291.3513633060345, 267.47745327823907, 265.31567762171181, 265.07311121000367, 265.04217683341682]

Die Abnahme beginnt normalerweise bei der zweiten oder dritten Iteration, selbst wenn 'ABNORMAL_TERMINATION_IN_LNSRCH' nicht auftritt. Ich weiß nicht, ob es dieses Problem mit dem vorherigen zu tun hat.

12
Munichong

Scipy ruft die ursprüngliche L-BFGS-B-Implementierung auf. Was ist ein Fortran77 (alter, aber schöner und superschneller Code) und unser Problem ist, dass die Abstiegsrichtung tatsächlich nach oben geht. Das Problem beginnt in Zeile 2533 (Link zum Code am unteren Rand)

Gd = ddot(n,g,1,d,1)
  if (ifun .eq. 0) then
     gdold=Gd
     if (Gd .ge. zero) then
c                               the directional derivative >=0.
c                               Line search is impossible.
        if (iprint .ge. 0) then
            write(0,*)' ascent direction in projection Gd = ', Gd
        endif
        info = -4
        return
     endif
  endif

Mit anderen Worten, Sie sagen ihm, dass Sie den Hügel hinuntergehen sollen, indem Sie den Hügel hinaufgehen. Der Code versucht, die so genannte Zeilensuche insgesamt 20 Mal in der von Ihnen angegebenen Abstiegsrichtung auszuführen, und stellt fest, dass Sie NICHT sagen, dass Sie bergab, sondern bergauf gehen sollen. Alle 20 mal.

Der Kerl, der es geschrieben hat (Jorge Nocedal, der übrigens ein sehr kluger Kerl ist), hat 20 gesetzt, weil das ziemlich viel ist. Machine epsilon ist 10E-16, ich denke, 20 ist eigentlich etwas zu viel. Mein Geld für die meisten Leute mit diesem Problem ist also: Ihr Gradient passt nicht zu Ihrer Funktion .

Nun könnte es auch sein, dass "2. Rundungsfehler die Berechnung beherrschen". Er meint damit, dass Ihre Funktion eine sehr flache Oberfläche ist, in der Steigerungen in der Größenordnung von Maschinen-Epsilon sind (in diesem Fall könnten Sie vielleicht die Funktion neu skalieren), Nun, ich wollte, dass es vielleicht etwas geben sollte eine dritte Option, wenn Ihre Funktion zu komisch ist. Schwingungen? Ich könnte etwas wie $\sin ({\ frac {1} {x}}) $ sehen, das diese Art von Problem verursacht. Aber ich bin kein kluger Kerl, also gehe nicht davon aus, dass es einen dritten Fall gibt.

Ich denke, die Lösung des OP sollte sein, dass Ihre Funktion zu schwach ist. Oder schauen Sie sich den Fortran-Code an.

https://github.com/scipy/scipy/blob/master/scipy/optimize/lbfgsb/lbfgsb.f

Hier ist die Zeilensuche für diejenigen, die es sehen wollen. https://en.wikipedia.org/wiki/Line_search

Hinweis. Dies ist 7 Monate zu spät. Ich habe es der Zukunft wegen hier hingestellt.

47
Wilmer E. Henao

Ich habe auch den Fehler "ABNORMAL_TERMINATION_IN_LNSRCH" mit dem Optimierer L-BFGS-B erhalten.

Während meine Gradientenfunktion in die richtige Richtung zeigte, skalierte ich den tatsächlichen Gradienten der Funktion um die L2-Norm. Das Entfernen oder das Hinzufügen einer anderen geeigneten Art der Neuskalierung hat funktioniert. Ich vermute, dass der Gradient vorher so groß war, dass er sofort die Grenzen überschritt.

Das Problem von OP war unbegrenzt, wenn ich richtig gelesen habe, so dass dies bei dieser Problemeinstellung sicherlich nicht helfen wird. Wenn Sie den Fehler "ABNORMAL_TERMINATION_IN_LNSRCH" googeln, wird diese Seite jedoch als eines der ersten Ergebnisse angezeigt. Daher kann es anderen helfen ...

0
gebbissimo

In der Antwort von Wilmer E. Henao wurde darauf hingewiesen, dass das Problem wahrscheinlich im Gefälle liegt. Da Sie approx_grad=True verwenden, wird der Farbverlauf numerisch berechnet. In diesem Fall kann es hilfreich sein, den Wert von epsilon zu reduzieren. Dies ist die Schrittgröße, die zur numerischen Berechnung des Gradienten verwendet wird.

0
toliveira