超参数优化(二): 贝叶斯优化

franciscochonge · 发表于 2021-11-19 21:14

引言：近年来贝叶斯优化在求解黑盒函数问题中应用越来越广泛，已经成为超参数优化的主流方法。贝叶斯优化是一种全局优化的方法，目标函数只需要满足一致连续或者利普希茨连续等局部平滑性假设；引入采集函数，进行有效探索和利用，能在较少的评估次数下取得复杂目标函数的近似解。
<hr/>

2.1 背景
2.2 贝叶斯优化建模
2.2.1 问题定义
2.2.2 贝叶斯优化框架
2.3 代理模型
2.4 采集函数
2.5 贝叶斯优化进一步探讨

二、贝叶斯优化

2.1 背景

自动超参数优化是黑盒优化的一个具体应用。黑盒优化具有如下的特点：

优化目标

函数空间

优化目标求解

黑盒优化的求解方法：

元启发式算法(meta-heuristic algorithm)

无导数优化方法

近年来，贝叶斯优化在求解黑盒函数问题中应用越来越广泛，已经成为超参数优化的主流方法。贝叶斯优化的优势[15]：

局部平滑性假设

较少的评估次数

探索和利用

我们将在本节末尾讨论贝叶斯优化的局限性。
2.2 贝叶斯优化建模

2.2.1 问题定义

超参数优化问题定义：

$\begin{aligned} argmin_{x\in X} \enspace f(x) \end{aligned} \tag{3}$
其中，为超参数的一组设置取值， $X$ 为混合设计空间(Design Space)。为超参数优化中，我们需要优化的目标（如最小化Loss)。
超参数优化算法的目标是以最快的方式找到全局最优解 $x^* = argmax_{x\in X}\enspace f(x)$ 。
为了达到这个目标，贝叶斯算法求解超参数优化问题，通常分为两步：

第1步

第2步

2.2.2 贝叶斯优化框架

由贝叶斯定理：

$\begin{aligned} 后验分布 &= 先验分布 + 观察数据\\ p(A|B) &= \frac{p(B|A) \cdot p(A)}{ p(B)} \end{aligned} \tag{4}$

$p(A)$

$p(B|A)$

$p(A|B)$

贝叶斯优化框架：

图1：贝叶斯优化框架

步骤1

$n_0$

$X_{init} = \{x_0,x_1,...,x_{n_0-1}\}$

步骤2

$f(X_{init})$

$D_0=\{X_{init} ,f(X_{init})\}$

$t=n_0$

$D_{t-1} = D_0$

$N$

步骤3

$D_{t-1}$

步骤4

$\alpha(x|D_{t-1})$

$x_t= argmin \enspace \alpha(x|D_{t-1}) \\$

步骤5

$x_t$

$f(x_t)$

$D_t=D_{t-1} U \{x_t,f(x_t) \} \\$

步骤6

$\{x^*,y^*\}$

2.3 代理模型

当黑盒函数的自变量是连续值时，高斯过程回归模型(GPs)是一个非常高效的代理模型。对于黑盒函数，我们通常假设其符合某一个GPs先验分布。高斯过程回归模型(GPs)有如下的两方面来决定[3]：

$m(x)$

$k_{\theta}(x,x^{'})$

$\theta$

基于上面两点，我们通常假设我们观测到的函数值 $y_{l}$ 通过如下的形式产生：

$y_{l} = f(x_l) + \epsilon_{l}， where \enspace \epsilon_{l} \sim N(0,\sigma_{noise}^2 ) \\$
进而，可以得到高斯似然函数形式：

$y_{l}|x_{l} \sim N(f_l ,\sigma_{noise}^2 ) \\$
其中 $f_l = f(x_l)$ , 服从如下的分布：

$f(x) \sim GP(m(x),k_{\theta}(x,x^{'})) \tag{5}$
通常假设GP kernel 是平稳的，只依赖于两个点和 $x^{'}$ 之间的模 $||x-x^{'}||$ ，进一步我们假设在带噪音分布条件数据点是平稳的且同质的。如果我们观测的数据点 $\{x,y\}$ 不满足这个条件，我们将不能很好的近似黑盒函数。
2.4 采集函数

给定先验和观察数据，由贝叶斯定理我们可以得到相应的后验分布：

$后验分布= 先验分布 + 观察数据 \\$
采集函数是根据后验分布 $p_{\theta}(f(\cdot)|D)$ 来构造的。在选取GPs作为代理模型条件下，其后验分布仍然是高斯分布：

$p(f(x_{1:q})| D) = N(\mu_{\theta}(x_{1:q}), \sum_{\theta}(x_{1:q})) \tag{6}$
接下来我们列出贝叶斯优化中常见的3种采集函数[3]：

$(Probability improvement ,PI)$

$\alpha_{PI}^{\theta} (x_{1:q} | D ) = E_{post.}[\max_{j\in 1:q}\{H\{f(x_j) - f(x^+) \}\}] \tag{7}$
其中 $H\{.\}$ 为左连续的阶跃函数或开关函数。采集函数PI的原理是在当前 $x^+$ 的邻域附近，找到比大的候选点，取这些概率最大的点，而不管比大多少。

$(Expected Improvement ,EI)$

$\alpha_{EI}^{\theta} (x_{1:q}|D) = E_{post.}[\max_{j\in 1:q}\{ReLU(f(x_j) - f(x^+))\}] \tag{8}$
相比 $PI$ ，给出了下一候选点比当前最优值大多少的问题（提升期望)

$(Upper confidence bound ，UCB)$

$\alpha_{UBC}^{\theta} (x_{j}) = E_{post.}[\max_{j\in 1:q}\{ \mu_{\theta} (x_j) + \sqrt{\beta \pi /2 } | \gamma_{\theta} (x_j) | \}] \tag{9}$
其中 $\mu_{\theta} (x_j)$ 是后续点的后验均值， $\gamma_{\theta} (x_j) = f(x_j) - \mu_{\theta} (x_j)$
不同的采集函数在处理具体问题时有不同的优缺点[15]：

图2：采集函数优缺点对比

和 $UCB$ 都倾向于选取高均值高方差的候选点，但候选点并不趋一致[16]：

图3：EI和UCB不一致情况

2.5 贝叶斯优化进一步探讨

贝叶斯优化中存在的难点：

代理模型

采集函数

和具体优化问题相关

一招鲜吃遍天

<hr/>欢迎关注:simplex101,了解更多超参数优化（黑盒优化）分享内容。

参考文献

QQ浏览器2021AI算法大赛，https://algo.browser.qq.com/

Turner, Ryan, et al. &#34;Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020.&#34; arXiv preprint arXiv:2104.10201 (2021).

TCowen-Rivers, Alexander I., et al. &#34;Hebo: Heteroscedastic evolutionary bayesian optimisation.&#34; arXiv e-prints (2020): arXiv-2012.

Liu, Jiwei, Bojan Tunguz, and Gilberto Titericz. &#34;GPU Accelerated Exhaustive Search for Optimal Ensemble of Black-Box Optimization Algorithms.&#34; arXiv preprint arXiv:2012.04201 (2020).

Sazanovich, Mikita, et al. &#34;Solving black-box optimization challenge via learning search space partition for local bayesian optimization.&#34; NeurIPS 2020 Competition and Demonstration Track. PMLR, 2021.

Wang, Linnan, Rodrigo Fonseca, and Yuandong Tian. &#34;Learning search space partition for black-box optimization using monte carlo tree search.&#34; arXiv preprint arXiv:2007.00708 (2020).

Eriksson, David, et al. &#34;Scalable global optimization via local bayesian optimization.&#34; Advances in Neural Information Processing Systems 32 (2019): 5496-5507.

Eriksson, David, David Bindel, and Christine A. Shoemaker. &#34;pySOT and POAP: An event-driven asynchronous framework for surrogate optimization.&#34; arXiv preprint arXiv:1908.00420 (2019).

Regis, Rommel G., and Christine A. Shoemaker. &#34;A stochastic radial basis function method for the global optimization of expensive functions.&#34; INFORMS Journal on Computing 19.4 (2007): 497-509.

基于径向基函数(RBF)的函数插值

多目标优化总结：概念、算法和应用。知乎多目标优化专栏，https://www.zhihu.com/column/c_1360363335737843712

刘浩洋, 户将, 李勇锋，文再文，最优化：建模、算法与理论, 高教出版社，2020版

Garud, Sushant S., Iftekhar A. Karimi, and Markus Kraft. &#34;Design of computer experiments: A review.&#34; Computers & Chemical Engineering 106 (2017): 71-95.

Viana, Felipe AC. &#34;A tutorial on Latin hypercube design of experiments.&#34; Quality and reliability engineering international 32.5 (2016): 1975-1985.

崔佳旭, 杨博. 贝叶斯优化方法和应用综述[J]. 软件学报, 2018, 29(10): 3068-3090.

Vu Nguyen. &#34;Tutorial on Recent Advances in Bayesian Optimization&#34; Asian Conference on Machine Learning (ACML), 2020.

江璞玉, 刘均, 周奇, 等. 大规模黑箱优化问题元启发式求解方法研究进展[J]. 中国舰船研究, 2021, 16(4): 1–18 doi: 10.19693/j.issn.1673-3185.02248

Larson, Jeffrey, Matt Menickelly, and Stefan M. Wild. &#34;Derivative-free optimization methods.&#34; Acta Numerica 28 (2019): 287-404.

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

超参数优化(二): 贝叶斯优化

本帖子中包含更多资源