1. 项目概述当优化预算捉襟见肘时在超参数调优、机器人控制器设计、新材料配方探索这些实际工程问题里我们常常会面对一个共同的困境目标函数就像一个封装严密的“黑盒”。你只能给它输入一组参数然后得到一个输出结果比如模型的准确率、机器人的行走距离、材料的强度但你完全不知道这个函数内部长什么样——它不可导、非凸、甚至充满了噪声。这就是黑盒优化的核心场景。传统的优化方法比如梯度下降在这里完全失效因为你连梯度都算不出来。那么我们如何高效地“摸索”出这个黑盒函数的最优解呢一个主流且强大的思路是贝叶斯优化。它通过一个概率代理模型通常是高斯过程来建模我们对未知函数的认知并利用一个采集函数如期望改进EI来智能地决定下一个评估点应该选在哪里以此平衡“探索”未知区域和“利用”已知好区域。然而贝叶斯优化有一个“阿喀琉斯之踵”它的计算开销会随着已评估点的数量增加而急剧增长构建和更新高斯过程模型本身就需要不小的成本。更重要的是在许多现实场景中对目标函数进行一次评估的代价极其高昂——可能是需要训练一个大型神经网络数小时也可能是进行一次昂贵的物理实验。我们能负担得起的评估次数可能只有几十次到几百次。这就是所谓的低预算优化问题。在低预算的严苛限制下标准的贝叶斯优化策略可能会“失灵”。有限的样本点可能不足以让一个全局代理模型准确捕捉到复杂的函数形态尤其是在多峰有多个局部最优或高维空间中。算法很容易陷入一个局部最优区域或者因为探索不足而错过全局最优解。SPBOpt算法正是为了解决这一痛点而诞生的。它的核心思想非常直观且巧妙既然用一个模型去拟合整个复杂的空间在样本不足时很困难那我们为什么不把空间“分而治之”呢SPBOpt全称 Search Partition for Bayesian Optimization直译过来就是“通过搜索空间分区进行贝叶斯优化”。它不再试图用一个全局模型去覆盖一切而是将整个搜索空间动态地划分成若干个子区域然后在每个子区域内独立地运行一个“局部”的贝叶斯优化器。随着评估的进行算法会根据各区域的“表现”自适应地调整分区在表现好的区域进行更精细的划分投入更多搜索资源而逐渐放弃那些表现不佳的区域。这种策略在NeurIPS 2020黑盒优化挑战赛的严格预算仅128次评估下大放异彩最终获得了第三名的成绩证明了其在低预算场景下的强大竞争力。简单来说SPBOpt就像一位经验丰富的矿藏勘探队长。面对一片广袤而未知的矿区搜索空间他手头只有极其有限的钻探次数评估预算。他不会漫无目的地到处打孔而是会先将矿区划分成几个大区块在每个区块内进行初步的密集勘探局部BO。根据每个区块初步勘探出的矿石品位函数值他决定将后续宝贵的钻探资源集中到最有希望的1-2个区块甚至在这些区块内进行更小网格的细分和深入勘探同时果断放弃那些贫瘠的区块。通过这种“分区勘探聚焦资源”的策略他能在有限的钻探次数内最大概率地找到主矿脉。2. SPBOpt核心思路与工作流程拆解2.1 为何要分区——低预算下的效率困境与破局点要理解SPBOpt首先要明白标准贝叶斯优化在低预算下为何会“力不从心”。假设我们的搜索空间是一个边长为1的二维正方形而全局最优解只是这个正方形中一个非常小的“尖峰”。在只有几十次评估的机会下如果均匀地随机采样命中这个尖峰的概率极低。如果使用标准的贝叶斯优化其采集函数如EI在初期会倾向于探索未知区域这可能导致早期的评估点分散在空间的各个角落。由于样本点太少且分散高斯过程模型无法在任何局部形成准确的预测其给出的不确定性估计和均值预测都可能偏差很大从而误导后续的搜索方向。它可能过早地被一个“看似不错”的局部最优吸引而错过了真正的全局最优。SPBOpt的分区策略正是为了打破这个僵局。它将全局的“探索-利用”权衡分解为两个层次区域间的探索通过初始分区确保搜索覆盖到空间的不同部分避免早期搜索完全遗漏某些区域。区域内的利用在每个子区域内由于空间范围变小局部贝叶斯优化器可以用相对更少的样本快速建立相对准确的局部模型从而高效地在该区域内进行精细搜索寻找局部最优。这种分层策略带来几个关键优势提升局部建模精度在缩小的子空间内函数的形态可能更简单例如更接近线性或二次型局部高斯过程模型更容易用少量数据拟合准确。并行与模块化潜力各个子区域的优化过程理论上是独立的这为并行计算提供了天然的可能性虽然SPBOpt论文中并未强调并行实现但这是一个重要的工程扩展方向。自适应资源分配这是SPBOpt最精髓的部分。算法并非静态分区而是根据反馈动态调整。表现好的区域会被进一步细分获得更多的评估预算表现差的区域则可能被合并或直接忽略。这实现了预算的“按需分配”将好钢用在刀刃上。2.2 算法工作流程四步走SPBOpt的主体流程可以清晰地划分为四个核心步骤形成一个迭代循环直到评估预算耗尽。我们结合NeurIPS 2020挑战赛的具体设定总预算K×B128次评估其中K16轮每轮B8个候选点来具体说明。2.2.1 步骤一搜索空间分区这是算法的起点和后续自适应调整的基础。初始时我们需要将整个定义域Ω划分成多个子区域。如何划分论文中并未明确指定必须使用的方法这给了实践者灵活选择的空间。常见且合理的策略包括均匀网格划分最简单直接。例如在d维空间中沿着每个维度进行等分。这种方法实现简单能保证初始的全局覆盖但可能不够智能在函数变化平缓或剧烈的区域都采用同样的粒度。基于树的划分如KD-Tree或随机划分树。这种划分方式可以生成大小不一的区域并且便于后续的递归细分。例如可以随机选择维度进行划分使得初始分区具有一定的随机性有助于增加探索的多样性。基于已有数据的聚类划分如果有一些先验的评估数据哪怕很少可以根据这些数据点的分布进行聚类将空间划分为数据密度不同的区域。实操心得在完全无先验信息的场景下我推荐使用基于树的随机划分作为起点。它既保证了划分的随机性有助于探索又具有结构化的特点便于后续的细化和合并操作。初始分区的数量不宜过多通常与总评估预算的平方根成正比是一个经验法则。对于128次的总预算初始划分为4-8个区域是比较合理的这样每个区域在初期都能获得一定数量的评估机会。2.2.2 步骤二子区域内的局部贝叶斯优化分区完成后算法会为每一个子区域初始化一个独立的局部贝叶斯优化器。这个局部BO与全局BO在原理上完全一样都包含代理模型高斯过程和采集函数。但关键区别在于它的“视野”被限制在了当前的子区域内。在每一轮迭代中每个局部优化器会基于自己区域内已有的评估数据运行一次标准的贝叶斯优化流程用该区域内的数据拟合一个局部高斯过程模型。基于该模型和采集函数如EI、PI或UCB计算出一个或多个在该子区域内“最有希望”的候选点。这里有一个重要的设计选择每轮每个区域产生多少个候选点在NeurIPS 2020挑战赛的设置中每轮总共要提出B8个候选点。一个自然的策略是平均分配例如如果有4个区域则每个区域产生2个候选点。但更高级的策略可以是根据区域的历史表现进行加权分配表现好的区域获得更多的“提案权”。2.2.3 步骤三候选点评估与数据聚合所有子区域产生的候选点会被收集到一个全局的候选池中。然后算法会使用真实且昂贵的目标函数f(x)来评估这个候选池中的所有点。这是算法中唯一消耗评估预算的环节。评估完成后这些新的(x, f(x))数据点会被分别添加到其所属子区域的局部数据集中用于更新该区域的局部代理模型。同时它们也会被纳入一个全局的数据库中用于跟踪当前找到的最优解。2.2.4 步骤四分区的自适应更新这是SPBOpt的“智能”所在也是其区别于静态分区方法的核心。在获得新一轮的评估反馈后算法需要决定如何调整分区结构以更好地分配未来有限的评估预算。更新的策略通常基于各区域的“表现”什么是区域的表现一个直观的度量是该区域历史最佳函数值或者该区域最近几次评估的平均改进程度。区域内的样本点质量越高该区域就越“有希望”。如何更新分区细化对于表现最好的一个或几个区域算法会将其进一步细分。例如将一个区域沿着某个维度一分为二。这相当于在该有希望的区域投入更多的搜索“分辨率”进行更精细的挖掘。保持对于表现中等的区域可能保持其当前划分不变继续观察。舍弃/合并对于持续表现很差的区域算法可能会选择将其“关闭”——不再在该区域内部署局部优化器或者将其与相邻区域合并。这相当于将宝贵的评估预算从“贫矿”中撤出重新分配到更有希望的地方。这个过程循环往复K16轮。随着轮次的增加搜索资源会越来越集中到那些被证明包含高质量解的子空间上实现了从广泛探索到精细利用的自然过渡。3. 关键实现细节与参数选择3.1 分区策略的具体实现分区策略是SPBOpt的骨架其实现方式直接影响算法性能。基于树的结构如二分树是一个非常适合的选择因为它天然支持细化和可能的合并操作。初始化假设我们采用一个简单的随机二分树。初始时整棵树只有一个根节点代表整个搜索空间Ω。我们设定一个初始深度init_depth例如2然后递归地将每个节点区域随机选择一个维度并在该维度的中点进行分割直到达到设定的深度。这样我们会得到大约2^init_depth个叶子节点每个叶子节点对应一个初始的子区域。区域表现评估我们需要一个量化指标来决定哪个区域值得细化。一个有效的指标是区域改进概率。对于区域R我们可以计算score(R) (f_best_global - f_best_R) / (f_best_global - f_worst_global)其中f_best_R是区域R内历史最佳值f_best_global和f_worst_global分别是全局历史最佳和最差值或最近几轮的最佳最差。这个分数经过归一化越小的score(R)区域最佳值越接近全局最佳值意味着该区域表现越好。另一种更鲁棒的方法是使用该区域所有点的平均排名或中位数性能。细化操作每一轮结束后我们选择score最好的前M个区域例如M1或2进行细化。细化操作就是将该区域对应的叶子节点进行分裂随机选择一个维度在中点处分割生成两个新的子节点子区域。原区域的数据会根据点的坐标分配给这两个新的子区域。然后为每个新的子区域初始化一个新的、空的局部贝叶斯优化器。合并/舍弃操作对于持续表现很差的区域例如连续几轮score都排在最末且其最佳值远差于全局最佳值我们可以将其“休眠”。一种简单的实现是在分配每轮候选点提案名额时不给这些区域分配名额或者分配极少的名额如每5轮才允许提一个点。更激进的做法是直接删除该区域节点并将其数据合并到父节点或相邻兄弟节点中。注意事项分区不宜过细过快。如果过早地将空间分割成大量微小区域每个区域内的数据点会非常稀疏导致局部贝叶斯优化器无法建立有效模型退化为随机搜索。一个实用的启发式规则是确保每个活跃区域在每次被允许提案时其内部已有的数据点数量至少是维度的2-3倍否则应暂缓对该区域的进一步细分。3.2 局部贝叶斯优化器的配置每个子区域内的局部BO是算法的工作引擎。其配置需要针对低预算、小范围搜索的特点进行优化。代理模型高斯过程仍然是首选。其核函数的选择至关重要。在低数据量下马顿核通常比径向基函数核更稳定因为它对超参数不那么敏感且能产生更平滑的插值。核函数的长度尺度参数可以设置得相对较小以反映我们对“局部”空间内函数平滑度的假设。采集函数期望改进是经典且可靠的选择。在局部搜索中我们更关注“利用”因此也可以考虑概率改进。如果希望保留一定的探索性上置信界也是一个选项。由于局部空间较小采集函数的优化过程即寻找使得采集函数值最大的x可以做得相对精细一些例如使用多起点的局部优化算法。并行提案在NeurIPS挑战赛设置中每轮需要批量提出B8个点。局部优化器需要支持批量提案。常用方法有贪心序列化用已选点更新模型后再选择下一个点。使用批量采集函数如q-EI直接优化一组点的联合改进期望。蒙特卡洛采样从采集函数分布中采样多个点。 在SPBOpt的上下文中由于每个区域提案数量不多通常1-3个采用贪心序列化是一个在效果和复杂度之间很好的折中。3.3 超参数与预算分配SPBOpt本身引入了一些新的超参数需要仔细设置初始分区数量/深度如前所述建议与总预算的平方根成正比。对于128次评估4-8个初始区域是合理的起点。每轮候选点总数B这是由问题设定或评估并行能力决定的。B越大并行度越高但每轮对模型的更新跨度也越大。8-16是一个常见的范围。分区更新频率并非每一轮后都必须更新分区。可以每2-3轮更新一次给区域内的局部BO一些时间“热身”和积累数据。细化区域数量M通常每轮只细化1个表现最好的区域避免分区数量爆炸式增长。区域提案权分配如何将每轮B个提案名额分配给各个区域以按区域表现的softmax分布进行分配也可以采用“表现最佳区域获得固定名额如2个其余名额在其他区域平均分配”的混合策略。一个参考的配置方案如下表所示超参数建议值/策略说明初始分区方法随机二分树实现简单易于后续细化初始深度2产生约4个初始区域局部代理模型高斯过程马顿核低数据量下更稳定局部采集函数期望改进经典可靠侧重利用分区更新轮次间隔2每2轮评估后更新一次分区每轮细化区域数(M)1只细化当前最佳区域区域提案权分配混合策略最佳区域得2票其余区域平分剩余票数区域舍弃阈值连续3轮排名最后且差距20%避免过早舍弃设置保守阈值4. 实战模拟一个二维多峰函数的优化之旅为了更直观地理解SPBOpt是如何工作的让我们设想一个简单的二维测试函数例如六驼峰函数。这个函数在定义域[-3, 3]^2内有六个局部极小值点其中一个为全局最小。我们的评估预算非常紧张只有30次。4.1 迭代过程推演第0轮初始化分区将整个[-3, 3]^2空间通过随机二分树划分为4个大小相等的子区域R1(左上)、R2(右上)、R3(左下)、R4(右下)。局部BO初始化为每个区域初始化一个局部高斯过程模型目前都没有数据。第1-2轮局部提案由于所有区域都没有数据局部BO退化为在各自区域内随机采样。假设每轮每个区域产生1个点两轮后每个区域有2个评估点。评估与聚合评估这8个点得到函数值。分区更新第2轮后计算各区域的最佳值。假设R3左下区域内的某个点偶然落在了全局最优解所在的“洼地”附近取得了目前最好的函数值。因此算法决定细化R3区域将其一分为二变为R3a和R3b。现在总共有5个活跃区域。第3-5轮局部提案现在R3a和R3b会继承原R3的数据并开始独立的局部搜索。其他区域继续搜索。提案名额分配向R3a和R3b倾斜。评估与聚合新的评估点可能进一步确认R3a假设包含全局最优的潜力而R1、R2、R4区域的最佳值改善缓慢。分区更新第4轮后R3a区域表现持续优异被进一步细化分裂为R3a1和R3a2。同时表现最差的R2区域可能被标记为“低优先级”减少其提案权重。现在有6个活跃区域但资源明显向左下角聚集。第6-10轮及以后搜索资源持续向以R3a1、R3a2为核心的“潜力区”集中。这些区域内的局部BO由于数据点相对密集能够越来越准确地建模局部函数形态从而高效地定位极小值点。其他区域如R1、R4可能还会得到零星评估以防万一但主要作用已转变为“探索保障”。在预算耗尽前算法很可能已经在R3a1或R3a2中利用局部BO找到了全局最优解的一个高质量近似。4.2 与标准贝叶斯优化的对比如果我们在同样的30次评估预算下运行标准全局贝叶斯优化初期采集函数如EI会倾向于在全局范围内探索前10个点可能分散在整个空间。中期由于函数是多峰的早期分散的点使得高斯过程模型对整个空间的拟合非常粗糙。模型可能会被某个非全局的局部极小值区域比如R2里的一个洼地产生的“好”点所误导后续提案开始向那个区域集中。后期当算法“醒悟”过来那个区域可能不是最好时评估预算已经所剩无几没有足够的机会再去探索其他区域比如左下角的真正全局最优区域。而SPBOpt通过强制性的初始分区保证了早期评估点覆盖了空间的不同部分探索。又通过自适应细化迅速将资源聚焦到最早显示出希望的R3区域利用。这种结构化的搜索策略在低预算、多峰场景下比全局BO的“自由探索”更具鲁棒性和导向性。5. 优势、局限与适用场景5.1 SPBOpt的核心优势低预算下的样本高效性这是其设计的首要目标。通过分区和局部建模它用有限的样本在局部获得了更准确的模型从而做出了更明智的搜索决策。探索与利用的显式平衡分区机制在算法层面清晰地分离了“探索不同区域”和“利用区域内部”这两个任务并通过自适应更新来实现动态平衡。对多峰函数的鲁棒性由于同时维护多个区域的搜索算法不易陷入单一的局部最优陷阱。即使一个区域陷入了局部最优其他区域仍有发现更好解的机会。算法框架的通用性与可扩展性SPBOpt是一个元框架。其内部的局部优化器可以替换如换成不同的采集函数、甚至非BO的局部搜索器分区策略也可以定制。这为针对特定问题领域的改进提供了空间。5.2 潜在局限与挑战维度灾难的缓解而非解决分区策略在一定程度上缓解了高维问题但并未根除。在非常高维的空间中例如50维有意义的空间划分会变得极其困难子区域的数量可能呈指数增长。SPBOpt更适用于中低维度例如2-20维的问题。超参数敏感性初始分区数量、更新频率、细化策略等超参数需要根据问题进行调整。不合理的设置可能导致分区过早收缩或一直无法聚焦。计算开销增加需要维护多个局部代理模型和分区树结构这比单个全局模型带来额外的内存和计算成本。虽然评估函数的成本是主导但在一些极端情况下这种开销也需要考虑。边界区域的处理当最优解恰好位于分区边界时可能会被两个区域共享导致搜索效率下降。需要在分区设计或区域合并时考虑重叠或缓冲机制。5.3 典型适用场景基于其特点SPBOpt特别适合以下场景评估预算极其有限 200次例如自动化机器学习中的超参数调优训练一次模型需要数小时。目标函数可能是多峰的存在多个局部最优需要避免早熟收敛。问题维度属于中低范围2-20维在这个维度区间空间划分具有可操作性。需要可解释的搜索过程分区结构本身提供了一种搜索过程的可视化解释可以看到算法如何将资源聚焦。个人体会在实际工程中应用类似SPBOpt的思想时我最大的收获是不要迷信“全局”模型。当数据少得可怜时一个试图覆盖整个复杂空间的模型往往力不从心其预测远不如多个专注在小范围内的“专家”模型可靠。这种“分治”思想不仅适用于贝叶斯优化在很多数据稀缺的建模场景中都值得借鉴。另外自适应的资源分配逻辑——即根据实时反馈动态调整搜索重点——是这类算法成功的关键它模仿了人类解决问题时“大胆假设小心求证重点突破”的思维模式。6. 总结与扩展思考SPBOpt算法为低预算黑盒优化问题提供了一个简洁而有力的解决方案。它没有使用特别复杂的数学模型其力量来自于一个朴素而有效的理念在资源受限时将大问题分解为小问题并智能地分配资源。通过搜索空间的自适应分区与局部贝叶斯优化的结合它在NeurIPS 2020 BBO挑战赛等基准测试中证明了其卓越的性能。对于想要复现或应用此算法的实践者我的建议是从简单的分区策开始先实现一个固定的网格划分或随机二分树确保核心流程分区-局部BO-评估-更新跑通。重点关注自适应逻辑这是算法的“大脑”。花时间设计并调试区域表现评估指标和分区更新细化/舍弃的条件这通常对最终效果影响最大。局部BO不必过于复杂在低预算下局部BO的核函数和采集函数选择标准配置即可。稳定性比尖端性更重要。可视化是你的朋友对于中低维问题务必实现搜索过程的可视化。观察分区如何演变、评估点如何分布是理解算法行为和调试参数的最直观方式。最后SPBOpt也为我们打开了思路。它的框架可以进一步扩展例如异构局部优化器不同的区域可以根据其特性如平滑度、噪声水平使用不同类型的局部搜索器。基于机器学习的分区策略是否可以用一个轻量级模型来预测哪些分区方式更有效与元学习结合能否从大量类似的历史优化任务中学习到一个好的初始分区策略或区域表现评估器在计算资源日益宝贵、实验成本高昂的今天像SPBOpt这样致力于在“紧巴巴”的预算下榨取每一分性能的算法其价值和生命力将会持续凸显。