logo标签列表

scipy.optimize.fmin_l_bfgs_b返回'ABNORMAL_TERMINATION_IN_LNSRCH'

optimizationmachine-learningstatisticsnormal-distributiongradient-descent
28

我正在使用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.

我并非每次都收到这个警告，但有时会出现。(大多数是“收敛: 迭代梯度范数≤PGTOL”或“收敛: F的相对减少≤FACTR*EPSMCH”)。

我知道这意味着在这次迭代中可以达到最小值。我谷歌了一下这个问题。有人说经常发生这种情况是因为目标和梯度函数不匹配。但是我这里没有提供梯度函数，因为我使用了'approx_grad'。

我应该调查哪些可能的原因？什么是“舍入误差占据计算主导地位”的意思？

======

我还发现对数似然不单调增加：

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

通常在第二或第三次迭代时开始下降，即使没有出现'ABNORMAL_TERMINATION_IN_LNSRCH'问题。我不知道这个问题是否与以前的问题有关。

我遇到了类似的问题。它们似乎都集中在我给优化器的梯度函数上。你能百分之百确定你的梯度是完全正确的吗？ - jschabs
当我尝试最大化一个函数的对数似然时，我使用L-BFGS也遇到了类似的问题。需要补充说明的是，我没有传递函数的梯度，而是让L-BFGS来近似计算。有时候，我会使用Nelder-Mead优化器来解决这个问题...你能解决这个问题吗？ - muammar
@muammar，根据我的经验，使用L-BFGS时只有在提供显式导数函数时才能很好地工作。否则，它很容易迷失方向。 - ap21
4个回答
82

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次都是如此。编写此代码的人Jorge Nocedal（顺便说一下，他非常聪明）之所以使用20是因为基本上这已经足够了。机器epsilon为10E-16，我认为20实际上有点过多。所以，对于大多数遇到此问题的人，我的建议是您的梯度与函数不匹配。现在，也可能是“2.舍入误差支配计算”。他的意思是，您的功能是一个非常平坦的表面，其中增加的数量是机器epsilon的数量级（在这种情况下，您可以重新缩放该函数），现在，我在想可能应该有第三种选择，当您的功能太奇怪时。振荡？我可以看到类似于$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个月。我将其放在这里以备将来之需。

4
如果目标函数（或可能的梯度）变为 nan，也会打印出这个错误信息。 - Ilya Kolpakov
1
代码尝试在您提供的下降方向上进行20次所谓的线搜索，并意识到您并未告诉它往下走，而是往上走。这难道不意味着它已经找到了局部最优解，应该结束而不是抛出错误吗？ - El Dude
Nocedal的代码在另一个位置捕获收敛。 - Wilmer E. Henao
7

正如Wilmer E. Henao的回答中所指出的那样，问题可能在于梯度。由于您使用了approx_grad=True，因此梯度是通过数值计算得出的。在这种情况下，减小用于数值计算梯度的步长epsilon的值可以有所帮助。

1
将 epsilon 减小 4 个数量级在我的情况下有所帮助！ - dermen
Scipy在哪里调用这个函数？我想知道在哪里可以编辑L-BFGS-B的参数。 - learningthemachine
@learningthemachine，scipy.optimize.fmin_l_bfgs_b 可能在很多地方被调用。它存在的目的是让你随时可以调用它。 - toliveira
6
我用L-BFGS-B优化器也遇到了"ABNORMAL_TERMINATION_IN_LNSRCH"错误。
虽然我的梯度函数指向正确的方向，但我通过其L2-范数重新缩放了函数的实际梯度。移除或添加其他适当类型的缩放可以解决此问题。以前，我猜测梯度太大，导致立即超出范围。
如果我理解正确的话，OP的问题是无界的，因此在这个问题设置中，这肯定不会有所帮助。但是，通过搜索错误“ABNORMAL_TERMINATION_IN_LNSRCH”，可以将此页面作为第一个结果之一，因此它可能会帮助其他人...
4
我最近遇到了类似的问题。使用scipy的fmin_l_bfgs_b函数后，我有时会遇到ABNORMAL_TERMINATION_IN_LNSRCH消息。我尝试解释一下为什么会出现这种情况，如果我有错误的地方，我希望能得到补充说明或更正。
在我的情况下，我提供了梯度函数，因此approx_grad=False。我的代价函数和梯度是一致的。我进行了双重检查，大多数情况下优化实际上都可以正常工作。当我遇到ABNORMAL_TERMINATION_IN_LNSRCH时，解决方案并不是最优的，甚至不接近（即使这是一个主观的观点）。我可以通过修改maxls参数来解决这个问题。增加maxls有助于解决这个问题，最终得到最优解。然而，我注意到，有时比产生ABNORMAL_TERMINATION_IN_LNSRCH的那个更小的maxls会导致收敛解。数据框总结了结果。我惊讶地发现这一点。我预计减少maxls不会改善结果。因此，我尝试阅读描述线搜索算法的论文，但我很难理解它。
线搜索算法生成一系列嵌套间隔{Ik}和αk∈Ik∩[αmin；αmax]的迭代序列，根据[...]过程。如果我理解正确，我会说maxls参数指定了这个序列的长度。在maxls次迭代结束时（或更少，如果算法在较少的迭代中终止），线性搜索停止。最终试验点在最终间隔Imaxls内生成。我会说，这个公式不能保证得到一个满足两个更新条件（最小减少和曲率）的αmaxls，特别是当区间仍然很宽时。我猜想，在我的情况下，经过11次迭代后，生成的区间I11使得试验点α11同时满足这两个条件。但是，即使I12更小且仍包含可接受的点，α12也不满足条件。最终，在24次迭代后，间隔非常小，生成的αk符合更新条件。

我的理解/解释是否准确？如果是这样，那么当maxls=12时我会感到惊讶，因为生成的α11可接受但α12不可接受，为什么此时不选择α11而选择α12？

从实用角度考虑，建议在出现ABNORMAL_TERMINATION_IN_LNSRCH错误时尝试几个更高的maxls。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接