2.4　获取函数

在回顾了高斯过程后，回到算法2.1并讨论其中使用的获取函数。最常用的获取函数是期望改进，我们首先在2.4.1节中讨论它。期望改进表现良好且易于使用。然后本章讨论知识梯度（2.4.2节）、熵搜索和预测熵搜索（2.4.3节）获取函数。这些替代获取函数最适用于特殊问题，其中期望改进做出的假设不再成立，即采样的主要效益不再是通过在采样点处改进实现的。

2.4.1　期望改进

期望改进（Expected Improvement，EI）获取函数是通过一个理想的实验推导出来的。假设使用算法2.1求解式（2-1），其中 x _n 表示在第 n 次迭代中采样的点， y _n 表示其观测值。假设只能将评估过的解作为式（2-1）的最终解返回。此外，假设没有剩余的函数评估次数，所以必须根据已经执行的评估返回解。由于观测到 f 没有噪声，因此最佳选择是已经评估的具有最大观测值的点。让 为该点的值，其中 n 是迄今为止评估函数 f 的次数。

现在假设实际上有一次额外的函数评估要进行，而且可以在任意点处进行。如果在 x 处进行评估，将观察到 f （ x ）。在执行完新的函数评估后，已经观察到的最大观测值将是 f （ x ）（如果 ）或 （如果 ）。如果这个数量是正的，那么最佳观测点的值改进为 ，否则为0。我们可以更简洁地将这个改进写成[ f （ x ）- ] ⁺ ，其中 a ⁺ =max（ a ，0）表示正部分。

虽然希望选择 x 使得这种改进很大，但在评估之前 f （ x ）是未知的。然而，可以对这个改进的期望值进行计算，并选择 x 使其最大化。定义期望改进为

其中， E _n [·]= E _n [·| x _{1： n} ， y _{1： n} ]表示在给定 x ₁ ， x ₂ ，…， x _n 处对 f 进行评估的情况下取后验分布的期望值。这个后验分布由式（2-3）给出，即给定 x _{1： n} 和 y _{1： n} ， f （ x ）服从均值为 μ _n （ x ）、方差为 的正态分布。

可以使用部分积分的方法，如文献[37，135]所述，隐式地计算期望改进，即得到的表达式为

其中， 是建议点 x 与之前最佳观测点之间的预期质量差异。

通过期望改进算法获得新的评估点，然后在具有最大期望改进的点处进行评估。

该算法最初是由文献[136]提出的，但是在文献[37]中的有效全局优化方法（Efficient Global Optimization，EGO）中得到普及。

针对求解式（2-13）的方法，实现方案采用多种方法解决。与原始优化问题公式（2-1）中的目标函数 f 不同，EI _n （ x ）的评估成本较低，并且可以轻松地评估一阶和二阶导数。期望改进算法的实现可以使用连续的一阶或二阶优化方法求解式（2-13）。例如，一种有效的技术是计算一阶导数并使用拟牛顿法L-BFGS-B ^[137] 。

图2.3展示了EI _n （ x ）在 Δ _n （ x ）和后验标准差 σ _n （ x ）方面的等高线。EI _n （ x ）随着 Δ _n （ x ）和 σ _n （ x ）的增加而增加。在具有相等EI的情况下， Δ _n （ x ）与 σ _n （ x ）的曲线显示了EI如何在评估具有高预期质量（高 Δ _n （ x ））的点与高不确定性（高 σ _n （ x ））的点之间取得平衡。在优化的背景下，评估相对于之前的最佳点具有高预期质量的点是有价值的，因为好的近似全局最优解很可能存在于这些点上。另外，评估具有高不确定性的点是有价值的，因为它可以在先验知识很少且往往远离之前测量的位置上的目标。一个比已评估点更优的点很可能位于此位置。

图2.1中的底部面板显示了EI _n （ x ）。可以看出，这种权衡即最大的期望改进发生在后验标准差高（远离之前评估的点）且后验均值也高的地方。期望改进在已评估过的点处值最小，为0。在此点处，后验标准差为0，后验均值必然不大于之前评估的最佳点。期望改进将在下一个被标记为 x 的点处进行函数评估，该点是使得期望改进EI值最大的点。

基于高预期性能和高不确定性之间的权衡选择评估位置在其他领域中也出现过，包括多臂赌博机 ^[138] 以及强化学习 ^[139] ，通常被称为“利用与探索权衡” ^[140] 。

2.4.2　知识梯度

知识梯度获取函数是通过重新审视EI的假设推导出来的，该假设只允许将之前评估过的点作为最终解返回。当评估是无噪声的且风险容忍度极低时，这种假设是合理的。但如果决策者愿意容忍一些风险，那么该方法可报告具有一定不确定性的最终解。此外，如果评估存在噪声，那么最终解必然具有不确定的价值，因为几乎无法对其进行无限次数的评估。

通过允许决策者返回任何其喜欢的解替换这种假设，即使该解以前没有被评估过。还假设风险中立 ^[141] ，即根据其期望值对随机结果 X 进行评估。如果在 n 次采样后停止，会选择具有最大 μ _n （ x ）值的解。此解（称其为 ，因为它近似全局最优解 x ^* ）将具有值 。在后验下， 是随机的，并且具有条件期望值 。

另外，如果在 x 处再进行一次采样，将得到一个新的后验分布，其后验均值为 μ _{n +1} （·），该后验均值将通过式（2-3）计算，只不过其包括附加观测值 x _{n +1} ， y _{n +1} 。如果在这个样本之后报告最终解，它在新的后验分布下的期望值将是 。因此，由于采样而导致的条件期望解的均值的增加是 。

虽然在采样 x _{n +1} 前期值是未知的，但可以在给定已经获得 x ₁ ， x ₂ ，…， x _n 的观测值的情况下计算其期望值。我们称这个量为知识梯度（Knowledge Gradient，KG），用于衡量在 x 处进行测量。

使用知识梯度作为获取函数，则新的采样点为能最大化KG _n （ x ）的点，即argmax _x KG _n （ x ）。

该算法最初由文献[142]提出，用于离散 A 上的GP回归。基于早期工作 ^[143] ，该工作提出了相同的算法用于具有独立先验的贝叶斯排名和选择 ^[144] （贝叶斯排名和选择类似于贝叶斯优化，但是 A 是离散和有限的，观测值必然存在噪声，并且先验通常在 x 上是独立的）。

从概念而言，计算知识梯度获取函数最简单的方法是通过模拟，如算法2.2所示。在循环内，此算法模拟了在指定 x 处进行第 n +1次评估后观测值 y _{n +1} 的一个可能值。然后，它计算如果该 y _{n +1} 值是实际测量结果，则新的后验均值 的最大值是多少。接下来，它减去 以获得相应的解决方案质量的增加。以上循环是整个算法的一个循环。它迭代此循环多次（ J 次），并对来自不同模拟 y _{n +1} 值的 差异求均值，以估计KG _n （ x ）获取函数。随着 J 的增大，该估计值会收敛到KG _n （ x ）。

原则上，该算法可被用于在无导数模拟优化方法中评估KG _n （ x ）以优化KG获取函数。然而，在无法获得导数的情况下，优化基于模拟的噪声函数是非常具有挑战性的。文献[142]建议对 A 进行离散化，并使用正态分布的性质精确地计算式（2-14）。这对低维问题很有效，但在高维问题中计算量变得巨大。

为了克服维度挑战，文献[126]提出了一种更高效和可扩展的方法，基于多次启动的随机梯度上升方法。随机梯度上升 ^[145-146] 是一种用于寻找函数局部最优解的算法，广泛用于机器学习中的无偏梯度估计。多次启动的随机梯度上升 ^[147] 从不同的起始点运行多个随机梯度上升实例，并选择找到的最佳局部最优解作为近似全局最优解。

在算法2.3中总结了最大化KG获取函数的方法。该算法迭代启动点（由 r 索引），并针对每个启动点维护一个迭代序列 ，由 t 索引，该序列收敛到KG获取函数的局部最优解。 t 的内部循环依赖于随机梯度 G 。 G 是一个随机变量，其期望值等于在当前迭代 处采样时，KG获取函数相对于梯度的值。沿着随机梯度 G 的方向迈出一步，就能得到下一个迭代。这一步的大小由 G 的大小和递减的步长 α _t 确定。一旦每个启动点的随机梯度上升迭代 T 次后，算法2.3使用模拟（算法2.2）评估对每个起始点获得的最终点的KG获取函数进行评估，并选择最佳点。

算法2.3内循环使用的随机梯度 G 是通过算法2.4计算得到的。该算法基于如下思想。在足够的正则性条件下，通过交换梯度和期望值可以得到以下公式，即

其中， 不依赖于 x 。这种方法被称为无穷小扰动分析 ^[148] 。因此，构造随机梯度只需要采样▽ 即可。换言之，先在算法2.2的内循环中采样 Z ，然后在计算 相对于 x 的梯度时，将 Z 固定不变。要计算该梯度，可以看到 是 μ _{n +1} （ x' ； x ， y _{n +1} ）= μ _{n +1} （ x' ； x ， μ _n （ x ）+ σ _n （ x ） Z ）关于 x' 的最大值，其中 x' 是 x 的一组函数。由包络定理 ^[149] 可知，在足够的正则性条件下，要求得与 x 相关的一组函数的最大值相对于 x 的梯度，只需首先找到这个集合中的最大值，然后对这个单一函数相对于 x 的梯度进行微分即可。在设置中，通过令 为最大化 μ _{n +1} （ x' ； x ， μ _n （ x ）+ σ _n （ x ） Z ）的 x' ，然后在保持 不变的情况下计算 相对于 x 的梯度。换言之，即

▽表示相对于 x 取梯度，此处和其他地方亦如此。算法2.4概括如下。

与只考虑采样点后验的EI不同，KG考虑了 f 整个定义域上的后验值，以及采样如何改变此后验值。即使采样点的值不比之前的最佳点更好，KG也会对导致后验均值最大值提高的测量赋予正值。这为无噪声评估的标准贝叶斯选择问题带来了微小的性能优势 ^[142] ，并在存在噪声、多保真度观测、导数观测、需要整合环境条件以及其他更奇特的问题特征中提供了显著的性能提升。在这些替代问题中，采样的价值并不是通过在采样点上的最佳解的改进实现的，而是通过改进可行解的后验均值的最大值实现的。例如，导数观测可能会显示，在采样点附近，函数沿特定方向递增。即使采样点的函数值比之前的最佳采样点更差，这可能导致后验均值的最大值显著大于之前的最大值。当这种现象属于一阶现象时，KG往往会明显优于EI ^{[121，126，150]} 。

2.4.3　熵搜索和预测熵搜索

熵搜索（ES） ^[65] 获取函数根据差分熵对已知有关全局最大值位置的信息进行估值。ES会查找导致差分熵下降最大的点进行评估（例如文献[151]所述，连续概率分布 p （ x ）的微分熵为∫ p （ x ）log（ p （ x ））d x ，较小的微分熵表示较少的不确定性）。预测熵搜索（PES） ^[66] 寻求相同的点，但是使用基于互信息的熵减少目标的重新表述。精确计算PES和ES将会得到等效的获取函数，但通常无法进行精确计算，因此用于近似PES和ES获取函数的计算技术的差异会导致这两种方法在采样决策中产生实际差异。首先讨论ES，然后讨论PES。

设 x ^* 为 f 的全局最优解，时间为 n 时的 f 后验分布可以推出 x ^* 的概率分布。实际上，如果定义域 A 是有限的，那么可以通过向量（ f （ x ）： x ∈ A ）定义 f 在其定义域上的分布，而 x ^* 对应于该向量中的最大元素。在时间 n 的后验分布下，该向量的分布是多元正态分布，而这个多元正态分布意味着 x ^* 的分布。当 A 连续时，相同的思想适用，其中 x ^* 是一个随机变量，其分布由对 f 的高斯过程后验所指示。

基于这种理解，用符号 H （ P _n （ x ^* ））表示 x ^* 的时间 n 后验分布的熵。类似地， H （ P _n （ x ^* | x ， f （ x ）））表示如果在 x 处观察到 f （ x ），则时间 n +1后验分布在 x ^* 上的熵。这个量取决于观察到的 f （ x ）值。因此由于采样 x 导致的熵减少可以表示为

在第二项中，外部期望中的下标表示对 f （ x ）求期望。等价地，这可以写成∫ φ （ y ； μ _n （ x ）， ，其中 是均值为 μ _n （ x ）、方差为 的正态分布的概率密度。

与KG一样，ES和PES受测量如何改变整个定义域上的后验分布的影响，而不仅仅取决于在采样点上是否比现有解法有所改进。这对于决定在奇异问题中的采样位置非常有用，而且ES和PES在这方面比EI更有价值。

虽然ES可以近似计算和优化 ^[65] ，但这样做具有挑战性，因为：①高斯过程最大化的熵无法以封闭形式获得；②必须对大量 y 的熵，以近似式（2-17）中的期望；③然后必须优化这个难以评估的函数。与KG不同，目前还没有已知的计算随机梯度的方法简化这一优化过程。

PES提供了一种计算式（2-17）的替代方法。该方法指出，由于测量 f （ x ）而导致 x ^* 熵的减少等于 f （ x ）和 x ^* 之间的互信息，而互信息又等于由于测量 x ^* 而导致 f （ x ）减少的熵。这一等价关系给出了下面的表达式，即

其中，第二项期望中的下标表示期望是针对 x ^* 进行的。

与ES不同，PES获取函数中的第一项 H （ P _n （ f （ x ）））可以通过封闭形式计算。第二项仍然需要进行近似计算：文献[66]提供了一种从后验分布中采样 x ^* ，并使用期望传播近似计算 H （ P _n （ f （ x ）| x ^* ））的方法，然后可以通过模拟进行无导数优化的方法优化这种评估方法。

2.4.4　多步最优获取函数

可以将求解式（2-1）的过程视为一个顺序决策问题 ^[124] ，其中依次选择 x _n ，并观察 y _n = f （ x _n ）， x _n 的选择取决于所有过去的观察结果。在这些观察结束时，会获得一个奖励，这个奖励可能等于已观察到的最佳点的值max _{m ≤ N} f （ x _m ），就像在EI分析中那样，或者可能等于基于这些观察结果选择的某个新点 处的目标函数的值 ，如同在KG的分析中，或者它可能是 x ^* 的后验分布的熵，就像在ES或PES中一样。

根据构造，当 N = n +1时，EI、KG、ES和PES获取函数是最优的，即最大化后验下的预期收益。然而，当 N > n +1时，显然它们不再是最优的。原则上，可以通过随机动态规划 ^[152] 计算多步最优获取函数，以在一般情况下最大化预期奖励，但所谓的维度诅咒 ^[153] 使得在实践中计算这种多步最优获取函数非常具有挑战性。

然而，近年来文献开始使用近似方法计算这个解，包括文献[124，154-155]。这些方法似乎还没有达到可以广泛应用于实际问题的程度，因为近似解决随机动态规划问题所引入的误差和额外成本往往会超过考虑多步最优算法所提供的好处。然而，鉴于强化学习和近似动态规划的同时进步，贝叶斯优化是一个有前途和令人兴奋的方向。

此外，还有其他一些与贝叶斯优化最常考虑的问题设置密切相关的问题，可以计算多步最优算法。例如，文献[156-157]利用问题结构有效地计算某些贝叶斯可行性确定问题类的多步最优算法，其中我们希望高效地采样以确定每个 x 的 f （ x ）是否高于或低于阈值。同样，文献[158]计算了具有熵目标的一维随机寻根问题的多步最优算法。虽然这些多步最优方法只直接适用于非常特殊的环境，但它们为研究从一步最优到多步最优所可能带来的更普遍的改进提供了机会。令人惊讶的是，在这些设置中，现有的获取函数的表现几乎与多步最优算法一样好。例如，文献[156]进行的实验显示，KG获取函数在其计算的问题中接近98%的最优解，而文献[158]表明，在其考虑的设置中，ES获取函数是多步最优的。从这些结果推广，可能是一步获取函数已足够接近最优，以至于进一步改进并无实际意义，或者可能是多步最优算法将在尚未确定的实际环境中提供更好的性能。 2p6guLqKCWFnV4XLgbcxMF5+cnEf2Nr+Xok0AG27YoztzVNNP0dfpNo73XR4RfHI