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

RhinoFreak · 发表于 2022-6-20 09:34

什么是蒙特卡洛树搜索？

蒙特卡洛树搜索是一种规划算法，简单来说，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算法实现对连续优化问题的求解，即找到 $f(x)$ 的最优解 $x^*$ 。

$\mathbf{x}^{*}=\arg \max _{\mathbf{x} \in X} f(\mathbf{x}) \tag{1}$
MCTS搜索空间构建

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

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

首先，对于某个区域内的样本点，LA-MCTS将样本点 $[\mathrm{x}, f(\mathrm{x})]$ 使用K-Means进行聚类，划分成高质量和低质量两个区域。
随后，使用Kernel-SVM将空间划分为两个区域。

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

MCTS节点选择

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

$u c b_{j}=\frac{v_{j}}{n_{j}}+2 C_{p} * \sqrt{2 \log \left(n_{p}\right) / n_{j}} \tag{2}$
MCTS节点采样

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

LA-MCTS结果

强化学习问题

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

消融实验

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

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

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

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源