NAS 学习笔记(五)- DARTS

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言,谢谢

引言

  DARTS [1] 是 ICLR 2019 上的一篇关于 NAS 的论文,如我们前几篇文章提到的,大多数 NAS 算法是使用 RL 算法或 Evolution 算法进行结构搜索,把它们当做 black box 优化问题,然而这样的话的 search space 是离散的,搜索非常耗时了。DARTS 试图解决这个问题,提出了一种新的网络搜索算法,它的 search space 是连续的,在搜索过程中它通过在验证集上验证,然后使用梯度下降算法来完成搜索。实验也表明了 DARTS 进行网络架构搜索的计算开销要比普通网络架构算法小几个量级,但搜索得到的网络结构却仍能和之前 SOTA 算法几乎持平。同时它的泛化能力也很好,不仅可以用于 CNN 结构的搜索,还可以用于 RNN 结构的搜索。本文对它作一个简单的记录。

Differentiable Architecture Search

  从 DARTS(Differentiable ARchitecture Search)的名字也可以看出来它是支持可微的,下面按照论文的脉络,分为四个部分,来介绍下它是如何支持可微的。

Search Space

  DARTS 中搜索的最小单位也叫 cell,它是一个 DAG,以它为 block 来构建 architecture。每个 cell 以 \(N\) 个有序的 nodes 组成,每个 node \(x^{(i)}\) 代表一个 latent representation,每条 edge \((i,j)\) 代表在 \(x^{(i)}\) 执行了某种 operation \(o^{(i, j)}\)(e.g. convolution, max pooling, zero)。每个 cell 有两个 input node,和一个 output node,对于 CNN 来说,input node 就是任意两个 pervious layer 的 output,对于 RNN 来说,input node 就是 current step 和一个 previous step 的 state。cell 的 output 会通过对所有 intermediate nodes 执行一个 reduction operation,例如将它们 concatenate 起来。每个 intermediate node 都通过它们的 predecessor 来计算:

\[ x^{(j)}=\sum_{i<j} o^{(i, j)}\left(x^{(i)}\right) \tag{1} \]

  zero operation 可以用来表示两个 node 之间没有连接。实际上,了解了 DARTS 的 search space 后,其实可以发现 learn cell 的任务其实就已经被转换成 learn edge 的任务上了,搜索的结果是某些特定结构的 cell,这些 cell 中哪些 node 之间有 edge ,edge 上的 operation 是什么。

Continuous Relaxation and Optimization

  我们用 \(\mathcal{O}\) 来表示 candidate operations,到目前为止,search space 还是离散的。所以为了使 search space 连续,作者为 edge 上的每一种 operation 赋上一个 weight \(\alpha_o^{(i,j)}\),所以 operation 可以表示为:

\[ \bar{o}^{(i, j)}(x)=\sum_{o \in \mathcal{O}} \frac{\exp \left(\alpha_{o}^{(i, j)}\right)}{\sum_{o^{\prime} \in \mathcal{O}} \exp \left(\alpha_{o^{\prime}}^{(i, j)}\right)} o(x) \tag{2} \]

  其实这也很简单,就是利用 \(\alpha = \{\alpha_o^{(i,j)}\}\) 做一个 softmax 激活,然后对各种 operation 作加权平均罢了。那么问题实际上就是被转移成 learn 一组参数 \(\alpha = \{\alpha_o^{(i,j)}\}\) 了,搜索结束后只要通过 \(o^{(i, j)}=\operatorname{argmax}_{o \in \mathcal{O}} \alpha_{o}^{(i, j)}\)\(\bar{o}^{(i, j)}\) 替换成 \(o^{(i, j)}\) 就可以了。下图是一个示意图:

  我们再记具体某个 architecture 里的可训练的 weights 为 \(w\)(e.g. convolution, maxpooling 里的 weights),那么优化问题就变成了最小化验证集上的 loss \(\mathcal{L}_{v a l}\left(w^{*}, \alpha^{*}\right)\),当 architecture 固定即 \(\alpha^*\) 固定时,需要得到 \(w^*\) 来最小化训练集上的 loss \(w^{*}=\operatorname{argmin}_{w} \mathcal{L}_{t r a i n}\left(w, \alpha^{*}\right)\)
  上述问题,其实就变成了:

\[ \begin{array}{cl}{\min _{\alpha}} & {\mathcal{L}_{v a l}\left(w^{*}(\alpha), \alpha\right)} \\ {\text { s.t. }} & {w^{*}(\alpha)=\operatorname{argmin}_{w} \mathcal{L}_{t r a i n}(w, \alpha)}\end{array} \tag{3} \]

  这实际上就变成了一个 bilevel optimization 的问题。

Approximate Architecture Gradient

  直接去优化\((3)\)比较困难,所以作者采用了迭代近似优化的方法,这也是这篇论文很厉害的地方:

\[ \begin{aligned} & \nabla_{\alpha} \mathcal{L}_{v a l}\left(w^{*}(\alpha), \alpha\right) \\ \approx & \nabla_{\alpha} \mathcal{L}_{v a l}\left(w-\xi \nabla_{w} \mathcal{L}_{t r a i n}(w, \alpha), \alpha\right) \end{aligned} \tag{4} \]

  其中 \(\xi\) 是学习率,上式其实是一个复合函数求导,进一步展开化简为:

\[ \nabla_{\alpha} \mathcal{L}_{v a l}\left(w^{\prime}, \alpha\right)-\xi \nabla_{\alpha, w}^{2} \mathcal{L}_{t r a i n}(w, \alpha) \nabla_{w^{\prime}} \mathcal{L}_{v a l}\left(w^{\prime}, \alpha\right) \tag{5} \]

  接着利用泰勒展开进一步化简得到:

\[ \nabla_{\alpha, w}^{2} \mathcal{L}_{t r a i n}(w, \alpha) \nabla_{w^{\prime}} \mathcal{L}_{v a l}\left(w^{\prime}, \alpha\right) \approx \frac{\nabla_{\alpha} \mathcal{L}_{t r a i n}\left(w^{+}, \alpha\right)-\nabla_{\alpha} \mathcal{L}_{t r a i n}\left(w^{-}, \alpha\right)}{2 \epsilon} \tag{6} \]

  乍一看还是比较难推出来的,详细的推导可以看这个大神的推导
  它的总体伪代码如下:

First-Order Approximation

  作者把 \(\xi = 0\) 时称为 First-Order Approximation,很显然这种情况下 gradient 只剩 \(\nabla_{\alpha} \mathcal{L}_{v a l}(w, \alpha)\),此时假设 \(w\) 已是 \(w^*(\alpha)\),这种情况下,速度会提升,但是效果会变差。同时作者把 \(\xi \gt 0\) 的情况称为 Second-Order Approximation,作者在后续的实验中都测试了这两种情况的差边,总的来说 Second-Order Approximation 的精度还是要好一些的,但是也更慢一些。

Deriving Discrete Architectures

  对于 CNN,我们会挑选两个最好的 operation 作为输入,对于 RNN 则是一个,最好的标准是根据这个来评价的 \(\frac{\exp \left(\alpha_{o}^{(i, j)}\right)}{\sum_{o^{\prime} \in \mathcal{O}} \exp \left(\alpha_{o^{\prime}}^{(i, j)}\right)}\)

Drawbacks

  了解了 DARTS 的原理后,它的缺点也显而易见:

  • 因为实际上是一个 operations 的 ensemble,所以 update \(w\) 的时候需要 forward 和 backword-ropagated 所有的 operations,开销太大。
  • 求解二阶导的开销太大
  • derive 新的 architecture 时,因为是通过 softmax 来求 top k,所以存在 operations 存在关联的情况,例如两个 op 的概率依次是 0.33 和 0.34,很难说第一个 op 就比第二个差。
  • DARTS 在搜索时不能控制模型的大小,我们无法刻意的去搜索一些较小的模型。

Conclusion

  看完 DARTS 的论文,感觉作者打开了新世界的大门,把黑盒问题变成了可导可微的问题,DARTS 中最关键的也就是将候选 operation 使用 softmax 函数进行混合。这样就将 search space 变成了连续空间,目标函数成为了可微函数。这样就可以用基于梯度的优化方法找寻最优结构了。搜索结束后,这些混合的操作会被权重最大的操作替代,形成最终的结果网络。实在是非常优美,当然也存在一些问题和优化,后面也有不少论文针对 DARTS 的问题去做优化的。

Refer

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

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. Differentiable Architecture Search
    1. 2.1. Search Space
    2. 2.2. Continuous Relaxation and Optimization
    3. 2.3. Approximate Architecture Gradient
      1. 2.3.1. First-Order Approximation
    4. 2.4. Deriving Discrete Architectures
  3. 3. Drawbacks
  4. 4. Conclusion
  5. 5. Refer
  6. 6. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 680.3k 字啦

载入天数...载入时分秒...