2018/07/22 13:31

带引导的进化策略：摆脱随机搜索中维数爆炸的魔咒

机器学习模型优化的很多案例中都需要对真实梯度未知的函数进行优化。虽然真实梯度未知，但其代理梯度信息却可用。本文提出了一种带引导的进化策略——一种利用代理梯度方向和随机搜索的优化方法，并将该方法应用于合成梯度等问题，最终证明该方法在标准进化策略和直接遵循代理梯度的一阶方法上得到提升。

1 引言

机器学习模型的优化常常涉及最小化代价函数，其中代价关于模型参数的梯度是已知的。当梯度信息可用时，梯度下降和变量等一阶方法因其易于实现、存储效率高（通常需要与参数维度相匹配的存储空间）和收敛有保障 [1] 而广受欢迎。然而，当梯度信息不可用时，我们转向零阶优化方法，包括随机搜索方法，例如最近重新流行起来的进化策略 [2，3，4]。

然而，如果只有部分梯度信息可用，我们又该怎么做呢？也就是说，如果我们能够获得与真实梯度相关的代理梯度，但是这种替代方法会以某种未知的方式产生偏置，我们该怎么做？事实上，各种各样的机器学习问题中都会出现这种情况。例如，Wu 等人在论文 [5] 中说明，在展开优化（通过一种展开优化过程计算梯度）问题中，与在许多展开步骤之后计算（代价高昂的）梯度相比，计算小规模展开步骤的梯度是存在偏置的。在其它应用中，真实梯度并不提供学习信号，我们可以用代理梯度作为一种替代。例如，在神经网络的量化问题中，我们希望用离散（甚至二值化的）权重和/或激活函数来训练神经网络。实现这个目标的一种方法是使用直流评估器 [6]（STE），它通过平滑处理（或直接忽略）神经网络中一些执行量化的节点来生成代理梯度，并且使用该梯度来训练网络。然而，我们并不能保证这个方向是一个好的梯度下降方向。最后，代理梯度也出现在强化学习算法中，例如，actor-critic 方法 [7]，和 Q-learning [8，9，10]。

图 1:（a）带引导的进化策略示意图。我们使用沿着给定子空间（白色箭头）延伸的分布（白色等高线）进行随机搜索，而不是使用真正的梯度方向（蓝色箭头）。（b）对不同算法的二次损失进行比较，向梯度显式地加入一个偏置，用来模拟真实梯度未知的情况。优化过程中显示了损失（左图）以及代理梯度和真实梯度（右图）之间的相关性。实验细节请参阅 4.1 节。

直观地说，有两种极端的方法可以使用代理梯度进行优化。一方面，你可以完全忽略代理梯度信息并执行零阶优化，使用进化策略等方法来估计梯度下降的方向。当参数的维度较大时，这些方法的收敛性较差 [11]。另一方面，你可以直接将代理梯度输入到一阶优化算法中去。然而，代理梯度中存在的偏置会影响到目标问题的优化 [12]。理想情况下，我们希望有一种方法能够融合上述两种方法互补的优势：我们希望将通过进化策略估计出的无偏梯度下降方向与通过代理梯度得到的低方差估计结合起来。在本文中，我们提出了一种被称为「带引导的进化策略」（Guided ES）的方法。

我们的想法是跟踪一个低维子空间，这个子空间是由优化过程中代理梯度的最近历史定义的（受拟牛顿法启发），我们称之为引导子空间。然后，我们优先在这个子空间内执行有限差分随机搜索（就像在进化策略中那样）。通过将搜索样本集中在真实梯度具有非负支持的低维子空间中，我们可以显著减小搜索方向的方差。本文的贡献如下：

将代理梯度信息与随机搜索相结合的新方法。
基于技术的偏置-方差权衡分析。（见 3.3 节）
为相关方法选择最优超参数的方案。（见 3.4 节）
示例问题的应用。（见第 4 节）

文中方法的演示程序，请参阅：https://github.com/brain-research/guided-evolutionary-strategies

图 2：在带引导的进化策略中对偏置-方差权衡进行探索。归一化偏置˜b 的等高线图（a），归一化方差 v˜的等高线图（b），以及前面二者之和的等高线图（c）。它们是关于权衡（α）和规模（β）超参数的函数，其中，是固定的。在这些等高线图中，子空间维数被设定为 k=3，参数维数被设定为 n=100。（c）中蓝色的线表示对于每一个 α 值来说最优的 β，星标表示全局最优点。

图 3：选择最优超参数。（a）阴影区域显示了在平面中最优超参数的不同机制。细节请参阅 3.4 节。（b）随着增加，最优超参数从 α^ ∗ = 1, β^∗ = n /(n+2) 到α^∗ = 0, β^∗ = k /(k+2) 划出了一条曲线。

图 4：展开优化。（a）少量展开优化步骤（t）展开优化过程中的损失情况的偏置。（b）用于训练多层感知器的训练曲线（显示为与最优点的距离），它作为一个用于优化的函数的特征值的函数去预测最佳学习率。细节请参阅 4.2 节。

图 5：作为带引导的进化策略的引导子空间的合成梯度。（a）使用合成梯度最小化目标二次问题时的损失曲线。（b）带引导的进化策略的优化过程中合成更新方向和真实梯度的相关性。

论文：Guided evolutionary strategies: escaping the curse of dimensionality in random search

论文链接：https://arxiv.org/pdf/1806.10230.pdf

摘要：机器学习中很多应用都需要对一个真实梯度未知的函数进行优化，但是其代理梯度信息（可能与真实梯度相关但不一定完全相同的方向）是可知的。当一个近似梯度比完整的梯度更容易计算时（例如，在元学习或展开优化中），或者当一个真实梯度比较棘手且可以被代理梯度替换时（例如，在某些强化学习应用中，或使用合成梯度时），就会出现这种情况。我们提出了带引导的进化策略，这是一种利用代理梯度方向和随机搜索的优化方法。我们为进化策略定义了一个搜索分布，它沿着代理梯度指向的引导子空间延伸。这使我们能够估计出梯度下降方向，并且接着将这个方向传递给一阶优化器。我们定性和定量地刻画了因为调整搜索分布在引导子空间上的伸展程度而产生的权衡，并由此推导出了一个超参数的集合，该集合可以很好地解决各类问题。最终，我们将该方法应用于包括截断展开优化和合成梯度问题在内的示例问题，证明了该方法在标准进化策略和直接遵循代理梯度的一阶方法上的提升。我们为带引导的进化策略（Guided ES）提供了一个演示程序，链接如下：http://github.com/brain-research/guided-evolutionary-strategies。

理论梯度回归森林

相关数据

激活函数技术

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

来源：维基百科 Google ML glossary

权重技术

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

来源：Google AI Glossary

机器学习技术

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

来源：Mitchell, T. (1997). Machine Learning. McGraw Hill.

多层感知机技术

感知机（Perceptron）一般只有一个输入层与一个输出层，导致了学习能力有限而只能解决线性可分问题。多层感知机（Multilayer Perceptron）是一类前馈（人工）神经网络及感知机的延伸，它至少由三层功能神经元（functional neuron）组成（输入层，隐层，输出层），每层神经元与下一层神经元全互连，神经元之间不存在同层连接或跨层连接，其中隐层或隐含层（hidden layer）介于输入层与输出层之间的，主要通过非线性的函数复合对信号进行逐步加工，特征提取以及表示学习。多层感知机的强大学习能力在于，虽然训练数据没有指明每层的功能，但网络的层数、每层的神经元的个数、神经元的激活函数均为可调且由模型选择预先决定，学习算法只需通过模型训练决定网络参数（连接权重与阈值），即可最好地实现对于目标函数的近似，故也被称为函数的泛逼近器（universal function approximator）。

来源：Deep Learning Book

参数技术

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

来源：维基百科

收敛技术

在数学，计算机科学和逻辑学中，收敛指的是不同的变换序列在有限的时间内达到一个结论（变换终止），并且得出的结论是独立于达到它的路径（他们是融合的）。通俗来说，收敛通常是指在训练期间达到的一种状态，即经过一定次数的迭代之后，训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说，如果采用当前数据进行额外的训练将无法改进模型，模型即达到收敛状态。在深度学习中，损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变，暂时形成收敛的假象。

来源：Wikipedia Google ML glossary

学习率技术

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

来源：Liu, T. Y. (2009). Learning to rank for information retrieval. Foundations and Trends® in Information Retrieval, 3(3), 225-331. Wikipedia

超参数技术

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

来源：Wikipedia

元学习技术

元学习是机器学习的一个子领域，是将自动学习算法应用于机器学习实验的元数据上。现在的 AI 系统可以通过大量时间和经验从头学习一项复杂技能。但是，我们如果想使智能体掌握多种技能、适应多种环境，则不应该从头开始在每一个环境中训练每一项技能，而是需要智能体通过对以往经验的再利用来学习如何学习多项新任务，因此我们不应该独立地训练每一个新任务。这种学习如何学习的方法，又叫元学习（meta-learning），是通往可持续学习多项新任务的多面智能体的必经之路。

来源：机器之心

神经网络技术

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

来源：机器之心

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。要使用梯度下降找到函数的局部最小值，可以采用与当前点的函数梯度（或近似梯度）的负值成比例的步骤。如果采取的步骤与梯度的正值成比例，则接近该函数的局部最大值，被称为梯度上升。

来源：Vapnik V. N. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag.Wikipedia

拟牛顿法技术

拟牛顿法是一种以牛顿法为基础设计的，求解非线性方程组或连续的最优化问题函数的零点或极大、极小值的算法。当牛顿法中所要求计算的雅可比矩阵或Hessian矩阵难以甚至无法计算时，拟牛顿法便可派上用场。

来源：维基百科

强化学习技术

强化学习是一种试错方法，其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划（Dynamic Programming）。流行的强化学习方法包括自适应动态规划（ADP）、时间差分（TD）学习、状态-动作-回报-状态-动作（SARSA）算法、Q 学习、深度强化学习（DQN）；其应用包括下棋类游戏、机器人控制和工作调度等。

来源：机器之心

优化器技术

优化器基类提供了计算梯度loss的方法，并可以将梯度应用于变量。优化器里包含了实现了经典的优化算法，如梯度下降和Adagrad。优化器是提供了一个可以使用各种优化算法的接口，可以让用户直接调用一些经典的优化算法，如梯度下降法等等。优化器（optimizers）类的基类。这个类定义了在训练模型的时候添加一个操作的API。用户基本上不会直接使用这个类，但是你会用到他的子类比如GradientDescentOptimizer, AdagradOptimizer, MomentumOptimizer（tensorflow下的优化器包）等等这些算法。

来源：维基百科