贝叶斯优化/Bayesian Optimization

BO算法理解起来其实非常简单。比如我们要优化的function是  ，其中的domain  一般是compact的，也有一些paper为了简便会assume  是discrete的。然后假设我们要解决的优化问题是  。

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

这时候长得好看的同学可能看出来了，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）。

关于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有以下几种：

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

EI [2] 的假设是没有observation noise，也就是我们每一个iteration都可以直接观察到 ，而不是  。首先定义  ，也就是  是前  个iterations里面我们观察到的最大值。然后EI策略定义为

其中  和  分别是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应用非常广泛，而且据说好多时候效果拔群。

Entropy Search（ES）和Predictive Entropy Search（PES）是两个基于信息论（information theory）的策略。在这两个框架下，我们试图通过观测一个输入点  来增加我们关于  的分布（  ）的信息，或者说来减少我们对于  这个分布的uncertainty。众所周知，在信息论里面，测量一个分布的uncertainty用的是entropy；也就是说一个分布的entropy越大，我们对于这个分布的uncertainty越大。Entropy search（ES）测量的就是通过观测  造成的expected reduction in entropy of  ：

上面式子中第一项是根据当前已有的观测结果  计算出来的关于  的分布的entropy；第二项的expectation里面那一项是我们在已经观测的结果  基础上再加上  的话（更新GP posterior之后）得到的关于  的entropy；这个expectation是对于  所对应的noisy observation  的posterior distribution的： 的。所以，这两项相减的话我们得到的就是通过观测  我们可以减少多少（in expectation）关于  分布的entropy。

PES和ES的数值是相等的，因为只是做了一个变换。这样做的好处是PES的acquisition function计算起来更简便一下。不过其实大家可能可以感受到，ES和PES都不好计算，所以中间需要好多approximation，比如需要对domain进行discretization，需要通过Monte Carlo sampling来approximate  的分布等等。

除了上面提到的GP-UCB，TS是另外一个从multi-armed bandit领域搬过来的算法。算法相当简单，第一步先从当前的GP posterior里面sample得到一个function（大家回忆一下，GP是一个distribution over functions，所以每一次sample得到的是一个function），不妨表示为  ，然后我们要观测的点就是：

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

参考文献