Py学习  »  机器学习算法

当机器学习遇上进化算法

混沌巡洋舰 • 4 年前 • 488 次点击  

进化,是生物智能演化的原动力。 学习, 是人类文明产生的原动力,也是当下红红火火的AI进步的原动力。 如果这两种神秘的力量结合, 我们会得到一个怎样的物种呢?虽然说这方面的尝试还不多, 不过我们已经可以在一些过去人的研究中见出端倪。 


首先,我们说两种算法的本质都是在做优化。 在充满随机性的世界里, 大部分的自然过程趋势是熵增,耗散,或者说随机性的增加。而唯有生物的进化和学习,却可以抵抗这种趋势,在随机中产生有序,产生结构。 


虽然都在做优化, 它们的优势和缺点也非常明显。  让我们来概述一下两种方法的核心。 


进化算法vs机器学习


进化算法

进化算法建立在基因之上,基因 - 可以理解为生命在各种条件下的一组行为策略。比如吃什么, 向什么方向移动,肤色的选择等。 这组策略被一套叫DNA的大分子固定, 也就是我们常常说的遗传编码 , 它通过一个复杂的化学反应, 制造RNA和特定的蛋白质,而一切生命现象都是由特定蛋白质实现的, 我们简单的说就是生命策略, 比如在外界环境出现如何变化时候如何反应。 你可以把DNA的编码看成一系列的if else语句, 就是在某种条件下, 触发某个蛋白质, 实现某一个功能。

那么进化算法包含以下要素:

1,生物通过基因编码生存策略。 基因即一组可以编码蛋白质的生物大分子。

2, 单组策略的存在时间有限, 它会以繁殖的形式得到一个和自己一样的策略, 但是这个过程不是完全精确的, 它会以一定的方式出错或者说变化, 这恰恰使得下一代的策略可以轻微的偏离上一代。 从而在一段时间里, 形成越来越多的策略,我们叫做基因池。

3, 有的时候不同的基因会发生交叉, 也就是说把两组策略把各自的一部分给对方, 然后形成新的策略组合。 这种重组产生新的基因的速度会比变异快的多, 也就是我们说的交配。

3, 环境会评估某个策略(DNA) 是不是适合自己, 这个通常由一个叫适应度函数的东西表达。 适应度越高, 基因就是越适应当下环境。这个适应度很像机器学习里的目标函数。

3, 经过一段时间, 适应环境的策略会比不适应的环境的策略得到更多的个体,因为它自身存活的概率更高, 这样, 最终环境里数量最多的, 是最适应环境的策略。这样的策略不一定有一个。

4, 环境会变化。当环境变化, 最适宜的策略发生变化, 这个时候最适合的策略也发生变化, 导致新的物种和生态系统的生成。


机器学习:


理解机器学习最简单的角度是从一个计算机程序来看: 学习算法是一段特殊的程序。 

如果说一段程序可以看做一连串从输入到输出的过程,无论是工程师还是程序员,我们都想通过设计来完成某种功能, 比如说你做一个网页, 你要画视觉图, UI图, 前端后端交互图,我们都是在给计算机设计一套解决具体问题的流程, 如做一个淘宝网。

而机器学习呢? 机器学习是你不去设计, 而让计算机自己去磨,如同用一套很一般的模子里打磨出能够解决特定问题的武器。 这点上,机器学习做的正是” 自发能够产生解决问题的程序的程序” , 一些机器学习的经典算法如线性回归, SVM, 神经网络, 它们单个都不能解决问题, 但是通过“学习”却可以一会去预测房价, 一会去寻找美女。


生物世界的学习与机器学习最接近的是强化学习。 强化学习的目标函数是未来的奖励总和, 智能体需要学习到合理的行为来实现奖励最大化。 最简单的强化学习即条件反射。 与进化算法非常类似的, 强化学习在优化行为策略, 但是与之不同的是, 强化学习的优化方法是下面要讲的梯度方法, 一种更为贪婪, 高效的优化方法。 


整个机器学习依靠的寻求最优的方法就是梯度优化, 这个方法相比进化算法, 更具方向性和目的性, 虽然我依然不知道我要寻找的那个最优是什么, 但是我每往前走一步, 都希望最大程度的接近它, 或者说贪婪的接近它, 这个时候我们就会设置一个目标函数(类似于进化算法里的适应度), 然后我们让参数顺着最快速减少目标函数的方向去自动调整, 如下图。


深度学习作为机器学习的发展, 其成功几乎完全依靠了以反向传播为基础的梯度下降方法, 而事实上也是, 梯度下降在很多时候更加精准。但是, 如果你认为因为梯度下降完全优于进化算法的优化方法, 就错了。 

首先, 关于优化问题, 我最喜欢用的例子是一个小姑娘在山上采集蘑菇, 地势越低的地方蘑菇越多。 因而, 她需要找到一个最快的到达山谷的路径,小姑娘视力不好,因此她最好的做法就是用脚感受当下地势下降最快的方向往前走一步, 这就是梯度下降法。 在一个山谷形状比较简单的地方, 犹如上图, 你是很容易达到这个目标的。


然而真实世界的地形却并非如此简单, 比如下图,你看到无数的波峰和波谷。 每个波谷都代表一个局部最小值。 而事实上哪一个谷是最低谷, 这件事并没有那么容易。 如果你采用机器学习所使用的梯度下降, 则你极大可能会陷入到某个小的山谷里长期停滞。 当然, 在深度学习的问题里, 局部最优往往足够好了。 可是在最真实的情况下, 这下波峰和波谷的高低也可能是动态调整的, 今天的谷底可能是明天的波峰。 



地形比较崎岖


而进化算法呢? 进化算法就不一样了, 进化算法相当于一次释放出无数个小姑娘(基因池), 这些小姑娘, 各自在这个崎岖的地形里试错寻找蘑菇丰盛的最低点。 每个人的搜索策略(每个人的基因)有不同。 虽然趋近每个小山谷的速度不如梯度下降。 但是最终找到那个最优解的可能反而还更快。 这里面最核心的是, 用一个群体替代个体, 在优化的同时更多的保持多样性。 就如同自然界的物种, 有些物种比如说熊猫,居然进化成那么可爱但是站动力不强的样子, 但是自然还是没有淘汰它。 因为这种当下看着不太有利的基因, 不一定在自然巨变中就一定是没有用的。 


进化算法结合机器学习之最小案例


废话少说,我们来看看把学习算法和进化算法合在一起, 会发生什么? 

我们从一篇1994年的文章开始看起(Learning and evolution in neural networks by Nolfi, Elman, & Parisi)  这篇文章的作者试图阐述一件事,就是如果进化和学习是相辅相成的,不仅进化可以促进学习能力的增加,反过来, 学习也会促进进化的过程 , 造成类似于拉马克进化的效果。 


来看如下的儿童游戏:  在一个grid走方格任务里,模拟生物需要在最短的时间里收集足够多的食物(用F代表),  这个生物由一个菜鸟级的神经网络代表。 神经网络接受的输入数据来自周围的食物的方向和距离远近(一种视觉,足以让你找到临近的食物)。 它的行为呢? 直线前进, 向左或向右转动。  神经网络的输出决定它的行为。 

进化算法在这里具体管什么呢? 由于网络只有7个隐层神经元, 和两个动作输出神经元, 它的策略就是由它们的权重表达的。 而一组权重, 就可以看作一组DNA。 我们一开始准备很多这样的权重, 代表不同的策略(基因池)然后放到略有不同的环境里让这些虚拟生物跑, 跑到一定时间,就开始看它们采集到的食物的数量(fitness适应度), 那些食物采集比较少的生物, 而保留优胜者,经过这样一个经典的进化算法流程, 生物就可以学到上图所示的那种策略。 


然而, 文章的发出者偏偏不是等闲之辈, 这个网络在干这件事之余还干的一件事是, 进行预测! 不停的预测下一刻它会看到的东西 ,或者说理解它的动作将给它带来什么样的环境变化。你看, 这不就是当下大名鼎鼎的好奇心或预训练的前身吗, 看来还真的是我们总在重复前辈的思想。 


预测这个事情会产生什么效果呢? 通过预测的对错(不停的把自己想到的和最终结果对比),它会开始进行学习,一个重点在于, 学习的过程只在代系之内, 也就是说比如100轮(一轮就是一次游戏)做一次进化算法的迭代, 那么学习可能是在这100轮里每轮都进行的, 但是学习的结果不会传递给下一代, 就好像你死了, 你头脑里的知识也消失了。   那么随之而来的是什么现象呢? 学习不是就没有意义了吗? 


不是。  在实验中我们发现, 这个预测性学习, 不仅仅是学会了预测, 而且, 它让虚拟生物在进化算法中得到的食物采集能力, 也就是说任务采集能力大大增加,也就是说,进化算法被监督学习助力了!  

这件事表明看上去匪夷所思, 它就好像是我们过去所说的拉马克进化的复兴。拉马克进化是说, 亲代在后来习得的能力是可以通过遗传传递给子代的, 用一句话就是“用进废退” 。如果你看上面的曲线, 仿佛是说监督学习的个体, 由于亲代可以把它监督学习的成果传递给下一代, 引起了具备监督学习的批次进化速度更快。 事实上呢? 这是不可能的, 因为每一次学习到的权重并不会传递给子代, 虽然说传递是会发生的, 但是学习得到的权重改变却没有被传递。 


那么学习是如何作用于进化的呢?用一句话概括这个过程的本质是: 学习使得进化的选择效应发生了变化。 那些通过监督学习能够最大程度的改变命运的个体,每一次被选择出来, 而非像在没有学习的版本里只是天生丽质被选择了。 一句话, 学习, 使得进化的选择更准确。 


如果你这样理解这件事情, 还是会觉得有点民科, 我们可以给出一个比较数学的版本。 你依然想象一个高低不平的山区地图, 然后我们希望在上面寻找最小值。 每一个不同的策略, 代表地图上的一个点。 那么学习的效果是什么呢?学习可以在局部改变你的策略, 这就好比, 我们的策略可以从当下的一个点, 丰富到周围的很多点, 甚至是一个小的局域。 由于我们的地图是极度凹凸不平的, 可能在很小的局域里就包含了很多的地势变化。 一个没有学习的群体, 它的效果是在这个凹凸不平的地图上撒上很多点, 而有学习的呢?就是撒上很多小圆圈, 如果小圆圈所覆盖的地方包含了极小值, 我们就可以迅速的锁定它。 也就是说, 虽然学习本身的成果无法遗传, 通过学习, 我们才能更好判断哪些是值得保留的真正优势策略。 用优化的语言说就是学习通过局部优化增加了进化这个全局搜索器的效率。 


好了 , 这个游戏看起来有点简单, 但那时你一定不要小瞧简单的游戏, 做AI, 你就应该从toy model 里理解问题, 然后看你的想法是否salable, 可扩展。 恰恰是, 这篇文章的成果可以映射当下的一系列AI成果, 直到征服星际争霸的alpha-star。


如果你追溯这条线的发展, 你首先会看到。机器学习和进化算法, 在这篇文章后, 都得到了飞速发展, 但是机器学习要快很多。

然后你会看到, 进化算法开始桥悄悄进入很多机器学习框架。而且, 正在实现之前机器学习所完全不可能实现的任务。  


进化算法结合机器学习带来的无限可能


首先, 进化算法的本质是一种集群算法, 通过集群, 遍历式的搜索策略空间。 这点, 就比梯度下降更好克服非线性问题里局部极小的问题。  而且在用梯度方法不好并行的一些问题里, 如RNN的训练, 这种方法却可以产生出并行的威力。 再有,进化算法可以帮助我们做梯度下降所难以实现的改变,梯度下降需要问题可以微分, 而进化算法就自由的多, 只要你能够定义适应度和策略就可以做。 它特别擅长做超参数的调整, 改进网络架构, 甚至可以改变学习算法本身。 一句话就是说, 进化算法迈大步, 梯度下降局部调。 这样的思路结合,可以解决相当困难的问题。最后, 进化算法更有遐想力的地方, 还在于它所带来的智能体间合作与博弈的可能。 


我们先来看合作, 后面的文章来自那个AI界的不为人赏识的教父级人物Schmidhuber: Accelerated Neural Evolution through Cooperatively Co-evolved Synapses  这篇08年左右的文章,将这种思路几乎用到了极致。这篇文章用进化算法直接解决了一个传统强化学习的经典任务pole balancing的较困难版本, 并且证明它在这类问题上比强化学习更有可扩展性。  联想到强化学习运用到现实生活中, 却经常碰壁, 原因就是鲁棒性差, 可扩展性不高,进化算法会是对它的一个极好补充。

 

那么何为合作? 这篇文章里, Schmidhuber直接用进化算法来优化一个模块化的网络。 网络中的每个模块可以看作群体中的一个个体, 而它们的组合网络就可以解决更复杂的任务, 合作体现在网络模块之间的配合。 这点让人不仅想到那个群体和个体的界限问题。 人由不同的器官组成, 人脑由不同脑区组成, 社会由人组成, 这些都可以看作一种广义的合作。 如果每个个体都很优秀, 组成的国家很弱小, 它还是会灭亡,基因传不下去。因此, 进化就会鼓励合作。同样的道理, 在这个模块化的网络里, 进化算法会促进模块间更好的配合最终完成复杂的控制任务。  


四个模块的网路, 网络权重由一组“染色体”编码Accelerated Neural Evolution through Cooperatively Co-evolved Synapses




经典强化学习游戏, 平衡杆, 我们需要以恰当的方法移动小车,让上面的倒立单摆稳定。 这个游戏有很多复杂版本。


进化算法和机器学习混合的最新应用案例 - AlphaStart: AlphaStart, 在星际争霸这样级别的游戏击败人类, 应该说这是一个了不起的胜利, 因为星际争霸这个游戏比围棋要接近真实世界很多, 信息是局部的,远方的世界笼罩在黑雾里, 当下和未来是连续的, 战略需要跨越很多时间尺度。这些问题,需要比阿法狗更加复杂的接近方法。  AlphaStart以一个具有记忆的神经网络LSTM为基础, 然后用到的学习方法, 正是进化算法加机器学习(强化+监督学习)。应该说, 这才是这套方法的灵魂(参见AlphaStart: An Evolutionary Computation Perspective)。 


它的思想简直是对1994文章的升华, 把拉马克进化真正用起来。 也就是说, 我们把一个最外层的代系间的进化过程, 和内层的持续不断的强化学习结合起来。 内层的学习会影响外层的进化。 更重要的是, 在这里, 我们通过进化引入了不同参数的网络(智能体)间的博弈。 那些从一个根基上产生的稍有不同的网络, 会通过学习来改变自己, 并在战斗中一决雌雄, 当一轮结束, 优胜者将改写失败者的基因, 但失败者不会马上消失,正如文章中所说:

“The fittest solutions survive longer, naturally providing a form of elitism/hall of fame, but even ancestors that aren’t elites may be preserved, maintaining diversity.”


alphastar的进化历程图, 我们看到在每个时间点我们得到的都不是一个点, 而是一群点,代表我们式以族群为单元进化的, alaphastart不是一个网络


这样, 我们就鼓励了种群的多样性, 而得到一个在纳什均衡状态下多样化的解空间(一组不同策略的组合)。也就说, 最后的最优解不是一个网络, 一个是策略集群。 如此, 我们就可以玩转很复杂的问题。  保持多样性的好处还是在之前的小姑娘采蘑菇的例子说的,任何优化都是在高低不平的空间里寻找最低点, 而在星际这样复杂的游戏中, 整个地形都在缓慢或迅速的变化着, 之前处于劣势的个体,可能在下一个拐点变成处于优势的。 这也是进化算法的温情之处, 世界是充满不确定性的,因此我不要斩尽杀绝。 


正如schmidhuber在上一篇文章说的, 这一类损失函数对应的地形动态变化的问题里, 那些传统的优化问题甚至会完全失效(稳定性丧失), 而最后剩下的,会是进化算法。 


deepmind的宣传稿里有一个非常好的例子, 我不是星际玩家, 但是你应该可以很快理解。 大意说的是在早期具有优势的策略(比如用某种武器迅速偷袭对方的高风险策略), 会随着时间发生变化, 有的时候, 这种变化完全不是之前基础的改进, 而是从完全不同的分支长出来的(比如早期通过增加工人取得经济优势,这与风险策略几乎相反,而这个策略后来居上)。如果你砍掉所有的分支, 你是否还能找到那个后期的优势策略呢?  那个后来最优的策略, 压根不是你先前的最优渐进发展出来的。     

“As the league progresses and new competitors are created, new counterstrategies emerge that are able to defeat the earlier strategies. While some new competitors execute a strategy that is merely a refinement of a previous strategy, others discover drastically new strategies consisting of entirely new build orders, unit compositions, and micro-management plans.“


在进化算法和学习算法的结合里, 我们看到了一种AI发展的未来路径。 我们也看到了让AI从一个单个学习的网络, 发展到群体, 并通过群体间的合作和博弈促进发展的某种必要性。 在整个过程里, 我们看到人类自己智能产生和发展的影子。 这样的一条道路, 会给我们带来怎样的未来, 让我们拭目以待。



更多内容请关注作者新书


Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/31509
 
488 次点击