模型搜索

1. 前言

最近做了一段时间的模型搜索，实验过程中发现模型搜索作用还是很明显的。本篇文章主要回顾了一下近几年一些关于模型搜索的文章：

RL-based

Gradient-based

2. Neural Architecture Search with RL

http://cn.arxiv.org/pdf/1611.01578v2
这篇论文应该是比较早的关于模型结构搜索的论文，主要基于增强学习算法，将搜索得到的模型的performance作为reward，反馈给agent，不断更新agent以最大化 $E[R]$ 。

论文使用了一个RNN来作为agent，也就是controller，如下图：

Screen Shot 2019-03-06 at 9.56.54 PM.png

可以看到，通常我们使用RNN在每一个时刻输出一个word的表示，现在改为输出网络结构的参数。

每一次当RNN选择一组参数，就根据参数构建网络，然后在一个数据集上进行训练，训练结束后使用一个验证集，对得到的网络进行评测，评测的结果计算一个reward值返回给RNN。

作者使用验证集的准确度(accuracy)作为reward $R$ ，RNN的参数更新使用REINFORCE算法。该算法是增强学习的基础算法，可以直接使用agent的动作得到的reward对策略梯度进行近似，也就是RNN的参数的梯度。公式如下：

Screen Shot 2019-03-06 at 10.03.03 PM.png

从公式中可以看出，可以直接将 $log P * R$ 的梯度作为策略的梯度。
通常还会增加一个baseline，用于减少variance，baseline的选择可以为之前reward的moving average。

Screen Shot 2019-03-06 at 10.05.05 PM.png

有了RNN参数的梯度公式，我们就可以用任何常见的深度学习框架来建模训练啦。

但是非常明显，这种每次都要训练一个模型的方式必然是非常非常慢的，论文中提出了可以使用一大堆GPU服务器，来异步训练的方式。

整个架构如下图：

Screen Shot 2019-03-06 at 10.07.16 PM.png

RNN的参数保存在PS（参数服务器）的服务器端，然后复制 $K$ 个RNN，它们的参数都与服务器端参数一致（在某些时刻）。之后每个RNN，每人按照之前说到的方式，采样出 $m$ 个模型，这 $K*m$ 的模型异步地在不同的GPU上进行训练，得到accuracy。

然后每个agent，也就是每个RNN的复制，根据自己的 $m$ 个得到的accuracy，计算出RNN参数的梯度，将梯度push给服务器，服务器根据梯度进行参数的更新，由于是异步的，服务器不会等待得到所有 $K$ 个agent的梯度，就进行参数的更新，RNN push完梯度后，会将新的参数pull下来。

作者还期望能够对结构的复杂度进行选择，也就是对网络节点之间的链接进行选择，因此如下图：

Screen Shot 2019-03-06 at 10.12.49 PM.png

对每个节点增加了anchor point，第 $N$ 层的anchor point预测 $N-1$ 个值，表示与之前节点的链接：

Screen Shot 2019-03-06 at 10.14.23 PM.png

论文后面还提出了搜索RNN结构的方式，类似于LSTM，LRU之类的结构，就不赘述了。

3. Efficient Neural Architecture Search via Parameter Sharing

http://cn.arxiv.org/pdf/1802.03268v2

上篇论文太贵，因此这篇论文提出了更加高效的搜索方式。

这篇论文的核心思想：将整个搜索空间看作一个巨大的图，搜索得到的模型就是这个图的子图，所以可以进行参数共享。
如下图：

Screen Shot 2019-03-06 at 10.24.21 PM.png

红线代表了选择的模型，它其实是一个DAG的一个子图。

因此，在整个模型搜索中可以认为有两种参数：RNN的参数，共享模型的参数。训练是交替进行的：

训练共享模型的参数：固定RNN的参数，sample一个模型，按照标准的方式训练参数 $w$ 。
训练RNN参数：固定 $w$ ，使用REINFORCE算法，不断sample模型，计算reward，这里reward是在验证集上计算。

其实后面很多的模型搜索方法，都和这里训练的框架一致。

论文后面还介绍了具体的模型搜索空间的设计，就不赘述了。

4. DARTS: Differentiable Architecture Search

http://cn.arxiv.org/pdf/1806.09055v1

之前的两篇是使用增强学习算法，这一篇是比较早的使用梯度法的模型搜索，并且在github上开源了搜索源码。

整体思路如下图：

Screen Shot 2019-03-06 at 11.07.25 PM.png

从图中可以看出，每个小的block有 $n$ 个节点，每个节点都进行了编号，并且每个节点和编号比它小的节点之间都有链接。然后每个节点的输入，就是和它有链接的节点的加权和。公式如下：

Screen Shot 2019-03-06 at 11.10.26 PM.png

这里的 $o$ 就代表了边，每个边 $o$ 都有一组可选择的操作，通常我们想要从这个DAG中选择一个模型，就需要这个 $o$ 是 $max$ ，也就是：

Screen Shot 2019-03-06 at 11.12.54 PM.png

论文中作者使用的是softmax：

Screen Shot 2019-03-06 at 11.13.43 PM.png

这样就将选择模型这个任务，转换为了训练一组参数 $\alpha$ 的任务。就像Figure 1。

因此，任务转换称为了一个bilevel优化问题：

Screen Shot 2019-03-06 at 11.15.45 PM.png

需要在 $w$ 最优的情况下，不断地优化 $\alpha$ ，但是这种优化问题需要在 $\alpha$ 每次改变是优化 $w$ ，这将是非常耗时的。

因此，作者提出一种迭代优化的策略，来近似地优化上面的问题。算法如下图所示：

Screen Shot 2019-03-06 at 11.17.50 PM.png

在每一步，首先将 $w_{k-1}$ 按照最小化 $L_{train}(w_{k-1},\alpha_{k-1})$ 的梯度方向进行更新得到 $w_k$ ，接着固定 $w_k$ ，然后按照最小化下面公式的梯度方向更新 $\alpha_{k-1}$

Screen Shot 2019-03-06 at 11.20.49 PM.png

上面公式的直观解释就是，在假设 $w_k$ 进行了一步虚拟的更新之后，优化validation loss，这里，我并不是特别理解对 $w_k$ 进行更新的必要性，为什么不直接用 $w_k$ 呢？就好像 $\alpha$ 的更新，是在预测 $w$ 的下一步的情况下进行的。

作者给出了梯度公式，然后又因为需要计算二阶导数运算量太大又给出了近似公式（这是在向我等渣渣秀数学功底嘛）：

Screen Shot 2019-03-06 at 11.26.37 PM.png

二阶导数主要是用差分来近似。

在算法收敛后，我们就得到了一组 $\alpha$ ，使用它就可以选择每个边的具体操作是什么了，以及选择每个节点的输入节点。看代码貌似是stride为2的层是一组 $\alpha$ ，为1的层共享一组 $\alpha$ 。这里为什么不每层都一组参数呢？

其实对比一下上一篇论文ENAS，差别主要在于将ENAS中的RNN，替代为了这里的 $\alpha$ ，然后更改了训练算法，RNN使用REINFORCE训练， $\alpha$ 采用梯度下降法训练。

5. SNAS: Stochastic Neural Architecture Search

http://cn.arxiv.org/pdf/1812.09926v2

这是一篇会议收录的论文，出自商汤。这篇论文使用了很多增强学习中的概念来解释论文提出的搜索方法。

论文首先在介绍里指出里RL-based的NAS和darts的不足之处。论文指出在RL-based的NAS中，NAS通过Markov Decision Process来进行建模，我们知道MDP描述的是一个agent不断选择action与环境交互的过程。作者提到MDP中如果使用TD learning，会由于delayed reward导致效率和可解释性变差。在ENAS中，一个agent的reward只有在它作出了一系列的action之后，也就是得到模型之后才能得到，因此就出现了delayed reward。

darts虽然没有这样的问题，但是由于operation的非线性，在loss中引入了untractable bias。这里并不是特别理解，我认为大意是在说darts在最终选择模型的时候，会去掉权重较小的部分，导致搜索时的loss与最终选择的模型的loss直接存在一个偏差。

因此，这篇论文提出了SNAS，试图解决上面的问题。

首先，SNAS去掉了对于模型搜索的MDP假设，也就是摆脱掉了reward。并且使用了完全可求导的loss，sample的过程被可微分的relaxing的分布代替。

作者证明了SNAS优化的是RL-based相同的目标，以及loss是如何分布在每一次sample的action中。

单纯从方法论的角度，SNAS并不是特别的复杂。如下图：

微信截图_20190307103948.png

与darts非常相似，每一边都是一组operation，参数的大小代表了它们的权重。公式如下，

图片.png

这里使用

Z_{i,j}

表示节点之间边的权重，和darts中的

\alpha_{i,j}

的softmax值貌似是一样的东西。区别在于，在darts中，概率是根据softmax计算，在SNAS中

Z

是通过下面公式计算：

图片.png

那么我们的目标函数就是：

图片.png

问题是它可以求导吗？我们知道在

P_\alpha(Z)

是一个已知的概率分布情况下，它是可以通过likelihood ratio trick来进行求导的，但是论文提到，这种方式的variance非常高，因此，作者使用了上面对

Z_{i,j}

计算的方式，使用了reparameterization trick，也就是使用了一个gumbel随机变量，来模拟

Z

的分布，也就是：

G_{i, j}^k = -log(-log(U_{i,j}^k))

，其中

U

是均匀分布。

可以证明在 $\lambda$ 趋近于0的时候， $Z$ 是趋近于max分布的。

这样就减轻了搜索时的loss与真实搜索出来的模型的loss之间的bias。

那么SNAS怎么解决了像ENAS中的delayed reward的问题呢？首先SNAS中没有常数项的reward，reward在SNAS中是可导的。我们可以求出reward对于模型搜索参数 $\alpha$ 的导数：

图片.png

其中

[]_c

里面表示的是对于

\alpha

无关项，可以看做是常数。那么，显而易见，这其实就是REINFORCE的策略梯度的公式，可以将该常数项看作是reward。也就是说每个边的credit assignment是：

图片.png

也就是说每个边都得到了自己的reward，它并不是delayed。

在模型搜索中，除了将accuracy，loss作为目标之外，我们还期望搜索得到的模型的计算量，效率得到优化。因此，SNAS引入了resource constraints，如下图：

图片.png

C

代表了类似于MAC（参考shufflenet），FLOPS等loss，可以通过蒙特卡洛来近似：

图片.png

6. FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search

http://cn.arxiv.org/abs/1812.03443

这是一篇Facebook出的，这篇论文的思路是之前又不太一样，与其在小的block上做文章，这篇论文尝试在整个模型架构上进行搜索。
其实从方法上来讲，FBNet依旧采用了使用一组参数代表权重的方式，只不过darts代表的是节点之间op的权重，FBNet中代表的是一组给定block，每个block的权重。具体来讲就是，FBNet整体结构如下图：

图片.png

TBS代表等待搜索的block，每一层有8个或9个block，block的设计如下：

图片.png

根据参数计算得到的权重，就代表了每个block被选中的概率。

论文有两点值得注意，一是根据参数计算概率的方式，二是论文引入了真实环境中，block运算所需时间，作为loss。
首先是loss，如下图：

图片.png

这里我非常不理解乘一个

\alpha

的意义，在具体的实现中，我将乘法改成了加法。

然后是block的概率，在正常情况下，我们最终使用的模型应该是从每层中的多个选择一个block，选择的概率分布为：

图片.png

每一层的输出为：

图片.png

其中 $m$ 表示0,1随机变量，代表是否被选中。显然，这个没法求导，因此，类似于SNAS，FBNet也采用了reparameterize trick，使用gumbel分布代替真实分布：

图片.png

7. ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware

http://cn.arxiv.org/abs/1812.00332

这篇来自于MIT，论文作者貌似曾经出过很多关于模型压缩的文章。其实模型搜索类似于模型压缩，都是将一个大的网络，弄成一个小的网络。

其实proxyless nas与FBNet非常类似，不同处在于FBNet是每一层的所有block一起训练，输出是加权平均，然而proxyless nas是真正地去sample一个block来训练。

整个训练框架如下图：

图片.png

每一层的输出为：

图片.png

那么训练流程依旧采取交替的方式，首先使用采样出来的block训练weight parameters，接着固定weight parameters训练architecture parameteres。
weigh的训练类似于一个神经网络的训练，容易理解，那么architecture参数是怎么训练的呢？

一种是类似于RL-based的方式，采用REINFORCE算法。每层选择block看作是agent的action，将得到的网络的performance作为reward，可是在论文中好像并没有给出reward的计算公式。这个reward可以有各种形式，accuracy，-ce，或者是负的时间代价，以及它们的组合。

还有一种方式，感觉实现起来很复杂，由于作者并没有开源出search的代码，具体的细节我也不清楚，这里就不赘述了。

8. 小结

模型搜索应该是近两年非常热门的内容，它其实属于AutoML的大框架之下，有兴趣的可以在https://www.automl.org/ 找到很多相关内容。

最后，有没有今年（2019）考研计算机的小伙伴呀。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,547评论 6赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,399评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,428评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,599评论 1赞 274
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,612评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,577评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,941评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,603评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,852评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,605评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,693评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,375评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,955评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,936评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,172评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,970评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,414评论 2赞 342

模型搜索

1. 前言

2. Neural Architecture Search with RL

3. Efficient Neural Architecture Search via Parameter Sharing

4. DARTS: Differentiable Architecture Search

5. SNAS: Stochastic Neural Architecture Search

6. FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search

7. ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware

8. 小结

推荐阅读更多精彩内容