scipy.optimize.fmin_l_bfgs_b возвращает «ABNORMAL_TERMINATION_IN_LNSRCH»

Я использую scipy.optimize.fmin_l_bfgs_b для решения проблемы гауссовой смеси. Средние распределения смесей моделируются регрессиями, веса которых должны быть оптимизированы с использованием алгоритма EM.

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)

Но иногда я получал предупреждение «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.

Я не получаю это предупреждение каждый раз, но иногда. (Большинство получают «СХОДИМОСТЬ: NORM_OF_PROJECTED_GRADIENT_‹=_PGTOL» или «СХОДИМОСТЬ: REL_REDUCTION_OF_F_‹=_FACTR*EPSMCH»).

Я знаю, что это означает, что минимум может быть достигнут в этой итерации. Я погуглил эту проблему. Кто-то сказал, что это происходит часто, потому что целевая функция и функция градиента не совпадают. Но здесь я не предоставляю функцию градиента, потому что использую «приблизительно_град».

Каковы возможные причины, которые я должен исследовать? Что означает выражение «ошибка округления преобладает в вычислениях»?

======

Я также обнаружил, что логарифмическая вероятность не увеличивается монотонно:

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

Обычно оно начинает уменьшаться на второй или третьей итерации, даже через 'ABNORMAL_TERMINATION_IN_LNSRCH' не происходит. Не знаю, связана ли эта проблема с предыдущей.


machine-learning optimization statistics gradient-descent normal-distribution
person Munichong    schedule 07.01.2016    source источник
comment
Я сталкиваюсь с подобными проблемами. Все они, кажется, сосредоточены на функции градиента, которую я даю оптимизатору. Вы со 100% уверенностью знаете, что ваш градиент полностью правильный?   -  person jschabs    schedule 14.04.2016
comment
Я получаю аналогичные проблемы с L-BFGS при попытке максимизировать логарифмическую вероятность функции. Я должен добавить, что я не передаю градиент функции, а вместо этого позволяю L-BFGS аппроксимировать его. Иногда мне удавалось решить эту проблему, используя оптимизатор Нелдера-Мида... Удалось ли вам решить эту проблему?   -  person muammar    schedule 17.06.2018
comment
@muammar, по моему опыту использования L-BFGS, он работает хорошо, только если вы предоставляете явную производную функцию. В противном случае он довольно легко теряется.   -  person ap21    schedule 12.09.2018

Ответы (3)


arrow_upward
70
arrow_downward

Scipy называет исходную реализацию L-BFGS-B. Какой-то fortran77 (старый, но красивый и сверхбыстрый код), и наша проблема в том, что направление спуска на самом деле идет вверх. Проблема начинается в строке 2533 (ссылка на код внизу)

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

Другими словами, вы говорите ему идти вниз с холма, поднимаясь на холм. Код пытается что-то, называемое линейным поиском, в общей сложности 20 раз в указанном вами направлении спуска и понимает, что вы НЕ говорите ему идти вниз, а вверх. Все 20 раз.

Парень, который это написал (Хорхе Носедал, который, кстати, очень умный парень) поставил 20, потому что этого вполне достаточно. Машина эпсилон это 10Е-16, мне кажется 20 на самом деле многовато. Итак, я уверен, что у большинства людей, имеющих эту проблему, будет то, что ваш градиент не соответствует вашей функции.

Теперь также может быть, что «2. ошибки округления преобладают в вычислениях». Под этим он подразумевает, что ваша функция представляет собой очень плоскую поверхность, на которой увеличение порядка машинного эпсилон (в этом случае вы, возможно, могли бы изменить масштаб функции). Теперь я подумал, что, возможно, должен быть третий вариант, когда ваша функция слишком странная. Колебания? Я мог видеть что-то вроде $\sin({\frac{1}{x}})$, вызывающее такого рода проблемы. Но я не умный парень, так что не думайте, что есть третий случай.

Поэтому я думаю, что решение OP должно заключаться в том, что ваша функция слишком плоская. Или посмотрите на код fortran.

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

Вот строка поиска для тех, кто хочет это увидеть. https://en.wikipedia.org/wiki/Line_search

Примечание. Это опоздание на 7 месяцев. Я положил его здесь на будущее.

person Wilmer E. Henao    schedule 25.08.2016
comment
Это сообщение об ошибке также выводится, если целевая функция (или, возможно, градиент) становится nan. - person aickley; 01.11.2018
comment
Код пытается что-то, называемое линейным поиском, в общей сложности 20 раз в указанном вами направлении спуска и понимает, что вы НЕ говорите ему идти вниз, а вверх. –– Не означает ли это, что он нашел локальный оптимум и должен завершиться, а не выдать ошибку? - person El Dude; 02.11.2018
comment
Код Nocedal улавливает сходимость в другом месте кода. - person Wilmer E. Henao; 12.11.2018

arrow_upward
5
arrow_downward

Как указано в ответе Уилмера Э. Энао, проблема, вероятно, в градиенте. Поскольку вы используете approx_grad=True, градиент рассчитывается численно. В этом случае может помочь уменьшение значения epsilon, которое представляет собой размер шага, используемый для численного расчета градиента.

person toliveira    schedule 13.10.2018
comment
В моем случае помогло уменьшение эпсилон на 4 порядка! - person dermen; 01.12.2019
comment
где scipy вызывает эту функцию? Я хочу знать, где я могу отредактировать параметры L-BFGS-B. - person learningthemachine; 09.02.2020
comment
@learningthemachine, scipy.optimize.fmin_l_bfgs_b, вероятно, вызывается во многих местах. Это там, так что вы можете вызвать его, когда вы хотите. - person toliveira; 18.02.2020

arrow_upward
4
arrow_downward

Я также получил ошибку "ABNORMAL_TERMINATION_IN_LNSRCH" при использовании оптимизатора L-BFGS-B.

Пока моя функция градиента указывала в правильном направлении, я перемасштабировал фактический градиент функции по его L2-норме. Удаление этого или добавление другого подходящего типа масштабирования сработало. Раньше я предполагаю, что градиент был настолько большим, что сразу выходил за пределы.

Проблема с ОП была неограничена, если я правильно прочитал, так что это точно не поможет в этой постановке проблемы. Однако поиск в Google ошибки «ABNORMAL_TERMINATION_IN_LNSRCH» дает эту страницу как один из первых результатов, так что это может помочь другим...

person gebbissimo    schedule 08.02.2019