进化计算在深度学习中的应用 | 附多篇论文解读

随着当今计算能力的大幅度提升和大数据时代的到来,深度学习在帮助挖掘海量数据中蕴含的信息和完成一些人工智能任务中,展现出了非凡的能力。然而目前深度学习领域还有许多问题亟待解决,其中算法参数和结构的优化尤为困难。而进化优化作为一种通用的优化方法,逐渐受到学术界的一些关注和应用,以期能解决以上难题。

基于遗传规划的自动机器学习

自动机器学习(Automated/Automatic Machine Learning, AutoML)作为近年来逐渐兴起的热门研究领域,旨在降低机器学习的门槛,使其更加易用。

一般而言,一个完整的机器学习(特别是监督式机器学习)工作流通常包含以下部分,数据清洗,特征工程,模型选择,训练测试以及超参数调优。每一道工序都有相当多的实现选项,且工序之间相互影响,共同决定最终的模型性能。

对于机器学习使用者而言,针对具体任务设计实现合适的工作流并不容易,在很多情况下可能会耗费大量的时间进行迭代。AutoML 的目标便是尽可能地使以上的过程自动化,从而降低使用者的负担

本次我们要同大家分享的是近年来在 AutoML 领域内比较有影响力的一个工作,基于树表示的工作流优化(Tree-based Pipeline Optimization Tool, TPOT)

TPOT 的作者为 Randal S. Olson 等人,相关文献为 [1] (2016 EvoStar Best Paper) 和[2] (2016 GECCO Best Paper),我们在这里将两篇文献的内容统一为大家作介绍。

 图1:机器学习工作流中被TPOT优化的部分

如图 1 所示,TPOT 希望从整体上自动优化机器学习的工作流 。在 TPOT 中,一个工作流被定义为一棵树,树上每一个非叶子节点为操作(Operator)节点,叶子节点则为数据节点。数据集从叶子节点流入,经过操作节点进行变换,最终在根节点处进行分类/回归,图 2 给出了一个例子。

 图2:基于树表示的工作流的一个例子

TPOT 一共定义了 4 种操作节点类型(见图 3),分别是预处理、分解/降维特征选择以及学习模型。这些操作的底层实现均是基于 Python 的机器学习库 scikit-learn。

 图3:TPOT操作节点类型

有了以上基于树的表示,TPOT 直接利用遗传规划(具体来说,是 Python 库 DEAP 中的 GP 实现)对工作流进行优化。在搜索过程中,任一工作流首先在训练集上训练,然后在独立的验证集上评估(另一种更为耗时的选项是交叉验证)。在搜索结束后,TPOT 将返回最好的工作流所对应的代码。

TPOT 的一个潜在问题在于可能会产生过于复杂的工作流,从而导致过拟合。针对这个问题,论文 [2] 对 TPOT 作出了拓展,将工作流复杂度(即包含的操作节点个数)作为第二个优化目标,提出了 TPOT-Pareto,其使用了类似于 NSGA 中所采用的选择算子。

 图4:部分实验结果

论文 [1] 和 [2] 在很多任务上对 TPOT 和 TPOT-Pareto 进行了评估,实验结果(图 4 给出了在 UCI 数据集上的部分实验结果,其中 Random Forest 包含了 500 棵决策树,TPOT-Random 采用了随机搜索而不是 GP)表明了 TPOT 系的方法在很多任务上都能取得不错的效果。

 图5:工作流复杂度对比

图 5 给出了不同方法得到的模型的复杂度,可以看出 TPOT-Pareto 确实能得到更为精简的工作流。一个比较有趣的问题是采用随机搜索的 TPOT-random 在很多任务上(以更高的工作流复杂度)也能够达到 TPOT 以及 TPOT-Pareto 相当的效果。 

TPOT 项目已经开源,且仍在开发迭代中,目前整个社区相当活跃,已经有了 4000+ 的 star 和 680+ 的 fork。

TPOT项目地址:

https://github.com/EpistasisLab/tpot

参考文献

[1] Olson, Randal S., et al. “Automating biomedical data science through tree-based pipeline optimization.” European Conference on the Applications of Evolutionary Computation. Springer, Cham, 2016. 

[2] Olson, Randal S., et al. “Evaluation of a tree-based pipeline optimization tool for automating data science.” Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, 2016.

多目标演化优化深度神经网络

本文主要侧重于分享近期基于多目标演化优化深度神经网络的工作。由于笔者能力有限,如果分享过程中存在疏忽,还请大家不吝赐教与指正。

第一个工作发表于 IEEE Transaction on Neural Networks and Learning Systems 2016,来自 Chong Zhang,Pin Lim,K. Qin 和 Kay Chen Tan 的文章Multiobjective Deep Belief Networks Ensemble for Remaining Useful Life Estimation in Prognostics本文为预估系统剩余使用周期设计了多目标深度网络集成算法(Multiobjective Deep Belief Networks Ensemble,MODBNE)。

MODBNE 是一个集成学习模型,其以单个 DBN(Deep Belief Networks)模型的准确性和多样性作为优化目标,使用 MOEA/D 算法对 DBN 模型进行优化,将最终获得的一系列占优的 DBN 模型用于集成学习模型。

其中,演化种群中的每一个个体代表一个 DBN 模型,其决策空间由 DBN 模型的隐藏神经元数量、神经网络中的权重以及推理过程中需要的学习率构成,这意味着每一个个体都代表着不同结构的 DBN 模型。

最后,通过以平均学习错误率为目标的单目标 DE 算法优化集成学习模型中各个模型的比重。

MODBNE 在 NASA 的 C-MAPSS 数据集上进行实验,结果表明该算法明显优于其他现有的算法。

第二个工作发表于 IEEE Transaction on Neural Networks and Learning Systems 2017,来自 Jia Liu,Maoguo Gong,Qiguang Miao,Xiaogang Wang 和 Hao Li 的文章 Structure Learning for Deep Neural Networks Based on Multiobjective Optimization论文提出一种使用多目标优化算法优化深度神经网络的连接结构的方法

首先,将多层神经网络看成多个单层的神经网络,逐层优化。在优化每一层的时候,以神经网络的表达能力(Representation Ability)和神经网络连接的稀疏性作为优化目标,使用 MOEA/D 算法进行优化。

其中,演化种群中的每一个个体代表单层神经网络的一种配置,神经网络的表达能力用观测数据的 PoE(Products of Experts)评估,稀疏性由神经节点之间连接的个数表示。

通过用该算法优化单层神经网络、多层神经网络以及一些应用层面的神经网络进行测试,实验验证该方法可以大幅提升深度神经网络的效率。

演化深度神经网络

演化算法和人工神经网络都可以看作是对某些自然过程的抽象。早在上世纪 90 年代早期,就有研究试图将二者结合起来,并最终形成了演化人工神经网络(Evolutionary Artificial Neural Networks,EANN)这一分支。

EANN 旨在利用演化算法强大的搜索能力在神经网络的多个层面上(全局参数学习率,网络拓扑结构,局部参数如连接权值)寻优。

在实际中,这种利用工具来自动设计算法的思路可以在很大程度上减轻算法设计者的负担。同时,在计算资源充足的条件下,针对给定的任务,演化算法往往能成功地发现有效的神经网络结构

近年来,计算能力的大幅提升和大数据时代的到来助推了深度学习的兴起,在此期间各种深度神经网络(Deep Neural Networks,DNN)被相继提出。然而即使在今天,针对特定问题设计有效的深度神经网络仍然是一项非常困难的任务。

以此为背景,利用自动化工具(比如演化算法)来设计深度神经网络逐渐受到了学术界的一些关注。本文将同大家分享演化深度神经网络的一项近期工作。由于笔者能力有限,如果分享过程中存在疏忽,还请大家不吝赐教与指正。 

由于 DNN 连接数巨大,利用演化算法直接优化 DNN 权值的计算代价太高。因此一般采用两层(bilevel)策略对 DNN 进行优化,其顶层由演化算法优化 DNN 的结构和全局参数,其底层依然采用随机梯度下降的方法训练连接权值。

发表在 ICML 2017,来自 Google Brain 的 Esteban Real,Sherry Moore,Andrew Selle,Saurabh Saxena,Yutaka Leon Suematsu,Quoc Le,Alex Kurakin 的文章Large-Scale Evolution of Image Classifiers提出了一种针对图像分类的 DNN 的分布式演化算法

 图1:文章提出的分布式演化算法

算法的流程如图 1 所示,该算法维护了一个 DNN 种群,种群中每一个个体都是一个已经训练好的 DNN 模型,其适应度即为该模型在验证集上的准确率

大量的计算节点(worker)被用来对 DNN 种群进行演化。具体而言,所有的 worker 处在分布式环境下,共享存储 DNN 种群的文件系统,并以异步的方式工作。

每一个当前空闲的 worker 都会从 DNN 种群中随机选取两个 DNN 模型,然后将较差的 DNN 直接从种群中删除,并基于较好的 DNN 变异生成一个子代个体加入 DNN 种群。

整个过程中个体的编码是图,图上每一个顶点表示一个三阶张量(比如卷积层)或者一个激活函数,每一条边则表示恒等连接(identity connection)或者卷积。变异操作则包括重置权值,插入删除神经层,插入删除神经层之间的连接等等。

实验中,种群规模被设置为 1000,并有 250 个 worker 参与,在 CIFAR-10 和 CIFAR-100 数据集上的实验结果如图 2 所示,相比于手工设计的 DNN,用此分布式演化算法得到的 DNN 能够取得有竞争力的结果。

 图2:在CIFAR-10和CIFAR-100上的测试结果

更多论文推荐

最后,再附上 Github 上几篇进化计算在 AutoML 上的应用论文。

■ 论文 | Evolving Neural Networks through Augmenting Topologies

■ 链接 | https://www.paperweekly.site/papers/1979

■ 作者 | Kenneth O. Stanley / Risto Miikkulainen

Abstract

An important question in neuroevolution is how to gain an advantage from evolving neural network topologies along with weights. We present a method, NeuroEvolution of Augmenting Topologies (NEAT), which outperforms the best fixed-topology method on a challenging benchmark reinforcement learning task. We claim that the increased efficiency is due to (1) employing a principled method of crossover of different topologies, (2) protecting structural innovation using speciation, and (3) incrementally growing from minimal structure. We test this claim through a series of ablation studies that demonstrate that each component is necessary to the system as a whole and to each other. What results is significantly faster learning. NEAT is also an important contribution to GAs because it shows how it is possible for evolution to both optimize and complexify solutions simultaneously, offering the possibility of evolving increasingly complex solutions over generations, and strengthening the analogy with biological evolution.

■ 论文 | Autostacker: A Compositional Evolutionary Learning System

■ 链接 | https://www.paperweekly.site/papers/1980

■ 作者 | Boyuan Chen / Harvey Wu / Warren Mo / Ishanu Chattopadhyay / Hod Lipson

Abstract

We introduce an automatic machine learning (AutoML) modeling architecture called Autostacker, which combines an innovative hierarchical stacking architecture and an Evolutionary Algorithm (EA) to perform efficient parameter search. Neither prior domain knowledge about the data nor feature preprocessing is needed. Using EA, Autostacker quickly evolves candidate pipelines with high predictive accuracy. These pipelines can be used as is or as a starting point for human experts to build on. Autostacker finds innovative combinations and structures of machine learning models, rather than selecting a single model and optimizing its hyperparameters. Compared with other AutoML systems on fifteen datasets, Autostacker achieves state-of-art or competitive performance both in terms of test accuracy and time cost.

■ 论文 | Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning

■ 链接 | https://www.paperweekly.site/papers/1981

■ 源码 | https://github.com/uber-common/deep-neuroevolution

Abstract

Deep artificial neural networks (DNNs) are typically trained via gradient-based learning algorithms, namely backpropagation. Evolution strategies (ES) can rival backprop-based algorithms such as Q-learning and policy gradients on challenging deep reinforcement learning (RL) problems. However, ES can be considered a gradient-based algorithm because it performs stochastic gradient descent via an operation similar to a finite-difference approximation of the gradient. That raises the question of whether non-gradient-based evolutionary algorithms can work at DNN scales. Here we demonstrate they can: we evolve the weights of a DNN with a simple, gradient-free, population-based genetic algorithm (GA) and it performs well on hard deep RL problems, including Atari and humanoid locomotion. The Deep GA successfully evolves networks with over four million free parameters, the largest neural networks ever evolved with a traditional evolutionary algorithm. These results (1) expand our sense of the scale at which GAs can operate, (2) suggest intriguingly that in some cases following the gradient is not the best choice for optimizing performance, and (3) make immediately available the multitude of neuroevolution techniques that improve performance. We demonstrate the latter by showing that combining DNNs with novelty search, which encourages exploration on tasks with deceptive or sparse reward functions, can solve a high-dimensional problem on which reward-maximizing algorithms (e.g.\ DQN, A3C, ES, and the GA) fail. Additionally, the Deep GA is faster than ES, A3C, and DQN (it can train Atari in ∼4 hours on one desktop or ∼1 hour distributed on 720 cores), and enables a state-of-the-art, up to 10,000-fold compact encoding technique.

■ 论文 | Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents

■ 链接 | https://www.paperweekly.site/papers/1982

■ 源码 | https://github.com/uber-common/deep-neuroevolution

Abstract

Evolution strategies (ES) are a family of black-box optimization algorithms able to train deep neural networks roughly as well as Q-learning and policy gradient methods on challenging deep reinforcement learning (RL) problems, but are much faster (e.g. hours vs. days) because they parallelize better. However, many RL problems require directed exploration because they have reward functions that are sparse or deceptive (i.e. contain local optima), and it is not known how to encourage such exploration with ES. Here we show that algorithms that have been invented to promote directed exploration in small-scale evolved neural networks via populations of exploring agents, specifically novelty search (NS) and quality diversity (QD) algorithms, can be hybridized with ES to improve its performance on sparse or deceptive deep RL tasks, while retaining scalability. Our experiments confirm that the resultant new algorithms, NS-ES and a version of QD we call NSR-ES, avoid local optima encountered by ES to achieve higher performance on tasks ranging from playing Atari to simulated robots learning to walk around a deceptive trap. This paper thus introduces a family of fast, scalable algorithms for reinforcement learning that are capable of directed exploration. It also adds this new family of exploration algorithms to the RL toolbox and raises the interesting possibility that analogous algorithms with multiple simultaneous paths of exploration might also combine well with existing RL algorithms outside ES.

入门
2
相关数据
激活函数技术
Activation function

在 计算网络中, 一个节点的激活函数定义了该节点在给定的输入或输入的集合下的输出。标准的计算机芯片电路可以看作是根据输入得到"开"(1)或"关"(0)输出的数字网络激活函数。这与神经网络中的线性感知机的行为类似。 一种函数(例如 ReLU 或 S 型函数),用于对上一层的所有输入求加权和,然后生成一个输出值(通常为非线性值),并将其传递给下一层。

神经网络技术
Neural Network

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

交叉验证技术
Cross validation

交叉验证,有时亦称循环估计, 是一种统计学上将数据样本切割成较小子集的实用方法。于是可以先在一个子集上做分析, 而其它子集则用来做后续对此分析的确认及验证。 一开始的子集被称为训练集。而其它的子集则被称为验证集或测试集。交叉验证的目标是定义一个数据集到“测试”的模型在训练阶段,以便减少像过拟合的问题,得到该模型将如何衍生到一个独立的数据集的提示。

深度神经网络技术
Deep neural network

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

进化计算技术
Evolutionary computation

进化计算是遗传算法、进化策略、进化规划的统称。进化计算起源于20世纪50年代末,成熟于20世纪80年代,目前主要被应用于工程控制、机器学习、函数优化等领域。

集成学习技术
Ensemble learning

集成学习是指使用多种兼容的学习算法/模型来执行单个任务的技术,目的是为了得到更佳的预测表现。集成学习的主要方法可归类为三大类: 堆叠(Stacking)、提升(Boosting) 和 装袋(Bagging/bootstrapaggregating)。其中最流行的方法包括随机森林、梯度提升、AdaBoost、梯度提升决策树(GBDT)和XGBoost。

降维技术
Dimensionality reduction

降维算法是将 p+1 个系数的问题简化为 M+1 个系数的问题,其中 M<p。算法执行包括计算变量的 M 个不同线性组合或投射(projection)。然后这 M 个投射作为预测器通过最小二乘法拟合一个线性回归模型。两个主要的方法是主成分回归(principal component regression)和偏最小二乘法(partial least squares)。

特征工程技术
Feature engineering

特征工程是利用数据所在领域的相关知识来构建特征,使得机器学习算法发挥其最佳的过程。它是机器学习中的一个基本应用,实现难度大且代价高。采用自动特征工程方法可以省去采用人工特征工程的需求。Andrew Ng 说“挖掘特征是困难、费时且需要专业知识的事,应用机器学习其实基本上是在做特征工程。”

超参数技术
Hyperparameter

在机器学习中,超参数是在学习过程开始之前设置其值的参数。 相反,其他参数的值是通过训练得出的。 不同的模型训练算法需要不同的超参数,一些简单的算法(如普通最小二乘回归)不需要。 给定这些超参数,训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式,并且必须对其进行调整以便模型能够最优地解决机器学习问题。 在实际应用中一般需要对超参数进行优化,以找到一个超参数元组(tuple),由这些超参数元组形成一个最优化模型,该模型可以将在给定的独立数据上预定义的损失函数最小化。

学习率技术
Learning rate

在使用不同优化器(例如随机梯度下降,Adam)神经网络相关训练中,学习速率作为一个超参数控制了权重更新的幅度,以及训练的速度和精度。学习速率太大容易导致目标(代价)函数波动较大从而难以找到最优,而弱学习速率设置太小,则会导致收敛过慢耗时太长

机器学习技术
Machine Learning

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

神经元技术
neurons

(人工)神经元是一个类比于生物神经元的数学计算模型,是神经网络的基本组成单元。 对于生物神经网络,每个神经元与其他神经元相连,当它“兴奋”时会向相连的神经元发送化学物质,从而改变这些神经元的电位;神经元的“兴奋”由其电位决定,当它的电位超过一个“阈值”(threshold)便会被激活,亦即“兴奋”。 目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。 在这个模型中,神经元通过带权重的连接接处理来自n个其他神经元的输入信号,其总输入值将与神经元的阈值进行比较,最后通过“激活函数”(activation function)产生神经元的输出。

过拟合技术
Overfitting

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

参数技术
parameter

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

规划技术
Planning

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

随机森林技术
Random Forest

在机器学习中,随机森林是一个包含多个决策树的分类器,并且其输出的类别是由个别树输出的类别的众数而定。 Leo Breiman和Adele Cutler发展出推论出随机森林的算法。而"Random Forests"是他们的商标。这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林(random decision forests)而来的。这个方法则是结合Breimans的"Bootstrap aggregating"想法和Ho的"random subspace method" 以建造决策树的集合。

随机梯度下降技术
Stochastic gradient descent

梯度下降(Gradient Descent)是遵循成本函数的梯度来最小化一个函数的过程。这个过程涉及到对成本形式以及其衍生形式的认知,使得我们可以从已知的给定点朝既定方向移动。比如向下朝最小值移动。 在机器学习中,我们可以利用随机梯度下降的方法来最小化训练模型中的误差,即每次迭代时完成一次评估和更新。 这种优化算法的工作原理是模型每看到一个训练实例,就对其作出预测,并重复迭代该过程到一定的次数。这个流程可以用于找出能导致训练数据最小误差的模型的系数。

验证集技术
Validation set

验证数据集是用于调整分类器超参数(即模型结构)的一组数据集,它有时也被称为开发集(dev set)。

权重技术
Weight

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

深度学习技术
Deep learning

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法。观测值(例如一幅图像)可以使用多种方式来表示,如每个像素强度值的向量,或者更抽象地表示成一系列边、特定形状的区域等。而使用某些特定的表示方法更容易从实例中学习任务(例如,人脸识别或面部表情识别)。 近年来监督式深度学习方法(以反馈算法训练CNN、LSTM等)获得了空前的成功,而基于半监督或非监督式的方法(如DBM、DBN、stacked autoencoder)虽然在深度学习兴起阶段起到了重要的启蒙作用,但仍处在研究阶段并已获得不错的进展。在未来,非监督式学习将是深度学习的重要研究方向,因为人和动物的学习大多是非监督式的,我们通过观察来发现世界的构造,而不是被提前告知所有物体的名字。 至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

张量技术
Tensor

张量是一个可用来表示在一些矢量、标量和其他张量之间的线性关系的多线性函数,这些线性关系的基本例子有内积、外积、线性映射以及笛卡儿积。其坐标在 维空间内,有 个分量的一种量,其中每个分量都是坐标的函数,而在坐标变换时,这些分量也依照某些规则作线性变换。称为该张量的秩或阶(与矩阵的秩和阶均无关系)。 在数学里,张量是一种几何实体,或者说广义上的“数量”。张量概念包括标量、矢量和线性算子。张量可以用坐标系统来表达,记作标量的数组,但它是定义为“不依赖于参照系的选择的”。张量在物理和工程学中很重要。例如在扩散张量成像中,表达器官对于水的在各个方向的微分透性的张量可以用来产生大脑的扫描图。工程上最重要的例子可能就是应力张量和应变张量了,它们都是二阶张量,对于一般线性材料他们之间的关系由一个四阶弹性张量来决定。

特征选择技术
Feature selection

在机器学习和统计学中,特征选择(英语:feature selection)也被称为变量选择、属性选择或变量子集选择。 它是指:为了构建模型而选择相关特征(即属性、指标)子集的过程。

准确率技术
Accuracy

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

返回顶部