DARTS: Differentiable Architectu

2019-07-22 本文已影响0人斯文攸归

深度学习可以自动学习出有用的特征，脱离了对特征工程的依赖，在图像、语音等任务上取得了超越其他算法的结果。这种成功很大程度上得益于新神经网络结构的出现，如ResNet、Inception、DenseNet等。但设计出高性能的神经网络需要大量的专业知识与反复试验，成本极高，限制了神经网络在很多问题上的应用。神经结构搜索（Neural Architecture Search，简称NAS）是一种自动设计神经网络的技术，可以通过算法根据样本集自动设计出高性能的网络结构，在某些任务上甚至可以媲美人类专家的水准，甚至发现某些人类之前未曾提出的网络结构，这可以有效的降低神经网络的使用和实现成本。NAS的原理是给定一个称为搜索空间的候选神经网络结构集合，用某种策略从中搜索出最优网络结构。神经网络结构的优劣即性能用某些指标如精度、速度来度量，称为性能评估。

摘要

本文提出通过可微的方式来解决神经网络结构搜索的问题。前人的网络搜索方法，要么是基于强化学习的，要么是基于遗传算法的，都是非常耗时的，最近的几个算法表示他们的计算时间可能需要：1800 GPU days 以及 3150 GPU days，上述算法都是在不可微或者离散的空间中求解，本文的方法基于架构表示的连续空间，允许使用梯度下降有效地搜索架构。在CIFAR-10，ImageNet，Penn Treebank和WikiText-2上进行了大量实验，表明本文的算法擅长于发现用于图像分类的高性能卷积结构和用于语言建模的循环神经网络结构，同时比现有技术的非微分搜索技术要快几个数量级。

介绍

发现最先进的神经网络架构需要人类专家的大量工作。最近，人们越来越有兴趣开发自动化算法解决神经网络结构的设计。自动搜索架构在诸如图像分类和目标检测任务上有着优异的性能。

尽管具有卓越的性能，但现有的最佳架构搜索算法在计算上要求很高。在CIFAR-10和ImageNet上获得最好的神经网络结构，采用增强学习需要2000 GPU days，采用遗传算法需要3150 GPU days。也有一些人提出了加速方法：例如强加搜索空间的特定结构，对每个单独架构的权重或性能预测，以及跨体系结构的权重共享，但可扩展性的根本问题依然存在。主流方法（RL, evolution, MCTS, SMBO,Bayesian optimization）低效率的原因在于：他们将结构搜索这个任务当做是一个离散领域的黑盒优化问题，从而导致需要评价大量的结构。

本文另辟蹊径，提出DARTS（Differentiable Architecture Search）。不再搜索一组离散的候选架构，而是将搜索空间放松至连续，从而可以通过梯度下降的方法对神经网络结构在验证集上的性能进行优化。因为基于梯度的优化，与低效的黑盒搜索不同，使得DARTS使用比现有技术数量级较少的计算资源实现同具竞争力的表现。它也优于另一种最近的高效架构搜索方法：ENAS，值得注意的是，DARTS比许多现有方法简单，因为它不涉及任何controllers、hypernetworks，或表现预测因子。

在一个连续的领域内搜索体系结构的想法并不新鲜，本文与先前的工作有几个主要区别在于：

1、虽然之前的工作试图对结构的特定方面进行微调，如卷积网络中的卷积核形状或分支模式，但是DARTS能够在丰富的搜索空间内发现具有复杂图形拓扑的高性能架构。

2、DARTS不限于任何特定架构，能够搜索卷积神经网络和循环神经网络。

在实验中，DARTS能设计一个在CIFAR-10分类数据集上测试误差为 $2.76\pm 0.09$ %，参数量为 $3.3M$ 的卷积单元，与regularized evolution的方法相比，表现相当，但是后者使用的计算资源是前者的三倍。同样的卷积单元在ImageNet数据集上实现了 $26.7$ %的 $Top_1 Error$ ，同样与强化学习最好的方法相当。在语言模型任务上，DARTS发现了一个循环单元，在Penn Treebank上达到了55.7的测试 perplexity，由于现有的LSTM模型和所有自动结构搜索（NAS&ENAS）得到的模型。

总结起来，贡献有四：

1、引入了一种适用于卷积和循环结构的可微分网络结构搜索的新算法；

2、实验表明本文的方法具有很强的竞争力（CIFAR-10&PTB）；

3、实现了卓越的结构搜索效率（4个GPU：1天内CIFAR-10误差2.83％; 6小时内PTB误差56.1），这归因于使用基于梯度的优化而非非微分搜索技术；

4、证明 DARTS 在 CIFAR-10 和 PTB 上学习的网络结构可以迁移到 ImageNet 和 WikiText-2 上

可微结构搜索

在第一部分，用一般形式描述搜索空间，其中结构（或其中的单元cell）的计算过程被表示为有向无环图。在第二部分，为搜索空间引入一个简单的连续松弛方案，使得架构及其权重的联合优化目标可微。在第三部分，提出了一种近似技术，使算法在计算上可行和高效。

搜索空间

根据前人的工作，搜索一个计算单元（cell）作为最终架构的构建块，学习的单元可以堆叠以形成卷积网络，或者递归地连接以形成循环网络。单元是 $N$ 个有序节点构成的有向无环图，每个节点 $x^{(i)}$ 都是一个Latent Representation（如卷积神经网络中的特征图），每个有向边 $(i,j)$ 是对节点 $x^{(i)}$ 的某种运算操作 $o^{(i,j)}$ ，假设每个单元有两个输入节点和一个输出节点，对于卷积单元来说，输入节点被定义为前两层的单元输出；对于循环神经网络，输入节点被定义为当前时间步的输入以及上一时间步中的隐藏状态。通过对所有中间节点应用reduction操作（例如concatenation）来获得单元的输出。

每个中间节点都是基于所有它之前的节点进行计算的： $x^{j}=\sum_{i<j}o^{(i,j)}(x^{(i)})$

特殊的零操作指示两个节点之间缺少连接。因此，学习单元的任务减少了学习其边缘的操作。

连续的放松和优化

令 $O$ 表示候选操作的集合（如卷积，池化，或者零操作），每个操作都代表应用于 $x^{(i)}$ 的一些函数 $o(\cdot )$ ，为了令搜索空间连续，将特定操作的分类选择放宽到所有可能操作的softmax：

其中一对节点 $(i,j)$ 的操作混合权重由向量 $\alpha ^{(i,j)}$ （维数为 $\vert O \vert$ ）参数化表示，结构搜索任务简化为学习一系列连续的变量 $\alpha =(\alpha ^{(i,j)} )$ ，在搜索的最后，通过将每个混合操作替换为最可能的操作 $o^{(i,j)}=argmax_{o\in O} \alpha _{o}^{(i,j)}$ ，下面将用 $\alpha$ 来表示结构的编码。

在放松得到连续的优化空间之后，我们的目标是同时学习网络结构 $\alpha$ 和所有混合操作的权重 $w$ （例如卷积神经网络卷积核的权重），在强化学习和遗传算法中，验证集上的表现被视为奖励或者拟合程度。DARTS用梯度下降来优化验证损失。

DARTS的算法流程

在上图 $(a)$ 中，每条边上的操作初始化为未知的；图 $(b)$ 中，将候选操作的混合放置于每条边以此来进行放松使得搜索空间连续；图 $(c)$ 中，通过求解双层优化问题联合优化混合概率和网络权重；图 $(d)$ 中，从学习的混合概率中得到最终的结构。

用 $L_{train} ,L_{val}$ 分别代表训练和验证损失，上述损失不仅由结构 $\alpha$ 定义，也由网络中的权重矩阵 $w$ 定义，网络搜索的目标是找到某一结构 $\alpha ^*$ 使得验证损失 $L_{val}(w^*,\alpha ^* )$ 最小化，意即 $\alpha ^* =argmin_\alpha L_{val}(w^*,\alpha )$ ，与结构相关的权重 $w^*$ 通过最小化训练损失得到： $w^* =argmin_w L_{train}(w,\alpha ^* )$ 。

这是一个双层优化问题， $\alpha$ 是上层变量， $w$ 是下层变量：

$min_{\alpha } L_{val}(w^*(\alpha ),\alpha )$

$s.t. \quad w^*(\alpha ) =argmin_{w}L_{train}(w,\alpha )$

嵌套公式也出现在基于梯度的超参数优化中，这在某种意义上是相关的，即架构 $\alpha$ 可以被视为一种特殊类型的超参数，尽管它的维度远远高于标量值超参数，例如学习率，并且它更难以优化。

算法1：DARTS：

建立一个混合操作，由边 $(i,j)$ 的向量 $\alpha ^{(i,j)}$ 参数化得到：

如果没有收敛：

就以下式更新结构 $\alpha$ （理论上，权重应该已达最优，此处为近似表达）

梯度下降更新

\alpha

再以下式更新权重 $w$ （对于确定的结构 $\alpha$ ，更新权重）

梯度下降更新

w

收敛之后由学习到的 $\alpha$ 得到最后的网络结构。

估计结构梯度

由于昂贵的内部优化，准确地评估架构梯度可能是令人望而却步的，因此提出一个简单的梯度估计：

梯度估计

或者表示为：

在 $step \quad k$ ，给定当前的结构 $\alpha _{k-1}$ ，我们通过朝向降低训练损失的方向去移动 $w_{k-1}$ 来得到 $w_{k}$ 。然后，保持权重 $w_{k}$ 不变，去更新网络结构，使其可以最小化验证集损失：

验证集损失

$w$ 代表算法使用的当前权重， $\xi$ 代表内部优化的学习率，用权重 $w$ 一个训练步骤的更新来估计最优权重 $w^*(\alpha )$ ，而不是训练直到收敛以完全求解内部优化问题。如果 $w$ 已经达到局部最优，上式将会退化为：

退化表达

虽然我们目前还不能指出该优化算法的收敛性，但在实践中它能够通过合适的 $\xi$ 达到一个固定的点。当动量被用于权重优化时，上式中的一步展开学习目标被相应地修改，并且我们的所有分析仍然适用。

应用链式法则：

上述梯度估计为：

链式法则展开式

由于链式法则展开后的第二项将涉及到矩阵内积运算，计算非常昂贵，因此采用有限差分近似来降低复杂度：

有限差分近似

其中：

推导

评估该有限差分仅需要两次前向传播即可得到 $w$ ，两次反向传播，就可以得到 $\alpha$ ，运算复杂度大大的降低了：由 $O(\vert w \vert \vert \alpha \vert )$ 降低为 $O(\vert w \vert +\vert \alpha \vert )$ 。

一阶估计：

当内部优化学习率 $\xi =0$ 时，二阶导数将消失，此时，关于结构 $\alpha$ 的梯度将由下式给出：

一阶情况

意即假设当前步的权重 $w$ 就是 $w^*(\alpha )$ ，这会带来速度的提升，但是性能会下降。

迭代算法的学习表现

当 $L_{val} (w,\alpha )=\alpha w-2\alpha +1$ 和 $L_{train}(w,\alpha ) =\alpha ^2-2\alpha w+w^2$ 时，从 $(\alpha ^{(0)},w^{(0)})=(2,-2)$ 开始优化，两层优化问题的理论最优解为 $(\alpha ^*,w^*)=(1,1)$ ，红色虚线表示精确满足双层优化数学描述的可行组，上图表明一个合适的学习率 $\xi$ 将有助于收敛到较好的局部最优点。

推导离散结构

为了在离散架构中形成每个节点，我们保留从所有先前节点收集的所有非零候选操作中的前 $k$ 个强度最高的操作（来自不同节点），强度定义为：

强度定义

对于卷积单元，设置 $k=2$ ，对于循环单元，设置 $k=1$ 。

意即：为每个中间节点保留 $k$ 个最强的前导，其中边的强度定义为上式；通过采用argmax将每个混合操作替换为最可能的操作。

要将零操作去除的原因是：首先，我们需要每个节点恰好有 $k$ 个非零入射边，以便与现有模型进行公平比较；其次，零操作的强度是不确定的，因为增加零操作的logits仅影响结果节点表示的规模，并且由于存在批量规范化而不影响最终的分类结果。

实验和结果

在CIFAR-10和PTB数据集上的实验包含两个部分：结构搜索和结构评估，在第一阶段，使用DARTS搜索单元体系结构，并根据其验证性能确定最佳单元；在第二阶段，使用这些单元构建更大的架构，从头开始训练并在测试集上评估它们的性能。同时还分别通过在ImageNet和WikiText-2（WT2）上评估它们来研究在CIFAR-10和PTB上学习的最佳单元的可迁移性。

结构搜索

CIFAR-10上的结构搜索

操作集合 $O$ 中包含 $3\times 3$ 和 $5\times 5$ 可分离卷积， $3\times 3$ 和 $5\times 5$ 的空洞可分离卷积， $3\times 3$ 最大池化， $3\times 3$ 平均池化，恒等映射和零操作。所有步长均为1，填充卷积特征图以保持其空间分辨率。使用ReLU-Conv-BN顺序进行卷积运算，每个可分离卷积总是应用两次。

一个卷积单元包含7个节点，其中输出节点被定义为所有中间节点（排除输入节点）的深度级联（concat）。然后通过将多个单元堆叠在一起形成网络。单元 $k$ 的第一和第二个节点设置为单元 $k-1$ 和单元 $k-2$ 的输出，必要时插入 $1\times 1$ 卷积。在网络深度 $1/3$ 和 $2/3$ 处的单元是降采样单元，与输入节点相邻的所有操作的步长设置为2。因此网络表示为 $(\alpha _{normal} ,\alpha _{reduce})$ ，其中所有正常单元共享 $\alpha_{normal}$ ，所有下采样单元共享 $\alpha_{reduce}$ 。

PTB上的结构搜索

所有可能的操作集合中包含：线性变换+ $tanh$ ，线性变换+ $relu$ ，线性变换+ $sigmoid$ ，恒等映射，零操作。

循环单元包含12个节点，通过对两个输入节点进行线性变换来获得第一中间节点，结果相加后通过 $tanh$ 激活函数。并通过一个旁路来增强每个操作，单元输出定义为所有中间节点的平均值，在进行结构搜索时启用BN，以防止出现梯度爆炸，在测试网络结构时禁用BN。循环网络只包含一个单元，即不会在循环结构中假设任何重复模式。

Normal Cell Learned on CIFAR -10

Reduce Cell Learned on CIFAR-10

Recurrent Cell Learned on PTB

结构评估

为了确定最终评估的体系结构，使用不同的随机初始化运行DARTS四次，并根据其在短时间内从头开始训练获得的验证性能选择最佳单元（100 epochs on CIFAR-10 and 300 epochs on PTB）。（循环单元的优化结果对初始化很敏感）

为了评估所选择的架构，我们随机初始化其权重（在搜索过程中学习的权重被丢弃），从头开始训练，并在测试集上报告其性能。注意，测试集从未用于架构搜索。

CIFAR-10

PTB

ImageNet

结果分析

为了更好地理解双层优化的必要性，本文研究了一种简单的搜索策略， $\alpha ，w$ 在训练验证联合数据集上使用协同过滤进行联合优化，这样最好的卷积单元测试错误率为 $4.16\pm 0.16$ %，参数量为 $3.1M$ ，比随机搜索要差。在第二个实验中，在训练验证联合数据集上使用SGD同时优化 $\alpha, w$ ，这样最好的卷积单元测试错误率为 $3.56\pm 0.10$ %，参数量为 $3.0M$ 。猜想是因为这些启发式方法会导致结构 $\alpha$ 过度（类似于超参数）拟合训练数据，从而导致较差的泛化。请注意， $\alpha$ 未在DARTS中的训练集上直接优化。

值得注意的是，随机搜索在卷积模型和循环模型上表现都很良好，这反映了搜索空间设计的重要性。

实验细节：

在CIFAR-10上的结构搜索：

由于架构在整个搜索过程中会有所不同，因此始终使用批量特定的统计信息进行批量标准化而不是全局移动平均值。在搜索过程中禁用所有批量标准化中可学习的仿射参数，以避免重新调整候选操作的输出。

为了进行结构搜索，将一半的CIFAR-10训练数据作为验证集，8个单元的小网络以DARTS训练50轮，batch_size=64，初始通道数为16，优化 $w$ ，初始化学习率 $\eta _w=0.025$ ，在没有重启的情况下按照余弦计划退火到零，对结构变量进行零初始化（对于正常单元和降采样单元中的 $\alpha$ ），这意味着在所有可能的操作上都会有相同的注意力（在采用softmax之后）。在早期阶段，这确保了每个候选操作中的权重以接收足够的学习信号（更多探索）。使用Adam算法来优化 $\alpha$ ，初始化学习率 $\eta_{\alpha}=0.0003$ ，结构搜索在单GPU上需要一天。

在CIFAR-10上的结构评估：

有20个单元的大网络以batch_size=96训练600轮，通道数初始化为36，使用了一些增强如cutout，path dropout，auxiliary towers with weight 0.4，训练在单GPU上需要1.5天，由于即使设置完全相同，CIFAR结果也会出现很大的差异，因此报告了完整模型的10次独立运行的平均值和标准差。