「干货」2018值得尝试的无参数全局优化新算法

新智元报道 微信公众号：新智元（AI_era）

【新智元导读】本文介绍了一个名为LIPO的全局优化方法，这个方法没有参数，而且经验证比随机搜索方法好。基于此，作者提出了MaxLIPO和置信域方法混合使用的优化方法，在所有测试中，都取得了最优结果，而且不需要任何参数。你还在手动调参？不如试一下更好的方法。

有一个常见的问题：你想使用某个机器学习算法，但它总有一些难搞的超参数。例如权重衰减大小，高斯核宽度等等。算法不会设置这些参数，而是需要你去决定它们的值。如果不把这些参数设置为“良好”的值，这个算法就不会起作用。那么你会怎么做呢？下面我列出了我见过的人们的做法，从最常见到最不常见排序：

• 猜测和检查：听从你的直觉，选择感觉不错的数字，看看它们是否工作。一直持续这样做，直到厌倦。

• 网格搜索：让计算机尝试在一定范围内均匀分布的一组值。

• 随机搜索：让计算机随机挑选一组值。

• 贝叶斯优化：使用像MATLAB的bayesopt之类的工具来自动选择最佳参数，然后你会发现贝叶斯优化比你的机器学习算法有更多的超参数，你变得沮丧，然后回头使用猜测和检查或网格搜索。

• 在有一个良好的初始猜测的前提下进行局部优化：这就是MITIE的方法，它使用BOBYQA算法，并有一个精心选择的起始点。由于BOBYQA只寻找最近的局部最优解，所以这个方法是否成功很大程度上取决于是否有一个好的起点。在MITIE的情况下，我们知道一个好的起点，但这不是一个普遍的解决方案，因为通常你不会知道好的起点在哪里。从好的方面来说，这种方法非常适合寻找局部最优解。稍后我会再讨论这一点。

绝大多数人只会用猜测和检查的方法。但应该有更好的方法。我们都希望像贝叶斯优化这样的黑盒子优化策略有用，但根据我的经验，如果你没有将其超参数设置为正确的值，那么它还不如专业的猜测和检查。我认识的每个使用贝叶斯优化的人都有相同的经验。最终，如果我认为手动调参能做得更好，那么就手动呗，而且我的大多数同事也这样想。最终的结果是，我大部分时间都没有使用自动化的超参数选择工具。 我很想有一个无参数的全局优化器，可以信任地用它做超参数选择。

所以当我读到Cédric Malherbe和Nicolas Vayatis在去年的机器学习国际会议上发表的Global optimization of Lipschitz functions这篇论文时，我非常兴奋。在这篇论文中，他们提出了一个非常简单的无参数、而且经证明有效的方法来寻找使函数f(x)最大化的

，即使 f(x)有多个局部极大值。论文中的关键思想是保持f(x)的分段线性上界，并用它来决定在每个优化步骤中用于评估的x。因此，如果你已经评估了点x₁，x₂，...，xt，那么您可以在 f(x)上定义一个简单的上界，如下所示：

其中k是f(x)的Lipschitz常数。因此，根据Lipschitz常数的定义， U(x)≥f(x),∀x, 是正确的。作者继而提出一个简单的算法，称为LIPO，该算法随机挑选点，检查新点的upper bound是否比迄今所见的最佳点好，如果是，则选择它作为下一个点来评估。例如，下图显示了一个简单的f(x)函数（红色线），它相关的upper bound U(x)以绿色显示。在这种情况下， U(x) 由4个点定义，这里用小黑方块表示。

很容易看出upper bound如何帮助你选择好的点来评估。例如，如果你选择最大上界作为下一次迭代，那么你已经非常接近全局最大化。作者继续证明了这种方法的一些不错的特性。特别是，它们都是用数学方法证明的，并且在经验上也证明了在许多非平凡的情况下，这种方法比随机搜索更好。他们还将该方法与贝叶斯优化等其他算法进行比较，并显示出其竞争力。

但是你可能会想：“等一下，我们不知道Lipschitz常数k的值！” 这不是大问题，因为它很容易估计，例如，在每次迭代之前将k设置为f(x)的最大观察斜率。这相当于解决下面这个简单的问题：

Malherbe等人测试了这个k估计方法的变体，并显示它可以工作。

这方法很棒。我喜欢这篇论文。总结一下，它提出了一个名为LIPO的全局优化方法，这个方法没有参数，而且经验证比随机搜索方法好。而且它也很简单。所以我打算给dlib加入一些LIPO算法，我在最新的dlib v19.8版本中实践了。

但是，如果你想在实践中使用LIPO，还需要解决一些问题。这篇文章接下来的部分讨论了这些问题以及dlib实现如何解决这些问题。首先，如果 f(x) 有噪声或不连续，即使只有一点点，它也不能可靠地工作，因为k会变成无穷大。在现实世界的问题中总是会发生这种情况。其次，并不是所有的超参数都同等重要，有些参数几乎没有关系，而另一些参数的一点小变化都会对 f(x)的输出影响很大。所以如果每个超参数都有自己的k，那会很好。你可以通过定义上界U(x) 来解决这些问题，如下所示：

现在，来自 f(x) 的每个sample 都有自己的噪声项

，大部分时间它的值应该是0，除非

非常接近于不连续性或者存在一些随机性。在这里，K是一个对角线矩阵，包含“每个超参数一个Lipschitz k项”。通过这个公式，将每个σ设为0，

给出与Malherbe等人所提出的相同的U(x)，但是如果采取更一般的值，可以处理上面提到的问题。

像之前那样，我们可以通过求解一个优化问题来找到U(x)的参数：

σ²上的

的penalty使得大多数σ项恰好为0。整个算法的表现对于这里使用的特定penalty的值是不敏感的，只要它大得合理，那么大部分时间σ值都是0，同时仍然阻止k变成无限，这是我们想要的。也可以将它重写为一个大的二次规划问题，并用双坐标下降法来解决这个问题。这里就不再详细讨论。

需要解决的最后一个问题是LIPO在局部最大化方面的收敛问题。所以，虽然LIPO擅长达到f(x)的最高峰值，但一旦到达，它不会非常快地向最优位置（即峰顶）进展。这是许多衍生优化算法都有的问题，包括MATLAB的贝叶斯优化工具。幸运的是，并不是所有的方法都受到这个限制。尤其是，Michael J.D.Powell撰写了一系列有关如何将经典置信域方法应用于无梯度优化的论文。这些方法在目前所见的最佳点附近拟合一个二次曲面，然后在当前最佳点的某个距离内进行下一次迭代，成为该二次曲面的最大值。所以我们“信任”这个局部二次模型在最佳点附近的一个小区域内是准确的，因此被称为“置信域”。上面提到的BOBYQA方法是其中之一，它对最接近的局部最优收敛性非常好，很容易只需很少的步骤找到局部最优值。

我们可以结合这两种方法来解决LIPO的收敛问题，LIPO将探索 f(x)并快速找到最大峰值点。然后一个Powell 置信域方法可以有效地找到该峰值的确切最大化值。把这两者结合起来最简单的方法是在它们之间交替，这就是dlib所做的。在偶数次迭代中，我们根据upper bound选取下一个x，而在奇数次迭代中，我们根据置信域模型选择下一个x。我还用了一个略微不同的LIPO版本，叫做MaxLIPO。回想一下，Malherbe等人建议选择一个upper bound大于当前最佳目标值的点。不过，我发现在每次迭代中选择最大 upper bound点更好。这个替代版本MaxLIPO就是dlib使用的。

红线是要优化的函数，我们要找的是最大值点。每次算法从函数中抽取一个点时，我们就会用一个小框来记录。求解器的状态由全局上界U(x)和置信域方法所使用的局部二次模型决定。因此，我们绘制了upper bounding 模型以及当前的局部二次模型，这样你就可以看到随着优化的进行，它们是如何演进的。我们还用一条垂直线标注了到目前为止所看到的最佳点的位置。

将MaxLIPO和Powell置信区间综合方法（MaxLIPO+TR，红色）与MATLAB贝叶斯优化工具的默认设置（蓝色）相比较，贝叶斯优化在±10的-3次方精度趋于停滞，而混合方法很快就降到了±10的-17次方浮点精度。

MaxLIPO+TR与其他方法的比较，在所有测试中，都取得了最优结果，而且不需要任何参数，使用起来非常方便。

原文还附有使用这个优化函数的Python代码，具体看这里：http://blog.dlib.net/2017/12/a-global-optimization-algorithm-worth.html

论文：Global optimization of Lipschitz functions https://arxiv.org/abs/1703.02628