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

franciscochonge

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

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

二、贝叶斯优化

2.1 背景

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

优化目标：没有显式的函数表达式，获取不到其梯度信息；其值域分布是多峰、非凸非凹的复杂昂贵函数；函数空间：由连续、离散整数值构成的，且实际应用中维度较高；优化目标求解：求解非常昂贵耗时，在工业设计中通常一次评估花费数十万至百万元以上；在大规模的深度学习训练中通常花费若干天甚至数周时间进行一次参数搜索。

黑盒优化的求解方法：

元启发式算法(meta-heuristic algorithm)[17]： 遗传算法 (genetic algorithm, GA)、差分进化(differential evolution, DE) 算法、粒子群算法 (particle swarm optimization, PSO)、进化策略(evolutionary strategies, ES)无导数优化方法[18]：随机搜索、直接搜索法；基于模型的如多项式方法，径向基函数插值方法和基于代理模型方法，如贝叶斯优化。

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

是一种全局优化的方法，目标函数只需要满足一致连续或者利普希茨连续(Lipschitz) 等局部平滑性假设；能在较少的评估次数下，取得复杂目标函数的近似解；引入采集函数，进行有效的探索和利用(Exploration and Exploitation)

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

2.2.1 问题定义

超参数优化问题定义：


其中，为超参数的一组设置取值，为混合设计空间(Design Space)。为超参数优化中，我们需要优化的目标（如最小化Loss)。
超参数优化算法的目标是以最快的方式找到全局最优解 。
为了达到这个目标，贝叶斯算法求解超参数优化问题，通常分为两步：

第1步：学习一个代理模型(Surrogate Model)；第2步：通过采集函数(Acquisition Function)，来决定输出下一个采集点。

2.2.2 贝叶斯优化框架

由贝叶斯定理：

为先验分布，即我们的代理模型； 为给定代理模型，观察数据的分布； 为后验分布，即给定观察数据之后代理模型新分布。

贝叶斯优化框架：



图1：贝叶斯优化框架

步骤1： 随机初始化点步骤2：获得其对应的函数值，初始点集令, ，循环直到达到最大次数

步骤3：根据当前获得的点集，构建代理模型步骤4：基于代理模型，最大化采集函数，获得下一个评估点:

步骤5：获得评估点的函数值, 将其加入到当前评估点集合中:

步骤6：输出最优候选评估点：

2.3 代理模型

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

均值函数 ；协方差函数(矩阵)，或者核函数 ，其中为核函数超参数。

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


进而，可以得到高斯似然函数形式：


其中,  服从如下的分布：


通常假设GP kernel 是平稳的，只依赖于两个点和之间的模 ，进一步我们假设在带噪音分布条件数据点是平稳的且同质的。如果我们观测的数据点不满足这个条件，我们将不能很好的近似黑盒函数。
2.4 采集函数

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


采集函数是根据后验分布来构造的。在选取GPs作为代理模型条件下，其后验分布仍然是高斯分布：


接下来我们列出贝叶斯优化中常见的3种采集函数[3]：

提升的概率:

其中为左连续的阶跃函数或开关函数。采集函数PI的原理是在当前的邻域附近，找到比大的候选点，取这些概率最大的点，而不管比大多少。

提升的期望:

相比，给出了下一候选点比当前最优值大多少的问题（提升期望)

上置信边界:

其中是后续点的后验均值，
不同的采集函数在处理具体问题时有不同的优缺点[15]：



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


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



图3：EI和UCB不一致情况

2.5 贝叶斯优化进一步探讨

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

代理模型：我们通常选取GPs；当我们求解的问题维度变高时，GPs求解的复杂度变高；如何求解高维的贝叶斯优化问题，是一个值得探讨和研究的问题；采集函数：通常选取上述函数中的一个作为代理模型的采集函数（中途不会更改采集函数）。这个采集函数相对于我们的代理模型和我们要优化的问题是否是最优的呢？我们在HEBO这一节详细讨论这个问题；和具体优化问题相关：在应用贝叶斯优化求解实际问题，通常要根据实际问题，结合相关的领域知识选择合适的代理模型和采集函数，如我们后续讨论的没有”一招鲜吃遍天“的方法。

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

参考文献

[1] QQ浏览器2021AI算法大赛，https://algo.browser.qq.com/ [2] Turner, Ryan, et al. "Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020." arXiv preprint arXiv:2104.10201 (2021). [3] TCowen-Rivers, Alexander I., et al. "Hebo: Heteroscedastic evolutionary bayesian optimisation." arXiv e-prints (2020): arXiv-2012. [4] Liu, Jiwei, Bojan Tunguz, and Gilberto Titericz. "GPU Accelerated Exhaustive Search for Optimal Ensemble of Black-Box Optimization Algorithms." arXiv preprint arXiv:2012.04201 (2020). [5] Sazanovich, Mikita, et al. "Solving black-box optimization challenge via learning search space partition for local bayesian optimization." NeurIPS 2020 Competition and Demonstration Track. PMLR, 2021. [6] Wang, Linnan, Rodrigo Fonseca, and Yuandong Tian. "Learning search space partition for black-box optimization using monte carlo tree search." arXiv preprint arXiv:2007.00708 (2020). [7] Eriksson, David, et al. "Scalable global optimization via local bayesian optimization." Advances in Neural Information Processing Systems 32 (2019): 5496-5507. [8] Eriksson, David, David Bindel, and Christine A. Shoemaker. "pySOT and POAP: An event-driven asynchronous framework for surrogate optimization." arXiv preprint arXiv:1908.00420 (2019). [9] Regis, Rommel G., and Christine A. Shoemaker. "A stochastic radial basis function method for the global optimization of expensive functions." INFORMS Journal on Computing 19.4 (2007): 497-509. [10] 基于径向基函数(RBF)的函数插值 [11] 多目标优化总结：概念、算法和应用。知乎多目标优化专栏，https://www.zhihu.com/column/c_1360363335737843712 [12] 刘浩洋, 户将, 李勇锋，文再文，最优化：建模、算法与理论, 高教出版社，2020版 [13] Garud, Sushant S., Iftekhar A. Karimi, and Markus Kraft. "Design of computer experiments: A review." Computers & Chemical Engineering 106 (2017): 71-95. [14] Viana, Felipe AC. "A tutorial on Latin hypercube design of experiments." Quality and reliability engineering international 32.5 (2016): 1975-1985. [15] 崔佳旭, 杨博. 贝叶斯优化方法和应用综述[J]. 软件学报, 2018, 29(10): 3068-3090. [16] Vu Nguyen.  "Tutorial on Recent Advances in Bayesian Optimization" Asian Conference on Machine Learning (ACML), 2020. [17] 江璞玉, 刘均, 周奇, 等. 大规模黑箱优化问题元启发式求解方法研究进展[J]. 中国舰船研究, 2021, 16(4): 1–18 doi:  10.19693/j.issn.1673-3185.02248 [18] Larson, Jeffrey, Matt Menickelly, and Stefan M. Wild. "Derivative-free optimization methods." Acta Numerica 28 (2019): 287-404.