贝叶斯优化/Bayesian Optimization
最近心情不好，写篇文章让大家开心一下吧。介绍一下世界上最好的算法：贝叶斯优化。这篇文章将尽量从数学和intuition两个角度都介绍一下作者对于贝叶斯优化的深（粗）刻（浅）理解。背景介绍
近年来深度神经网络大火，可是神经网络的超参（hyperparameters）选择一直是一个问题，因为大部分时候大家都是按照玄学指导手动调参，各位调参的同学也跟奇异博士一样算是master of mystic arts了。由于这个原因，贝叶斯优化（Bayesian Optimization，以下简称BO）开始被好多人用来调神经网络的超参，在这方面BO最大的优势是sample efficiency，也就是BO可以用非常少的步数（每一步可以想成用一组超参数来训练你的神经网络）就能找到比较好的超参数组合。另一个原因是BO不需要求导数（gradient），而正好一般情况下神经网络超参的导数是求不出来的。这两个原因导致BO成为了如今世界上最好的调超参的方法（当然了我可能有粉丝滤镜）。
其实BO不是只能用来调超参的，因为他是一个非常general的gradient-free global optimization的方法，所以他的适用场景一般有两个特点：（1）需要优化的function计算起来非常费时费力，比如上面提到的神经网络的超参问题，每一次训练神经网络都是燃烧好多GPU的；（2）你要优化的function没有导数信息。所以如果你遇到的问题有以上两个特点的话直接闭着眼睛用BO就行了。当然了这么说还是有点太暴力了，因为有一些特殊的问题结构也会影响BO的效果，比如需要调的参数太多的话（对应high-dimensional BO的问题），或者参数里面有太多discrete parameter的话BO的效果都会受影响，当然了这两种场景也是BO目前的open problems之二。
贝叶斯优化算法
BO算法理解起来其实非常简单。比如我们要优化的function是 https://www.zhihu.com/equation?tex=f%3A%5Cmathcal%7BX%7D%5Crightarrow+%5Cmathbb%7BR%7D ，其中的domain一般是compact的，也有一些paper为了简便会assume是discrete的。然后假设我们要解决的优化问题是 https://www.zhihu.com/equation?tex=x%5E%2A%3D%5Carg%5Cmax_%7Bx+%5Cin%5Cmathcal%7BX%7D%7D+f%28+x+%29 。
BO是一个sequential decision-making problem，也就是我们有好多iterations。在每一个iteration https://www.zhihu.com/equation?tex=t%3D1%2C%5Cldots%2CT ，我们选一个输入 https://www.zhihu.com/equation?tex=x_t+%5Cin+%5Cmathcal%7BX%7D （比如我们选一组神经网络的超参），然后我们用选择的来看对应的function的值（比如这一组超参对应的神经网络的validation accuracy）；可是大多数情况下我们都只能观测到一个有噪声的值，也就是我们观测到的是 https://www.zhihu.com/equation?tex=y_t+%3D+f%28x_t%29+%2B+%5Cepsilon，其中 https://www.zhihu.com/equation?tex=%5Cepsilon 是一个zero-mean Gaussian distribution： https://www.zhihu.com/equation?tex=%5Cepsilon+%5Csim+%5Cmathcal%7BN%7D%280%2C%5Csigma+%5E+2%29 ， https://www.zhihu.com/equation?tex=%5Csigma 是noise variance。然后呢，我们把新观测到的这组值 https://www.zhihu.com/equation?tex=%28x_t%2Cy_t%29 加到我们所有的观测到的数据里面，然后进行下一个iteration https://www.zhihu.com/equation?tex=t%2B1 。
这时候长得好看的同学可能看出来了，BO问题的核心是在每一个iteration里面如何选择我要观测哪一个。在BO里面是通过优化另一个function来选择的：acquisition function；也就是 https://www.zhihu.com/equation?tex=x_t%3D%5Carg%5Cmax_%7Bx%5Cin+%5Cmathcal%7BX%7D%7D+%5Calpha_t%28x%29 。长得好看的同学可能又发现了，我们这是把一个优化问题替换成了好多个优化问题，所以这个acquisition function必须是优化起来非常非常容易才行。另外在设计这个acquisition function的时候最重要的一点是他要做好一个balance，这就引出了传说中的exploration-exploitation trade-off：在选下一个点的时候，我们既想要去尝试那些我们之前没有尝试过的区域的点（exploration），又想要去选择根据我们目前已经观测到的所有点预测的的值比较大的点（exploitation）。为了能很好地balance这两点，对于domain里面任意一个点，我们既需要预测对应的的值（为了exploitation），又需要知道对应的的uncertainty（为了exploration）。这时候最合适的模型已经呼之欲出了：Gaussian Process（GP）。
关于GP在这里就不详细介绍了，知乎上有不少好文章大家可以去复习一下。在这里大家需要知道的是，假设现在我们已经跑完了个BO的iteration，也就是我们现在手里的数据是 https://www.zhihu.com/equation?tex=%5Cmathcal%7BD%7D_%7Bt-1%7D%3D%5C%7B%28x_1%2Cy_1%29%2C%28x_2%2Cy_2%29%2C%5Cldots%2C%28x_%7Bt-1%7D%2Cy_%7Bt-1%7D%29%5C%7D ，那么我们根据GP的预测，整个domain里面任意一点对应的的值服从一维高斯分布，而且对应的posterior mean和posterior variance可以写成closed-form。GP的公式在这里就不重复了，我们就把对应的mean和variance表示成和，他们两个可以分别理解为用来做exploitation和exploration的信息。这个应该不难理解，因为预测的posterior mean就相当于我们预测的的值，然后posterior variance就相当于我们对于的uncertainty。现在呢，上面提到的acquisition function就可以通过和计算出来了。目前常用的acquisition function有以下几种：
Gaussian Process-Upper Confidence Bound (GP-UCB):
https://www.zhihu.com/equation?tex=x_%7Bt%7D+%3D%5Carg%5Cmax_%7Bx%5Cin+%5Cmathcal%7BX%7D%7D%5Calpha_t%28x%29%3D%5Carg%5Cmax_%7Bx%5Cin+%5Cmathcal%7BX%7D%7D%5Cmu_%7Bt-1%7D%28x%29%2B%5Cbeta_%7Bt%7D%5E%7B1%2F2%7D%5Csigma_%7Bt-1%7D%28x%29
这个形式可以说非常简单了，就是posterior mean和posterior standard deviation的加权和；同时也很好理解，加权和里面的两项可以分别理解为对应exploitation和exploration。GP-UCB 是基于multi-armed bandit里面的upper confidence bound （UCB）算法提出的，所以一个很大的好处是他的理论很完美，这个在下面讲BO的理论的时候会再提到。公式里面 https://www.zhihu.com/equation?tex=%5Cbeta_t 的值是根据理论分析推出来的，随时间递增；可是在实际应用里面，好多人为了简便直接把 https://www.zhihu.com/equation?tex=%5Cbeta_t+ 设成一个常数，也是可以的。
Expected Improvement (EI):
EI 的假设是没有observation noise，也就是我们每一个iteration都可以直接观察到，而不是 https://www.zhihu.com/equation?tex=y_t 。首先定义 https://www.zhihu.com/equation?tex=f_%7Bt-1%7D%5E%2B%3D%5Cmax_%7Bt%27%3D1%2C%5Cldots%2Ct-1%7Df%28x_%7Bt%27%7D%29 ，也就是 https://www.zhihu.com/equation?tex=f_%7Bt-1%7D%5E%2B 是前个iterations里面我们观察到的最大值。然后EI策略定义为
https://www.zhihu.com/equation?tex=x_t%3D%5Carg%5Cmax_%7Bx%5Cin+%5Cmathcal%7BX%7D%7D%5Cmathbb%7BE%7D_%7Bf%28x%29%5Csim+%5Cmathcal%7BN%7D%28%5Cmu_%7Bt-1%7D%28x%29%2C%5Csigma_%7Bt-1%7D%5E2%28x%29%29%7D%5B%5Cmax%28f%28x%29-f_%7Bt-1%7D%5E%2B%2C+0%29%5D%5C%5C+%3D%5Carg%5Cmax_%7Bx%5Cin+%5Cmathcal%7BX%7D%7D%28%5Cmu_%7Bt-1%7D%28x%29-f_%7Bt-1%7D%5E%2B%29%5CPhi%28%5Cfrac%7B%5Cmu_%7Bt-1%7D%28x%29-f_%7Bt-1%7D%5E%2B%7D%7B%5Csigma_%7Bt-1%7D%28x%29%7D%29%2B%5Csigma_%7Bt-1%7D%28x%29%5Cphi%28%5Cfrac%7B%5Cmu_%7Bt-1%7D%28x%29-f_%7Bt-1%7D%5E%2B%7D%7B%5Csigma_%7Bt-1%7D%28x%29%7D%29
其中 https://www.zhihu.com/equation?tex=%5CPhi 和 https://www.zhihu.com/equation?tex=%5Cphi 分别是standard Gaussian distribution的cumulative distribution function（CDF）和probability density function（PDF）。注意第一行里面的expectation是对于的posterior distribution的，这个在之前讲GP的时候有提到，他的distribution是一个一维高斯分布：https://www.zhihu.com/equation?tex=f%28x%29%5Csim+%5Cmathcal%7BN%7D%28%5Cmu_%7Bt-1%7D%28x%29%2C%5Csigma%5E2_%7Bt-1%7D%28x%29%29 。第二个等号可以直接推出来，大家吃的太饱的时候可以自己试一下。Expectation里面的 https://www.zhihu.com/equation?tex=%5Cmax%28f%28x%29-f_%7Bt-1%7D%5E%2B%2C+0%29 可以简单的理解为对应的function的值比当前观测到的最大值improve多少，所以叫做improvement function，然后EI的名字就是这么来的。还有注意一下之前提到的没有observation noise只是一个假设，实际用的时候直接插入目前位置观察到的最大值就可以。EI应用非常广泛，而且据说好多时候效果拔群。
(Predictive) Entropy Search:
Entropy Search（ES）和Predictive Entropy Search（PES）是两个基于信息论（information theory）的策略。在这两个框架下，我们试图通过观测一个输入点来增加我们关于的分布（）的信息，或者说来减少我们对于这个分布的uncertainty。众所周知，在信息论里面，测量一个分布的uncertainty用的是entropy；也就是说一个分布的entropy越大，我们对于这个分布的uncertainty越大。Entropy search（ES）测量的就是通过观测造成的expected reduction in entropy of：
https://www.zhihu.com/equation?tex=x_t+%3D+%5Carg%5Cmax_%7Bx%5Cin+%5Cmathcal%7BX%7D%7DH%28%5Cmathbb%7BP%7D%28x%5E%2A%7C%5Cmathcal%7BD%7D_%7Bt-1%7D%29%29-%5Cmathbb%7BE%7D_%7By%7C%5Cmathcal%7BD%7D_%7Bt-1%7D%2Cx%7D%5Cleft%5BH%28%5Cmathbb%7BP%28x%5E%2A%7C%5Cmathcal%7BD%7D_%7Bt-1%7D%5Ccup%28x%2Cy%29%29%7D%29%5Cright%5D
上面式子中第一项是根据当前已有的观测结果计算出来的关于的分布的entropy；第二项的expectation里面那一项是我们在已经观测的结果基础上再加上 https://www.zhihu.com/equation?tex=%28x%2Cy%29 的话（更新GP posterior之后）得到的关于的entropy；这个expectation是对于所对应的noisy observation https://www.zhihu.com/equation?tex=y 的posterior distribution的：https://www.zhihu.com/equation?tex=y%3Df%28x%29%2B%5Cepsilon+%5Csim+%5Cmathcal%7BN%7D%28%5Cmu_%7Bt-1%7D%28x%29%2C%5Csigma%5E2_%7Bt-1%7D%28x%29%2B%5Csigma%5E2%29 的。所以，这两项相减的话我们得到的就是通过观测我们可以减少多少（in expectation）关于分布的entropy。
Predictive Entropy Search（PES）则是在ES基础上利用conditional information gain的symmetric的性质做了一个机智的变换：
https://www.zhihu.com/equation?tex=x_t%3D%5Carg%5Cmax_%7Bx%5Cin+%5Cmathcal%7BX%7D%7DH%28%5Cmathbb%7BP%7D%28y%7C%5Cmathcal%7BD%7D_%7Bt-1%7D%2Cx%29%29-%5Cmathbb%7BE%7D_%7Bx%5E%2A%7C%5Cmathcal%7BD%7D_%7Bt-1%7D%7D%5Cleft%5BH%28%5Cmathbb%7BP%7D%28y%7C%5Cmathcal%7BD%7D_%7Bt-1%7D%2Cx%2Cx%5E%2A%29%29%5Cright%5D
PES和ES的数值是相等的，因为只是做了一个变换。这样做的好处是PES的acquisition function计算起来更简便一下。不过其实大家可能可以感受到，ES和PES都不好计算，所以中间需要好多approximation，比如需要对domain进行discretization，需要通过Monte Carlo sampling来approximate的分布等等。
Thompson Sampling（TS）：
除了上面提到的GP-UCB，TS是另外一个从multi-armed bandit领域搬过来的算法。算法相当简单，第一步先从当前的GP posterior里面sample得到一个function（大家回忆一下，GP是一个distribution over functions，所以每一次sample得到的是一个function），不妨表示为 https://www.zhihu.com/equation?tex=%5Chat%7Bf%7D_t ，然后我们要观测的点就是：
https://www.zhihu.com/equation?tex=x_t%3D%5Carg%5Cmax_%7Bx%5Cin+%5Cmathcal%7BX%7D%7D%5Chat%7Bf%7D_t%28x%29
从GP里面draw sample这个问题已经有不少研究了，所以TS算法不只看起来简单，用起来也很简单。可是不知道为什么TS在BO里面应用不是很多，个人猜测是因为很难找到合适的应用场景，因为大多数可以用TS的场景里面用GP-UCB也可以，而且TS的理论分析是基于GP-UCB的分析的extension，所以很难找到可以用TS而不可以用GP-UCB的场景。
其他acquisition function
除了以上几个之外，还有几个用的稍微少一点的acquisition function，比如
[*]probability of improvement （PI）：这个应该算是一个比较经典的算法了，可是感觉现在很少用了。
[*]knowledge gradient（KG）：这个算是来自Operations Research（OR）大佬Peter Frazier的跨领域打击，因为KG策略是Frazier大佬在OR领域的成名作，近些年大佬有好多把KG用在BO的工作。
[*]Max-Value Entropy Search：这个是在PES的基础上，把的分布换成 https://www.zhihu.com/equation?tex=y%5E%2A 的分布。
贝叶斯优化的理论
鲁迅先生曾经说过：一个没有regret bound的BO算法是没有灵魂的。所以接下来才是重头戏：BO的理论。
贝叶斯优化的研究前沿
结论
参考文献
Srinivas, N., et. al. Gaussian process optimization in the bandit setting: No regret and experimental design. ICML 2010.
Jones, D., et. al., Efficient global optimization of expensive black-box functions. J. Global Optimization, 1998. 期待后续哦！ 蹲( 大神我最近在看你今年icml那篇论文 感觉现在贝叶斯优化也不general了，动不动就假设additive form或者low dim manifold[捂脸] 不是大神不是大神。。。github上那个issue就是你提的吧哈哈，我先去把那个坑填上。。。 有读过大佬最近的那篇Binary Auxiliary Information
[干杯] 哈哈那篇基本都是我们师姐做的，我只是帮忙做了一点实验。。。 这是因为high-dimensional的问题太难搞了。。。不用这些simplifying assumptions几乎什么都做不了。。。 哈哈哈，被认出来了，我看你github不经常用，结果今天在知乎上碰到真的有缘