超参数优化(五): MCTS+TuRBO-基于蒙特卡洛树搜索的 ...
摘要：本文介绍了一种基于蒙特卡洛树搜索MCST+TuRBO的黑盒函数优化方法。主要的思想是在全局函数空间，通过二叉树递归的将函数空间划分为高函数值和低函数值两部分；能够有效的对高潜力的函数空间进行搜索，特别是在高维情况；在上述方法划分出的局部空间内，使用基于信赖域的二阶求解方法进行高效的求解。<hr/>本系列文章目录：
张大快：超参数优化(一): 简介
张大快：超参数优化(二): 贝叶斯优化
张大快：超参数优化(三): 实验设计
张大快：超参数优化(四): TuRBO--基于信赖域的贝叶斯优化
张大快：超参数优化(五): MCTS+TuRBO-基于蒙特卡洛树搜索的贝叶斯优化
五、MCTS+TuRBO：基于蒙特卡洛树搜索的贝叶斯优化
5.1 背景
在黑盒函数优化中：
https://www.zhihu.com/equation?tex=%5Cmin_%7Bx%7D+%5Censpace+f%28x%29++%2Cx+%5Cin+R%5EN+%5Ctag%7B1%7D++
我们通常面临着函数搜索空间巨大（N的维数非常高）黑盒函数https://www.zhihu.com/equation?tex=f%28x%29为高度非线性（highly nonlinear)，在有限的时间和资源条件下，比较难进行有效的搜索。
论文提出了一种基于空间划分+局部建模优化的方法。主要的思想：
[*]基于蒙特卡洛树搜索空间划分。通过二叉树，递归的将函数空间划分为高函数值和低函数值两部分；在每次函数空间划分时，通过聚类算法聚成两类（高潜力点、低潜力点），使用两类类别信息构建出非线性的决策面（SVM）,能够有效的对高潜力的函数空间进行搜索，特别是在高维情况；
[*]在局部空间使用TuRBO进行求解。在上述方法划分出的局部空间内，使用基于信赖域的二阶求解方法进行高效的求解。
为了方便叙述，我们假定我们已经通过实验设计的方法(张大快：超参数优化(三): 实验设计)获得了评估点集：
https://www.zhihu.com/equation?tex=D_%7B0%7D+%3D+%5C%7B+x_i%2C+f%28x_i%29+%5C%7D%2C+i%3D1%2C...%2CM+%5C%5C
进一步我们可以将MCST+TuRBO方法分成3步：
[*]第1步：树构建（训练阶段），核心是对搜索空间进行有效划分；
[*]第2步：树搜索（预测阶段），从评估点集中筛选出高潜力点；
[*]第3步：TuRBO方法（精确求解），从第2步的高潜力点的信赖域半径内搜索出下一高潜力点。
论文是在2020 NeurIPSBBO 比赛中的一种实现。我们将结合论文及的源码，按照上面3步进行详细的介绍。
5.2 蒙特卡洛树构建（MCT)
从何角度来理解蒙特卡洛树搜索呢？蒙特卡罗方法的三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。
经典的蒙特卡洛树构建，包含了4个步骤：
[*]选择(Selection)：从当前节点(R)选择一个子节点(E,随机或者根据UCB) ；
[*]拓展(Expansion)：对节点E进行拓展。选择和拓展属于下图的Tree Policy ；
[*]模拟(Simulation)：从扩展的E节点出发，进行模拟（生成一系列的子节点），模拟结束后计算节点E的reward
[*]反向传播(Backpropagation)：将E的reward回传给父节点
图15：经典蒙特卡洛树构建
论文提出的LA-MCTS构建，包含了3个步骤：
[*]学习和分裂(Learning & Splitting ): 基于当前获得的评估点集，学习和构建LA-MCTS树搜索（ 包含Kmeans聚类和SVM分类器构建决策面)，搜索树的每个节点是一个SVM分类器;
[*]选择函数空间(Select)：简单的策略是直接选择最左子树，但容易陷入局部最优解，作者引入UCB来进行选择；
[*]采样(Sampling )：在上面选择的函数空间内（叶子节点)，使用BO的方法，生成下一高潜力点。
图16：LA-MCTS树构建
5.2.1 树构建
图17：搜索空间划分
如上图所示，假设我们已经获得了评估点集，我们根据N个样本点构建一颗二叉树来对搜索空间进行划分。约定左子树是高潜力区域，右子树是低潜力区域：
[*]从根节点到最左的叶子节点H是最高潜力区域
[*]从根节点到最右的叶子节点K是最低潜力区域
通过树节点的不断分裂，将整个空间A划分出了若干的区域。当评估点集数量https://www.zhihu.com/equation?tex=%7CD_%7B0%7D%7C较少时，划分出蒙特卡洛树搜索将不置信。对样本点有如下的两个基本要求：
[*]样本点数量要有一定量级，如https://www.zhihu.com/equation?tex=%7CD_%7B0%7D%7C+%5Cgeq+10 ；
[*]样本点在搜索空间中分布均匀，即需要有个较好的实验设计，具体可用参考笔者前面文章
5.2.2 树节点分裂
上面树的构建中，有一个比较重要的问题是每一次节点是如何分裂生成左子树和右子树的呢？ 主要分为3步：
[*]第1步，聚类：根据落在当前节点的样本（设为https://www.zhihu.com/equation?tex=N%28N%5Cleq+M%29个），使用Kmeans聚类，将https://www.zhihu.com/equation?tex=N个样本划分为个高潜力样本(https://www.zhihu.com/equation?tex=label+%3D+1) 、个低潜力样本(https://www.zhihu.com/equation?tex=label+%3D+0): https://www.zhihu.com/equation?tex=N%3DN_%7Bhigh%7D+%2B+N_%7Blow%7D；
[*]第2步，分类：根据第1步的https://www.zhihu.com/equation?tex=label信息，构建https://www.zhihu.com/equation?tex=SVM分类器，学习出当前节点的决策面(Boundary)；
[*]第3步，递归：递归的将当前个结点分裂成左子树，将当前结点分裂成右子树。
详细见下图
图18：Kmeans聚类，SVM划分决策面
5.3 蒙特卡洛树搜索（MCTS)
在上面构建好一颗蒙特卡洛树后，我们如何进行搜索，探测下一个高潜力节点呢？假设当前构建的蒙特卡洛树，从根节点到最左叶子节点的深度为https://www.zhihu.com/equation?tex=K。（注：因我们关注的是高潜力节点，右子树节点为低潜力节点，实际可以不分裂，搁置不管，我们后面介绍的代码实现也是这个策略） 给定当前的https://www.zhihu.com/equation?tex=M个评估点集，我们从根节点出发到最左叶子节点，落在每个节点的评估点集数量为https://www.zhihu.com/equation?tex=m_k ，得到序列https://www.zhihu.com/equation?tex=%5C%7Bm_1%2Cm_2%2C...m_k%2C...%2Cm_K%5C%7D:
[*]https://www.zhihu.com/equation?tex=M+%5Cgeq+m_1+%5Cgeq+m_2+...+%5Cgeq+m_K
[*]高潜力评估点集数量为https://www.zhihu.com/equation?tex=m_K,设为
5.4 TuRBO求解
我们根据上面筛选的高潜力评估点集，将输入到TuRBO中进行求解，筛选出下一高潜力候选点。 TuRBO求解，可以参考笔者文章：
5.5 MCTS+TuRBO代码解析
源代码：https://github.com/jbr-ai-labs/bbo-challenge-jetbrains-research/blob/master/submissions/space-decay/optimizer.py
5.5.1 MCTS树构建
主要的步骤：
[*]1. 对评估点集 ，使用Kmeans聚类，SVM进行决策面划分
[*]2. 预测当前候选点X落在高潜力区域的数量
[*]3. 筛选高潜力候选
[*]4. 筛选低潜力候选
[*]5. 高潜力候选点，递归构建搜索树
[*]6. 返回构建好的MCTS树
def _build_tree(self, X, y, depth=0):
print(&#39;len(X) in _build_tree is&#39;, len(X))
if depth == self.config[&#39;max_tree_depth&#39;]:
return []
split = self._find_split(X, y) # 1. 对评估点集$D_{0}$ 使用Kmeans聚类，SVM进行决策面划分
if split is None:
return []
in_region_points = split.predict(X)# 2. 预测当前候选点X落在高潜力区域的数量
left_subtree_size = np.count_nonzero(in_region_points == 1)# 3. 筛选高潜力候选点
right_subtree_size = np.count_nonzero(in_region_points == 0)# 4. 筛选低潜力候选点
print(f&#39;{len(X)} points would be split {left_subtree_size}/{right_subtree_size}.&#39;)
if left_subtree_size < self.n_init:
return []
idx = (in_region_points == 1)
splits = self._build_tree(X, y, depth + 1)# 5. 高潜力候选点，递归构建搜索树
return + splits # 6. 返回构建好的MCTS树
5.5.2 获得下一高潜力候选点
主要的步骤：
[*]1. 构建MCTS树搜索、构建TURbo
[*]2. 获得落在高潜力区域的候选点
[*]3. 从高潜力候选点出发，生成下一高潜力候选点
[*]4. 使用GPs + sobol构建候选点集
[*]5. 使用MCTS，获取候选点集的高潜力候选点
[*]6. 高潜力候选点择优
def _suggest(self, n_suggestions):
X = to_unit_cube(deepcopy(self.X), self.lb, self.ub)
y = deepcopy(self.y)
if not self.node:
# 1. 构建MCTS树搜索、构建TURbo
else:
# 2. 获得落在高潜力区域的候选点
idx = (self._get_in_node_region(X, self.node) == 1)
X = X
y = y
length_reties = self.config[&#39;turbo_length_retries&#39;]
for retry in range(length_reties):
# 3. 从高潜力候选点出发，生成下一高潜力候选点
XX = X
yy = copula_standardize(y.ravel()) # 函数值标准化
# 4. 使用GPs + sobol构建候选点集
X_cand, y_cand, _ = self.turbo._create_candidates(
XX, yy, length=length, n_training_steps=self.config[&#39;turbo_training_steps&#39;], hypers={})
# 5. 使用MCTS，获取候选点集的高潜力候选点
in_region_predictions = self._get_in_node_region(X_cand, self.node)
in_region_idx = in_region_predictions == 1
if DEBUG:
print(f&#39;In region: {np.sum(in_region_idx)} out of {len(X_cand)}&#39;)
if np.sum(in_region_idx) >= n_suggestions:
X_cand, y_cand = X_cand, y_cand
self.turbo.f_var = self.turbo.f_var
if DEBUG:
print(&#39;Found a suitable set of candidates.&#39;)
break
else:
length /= 2
if DEBUG:
print(f&#39;Retrying {retry + 1}/{length_reties} time&#39;)
# 6. 高潜力候选点择优
X_cand = self.turbo._select_candidates(X_cand, y_cand)[:n_suggestions, :]
return X_cand
5.6 总结
本文介绍了一种基于蒙特卡洛树搜索MCST+TuRBO的黑盒函数优化方法。主要的思想：
[*]在全局函数空间，通过二叉树递归的将函数空间划分为高函数值和低函数值两部分；在每次函数空间划分时，通过聚类算法聚成两类（高潜力点、低潜力点），使用两类类别信息构建出非线性的决策面（SVM）,能够有效的对高潜力的函数空间进行搜索，特别是在高维情况；
[*]在局部空间使用TuRBO进行求解。在上述方法划分出的局部空间内，使用基于信赖域的二阶求解方法进行高效的求解。
笔者在QQ浏览器2021AI算法大赛使用了该方法，MCST+TuRBO在全局空间的探索上，表现出色；当问题有较多的局部最优解时，容易陷入局部最优解，跳不出来。后面我们介绍的《HEBO：异质方差进化贝叶斯优化》、 《pySOT和POAP: 代理模型优化工具箱及其异步并行框架》将在一定程度上弥补MCST+TuRBO的不足。
后续文章目录：
[*]超参数优化(六)：HEBO-异质方差进化贝叶斯优化
[*]超参数优化(七)：pySOT和POAP-代理模型优化工具箱及其异步并行框架
[*]超参数优化(八)：QQ浏览器2021超参数优化大赛参赛经验总结
<hr/>欢迎关注:simplex101,了解更多超参数优化（黑盒优化）分享内容。
参考文献
QQ浏览器2021AI算法大赛，QQ浏览器2021AI算法大赛
Turner, Ryan, et al. &#34;Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020.&#34; arXiv preprint arXiv:2104.10201 (2021).
TCowen-Rivers, Alexander I., et al. &#34;Hebo: Heteroscedastic evolutionary bayesian optimisation.&#34; arXiv e-prints (2020): arXiv-2012.
Liu, Jiwei, Bojan Tunguz, and Gilberto Titericz. &#34;GPU Accelerated Exhaustive Search for Optimal Ensemble of Black-Box Optimization Algorithms.&#34; arXiv preprint arXiv:2012.04201 (2020).
Sazanovich, Mikita, et al. &#34;Solving black-box optimization challenge via learning search space partition for local bayesian optimization.&#34; NeurIPS 2020 Competition and Demonstration Track. PMLR, 2021.
Wang, Linnan, Rodrigo Fonseca, and Yuandong Tian. &#34;Learning search space partition for black-box optimization using monte carlo tree search.&#34; arXiv preprint arXiv:2007.00708 (2020).
Eriksson, David, et al. &#34;Scalable global optimization via local bayesian optimization.&#34; Advances in Neural Information Processing Systems 32 (2019): 5496-5507.
Eriksson, David, David Bindel, and Christine A. Shoemaker. &#34;pySOT and POAP: An event-driven asynchronous framework for surrogate optimization.&#34; arXiv preprint arXiv:1908.00420 (2019).
Regis, Rommel G., and Christine A. Shoemaker. &#34;A stochastic radial basis function method for the global optimization of expensive functions.&#34; INFORMS Journal on Computing 19.4 (2007): 497-509.
页:
[1]