世界上最好的算法：贝叶斯优化（数学和intuition角度）

世界上最好的算法：贝叶斯优化。这篇文章将尽量从数学和intuition两个角度都介绍一下作者对于贝叶斯优化的深（粗）刻（浅）理解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

背景介绍

近年来深度神经网络大火，可是神经网络的超参（hyperparameters）选择一直是一个问题，因为大部分时候大家都是按照玄学指导手动调参，各位调参的同学也跟奇异博士一样算是master of mystic arts了。由于这个原因，贝叶斯优化（Bayesian Optimization，以下简称BO）开始被好多人用来调神经网络的超参，在这方面BO最大的优势是sample efficiency，也就是BO可以用非常少的步数（每一步可以想成用一组超参数来训练你的神经网络）就能找到比较好的超参数组合。另一个原因是BO不需要求导数（gradient），而正好一般情况下神经网络超参的导数是求不出来的。这两个原因导致BO成为了如今世界上最好的调超参的方法（当然了我可能有粉丝滤镜）。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

其实BO不是只能用来调超参的，因为他是一个非常general的gradient-free global optimization的方法，所以他的适用场景一般有两个特点：（1）需要优化的function计算起来非常费时费力，比如上面提到的神经网络的超参问题，每一次训练神经网络都是燃烧好多GPU的；（2）你要优化的function没有导数信息。所以如果你遇到的问题有以上两个特点的话直接闭着眼睛用BO就行了。当然了这么说还是有点太暴力了，因为有一些特殊的问题结构也会影响BO的效果，比如需要调的参数太多的话（对应high-dimensional BO的问题），或者参数里面有太多discrete parameter的话BO的效果都会受影响，当然了这两种场景也是BO目前的open problems之二。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

贝叶斯优化算法

BO算法理解起来其实非常简单。比如我们要优化的function是 ，其中的domain 一般是compact的，也有一些paper为了简便会assume 是discrete的。然后假设我们要解决的优化问题是 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

BO是一个sequential decision-making problem，也就是我们有好多iterations。在每一个iteration ，我们选一个输入 （比如我们选一组神经网络的超参），然后我们用选择的 来看对应的function 的值 （比如这一组超参对应的神经网络的validation accuracy）；可是大多数情况下我们都只能观测到一个有噪声的值，也就是我们观测到的是 ，其中 是一个zero-mean Gaussian distribution： ， 是noise variance。然后呢，我们把新观测到的这组值 加到我们所有的观测到的数据里面，然后进行下一个iteration 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

这时候长得好看的同学可能看出来了，BO问题的核心是在每一个iteration里面如何选择我要观测哪一个 。在BO里面 是通过优化另一个function来选择的：acquisition function ；也就是 。长得好看的同学可能又发现了，我们这是把一个优化问题替换成了好多个优化问题，所以这个acquisition function必须是优化起来非常非常容易才行。另外在设计这个acquisition function的时候最重要的一点是他要做好一个balance，这就引出了传说中的exploration-exploitation trade-off：在选下一个点 的时候，我们既想要去尝试那些我们之前没有尝试过的区域的点（exploration），又想要去选择根据我们目前已经观测到的所有点预测的 的值比较大的点（exploitation）。为了能很好地balance这两点，对于domain里面任意一个点 ，我们既需要预测对应的 的值（为了exploitation），又需要知道对应的 的uncertainty（为了exploration）。这时候最合适的模型已经呼之欲出了：Gaussian Process（GP）。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

关于GP在这里就不详细介绍了，知乎上有不少好文章大家可以去复习一下。在这里大家需要知道的是，假设现在我们已经跑完了 个BO的iteration，也就是我们现在手里的数据是 ，那么我们根据GP的预测，整个domain里面任意一点 对应的 的值服从一维高斯分布，而且对应的posterior mean和posterior variance可以写成closed-form。GP的公式在这里就不重复了，我们就把对应的mean和variance表示成 和 ，他们两个可以分别理解为用来做exploitation和exploration的信息。这个应该不难理解，因为预测的posterior mean就相当于我们预测的 的值，然后posterior variance就相当于我们对于 的uncertainty。现在呢，上面提到的acquisition function 就可以通过 和 计算出来了。目前常用的acquisition function有以下几种：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

Gaussian Process-Upper Confidence Bound (GP-UCB):文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

这个形式可以说非常简单了，就是posterior mean和posterior standard deviation的加权和；同时也很好理解，加权和里面的两项可以分别理解为对应exploitation和exploration。GP-UCB [1] 是基于multi-armed bandit里面的upper confidence bound （UCB）算法提出的，所以一个很大的好处是他的理论很完美，这个在下面讲BO的理论的时候会再提到。公式里面 的值是根据理论分析推出来的，随时间递增；可是在实际应用里面，好多人为了简便直接把 设成一个常数，也是可以的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

Expected Improvement (EI):文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

EI [2] 的假设是没有observation noise，也就是我们每一个iteration都可以直接观察到 ，而不是 。首先定义 ，也就是 是前 个iterations里面我们观察到的最大值。然后EI策略定义为文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

其中 和 分别是standard Gaussian distribution的cumulative distribution function（CDF）和probability density function（PDF）。注意第一行里面的expectation是对于 的posterior distribution的，这个在之前讲GP的时候有提到，他的distribution是一个一维高斯分布： 。第二个等号可以直接推出来，大家吃的太饱的时候可以自己试一下。Expectation里面的 可以简单的理解为 对应的function的值 比当前观测到的最大值improve多少，所以叫做improvement function，然后EI的名字就是这么来的。还有注意一下之前提到的没有observation noise只是一个假设，实际用的时候直接插入目前位置观察到的最大值就可以。EI应用非常广泛，而且据说好多时候效果拔群。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

(Predictive) Entropy Search:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

Entropy Search（ES）和Predictive Entropy Search（PES）是两个基于信息论（information theory）的策略。在这两个框架下，我们试图通过观测一个输入点 来增加我们关于 的分布（ ）的信息，或者说来减少我们对于 这个分布的uncertainty。众所周知，在信息论里面，测量一个分布的uncertainty用的是entropy；也就是说一个分布的entropy越大，我们对于这个分布的uncertainty越大。Entropy search（ES）测量的就是通过观测 造成的expected reduction in entropy of ：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

上面式子中第一项是根据当前已有的观测结果 计算出来的关于 的分布的entropy；第二项的expectation里面那一项是我们在已经观测的结果 基础上再加上 的话（更新GP posterior之后）得到的关于 的entropy；这个expectation是对于 所对应的noisy observation 的posterior distribution的： 的。所以，这两项相减的话我们得到的就是通过观测 我们可以减少多少（in expectation）关于 分布的entropy。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

Predictive Entropy Search（PES）则是在ES基础上利用conditional information gain的symmetric的性质做了一个机智的变换：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

PES和ES的数值是相等的，因为只是做了一个变换。这样做的好处是PES的acquisition function计算起来更简便一下。不过其实大家可能可以感受到，ES和PES都不好计算，所以中间需要好多approximation，比如需要对domain进行discretization，需要通过Monte Carlo sampling来approximate 的分布等等。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

Thompson Sampling（TS）：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

除了上面提到的GP-UCB，TS是另外一个从multi-armed bandit领域搬过来的算法。算法相当简单，第一步先从当前的GP posterior里面sample得到一个function（大家回忆一下，GP是一个distribution over functions，所以每一次sample得到的是一个function），不妨表示为 ，然后我们要观测的点就是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

从GP里面draw sample这个问题已经有不少研究了，所以TS算法不只看起来简单，用起来也很简单。可是不知道为什么TS在BO里面应用不是很多，个人猜测是因为很难找到合适的应用场景，因为大多数可以用TS的场景里面用GP-UCB也可以，而且TS的理论分析是基于GP-UCB的分析的extension，所以很难找到可以用TS而不可以用GP-UCB的场景。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

其他acquisition function文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

除了以上几个之外，还有几个用的稍微少一点的acquisition function，比如文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

• probability of improvement （PI）：这个应该算是一个比较经典的算法了，可是感觉现在很少用了。
• knowledge gradient（KG）：这个算是来自Operations Research（OR）大佬Peter Frazier的跨领域打击，因为KG策略是Frazier大佬在OR领域的成名作，近些年大佬有好多把KG用在BO的工作。
• Max-Value Entropy Search：这个是在PES的基础上，把 的分布换成 的分布。

贝叶斯优化的理论

鲁迅先生曾经说过：一个没有regret bound的BO算法是没有灵魂的。所以接下来才是重头戏：BO的理论。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

贝叶斯优化的研究前沿

结论

参考文献

[1] Srinivas, N., et. al. Gaussian process optimization in the bandit setting: No regret and experimental design. ICML 2010.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

[2] Jones, D., et. al., Efficient global optimization of expensive black-box functions. J. Global Optimization, 1998.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

作者：Dai Zhongxiang 来源：知乎文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html