网络搜索之DARTS, GDAS, DenseNAS, P-DARTS, PC-DARTS

最近项目需要，看了下 NAS，这里总结一下

由于笔者不懂RL 也不懂进化算法，谷歌那套是follow不了，故看的都是 gradient based 的方法，先总结下几篇文章的相关工作：

1.DARTS [1]：第一个能work的 end2end 基于梯度反传的 NAS 框架，当然你也可选择ENAS（重点是开源了，而且代码写得易懂，后面几个文章都是基于这个做的）。

2.GDAS [2]：百度出品，提出了可微的operation sampler，故每次只需优化采样到的部分子图，故特点就是一个字：快 （4 GPU hours）。

3.DenseNAS [3]：地平线出品，提出了可以同时搜 block的宽度和空间分辨率的可微分NAS，story讲得还行，实验部分有点虚。

4.P-DARTS [4]：华为出品，致力于解决在proxy训练与target测试的模型depth gap问题，参考李飞飞 PNAS 的思路用在block间。

5.PC-DARTS [5]：华为出品，针对现有DARTS模型训练时需要 large memory and computing问题，提出了 channel sampling 和 edge normalization的技术，故两个字：更快更好 （0.1 GPU-days）。

它们之间的联系：

无疑 [2], [3], [4], [5] 都是基于 DARTS 来进行拓展；[2] 和 [5] 都是希望加快搜索速度，故采取的sampling的策略和目标也不同；[3] 和 [4] 分别就模型 宽度 和 深度 方面进行拓展。更准确地来说，[3] 是针对移动端来做的，更类似应该是 ProxylessNAS, FBNet 。

一、DARTS [1]，ICLR2019

很早提出的文章，不知道为啥才中的ICLR。

DARTS 思想是直接把整个搜索空间看成supernet，学习如何sample出一个最优的subnet。这里存在的问题是子操作选择的过程是离散不可导，故DARTS 将单一操作子选择 松弛软化为 softmax 的所有操作子权值叠加。

下面来看看它主要做了什么：

DARTS总览

由上图得：

(a) 定义的一个cell单元，可看成有向无环图，里面4个node，node之间的edge代表可能的操作（如：3x3 sep 卷积），初始化时unknown

(b) 把搜索空间连续松弛化，每个edge看成是所有子操作的混合（softmax权值叠加）

(c) 联合优化，更新子操作混合概率上的edge超参（即架构搜索任务）和 架构无关的网络参数

(d) 优化完毕后，inference 直接取概率最大的子操作即可

故文章的重点就放在了 (b) 和 (c) 部分，分别可以由下面的一条公式和算法描述表示：

Softmax操作，每对nodes (i,j) 的子操作混合权重为

，维度为 |O| 即node间子操作的总个数； o() 表示当前子操作。

算法实现上就是轮流更新，在训练集上更新网络参数

，在验证集上更新网络架构超参

二、GDAS [2]，CVPR2019

全称叫 Gradient-based search using Differentiable Architecture Sampler (GDAS)，顾名思义，是一种 gradient-based 的方法，且使用了可微采样器，那问题来了，为什么要采样呢？

1. 直接在整个supernet更新整图太耗时了，每次iteration都要更新所有参数，比如DARTS，需要耗时一天。

2.同时优化不同的子操作会导致训练不稳定，因为有些子操作会有相反的值，是竞争关系，直接相加不科学。

故文中就提出了采样器来得到sub-graph，这样每次iteration优化更新只针对sub-graph操作即可。

Differentiable Sampler：

那么问题来了，怎么设计这个sampler？如果sampler不可微，怎么进行梯度反传更新呢？

首先对于node (i,j) , 从离散概率分布

中采样一个变换函数（即子操作），故在搜索时通过下式计算可得每个node值：

其中

是从离散概率分布

采样得到，

为其参数。离散概率分布可通过下述的可学习概率质量函数表示：

其中

是 K 维可学习 vector

中的第 k 个元素。

由于上述操作不可导，故作者使用 Gumbel-Max trick 来将公式(3)重写为：

将 arg max 松弛软化为softmax形式，就可导了：

定制化Reduction cell

为了减少搜索空间的大小和减缓联合搜 normal & reduction cell 的优化难度，文中根据专家经验自定义了 reduction cell：

reduction cell

实验结果

来看看GDAS与DARTS在CIFAR和ImageNet的性能对比：

1.识别率基本与DARTS持平的情况下，搜索时间比它快5倍以上。

2.GDAS(FRC) 是基于上图定制化的reduction cell 来只搜normal cell的，性能更好，参数更少，搜索时间更短。

Search on CIFAR10, test on CIFAR10 & CIFAR100

Search on CIFAR10, test on ImageNet

文中3.2节有一段值得思考的话：

其实文章初衷是设计跑得快的NAS，估计是想用于直接跑target大数据集，比如ImageNet，不过最后发现搜出来的性能堪忧。哈哈，可以思考下why。（花絮，后面PC-DARTS里有句话解释了这个现象）

三、DenseNAS [3]，2019

由于NAS一般需要很强的专家经验来设计中间block的channel数以及何时进行downsampling，故人工设定的可能不是最优的，DenseNAS做的就是让网络通过搜索自行决定渐进的block的宽度及何时downsampling。

如何实现这个功能呢？如下图所示，定义一个密集连接的搜索空间，里面block间的宽度渐渐增加，stride慢慢下降，而每个block有一定概率与同分辨率及stride=2于当前的block进行连接（如灰色连接线所示）；由于这一套是基于stack mobile convolution block，故中间不设skip-connect操作， 最后训练完毕后，按照特定算法选择路径（红色实线）即可。

密集连接的搜索空间

那么问题来了：

1.不同block的宽度和分辨率可能不同，怎么进行连接？

2.block之间多了这么多path，怎么进行端到端梯度反向传播？

文中给出的方案是：

1.如下图所示，Block模块里，针对每个输入的previous block，都有各自的head layers，功能是转化为相同宽度和分辨率的tensor，这样才能权值叠加

2.在layer-level，跟DARTS一样，node之间该怎么反传就怎么反传；在Block-level， 也仿照layer-level 来松弛软化使用softmax来当成多个head layers后的权值叠加。

Layer, Block, Network

最后当搜索完成，layer-level直接选择最大概率的子操作即可；对于 Network-level，使用Viterbi algorithm 来选择最高转移概率的block进行连接。

由于本文是做移动端搜索，故latency也作为优化的目标之一：

实验结果

只在ImageNet搜测了实验结果，感觉亮点不够突出呀。

四、P-DARTS [4]，2019

由于NAS受限于memory和计算消耗，一般都会在proxy集进行较浅的initial channel及layer depth搜索，然后把搜好的模型再扩充较大的channel和depth放到target集上重训重测。

那么问题来了：怎么优化这个 depth gap 问题？

如上图所示，在DARTS中，搜索时候是以 8 cells with 50 epochs 来进行的，而evaluate时却以 20 cells，这bias造成了精度大幅度下降；而 P-DARTS 以渐进的方式 5 cells, 11 cells, 17 cells 分别 25 epochs 来进行，这样更能接近evaluate时的情况，故性能也更好。

OK，你可能会问，为什么不直接以20 cells 来进行搜索呢？好问题，理论上应该是可行的，就是太耗memory且容易网络架构过拟合；那17 cells也很深，memory够吗？这也是好问题，P-DARTS其实就是在解决这个问题：

P-DARTS pipeline

如上图所示

(a) cells=5时，每个node间有5个candidate，当训练好了25 epochs后，会有对应的softmax置信度。

(b) 接着进行 cells=11的搜索，虽然深度加了一倍多，但这时每个node间operation candidate将会减少接近一半，即把(a)中最后置信度较低的operation直接delete掉。

(c) 同样的流程，最后进行 cells=17的搜索，再砍掉置信度低的一半opeartion。通过这样的方式来tradeoff depth及memory。

文中还探讨了另外一个问题，就是搜索空间里skip-connect的影响，从实际效果来看，过多的skip-connect（无可学习参数）会使其表征能力下降，测试时性能欠佳；但往往因为搜索时 skip-connect收敛得更快，故如何设计基于skip-connect的约束项呢？

1. 在每个skip-connect操作后插入operation-level dropout，然后训练时逐渐减少Dropout rate。

2.加个超参 M=2 来限制最后cell内部 skip-connect的最大总数。

实验结果

来看看在CIFAT上的实验结果，明显在搜索时间和性能上都碾压DARTS了。

不过有趣的是，最后两行(large) 是指将 initial channel 从 36 增加到 64，性能增加；故要不要搞个progressive channel 版本的搜索呢？哈哈

最后我们来看看三个stage的memory消耗情况，尽管已经17 cells了，一个P100还OK：

五、PC-DARTS [5]，2019

接着上面的P-DARTS来看，尽管上面可以在17 cells情况下单卡完成搜索，但妥协牺牲的是operation的数量，这明显不是个优秀的方案，故此文 Partially-Connected DARTS，致力于大规模节省计算量和memory，从而进行快速且大batchsize的搜索。

PC-DARTS的贡献有两点

1.设计了基于channel的sampling机制，故每次只有小部分1/K channel的node来进行operation search，减少了(K-1)/K 的memory，故batchsize可增大为K倍。

2.为了解决上述channel 采样导致的不稳定性，提出了 edge normalization，在搜索时通过学习edge-level 超参来减少不确定性。（这跟DenseNAS中的head layer权值叠加有点像）

PC-DARTS

A、部分通道连接

如上图的上半部分，在所有的通道数K里随机采样 1/K 出来，进行 operation search，然后operation 混合后的结果与剩下的 (K-1)/K 通道数进行 concat，公式表示如下：

B、边缘正规化

上述的“部分通道连接”操作会带来一些正负作用：

正作用：能减少operations选择时的biases，弱化无参的子操作（Pooling, Skip-connect）的作用。文中3.3节有这么一句话：当proxy dataset非常难时（即ImageNet），往往一开始都会累积很大权重在weight-free operation，故制约了其在ImageNet上直接搜索的性能。

所以可以解释为啥GDAS直接在ImageNet搜效果不行，看回用GDAS在CIFAR10搜出来的normal cell，确实很多是Skip-connect，恐怕在ImageNet上搜，都是skip-connect。。。

副作用：由于网络架构在不同iterations优化是基于随机采样的channels，故最优的edge连通性将会不稳定。

为了克服这个副作用，提出边缘正规化（见上图的下半部分），即把多个PC后的node输入softmax权值叠加，类attention机制：

由于 edge 超参

在训练阶段是共享的，故学习到的网络更少依赖于不同iterations间的采样到的channels，使得网络搜索过程更稳定。当网络搜索完毕，node间的operation选择由operation-level和edge-level的参数相乘后共同决定。

实验结果

来看看直接在ImageNet搜出来的SOTA结果，只需要 3.8 GPU-days，有点厉害。

不过对比下，P-DARTS（CIFAR10）的也厉害，性能和搜索时间很好的tradeoff。

最后的最后，来看个有趣的消融实验：

直接看第二行，加了EN后，普通的DARTS性能也能提升；也就是说EN是可以用到所有的DARTS框架中，这个很不错。

总结与展望

小memory，少人工定义的参数(initial channel, layer数啥的就很头疼)，design more task-related search space，架构跨数据集泛化能力。

在各个领域用起来，才能有各种新坑，和各种新的改进。

Reference:

[1] Hanxiao Liu et al., DARTS: DIFFERENTIABLE ARCHITECTURE SEARCH, ICLR2019

[2] Xuanyi Dong et al., Searching for A Robust Neural Architecture in Four GPU Hours, CVPR2019

[3] Jiemin Fang et al. ,Densely Connected Search Space for More Flexible Neural Architecture Search

[4] Xin Chen et al. ,Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation

[5] Yuhui Xu et al. ,PC-DARTS: Partial Channel Connections for Memory-Efficient Differentiable Architecture Search