架构搜索文献笔记（2）：《基于端到端随机森林预测的代理辅助进化深度学习 》_基于随机森林的代理

论文《Surrogate-Assisted Evolutionary Deep Learning Using an End-to-End Random Forest-based Performance Predictor》-2019-IEEE Transactions on Evolutionary Computation

论文链接
E2EPP代码链接

一、摘要

摘要：卷积神经网络(CNNs)在各种现实应用中表现出了卓越的性能。不幸的是，只有在优化结构的情况下，cnn才能实现良好的性能。最先进的有线电视网络的架构通常是手工制作的有线电视网络和调查数据的广泛专业知识，这因此阻碍了有线电视网络的广泛采用，为缺乏经验的用户。进化深度学习(EDL)能够在不需要太多专业知识的情况下自动设计出最好的CNN架构。然而，现有的EDL算法通常通过从头开始训练来评估一个新架构的适用性，这导致了极高的计算成本，甚至在高性能计算机上运行。

——》本文提出了一种基于随机森林的端到端离线性能预测器，用于加速数据挖掘中的适应度评估。通过将其集成到现有的EDL算法作为一个案例研究，与18个最先进的竞争对手相比，所提出的性能预测器在分类精度和消耗的计算资源方面显示了有前途的性能。并将所提出的性能预测器与其他两种代表性的性能预测器进行了比较。

——》实验结果表明，所提出的性能预测器不仅提高了适应度评估的速度，而且在同类性能预测器中取得了最好的预测效果。。

二、相关介绍

2.1 深度进化学习

由以下步骤组成:

	步骤1:使用预先定义的对象随机初始化人口大小基于相应的基因型到表型映射策略。

	步骤2:将每个基因型个体映射到对应的CNN，训练每个CNN，得到验证数据集上的分类精度作为其适应度值。
	
	步骤3:使用竞赛选择法根据适应度选择父个体，然后通过交叉和变异算子生成具有相同预定义大小的新后代。
	
	步骤4:对合并的种群进行环境选择，选择一个能够存活到下一代的新种群。
	
	步骤5:如果不满足终止条件，请转步骤3。否则，选择最适合的个体，终止进化过程。
1
2
3
4
5
6
7
8
9

2.2 随机森林

	优点：与神经网络等其他学习算法相比，随机森林的优点是直接接受离散数据作为输入，几乎不需要额外的参数进行调整，不依赖大量的训练数据。
	
	训练过程：随机森林是一种通过操作一组决策树来进行分类和回归任务的集成学习方法。在随机森林的训练过程中，每棵决策树随机选择整个特征集的一部分，然后学习从所选特征到相应目标的映射。
	
	预测过程：每个决策树选择与训练阶段选择相同的特征，然后输出相应的预测。随机森林使用所选决策树的平均输出作为其最终输出。随机选取整个特征集的一部分也是著名的随机子空间方法[47]，该方法既简单又有效。
1
2
3
4
5

2.3 早停-贝叶斯优化( Freeze thaw Bayesian Optimization algorithm，FBO)：

	——》FBO算法使用基于贝叶斯优化的回归模型来预测CNN的性能。
	——》回归模型是根据第一个t期的学习曲线采样数据建立的，即不同训练期的一系列数据对及其在这些时期的表现。
	——》在经过贝叶斯优化方法优化的回归模型之后，用它来预测同一CNN在T-th epoch T> T的性能。
	优点：不需要训练的大量CNN
	缺点：一旦学习曲线发生变化，会影响预测
1
2
3
4
5

2.4 窥孔算法(the Peephole algorithm，FBO)

	——》窥孔算法用窥视孔算法使用了许多CNN架构及其相应的性能，作为训练样本训练一个长-短时间记忆神经网络的CNN体系结构及其相应的性能。
	——》训练后的神经网络根据其结构直接预测一个新的CNN的性能，这被称为端到端机制，因为输入的端是原始数据，输出的端是分类精度。
	优点：使用端到端方法，较为方便
	缺点：需要大量样本
1
2
3
4

三、 算法主要框架

主要框架由三个块组成，即
（1）数据收集模块（Data Collection）、
（2）高效端到端性能预测器模块（ Efficient End-to-End Performance Predictor，E2EPP）
（3）进化深度学习模块（Evolutionary Deep Learning ，EDL）

3.1 数据收集模块

收集一组训练数据来训练随机森林预测器，其中收集是通过执行相应的EDL而不使用E2EPP来实现的。
每个数据样本由CNN架构和从零开始训练CNN获得的相应分类精度组成。 其次，这些体系结构被编码成离散代码。

3.2 高效端到端性能预测器模块

用于构建具有大量(如K)回归树(表示为CART)的随机森林预测器池

3.3 进化深度学习模块

在EDL的每一代中，新生成的CNN架构被编码为随机森林的输入，然后使用来自预测池的CART的自适应组合来预测其性能

四、具体操作

4.1 编码

a.残差块  (ResNet Blocks，RBs)
b.稠密网络块（DenseNet Blocks ，DBs）
c.池化块（Pooling Blocks ，PBs）

aa.残差单元（ResNet Units ，RUs）
bb.稠密单元（DenseNet Units ，DUs）
1
2
3
4
5
6

每个残差块由多个残差单元组成
每个稠密块由多个稠密单元组成
每个池化块由一个池化层组成：最大池化层和平均池化层

一个CNN架构最多由4个残差块和4个稠密块以及4个池化块组成。
编码规则：

1.残差块编码参数【type，out，amount】，type设置为1。
2.稠密块编码参数【type，out，amount】，type设置为12,20,40。
3.池化块编码参数【[pooling type, layer position】，最大池化设置为1，平均池化设置为0。
4.编码中残差块RBs和稠密块DBs的最大数目表示为Nb,池化块的最大数目表示为Pb。
5.遍历整个CNN架构的长度，如果为残差块和稠密块，就往b_list里面编码，如果为池化块，就往p_list里面添加编码。
6.终止条件|b_list|=3Nb,|p_list|=2Pb。
1
2
3
4
5
6

4.2 训练随机森林

在预测器池中生成大量的CART。 每个CART都是由具有随机特征子集的整个训练数据(即离散变量)，其中每个离散变量被分配0.5的概率，以最大化预测池的多样性。一个CART的每个节点在决策空间中呈现一个矩形区域。 该区域（节点）中这些样本的输出的均方误差决定了该节点是否需要分裂(即均方误差下降是否小于设定阈值Ts，如果是，则该节点为叶节点)。 当得到KCART时，预测池已准备好用于优化器。 训练CART的细节如算法3所示。

训练过程：
	1.对K个已经编码的CART数据进行遍历。
	2.对每个CART数据随机给定一个大小范围[0,1]值。
	3.选择出值大于0.5的元素的CART位置Ii。
	4.训练那些特征图id的CART的Ii。
	5.输出为经过训练的CART和相应ID。
1
2
3
4
5
6

4.3 性能预测

组合策略最初提出的工作是解决决策变量有连续值，论文使用它更新随机预测算法，论文从预测器池中选择QCART，然后使用它们的平均预测作为适合度值。虽然该算法的决策变量是离散的，但实验表明，该组合策略仍然很好。

在每一代中，所有的K个训练的CARTS都重新估计了CNN Ab上具有最佳预测适应度值的性能；然后，根据它们在Ab上的预测值，从K CART中均匀地选择Q。
将Q CARTs组合为集成性能预测器，对亲本和后代群体进行评价。这样的选择是基于CART的性能多样性7围绕当前最好的CNN架构Ab。
之后，使用Q CART的集成预测器对生成的CNN体系结构A进行评估因此，自适应预测器可以平衡适应度景观中的全局趋势和局部信息，其中K CARTs的组合预测了全球平均景观，Q多种CARTS在一个小区域内的景观细化了局部景观。 在一代中预测过程的细节如算法4所示。

性能预测流程：
	1.输入为:
		K个训练过的CART，
		每个CART选择的feature id I，
		当前最好的CNN Ab，
		最多样化的预测Q，
		生成的待评估架构A。
	2.输出为：架构A的适应度值
	3.遍历1到K，从CARTS中选出第i个CART，
	其中x为被编码的ID，y为变量x的I预测分类精度
1
2
3
4
5
6
7
8
9
10

五、论文试验部分

在Cifar10和cifar100实验结果，GPU Day很有优势，并且分类精度也不错。

六、论文总结

主要贡献：
1)提出了一种有效的编码方法，可以提取CNN体系结构的特征作为数值，作为训练随机森林的样本。
2）如果采取森林中最好的个体作为性能预测标本，结果会存在偏差。因此文章采用选择性集成策略，在每一代的局部区域内选择不同的树木进行组合。
3）用了大量实验验证了文章算法：加速进化和性能较优