自动化机器学习（AutoML）最近变得越来越火，是机器学习下个发展方向之一。其中的神经网络结构搜索（NAS）是其中重要的技术之一。人工设计网络需要丰富的经验和专业知识，神经网络有众多的超参数，导致其搜索空间巨大。NAS即是在此巨大的搜索空间里自动地找到最优的网络结构，实现深度学习的自动化。自2017年谷歌与MIT各自在ICLR上各自发表基于强化学习的NAS以来，已产出200多篇论文，仅2019年上半年就有100多篇论文。此系列文章将解读AutoDL领域的经典论文与方法，笔者也是刚接触这个领域，有理解错误的地方还请批评指正！

本次介绍的两篇论文是谷歌的《Efficient Neural Architecture Search via Parameter Sharing》和自动化所、图森的《You Only Search Once: Single Shot Neural Architecture Search via Direct Sparse Optimization》。一般自动生成的网络模型庞大而冗余，且搜索过程耗时耗力，这次的论文是用权值共享的办法来加速模型搜索。

一、Efficient Neural Architecture Search via Parameter Sharing

1、总览

这篇论文也是基于NAS的框架，对其进行了改进，称之为ENAS。NAS搜索到的图是一个更大的图的子图，也就是说NAS的搜索空间可以用一个有向无环图（DAG）来表示。下图给出了一个例子：

上面的图是整个搜索空间，红色的线连起来的子图是控制器发现的模型。ENAS的DAG是NAS搜索空间里所有可能子模型的叠加，图中的结点表示具体的计算操作，边表示信息流动。每个节点都有其自己的参数，这些参数在所有的子模型中都可以共享。其实ENAS要学习的就是节点之间的连线关系，通过不同的连线产生大量的模型。

2、生成RNN的cell

为了生成RNN的cell，作者使用一个有N个节点的DAG。ENAS的控制器是个RNN，它决定两个方面：（1）哪个边被激活；（2）DAG中的结点选择哪种操作。原NAS论文里的RNN生成，cell的结构被固定为二叉树结构，只决定树上每个节点的操作。而这里ENAS即设计节点操作也设计cell的结构。以下图为例说明控制器生成cell的过程：

假设有N=4个节点，$x{t}$是cell的输入，$h{t-1}$是前一个时间步的输出。采样过程如下：

• 在节点1：控制器采样一个激活函数。图中例子选择了tanh，那么节点1的计算为$h{1}={rm tanh}(x{t} cdot W^{x}+h{t-1} cdot W{1}^{h})$
• 在节点2：控制器采样之前节点的编号和激活函数。例子中选择了编号1和ReLU，则节点2的计算为$h{2}={rm ReLU}(h{1} cdot W_{2,1}^{h})$
• 在节点3：控制器再次采样之前节点的编号和激活函数。例子中选择了编号2和ReLU，则节点3的计算为：$h{3}={rm ReLU}(h{2} cdot (W_{3,2}^{h}))$
• 在节点4：控制器再次采样之前节点的编号和激活函数。例子中选择了编号1和tanh，则节点3的计算为：$h{4}={rm tanh}(h{1} cdot (W_{4,2}^{h}))$
• 对于输出，将那么没有被选做其他任何节点输入的结点取平均。例子中，节点3和节点4没有被选为其他节点的输入，那么$h{t}=(h{3}+h_{4})/2$

在上面的例子中可以看出，对于每个节点对$j<l$都有独立的参数矩阵$W_{l,j}^{h}$，通过选择前面节点的彪悍，控制器也选择了使用哪个参数矩阵，因此搜索空间里所有的cell都共享同样的参数集合。如果一个cell有N个节点，选择4种激活函数（tahn，ReLU，identity，sigmoid），那么搜索空间有$4^{N} times N!$种配置。

3、训练ENAS、导出网络结构

这里控制器LSTM有100个节点，通过softmax分类器进行采样。在ENAS中，有两类需要学习的参数：控制器LSTM的参数$theta$和子模型共享的参数$omega$。训练过程也包括两个阶段，第一个阶段用整个数据集训练$omega$，第二个阶段是训练$theta$，两个阶段轮流训练，具体细节如下：

• 训练$omega$。这步中，控制器的策略$pi(m;theta)$被固定，用SGD去最小化交叉熵损失函数${Bbb E}{m ~ pi}[L(m{i}, omega)]$，$m$是从$pi (m; theta)$中采样得到的一个模型。梯度使用蒙特卡洛估计： $$ nabla{omega} mathbb{E}{mathbf{m} sim pi(mathbf{m} ; theta)}[mathcal{L}(mathbf{m} ; omega)] approx frac{1}{M} sum{i=1}^{M} nabla{omega} mathcal{L}left(mathbf{m}_{i}, omegaright) $$ 上式是对梯度的无偏估计，有较大的方差。但作者发现当$M=1$的时候效果就比较好，也就是说使用从$pi (m; theta)$采样到的任意一个模型$m$上计算到的梯度就可以更新$omega$。
• 训练参数$theta$。在这步中固定$omega$来更新$theta$，以最大化期望奖励${Bbb E}_{m ~ pi(m; theta)}[mathcal R(m, omega)]$。奖励$mathcal R(m,omega)$是在验证集上计算得到的。
• 导出网络结构。首先从训练的策略$pi (m, theta)$采样几个模型，对于每个采样的模型，直接在验证集上计算奖励，然后选择奖励最高的模型从头训练。实际上这个过程会进行很多次，共享的权重也会在一段时间后更新。

4、设计卷积网络

在生成CNN时，控制器作出两个方面的决定：（1）连接前面的那个些节点；（2）使用哪种操作。这两个决策构造了一个卷积层。选择连接到前面的那些节点可以用来产生跨连接，在第$k$层，前面最多有$k-1$个可选的结点，这会有$2^{k-1}$种可能的决策。举例如下图：

上图中，在第$k=4$层，控制器选择了前面的第1、3个节点，所以第1、3层的输出在深度这个轴连接起来送到第4层。

对于可选的操作，一共有6种：3×3大小卷积、5×5大小卷积、3×3大小的可分离卷积、5×5大小可分离卷积、3×3的最大池化、3×3的平均池化。做这样的决策一共L次，可以得到一个L层的网络，在搜索空间里一共有$6^{L} times 2^{L(L-1)/2}$种网络。

5、设计卷积cell

上述的搜索是从头搜索整个网络，也称作macro搜索。也可以只搜索卷积cell，然后将它们连接起来组成整个网络，这称为micro搜索。在每个cell里有B个节点，节点1和节点2作为cell的输入，是前两个cell的输出。对于剩下的B-2个节点，使用控制器取做两个决策：（1）选择两个前驱节点作为当前节点的输入；（2）选择两个操作作用在这两个前驱节点上。上述操作之后，将两个节点相加。可能的操作有5种：identity，3×3和5×5的可分离卷积，3×3的最大池化和平均池化。以B=4举例，如下图所示：

• 对于节点1、2，其作为输入，控制器不对此作决策。用$h{1}$和$h{2}$表示。
• 在节点3，控制器选择两个前驱节点和两种操作。这里选择了节点2和节点2，选择的操作为5×5可分离卷积和identity，所以$h{3}={rm sep_conv_5x5}(h{2})+{rm id}(h_2)$
• 在节点4，控制器选择了节点3和节点1，选择的操作为3×3可分离卷积和3×3可分离卷积，所说$h{4}={rm sep_conv_3x3}(h{3})+{rm sep_conv3×3}(h{1})$
• 最终除了$h{4}$其他节点都作为了其他节点的输入，所以$h{4}$作为cell的输出

从此搜索空间中还可以生成reduction cell，只需：（1）采样一个卷积cell；（2）应用步长为2的操作。卷积cell和reduction cell同时采样，则控制器RNN一共作$2(B-2)$种决策。在节点$i(3 leq i leq B)$，控制器从前$i-1$个节点任意选择2个节点，从5种操作中任意选择2个，所以总共有$(5 times (B-2))^{2}$种可能的cell，算上reduction cell，一共有$(5 times (B-2))^{4}$种可能的cell。

二、You Only Search Once: Single Shot Neural Architecture Search via Direct Sparse Optimization

1、总览

在这篇论文里，作者将NAS重新表述为从一个大型网络中剔除无用的连接，因此只需一个模型被训练。由于模型在训练阶段就直接被优化了，作者称之为直接稀疏优化NAS（Direct Sparse Optimization NAS， DSO-NAS）。作者进一步论证了这个稀疏正则化可以被改进的加速近端梯度（proximal gradient）方法优化，不需要任何的控制器、性能预测或者搜索空间松弛（搜索空间松弛是可微分方法的内容）。DSO-NAS也第一次论证了NAS可以直接在大型数据集上使用而没有块结构的共享。

2、Motivation

DSO-NAS通用是根据神经网络的结构空间可以用有向无环图DAG表示，在此空间的任何结构都是其子图。也就是说一个特定的结构可以从整个图中选择节点和边来得到。这里作者用完整的图来表示单个block的搜索空间，整个网络是由这些block用跨连接堆叠起来。

对于一个有T个节点的DAG，第$i$个节点的输出$h^{(i)}$可以通过变换所有前驱节点输出$h^{(j)},j<i$的和来得到：

$$ h^{(i)}={mathcal O}^{(i)} left(sum_{j=1}^{i-1}h^{(j)} right) $$

下图展示了DAG里的一个特定的block，节点表示操作$mathcal O$,边表示信息流动。

上图中节点1和节点6是输入节点和输出节点，虚线表示没被连接起来的结点。那么节点5的输出是$h^{(5)}={mathcal O} ^{(5)}left(sum_{j=4}^{4}h^{(j)} right)$，也就是$h^{(5)}={mathcal O} ^{(5)}(h^{(2)} + h^{(4)})$

然后结构搜索问题可以看作边裁剪问题。在搜索过程中，我们移除没有用的边和节点，留下最重要的结构。这里作者对每个节点的输出都乘上一个乘子，上式变成：

$$ h^{(i)}={mathcal O}^{(i)} left(sum{j=1}^{i-1} lambda{(j)}^{(i)} h^{(j)} right) $$

$lambda{(j)}^{(i)}$是作用在从节点$j$到节点$i$的乘子，然后对这些乘子使用稀疏正则化，使其在搜索过程中有些为0。如果$lambda{(j)}^{(i)}$为0，则相关的边和节点就被移除了。

3、搜索空间

DSO-NAS可以搜索block然后堆叠起来（micro-search），也可以搜索不带block的整个网络（macro-search）。

对于要搜索的block，设定里面有M个层级，每个层级包含N个不同的操作（也就是节点）。每个操作将其所有前层级的节点和block的输入连接起来，block的输出就是将block里的所有节点连接起来。对于每个连接，都乘上一个乘子$lambda$。对其使用稀疏正则化，优化之后移除$lambda$为0的连接和节点，得到最终的block结构。整个过程如下图所示：

图（a）是完整的DAG，图（b）是优化每个边的乘子$lambda$，图（c）是移除了没有用的边和节点后最终的block。

第$b$个block里第$i$层级的第$j$个节点$h_{(b,i,j)}$可以用如下公式表示：

$$ h{(b,i,j)}={mathcal O}{(b,i,j)} left(sum{m=1}^{i-1} sum{n=1}^{N} lambda{(b,m,n)}^{(i,j)} h{(b,m,n)} + lambda{(b,0,0)}^{(i,j)} O{(b-1)} right) $$

这里$h{(b,0,0)}=O{(b-1)}$和$h{(b, M+1,0)}=O{(b)}$分别是第$b$个block的输入节点和输出节点。第$m$个层级有$(m-1)N+1$个输入。第$b$个block的输出$O_{(b)}$是对所有连接到输出的结点应用reduction操作（1×1的卷积）$mathcal R$得到的：

$$ begin{aligned} O{(b)}=mathcal{R}left(left[lambda{(b, 1,1)}^{(M+1,0)} h{(b, 1,1)}right], lambda{(b, 1,2)}^{(M+1,0)} h{(b, 1,2)}, ldots, lambda{(b, m, n)}^{(M+1,0)} h{(b, m, n)}, ldots lambda{(b, M, N)}^{(M+1,0)} h{(b, M, N)}right) +O{(b-1)}, m in[1, M], n in[1, N] end{aligned} $$

整个由block堆叠的完整网络如下图所示：

整个网络有$S$个stage，每个stage有$B$个卷积block。除了最后一个stage，每个stage的最后都有一个reduction block。这里作者尝试了两种搜索空间：（1）$lambda$在所有block中都共享的搜索空间；（2）每个block中$lambda$都不同的搜索空间。

卷积操作遵循Conv-Bn-ReLU的顺序，使用下面几种操作：

• 3×3的可分离卷积
• 5×5的可分离卷积
• 3×3的平均池化
• 3×3的最大池化

对于reduction block，使用1×1和3×3大小的卷积核，步长为2。

搜索block的任务因此可以简化为学习每个边的$lambda$，可以用下式表示：

$$ min {mathbf{W}, boldsymbol{lambda}} frac{1}{K} sum{i=1}^{K} mathcal{L}left(mathbf{y}{i}, N e tleft(mathbf{x}{i}, mathbf{W}, boldsymbol{lambda}right)right)+delta|mathbf{W}|{F}^{2}+gamma|boldsymbol{lambda}|{1} $$

$mathbf{x}{i}$和$mathbf{y}{i}$是输入数据和标签，$K$表示训练样本的数目，$mathbf{W}$表示网络的权重，$delta$和$lambda$表示正则化权重。可以设${mathcal G}(lambda)=frac{1}{K} sum{i=1}^{K} mathcal{L}left(mathbf{y}{i},N e tleft(mathbf{x}_{i}, mathbf{W}, boldsymbol{lambda}right)right)$

4、优化、训练

正则化参数$lambda$优化起来非常困难，尤其在有随机性的深度神经网络里，虽然启发式的阈值方法可行，但优化是不稳定的。不过使用稀疏结构选择（Sparse Structure Selection，SSS）可以解决这个问题，SSS通过修改理论上合理的优化方法加速近端梯度（Accelerated proximal Gradient，APG）方法，重写公式避免在计算梯度时重复地前向和反向计算：

$$ begin{array}{l}{mathbf{z}{(t)}=boldsymbol{lambda}{(t-1)}-eta{(t)} nabla mathcal{G}left(boldsymbol{lambda}{(t-1)}right)} {mathbf{v}{(t)}=S{eta{(t)} gamma}left(mathbf{z}{(t)}right)-boldsymbol{lambda}{(t-1)}+mu{(t-1)} mathbf{v}{(t-1)}} {boldsymbol{lambda}{(t)}=mathcal{S}{eta{(t)} gamma}left(mathbf{z}{(t)}right)+mu{(t)} mathbf{v}_{(t)}}end{array} $$

$t$是迭代地轮数，${mathcal S}{eta{(t)} gamma}$表示软阈值操作${mathcal S}{alpha}(mathbf{z}){i}={rm sign}(z{i})(|z{i}|-alpha){+}$，${eta}{(t)}$表示梯度步长，$mu$是动量大小。这种方法称之为APG-NAG。$mathbf{W}$和$mathbf{lambda}$使用NAG（Nesterov Accelerated Gradient ）和APG-NAG同时被更新。然而APG-NAG不能直接用在这里，裁剪的搜索空间是有限的，会导致一定程度的过拟合。这里作者将训练数据分成两部分，一部分用来更新$mathbf{W}$，另一部分用来更新$mathbf{lambda}$。

整个方法包括三个阶段：

• 训练DAG全部连接的网络，得到好的权重初始化
• 从预训练的模型中搜索结构
• 从头训练最终的网络

在前两个阶段，BN层的参数被固定为1，为了避免影响$mathbf{lambda}$的学习。在第二步之后，作者通过一个全局宽度乘法器来调整每个操作中的滤波器数量，以满足计算预算。

参考文献

[1] Pham H, Guan M Y, Zoph B, et al. Efficient Neural Architecture Search via Parameter Sharing[J]. 2018. [2] Zhang X , Huang Z , Wang N . You Only Search Once: Single Shot Neural Architecture Search via Direct Sparse Optimization[J]. 2018. [3] 你想要的神经网络自动设计，谷歌大脑帮你实现了：用参数共享高效地搜索神经网络架构（ENAS）[4] https://blog.csdn.net/weixin_34319817/article/details/89581856[5] Huang Z , Wang N . Data-Driven Sparse Structure Selection for Deep Neural Networks[J]. 2017. [6] 《深入理解AutoML和AutoDL》