Uber AI实验室：遗传算法PK随机梯度下降，欢迎来到深度神经进化时代！

2017 年 12 月 19 日 论智 Bot

来源：Uber Engineering

编译：Bot

编者按：今天，Uber AI实验室发表长文，对近期发表的5篇关于神经进化的论文做了总结，指出遗传算法也可用于DNN优化，结合了随机梯度下降（SGD）的一些思想后，改良版的GA和ES在优化上表现出了令人惊奇的效果。事实上，自今年OpenAI提出进化策略在强化学习问题上有优秀表现后，遗传算法、进化策略等传统概念再一次成为机器学习领域的热门词汇，大有“文艺复兴”的趋势，那Uber在文章中讲了什么呢？请跟着论智去一探究竟。

以下内容由论智编译自原文：

在深度学习领域，现在人们常用随机梯度下降（SGD）算法来对层数很深、拥有数百万个连接的深层神经网络（DNN）进行训练。许多人认为，SGD对梯度的有效计算在这当中扮演着重要角色。为此，我们最近发布了5篇论文来支持另一种新观点——神经进化（neuroevolution），它指出遗传算法（genetic algorithm，GA）也可用于神经网络优化，经GA训练的DNN在强化学习问题上也有出色表现。

遗传算法在训练DNN上的竞争力

在实验中，我们使用了一种自创的新型DNN演化方法，让神经网络玩雅达利像素游戏。我们惊奇地发现，最简单的遗传算法竟然能训练一个包含400万参数的深层卷积网络，经它训练的模型不仅在许多游戏的效果上胜过使用经典强化学习算法的网络，而且由于是并行计算，它在速度上也有显著优势。

这一结果令我们始料未及，因为遗传算法不基于梯度计算，所以一般人们认为它不能很好地扩展到如此大的参数空间，并且一些学界最先进的研究成果也显示，遗传算法无法与强化学习算法相媲美。为了解释这个现象，我们做了进一步研究，发现现代的一些遗传算法增强版本弥补了传统的缺陷，如新颖性搜索（novelty search）算法，它可以在DNN这样规模的神经网络中运作，还可以通过扩大搜索来解决欺骗性问题（局部最优解）。而局部最优解/最大值正是阻碍DQN、A3C、ES、传统GA等实现奖励最大化的主要困难。

左：GA在过河游戏Frostbite上获得10,500分，而DQN、A3C、ES只有不到1000分；右：GA在太空游戏Asteroids上的平均表现超过DQN和ES，但不及A3C

用梯度实现安全突变

在Safe Mutations for Deep and Recurrent Neural Networks through Output Gradients一文中，我们尝试过一种通过将梯度计算结合进神经进化，让遗传算法能在非常深的神经网络内起效的方法。实验表明，这种做法可以使100层DNN中的参数不断进化，远远超过过去研究显示的水平。不同于深度学习中常使用的误差（error）梯度，我们输入的是一个权重梯度，它能将突变校准到少量敏感参数上，从而解决大型神经网络随机进化问题。

如上图所示，左图为安全突变，右图为正常GA突变。突变参数（蓝球）从左下角输入，需要前往左上角“出口”，可以发现，安全突变保留了大部分达成目标能力，并实现了多样性，在这类问题上，它和传统GA相比有着显著的优越性。

如何实现ES和SGD的关联

在论文中，我们援引了otoro的一篇文章：ML领域的生物进化论，进化策略图文详解。主要介绍了OpenAI在今年早些时候提出的一个用于强化学习问题的进化策略（ES）算法。虽然时至今日，学界对他们的成果仍会有一些猜想，但我们在原有基础上做了一些创新。

通过全面研究，我们深入探讨了进化策略和SGD的关系，检查了OpenAI版进化策略在MNIST数据集上的梯度，以及这些梯度与SGD算法梯度的相似性。事实证明，两者的梯度越相近，模型的表现越好，如果能提供足够的计算来保证梯度近似，那OpenAI版进化策略可以在MNIST取得99%的准确度。

而这也暗示了进化策略可能将成为深度强化学习中的一个有力竞争者，因为它能获得大量我们无法计算得到的完美梯度信息。

和梯度下降方法的差异

我们的另一篇论文ES Is More Than Just a Traditional Finite-Difference Approximator对进化策略在神经网络优化上的表现做了一些分析。研究表明，进化策略（有足够大扰动规模的参数，P.S.Uber论文称ES靠扰动现有参数来搜索参数空间）的优化方式和SGD不同，它依靠概率分布给出的是整个群体（种群）的期望奖励（搜索空间中的一片云），而SGD预测的只是一个参数的奖励（搜索空间中的一个点）。这个差异使进化策略能搜索参数空间中的不同区域，并标出哪块是好的，哪块是不好的。

扰动参数群体进行优化的另一个结果是进化策略不是靠SGD梯度下降来获得鲁棒性的，这也揭示了它和贝叶斯方法的一些有趣联系。

上述视频是进化策略是TPRO（信赖域策略优化）算法的训练结果对比，两者基于步态质量相同小人（九宫格最中间的小人）。两种算法都对参数进行了扰动，但可以发现，由于TPRO是根据权重做随机扰动，所以它训练的小人步态更不稳定，而进化策略的小人稳定性和原始小人类似，摔倒次数也相对更少。

左图为进化策略，右图为梯度下降。传统的梯度下降方法不能穿过低fit的狭窄区域，但ES可以

当高fit区域收窄时，ES停滞不前，但梯度下降没有受到干扰。这证明两者的优化方式有差别

增进对ES的探索

深度神经进化研究带来的一个令人兴奋的成果，是我们能把以往为神经进化开发的工具用来加强DNN训练，我们把握住了这个点，并在论文Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents中提出了一种新算法。

我们的算法继承了进化策略的优化能力和可扩展性，同时使用了神经进化的一些工具，它通过激励agent群体做彼此不同的参数空间探索来适应强化学习问题。简而言之，就是它虽然也像传统增强学习算法一样会在单个参数上做探索，但这个独立的探索是一种基于参数群体的探索。我们在雅达利游戏和奔跑小人上做了实验，证明这种算法可以提升进化策略在许多问题上的性能，同时避免局部最优解。