20201107 OR Talk NO 19 Facebook田渊栋博士：基于蒙特卡洛树搜索的隐动作集黑盒优化

开源库与黑盒优化基础

本次讲座的核心内容围绕黑盒优化展开，旨在解决那些无法获取导数信息、仅能通过函数调用获取数值的复杂优化问题。为了便于社区使用，团队已将相关算法代码开源，用户可以通过扫描二维码或访问网站直接试用该库。黑盒优化的基本逻辑是：面对一个未知的函数 $f$，算法通过多次调用获取输出值，并基于这些反馈数据决定下一步的搜索方向，从而以最小的代价逼近最优解。这种技术在旅行商问题（TSP）、作业调度、蛋白质折叠等 NP-hard 问题中具有广泛应用，因为这类问题在最坏情况下需要指数级时间才能找到精确解。传统的深度学习和强化学习方法试图将优化问题转化为序列决策问题，利用神经网络的泛化能力来预测下一步动作，以期在相同时间内获得比常规求解器更优的解。然而，不同问题的具体特性差异巨大，需要针对每个问题进行具体分析，没有通用的定论。

行动空间对搜索效率的决定性影响

与围棋等游戏不同，优化问题的行动空间并非固定不变。在围棋中，每一步只能在固定的361个交叉点中选择，行动空间是离散且明确的；而在高维空间的优化问题中，可选的行动路径（如直线、绕路等）极其庞大且难以想象。讲座指出，行动空间的设计直接决定了搜索效率。以往的研究多采用人工设计的固定行动空间，例如在神经架构搜索（NAS）中，通过RNN逐层生成卷积层的参数；或在TSP中，根据当前城市选择最近邻的下一个城市。然而，这些方法忽略了行动空间本身也可以被优化这一关键点。如果行动空间设计不当，搜索过程可能会在大量低效的分支中徘徊。因此，核心创新在于自动学习隐式的行动空间（Latent Action Space），通过更合理的空间切分来加速收敛。

隐动作集实验：Sequential vs Global

为了验证行动空间设计的重要性，团队在神经架构搜索中进行了对比实验。搜索空间被简化为三个参数：深度（5种选择）、通道数（2种选择）和卷积核大小（2种选择），形成有限的网络结构组合。实验对比了两种行动空间策略：

1. Sequential Action Space：模仿Google的方法，逐层添加网络层，每层同时决定kernel size和channel数。这种策略将决策分散在每一步，导致搜索树中好坏节点分布杂乱。
2. Global Action Space：首先决定整个网络的深度，然后再决定每一层的具体参数。这种策略将最重要的决策（深度）前置。

实验结果清晰地展示了两种策略在搜索效率上的巨大差异。随着样本数的增加，Global策略能更快地提升最优准确率。这是因为在Global策略下，好的区域和坏的区域在搜索树中分布更为规整，算法可以迅速剪枝掉表现差的深度分支，而在表现好的分支中继续深入探索。相反，Sequential策略中，即使某一层参数选择较差，后续层仍可能通过调整参数弥补，导致“好点”和“坏点”在树中交错分布，增加了搜索难度。

隐动作集的理论基础与算法思路

讲座进一步从理论层面解释了为何不同的行动空间会导致不同的搜索性能。以井字棋为例，每一步决策实际上是将剩余的游戏结果空间进行切分。在优化问题中，这种切分方式不是固定的，而是可以通过学习获得的。行动空间的定义本质上是对搜索空间的切分策略。在Sequential策略中，由于每一步只切分局部参数，导致搜索树中相邻节点的性能差异可能很大，且好坏区域混杂。而在Global策略中，第一步切分（如决定深度）往往能根据直觉或初步评估，将空间划分为“高潜力”和“低潜力”两个大块。这种值函数分布的规整性使得蒙特卡洛树搜索（MCTS）能够更有效地利用探索与利用的平衡，将计算资源集中在高潜力区域。因此，通过学习隐动作集，算法能够自动找到最优的切分方式，从而在复杂的黑盒优化问题中实现更高的搜索效率。这一思路不仅适用于神经架构搜索，也为其他高维优化问题提供了新的解决视角。

隐动作集黑盒优化的核心逻辑：动态切分设计空间

该研究的核心在于将神经网络架构搜索（NAS）中的“行动空间”（Action Space）定义为对高维设计空间的动态切分。传统的搜索往往在固定空间内盲目尝试，而本方法通过蒙特卡洛树搜索（MCTS）将设计空间不断划分为“好”与“坏”两个子区域。每一次切分都基于当前已知的性能数据，旨在将表现优异的节点聚集在同一个叶节点（Leaf Node）中。这种切分方案并非静态，而是随着搜索过程的深入动态调整和学习。通过迭代地生成新的切分方案，算法能够更精准地定位高性能架构所在的区域，从而提升搜索效率。

“我们每次把这个 design space 切成好的和坏的两块……这个切分的方案呢，其实在整个的搜索过程中呢，是可以动态的去调整去学习的。”

为了实现这一目标，算法采用交替进行的两个步骤：首先随机采样并训练以初步划分行动空间，随后利用MCTS在该空间内搜索有希望的节点；接着，利用新发现的数据重新训练行动空间的定义，优化切分边界，再回到MCTS搜索阶段。这种迭代机制确保了行动空间始终贴合当前搜索进展，使得最终切分出的区域具有更高的纯度，即叶节点内的神经网络子集整体表现良好。

行动空间的学习策略：从线性到非线性边界

在行动空间的定义上，研究首先介绍了一种简单的线性方案，这属于机器学习的基础概念。假设行动空间由宽度、深度及每层决策数目等参数组成，算法可以通过这些参数与性能（Performance）之间的关系，在参数空间中切一刀，将好结构与坏结构分离。例如，沿性能提升最快的方向进行切割，使得一侧为优质结构，另一侧为劣质结构。这种线性切分虽然简单，但为后续的非线性扩展奠定了基础。

为了提升搜索精度，研究进一步将线性切分拓展为非线性边界。具体做法是先对数据进行聚类，将好坏样本初步分组，然后使用支持向量机（SVM）训练出一个非线性的决策边界。这个非线性边界能够更灵活地包裹住高性能架构所在的复杂区域，从而更精确地定义行动空间。通过这种从线性到非线性的演进，算法能够适应更复杂的设计空间结构，并在迭代中不断优化切分效果，确保MCTS搜索时能更有效地聚焦于潜在的最优解区域。

蒙特卡洛树搜索（MCTS）在探索与利用间的平衡

引入MCTS的主要目的是解决探索（Exploration）与利用（Exploitation）的平衡问题。在实际应用中，由于样本不足，初始切分可能导致算法误判。例如，左侧区域样本表现尚可但无最优解，右侧区域整体糟糕但隐藏着一个全局最优解（Optimal Solution）。如果仅基于当前均值判断，算法会倾向于持续探索左侧，从而错失右侧的潜在最优解。

MCTS通过维护一棵搜索树来解决此问题，其核心在于UCB（Upper Confidence Bound）准则，具体实现为PUCT算法。该算法在每一步决策时，既考虑历史胜率（利用），也考虑节点访问次数（探索）。对于访问次数较少的节点，即使当前胜率不高，算法也会保留探索的权利，因为未被充分探索的区域可能隐藏着更好的解。

“如果我没有任何的 exploration，没有任何探索，我会觉得我就一直往左边探索就行了……那么这样的话，你就会失去这个找到 optimal 的机会。”

每次搜索完成后，算法通过回溯（Back Trace）更新节点的胜率和访问次数，从而动态调整后续搜索策略。这种机制确保了算法不会过早收敛于局部最优，而是能在保证利用已知好解的同时，持续探索未知区域，最终在重新定义行动空间后，更有可能发现全局最优架构。

子区域采样策略与高斯过程拟合的优势

在MCTS的每个节点（对应一个子区域）进行扩展时，需要在该区域内采样以进一步切分。研究提供了三种采样策略： 1. 线性约束采样：利用线性切分形成的多面体（Polytope）结构，通过特定算法高效采样。 2. 拒绝采样（Reject Sampling）：在一个包含目标区域的大区域内随机采样，然后剔除不满足所有父节点约束的点。该方法简单但需要一个初始种子点。 3. 高斯过程（Gaussian Process, GP）拟合：在子区域内拟合一个高斯过程函数，通过寻找函数的最大值来指导采样。

“因为这个区域比较小啊，所以你用高线 process 来那个 fit 这个区域呢，其实是比较容易的。”

高斯过程拟合具有显著优势：首先，子区域小意味着拟合所需的样本量呈指数级下降，避免了在全局大空间拟合的高成本；其次，GP拟合的是区域的最大值预测，这与搜索最优解的目标一致，而非仅关注平均值；最后，GP的计算复杂度通常随样本量呈平方或立方增长，但由于每个子区域内的点数量有限（点多则分裂），因此不会遇到大规模矩阵求逆的性能瓶颈。这种权衡使得GP在小区域优化中成为高效且准确的选择。

实验结果：NASNet搜索与黑盒优化性能对比

该算法在神经网络架构搜索（NAS）和黑盒优化任务中展现了优异性能。在NASNet搜索空间中，算法通过自动设计Normal Cell和Reduction Cell的结构，在极少的样本量下实现了高精度的分类准确率。实验结果显示，该方法在搜索初期就能迅速提升性能，优于多种基线算法。

在CIFAR-10数据集上的实验进一步验证了其效率。使用黑盒表示的算法在仅进行约800次搜索的情况下，达到了极低的Top-1错误率。这一搜索次数远低于其他对比方案，证明了动态行动空间定义的高效性。此外，在ImageNet压缩任务中，该方法同样保持了低错误率，展现了泛化能力。

在Win-Shot方法的改进实验中，研究引入简单的值函数替代完整的网络训练过程，以节省大量GPU时间。虽然估计精度略低于完整训练，但搜索效果依然良好。这种方法在大幅降低计算成本的同时，保持了较高的搜索质量，证明了该框架在资源受限场景下的实用价值。

隐动作集搜索作为元方法：超越单一求解器

田渊栋博士提出，将蒙特卡洛树搜索（MCTS）框架视为一种元方法（Meta Method），其核心优势在于叶节点内可嵌入任意近似函数拟合器（如高斯过程）或现有求解器。实验表明，将现有求解器嵌入该框架后，其表现优于该求解器单独运行时的效果。这一现象在阿克里（Ackley）和罗斯布洛克（Rosenbrock）等具有多个局部极小值的复杂人工函数验证中尤为明显。传统优化方法易陷入局部最优，而该方法在零点附近的最优解搜索中展现出更高效率。

“我们的方法加上一个已有的 solver，在每一个节点上，它的效果呢其实是高于这个 solver 本身的。”

在高维空间（如100维）的对比实验中，实线代表采用本方法，虚线代表未采用本方法。数据显示，在高维空间中，实线的下降速度显著快于虚线，证明搜索效率更高。相比之下，传统贝叶斯优化（Bayesian Optimization, BO）在100维空间中因计算代价巨大，曲线几乎停滞，而本方法仍能保持较快的收敛速度，有效缓解了维数灾难带来的性能衰减。

高维黑盒优化与强化学习任务的性能对比

在蒙特卡洛任务中，该方法被用于优化零点策略（Zero-point Policy）的参数，而非使用传统的梯度下降。实验选取了高维问题，包括 Ant 和 Humanoid 两个环境。对比对象主要为进化算法框架及传统贝叶斯优化框架下的多种基线算法。结果显示，本方法（蓝线）在高维函数优化上的效率显著高于其他无梯度（Gradient-free）黑盒优化方法。

需要明确的是，该方法定位为无梯度（Gradient-free）方法。若与基于梯度的方案相比，基于梯度的方法通常能更快达到更优结果，因为梯度提供了明确的优化方向。然而，本方法的优势在于其不依赖梯度信息，这在目标函数不可微或梯度难以计算时至关重要。因此，所有性能对比均严格限定在无梯度黑盒优化的范畴内，以体现其在特定场景下的竞争力。

算法特性： anytime 属性与资源权衡

该算法具备 Anytime Algorithm（随时算法） 的特性，即计算资源与求解精度之间存在直接的可交换性。只要有足够的 CPU 资源和时间，算法可以持续运行，运行时间越长，结果越优。这种特性允许用户根据实际场景的需求，在求解速度和求解精度之间进行灵活权衡。对于代码调用，用户只需定义输入输出接口，即可通过简单的类封装直接调用求解器，无需复杂的配置。

“因为我们这个算法呢，其实是叫 anytime algorithm，就是说你可以一直跑下去。你可以跑到就是天荒地老，如果你你想跑多久跑多久，那么跑的越久它效果会越好。”

在应用场景上，该方法适用于所有黑盒优化背景的问题，即目标函数调用耗时且最优解未知的情形。例如，在大规模调度系统中，调整参数后需运行一天才能得知收益，此时无法计算梯度，只能依赖此类无梯度方法。此外，核函数（Kernel）的选择相对灵活，通常使用简单的线性核或高斯核即可，无需寻找极端的核函数，只要参数可调，通常都能取得良好效果。

Q&A：局部最优、高维瓶颈与梯度结合

针对局部最优问题，虽然随机搜索可能陷入局部最优，但得益于 MCTS 的性质，只要搜索时间足够长，总有机会跳出局部最优并找到全局最优解，尽管这需要较大的时间成本。关于高维优化瓶颈，传统 BO 在高维下失效的根本原因在于高斯过程（GPR）的协方差矩阵计算复杂度与点数平方成正比，且拟合高维函数需指数级样本，即维数灾难。而 Tube 算法通过在外层增加一层优化机制，每次将优化区域缩小一倍，从而在局部区域内高效优化，避免了全局高维拟合的计算爆炸，但代价是可能放弃某些区域。

“有梯度的问题是它局部很准，对吧？它可以很让很快让你到一个比较好的解，但你并不知道这个解到底有没有效果啊。也许这个解是个 local minimum，然后你又跳不出去。”

在梯度结合方面，建议先利用本方法探索空间获得大致解，再以此为基础运行梯度下降，这是一种可行的混合策略。对于 Go 或 Poker 等固定动作空间的游戏，该方法直接应用价值有限，因为动作空间已预定义，但可能适用于战术思路层面的优化。最后，神经网络架构在此框架中被广义定义为任何超参数或结构表示，而不仅仅是神经元数量或层数，这使得该方法在神经架构搜索（NAS）中具有广泛的适用性。