布朗大学和FAIR开源：LA-MCTS，及其在神经网络结构搜索的应用

点击上方“CVer”，选择加"星标"置顶

重磅干货，第一时间送达

本文作者：王林楠

https://zhuanlan.zhihu.com/p/266965685

本文已由原作者授权，不得擅自二次转载

Github地址：

https://github.com/facebookresearch/LaMCTS

大家好，我们开源了在NeurIPS-2020所提出一个，基于蒙特卡洛树搜索（MCTS）的全新黑盒优化算法 (命名为LA-MCTS)。同时也开源了，近2年来我们利用MCTS在神经网络结构搜索的工作 (命名为LaNAS)。下面是这个开源项目一览：

• Neural Architecture Search，全网最全的神经网络结构搜索pipeline。

1. 开源LaNAS on NASBench101：无需训练网络，在你笔记本上快速评估LaNAS。

2. 开源LaNAS搜索出的模型"LaNet"：在CIFAR-10和ImageNet上都取得SoTA结果。

3. 开源one-shot/few-shots LaNAS：只需几个GPU，快速并且高效完成神经网络结构搜索。含搜索，训练，整套pipeline。

4. 分布式 LaNAS：让我们用上百个GPU来超过最先进的模型。整套pipeline。

5. Bag of tricks 模型训练的那些黑科技：我们列出当下训练模型的一些提升点数黑招数。

• Black-box optimizations，黑盒优化

1. 1分钟的对比：只需1分钟，评测LA-MCTS，和贝叶斯优化及进化算法。

2. MuJoCo Tasks：应用LA-MCTS在机器人，强化学习，并可视化你学出来的策略。

----------------------------------------------------------------------------------------

感谢大家，下面是我们这些年在NAS的发展方向探索的一个简介，和思考。

1. 起源：应用蒙特卡洛树搜索在神经网络结构搜索。

2017年初，我的导师从美国国防高级研究计划局的D3M项目拿到了一笔项目资金，开启了我们的AutoML研究。而我被分配的子任务，就是神经网络结构搜索(NAS)。当时NAS研究的2篇文章，都是利用强化学习（谷歌的policy gradients和MIT的Q-learning）。我们发现Q-learning的epsilon greedy非常简单的同等对待了所有的状态(states)，并不考虑每个states过去探索了多少次，所以并不能很好的去平衡利用(exploitation)和探索(exploration)。从这点出发，我们考虑对每个状态去建模，来更好的平衡利用和探索，来提高搜索效率。而蒙特卡洛树搜索(MCTS)正是对每一个状态建模，利用UCT来动态的平衡利用和探索。同时，AlphaGo的成功证实MCTS在大规模状态空间下效果非常好。在这样的背景下，我们开发第一个基于MCTS的NAS算法，并命名为AlphaX。

AlphaX构建网络和MIT的Q-learning算法相似。从一个空网络开始，根据动作集，比如添加一个conv或者pooling，逐层构建一个网络架构（s→a→s’）。因为训练一个网络非常慢，AlphaX提出利用一个价值函数预测器（value function predictor）来预测当下状态下的子网络们的性能。这个价值函数器输入就是一个网络架构，输出就是预测的该网络的精度。同时我们验证了，NAS能够提升很多下游的视觉应用，比如风格迁移，目标检测等。详情请见[1]。

2. 学习蒙特卡洛树里的动作集，从LaNAS到LA-MCTS。

基于AlphaX，我FB的导师 @田渊栋洞察到动作集在AlphaX对搜索效率有着显著的影响。为了证实这个想法，我们设计了动作集sequential和global。动作集sequential就是按照逐层构建网络的思路，一步步的增加conv或者pooling，并指定每层的参数；而动作集global则首先划定网络的深度，比如10层网络。然后同时给这10层网络指定每层的种类，参数等。我们发现动作集global的搜索效率显著高于动作集sequential，并且可视化了状态空间，如下图。

直观上而言，状态空间在global的动作集下，好的状态（深色）和差的状态（浅色）区分的很好，不像sequential混杂在一起。这样搜索算法可以很快找到一个好的区域，所以效率更高。

基于这个观察，促使我们去给MCTS学习动作集，并提出了Latent Action Monte Carlo Tree Search (LA-MCTS)。

LA-MCTS的核心思想就是，在每一个树的节点上，我们想学到一个边届，根据当下的采样点（既网络和精度），能够把搜索空间分为一个好的子空间（左节点），和一个坏的子空间（右节点），如上图。而这里的隐动作集(Latent Action)就是，从当下节点选择去左/右孩子。至于动作的选择，在每个节点是根据UCT公式来决定。因为每个节点对应一个搜索空间，这个搜索空间上有相应的样本。每个孩子上对应搜索空间的样本的个数就是UCT里的n，而这些样本性能的平均值就是UCT里的v。当我们对搜索空间建立这样的一个搜索树，随着树深度的增加，在搜索空间找到好的区域也越来越精确。

我们最初把这个想法应用在了NAS，并构建了一个NAS系统命名为LaNAS[2]。对比贝叶斯优化和进化算法，LaNAS在NAS的基准数据集NASBench-101上取得了显著的提升。所以我们又扩展了LaNAS成为了LA-MCTS去做应用更广的黑盒优化。从LaNAS到LA-MCTS，核心更新有：1）LA-MCTS把LaNAS里的边界扩展成一个非线性边界，2）LA-MCTS在采样的时候利用贝叶斯优化来选择样本。最后，LA-MCTS在各种测试函数和MuJoCo上取得了显著的提升，详见[3]。

3. 快速回顾MCTS在黑盒优化的历史。

早在2011年，Rémi Munos (DeepMind) 提出利用MCTS来分割搜索空间用来优化一个黑盒函数 [4]，然后，剑桥大学和MIT，有很多工作把这种切分搜索空间的思想用在了高维贝叶斯优化 [5][6]。但是这些工作一般都会采用一个k-ary区块切分（如下图）。2020年，MIT的Beomjoon Kim在[7] 展示出利用沃罗诺伊图（Voronoi Graph）去切分搜索空间，结果会更好。我们的工作，LA-MCTS，则是利用了learning的法则，根据当下样本来学习分割方法，来提高搜索效率。

4. 那么对比贝叶斯优化的优势是什么？

贝叶斯优化 (BO) 由一个surrogate和一个acquisition组成。基于高斯过程的surrogate往往因为计算，随样本数(N)呈N^3增加，而受限于小规模应用。很多工作已经很好的解决了这个问题，比如利用贝叶斯网络去近似均值和方差。所以大规模采样在贝叶斯优化已不是问题。但是在连续空间下，往往一个问题的纬度 > 10后，BO就会出现过度探索搜索空间边界的问题[6]。因为LA-MCTS分割了搜索空间，UCT会动态探索子空间，避免了BO上述的问题。

更多细节，及和遗传算法的对比，请见LA-MCTS的related works章节[8]。

5. 搜索是否对NAS重要？

我认为是重要的。以下是我观测到的一些趋势及我的思考。

1）最近有些文章展示随机搜索都可以达到很好的结果，那么是不是意味着搜索不重要了？

首先这些文章是说随机搜索得到的结果还不错，是一个非常强的对比基准。这个往往因为目前的搜索空间的设计，导致大部分网络结果都很好，比如下图所呈现的NASBench-101中42万个网络的分布（横轴是精度，纵轴是这个精度下有多少网络）。所以找出一个工作还不错的网络并不难。

2) 既然搜索空间的设计影响很大，那么是不是更应该把注意力放在设计搜索空间，而不是搜索？

我觉得这个问题应该站在不同的角度。首先，近几年神经网络的高速发展让我们在设计搜索空间的时候有了很多先验经验，所以设计出来的搜索域里的网络都不会太差。在一些传统的视觉应用，搜索的贡献可能就不如加各种tricks或者调参数在工程中来的更实际一些。

但是如果当我们遇到一个新的任务，比如设计一个神经网络去调度网络节点。由于先验经验很少，这个时候搜索就可以极大的加速我们设计网络的速度。并且搜索可以提供很多的经验去让我们改进搜索空间。

3）基于搜索方法的NAS和DARTS类算法的对比。

以DARTS为代表的one-shot NAS方法跑的很快，是因为利用了一个超级网络(Supernet)去近似每个网络的性能。在这个过程中，Supernet相当提供一个网络性能的预测，然后利用SGD在Supernet上去找一个比较好的结果。这里Supernet和Search也是可以分开，而且分开后更易分别提高这两个部分。所以只需要把Supernet的概念应用在传统搜索方法上，也是可以很快得到结果。SGD的问题是很容易卡在一个局部最优，而且目前SoTA的结果基本都是利用传统搜索方法直接，或者利用一个supernet搜索出来的。

6. 我们搜索出的LaNet结果一览。

[1] Neural Architecture Search using Deep Neural Networks and Monte Carlo Tree Search, AAAI-2020.

[2] Sample-Efficient Neural Architecture Search by Learning Action Space, 2019

[3] Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search, NeurIPS 2020.

[4] Optimistic optimization of a deterministic function without the knowledge of its smoothness, NeurIPS 2011.

[5] Batched Large-scale Bayesian Optimization in High-dimensional Spaces, AISTATS 2018.

[6] Heteroscedastic Treed Bayesian Optimisation, 2014.

[7] Monte Carlo Tree Search in continuous spaces using Voronoi optimistic optimization with regret bounds, AAAI-2020.

[8] Bock: Bayesian optimization with cylindrical kernels

重磅！CVer-NAS 微信交流群已成立

扫码添加CVer助手，可申请加入CVer-NAS 微信交流群

同时也可申请加入CVer大群和细分方向技术群，细分方向已涵盖：目标检测、图像分割、目标跟踪、人脸检测&识别、OCR、姿态估计、超分辨率、SLAM、医疗影像、Re-ID、GAN、NAS、深度估计、自动驾驶、强化学习、车道线检测、模型剪枝&压缩、去噪、去雾、去雨、风格迁移、遥感图像、行为识别、视频理解、图像融合、图像检索、论文投稿&交流、PyTorch和TensorFlow等群。

一定要备注：研究方向+地点+学校/公司+昵称（如NAS+上海+上交+卡卡），根据格式备注，可更快被通过且邀请进群

▲长按加群

▲长按关注我们

整理不易，请给CVer点赞和在看！