【源头活水】NAS中基于MCT的搜索空间采样方法

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

本文分享自华为云社区《[NAS论文]Prioritized Architecture Sampling with Monto-Carlo Tree..》，原文作者：苏道

地址：https://bbs.huaweicloud.com/blogs/263422

作者认为以前的NAS在sample layer的op的时候，都是独立的，没有考虑之前layer的采样情况，搜索阶段的进化算法只允许变异和交叉操作，没有考虑层间的关系，导致了次优结果。所以用Monte Carlo Tress(MCT)方法捕捉层间依赖，存储过往op采样和性能信息。

 【Prioritized Architecture Sampling with Monto-Carlo Tree Search】 

作者：悉尼大学、旷视大佬们

Paper: https://arxiv.org/abs/2103.11922

Code: https://github.com/xiusu/NAS-Bench-Macro

注：以下图片都来自论文原文、文字基于原文翻译和个人主观理解，作者水平很差，大家手下留情，如有错误欢迎大家指正，拜谢

01

太长不看系列

1、作者认为以前的NAS在sample layer的op的时候，都是独立的，没有考虑之前layer的采样情况（ they often consider each layer separately while ignoring the dependencies between the operation choices on different layers），搜索阶段的进化算法只允许变异和交叉操作，没有考虑层间的关系，导致了次优结果。所以用Monte Carlo Tress(MCT)方法捕捉层间依赖，存储过往op采样和性能信息。

2、并且存在MCT的信息在search阶段会用得上，具体的话，MCT是用训练损失作为对架构性能的奖励来更新的

3、当然，为了准确地评估众多的node，在训练和搜索阶段提出了节点通信和分层节点选择方法

4、在搜索阶段用MCT方法抽一定约束下的20个子架构用验证集刷精度，用就好那个就完成了搜索过程，减少不少计算量和工作量，442M FLOPs 在Imagenet能有78.0% Top-1 acc

5、消融实验做的不错！

个人感觉：

MCT的训练方法在这里没用好，甚至在起负向作用，我指的是MCT sample这个方法可能用的不是很好，但是不可否认的是uniform+MCT sample （tau 76.22 in CIFAR-10）方案明显相关性系数kendall tau 比uniform sampe（tau 72.41 in CIFAR-10）更高，但是却不见得能搜到一个更好的结果比起uniform sample（下图），因为训练是uniform + MCT sample，搜索是MCT搜索，估计是这个训练和搜索的GAP导致的，一般的理解是，当抽supernet的架构acc排序和单架构从头 训练的acc排序相关性越一致越能够搜到一个更好的结构，意味supernet更能够预测不同架构的性能，在跑EA的时候更加精确，但是从这里的结果看居然起到了一个反效果，只能归结于训练和搜索的GAP了 。

02

细品系列

大体流程

以往的搜索空间采样，层间采样是相互独立的，本文的方法是构建一个MCT树，采样都依赖这样一个统一的树状结构，更能关注到层间的联系。

更具体的，作为一个two-stage的NAS方法，采样的形式如下图中间，按树状结构的MCT方法抽一个出来更新超网络，训练完再搜索阶段如下图右边，使用分层节点选择搜索最优架构。

训练的loss会做奖励反馈给每个op，并且作者提出一种节点通信技术，在相同depth的op可以共享奖励，避免重复计算。并且在搜索阶段，为了更准确的评估每个op，提出用分层op选择的方式，然后用验证集分层更新那些比较少被访问到的op上的奖励。然后采用分层node【op】选择方法搜索子架构，得到验证精度最高的最终体系结构。

MCT的搜索空间

一般的NAS的采样策略是独立选择op的，用公式表示的话如下：， P（o^{l}）表示第 l [小L]层操作选择的概率分布。

但是MCT，每一层操作的选择应该依赖于前一层的操作，可以表示为：，非常直观

MCT采样训练过程

对于每个node，都存了两个值在MCT上，一个是Q[quality]值，一个是n值[表示出现次数numbers]，一开始打算用训练的loss来表示Q值，但是这样其实有失偏颇，因为不好直接比较不同迭代次数下的架构，所以采用了滑动平均的训练Loss值，然后取了个比值算到Q值：

其中Ltr(αt)表示第t次迭代下的架构αt的训练loss。上面第一条公式的  L波浪线t 表示超网络在第t次迭代下滑动平均的loss，所以Q值就表示为滑动平均的loss比上当前的loss的值，感觉这里有点问题，如果一个架构本来loss就比较持续性高且稳定，那么这个Q值不低的，但是这个loss高一般acc也就不高了，那其实这个架构是不是不咋地但是被判定为Q值高而不错？（我猜的）

接着，MCT的采样方法基于Upper Confidence Bounds for Trees (UCT)：

  是父节点的访问次数。一般情况下，MCT只选择UCT评分最高的节点，但是它阻碍了采样方法探索更多样的架构，所以和DARTS的方法类似，要把UCT给relax一下，就是softmax一下，其中Nl表示深度为l的总节点数，在所有实验中τ到0:0025：

节点通信

在supernet中，同一层中的相同op共享相同的权重，这启发了节点应该从它们的op类型获得一些公共知识，所以提出了一种节点通信技术来共享相同op和深度的节点的奖励，为了表示特定层中某个op的奖励G，使用相应节点的所有奖励的移动平均值，就是滑动平均掉Q值：

那么UCT方程也可以变为，C1/C2是超参数：

层间节点选择

在搜索阶段。通过MCT存储的Qvalue，很容易可以直接采样奖励最高的架构作为最终结果，然而，在训练集上表现最好的子架构可能并不总是在验证集上表现最好的，因此，需要通过搜索阶段来重新验证一小部分奖励高的架构，然后输出验证精度最高的架构作为搜索的结果。

此外，为了准确评估访问次数较少的node，用分层节点选择方法，分层地选择节点，对访问次数较少的节点进行重新评估。

然后，从root 节点开始，如果子节点的访问次数＞阈值，那么就认为这些满足条件的子节点是有前途的，然后relax分布这些节点，然后采样，如果所有节点的平均访问次数达不到阈值，就随机采样这些节点用batch验证集刷，直到刷到次数够阀值，才继续前一步。

得到具体的子架构，然后用完整的验证集对其进行验证。我们重复这个过程Search number，然后选其中最好的。就是抽Search number个用验证集验证选最好的吧

03

目标检测

cifar10上做相关系分析

超网络的架构性能排序是一个非常重要的一个指标，本文在cifar10做了相关系分析吗，对比3种NAS采样架构训练方法、1、uniform、2、MCT、3、uniform+MCT：

结果表明uniform预训练一段时间再接MCT训相关系最好，tau能有76.22，当然如果在imagenet估计得再降低不少。先uniform感觉是提供了一个不错的预训练参数给MCT，起到了加速的作用。

参数量/FLOPs大性能就好嘛？

由下图结果可知，虽然FLOPs和参数在搜索空间中分布均匀，但精度表现不同，这可能是因为当模型容量增加到饱和水平时，容量的增加不会产生显著的性能增量，就是当FLOPs和参数增加的时候，acc不一定会线性提高;

增加FLOPs和增加parameters哪个对性能提升大

从下图其实就能看到，FLOPs的增加比参数的增加对精度的贡献更大。

search number多少才算好

因为MCT已经存储了每个子网的奖励，所以我们可以直接使用奖励最高的子网作为最终的架构，然而，这些奖励只限于训练损失，因此对性能不够准确，因此仍需要在验证集上评估子网以获得更好的结果， 所以就是拿search number个架构用验证集刷一下，看看哪个好就用哪个，具体多少个search number 看下图：首先可以看到直接冲最高奖励的子架构，其实就能达到很好的效果超过用EA和random sampling的搜索方案，然后抽50个search number 来刷一下验证集取最好基本也能达到了最好的效果，以后都用search number = 20,因为够好了【这部分的试验都在CIFAR-10】。

具体的话，就是使用分层节点选择和MCT进行体系结构搜索，对于一个路径(子网)的采样，从MCT的根节点中分层次选择最优节点，阈值常数nthird为6。如果子节点的平均访问次数低于 nthrd，我们随机抽样由这些子节点组成的路径，然后使用一批(即128)验证数据eval这个架构，直到达到阈值。选取所有节点后，得到具体的子网(结构);然后，使用完整的验证数据集对其进行评估。此外，重复这个过程对子网进行抽样，直到达到预定义的搜索次数(即20次)。然后，我们选择验证精度最好的结构从头开始训练评估

在ImageNet上的试验结果

搜索空间的设计上没有太特别的地方，batchsize=1024，SGB0.9，初始lr0.12，只训练了120epoch，前60epoch是uniform sampling作为warmup，后60epoch，采样子网的FLOPs必须在一定的预算范围内（0.9-1.0X），在接下来的20%epochs（ 61-85 epochs）, 仍旧是uniform sampling，也uniformly sample才构建MCT，在后面的epochs采用MCT方法采样来训练（86-120epochs），其实整个过程大部分都在uniform sample，整个过程应该是：【无约束uniform sample】--> 【有约束uniform sample】-->【有约束MCT sample】，其实到MCT sample的时候，lr只剩下不到一半，0.05448左右了。

没有用蒸馏，但是搜索这个阶段因为MCT的原因感觉效率很高。

至于为什么只训练120epochs呢，看下图：蓝色是直接supernet出来的精度，橙色是搜到的架构train form scratch的。说明几个问题：

1、supernet的训练程度没有很高，都低于60%
2、随着训练epoch的增加，搜出来的架构acc居然在震荡，

具体：
1-60epochs是在无约束uniform sample，得益于此，搜到的结果一直稳定提升，
60-85epcoh也仍旧在uniform sample，但是是有FLOPs的约束，
不过，搜到的acc也在上升，
但是一换成MCT采样，就是85epoch之后，搜到的结构就不好了，acc在下降/震荡，这个说明这个MCT没用，或者其实MCT没用好，毕竟在搜索阶段的MCT优势对比过EA其实是可以的，但是训练阶段的MCT sample好像差强人意，也是日后可以改进的点

04

消融实验

在ImageNet上评估这些技术的不同组合的性能

1、在ImageNet上评估这些技术的不同组合的性能，并给出验证的acc，如下图：

说明几个问题：

①、通过对搜索阶段第1、2、3行进行比较，由于在训练阶段使用了大量的信息，所以在搜索过程中使用MCTS搜索比使用进化搜索得到更好的结果

②、对比搜索阶段5/6可以看出用了层间更新的方法能在搜索阶段搜到更好的结果。

不同子架构采样方法的增益

为了检验不同搜索方法的搜索效率和结果，在ImageNet上使用uniform sample的方法训练超级网络，分别采用进化抽样、随机抽样和MCT-NAS方法搜索330M-FLOPs路径，search number是1000，能看出来，这个MCT搜索能比EA的方法搜的结构好，训练超网络很重要，一个好的搜素方法也很重要

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“源头活水”历史文章

更多源头活水专栏文章，

请点击文章底部“阅读原文”查看

分享、在看，给个三连击呗！