hulu机器学习问题与解答系列|十七：随机梯度下降算法之经典变种

这是本周第二篇机器学习，也是Hulu面试题系列的第十七篇了~ 之前的所有内容都可以在菜单栏的“机器学习”中找到，愿你温故，知新。

今天的内容是

【随机梯度下降算法之经典变种】

场景描述

提到Deep Learning中的优化方法，人们都会想到Stochastic Gradient Descent (SGD)，但是SGD并不是理想的万金油，反而有时会成为一个坑。当你设计出一个deep neural network时，如果只知道用SGD来训练，不少情况下你得到一个很差的训练结果，于是你放弃继续在这个深度模型上投入精力。但可能的原因是，SGD在优化过程中失效了，导致你丧失了一次新发现的机会。

问题描述

Deep Learning中最常用的优化方法是SGD，但是SGD有时候会失效，无法给出满意的训练结果，这是为什么？为了改进SGD，研究者都做了哪些改动，提出了哪些SGD变种，它们各有哪些特点？

背景知识假设：Gradient Descent Method, 

Stochastic Gradient Descent Method

解答与分析

（1）SGD失效的原因——摸着石头下山

为了回答第一个问题，我们先做一个形象的比喻：想象一下你是一个下山的人，眼睛很好，能看清自己所在位置的坡度，那么沿着坡向下走，最终你会走到山底。现在你被蒙上双眼，只能凭脚底踩石头的感觉判断当前位置的坡度，精确性大大下降。有时候你认为的坡，实际上可能不是坡，走上一段时间发现没有下山，或者曲曲折折走了好多弯路才下山。

我们回到SGD，传统的Gradient Descent（也称Batch Gradient Descent）是带着眼睛下山，而SGD是蒙着眼睛下山。Gradient Descent的每一步，为了获取准确的梯度，把整个训练集载入模型中计算，时间花费和内存开销非常大，无法用于实际中大数据集和大模型的场景。SGD放弃了对梯度准确性的追求，每步仅仅随机采样少量样本来计算梯度，计算速度快，内存开销小，但是由于每步接受的信息量有限，对梯度的估计常常出现偏差，造成目标函数曲线收敛得很不稳定，伴有剧烈波动，甚至有时出现不收敛的情况。图1展示了GD与SGD在优化过程中的参数轨迹，可以看到GD稳定地逼近最低点，而SGD曲曲折折简直是“黄河十八弯”。

图1 GD与SGD的参数优化轨迹

进一步地，有人会说deep learning优化问题本身就很难，有太多局部最优点的陷阱。没错，这个陷阱对SGD和GD都是普遍存在的。但对SGD来说，可怕的不是局部最优点，而是两类地形——山谷和鞍点[1]。山谷顾名思义就是狭长的山间小道，左右两边是峭壁；鞍点的形状像是一个马鞍，一个方向上两头翘，另一个方向上两头垂，而中心区域是一片近乎水平的平地。

为什么SGD最害怕遇上这两类地形呢？在山谷中，准确的梯度方向是沿山道向下，稍有偏离就会撞向山壁，而SGD粗糙的梯度估计使得它在两山壁间来回反弹震荡，不能沿山道方向迅速下降，导致收敛不稳定和收敛速度慢；在鞍点处，SGD走入一片平坦之地（此时离最低点还很远，故也称plateau），想象一下蒙着双眼只凭借脚底感觉坡度，如果坡度很明显那么不精确也能估计出下山的大致方向，但是如果坡度不明显那么很可能走错方向，同样在几近零的梯度区域，对梯度微小变化无法准确察觉的SGD蒙圈了，结果停滞下来。

（2）解决之道——惯性保持和环境感知

SGD本质上是采用迭代方式更新参数，每次迭代在当前位置的基础上，沿着某一方向迈一小步抵达下一位置，然后在下一位置接着这么做。SGD的更新公式是：

其中当前估计的梯度﹣g_t表示步子的方向，学习速率η控制步子的大小。改造SGD仍然基于这个更新形式。

变种1：Momentum

为了解决SGD的山谷震荡和鞍点停滞的问题，我们做一个简单的思维实验。想象一下纸团在山谷和鞍点处的运动轨迹，在山谷中纸团受重力作用沿山道滚下，两边是不规则的山壁，纸团不可避免地撞在山壁，由于质量小受山壁弹力的干扰大，从一侧山壁反弹回来撞向另一侧山壁，结果来回震荡地滚下；当纸团来到鞍点的一片平坦之地时，还是由于质量小，速度很快减为零。纸团的情况和SGD遇到的问题简直如出一辙。直觉上，如果换成一个铁球，当沿山谷滚下时，会不容易受到途中旁力的干扰，轨迹更稳更直；当来到鞍点中心处，在惯性作用下继续前行，从而有机会冲出这片平坦的陷阱。因此，我们有了Momentum的方法[2]，更新公式为

前进步子﹣v_t由两部分组成：(1) 学习速率η和当前估计梯度g_t，(2) 衰减下的前一次步子v_t－1。这里，惯性就体现在对前次步子信息的重利用上。拿中学物理作个类比，当前梯度就好比当前时刻受力产生的加速度，前一次步子好比前一时刻的速度，当前步子好比当前时刻的速度，为了计算当前时刻的速度，我们应当考虑前一时刻速度和当前加速度共同作用的结果，因此v_t直接依赖于v_t－1和g_t，而不是仅有g_t。另外，衰减系数γ扮演了阻力的作用。

中学物理还告诉我们，刻画惯性的物理量是动量，这也是算法名字的由来。沿山谷滚下的铁球，会受到两个方向上的力：沿坡道向下的力和与左右山壁碰撞的弹力。向下的力稳定不变，产生的动量不断累积，速度越来越快；左右的弹力总是在不停切换，动量累积的结果是相互抵消，自然减弱了球的来回震荡。因此，与SGD相比，Momentum的收敛速度快，收敛曲线稳定。

变种2：AdaGrad

惯性的获得是基于历史信息的。那么，除了从过去的步伐中获得一股子向前冲的劲儿，我们还能获得什么？我们期待获得对周围环境的感知，即使蒙上双眼，依靠前几次迈步的感觉，我们也应该能判断出一些信息，比如这个方向总是坑坑洼洼的，那个方向可能很平坦。

具体到SGD中，对环境的感知是指在参数空间中，对不同参数方向上的经验性判断，确定这个参数的自适应学习速率，即更新不同参数的步子大小应是不同的。在一些任务中，如文本处理中训练word embeddings参数，有的words频繁出现，有的则极少出现，数据的稀疏导致相应参数的梯度稀疏，即不频繁出现words的参数大多数情况梯度为零，使得这些参数被更新的频率很低，因此我们希望更新它们的步子大些，而对频繁更新的参数，更新的步子小些。AdaGrad[2]采用过往梯度平方和

的方式来衡量不同参数的梯度稀疏性，和越小表明越稀疏。AdaGrad的更新公式是：

其中θ_t＋1,i表示θ_t＋1的第i个参数。另外，分母中和的形式实现了退火的过程，这是很多优化技术中常见的策略，意味着随着时间推移，学习速率

越来越小，从而保证了优化的最终收敛。

变种3：Adam

Adam方法[4]将惯性保持和环境感知这两个优点集于一身。一方面，Adam记录梯度的first moment，即过往梯度与当前梯度的平均，这体现了惯性保持；另一方面，Adam还记录梯度的second moment，即过往梯度平方与当前梯度平方的平均，这类似AdaGrad，体现了环境感知，为不同参数产生自适应的学习速率。First moment和second moment求平均的思想类似滑动窗口内求平均的做法，关注当前梯度和近一段时间内梯度的平均值，时间久远的梯度对当前平均的贡献呈指数衰减，具体采用指数衰退平均(exponential decay average)技术，计算公式为：

其中β₁, β₂为衰减系数。

如何理解first moment和second moment呢？First moment相当于估计，由于当下梯度g_t是随机采样估计的结果，比起g_t我们更关心它在统计意义上的期望；second moment相当于估计，这点与AdaGrad不同，不是从开始到现在的和而是它的期望。它们的物理意义是：当‖m_t‖大v_t大时，梯度大且稳定，表明遇到一个明显的大坡，前进方向明确；当‖m_t‖趋零v_t大时，梯度不稳定，可能遇到一个峡谷，容易引起反弹震荡；当‖m_t‖大v_t趋零时，这种情况不可能出现；当‖m_t‖趋零v_t趋零时，梯度趋零，可能到达局部最低点，也可能走到一片坡度极缓的平地，此时要避免陷入plateau。另外，Adam还考虑了m_t, v_t在零初始值情况下的偏置矫正。Adam的更新公式为：

扩展阅读

除了上述三种SGD变种，研究者还提出了其他方法：

1. Nesterov Accelerated Gradient：扩展了Momentum方法，顺着惯性方向，计算未来可能位置处的梯度而非当前位置的梯度，这个“提前量”的设计让算法有了对前方环境预判的能力。

2. AdaDelta和RMSProp：这两个方法非常类似，是对AdaGrad的改进。AdaGrad采用所有过往梯度平方和的平方根做分母，分母随时间单调递增，产生的自适应学习速率随时间衰减的速度过于激进，因此AdaDelta和RMSProp采用指数衰退平均的计算方法，用过往梯度的均值代替它们的和。

3. AdaMax：基于Adam的一个变种，对梯度平方的处理由指数衰退平均改为指数衰退求max。

4. Nadam：可看成Nesterov Accelerated Gradient版的Adam。

参考文献：

[1] Yann N. Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional nonconvex optimization. arXiv, pages 1–14, 2014

[2] Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks: the official journal of the International Neural Network Society, 12(1):145–151, 1999

[3] John Duchi, Elad Hazan, and Yoram Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12:2121–2159, 2011

[4] Diederik P. Kingma and Jimmy Lei Ba. Adam: a Method for Stochastic Optimization. InternationalConference on Learning Representations, pages 1–13, 2015.

下一题预告

【SVM – 核函数与松弛变量】

场景描述

当我们在SVM中处理线性不可分的数据时，核函数可以对数据进行映射，从而使得原问题在某种度量下具有更为可分的相似度，而通过引入松弛变量，我们可以放弃一些离群点的精确分类来使分类平面不受太大的影响。将这两种技术与SVM结合起来，正是SVM分类器简洁而强大的原因之一。

问题描述

1. 一个使用高斯核

   

   训练的SVM（Support Vector Machine）中，试证明若给定训练集中不存在两个点在同一位置，则存在一组参数α₁, ... α_m, b以及参数γ使得该SVM的训练误差为0。

2. 若我们使用问题1中得到的参数γ训练一个不加入松弛变量的SVM，是否能保证得到的SVM，仍有训练误差为0的结果，试说明你的观点。

3. 若我们使用SMO（Sequential Minimal Optimization）算法来训练一个带有松弛变量的SVM，并且惩罚因子C为任意事先不知道的常数，我们是否仍能得到训练误差为0的结果，试说明你的观点。