NIPS-2020 基于蒙特卡洛树搜索的连续优化算法 LA-MCTS

RhinoFreak

什么是蒙特卡洛树搜索？

蒙特卡洛树搜索是一种规划算法，简单来说，MCTS包含四个部分，选择->扩展->模拟->反向传播。下面将以神经网络架构搜索任务为例，阐述如何使用MCTS搜索到最佳的神经网络架构。
选择：在选择阶段，MCTS决定执行探索的区域。例如，在神经网络搜索中，我们需要决定基于哪个神经网络架构进行进一步的修改。有些神经网络架构，例如ResNet，肯定具有更高的修改价值。当然，也可能会存在VGG架构，但该架构就不如ResNet更值得被探索。精准来说，在MCTS中，ResNet架构所对应的UCB分数会比VGG架构更高，从而会被优先探索。
扩展：扩展操作决定具体的行为动作。例如，在神经网络搜索中，MCTS即可以决定增加当前架构的隐藏层，也可以决定增加现有网络最后一层的神经元数量。
模拟：模拟操作决定某个节点的分数。例如，在神经网络搜索中，我们可以对扩展之后的神经网络架构进行评估，从而得到该扩展节点的分数。
反向传播：反向传播将模拟分数反向传播会前面的节点。例如，在神经网络搜索中，我们模拟了扩展ResNet架构的分数，那么就可以反向传播回ResNet架构节点。当进行了多种扩展模拟操作之后，我们可以预估出扩展ResNet的平均值。可以预见，扩展ResNet会比扩展VGG具有更高的期望收益。


LA-MCTS算法

在上一节，我们了解了一种基础版本的蒙特卡洛树搜索算法，并直观了解了如何使用MCTS搜索神经网络架构。在这里，为了进一步加深对MCTS的理解，本节将以Facebook NIPS 2020论文《Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search》为例，阐述一下如何使用MCTS算法实现对连续优化问题的求解，即找到 的最优解 。


MCTS搜索空间构建

LA-MCTS的核心思路如下所示，节点 代表整个搜索空间。在具体的每一步，LA-MCTS在UCB最大的节点所对应的搜索空间上进行采样，并评估得到样本分数（例如神经网络架构的分数）。当该节点内的样本点数量超过 时，该样本点分裂为高质量和低质量两个区域。


MCTS的分裂过程主要包含两步：

• 首先，对于某个区域内的样本点，LA-MCTS将样本点 使用K-Means进行聚类，划分成高质量和低质量两个区域。
  
• 随后，使用Kernel-SVM将空间划分为两个区域。
  

下图展示了一个划分示例。MCTS通过递归的方式不断将整个搜索空间分为优质区域和劣质区域。


MCTS节点选择

LA-MCTS根据UCB分数选择值最大的节点进行采样。假设 代表节点  下所有历史采样点的平均分数， 代表节点  的采样次数， 代表一个超参数， 代表  节点的父节点被采样的次数。那么节点  的UCB分数 如下所示，其中第一项代表节点  的历史平均收益，第二项代表探索权重。


MCTS节点采样

在每个节点上进行采样时，由于前面使用非线性SVM进行了空间分割，因此不能使用传统的均匀采样方式在特定区域内进行采样。为此，LA-MCTS针对两种采样算法设计了两种空间采样方式，即基于信任域的TuRBO采样和经典的BO采样。
对于基于信任域的TuRBO采样，由于TuRBO涉及到一个信任域的概念，因此一个很自然的想法是在TuRBO的信任域内均匀采样，并对于不在非线性候选区域  ，直接拒绝采样。这样一来，TuRBO可以在节点区域内不断优化，直到信任域缩减为零。最终，TuRBO选择采样函数估值最大的点作为真实的采样点。
对于经典的Bayesian Optimization (BO)采样，如果直接采用拒绝采样，可能会存在效率低下的问题。因此，一个比较好的方案是从每一个样本点 开始，首先在其周围一个长度为 的区域内均匀采样，然后逐渐倍增采样区域，直到有一定的面积比例不在  中为止。最终，BO选择采样函数估值最大的点作为真实的采样点。


LA-MCTS结果

强化学习问题

下图展示了LA-MCTS相比其他无梯度优化方法在强化学习问题上的效果。从图中可以看出，LA-MCTS相比其他的无梯度优化算法具有更强的探索能力，不同容易收敛到局部最优，从而最终取得了更好的效果。


消融实验

下图展示了LA-MCTS策略相比传统BO的增强效果。从图中可以看出，LA-MCTS在高维优化任务上有着明显的效果。


下图中，图(a)展示了LA-MCTS的Regret随着采样数量的变化情况，从该图可以看出，随着MCTS的演进，Regret在不断降低。图中紫色图区代表了优质解的区域，黄色区域代表了劣质解的区域。从图(b)中可以看出，随着MCTS的演进，紫色区域在逐渐缩小，最终收敛到了全局最优点。


此外，作者还分析了探索权重，非线性核和分裂阈值的敏感性。从图中可以看出，非线性核是至关重要的。而探索权重和分裂阈值则需要适当调整，才可以实现最佳性能。