贝叶斯优化/Bayesian Optimization

DomDomm · 发表于 2022-1-4 09:54

最近心情不好，写篇文章让大家开心一下吧。介绍一下世界上最好的算法：贝叶斯优化。这篇文章将尽量从数学和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是 $f:\mathcal{X}\rightarrow \mathbb{R}$ ，其中的domain  一般是compact的，也有一些paper为了简便会assume  是discrete的。然后假设我们要解决的优化问题是 $x^*=\arg\max_{x \in\mathcal{X}} f( x )$ 。
BO是一个sequential decision-making problem，也就是我们有好多iterations。在每一个iteration $t=1,\ldots,T$ ，我们选一个输入 $x_t \in \mathcal{X}$ （比如我们选一组神经网络的超参），然后我们用选择的  来看对应的function  的值  （比如这一组超参对应的神经网络的validation accuracy）；可是大多数情况下我们都只能观测到一个有噪声的值，也就是我们观测到的是 $y_t = f(x_t) + \epsilon$ ，其中 $\epsilon$ 是一个zero-mean Gaussian distribution： $\epsilon \sim \mathcal{N}(0,\sigma ^ 2)$ ， $\sigma$ 是noise variance。然后呢，我们把新观测到的这组值 $(x_t,y_t)$ 加到我们所有的观测到的数据里面，然后进行下一个iteration $t+1$ 。
这时候长得好看的同学可能看出来了，BO问题的核心是在每一个iteration里面如何选择我要观测哪一个  。在BO里面  是通过优化另一个function来选择的：acquisition function  ；也就是 $x_t=\arg\max_{x\in \mathcal{X}} \alpha_t(x)$ 。长得好看的同学可能又发现了，我们这是把一个优化问题替换成了好多个优化问题，所以这个acquisition function必须是优化起来非常非常容易才行。另外在设计这个acquisition function的时候最重要的一点是他要做好一个balance，这就引出了传说中的exploration-exploitation trade-off：在选下一个点  的时候，我们既想要去尝试那些我们之前没有尝试过的区域的点（exploration），又想要去选择根据我们目前已经观测到的所有点预测的  的值比较大的点（exploitation）。为了能很好地balance这两点，对于domain里面任意一个点  ，我们既需要预测对应的  的值（为了exploitation），又需要知道对应的  的uncertainty（为了exploration）。这时候最合适的模型已经呼之欲出了：Gaussian Process（GP）。
关于GP在这里就不详细介绍了，知乎上有不少好文章大家可以去复习一下。在这里大家需要知道的是，假设现在我们已经跑完了  个BO的iteration，也就是我们现在手里的数据是 $\mathcal{D}_{t-1}=\{(x_1,y_1),(x_2,y_2),\ldots,(x_{t-1},y_{t-1})\}$ ，那么我们根据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):

$x_{t} =\arg\max_{x\in \mathcal{X}}\alpha_t(x)=\arg\max_{x\in \mathcal{X}}\mu_{t-1}(x)+\beta_{t}^{1/2}\sigma_{t-1}(x)$
这个形式可以说非常简单了，就是posterior mean和posterior standard deviation的加权和；同时也很好理解，加权和里面的两项可以分别理解为对应exploitation和exploration。GP-UCB [1] 是基于multi-armed bandit里面的upper confidence bound （UCB）算法提出的，所以一个很大的好处是他的理论很完美，这个在下面讲BO的理论的时候会再提到。公式里面 $\beta_t$ 的值是根据理论分析推出来的，随时间递增；可是在实际应用里面，好多人为了简便直接把 $\beta_t$ 设成一个常数，也是可以的。
Expected Improvement (EI):
EI [2] 的假设是没有observation noise，也就是我们每一个iteration都可以直接观察到  ，而不是 $y_t$ 。首先定义 $f_{t-1}^+=\max_{t'=1,\ldots,t-1}f(x_{t'})$ ，也就是 $f_{t-1}^+$ 是前  个iterations里面我们观察到的最大值。然后EI策略定义为

$x_t=\arg\max_{x\in \mathcal{X}}\mathbb{E}_{f(x)\sim \mathcal{N}(\mu_{t-1}(x),\sigma_{t-1}^2(x))}[\max(f(x)-f_{t-1}^+, 0)]\\ =\arg\max_{x\in \mathcal{X}}(\mu_{t-1}(x)-f_{t-1}^+)\Phi(\frac{\mu_{t-1}(x)-f_{t-1}^+}{\sigma_{t-1}(x)})+\sigma_{t-1}(x)\phi(\frac{\mu_{t-1}(x)-f_{t-1}^+}{\sigma_{t-1}(x)})$
其中 $\Phi$ 和 $\phi$ 分别是standard Gaussian distribution的cumulative distribution function（CDF）和probability density function（PDF）。注意第一行里面的expectation是对于  的posterior distribution的，这个在之前讲GP的时候有提到，他的distribution是一个一维高斯分布： $f(x)\sim \mathcal{N}(\mu_{t-1}(x),\sigma^2_{t-1}(x))$ 。第二个等号可以直接推出来，大家吃的太饱的时候可以自己试一下。Expectation里面的 $\max(f(x)-f_{t-1}^+, 0)$ 可以简单的理解为  对应的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  ：

$x_t = \arg\max_{x\in \mathcal{X}}H(\mathbb{P}(x^*|\mathcal{D}_{t-1}))-\mathbb{E}_{y|\mathcal{D}_{t-1},x}\left[H(\mathbb{P(x^*|\mathcal{D}_{t-1}\cup(x,y))})\right]$
上面式子中第一项是根据当前已有的观测结果  计算出来的关于  的分布的entropy；第二项的expectation里面那一项是我们在已经观测的结果  基础上再加上 $(x,y)$ 的话（更新GP posterior之后）得到的关于  的entropy；这个expectation是对于  所对应的noisy observation $y$ 的posterior distribution的： $y=f(x)+\epsilon \sim \mathcal{N}(\mu_{t-1}(x),\sigma^2_{t-1}(x)+\sigma^2)$ 的。所以，这两项相减的话我们得到的就是通过观测  我们可以减少多少（in expectation）关于  分布的entropy。
Predictive Entropy Search（PES）则是在ES基础上利用conditional information gain的symmetric的性质做了一个机智的变换：

$x_t=\arg\max_{x\in \mathcal{X}}H(\mathbb{P}(y|\mathcal{D}_{t-1},x))-\mathbb{E}_{x^*|\mathcal{D}_{t-1}}\left[H(\mathbb{P}(y|\mathcal{D}_{t-1},x,x^*))\right]$
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），不妨表示为 $\hat{f}_t$ ，然后我们要观测的点就是：

$x_t=\arg\max_{x\in \mathcal{X}}\hat{f}_t(x)$
从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的基础上，把的分布换成 $y^*$ 的分布。

贝叶斯优化的理论

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

BlaXuan · 发表于 2022-1-4 10:01

期待后续哦！

xiangtingsl · 发表于 2022-1-4 10:05

蹲(

Ylisar · 发表于 2022-1-4 10:13

大神我最近在看你今年icml那篇论文

stonstad · 发表于 2022-1-4 10:16

感觉现在贝叶斯优化也不general了，动不动就假设additive form或者low dim manifold[捂脸]

IT圈老男孩1 · 发表于 2022-1-4 10:25

不是大神不是大神。。。github上那个issue就是你提的吧哈哈，我先去把那个坑填上。。。

Zephus · 发表于 2022-1-4 10:25

有读过大佬最近的那篇Binary Auxiliary Information
[干杯]

pc8888888 · 发表于 2022-1-4 10:28

哈哈那篇基本都是我们师姐做的，我只是帮忙做了一点实验。。。

fwalker · 发表于 2022-1-4 10:29

这是因为high-dimensional的问题太难搞了。。。不用这些simplifying assumptions几乎什么都做不了。。。

mypro334 · 发表于 2022-1-4 10:38

哈哈哈，被认出来了，我看你github不经常用，结果今天在知乎上碰到真的有缘

		自动登录	找回密码
密码			立即注册