写在前面

梯度下降(Gradient descent)算法可以说是迄今最流行的机器学习领域的优化算法。并且，基本上每一个深度学习库都包括了梯度下降算法的实现，比如Lasagne、cafe、keras等。关于梯度优化的三种分类在机器学习中常用的优化方法这篇博客中已经介绍过，按照每次更新参数使用的数据量可以分为Batch gradient descent、Stochastic gradient descent和Mini-batch gradient descent。

src：An overview of gradient descent optimization algorithms

Challenges

然而，朴素Mini-batch gradient descent并没有完全确保完美的收敛性，这也为我们提供了一些需要被强调的挑战之处：

选择一个合适的学习率是非常困难的。一个小的学习率会导致我们的训练过程进行地非常慢，painfully；一个大的学习率则会导致跳过最优解，同时使得损失函数表现地波动起伏。
设置学习率时间表以在训练过程中调整学习率，比如，annealiing算法。通过提前设置训练期间的学习率变化特定规则来优化算法。但是，这种做法需要我们提前设定一些参数并且难以在不同的数据集中通用；
此外，相同的学习率会被应用到所有参数更新。如果我们的数据稀疏并且我们的功能具有非常不同的频率，我们可能不希望将所有数据更新到相同的范围，而是对于很少发生的功能执行更大的更新。
最小化神经网络常见的高度非凸误差函数的另一个关键挑战是避免陷入其众多次优的局部最小值。 Dauphin等人认为困难实际上不是来自局部最小值，而是来自鞍点，即一维向上倾斜而另一维向下倾斜的点。这些鞍点通常被相同误差的平台所包围，这使得SGD难以逃脱，因为梯度在所有维度上都接近于零。

梯度下降优化算法

接下来我们讨论几种在深度学习领域常用的算法，这些算法可以用于解决前面提及的challenges。

Momentum

SGD算法在遇到沟谷（ravines）会比较难以计算，即在一个维度上比另一个维度更陡峭的曲面，这些通常出现在局部最优点的附近。在这些情况下，SGD震荡且缓慢的沿着沟壑的下坡方向朝着局部最优点前进如下图所示。

Momentum是一种在相关方向加速SGD的方法，并且能够减少震荡和摇摆。如下图所示：

Momentum在更新向量中加入了先前一步的状态：

$\large v _ { t } = \gamma v _ { t - 1 } + \eta \nabla _ { \theta } J ( \theta )$

$\large \theta = \theta - v _ { t }$

其中 $\large \gamma$ 为动量系数，通常设置为0.9或者相似的值

本质上来说，当我们使用动量时，类似于我们把球推下山的过程。在球下山的过程中，球累计动量使得其速度越来越快（直到达到其最终速度）。相同的事情也发生在我们的参数更新过程中：对于梯度指向方向相同的维度动量项增大，对于梯度改变的方向的维度动量项减小，最终，我们获得了更快的收敛并减少了震荡。

Nesterov accelerated gradient

然而，一个球盲目地沿着斜坡下山，这不是我们希望看到的。我们希望有一个聪明的球，它知道将要去哪里并且可以在斜坡变成上坡之前减速。

Nesterov accelerated gradient（NAG）就是这样一种给与我们的动量项预知能力的神奇方法。我们知道我们将使用动量项 $\large \gamma v _ { t - 1 }$ 来更新参数 $\large \Theta$ 。因此计算 $\large \theta - \gamma v_{t-1}$ 可以得出我们下一个位置参数的估计，这是一个简单粗暴的方法。

$\large v _ { t } = \gamma v _ { t - 1 } + \eta \nabla _ { \theta } J \left( \theta - \gamma v _ { t - 1 } \right)$

$\large \theta = \theta - v _ { t }$

我们仍然将 $\large \gamma$ 项设置为0.9左右。Momentum算法首先计算当前梯度（下图总的小蓝色向量），然后再更新累计梯度方向上大幅度的跳跃（下图中的大蓝色向量）。与此不同的是，NAG首先在先前的累计梯度方向上进行大幅度的跳跃（下图中的棕色向量），评估这个荼毒并做一下修正（红色向量），这就构成了一次完整的NAG更新（绿色向量）。这种预期更新防止我们进行地太快，也带来了更高的响应速度，

现在我们已经能够依据误差函数的斜率来调整更新，并加快SGD的速度，此外我们也想个根据每个参数的重要性来决定进行更大还是更小

的更新。

Adagrad

Adagrad [Adaptive Subgradient Methods for Online Learning and Stochastic Optimization]的思想是这样的：根据参数来调整学习率，对于不常见的参数给予更大的更新，而对于常见的给予更小的更新。因此，Adagrad 非常适用于稀疏数据。

前面几种算法在对所有参数更新时每个参数使用相同的学习率 $\large \eta$ 。Adagrad在每个时间点t对每个参数 $\large \theta _ { i }$ 使用不同的学习率，我们首先展现每个参数的更新，然后再向量化。简单起见，我们使用 $\large g _ { t , i }$ 来表示目标函数关于 $\large \theta _ { i }$ 在时间点t的梯度：

$\large g _ { t , i } = \nabla _ { \theta } J \left( \theta _ { t , i } \right)$

SGD在每个时间点t对每个参数的更新变为：

$\large \theta _ { t + 1 , i } = \theta _ { t , i } - \eta \cdot g _ { t , i }$

在这个更新规则里面，Adagrad在每个时间点t对每个参数都会基于过去的梯度修改学习率：

$\large \theta _ { t + 1 , i } = \theta _ { t , i } - \frac { \eta } { \sqrt { G _ { t , i i } + \epsilon } } \cdot g _ { t , i }$

其中， $\large G _ { t } \in \mathbb { R } ^ { d \times d }$ 是一个对角矩阵，对角元素 $\large G _ { t } [ i , i ]$ 是参数 $\large \theta _ { i }$ 从开始到时间点t为止的梯度平方和， $\large \epsilon$ 是一个平滑项，用于防止分母为0。有趣的是，去掉开方操作，算法性能将会大幅下降。

由于Gt的对角元素是关于所有参数的过去的梯度平方和，我们可以将上面的公式实现向量化，即使用点乘 $\large \odot$

$\large \theta _ { t + 1 } = \theta _ { t } - \frac { \eta } { \sqrt { G _ { t } + \epsilon } } \odot g _ { t }$

Adagrad 最大的一个优点是我们可以不用手动的调整学习率。大多数实现使用一个默认值 0.01 。

Adagrad 主要的缺点是分母中累积的平方和梯度：由于每一个新添加的项都是正的，导致累积和在训练期间不断增大。这反过来导致学习率不断减小，最终变成无限小，这时算法已经不能再继续学习新东西了。下面的这个算法就解决了这个问题。

Adadelta

Adadelta是 Adagrad的扩展，旨在帮助缓解后者学习率单调下降的问题。 AdaGrad 中对 learning rate 进行 normalize 的参数是使用之前所有时间得到的梯度的累积, AdaDelta 的思想是通过设置窗口 w, 只使用部分时间的梯度累积.

在实际使用中, 其算法并没有存储前 w 个梯度然后计算, 而是类似与 moving average 的方法. 在任意一个时间 t, 当前的 normalize 的参数是 t-1 时刻的参数和当前的梯度做加权求和. 关于指数加权平均的具体细节可以参考：通俗理解指数加权平均

$\large E \left[ g ^ { 2 } \right] _ { t } = \gamma E \left[ g ^ { 2 } \right] _ { t - 1 } + ( 1 - \gamma ) g _ { t } ^ { 2 }$

现在我们就可以使用 $\large E \left[ g ^ { 2 } \right] _ { t }$ 去代替Adagrad中的正则化项：

$\large \nabla \theta _ { t } = - \frac { \eta } { \sqrt { E \left[ g ^ { 2 } \right] _ { t } + \epsilon } } g _ { t }$

最终的更新方法为

$\large \nabla \theta _ { t } = - \frac { R M S [ \nabla \theta ] _ { t - 1 } } { R M S [ g ] _ { t } } g _ { t }$

$\large \theta _ { t + 1 } = \theta _ { t } + \nabla \theta _ { t }$

其中 $\large R M S [ x ] _ { t } = \sqrt { E \left[ x ^ { 2 } \right] _ { t } + \epsilon }$

可以看到，在Adadelta中，我们甚至不需要设置learning rate，因为其自身可以计算学习率

RMSProp

RMSProp是一种还未发布的自适应学习率的方法，有HInton老爷子在Neural Networks for Machine Learning中提出。

RMSprop 和 Adadelta 在同一时间被独立地发明出来，都是为了解决 Adagrad 的学习率递减问题。事实上 RMSprop 与我们上面讨论过的 Adadelta 的第一个更新向量一模一样： $\large \beta _ { 2 }$

$\large E \left[ g ^ { 2 } \right] _ { t } = 0.9 E \left[ g ^ { 2 } \right] _ { t - 1 } + 0.1 g _ { t } ^ { 2 }$

$\large \nabla \theta _ { t } = - \frac { \eta } { \sqrt { E \left[ g ^ { 2 } \right] _ { t } + \epsilon } } g _ { t }$

$\large \theta _ { t + 1 } = \theta _ { t } + \nabla \theta _ { t }$

RMSProp也是将学习率除以平方梯度的指数衰减平均值。Hinton建议将 $\large \gamma$ 设为0.9，默认学习率为0.001。

RMSProp算法和Adagrad算法的区别在于Gt 的计算由累积方式变成了指数衰减移动平均。在迭代过程中，每个参数的学习率并不是呈衰减趋势，既可以变小也可以变大。其在Adagrad的基础上增加了一个衰减系数来控制历史信息的获取多少。

Adam

Adam（Adaptive momentum estimation）是另一种为每个参数计算自适应学习率的方法。除了像Adadelta和RMSProp一样存储历史平方梯度的指数衰减平均值 $\large \boldsymbol { v } _ { t }$ 外，Adam也存储类似Momentum的历史梯度指数衰减平均值 $\large m _ { t }$ ：

$\large m _ { t } = \beta _ { 1 } m _ { t - 1 } + \left( 1 - \beta _ { 1 } \right) g _ { t }$

$\large v _ { t } = \beta _ { 2 } v _ { t - 1 } + \left( 1 - \beta _ { 2 } \right) g _ { t } ^ { 2 }$

由于 $\large m _ { t }$ 和 $\large \boldsymbol { v } _ { t }$ 是用零向量初始化，Adam的作者发现他们趋向于0，特别是最开始的时候和衰减率很小的时候（ $\large \beta _ { 1 }$ 和 $\large \beta _ { 2}$ 接近于1）。

他们通过计算偏差纠正（bias-corrected）的一阶和二阶矩估计值来抵消这些偏差：

$\large \hat { m } _ { t } = \frac { m _ { t } } { 1 - \beta _ { 1 } ^ { t } }$

$\large \hat { v } _ { t } = \frac { v _ { t } } { 1 - \beta _ { 2 } ^ { t } }$

然后他们使用这些公式来更新参数，就像Adadelta和RMSProp一样：

$\large \theta _ { t + 1 } = \theta _ { t } - \frac { \eta } { \sqrt { \widehat { v } _ { t } } + \epsilon } \hat { m } _ { t }$

作者建议将 $\large \beta _ { 1 }$ 的默认值设为0.9， $\large \beta _ { 2}$ 设为0.999， $\epsilon$ 设为 $10 ^ { - 8 }$

AdaMax

在Adam参数更新规则中的 $\large \boldsymbol { v } _ { t }$ 项缩放了梯度，正比于历史梯度和当前梯度的l2范数：

$\large v _ { t } = \beta _ { 2 } v _ { t - 1 } + \left( 1 - \beta _ { 2 } \right) g _ { t } ^ { 2 }$

现在我们可以将此推广到Lp范数。

$\large v _ { t } = \beta _ { 2 } ^ { p } v _ { t - 1 } + \left( 1 - \beta _ { 2 } ^ { p } \right) \left| g _ { t } \right| ^ { p }$

注意，大的p值通常会导致数值上的不稳定，这也是L1和L2范数常用的原因。然而， $\large \ell _ { \infty }$ 一般会表现出稳定的特性。正因如此，作者们提出了AdaMax并获得了良好的表现。为了与Adam进行区分，这里使用了 $\large \boldsymbol { u} _ { t }$ 来代表

$\large \begin{aligned} u _ { t } & = \beta _ { 2 } ^ { \infty } v _ { t - 1 } + \left( 1 - \beta _ { 2 } ^ { \infty } \right) \left| g _ { t } \right| ^ { \infty } \\ & = \max \left( \beta _ { 2 } \cdot v _ { t - 1 } , \left| g _ { t } \right| \right) \end{aligned}$

我们现在可以将此加进Adam的更新规则里，用 $\large \boldsymbol { u} _ { t }$ 代替 $\large \sqrt { \hat { v } _ { t } } + \epsilon$ ，得到AdaMax的更新规则：

$\large \theta _ { t + 1 } = \theta _ { t } - \frac { \eta } { u _ { t } } \hat { m } _ { t }$

注意 $\large \boldsymbol { u} _ { t }$ 依赖于上面的max操作，这不像Adam中的 $\large m _ { t }$ 和 $\large \boldsymbol { v } _ { t }$ 那样容易趋向于0。建议 $\large \eta = 0.002 , \beta _ { 1 } = 0.9 , \text { and } \beta _ { 2 } = 0.999$

Nadam

正如前面说的那样，Adam可以看做是RMSProp和Momentum的组合：RMSProp贡献了历史平方梯度的指数衰减的平均值 $\large \boldsymbol { v } _ { t }$ ，而Momentum则负责历史梯度的指数衰减平均值 $\large m _ { t }$ 。我们也发现了Nesterov accelerated gradient (NAG)要比朴素动量算法更优化。

而Nadam（Nesterov-accelerated Adaptive Moment Estimation）则是结合了Adam和NAG。为了将NAG融进Adam中，我们需要修改其中动量项 $\large m _ { t }$ 。

首先，让我们回顾一下Momentum更新规则：

$\large g _ { t } = \nabla _ { \theta _ { t } } J \left( \theta _ { t } \right)$

$m _ { t } = \gamma m _ { t - 1 } + \eta g _ { t }$

$\large \theta _ { t + 1 } = \theta _ { t } - m _ { t }$

其中，J是目标函数， $\large \gamma$ 是动量衰减项， $\large \eta$ 是步长。将 $\large m _ { t }$ 带入上述第三个式子展开得到：

$\large \theta _ { t + 1 } = \theta _ { t } - \left( \gamma m _ { t - 1 } + \eta g _ { t } \right)$

这再次证明了动量更新涉及两个方向：先前动量向量的方向和当前梯度的方向。

NAG给我们提供了一种在梯度方向更精确的思路：在计算梯度之前通过动量更新参数。因此我们只需更改 $\large g _ { t }$ 来将NAG融进去：

$m _ { t } = \beta _ { 1 } m _ { t - 1 } + \left( 1 - \beta _ { 1 } \right) g _ { t }$

$\hat { m } _ { t } = \frac { m _ { t } } { 1 - \beta _ { 1 } ^ { t } }$

$\theta _ { t + 1 } = \theta _ { t } - \frac { \eta } { \sqrt { \hat { v } _ { t } } + \epsilon } \hat { m } _ { t }$

将 $\hat { m } _ { t }$ 和 $m _ { t }$ 带入：

$\theta _ { t + 1 } = \theta _ { t } - \frac { \eta } { \sqrt { \hat { v } _ { t } } + \epsilon } \left( \frac { \beta _ { 1 } m _ { t - 1 } } { 1 - \beta _ { 1 } ^ { t } } + \frac { \left( 1 - \beta _ { 1 } \right) g _ { t } } { 1 - \beta _ { 1 } ^ { t } } \right)$

注意到 $\frac { m _ { t - 1 } } { 1 - \beta _ { 1 } ^ { t } }$ 是先前动量向量 $m _ { t -1}$ 的偏差修正，因此我们可以用 $m _ { t -1}$ 来代替：

$\theta _ { t + 1 } = \theta _ { t } - \frac { \eta } { \sqrt { \hat { v } _ { t } } + \epsilon } \left( \beta _ { 1 } \hat { m } _ { t - 1 } + \frac { \left( 1 - \beta _ { 1 } \right) g _ { t } } { 1 - \beta _ { 1 } ^ { t } } \right)$

这个式子与我们上面展开得到的动量更新规则非常相似。我们可以加进Nesterov动量，就像我们之前一样简单地用当前动量向量的偏差修正估计 $\hat { m } _ { t }$ 来代替先前动量向量的偏差修正估计 $m _ { t -1}$ 。得到Nadam的更新规则：

$\theta _ { t + 1 } = \theta _ { t } - \frac { \eta } { \sqrt { \hat { v } _ { t } } + \epsilon } \left( \beta _ { 1 } \hat { m } _ { t } + \frac { \left( 1 - \beta _ { 1 } \right) g _ { t } } { 1 - \beta _ { 1 } ^ { t } } \right)$

可视化

不同算法的对比

	优点	缺点
SGD		选择合适的learning rate比较难对于所有的参数使用同样的learning rate 容易收敛到局部最优可能困在saddle point
Momentum	积累动量，加速训练局部极值附近震荡时，由于动量，跳出陷阱梯度方向发生变化时，动量缓解动荡。
Nesterov accelerated gradient	避免前进太快提高灵敏度
Adagrad	控制学习率，每一个分量有各自不同的学习率适合稀疏数据	依赖一个全局学习率学习率设置太大，其影响过于敏感后期调整学习率的分母积累的太大，导致学习率很低，提前结束训练。
RMSProp	解决了后期提前结束的问题	依然依赖全局学习率
Adam	结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点为不同的参数计算不同的自适应学习率也适用于大多非凸优化 - 适用于大数据集和高维空间