Chinaunix首页 | 论坛 | 博客

分类: 高性能计算

2018-01-04 14:52:07

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

  • 猜测和检查:听从你的直觉,选择感觉不错的数字,看看它们是否工作。一直持续这样做,直到厌倦。
  • 网格搜索:让计算机尝试在一定范围内均匀分布的一组值。
  • 随机搜索:让计算机随机挑选一组值。
  • 贝叶斯优化:使用像MATLAB的bayesopt之类的工具来自动选择最佳参数,然后你会发现贝叶斯优化比你的机器学习算法有更多的超参数,你变得沮丧,然后回头使用猜测和检查或网格搜索。
  • 在有一个良好的初始猜测的前提下进行局部优化:这就是MITIE的方法,它使用BOBYQA算法,并有一个精心选择的起始点。由于BOBYQA只寻找最近的局部最优解,所以这个方法是否成功很大程度上取决于是否有一个好的起点。在MITIE的情况下,我们知道一个好的起点,但这不是一个普遍的解决方案,因为通常你不会知道好的起点在哪里。从好的方面来说,这种方法非常适合寻找局部最优解。稍后我会再讨论这一点。

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

所以当我读到Cédric Malherbe和Nicolas Vayatis在去年的机器学习国际会议上发表的Global optimization of Lipschitz functions这篇论文时,我非常兴奋。在这篇论文中,他们提出了一个非常简单的无参数、而且经证明有效的方法来寻找使函数f(x)最大化的640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=,即使 f(x)有多个局部极大值。论文中的关键思想是保持f(x)的分段线性上界,并用它来决定在每个优化步骤中用于评估的x。因此,如果你已经评估了点x?,x?,...,xt,那么您可以在 f(x)上定义一个简单的上界,如下所示:

be386a0feee5a8547909e3d2658827583757e929

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

16b059dc7d67797febd6b9c3b5a46ee204dbbb51

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

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

c6e484cf1872d08702e793700f95d14f8e898a91

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

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

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

a82a39ddfd666fd97b083ad97c904417ec63955c

现在,来自 f(x) 的每个sample 都有自己的噪声项640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=,大部分时间它的值应该是0,除非640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=非常接近于不连续性或者存在一些随机性。在这里,K是一个对角线矩阵,包含“每个超参数一个Lipschitz k项”。通过这个公式,将每个σ设为0,640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=给出与Malherbe等人所提出的相同的U(x),但是如果采取更一般的值,可以处理上面提到的问题。

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

149eecc3ee84a33fbae6e80f25884cd05cd6f4d7

σ?上的640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=的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使用的。你可以在下面的视频中看到MaxLIPO和置信域方法混合使用的情况:

acafb5a089718e3a452b21c3a94894ff9a4ef5b3

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

8ea1f8da2b8b63a724784907be99af68e139807d

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

4d0df35c1d7f433046ee3c83bfadfeb05d34744a

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

阅读原文

http://click.aliyun.com/m/38771/

阅读(177) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册