💻 computer science

KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

本文介绍了 KSOS-BO，这是一种基于核的无导数框架，将贝叶斯优化采集函数的优化问题表述为半定规划，在多样化的基准景观上，相较于标准的无导数基线方法，展现出更优的样本效率和更快的实际运行时间收敛速度。

原作者： Buqing Ou, Frederike Dümbgen

发布于 2026-05-21

📖 1 分钟阅读☕ 轻松阅读

原作者： Buqing Ou, Frederike Dümbgen

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你试图在一片广阔且雾气弥漫的群山中找到最深的山谷，但你只能看到脚边的一小圈范围。每当你迈一步去检查地面，代价都极其高昂（就像花一百万美元进行一次测量）。这就是**贝叶斯优化（Bayesian Optimization, BO）**试图解决的现实问题：在“检查”答案的成本极其高昂的情况下，寻找问题的最佳解决方案。

本文介绍了一种名为KSOS-BO的新工具，旨在帮助你更快地找到那个山谷。以下是其工作原理的简化概念分解：

问题：“内部”谜题

在标准的贝叶斯优化中，计算机会根据目前已检查的少数昂贵数据点，构建地形的“地图”（模型）。然后，它必须决定：“我下一步该去哪里才能找到最深的山谷？”

为了做出这个决定，它使用一种称为**采集函数（Acquisition Function）**的数学公式。可以将这个公式想象成一个指向最有希望之处的“指南针”。然而，这个指南针很棘手。它通常充满了虚假的山峰和隐藏的山谷（在数学上，它是“非凸”且“多模态”的）。

通常，计算机会尝试使用标准方法来寻找该指南针的最佳位置，例如随机猜测（Sobol 搜索）或进化群（如 CMA-ES 或差分进化）。想象一下，试图通过在地图上投掷飞镖或派遣一群蚂蚁四处游荡，来在雾气弥漫的森林中找到最高的山峰。这种方法虽然有效，但可能缓慢且低效，尤其是当地形非常复杂时。

解决方案：KSOS-BO（“智能建筑师”）

作者提出了KSOS-BO，它改变了计算机解决上述“内部谜题”（即寻找下一个最佳位置）的方式。

KSOS-BO 不像只是投掷飞镖或派遣蚂蚁那样行动，它更像是一位智能建筑师，利用一种名为**核平方和（Kernel Sum of Squares, KernelSOS）**的特殊数学技术，构建地形的 3D 模型。

采样：首先，它采集有限数量的样本（就像在特定点拍摄地形照片）。
构建模型：它不仅仅是连接这些点，而是利用一种复杂的数学框架（半定规划）来构建整个景观的平滑、结构化的“代理”模型。这就像利用那几张有限的照片，通过强大的算法重建整个山脉，并确保模型尊重现实世界的平滑性。
搜索：一旦构建出这个平滑模型，计算机就不需要盲目地四处游荡了。它可以数学上“求解”该模型，以确定下一步绝对最佳的位置。

类比：寻宝游戏

标准方法（CMA-ES, Sobol）：想象你在寻找埋在田野里的宝箱。你派出一群人随机奔跑。如果他们发现一个看起来不错的地方，就告诉其他人聚集到那里。这虽然有效，但如果那个“好地方”只是一个从远处看像山的小土丘，你可能会错过宝箱。
KSOS-BO：想象你派出几名侦察兵拍摄照片。然后，你利用超级计算机根据这些照片构建整个田野的完美、平滑的全息图。接着，你可以观察全息图，并通过数学计算精确地找出宝箱的位置，而无需再派人四处奔跑。

论文发现

作者在 15 种不同类型的困难地形（有些有许多虚假山峰，有些具有平滑曲线，有些则有陡峭的落差）上，将这种新的“智能建筑师”与旧的“随机奔跑者”和“蚂蚁群”进行了测试。

胜利：KSOS-BO 在15 次测试中的 10 次中获胜。它比其他方法更快找到了更优的解决方案。
速度与成本：构建 3D 全息图（KSOS 模型）每一步所需的计算能力比仅仅运行几只蚂蚁要多。然而，由于全息图如此精确，KSOS-BO 所需的总步数更少就能找到宝箱。
结果：尽管每一步的成本更高，但找到解决方案的总时间实际上更快（在它获胜的测试中，平均快了约 93%）。它能更快地达到高质量的解决方案。
局限性：该方法并非完美。如果地形有极其陡峭的悬崖或完全平坦的高原（像巨大的煎饼），平滑的全息图难以捕捉这些尖锐的细节，此时该方法的表现不如标准奔跑者。

总结

KSOS-BO是一种优化昂贵问题的新方法。它不是盲目地搜索下一个最佳点，而是利用少量数据点构建一个智能的、数学结构化的问题景观模型。这使得它能够“看清”问题的全局结构，并以高精度选择最佳的下一步。虽然计算每一步的成本略高，但由于需要更少的昂贵实验就能找到最佳答案，它在总体上节省了巨大的时间。

技术摘要：KSOS-BO：通过核平方和改进贝叶斯优化中的采样

问题陈述
贝叶斯优化（BO）是全局优化昂贵黑盒函数的标准框架，广泛应用于超参数调优、机器人技术和科学设计。BO 过程包含两个步骤：拟合代理模型（通常为高斯过程）和优化采集函数以选择下一个查询点。尽管大量研究集中于改进代理模型和采集函数设计，但采集函数本身的优化仍是一个关键瓶颈。在实践中，该内层优化问题通常是非凸的、多峰的且高维的。现有的无导数优化器（例如差分进化、CMA-ES、Sobol 搜索）往往将其视为通用的黑盒问题，未能显式利用采集景观的结构化特性。因此，这些方法容易陷入局部最优，或需要过多的评估才能找到高质量候选点，从而限制了 BO 过程的整体效率。

方法：KSOS-BO
作者提出了KSOS-BO，这是一种专为优化采集函数而设计的基于核的无导数框架。该方法将**核平方和（KernelSOS）**方法适配到 BO 设定中。

公式化：核心思想是将采集函数 $\alpha(x)$ 的最小化问题重构为一个全局优化问题，旨在寻找最大的下界 $c$ ，使得对于定义域内的所有 $x$ ，都有 $\alpha(x) - c \geq 0$ 。
核松弛：与局限于多项式目标函数的经典平方和（SOS）方法不同，KSOS-BO 利用再生核希尔伯特空间（RKHS）。它用核函数替代了有限维多项式基。非负性约束被松弛为一个涉及由有限采样点集导出的核矩阵 $K$ 的半定规划（SDP）。
优化与恢复：该算法求解一个 SDP，以找到移位后采集函数的基于核的代理表示。它不是在输入空间中直接优化，而是将连续候选点 $x^*$ 恢复为采样点的加权组合。这使得该方法能够仅利用函数评估执行结构化的全局搜索。
集成：在每次 BO 迭代中，KSOS-BO 采样点以评估当前的采集函数，构建 KernelSOS 代理，求解 SDP 以找到下一个候选点，并更新 BO 模型。

主要贡献

结构化全局搜索：本文介绍了 KernelSOS 在采集优化中的新颖应用，超越了通用的黑盒搜索，利用由高斯过程代理诱导的采集景观的平滑、结构化特性。
无导数框架：该方法无需梯度即可运行，使其与标准的无导数设置兼容，同时为基于启发式群体的搜索提供了原则性的替代方案。
性能提升：作者证明，尽管由于 SDP 步骤导致每次迭代的计算成本更高，但 KSOS-BO 通过以更少的采集评估达到高质量解，实现了更快的墙钟时间收敛。

实验结果
作者在 10 维空间中，针对 15 个具有不同景观特性（多峰、碗状、谷状、平台状和陡峭下降）的基准函数，将 KSOS-BO 与三种无导数基线（Sobol 搜索、差分进化和 CMA-ES）进行了评估。

遗憾值改进：KSOS-BO 在15 个基准中的 10 个上取得了最佳性能。在这些表现最佳的函数上，与次优优化器相比，其平均遗憾值改进了81.16%。
墙钟时间效率：尽管 KSOS-BO 每次迭代的计算开销更高，但其在真实时间中的收敛速度更快。在其排名前十的 10 个基准上，其平均墙钟时间改进了93.55%，实际上将达到与基线相同精度所需的时间减半。
景观敏感性：该方法在多峰函数（如 Ackley、Rastrigin、Griewank）和平滑单峰函数（如 Rosenbrock、Dixon Price）上表现卓越。然而，在具有极端曲率、陡峭下降或平台状区域的函数（如 Michalewicz、Zakharov、Styblinski Tang）上，性能有所下降，因为基于核的表示被认为不够充分。
鲁棒性：消融研究表明，KSOS-BO 对初始设计大小、评估预算和核选择（高斯核与拉普拉斯核）的变化具有鲁棒性，尽管它在大多数测试用例中始终优于基线。

意义与主张
本文主张，仅增强采集优化步骤即可带来可测量的整体贝叶斯优化性能提升。其主要意义在于证明，将采集优化视为可通过 KernelSOS 松弛解决的结构化问题，优于将其视为通用黑盒问题。

作者谦逊地指出，虽然 KSOS-BO 对多样化的景观结构有效，但它并非万能解决方案；它在处理陡峭下降或平坦平台等特定几何特征时存在困难。此外，该方法引入了计算权衡：SDP 步骤比标准进化策略更昂贵，但这一成本因减少了找到最优解所需的昂贵函数评估次数而得到补偿。这项工作表明，未来的方向应集中于提高 KSOS-BO 的可扩展性，探索与局部细化相结合的混合策略，并在更高维或受约束的设置中进行测试。

问题：“内部”谜题

解决方案：KSOS-BO（“智能建筑师”）

类比：寻宝游戏

论文发现

总结

类似论文