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

2019-08-0910:40:22数据结构与算法Comments14,947 views1字数 4649阅读模式

世界上最好的算法:贝叶斯优化。这篇文章将尽量从数学和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是 世界上最好的算法:贝叶斯优化(数学和intuition角度) ,其中的domain 世界上最好的算法:贝叶斯优化(数学和intuition角度) 一般是compact的,也有一些paper为了简便会assume 世界上最好的算法:贝叶斯优化(数学和intuition角度) 是discrete的。然后假设我们要解决的优化问题是 世界上最好的算法:贝叶斯优化(数学和intuition角度)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

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

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

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

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

世界上最好的算法:贝叶斯优化(数学和intuition角度)文章源自菜鸟学院-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的理论的时候会再提到。公式里面 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的值是根据理论分析推出来的,随时间递增;可是在实际应用里面,好多人为了简便直接把 世界上最好的算法:贝叶斯优化(数学和intuition角度) 设成一个常数,也是可以的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

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

EI [2] 的假设是没有observation noise,也就是我们每一个iteration都可以直接观察到 世界上最好的算法:贝叶斯优化(数学和intuition角度) ,而不是 世界上最好的算法:贝叶斯优化(数学和intuition角度) 。首先定义 世界上最好的算法:贝叶斯优化(数学和intuition角度) ,也就是 世界上最好的算法:贝叶斯优化(数学和intuition角度) 是前 世界上最好的算法:贝叶斯优化(数学和intuition角度) 个iterations里面我们观察到的最大值。然后EI策略定义为文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

世界上最好的算法:贝叶斯优化(数学和intuition角度)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

其中 世界上最好的算法:贝叶斯优化(数学和intuition角度)世界上最好的算法:贝叶斯优化(数学和intuition角度) 分别是standard Gaussian distribution的cumulative distribution function(CDF)和probability density function(PDF)。注意第一行里面的expectation是对于 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的posterior distribution的,这个在之前讲GP的时候有提到,他的distribution是一个一维高斯分布:世界上最好的算法:贝叶斯优化(数学和intuition角度) 。第二个等号可以直接推出来,大家吃的太饱的时候可以自己试一下。Expectation里面的 世界上最好的算法:贝叶斯优化(数学和intuition角度) 可以简单的理解为 世界上最好的算法:贝叶斯优化(数学和intuition角度) 对应的function的值 世界上最好的算法:贝叶斯优化(数学和intuition角度) 比当前观测到的最大值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)的策略。在这两个框架下,我们试图通过观测一个输入点 世界上最好的算法:贝叶斯优化(数学和intuition角度) 来增加我们关于 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的分布( 世界上最好的算法:贝叶斯优化(数学和intuition角度) )的信息,或者说来减少我们对于 世界上最好的算法:贝叶斯优化(数学和intuition角度) 这个分布的uncertainty。众所周知,在信息论里面,测量一个分布的uncertainty用的是entropy;也就是说一个分布的entropy越大,我们对于这个分布的uncertainty越大。Entropy search(ES)测量的就是通过观测 世界上最好的算法:贝叶斯优化(数学和intuition角度) 造成的expected reduction in entropy of 世界上最好的算法:贝叶斯优化(数学和intuition角度)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

世界上最好的算法:贝叶斯优化(数学和intuition角度)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

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

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

世界上最好的算法:贝叶斯优化(数学和intuition角度)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

PES和ES的数值是相等的,因为只是做了一个变换。这样做的好处是PES的acquisition function计算起来更简便一下。不过其实大家可能可以感受到,ES和PES都不好计算,所以中间需要好多approximation,比如需要对domain进行discretization,需要通过Monte Carlo sampling来approximate 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的分布等等。文章源自菜鸟学院-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),不妨表示为 世界上最好的算法:贝叶斯优化(数学和intuition角度) ,然后我们要观测的点就是:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html

世界上最好的算法:贝叶斯优化(数学和intuition角度)文章源自菜鸟学院-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的基础上,把 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的分布换成 世界上最好的算法:贝叶斯优化(数学和intuition角度) 的分布。

贝叶斯优化的理论

鲁迅先生曾经说过:一个没有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

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15126.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/15126.html

Comment

匿名网友 填写信息

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

确定