贝叶斯优化中有哪些好用的采样函数？

FeastSC · 发表于 2022-1-31 16:31

贝叶斯优化的采样函数其实一直是贝叶斯优化领域的研究重点，主要用于平衡贝叶斯优化过程中的探索和利用困境。不过，近些年出现了一些工作对贝叶斯优化的采样函数在高维优化问题上的效果提出了质疑。这里我重点介绍一种《ACM Transactions on Evolutionary Learning and Optimization》期刊上新提出的 -Greedy采样函数，并尝试介绍该算法与传统的EI和UCB的采样函数的区别，希望能对大家有所启发吧。
什么是 -Greedy采样?

简单来说，在贝叶斯优化场景下，  -Greedy采样可以理解为有  的概率算法会从空间中随机采样，而在剩余情况下采样预测值最大的点[1]。不过这篇文章更进一步，将贝叶斯优化模型中的探索和利用困境视为一个二目标优化问题，从而提出了基于非支配点的随机采样算法，并在一些场景上取得了不错的搜索性能。
高斯过程

首先，我们简单来看一下高斯过程的定义。简单来说，高斯过程的作用就是基于历史数据对未知的待预测数据进行方差和均值的估测。如下图所示，对于给定的模型超参数 $\theta$ ，我们很容易能计算出新数据的预测均值和方差。

具体来说，计算公式如下所示。从下面的公式中可以看出，高斯过程是无参数的预测方法。例如对于均值这一项，高斯过程通过核函数 $\kappa(\mathrm{x}, X)$ 算出每个历史样本点的权重对预测点的权重，再通过协方差矩阵的逆 $K^{-1}$ 计算出历史样本点的相互影响，最后再乘以历史真实值 $f$ ，就可以得到最终的预测值。方差项类似均值项，也是利用核函数和历史数据进行变换，从而实现对方差的预估。

采样函数

采样函数是贝叶斯优化中非常重要的模块，因为高斯过程只能给出均值和方差的估计，然而在真实地贝叶斯优化问题中，我们往往需要平衡探索和利用。过多的探索会导致模型不能充分利用已知知识，从而无法在有限评估次数内达到较优解。而过多利用则会导致模型不能充分探索搜索空间，容易陷入局部最优。因此我们需要采样函数来基于模型给出的均值和方差估计平衡探索和利用。下面将介绍三种常见的采样函数。
Upper Confidence Bound
UCB函数的核心思想为均值和方差通过加权进行平衡，权重为 $\sqrt{\beta_{t}}$ ，从而实现在探索和利用方面的平衡。

Expected Improvement
假设当前最优值为 $f^*$ ，那么采样点  的提升值的定义如下所示。如果点  没有可能比当前最优点更好，那么 $I\left(\mathrm{x}, \hat{f}, f^{\star}\right)=0$ 。

在计算期望提升的时候，需要根据每个采样点的概率分布，利用上面对提升值的定义，计算出期望提升值 $\alpha_{E I}(\mathrm{x})$ 。

Probability of Improvement
PI指标和EI指标有一点类似，区别在于PI指标衡量的是采样点比最优点更好概率，而EI指标衡量的是期望提升值。

上面三种采样函数会导致不同的采样行为，如果把Exploitation和Exploration的平衡看成一个二目标的优化问题，那么下图展示了不同的采样函数最终计算得到的采样点在这样一个二目标优化问题上的位置。从实验结果可以看出，EI和UCB最终都会选择非支配解作为最终的采样点，而PI则会采样支配解。从图中可以看出UCB更偏向探索，EI更偏向利用。然而，在GECCO 2020会议上，有研究者表示，纯利用的采样函数在高维问题上往往能取得比EI和UCB更好的效果[2]。基于上述发现，作者在这篇论文中提出了  -Greedy算法，以期望在探索和利用之间取得一个更好的平衡。

-Greedy采样算法

在本文中，作者提出了  -Greedy算法。这个算法非常容易实现，核心逻辑只有下面短短五行代码。具体来说，我们可以使用多目标演化算法对高斯过程的模型进行优化，从而得到一组关于Exploration和Exploitation的帕累托最优解。随后在采样过程中，该算法有  的概率选择帕累托前沿上的任意一个最优解，而在其他情况下选择预测均值最大的解。

实验结果

下图展示了不同的采样函数在不同问题上的实验结果。该实验以优化得到的最优值和理想最优值之间的差作为评估指标（Regret）。从实验结果来看，  -RS的  -PF算法在不同问题上有着不同的效果。
从实验结果来看，一个比较有趣的现象是在十维问题上，贪婪算法（Exploit）可以取得非常好的效果。作者表示这有可能是因为在高维问题上GP建模并不准确，因此在高维问题上即便仅仅专注于利用，也会因为模型建模不准确从而导致意外的探索行为。

此外，作者还探索了不同  对实验结果的影响，实验结果表明不同  对实验结果的影响并不明显，作者表示  取值为0.1是一个相对较为合适的值。

参考

^De Ath G, Everson R M, Rahat A A M, et al. Greed is good: Exploration and exploitation trade-offs in Bayesian optimisation[J]. ACM Transactions on Evolutionary Learning and Optimization, 2021, 1(1): 1-22.
^Rehbach F, Zaefferer M, Naujoks B, et al. Expected improvement versus predicted value in surrogate-based optimization[C]//Proceedings of the 2020 Genetic and Evolutionary Computation Conference. 2020: 868-876.

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

贝叶斯优化中有哪些好用的采样函数？

本帖子中包含更多资源