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

NAS的原理是给定一个称为搜索空间的候选神经网络结构集合，用某种策略从中搜索出最优网络结构。神经网络结构的优劣即性能用某些指标如精度、速度来度量，称为性能评估，结构的性能评估将被返回给搜索策略。这一过程如下图所示。

NAS流程

在搜索过程的每次迭代中，从搜索空间产生“样本”即得到一个神经网络结构，称为“子网络”。在训练样本集上训练子网络，然后在验证集上评估其性能。逐步优化网络结构，直至找到最优的子网络。

搜索空间，搜索策略，性能评估策略是NAS算法的核心要素。搜索空间定义了可以搜索的神经网络结构的集合，即解的空间。搜索策略定义了如何在搜索空间中寻找最优网络结构。性能评估策略定义了如何评估搜索出的网络结构的性能。对这些要素的不同实现得到了各种不同的NAS算法。

搜索空间

搜索空间定义了NAS算法可以搜索的神经网络的类型，同时也定义了应该如何描述神经网络结构。神经网络所实现的计算可以抽象成一个无孤立节点的有向无环图（DAG），图的节点代表神经网络的层（卷积网络中的特征图），边代表数据的流动（进行的操作：卷积、池化等）。每个节点从其前驱节点（有边射入）接收数据，经过计算之后将数据输出到后续节点（有边射出）。理论上说，只要是无孤立节点的DAG，都是合法的神经网络结构。按照不同的尺度，神经网络的结构定义包含如下层次的信息：

（1）网络的拓扑结构。网络有多少个层，这些层的连接关系。最简单的神经网络是线性链式结构，其对应的图的每个节点最多只有一个前驱，一个后续，类似于数据结构中的链表。早期的全连接神经网络，卷积神经网络都是这种拓扑结构。Inception、ResNet、DenseNet中的节点允许有多个前驱，多个后续，从而形成了多分支、跨层连接结构，它们是更复杂的图。在描述网络的拓扑结构时，一般采用前驱节点来定义，即定义每个节点的前驱节点，一旦该信息确定，则网络拓扑结构确定。

不同的拓扑结构

（2）每个层的类型。除了第一个层必须为输入层，最后一个层必须为输出之外，中间的层的类型是可选的，它们代表了各种不同的运算即层的类型。典型有全连接，卷积，反卷积，可分离卷积，空洞卷积，池化，激活函数等。但这些层的组合使用一般要符合某些规则。

（3）每层内部的超参数。卷积层的超参数有卷积核的数量，卷积核的通道数，高度，宽度，水平方向的步长，垂直方向的步长等。池化层的超参数包含池化核高度，池化核宽度，水平方向步长，垂直方向步长。全连接层的超参数有神经元的数量。激活函数层的超参数有激活函数的类型，函数的参数（如果有）等。

为了提高搜索效率，有时候会搜索空间进行限定或简化。在某些NAS实现中会把网络切分成基本单元（cell），通过这些单元的堆叠形成更复杂的网络。基本单元由多个节点（神经网络的层）组成，它们在整个网络中重复出现多次，但具有不同的权重参数。另外一种做法是限定神经网络的整体拓扑结构，借鉴于人类设计神经网络的经验。这些做法虽然减少了NAS算法的计算量，但也限定了算法能够寻找的神经网络的类型。

由于描述神经网络结构的参数含有离散数据（如拓扑结构的定义，层的类型，层内的离散型超参数），因此网络结构搜索是一个离散优化问题。定义结构的参数数量一般比较大，因此属于高维优化问题。另外，对于该问题，算法不知道优化目标函数的具体形式（每种网络结构与该网络的性能的函数关系），因此属于黑盒优化问题。这些特点为NAS带来了巨大的挑战。

搜索策略

基于梯度的优化是目前的主流算法

强化学习和遗传算法等方案低效的一个原因是结构搜索被当作离散空间（网络结构的表示是离散的，如遗传算法中的二进制串编码）中的黑箱优化问题，无法利用梯度信息来求解。

DARTS将离散优化问题连续化，称之为可微结构搜索，将网络结构搜索转化为连续空间的优化问题，采用梯度下降法求解，可高效地搜索神经网络架构，同时得到网络的权重参数。

DARTS将网络结构、网络单元表示成有向无环图，对结构搜索问题进行松弛，转化为连续变量优化问题。目标函数是可导的，能够用梯度下降法求解，同时得到网络结构和权重等参数。算法寻找计算单元，作为最终网络结构的基本构建块。这些单元可以堆积形成卷积神经网络，递归连接形成循环神经网络。

将网络单元定义为有向无环图，共有N个顶点，顶点为数据的潜在表示，如卷积神经网络的特征图，图的边表示某种运算操作，对进行变换，然后将变换结果送入节点，典型的运算有卷积、池化、以及零运算（零运算是一种特殊的运算，它表示两个节点之间没有关系，即节点的值不会用来计算的值）。每个单元有2个输入节点，1个输出节点，对于卷积单元，输入节点为上两层的输出值。输出节点的值根据对所有中间节点进行约简运算（reduction operation，如concatenation）而得到。每个中间节点的值根据其所有前驱节点（编号更小的节点）计算得到，计算公式为：

接下来对问题进行松弛，转化为连续优化问题。对于某一网络结构，顶点到顶点的运算是确定的。将其概率化，表示为各种运算的概率叠加。假设表示为所有候选运算的集合，为作用于的某种运算，节点的值是各种候选运算的结果的概率叠加，而使用每种运算的概率用Softmax回归表示。计算公式为：

各种运算的概率叠加

其中，为操作混合权重向量，维度为，用于计算使用每种运算的概率值，如果定义变量：

则网络结构搜索问题可以转换为求解这些向量。得到这些向量的值之后即可确定网络解结构，在每个顶点处选择概率最大的运算作为该节点的运算：

这些向量可以看做是网络结构的编码表示。在将问题进行松弛之后，接下来的目标是同时求解网络结构以及所有混合运算所对应的权重。算法的目标是最优化验证集上的损失，采用梯度下降法。

假设分别为训练集和验证集上的损失，它们不仅与网络结构有关，还与网络参数权重有关。结构搜索的目标是寻找最优的结构以最小化验证集损失，而由此结构所决定的最优权重通过最小化训练集上的损失来确定：

因此该最优化问题是一个双层优化问题，为上层优化变量，为下层优化变量，因此该优化问题可以形式化地表述为：

精确求解上面的优化问题成本太高，只要有任何改变，都需要求解内层优化问题得到。DARTS进行了梯度近似，梯度下降时交替优化权重和结构，在第次迭代时，根据当前的结构，通过将向着使得训练误差最小化的方向移动得到，接下来固定，最小化在验证集上的损失得到新的网络结构，这一步的哟花目标为。

这里先对进行一次梯度下降迭代，为学习率，根据复合函数的求导法则，上面的目标函数对的梯度为

其中：

上面梯度计算公式的第二项为矩阵与向量的乘法，为了加快计算速度，用有限差分公式进行了近似。

算法流程：