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

Question

Ich benutze scipy.optimize.fmin_l_bfgs_b, um ein Problem mit der Gaußschen Mischung zu lösen. Die Mittel der Gemischverteilungen werden durch Regressionen modelliert, deren Gewichte mit Hilfe des 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 habe ich eine Warnung ‚ABNORMAL_TERMINATION_IN_LNSRCH‘ im Informations Wörterbuch:

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 kapier das nicht jedes Mal warnen, aber manchmal. (Die meisten erhalten 'KONVERGENZ: NORM_OF_PROJECTED_GRADIENT_ < = _PGTOL' oder 'KONVERGENZ: REL_REDUCTION_OF_F_ < = _FACTR * EPSMCH').

Ich weiß, dass es bedeutet, dass das Minimum in dieser Iteration erreicht werden kann. Ich habe dieses Problem gegooglet. Jemand sagte, dass es häufig vorkommt, weil die Ziel- und Gradientenfunktionen nicht übereinstimmen. Aber hier stelle ich keine Gradientenfunktion zur Verfügung, weil ich 'approxgrad' verwende.

Was sind die möglichen Gründe, die ich untersuchen sollte? Was bedeutet "Rundungsfehler dominieren"?

======

Ich finde auch, dass die Log-Likelihood nicht erhöht monoton:

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

Es normalerweise Abnahme bei der zweiten oder der dritten Iteration beginnen, auch durch ‚ABNORMAL_TERMINATION_IN_LNSRCH 'tritt nicht auf. Ich weiß nicht, ob dieses Problem mit dem vorherigen zusammenhängt.

Answer 1

Scipy ruft die ursprüngliche L-BFGS-B-Implementierung auf. Das ist etwas Fortran77 (alt, aber wunderschön und superschneller Code) und unser Problem ist, dass die Abstiegsrichtung tatsächlich steigt. Das Problem beginnt, auf der Leitung 2533 (Link zu dem Code unten)

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 es den Hügel hinuntergehen durch den Berg hinauf. Der Code versucht insgesamt 20 Mal in der von Ihnen angegebenen Abstiegsrichtung eine so genannte Liniensuche und stellt fest, dass Sie ihm NICHT sagen, dass er bergab fahren soll, sondern bergauf. Alle 20 mal.

Der Typ, der es geschrieben hat (Jorge Nocedal, der übrigens ein sehr schlauer Typ ist) legte 20, weil ziemlich viel genug ist. Maschine Epsilon ist 10E-16, ich denke, 20 ist eigentlich ein bisschen zu viel. Also, mein Geld für die meisten Menschen mit diesem Problem ist, dass Ihr Farbverlauf nicht Ihre Funktion entspricht.

Nun könnte es auch sein, dass "2. Rundungsfehler die Berechnung dominieren". Damit meint er, dass deine Funktion eine sehr flache Oberfläche ist, in der die Zunahmen in der Größenordnung von Maschinen-Epsilon liegen (in diesem Fall könntest du vielleicht die Funktion neu skalieren), Nun war ich der Meinung, dass es vielleicht eine dritte Option geben sollte. wenn deine 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 Typ, also glaube nicht, dass es einen dritten Fall gibt.

Also ich denke, die OP-Lösung sollte sein, dass Ihre Funktion zu flach ist. Oder sehen Sie sich den Fortran-Code an.

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

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

Hinweis. Das ist 7 Monate zu spät. Ich lege es hier um der Zukunft willen.