线性时间中的贝叶斯优化|拟合|新论文|算法|贝叶斯|高维

Bayesian Optimization in Linear Time

线性时间中的贝叶斯优化

https://arxiv.org/pdf/2605.00237

摘要：

贝叶斯优化是一种用于最小化目标函数的序列方法，此类目标函数评估代价高昂，且关于其几乎无法做出假设。通过利用所有已收集的数据训练该函数的高斯过程模型，并自适应地采用全局探索与局部利用的混合策略，该方法已被应用于包括机器学习、汽车工程和强化学习在内的诸多领域的优化问题中。然而，标准方法存在两个问题：1）其计算复杂度随训练集规模呈立方增长，最终导致模型训练在计算上不可行；2）鉴于最小化过程的局部特性，对目标函数进行全局建模未必是最优选择。通过对搜索空间进行灵活且递归的二分划分，我们调整了标准贝叶斯优化的建模与采集方面，使其与划分方案协同工作，从而改善了上述两个标准缺陷。我们在七个具有挑战性的测试函数（维度范围为6至124）上，将本方法与一个常用的贝叶斯优化库进行了对比，结果表明本方法在所有测试中均取得了更优的优化性能。此外，本方法具有线性的计算复杂度。

关键词：机器学习，全局优化，优化，随机过程，聚类，

1.引言

许多优化问题涉及不透明且难以评估的目标函数。此类"黑箱"问题出现在机器学习中的超参数调优[26]、汽车悬架部件设计[25]以及强化学习中的策略优化[30]等场景中。为了在函数f的d维定义域上最小化该函数，如果除了函数的定义域之外几乎无法做出任何假设，那么假设目标函数具有凸性或可微性等性质的标准优化技术可能不适用。此时，优化必须基于对f的性质及其在选定输入配置处评估值的灵活建模假设来进行。如果f的计算成本此外还很高昂，那么评估的预算就会受到限制，可能仅在几百次以内。

贝叶斯优化是应对此类挑战的标准技术[6, 第1章]。通过使用高斯过程对f进行建模，并在选择下一个观察f的点x时权衡探索与利用，贝叶斯优化已在各种技术和工程应用中成功最小化了许多此类函数，例如Google的机器学习模型[7]。

尽管取得了成功，标准贝叶斯优化仍存在两个缺点。首先，如第2节所述，训练f的模型在收集到的观测数量上具有立方级复杂度，这最终会在计算上变得难以处理。其次，f的优化既是一项全局任务也是一项局部任务：有必要准确建模f的全局结构，但仅需达到能够定位最小值参数邻域的程度即可。在其他区域，精度只需足以排除进一步的最小值即可。为了贝叶斯优化的成功，在对f进行建模和获取其连续观测值时，恰当地平衡这些局部和全局优先级是高度可取的。

我们在第3节中通过几种方法协同解决这些缺点。使用聚类和灵活的二元分类，我们递归地划分f的定义域。作为说明，图1(a)展示了d=2时的Rastrigin测试函数（d=6将在第4节中考虑），图1(b)展示了基于收集到的数据进行的划分。该递归过程创建了一个如图2所示的二叉树，其节点代表定义域的子区域。每个节点都获得自己使用从整个数据集中特别选择的子集创建的f的模型。接下来，我们修改f的建模以及后续观测值的获取，使其与搜索空间的划分协调工作。这些方法共同改善了贝叶斯优化的局部和全局建模方面的平衡，并解决了标准方法的两个缺点。更新f模型的计算复杂度从立方级降低到常数级，因为用于拟合节点模型的观测数量有一个硬性上限。此外，整体优化的复杂度从立方级降低到线性级。这导致对于特别苛刻的优化问题，运行时间显著减少。除了运行更快之外，与标准方法相比，改进的局部-全局建模平衡还提高了优化性能，有时提升幅度很大。

我们在第4节中通过将我们的方法（命名为TreeBO）与标准贝叶斯优化库DiceOptim[20]在一组多样化的七个测试函数上进行比较，从而实证验证这些主张，其中包括一个源自汽车质量最小化问题的高维测试。这些测试的维度范围从6到124，每个测试都在受控的初始条件下重复多次。结果表明，TreeBO在所有七个测试中都实现了更优的优化性能，同时在最长、维度最高的测试上运行时间大幅减少。与第5节中描述的替代划分方法相比，TreeBO更简单且更易于调整，与标准贝叶斯优化相比仅多了一个可调整的超参数。此外，这个额外的超参数无需特殊调整即可实现我们的结果。我们在第6节中总结我们的工作，并讨论尚未解决的问题和未来研究的前景。

2 背景

在计算上，使用多种技术来优化 ℓ 和 α ，包括拟牛顿法（如 L-BFGS-B）和遗传算法 [20,22]。贝叶斯优化常用的软件库选择是 R 包 DiceOptim [20, 21]。贝叶斯优化作为重复三元组动作的现代起源始于 Jones 等人 [11]。关于贝叶斯优化历史发展的描述，参见 [6, Ch. 12]。

3 贡献

3.1 分类器的选择

4 实证测试

第 1 节的核心主张是，TreeBO 改善了标准贝叶斯优化的计算难处理性（computational intractability），并改进了对 f f 建模的局部 - 全局平衡，与标准方法相比减少了运行时间并提高了性能。为了证明这些主张，我们将 TreeBO 与贝叶斯优化 R 语言库 DiceOptim [20] 在一组多样化的 7 个中维和高维测试函数上进行了比较。Ackley、Hartmann、Levy、Michalewicz、Rastrigin 和 Schwefel 函数来自仿真实验虚拟库（Virtual Library of Simulation Experiments）[23]，而第七个高维测试源自通用汽车（General Motors）[10] 的一个汽车质量最小化问题。后者通俗地被称为 MOPTA08 Jones 基准 [9, 10]；我们将其称为 Automotive（汽车）问题。我们在本节中描述的有利结果并非从更大规模的测试集中刻意挑选出来的。

这些函数为任何优化方法提供了一系列广泛的挑战：有些是可加的（Michalewicz, Rastrigin, Schwefel），有些是非可加的（Ackley, Hartmann, Levy），有些是高度振荡和多模态的（Michalewicz, Rastrigin, Schwefel），有些在其大部分定义域上具有高度误导性（Ackley），大多数是非常非线性的，且有些函数的特性（Hartmann 和 Automotive）足够晦涩以至于如同黑盒。

除 Automotive（汽车）问题仅进行了 10 次重复（因其耗时较长）外，所有测试均进行了 100 次重复。在不同起始函数评估集上进行多次重复，确保了我们获得的有利结果并非源于少量刻意选择的起始点。每次重复都是配对的，TreeBO 和 DiceOptim 均从相同的 n init ninit 个初始点和随机种子开始。除 Schwefel 函数外，所有测试均使用幂指数核（power-exponential kernel）；出于数值原因，后者使用了 Matérn 核。计算工作在西蒙弗雷泽大学（Simon Fraser University）的 Cedar 和 Fir 集群以及不列颠哥伦比亚大学（University of British Columbia）的 Sockeye 集群上进行。每种方法、每次重复均使用 1 个 CPU 核心和 4 GB 内存。

由于 DiceOptim 是一个 R 语言包，TreeBO 也使用 R 语言 [21] 编写。这使我们能够使用完全相同的方法和设置来为两种方法拟合 GP 模型，从而促进对比。DiceOptim 使用遗传优化（结合拟牛顿步）来最大化采集函数 [17]。TreeBO 最初也遵循此做法，但在经过大量测试后，我们发现对采集函数使用粒子群优化（同样结合拟牛顿步）能改善对目标函数的优化效果 [2]。我们对后者的实现进行了修改，以接受定制的起始点，如第 3 节和算法 4 所述。在将 DiceOptim 与 Python 库 BoTorch [1] 进行比较后，我们发现后者缺乏竞争力，因此未再进一步探究。

除 Automotive（汽车）问题使用 MATLAB [24] 编写外，所有测试函数均使用 R 语言 [21] 编写。为了将 DiceOptim 和 TreeBO 作为 R 程序运行，同时将 Automotive 作为 MATLAB 程序进行评估，我们编写了一个简单的系统级接口，用于在 R 与 MATLAB 之间传递信息。

尽管将原始的约束型 Automotive 测试转换为无约束测试，我们仍然记录了 DiceOptim 和 TreeBO 在观测到的最小目标函数值处违反约束的数量以及违反量的平方和。对于 DiceOptim，违反约束的数量在 40 到 47 之间，违反量的平方和在 5.91 到 7.98 之间。对于 TreeBO，相应的数值分别为 40 和 47，以及 4.72 和 10.16。

为了在平均值之外进一步证实我们在第 1 节中的主张，我们提供了在优化过程中几个时间点上所有重复实验中观测到的最小目标函数值的并排箱线图分布证据。这在图 3 中针对 Ackley 测试展示，在图 4 中针对 Automotive 测试展示。所有测试的图表均在补充材料的 E 节中。这些图表的 x 轴从 0 个后续观测开始，此时两种方法在任何重复实验中都以相同的次评估开始，因此 0 个后续观测处的箱线图是相同的。

对于图 3 中的 Ackley 测试，从 0 到 75 个后续观测，TreeBO 的性能与 DiceOptim 相当。然而，在 100 个后续观测（总共 160 个观测）之后，与 DiceOptim 相比，TreeBO 的中位数和第 75 百分位数已显著下降，而到 140 个后续观测（总共 200 个观测）时，TreeBO 的箱线图在 0 附近压缩得如此紧密，以至于几乎不可见。相比之下，DiceOptim 的第 75 百分位数约为 8。我们将这一改进归因于 TreeBO 的二元划分在搜索原点附近快速下降区域时促进了探索与利用之间更好的平衡。（关于 Ackley 函数的曲面图，参见 https://www.sfu.ca/~ssurjano/ackley.html。）Ackley 函数在其大部分定义域上相对平坦，因此 DiceOptim 的单一全局 GP 模型和采集函数优化可能难以定位原点附近的有希望区域。相比之下，TreeBO 为定义域的不同子区域拟合独立的 GP 模型，因此可能通过不同的 GP 模型获得对定义域的多个视角，从而增加找到全局最小值的机会。

对于高维的 Automotive（汽车）测试，作为一个黑盒，我们无法推测 DiceOptim 和 TreeBO 在方法上有何不同。然而，我们再次看到，在随后的 300 次观测（总共 425 次观测）中，TreeBO 的表现比 DiceOptim 差，在此之后 TreeBO 相对有所改进，以至于在随后的 475 次观测（总共 600 次观测）后，TreeBO 的第 75 百分位数低于 DiceOptim 的第 25 百分位数。

Michalewicz、Rastrigin 和 Hartmann 测试的图表显示出类似的趋势：TreeBO 最初的表现不如 DiceOptim，但最终会超越后者。作为我们在第 6 节讨论 TreeBO 潜在缺点的一部分，我们将讨论这一现象对 TreeBO 可能产生的影响。

5 相关工作

其次，Li 等人 [14] 在每次迭代时从头开始重构他们的树，并根据优化过程的近期表现调整深度。如果观测到的 f f的最小值近期一直在下降，则降低树深度以促进探索。反之，如果它没有下降，则增加树深度以促进利用。这需要一个关于最大树深度的参数。我们的方法从不重建二叉树，从而避免了额外的参数。

第三，为了选择节点，[14] 和 [27] 都使用置信上界（UCB）技术，这些技术源自多臂老虎机，并且需要一个参数来控制探索与利用的权衡。Li 等人 [14] 将其作为输入来计算每个叶节点的“划分得分”，这需要将一个依赖于参数的 softmax 函数应用于 UCB 得分。相比之下，TreeBO 在节点选择上不需要额外的参数，仅优化每个节点的采集函数，然后选择具有最高该值的节点。

[14] 和 [27] 均未公开其代码，导致无法进行比较。因此，在第 4 节中，我们在各种设置下（包括低维和高维）将 TreeBO 与标准贝叶斯优化库 DiceOptim [20] 进行了比较。

6 结论

标准形式的贝叶斯优化是一种有效且广泛使用的技术，用于最小化那些知之甚少且评估代价高昂的目标函数 f 。其计算局限性在于，更新 f 的 GP（高斯过程）模型在收集到的观测数量上具有立方级复杂度，这最终导致该方法变得难以处理。此外，贝叶斯优化需要在建模 f 时平衡局部和全局的优先级，而其拟合单一全局模型的方法未必是最优的。TreeBO 通过对 f 的定义域进行灵活、递归的二元划分来解决这些缺点，创建了一个二叉树，其叶节点代表了用于获取下一次观测的候选子区域。由于任何叶节点中的观测数量都有限制，拟合 f 模型所需的计算量最终变为常数，这改善了标准贝叶斯优化的第一个缺点。此外，每个叶节点都有自己的模型，这提供了对目标函数的多个视角，并改善了建模 f 时的局部 - 全局平衡，从而改善了第二个缺点。这些优势通过在七个具有不同特征的困难测试（包括一个高维、黑盒的汽车质量最小化问题）上进行的数百次运行中，TreeBO 与 DiceOptim 的配对比较得到了证明，在所有这些测试中 TreeBO 均优于 DiceOptim。