NSGANetV2：使用进化算法和多目标代理的高效网络搜索算法

概述：

本文提出一种高效搜索方法，可以针对多种目标约束，搜索特定网络结构。具体来说，这种方法由两个代理组成，一个在网络结构级别，以提高采样效率，另一个在权值级别，通过一个超网络，以提高梯度下降的训练效率。通过NSGANetV2搜索模型，效果会和当时的SOTA模型持平或者更优，但是搜索的样本效率要高很多。在各个数据集上的表现，都取得了当时的SOTA效果。

解决的问题：

一般的NAS方法能在公开数据集上搜索出理想的网络结构，然而这些方法虽然在学术研究上表现良好，但是实际应用很困难。因为NAS如果需要落地或者说实际应用的话，一般都需要在自定义的数据集上，且需要优化多种目标（如：准确率、计算量、推理速度……），而且搜索时间也不能太久。上述这些恰好是NAS的软肋。论文提出的NSGANetV2就算为了解决这一问题。

简介

NAS的目标是获得最优网络结构及其相关的最优权值。NAS通常被视为一个双层优化问题，其中内部优化针对网络结构的权重（低层次），外部优化针对网络体系结构本身（高层次）。从计算资源消耗的角度来看，要获取一个网络最优的权值，在较低的层次采用随机梯度下降迭代造成的代价很大。由于网络是离散的，搜索的也粒度比较小，所以我们也不能用暴力穷举的方式。

为了提高NAS算法的效率，在低层次和高层次都提出了相应的优化算法，例如低层次的权重共享、使用代理模型等。但是这类方法并没有解决的问题是：我们还是需要采样大量的结构用来评估网络的效果。相比之下，人们很少关注高层次的采样效率，我们常用一个代理去预测低层次网络的性能，然后再引导上层的搜索空间。但是这些代理模型的采样效率仍然非常低，因为在训练代理模型时，也需要对低层次的网络结构进行大量采样，导致低效。

本文提出了一种方法，在高低两个层次同时采用显式代理模型。在低层次代理采用fine-tune的方法，加载超网的初始权值。高层次的代理值专注于搜索空间中最接近当前trade-off（网络表现和限制条件的权衡）的网络结构，而不是像之前一样随机采样网络结构。相比于随机采样的方法，NSGANetV2在高层次的采样的效率有大幅度提升，例如PNAS需要采样1W+的网络结构来训练上层代理，而本文提出的方法只需采样350个结构就可以达到相似的性能。

Key Points：

提出了一个解决双层NAS问题优化的替代方法，同时优化网络结构和最优模型的权值，采用的策略是使用代理（不是类似DARTS的连续松弛）。总的来说，我们可以给定一个数据集和一组需要优化的目标，NSGANetV2可以达到和DARTS一样高效的性能，而且搜出的网络结果要高于DARTS。对于NAS中的高层次优化，相比于其他的代理网络，采样效率更高。可扩展性和实用性更强，在不同的数据集上都取得了SOTA效果。

改进&创新点详述

低层次的代理：

首先说明一下设置低层次代理的目的：主要是为降低在低层次基于sgd的权重优化带来的的计算开销，因为每次权重优化都需要高层次采样一个网络结构，然后对网络结构进行权重的优化。当前主流的方法是：训练一个包含所有候选结构的超网，然后以超网的准确性作为评价标准，然而大量研究表明在预测阶段，基于权值共享的预测和从头开始训练然后预测的结果呈现一种弱相关性（也就是用权值共享的预测表现很好，我们拿这个结构从头开始炼丹，效果却并不好）。【因此，NSGANetV2使用从超网继承的权值作为底层优化的初始化，这样就在fine-tune的时候可以得到较好的初始化，同时提高了超网初始化权值与训练权值在性能上的相关性。】

高层次的代理：

总结一下，高层次的代理主要有以下几种方式：MetaQNN和PNAS都是用过代理来推测网络性能，注意这里是推测，而不是直接训练得到的网络结构的性能。但是推测的精度和实际精度相关性较差，因此最后搜出的网络很难是最优结构。此外，我们还可以使用一个代理模型来预测架构编码的准确性，例如OnceForAll，但是代理模型在整个搜索空间中是离线训练的，因此需要大量的样本进行训练，所以时间成本很高。或者我们可以像ChamNet一样，只在低层次训练很多网络结构，但只选择其中的300个代表性网络结构（具有不同的FLOPs、延迟等），然后用它们离线训练代理模型。【NSGANetV2采用的方法不同于上述方式，只采样接近我们权衡目标的网络（具备指定FLOPs、延迟等），训练代理模型采用online的方式，因为只专注于设置目标附近模型的优化，所以搜索样本的效率会大大提高。】

搜索方法：

论文将神经网络搜索问题归结为以下两层优化问题：

我们逐一介绍公式里的参数：α表示高层次的候选网络结构，w(α)表示低层次的网络结构的权重。L(w,α)表示网络结构α在训练集上的交叉熵损失。F是我们期望的目标：具体来说可以分成两组，第一组（绿框部分）由网络结构和权重组成，用验证集的表现来衡量。第二组（蓝框部分）只依赖于网络结构的目标，例如参数量、延迟等。

总体来说，两层优化可以描述为：首先在训练集上最小化指定网络结构α的损失函数，更新α的网络结构参数w*；然后根据得到的网络结构α和它对应的网络结构参数w*，更新我们的期望目标F。循环进行上述步骤，直至找到最优的目标。

搜索空间

设置搜索空间主要包括四个层面：网络深度（层数）、网络宽度（channel）、卷积核大小、分辨率。将整体的网络结构划分为5个串联的block，网络从浅到深特征图的高宽逐渐减小，维度逐渐增大。每个block中由不同数量的layer组成（2~4个），只有每个block的第一个layer可以降采样（stride=2），通过其他layer的输出分辨率保持不变。每个layer采用倒残差结构，需要搜索layer的第一个1*1卷积的扩展比，以及深度可分离卷积核的大小，输入分辨率大小的范围为192~256。使用整数字符串对网络结构编码，如下图所示：

网络搜索的部分在图中是虚线框表示，实线框是需要固定的网络配置。我们搜索的部分是：Block的层数（蓝色），可选的大小为[2,3,4]；DW卷积的卷积核大小（绿色），可选尺寸为[3,5,7]；每个layer的第一个卷积的扩展比（橙色），可选[3,4,6]；以及分辨率（黄色），可选范围[192, 256]。为了方便编码，如图(c)所示，如果每个block的layer数小于4个，就在后面填充0，保证编码的长度是不变的（灰色）。

整体算法描述

针对双层优化问题，我们首先要知道它的计算资源主要消耗在什么地方：首先，学习指定结构α的最优权重w，需要我们训练较长的时间，在ImageNet上一次完整的训练需要16个GPU Days。其次，即使我们使用权重共享策略，避免使用SGD学习权重的过程，采样时我们依然需要评估很多结构，同样需要几天才能完成搜索。为了克服计算时的弊端，论文在高、低层次都使用了代理模型。具体来说，在高层次，我们根据字符串结构编码中的准确率最高的结构构建模型，在搜索的过程中以online的方式迭代模型然后改进精度预测器。我们使用精度预测器是由从搜索空间中随机抽样的网络结构搭建而成的，然后使用多目标算法，通过构造的精度预测器和限制目标来搜索。然后，我们评估NSGA-II的搜索出的网络结构，并使用这些结构作为新的训练样本来完善准确率预测模型。

上图是NSGANetV2的算法流程图和具体的运行实例图。首先，我们需要定义搜索空间SS、超网Sw、多目标任务C（指定FLOPs、延迟等）、初始采样个数N和最大迭代次数K。然后，我们先从超网中采样N个网络结构，然后从超网中得到α的权重Wo，然后加载权重Wo使用SGD训练α得到准确率ACC，将结构α和其对应的准确率acc添加到集合A中（这一步如图(a)所示）。接下来，我们通过集合A构建代理模型Sf，利用我们的多目标任务C得到新的候选网络结构α~（这一步如图(b所示)）。我们把新选择的α~也添加至原先的网络结构α中，使得候选子集的帕累托前沿多样化（这一步如图(c)(d)所示）。最后我们评估候选结构，把它的网络结构α和对应准确率acc一起添加到原先的集合A中（这一步如图(e)所示）。

高层次优化效率的提高

因为双层优化问题的固有性质，导致了高层次的优化需要消耗大量计算资源，因为每个高层次的更新都需要在低层次进行再次优化。因此，为了提高效率，需要减少我们网络结构采样的数量。为了实现这个目标，我们需要一个代理模型预测网络结构的准确性，这个模型要确保两件事：首先，预测的准确率和模型的真实表现强相关，其次，要使得采样网络结构的数量最少。作者通过调研和消融实验中发现，准确率预测代理模型主要有四种：MLP,CART,RBF,GP，此前的这四种预测器都不能同时确保做到以上两点。因此，论文提出了自适应切换（AS）机制，在每次迭代时构建所有四种代理模型，并通过交叉验证自适应地选择最佳模型，使用AS机制可以同时优化精度和用户自定义的其他搜索目标。

具体来说，假设我们需要将FLOPs作为搜索目标之一，还是看上面的算法整体流程图。首先在第一次搜索结束后，输出一组结构，如图(b)所示；因为我们不能暴力地选择所有结构，所以首先选择一个精度最高的网络结构（图b中最左上角的蓝点），然后我们将其所有的候选结构都投影到FLOPs的坐标中，也就是图(c)中棕色的点；然后选择其中部分候选结构（图d中的绿点），扩展FLOPs结构。然后将来自所选子集的体系结构发送到较低级别使用sgd训练。最后，我们将这些网络添加到训练的总样本中，并继续进行下一次迭代，如图3(e)所示。

从上面第一行图可以看出，使用AS机制（红线）比其他四种机制的相关性系数高（越高越好）。从下面一行图可以看出，AS机制（红色）的训练和预测模型的准确率更加相关（越贴近对角线越好，分布越集中越好）。

低层次优化效率的提高

其实这里就是采用权重共享的方法，首先我们选择一个超网，所有的候选结构都隶属于它的子网结构。然后将超网的超参数（block重复次数、扩展比、卷积核大小等参数）都设置为最大值，然后对超网训练，这样子网就可以使用超网的权值。

通过高、低两个层次的效率优化，可以看出NSGANetV2(也就是图中的MSuNAS)在推理速度上相较于其他使用代理的NAS搜索方法有了很大的提升，无论是ImageNet还是CIFAR-10数据集上的都能奏效，也证明了论文开头提出的：该方法适合用户自定义的不同的数据集的观点。

实验结果

通过上表中NSGANetV2和不同的分类网络的对比，可以看出，其在各个大小的分类网络中，在ImageNet上的准确率都达到了SOTA水准。且除了最小的模型在推理速度上略低于MobileV2以外，其他大小的模型的推理速度也是最快的。

上图是NSGANetV2在不同数据集上准确率和精度与其他网络的对比：第一行是各个网络的精度，第二行是各个网络的准确率。可以看到，NSGANetV2（红色）在ImageNet上无论是精度还是准确率，都达到了SOTA水准，在CIfar数据集中的表现也是数一数二的。