本工作通过贪心的搜索方式减轻了NAS中模型排名在搜索和最后评估不一致的问题。是一种更优更快的网络结构搜索算法，并同时支持CNN和GCN的搜索。代码已开源，想在图像，点云，生物图数据上做网络结构搜索的同学都可以试一试。

Code: https://github.com/lightaime/sgas

Arxiv: https://arxiv.org/abs/1912.00195

Project webpage: https://www.deepgcns.org/auto/sgas

相关工作

网络结构搜索（Neural Architecture Search， 简称NAS) 是一种神经网络结构自动化设计的技术。NAS基于相应算法在特定的样本集内自动设计出高性能的网络结构。这些自动搜索出的网络结构在某些任务上已经媲美或超过了人类专家手工设计的网络结构。

早期NAS的算法是基于强化学习（Zoph et al.[1]）或进化算法（Real et al.[2]）。这些算法计算成本高昂，阻碍了其广泛应用。 近来，Liu et al.[3]提出了一种高效的可微分的网络结构搜索算法：可微分网络结构搜索（Differentiable Architecture Search, 简称DARTS）。DARTS的提出使得网络结构搜索在单卡一天内完成搜索。后续许多工作都基于DARTS基础上进行改进，比如SNAS，FBNet，ProxylessNAS，P-DARTS，GDAS，MdeNAS，PC-DARTS，FairDARTS等等。

背景知识：DARTS

DARTS采用基于单元(Cell)的搜索方法进行网络结构搜索。Cell是一个网络子模块，可以自由堆叠多次形成卷积网络。DARTS通过学习cell的结构，完成对网络的结构搜索。Cell是由N个节点的有序序列组成的有向无环图(如图1)。 Cell中每个节点x^(i)是卷积网络中的特征图，每个有向边（i，j）代表一种对x的运算o(i, j) （如3x3的卷积）。 一个cell具有两个输入节点，一个输出节点和多个中间结点。 Cell的输入节点被定义为前两层的输出。 Cell的输出是对所有中间节点进行归约运算（例如concatenation）后的结果。每个中间节点由它之前结点经过算子op变换后相加得到：

DARTS为了实现可微搜索，提出了搜索空间的continuous relaxation机制，利用softmax函数来学习所有可能候选运算op的权重：

其中，$\mathcal(O)$ 表示搜索空间中的候选运算（例如卷积，最大池化，零）等，零表示没有运算（边）。 其中一对节点（i，j）之间的运算由向量\alpha_{i, j}参数化。运算的结果是每种可能运算结果的加权求和。向量\alpha_{i, j}的维度为搜索空间长度|O|。因而，DARTS将网络结构搜索的任务简化为了学习一组连续变量\alpha= {\alpha(i, j)}，如图1所示。DARTS在搜索结束阶段，通过argmax得到权重最大的候选运算op当作该边的搜索结果：

图1 DARTS的单元结构以及网络结构搜索示意图[3]

DARTS存在的部分问题

一般NAS的流程是分为搜索阶段和评估阶段，在训练集与验证集上进行结构的搜索（搜索阶段），然后在测试集上进行模型的评估（评估阶段）。DARTS在搜索结束的阶段直接得到网络结构，如图1和公式3所示。 这种策略导致在搜索和评估阶段派生的网络结构的性能相关性非常低。网络在搜索阶段的效果，并不能反映其在评估阶段的真实效果。我们将这种现象称之为：退化的搜索评估相关性（degenerate search-evaluation correlation）。我们认为造成这种想象的主要原因是：（1）搜索阶段和评估阶段设置的不一致性；（2）权重共享（weight sharing）造成的副作用。

举个例子：假设我们只搜索3种候选运算，skip-connect，3x3卷积，5x5卷积。如果搜索时分配的权重分别是skip-connect （0.34），3x3卷积（0.33），5x5卷积（0.33），最后所选的操作会是没有可学习参数的skip-connect，如果所有的边都是这种情况，那么最后的网络在评价阶段性能就会很差，然而在搜索阶段这个网络和权重分配为skip-connect （0.33），3x3卷积（0.34），5x5卷积（0.33），最后会得到3x3卷积的网络性能几乎不会有区别。这一现象并不仅仅发生在DARTS上，也发生其他大部分NAS算法上，这严重影响了NAS的性能。

肯德尔系数\tau[4]可用于量化搜索评估相关性（ search-evaluation correlation）。肯德尔系数介于-1到1，-1表示完全负相关，1表示完全正相关。 如果肯德尔系数为0，则分布完全独立。理想的NAS方法应具有较高的搜索评估相关性\tau。 我们以DARTS 为例， 在CIFAR-10数据集上运行10次，分别根据搜索准确性和最终评估准确性排名，计算其肯德尔系数。 一阶和二阶的DARTS的肯德尔系数分别仅为0.16和-0.29。 因此，DARTS算法的搜索评估相关性极低，无法根据DARTS在搜索阶段的效果预测模型测试阶段的准确性。

图2 搜索-测试相关性可以用肯德尔系数衡量。 常见的NAS算法，如DARTS，肯德尔系数低，无法根据其搜索阶段对最终测试的准确性做出可靠的预测。

SGAS详细方案

针对退化的搜索评估相关性这一重要的问题，我们提出了SGAS（Sequential Greedy Architecture Search），一种顺序贪心决策的搜索算法。图2 SGAS的网络结构搜索示意图我们基于贪心算法的思想将网络结构的搜索问题，转化为逐步地选择一条边并确定其运算的子问题。实验证明，依次解决这些简单的子问题，可以让最终结构具有更高的搜索-测试相关性。算法的迭代过程如算法1所示。

在每个决策时期，我们根据预先确定的选择标准选择一条边(i^{+}, j^{+})。通过用公式(3)得到这条边的运算，并替换相应的混合运算o^{\bar}。所选择的运算，即是所选的边基于贪心的最优选择。每当确定好一条边的运算，我们就不再需要这条边的结构参数\alpha(i^{+}, j^{+}))以及混合操作中其余路径的权重，我们可以将这条边从后续的优化中去除。这样可以带给我们一个额外的好处是：优化问题得到了剪枝，进而可以提高搜索的效率。一条边被剪枝后，剩下的超网络以及参数形成一个新的子问题，该子问题将被以相同的算法迭代求解。在搜索阶段的最后，便得到一个没有权重共享的离散子网络，如图2所示。SGAS算法基于顺序贪心算法，减少了在搜索阶段和评价阶段的模型不一致性和权重共享的副作用，使得模型的搜索-测试相关性最大化。

在SGAS中，选择标准的设计至关重要。我们考虑影响边的选择的三个重要因素：边的重要性，选择确定性和选择稳定性。

边的重要性：如果这条边的非零运算选择的可能性越高，表明这条边越重要。

选择确定性：熵（entropy）是分布用度量不确定性的常。 非零运算的归一化权重可以看作是一种分布：

我们将选择确定性定义为一减去操作分布的归一化熵：

选择稳定性：为了让选择更稳定，我们需要考虑选择确定性的历史分布。直方图相交[48]是检测分布变化的常用方法，我们利用直方图相交来计算第T步中的前K时间的边的平均选择稳定性：

根据这三个影响边选择的三个因素，我们提出了两个选择指标：

指标1 ：具有高的边重要性和高的边确定性的边将被选择，公式为：

指标2：在指标1的基础上，被选择的边也应该具有较高的稳定性：

这里，normalize(·) 指 Min-Max标准化。

实验结果

我们搜索了CNN和GCN网络结构，并在CIFAR，ImageNet图像分类，ModelNet点云分类，PPI生物图数据节点分类上达到了SOTA效果。

CNN

我们将SGAS用到CNN的网络结构搜索中， CNN网络结构由普通单元(normal cell) 和 归约单元(reduction cell)组成。普通单元保持特征图大小不变，归约单元缩小特征图至½. CNN任务中，搜索空间由8个运算组成：skip-connect, max-pool-3×3, avg-pool-3×3, sep-conv-3×3, sep-conv5×5, dil-conv-3×3, dil-conv-5×5, zero。

SGAS在CIFAR-10的训练集与验证集搜索结构，并在测试集上进行测试，结果如表1所示：

SGAS在CIFAR-10的训练集与验证集搜索结构，并在ImageNet测试集上进行测试，结果如表2所示：

我们的SGAS在性能超越了手工设计的网络结构以及其他NAS算法。

GCN

我们是同时将SGAS用到GCN的网络结构搜索中的。 GCN网络结构由普通单元(normal cell) 组成。其搜索空间由10个运算组成：conv-1×1, MRConv, EdgeConv, GAT, SemiGCN, GIN, SAGE, RelSAGE, skip-connect, and zero operation。

SGAS在ModelNet10的训练集与测试集搜索结构，并在ModelNet40训练集和测试集上进行训练与测试，结果如表3所示：

我们也将SGAS应用到生物信息图的结点预测上。我们在PPI (protein protein intersection) 数据集的训练集与验证集搜索结构，并在PPI的训练集和测试集上进行训练与测试，结果如表4所示：

我们SGAS在GCN上的实验，超越了之前最好的模型。我们在ModelNet40以及PPI数据集上成为了新的state-of-the-art. 

更多的结果与分析可以阅读我们的论文https://arxiv.org/abs/1912.00195（包含附录）， 访问我们的项目网页 https://www.deepgcns.org/auto/sgas或 参考我们的开源代码 https://github.com/lightaime/sgas。 

[1] Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint arXiv:1611.01578, 2016.

[2] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4780–4789, 2019.

[3] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.09055, 2018.

[4] Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81–93, 1938.