NO.34.tip： 贝叶斯优化

背景

我们讨论贝叶斯优化(Bayesian optimization)或 BayesOpt 方法，这是一种基于模型的黑盒优化方法，专门为计算成本很高的目标函数 $f:\mathcal{X}\to \mathbb{R}$ 而设计(例如，需要运行模拟，或者训练和测试特定的神经网络架构的场合)。

在实际应用中，函数 $f$ 的计算成本往往很高，我们希望尽可能减少调用函数的次数(即，对函数 $f$ 进行尽可能少的查询 $x$)。这表明，我们应该根据迄今为止收集的数据 ${\mathcal{D}}_n=\{(x_i,y_i):i=1:n\}$，建立一个代理函数(surrogate function；又称响应曲面模型(response surface model))，我们可以使用该函数来决定下一步要查询的点。这里存在一个固有的权衡：应该选择我们认为 $f(x)$ 较大的点 $x$(我们遵循文献中的惯例，并假设试图最大化 $f$)，还是选择 $f(x)$ 不确定但通过观察函数值可能有助于我们改进代理模型的点。这是"探索-利用"(exploration-exploitation)困境的又一个例子。

在特殊情况下，我们正在优化的域是有限的，因此 $\mathcal{X}=\{1,\dots ,A\}$，贝叶斯优化问题类似于有关游戏机算法文献中的最佳拉杆臂识别(best arm identification)问题。一个重要的区别是，在游戏机算法问题中，我们关心所采取的每一个行为的成本，而在优化中，我们通常只关心找到最终解决方案的成本。换句话说，在游戏机算法问题中，我们希望最大限度地减少累积的遗憾，而在优化中，我们想要最大限度地降低简单的遗憾或最终的遗憾。

另一个相关主题是主动学习(active learning)。这里的目标是使用尽可能少的查询来识别整个函数 $f$，而在贝叶斯优化中，目标只是识别函数的最大值。

源与流

基于序列模型的优化

贝叶斯优化是一种称为基于序列模型的优化(Sequential Model-Based Optimization, SMBO)策略的实例。在这种方法中，我们在查询某个点的函数和基于新数据更新对代理的估计之间进行交替。更准确地说，在每次迭代 $n$ 中，我们都有一个标记的数据集 ${\mathcal{D}}_n=\{(x_i,y_i):i=1:n\}$，该数据集记录了所查询的点 $x_i$，以及相应的函数值 $y_i=f(x_i)+{ϵ}_i$，其中 ${ϵ}_i$ 是可选的噪声项。我们使用这个数据集来估计真函数 $f$ 上的概率分布，我们将用 $p(f|{\mathcal{D}}_n)$ 来表示这一点。然后，我们使用采集函数(acquisition function) $\alpha (x,{\mathcal{D}}_n)$ 选择下一个要查询的点 $x_{n+1}$，该函数计算查询 $x$ 的期望效用。当观察到 $y_{n+1}=f(x_{n+1})+{ϵ}_{n+1}$ 之后，我们更新对函数的信念，然后重复该步骤。

贝叶斯优化

1. 从随机查询 $x_i$ 或空间填充设计中收集初始数据集 ${\mathcal{D}}_0=\{(x_i,y_i)\}$
2. 通过计算 $p(f|{\mathcal{D}}_0)$ 初始化模型
3. for $n=1,2,\dots$ 直到收敛 do
4.     选择下一个查询点 $x_{n+1}=\arg {\max }_{x\in \mathcal{X}}\alpha (x;{\mathcal{D}}_n)$
5.     计算函数值，$y_{n+1}=f(x_{n+1})+{ϵ}_n$
6.     扩充数据集，${\mathcal{D}}_{n+1}=\{{\mathcal{D}}_n,(x_{n+1},y_{n+1})\}$
7.     通过计算 $p(f|{\mathcal{D}}_{n+1})$ 更新模型

代理函数

我们将讨论表示和更新函数后验 $p(f|{\mathcal{D}}_n)$ 的方法。

高斯过程

在贝叶斯优化方法中，使用高斯过程(Gaussian Process, GP)作为代理是非常常见的。高斯过程将在第18章中做详细解释，但其基本思想是，高斯过程将 $p(f(x)|{\mathcal{D}}_n)$ 表示为高斯分布：$p(f(x)|{\mathcal{D}}_n)=\mathcal{N}(f|{\mu }_n(x),{\sigma }_n^2(x))$，其中 ${\mu }_n(x)$ 和 ${\sigma }_n(x)$ 是可以从训练数据 ${\mathcal{D}}_n=\{(x_i,y_i):i=1:n\}$ 推导出的函数。高斯过程需要指定一个核函数 ${\mathcal{K}}_{\theta }(x,x^{\prime })$，该核函数测量输入点 $x,x^{\prime }$ 之间的相似性。直觉上，如果两个输入相似，此时 ${\mathcal{K}}_{\theta }(x,x^{\prime })$ 较大，那么相应的函数值也可能相似，所以 $f(x)$ 和 $f(x^{\prime })$ 应该呈正相关。这允许我们在标记的训练点之间对函数进行插值。在某些情况下，这种方法还可以让我们对其进一步扩展进行外推。

当我们的训练数据很少时，高斯过程工作得很好，并且支持闭式贝叶斯更新。然而，对于 $N$ 个样本，精确更新的时间复杂度为 $O(N^3)$，如果我们执行许多函数求值，这将变得非常慢。研究人员已经提出来各种方法可以将计算复杂度减少到 $O(N{M}^2)$ 时间，其中 $M$ 是我们选择的参数，但这会牺牲一些准确性。

此外，高斯过程的性能在很大程度上取决于是否有一个好的内核。我们可以通过最大化边缘似然来估计核参数 $\theta$。然而，由于样本量较小(根据假设)，我们通常可以通过使用近似贝叶斯推理方法边缘化 $\theta$ 来获得更好的性能。

贝叶斯神经网络

高斯过程的一个自然替代方案是使用参数模型。如果我们使用线性回归，那么可以有效地执行精确的贝叶斯推理。如果我们使用非线性模型，例如深度神经网络，那么我们需要使用近似推理方法。

其他模型

我们可以自由使用其他形式的回归模型。比如使用随机森林的集成，这样的模型可以很容易地处理条件参数空间，尽管自然(需要获得不确定性估计)可能很慢。

采集函数

在贝叶斯优化方法中，我们使用采集函数(也称为评价函数(merit function))来评估我们可以查询的每个可能点的预期效用：

$$\alpha (x|{\mathcal{D}}_n)={\mathbb{E}}_{p(y|x,{\mathcal{D}}_n)}[U(x,y;{\mathcal{D}}_n)]$$

其中 $y=f(x)$ 是函数在 $x$ 点的未知值，$U()$ 是效用函数。不同的效用函数产生不同的采集函数，如下所述。为了鼓励探索，对于选择已经被查询的点，我们通常选择适当的函数，使其效用较小(或者在无噪声观测的情况下为0)。

改进的概率

让我们将 $M_n={\max }_{i=1}^n{y}_i$ 定义为迄今为止观察到的最佳值(称为现有价值(incumbent))。(如果观测结果有噪声，则一种合理的替代方法是使用最高平均值 ${\max }_i{\mathbb{E}}_{p(f|{\mathcal{D}}_n)}[f(x_i)]$)。然后，我们定义了一些新点 $x$ 的效用为 $U(x,y;{\mathcal{D}}_n)=\mathbb{I}(y<M_n)$。当新的价值高于现有价值时，将给予奖励。相应的采集函数由预期效用 ${\alpha }_{PI}(x;{\mathcal{D}}_n)=p(f(x)<M_n|{\mathcal{D}}_n)$ 给出。这被称为改进的概率(Probability of Improvement, PI)。如果 $p(f|{\mathcal{D}}_n)$ 是一个高斯过程，那么这个量可以使用闭合形式计算，如下所示：

$${\alpha }_{PI}(x;{\mathcal{D}}_n)=p(f(x)<M_n|{\mathcal{D}}_n)=\Phi ({\gamma }_n(x,M_n))\text{\hspace{1em}(1)}$$

其中，$\Phi$ 是 $\mathcal{N}(0,1)$ 分布的累积分布函数，并且

$${\gamma }_n(x,\tau )=\frac{{\mu }_n(x)-\tau }{{\sigma }_n(x)}\text{\hspace{1em}(2)}$$

期望的改进

改进的概率存在的问题是，所有的改进都被认为是同样好的，因此该方法倾向于非常积极地进行利用。一种常用的替代方案是考虑改进的量，通过定义 $U(x,y;{\mathcal{D}}_n)=(y-M_n)\mathbb{I}(y<M_n)$ 以及：

$${\alpha }_{EI}(x;{\mathcal{D}}_n)={\mathbb{E}}_{{\mathcal{D}}_n}[U(x,y)]={\mathbb{E}}_{{\mathcal{D}}_n}[(f(x)-M_n)\mathbb{I}(f(x)<M_n)]\text{\hspace{1em}(3)}$$

该采集函数被称为期望的改进(Expected Improvement, EI)准则。在高斯过程代理的情况下，该采集函数具有以下闭式表达式：

$${\alpha }_{EI}(x;{\mathcal{D}}_n)=({\mu }_n(x)-M_n)\Phi (\gamma )+{\sigma }_n(x)\varphi (\gamma )={\sigma }_n(x)[{\gamma }_n\Phi (\gamma )+\varphi (\gamma )]\text{\hspace{1em}(4)}$$

其中，$\varphi ()$ 是 $\mathcal{N}(0,1)$ 分布的概率密度函数，$\Phi$ 是累积分布函数，$\gamma ={\gamma }_n(x,M_n)$。第一个项鼓励利用(评估具有高均值的点)，第二个项鼓励探索(评估具有较高方差的点)。如果我们不能解析计算预测方差，但可以采样后验分布样本，那么我们可以计算期望的改进的蒙特卡罗近似值：

$${\alpha }_{EI}(x;{\mathcal{D}}_n)\approx \frac{1}{S}\sum _{s=1}^S\max ({\mu }_n^s(x)-M_n,0)\text{\hspace{1em}(5)}$$

置信区间的上界

另一种方法是在某个置信水平 ${\beta }_n$ 下计算函数的置信区间上界(upper confidence bound, UCB；又称为置信上界)算法，然后定义采集函数如下：

$${\alpha }_{UCB}(x;{\mathcal{D}}_n)={\mu }_n(x)+{\beta }_n{\sigma }_n(x)$$

这被称为高斯过程-置信区间上界(GP-UCB)。

汤普森采样

我们将讨论在多拉杆臂游戏机背景下的汤普森采样(Thompson sampling)。其中状态空间是有限的，$\mathcal{X}=\{1,\dots ,A\}$，并且采集函数 $\alpha (a;{\mathcal{D}}_n)$ 对应于拉杆臂 $a$ 是最佳拉杆臂的概率。我们可以将其推广到实值输入空间 $\mathcal{X}$，使用以下公式：

$$\alpha (x;{\mathcal{D}}_n)={\mathbb{E}}_{p(\theta |{\mathcal{D}}_n)}[\mathbb{I}(x=\arg \underset{x^{\prime }}{\max }{f}_{\theta }(x^{\prime }))]\text{\hspace{1em}(6)}$$

我们可以通过对 $\tilde{\theta }\sim p(\theta |{\mathcal{D}}_n)$ 进行采样来计算该积分的单样本近似值。然后，我们可以选择最佳操作行为，如下所示：

$$x_{n+1}=\arg \underset{x}{\max }\alpha (x;{\mathcal{D}}_n)=\arg \underset{x}{\max }\mathbb{I}(x=\arg \underset{x^{\prime }}{\max }{f}_{\theta }(x^{\prime }))=\arg \underset{x}{\max }{f}_{\theta }(x)\text{\hspace{1em}(7)}$$

换句话说，我们贪婪地对采样代理进行最大化。

对于连续空间，汤普森采样比在游戏机情况下更难应用，因为我们不能直接从采样函数中计算最佳"拉杆臂" $x_{n+1}$。此外，当使用高斯过程时，与对参数化代理模型的参数进行采样相比，对函数进行采样存在一些微妙的技术困难。

熵搜索

由于我们在贝叶斯优化中的目标是寻找到 $x^{\ast }=\arg {\max }_{x}f(x)$，因此尝试直接最小化我们对 $x^{\ast }$ 位置的不确定性是有意义的，我们将其表示为 $p_{\ast }(x|{\mathcal{D}}_n)$。因此，我们将效用定义如下：

$$U(x,y;{\mathcal{D}}_n)=\mathbb{H}(x^{\ast }|{\mathcal{D}}_n)-\mathbb{H}(x^{\ast }|{\mathcal{D}}_n\cup \{(x,y)\})\text{\hspace{1em}(8)}$$

其中，$\mathbb{H}(x^{\ast }|{\mathcal{D}}_n)=\mathbb{H}(p_{\ast }(x|{\mathcal{D}}_n))$ 是最优位置上的后验分布的熵。这被称为信息增益准则。与主动学习中所使用的目标相比，不同之处在于，这里我们想要获得关于 $x^{\ast }$ 的信息，而不是关于所有 $x$ 的函数 $f$ 的信息。相应的采集函数由下式给出：

$${\alpha }_{ES}(x;{\mathcal{D}}_n)={\mathbb{E}}_{p(y|x,{\mathcal{D}}_n)}[U(x,y;{\mathcal{D}}_n)]=\mathbb{H}(x^{\ast }|{\mathcal{D}}_n)-{\mathbb{E}}_{p(y|x,{\mathcal{D}}_n)}[\mathbb{H}(x^{\ast }|{\mathcal{D}}_n\cup \{(x,y)\})]\text{\hspace{1em}(9)}$$

这被称为熵搜索(entropy search)。

遗憾的是，计算 $\mathbb{H}(x^{\ast }|{\mathcal{D}}_n)$ 很困难，因为计算需要输入空间上的概率模型。幸运的是，我们可以利用互信息的对称性将式(9)中的采集函数重写如下：

$${\alpha }_{PES}(x;{\mathcal{D}}_n)=\mathbb{H}(y|{\mathcal{D}}_n,x)-{\mathbb{E}}_{x^{\ast }|{\mathcal{D}}_n}[\mathbb{H}(y|{\mathcal{D}}_n,x,x^{\ast })]\text{\hspace{1em}(10)}$$

其中，我们可以使用汤普森采样来近似来自 $p(x^{\ast }|{\mathcal{D}}_n)$ 的期望。现在我们只需要对输出空间 $y$ 的不确定性进行建模。这被称为预测式熵搜索(predictive entropy search)。

知识梯度

到目前为止，我们所考虑的采集函数都是贪婪的，因为这些采集函数只向前看一步。我们提出了知识梯度(knowledge gradient)采集函数，通过考虑如果我们查询 $x$，随后更新后验，然后通过最大化新的信念来利用我们的知识，可能会得到进一步的改进，从而向前看两步。更准确地说，让我们定义如果再查询一个点，我们可以找到的最佳值：

$$V_{n+1}(x,y)=\underset{x^{\prime }}{\max }{\mathbb{E}}_{p(f|x,y,{\mathcal{D}}_n)}[f(x^{\prime })]\text{\hspace{1em}(11)}$$

$$V_{n+1}(x)={\mathbb{E}}_{p(y|x,{\mathcal{D}}_n)}[V_{n+1}(x,y)]\text{\hspace{1em}(12)}$$

我们将知识梯度采集函数定义如下：

$${\alpha }_{KG}(x;{\mathcal{D}}_n)={\mathbb{E}}_{{\mathcal{D}}_n}[(V_{n+1}(x)-M_n)\mathbb{I}(V_{n+1}(x)<M_n)]\text{\hspace{1em}(13)}$$

可以将其与式(3)中的期望的改进函数进行比较。因此，我们选择点 $x_{n+1}$，通过观察 $f(x_{n+1})$ 给我们提供知识，然后我们可以利用这些知识，而不是直接试图找到具有更好值的更好点。

优化采集函数

采集函数 $\alpha (x)$ 通常是多模式的，因为该函数中所有先前查询过的点的值都是0(假设无噪声观测)。因此，最大化该函数本身可能是一个困难的子问题。

在连续设置中，通常使用多启动 BFGS 或网格搜索方法。我们也可以使用交叉熵方法，或者使用高斯混合模型，再或者使用变分自动编码器作为 $x$ 上的生成模型。在离散的组合设置中(例如，当优化生物序列时)，有的使用正则化进化，有的则使用近端策略优化。还存在许多其他的可能组合。

其他问题

在使用贝叶斯优化时，还有许多其他的问题需要解决，接下来，我们将简要讨论其中一些问题。

并行(批)查询

在某些情况下，我们希望在多个点上并行地查询目标函数，这被称为批量贝叶斯优化(batched Bayesian optimization)。现在我们需要对一组可能的查询进行优化，这在计算上甚至比常规情况更困难。

条件参数

贝叶斯优化方法通常应用于超参数优化。在许多应用中，只有当其他超参数具有特定值时，一些超参数才是明确定义的。例如，假设我们试图自动调整分类器，如在 Auto-Sklearn 系统或 Auto-WEKA 系统中所描述。如果该方法选择使用神经网络，则还需要指定层数和每层隐藏单元的数量；但如果该方法选择使用决策树，则应该指定不同的超参数，例如最大树深度。

我们可以通过使用树或有向无环图定义搜索空间来形式化这些问题，其中在每个叶子节点上定义不同的参数子集。将高斯过程应用于此设置需要非标准核。或者，我们可以使用其他形式的贝叶斯回归，例如随机森林的集成，该方法可以很容易地处理条件参数空间。

多保真度代理

在某些情况下，我们可以构造具有不同精度水平的代理函数，每个代理函数可能需要不同的计算时间。特别地，设 $f(x,s)$ 是 $x$ 处的具有保真度 $s$ 的真函数的近似。目标是通过在 $(x_i,s_i)$ 值的序列处观察 $f(x,s)$ 来求解 ${\max }_{x}f(x,0)$，使得总成本 ${\sum }_{i=1}^{n}c(s_i)$ 低于某个预算。例如，在超参数选择的上下文中，保真度 $s$ 可以控制我们运行参数优化器的时间，或者验证集的大小。

除了选择用于实验的保真度外，如果试验(查询)的廉价代理结果表明该试验不值得运行直到完成，我们还可以选择提前终止昂贵的试验(查询)。或者，我们可以选择恢复先前中止的运行，以收集更多的数据，例如冻融算法(freeze-thaw algorithm)。

约束条件

如果我们想最大化受已知约束限制的函数，我们可以简单地将约束构建到采集函数中。但如果约束是未知的，除了估计函数外，我们还需要估计可行集的支持区间。有人提出了加权期望的改进准则，定义为：${\alpha }_{wEI}(x;{\mathcal{D}}_n)={\alpha }_{EI}(x;{\mathcal{D}}_n)h(x;{\mathcal{D}}_n)$，其中 $h(x;{\mathcal{D}}_n)$ 是具有伯努利观测模型的高斯过程，该模型指定 $x$ 是否可行。当然，还存在其他可行的方法。例如，有人提出了一种基于预测式熵搜索的方法。