python - scipy优化中的整数步长最小化

Question

我有一个计算机视觉算法，我想使用scipy.optimize.minimize进行调整。现在我只想调整两个参数，但参数的数量最终可能会增加，所以我想使用一种可以进行高维梯度搜索的技术。SciPy 中的 Nelder-Mead 实现似乎很合适。

我把代码全部设置好了，但似乎最小化函数真的想使用步长小于一的浮点值。当前的参数集都是整数，一个有一个步长，另一个步长为 2（即该值必须是奇数，如果不是我要优化的东西，会将其转换为奇数）。大致一个参数是以像素为单位的窗口大小，另一个参数是阈值（0-255 的值）。

值得我使用来自 git repo 的全新 scipy 版本。有谁知道如何告诉 scipy 为每个参数使用特定的步长？有什么方法可以滚动我自己的渐变函数吗？有没有可以帮助我的 scipy 标志？我知道这可以通过简单的参数扫描来完成，但我最终希望将此代码应用于更大的参数集。

代码本身非常简单：

import numpy as np
from scipy.optimize import minimize
from ScannerUtil import straightenImg 
import bson

def doSingleIteration(parameters):
    # do some machine vision magic
    # return the difference between my value and the truth value

parameters = np.array([11,10])
res = minimize( doSingleIteration, parameters, method='Nelder-Mead',options={'xtol': 1e-2, 'disp': True,'ftol':1.0,}) #not sure if these params do anything
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print res

这就是我的输出的样子。正如你所看到的，我们重复了很多次运行，但在最小化过程中没有任何进展。

*+++++++++++++++++++++++++++++++++++++++++
[ 11.  10.]  <-- Output from scipy minimize
{'block_size': 11, 'degree': 10} <-- input to my algorithm rounded and made int
+++++++++++++++++++++++++++++++++++++++++
120  <-- output of the function I am trying to minimize
+++++++++++++++++++++++++++++++++++++++++
[ 11.55  10.  ]
{'block_size': 11, 'degree': 10}
+++++++++++++++++++++++++++++++++++++++++
120
+++++++++++++++++++++++++++++++++++++++++
[ 11.   10.5]
{'block_size': 11, 'degree': 10}
+++++++++++++++++++++++++++++++++++++++++
120
+++++++++++++++++++++++++++++++++++++++++
[ 11.55   9.5 ]
{'block_size': 11, 'degree': 9}
+++++++++++++++++++++++++++++++++++++++++
120
+++++++++++++++++++++++++++++++++++++++++
[ 11.1375  10.25  ]
{'block_size': 11, 'degree': 10}
+++++++++++++++++++++++++++++++++++++++++
120
+++++++++++++++++++++++++++++++++++++++++
[ 11.275  10.   ]
{'block_size': 11, 'degree': 10}
+++++++++++++++++++++++++++++++++++++++++
120
+++++++++++++++++++++++++++++++++++++++++
[ 11.    10.25]
{'block_size': 11, 'degree': 10}
+++++++++++++++++++++++++++++++++++++++++
120
+++++++++++++++++++++++++++++++++++++++++
[ 11.275   9.75 ]
{'block_size': 11, 'degree': 9}
+++++++++++++++++++++++++++++++++++++++++
120
+++++++++++++++++++++++++++++++++++++++++
~~~
SNIP 
~~~
+++++++++++++++++++++++++++++++++++++++++
[ 11.         10.0078125]
{'block_size': 11, 'degree': 10}
+++++++++++++++++++++++++++++++++++++++++
120
Optimization terminated successfully.
         Current function value: 120.000000
         Iterations: 7
         Function evaluations: 27
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  status: 0
    nfev: 27
 success: True
     fun: 120.0
       x: array([ 11.,  10.])
 message: 'Optimization terminated successfully.'
     nit: 7*

score 6 · Accepted Answer

假设要最小化的函数是任意复杂的（非线性），这通常是一个非常困难的问题。除非您尝试所有可能的选项，否则无法保证最佳解决方案。我不知道是否有任何整数约束非线性优化器（有点怀疑），我假设您知道 Nelder-Mead 如果它是一个连续函数应该可以正常工作。

编辑：考虑到@Dougal 的评论，我将在此处添加：首先设置粗+细网格搜索，如果您想尝试 Nelder-Mead 是否有效（并且收敛速度更快），以下几点可能会有所帮助...

但也许有些点会有所帮助：

考虑到整个整数约束非常困难，也许可以选择做一些简单的插值来帮助优化器。它仍应收敛到整数解。当然这需要计算额外的分数，但它可能会解决许多其他问题。（即使在线性整数规划中，它通常首先解决无约束系统 AFAIK）
Nelder-Mead 从 N+1 点开始，这些在 scipy（至少是旧版本）中硬连线到(1+0.05) * x0[j]（对于j所有维度，除非x0[j]是 0），您将在第一个评估步骤中看到。也许这些可以在较新的版本中提供，否则您可以更改/复制 scipy 代码（它是纯 python）并将其设置为更合理的东西。或者，如果您觉得这更简单，请按比例缩小所有输入变量，使 (1+0.05)*x0 具有合理的大小。
也许您应该缓存所有函数评估，因为如果您使用 Nelder-Mead，我猜您总是会遇到重复评估（至少在最后）。
您必须检查 Nelder-Mead 缩小到单个值并放弃的可能性有多大，因为它总是找到相同的结果。
您通常必须检查您的函数是否表现良好......如果函数在参数空间上没有平滑变化，那么这种优化注定要失败，即使这样，如果您应该拥有这些，它也很容易陷入局部最小值。（因为您缓存了所有评估 - 请参阅 2。 - 您至少可以绘制这些并查看错误情况，而无需进行任何额外的评估）

score 2 · Accepted Answer

不幸的是，Scipy 的内置优化工具不容易做到这一点。但永远不要害怕；听起来你有一个凸问题，所以你应该能够找到一个唯一的最优值，即使它在数学上并不漂亮。

我针对不同问题实现的两个选项是创建自定义梯度下降算法，以及对一系列单变量问题使用二分法。如果您在调整中进行交叉验证，那么您的损失函数很遗憾不会平滑（因为来自不同数据集的交叉验证的噪声），但通常会是凸的。

要以数值方式实现梯度下降（没有用于评估梯度的分析方法），请选择一个测试点和一个delta在所有维度上都远离测试点的第二个点。在这两点评估损失函数可以让您以数值方式计算局部次梯度。重要的是delta要足够大，使其超出由交叉验证噪声产生的局部最小值。

一个较慢但可能更强大的替代方法是对您正在测试的每个参数实施二等分。如果您知道两个参数（或n 个参数）的联合凸问题，您可以将其分解为n 个单变量优化问题，并编写一个二分算法递归地磨练最佳参数。这可以帮助处理某些类型的准凸性（例如，如果您的损失函数对其域的一部分采用背景噪声值，并且在另一个区域中是凸的），但需要对初始迭代的边界进行很好的猜测。

如果您只是将请求的x值捕捉到整数网格而不固定xtol映射到该网格大小，您可能会让求解器请求网格单元内的两个点，接收相同的输出值，并得出结论它是最小值。

不幸的是，没有简单的答案。

score 1 · Accepted Answer

将浮点数 x、y（又名 winsize、阈值）捕捉到函数内的整数网格，如下所示：

def func( x, y ):
    x = round( x )
    y = round( (y - 1) / 2 ) * 2 + 1  # 1 3 5 ...
    ...

然后 Nelder-Mead 将仅在网格上看到函数值，并且应该为您提供接近整数的 x、y。

（如果您想在某个地方发布您的代码，我正在寻找重启的 Nelder-Mead 的测试用例。）

score 1 · Accepted Answer

Nelder-Mead 最小化方法现在允许您指定初始单纯形顶点，因此您应该能够将单纯形点设置为相距很远，然后单纯形将翻转并找到最小值并在单纯形大小降至 1 以下时收敛。

https://docs.scipy.org/doc/scipy/reference/optimize.minimize-neldermead.html#optimize-minimize-neldermead

score 1 · Accepted Answer

问题是该算法在试图缩小其 (N+1) 单纯形时陷入困境。我强烈建议任何刚接触这个概念的人了解更多关于单纯形的地理形状并弄清楚输入参数如何与单纯形上的点相关联。一旦你掌握了这一点，那么正如 IP Freeley 建议的那样，可以通过为你的单纯形定义强大的初始点来解决这个问题，请注意，这与定义你的 x0 不同，并进入nelder-mead 的专用选项。这是一个更高--4-维问题的示例。另请注意，在本例 5 和您的情况 3 中，初始单纯形必须具有 N+1 个点。

init_simplex = np.array([[1, .1, .3, .3], [.1, 1, .3, .3], [.1, .1, 5, .3],
                         [.1, .1, .3, 5], [1, 1, 5, 5]])
minimum = minimize(Optimize.simplex_objective, x0=np.array([.01, .01, .01, .01]),
                   method='Nelder-Mead',
                   options={'adaptive': True, 'xatol': 0.1, 'fatol': .00001,
                            'initial_simplex': init_simplex})

在本例中，x0 被 initial_simplex 的定义忽略。高维问题中其他有用的选项是“自适应”选项，它在尝试设置模型操作系数时考虑参数的数量（即分别用于反射、膨胀、收缩和收缩的 α、γ、ρ 和 σ） . 如果您还没有，我还建议您熟悉算法的步骤。

现在，这个问题发生的原因是因为该方法在扩展中没有得到好的结果，所以它不断地缩小单纯形，试图找出可能存在或不存在的更好的解决方案。

python - scipy优化中的整数步长最小化

5 回答 5

Related

Reference