会员服务 ·

AutoML - 遗传算法与网络结构搜索

2020 年 9 月 22 日 AINLP

兴趣所致，关注了一些AutoML的知识，主要是AutoML中的网络结构搜索的部分，特记录下来希望能形成体系。以下是要写的文章列表。

强化学习与网络结构搜索(一)
强化学习与网络结构搜索(二)
强化学习与网络结构搜索(三)
遗传算法与网络结构搜索(本篇)
Darts可微结构搜索
ENAS：基于参数共享的网络结构搜索
AutoML-Zero
更多待续

进化算法

关于进化算法，也称为遗传算法。是一种解决最优化的搜索算法。具体算法如下：

选择初始生命种群
循环

评价种群中的个体适应度
以比例原则（分数高的挑中几率也较高）选择产生下一个种群（轮盘法（roulette wheel selection）、竞争法（tournament selection）及等级轮盘法（Rank Based Wheel Selection））。不仅仅挑分数最高的的原因是这么做可能收敛到局部的最佳点，而非整体的。
改变该种群（交叉和变异）

直到停止循环的条件满足.

而进化次数则受限于：

计算耗费的资源限制（例如计算时间、计算占用的内存等）；
一个个体已经满足最优值的条件，即最优值已经找到；
适应度已经达到饱和，继续进化不会产生适应度更好的个体；
人为干预；
以及以上两种或更多种的组合。

更多细节可以参考维基百科.

那么既然是搜索算法，当然也能够用到网络结构搜索这个问题上来了。

搜索空间

对于搜索问题，首先我们要关注的就是搜索空间，在论文中使用的搜索空间跟《强化学习网络结构搜索(二)》是一样的，我们再来简单回顾一下：

如下图所示:

(左图)大模型是由多个Normal Cell和Reduction Cell组成的，其中Reduction Cell会使得输出的size变小为原来的1/2。
(中图)Normal Cell之间还可能会有skip connection。
(右图)一个具体的Normal Cell或者Reduction Cell。输入有两个0和1，分别来自于上一个Cell的输出还有skip connection。一个Normal Cell的构建过程则是：

从当前状态集(初始为0，1)中选出两个(可以重复选择)，
然后对于每个状态，选择一个操作。
对于两个状态经过操作的输出，选择一个合并操作。
输出加入到状态集中以供选择
以上步骤重复五次，虚线框出来的是一次步骤。

另外，控制一个网络结构中有多少个Normal Cell和Reduction Cell的参数变量是超参数。

进化算法之结构搜索

论文提出的在结构搜索上的进化算法流程如下：

有三个超参数，P，C，S。其中P是初始的不同网络结构的集合。S是每次从P中选择出来的个数。C是所有训练过的模型的数目。C的大小其实和时间很相关，训练时间长，C就会大。

在开始的时候，随机的方式生成P个Normal/Reduction Cell结构
然后每次从集合中拿出来S个，
找出S个中最好的模型进行修改
训练修改后的新模型
把新模型加入到集合中
从集合中移除最老的一个结构

这里有论文的创新点，如果是移除掉最差的模型，那么就是普通的遗传算法。
相对于普通的遗传算法，本算法没有交叉操作。

在训练完成后，选择最好的模型。

进化算法之模型修改

在这个算法中，模型的修改分为两个部分，状态修改和操作修改。如下图所示：

状态修改就是修改状态输入给哪个操作。操作的修改就是去更改一个操作。当然，这两个操作都需要先选择是Normal Cell还是Reduction Cell，然后再选择是构建Cell的五个步骤中的哪一个。然后再选择状态或者操作。

为什么要移除最老的模型？

在网络搜索过程中，往往训练的时间越长，效果会越好，如果每次去除最差的，那么可能比较新的模型会被去除掉，这样就限制了算法的探索能力。

如果去掉的是差的模型，那么会导致lucky noise的出现，即有一个结构表现较好，所以会一直存在于集合中。
去掉最老的，意味着在集合里的候选模型都是比较新的，保证了算法的探索能力。

在使用去除最老模型的方法之后，一个模型想要长期存在集合中，就必须具有可扩展性，即在模型上做几次修改仍然是好的模型。这样就使得搜索算法专注在结构上。而不会过拟合在lucky noise上。
另外一个附加影响则是，这样做了之后，因为每个模型训练时间相当于就是固定的了，这样，收敛速度快，或者说比较高效的模型就容易脱颖而出。

实验

在实验过程中，为了加快速度，会先在小模型上训练，然后在大模型上训练。小模型指的是Normal Cell和Reduction Cell的个数少。

不同方法的训练时间和达到的最好效果如上图，可以看到，进化算法比RL算法要快。

而得到的模型的计算量和准确率如下图。

可以看到，进化算法倾向于得到计算量小的模型。最后得到的网络如下图：

在imageNet数据上的效果如下：

在搜索过程中，每个探索到的模型需要训练25个epoch，每个实验都需要探索20k个模型，在450块 K40的GPU上，每个实验需要7天才能完成。

计算量还是很大的，没错，是有钱人的游戏！可是思维还是值得学！

思考与总结

这篇文献是第一篇将遗传算法应用到模型结构搜索上来的论文。论文的要点就是对遗传算法的改进：

没有交叉，只有变异
把每次去掉最差的改为每次去掉最老的。

勤思考，多提问是Engineer的良好品德。

问题如下：

如果用这个算法去学习Transformer，试设计一个搜索空间？

回答后续公布，欢迎关注公众号【雨石记】。

参考文献

[1]. Real E, Aggarwal A, Huang Y, et al. Regularized evolution for image classifier architecture search[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2019, 33: 4780-4789.

说个正事哈

由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：

（1）点击页面最上方"AINLP"，进入公众号主页。

（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。

感谢支持，比心。

欢迎加入AINLP技术交流群

进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注NLP技术交流

推荐阅读

这个NLP工具，玩得根本停不下来

征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）

完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）

从数据到模型，你可能需要1篇详实的pytorch踩坑指南

如何让Bert在finetune小数据集时更“稳”一点

模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法

文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化

Node2Vec 论文+代码笔记

模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结

中文命名实体识别工具（NER）哪家强？

学自然语言处理，其实更应该学好英语

斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。