世界上最好的算法:贝叶斯优化(数学和intuition角度)

2019年8月9日10:40:22 发表评论 538 views

世界上最好的算法:贝叶斯优化。这篇文章将尽量从数学和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是 [公式] ,其中的domain [公式] 一般是compact的,也有一些paper为了简便会assume [公式] 是discrete的。然后假设我们要解决的优化问题是 世界上最好的算法:贝叶斯优化(数学和intuition角度)

BO是一个sequential decision-making problem,也就是我们有好多iterations。在每一个iteration [公式] ,我们选一个输入 [公式] (比如我们选一组神经网络的超参),然后我们用选择的 [公式] 来看对应的function [公式] 的值 [公式] (比如这一组超参对应的神经网络的validation accuracy);可是大多数情况下我们都只能观测到一个有噪声的值,也就是我们观测到的是 [公式],其中 [公式] 是一个zero-mean Gaussian distribution: [公式][公式] 是noise variance。然后呢,我们把新观测到的这组值 [公式] 加到我们所有的观测到的数据里面,然后进行下一个iteration 世界上最好的算法:贝叶斯优化(数学和intuition角度)

这时候长得好看的同学可能看出来了,BO问题的核心是在每一个iteration里面如何选择我要观测哪一个 [公式] 。在BO里面 [公式] 是通过优化另一个function来选择的:acquisition function [公式] ;也就是 [公式] 。长得好看的同学可能又发现了,我们这是把一个优化问题替换成了好多个优化问题,所以这个acquisition function必须是优化起来非常非常容易才行。另外在设计这个acquisition function的时候最重要的一点是他要做好一个balance,这就引出了传说中的exploration-exploitation trade-off:在选下一个点 [公式] 的时候,我们既想要去尝试那些我们之前没有尝试过的区域的点(exploration),又想要去选择根据我们目前已经观测到的所有点预测的 [公式] 的值比较大的点(exploitation)。为了能很好地balance这两点,对于domain里面任意一个点 [公式] ,我们既需要预测对应的 [公式] 的值(为了exploitation),又需要知道对应的 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的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 [公式] 就可以通过 [公式]世界上最好的算法:贝叶斯优化(数学和intuition角度) 计算出来了。目前常用的acquisition function有以下几种:

Gaussian Process-Upper Confidence Bound (GP-UCB):

世界上最好的算法:贝叶斯优化(数学和intuition角度)

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

Expected Improvement (EI):

EI [2] 的假设是没有observation noise,也就是我们每一个iteration都可以直接观察到 [公式] ,而不是 [公式] 。首先定义 [公式] ,也就是 [公式] 是前 世界上最好的算法:贝叶斯优化(数学和intuition角度) 个iterations里面我们观察到的最大值。然后EI策略定义为

世界上最好的算法:贝叶斯优化(数学和intuition角度)

其中 [公式][公式] 分别是standard Gaussian distribution的cumulative distribution function(CDF)和probability density function(PDF)。注意第一行里面的expectation是对于 [公式] 的posterior distribution的,这个在之前讲GP的时候有提到,他的distribution是一个一维高斯分布:[公式] 。第二个等号可以直接推出来,大家吃的太饱的时候可以自己试一下。Expectation里面的 [公式] 可以简单的理解为 [公式] 对应的function的值 世界上最好的算法:贝叶斯优化(数学和intuition角度) 比当前观测到的最大值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 世界上最好的算法:贝叶斯优化(数学和intuition角度)

世界上最好的算法:贝叶斯优化(数学和intuition角度)

上面式子中第一项是根据当前已有的观测结果 [公式] 计算出来的关于 [公式] 的分布的entropy;第二项的expectation里面那一项是我们在已经观测的结果 [公式] 基础上再加上 [公式] 的话(更新GP posterior之后)得到的关于 [公式] 的entropy;这个expectation是对于 [公式] 所对应的noisy observation [公式] 的posterior distribution的:[公式] 的。所以,这两项相减的话我们得到的就是通过观测 [公式] 我们可以减少多少(in expectation)关于 世界上最好的算法:贝叶斯优化(数学和intuition角度) 分布的entropy。

Predictive Entropy Search(PES)则是在ES基础上利用conditional information gain的symmetric的性质做了一个机智的变换:

世界上最好的算法:贝叶斯优化(数学和intuition角度)

PES和ES的数值是相等的,因为只是做了一个变换。这样做的好处是PES的acquisition function计算起来更简便一下。不过其实大家可能可以感受到,ES和PES都不好计算,所以中间需要好多approximation,比如需要对domain进行discretization,需要通过Monte Carlo sampling来approximate 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的分布等等。

Thompson Sampling(TS):

除了上面提到的GP-UCB,TS是另外一个从multi-armed bandit领域搬过来的算法。算法相当简单,第一步先从当前的GP posterior里面sample得到一个function(大家回忆一下,GP是一个distribution over functions,所以每一次sample得到的是一个function),不妨表示为 世界上最好的算法:贝叶斯优化(数学和intuition角度) ,然后我们要观测的点就是:

世界上最好的算法:贝叶斯优化(数学和intuition角度)

从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的基础上,把 [公式] 的分布换成 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的分布。

贝叶斯优化的理论

鲁迅先生曾经说过:一个没有regret bound的BO算法是没有灵魂的。所以接下来才是重头戏:BO的理论。

贝叶斯优化的研究前沿

结论

参考文献

[1] Srinivas, N., et. al. Gaussian process optimization in the bandit setting: No regret and experimental design. ICML 2010.

[2] Jones, D., et. al., Efficient global optimization of expensive black-box functions. J. Global Optimization, 1998.

作者:Dai Zhongxiang 来源:知乎

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: