深度学习常用优化算法

优化与深度学习

优化与深度学习的关系

虽然优化为深度学习提供了最小化损失函数的方法，但本质上，优化与深度学习的目标是有区别的。因为有训练误差和泛化误差的区别，而优化算法的目标函数通常是一个基于训练数据集的损失函数，优化的目标在于降低训练误差。而深度学习的目标在于降低泛化误差。为了降低泛化误差，除了使用优化算法降低训练误差以外，还需要注意应对过拟合。

本文中，我们只关注优化算法在最小化目标函数上的表现，而不关注模型的泛化误差。

优化在深度学习中的挑战

优化问题存在着解析解和数值解。因为深度学习的深度学习中绝大多数目标函数都很复杂。因此，很多优化问题并不存在解析解，而需要使用基于数值方法的优化算法找到近似解，即数值解。本文中讨论的优化算法都是这类基于数值方法的算法。为了求得最小化目标函数的数值解，我们将通过优化算法有限次迭代模型参数来尽可能降低损失函数的值。

优化在深度学习中有很多挑战。例如局部最小值和鞍点。

总结

• 由于优化算法的目标函数通常是一个基于训练数据集的损失函数，优化的目标在于降低训练误差。
• 由于深度学习模型参数通常都是高维的，目标函数的鞍点通常比局部最小值更常见。

梯度下降法

导数的定义为：函数变量在某个点周围的极小区域内变化，而导数就是变量变化导致的函数在该方向上的变化率。

$$\begin{eqnarray} \frac{df(x)}{dx}= lim_{h\to 0}\frac{f(x+h)-f(x)}{h} \end{eqnarray}$$

注意等号左边的分号和等号右边的分号不同，不是代表分数。相反，这个符号表示操作符$\frac{d}{dx}$被应用于函数$f$，并返回一个不同的函数（导数）。对于上述公式，可以认为$h$值非常小，函数可以被一条直线近似，而导数就是这条直线的斜率。换句话说，每个变量的导数指明了整个表达式对于该变量的值的敏感程度。比如，若$x=4,y=-3$，则$f(x,y)=-12$，$x$的导数$\frac{\partial f}{\partial x}=-3$。这就说明如果将变量$x$的值变大一点，整个表达式的值就会变小（原因在于负号），而且变小的量是$x$变大的量$h$的三倍。通过重新排列公式可以看到这一点$f(x+h)=f(x)+h \frac{df(x)}{dx}$。同样，因为$\frac{\partial f}{\partial y}=4$，可以知道如果将$y$，那么函数的输出也将增加（原因在于正号），且增加量是$4h$。

函数关于每个变量的导数指明了整个表达式对于该变量的敏感程度。

我们训练模型就是为了最小化损失函数，也就是一个求最值的过程。根据微积分的知识我们知道，梯度向量从几何意义上讲，就是函数增加最快的地方。比如函数$f\left( x,y \right)$，对 $ x,y$求偏导数就得到其梯度向量$\text{（}\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\text{）}^T$，或者表示为$\boldsymbol{grad\ }f\left( x,y \right)$或$\nabla \ f\left( x,y \right) $，在点$\left( x_0,y_0 \right)$处，沿着其梯度向量方向$\text{（}\frac{\partial f}{\partial x_0},\frac{\partial f}{\partial y_0}\text{）}^T $即为函数$f\left( x,y \right) $增加最快的方向，换句话说，在这个方向上可以更快的找到函数的最大值，相对地，如果沿着梯度的反方向$-\text{（}\frac{\partial f}{\partial x_0},\frac{\partial f}{\partial y_0}\text{）}^T$就更快找到函数最小值。也就是说，沿着梯度的反方向，函数$f\left( x,y \right)$的函数值随 $ x,y$变大增长的最快。

对于神经网络而言，通常要通过调整参数$w,b$来使得损失函数最小，所以关于$w$的迭代优化公式为

$$\begin{eqnarray} w_{i}=w_i-\alpha\frac {\partial f}{\partial w_i} \end{eqnarray}$$

其中$\alpha$是学习率，解释为：$f$是关于$w$的函数，那么$\frac {\partial f}{\partial w_i}$衡量的是随着$w$的增大$f$的增大程度。负梯度方向即为随着$w$的减少$f$的减小程度。所以沿着$w$的负梯度方向可以找到函数$f$的最小值。

但是值得注意的是，用梯度下降法找到的不一定是最小值，可能是极小值也可能是一个鞍点。因为梯度下降是寻找的是一个不动点（fixed point）！只有你的函数是凸函数的时候，极小值才为最小值。

梯度下降法的代数方式描述

先决条件：确认优化模型的假设函数和损失函数。

比如对于线性回归，假设函数表示为$h_\theta(x_1, x_2, …x_n) = \theta_0 + \theta_{1}x_1 + … + \theta_{n}x_{n}$, 其中$\theta_i (i = 0,1,2… n)$为模型参数，$x_i (i = 0,1,2… n)$为每个样本的n个特征值。这个表示可以简化，我们增加一个特征$x_0 = 1$ ，这样$h_\theta(x_0, x_1, …x_n) = \sum\limits_{i=0}^{n}\theta_{i}x_{i}$。

同样是线性回归，对应于上面的假设函数，损失函数为：

$$\begin{eqnarray} J(\theta_0, \theta_1..., \theta_n) = \frac{1}{2m}\sum\limits_{j=0}^{m}(h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)}) - y_j)^2 \end{eqnarray}$$

算法相关参数初始化

主要是初始化$\theta_0, \theta_1…, \theta_n$，算法终止距离$\varepsilon$以及步长$\alpha$。在没有任何先验知识的时候，可以将所有的$\theta$初始化为0， 将步长初始化为1。在调优的时候再优化。

算法过程

1）确定当前位置的损失函数的梯度，对于$\theta_i$,其梯度表达式如下：$\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1…, \theta_n)$
2）用步长乘以损失函数的梯度，得到当前位置下降的距离，即$\alpha\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1…, \theta_n)$。
3）确定是否所有的$\theta_i$，梯度下降的距离都小于$\varepsilon$，如果小于$\varepsilon$则算法终止，当前所有的$\theta_i(i=0,1,…n)$即为最终结果。否则进入步骤4。
4）更新所有的$\theta$，对于$\theta_i$，其更新表达式如下。更新完毕后继续转入步骤1.

$$\begin{eqnarray} \theta_i = \theta_i - \alpha\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1..., \theta_n) \end{eqnarray}$$

下面用线性回归的例子来具体描述梯度下降。假设我们的样本是$(x_1^{(0)}, x_2^{(0)}, …x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, …x_n^{(1)},y_1), … (x_1^{(m)}, x_2^{(m)}, …x_n^{(m)}, y_n)$，损失函数如前面先决条件所述：

$$\begin{eqnarray} J(\theta_0, \theta_1..., \theta_n) = \frac{1}{2m}\sum\limits_{j=0}^{m}(h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)})- y_j)^2 \end{eqnarray}$$

则在算法过程步骤1中对于$\theta_i$的偏导数计算如下：

$$\begin{eqnarray} \frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1..., \theta_n)= \frac{1}{m}\sum\limits_{j=0}^{m}(h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)}) - y_j)x_i^{(j)} \end{eqnarray}$$

由于样本中没有$x_0$上式中令所有的$x_0^{j}$为1.

步骤4中$\theta_i$的更新表达式如下：

$$\begin{eqnarray} \theta_i = \theta_i - \alpha\frac{1}{m}\sum\limits_{j=0}^{m}(h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{j}) - y_j)x_i^{(j)} \end{eqnarray}$$

从这个例子可以看出当前点的梯度方向是由所有的样本决定的，加$\frac{1}{m}$是为了好理解。由于步长也为常数，他们的乘积也为常数，所以这里$\alpha\frac{1}{m}$可以用一个常数表示。

在下面会详细讲到的梯度下降法的变种，他们主要的区别就是对样本的采用方法不同。这里我们采用的是用所有样本。

这一部分主要讲解梯度下降法的矩阵方式表述，相对于代数法，要求有一定的矩阵分析的基础知识，尤其是矩阵求导的知识。

梯度下降法的矩阵方式描述

先决条件

和1.1类似，需要确认优化模型的假设函数和损失函数。对于线性回归，假设函数$h_\theta(x_1, x_2, …x_n) = \theta_0 + \theta_{1}x_1 + … + \theta_{n}x_{n}$的矩阵表达方式为：

$$\begin{eqnarray} h_\mathbf{\theta}(\mathbf{X}) = \mathbf{X\theta} \end{eqnarray}$$

其中， 假设函数$h_\mathbf{\theta}(\mathbf{X})$为$m\times 1$的向量，$\mathbf{\theta}$为$n\times 1$的向量，里面有$n$个代数法的模型参数。$\mathbf{X}$为$m\times n$维的矩阵。$m$代表样本的个数，$n$代表样本的特征数。

这里需要注意的是，假设函数$h_\theta(x_1, x_2, …x_n) = \theta_0 + \theta_{1}x_1 + … + \theta_{n}x_{n}$是针对一个样本而言的，而$h_\mathbf{\theta}(\mathbf{X}) = \mathbf{X\theta}$是针对所有样本而言的，所以这里称为矩阵形式，而非向量形式。

损失函数的表达式为

$$\begin{eqnarray} J(\mathbf\theta) = \frac{1}{2}(\mathbf{X\theta} - {Y})^T(\mathbf{X\theta} - {Y}) \end{eqnarray}$$

其中$\mathbf{Y}$是样本的输出向量，维度为$m\times 1$。

算法相关参数初始化

$\theta$向量可以初始化为默认值，或者调优后的值。算法终止距离$\varepsilon$，步长$\alpha$和1.1.3小节比没有变化。

算法过程

1）确定当前位置的损失函数的梯度，对于$\theta$向量,其梯度表达式如下：$\frac{\partial}{\partial\mathbf\theta}J(\mathbf\theta)$
2）用步长乘以损失函数的梯度，得到当前位置下降的距离，即$\alpha\frac{\partial}{\partial\theta}J(\theta)$对应于前面登山例子中的某一步。
3）确定$\mathbf\theta$向量里面的每个值,梯度下降的距离都小于$\varepsilon$，如果小于$\varepsilon$则算法终止，当前$\mathbf\theta$向量即为最终结果。否则进入步骤4.
4）更新$\theta$向量，其更新表达式如下。更新完毕后继续转入步骤1.

$$\begin{eqnarray} \mathbf\theta= \mathbf\theta - \alpha\frac{\partial}{\partial\theta}J(\mathbf\theta) \end{eqnarray}$$

还是用线性回归的例子来描述具体的算法过程。

损失函数对于$\theta$向量的偏导数计算如下：

$$\begin{eqnarray} \frac{\partial}{\partial\mathbf\theta}J(\mathbf\theta) = \mathbf{X}^T(\mathbf{X\theta} - \mathbf{Y})\end{eqnarray}$$

步骤4中$\theta$向量的更新表达式如下：

$$\begin{eqnarray} \mathbf\theta= \mathbf\theta - \alpha\mathbf{X}^T(\mathbf{X\theta} - \mathbf{Y})\end{eqnarray}$$

对比代数法，可以看到矩阵法要简洁很多。这里面用到了矩阵求导链式法则，和两个矩阵求导的公式。

公式1：$\frac{\partial}{\partial\mathbf{X}}(\mathbf{XX^T}) =2\mathbf{X}$

公式2：$\frac{\partial}{\partial\mathbf\theta}(\mathbf{X\theta}) =\mathbf{X^T}$

梯度下降的算法调优

在使用梯度下降时，需要进行调优。哪些地方需要调优呢？

算法的步长选择

在前面的算法描述中，我提到取步长为1，但是实际上取值取决于数据样本，可以多取一些值，从大到小，分别运行算法，看看迭代效果，如果损失函数在变小，说明取值有效，否则要增大步长。前面说了。步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。所以算法的步长需要多次运行后才能得到一个较为优的值。

算法参数的初始值选择

初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，观察损失函数的最小值，选择损失函数最小化的初值。

归一化

由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化，也就是对于每个特征$x$，求出它的期望$\overline{x}$和标准差$std(x)$，然后转化为：

$$\begin{eqnarray} \frac{x - \overline{x}}{std(x)} \end{eqnarray}$$

这样特征的新期望为0，新方差为1，迭代速度可以大大加快。

梯度下降法的三种形式

批量梯度下降法BGD(Batch Gradient Descent)

批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新，这个方法对应于前面的线性回归的梯度下降算法，也就是批量梯度下降法。

$$\begin{eqnarray} \theta_i = \theta_i - \alpha\sum\limits_{j=0}^{m}(h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)}) - y_j)x_i^{(j)}\end{eqnarray}$$

从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果样本数目m很大，那么可想而知这种方法的迭代速度！所以，这就引入了另外一种方法，随机梯度下降。

优点： 全量梯度下降每次学习都使用整个训练集，因此其优点在于每次更新都会朝着正确的方向进行，最后能够保证收敛于极值点(凸函数收敛于全局极值点，非凸函数可能会收敛于局部极值点)；易于并行实现；

缺点：当样本数目很多时，训练过程会很慢且消耗大量内存；不能进行在线模型参数更新；

从迭代的次数上来看，BGD迭代的次数相对较少。其迭代的收敛曲线示意图可以表示如下：

随机梯度下降法SGD(Stochastic Gradient Descent)

随机梯度下降法，其实和批量梯度下降法原理类似，区别在于求梯度时没有用所有的$m$个样本的数据，而是仅仅选取一个样本$j$来求梯度。对应的更新公式是：

$$\begin{eqnarray} \theta_i = \theta_i - \alpha (h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)}) - y_j)x_i^{(j)}\end{eqnarray}$$

随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将$\theta$迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

优点：训练速度快；

缺点：每次更新可能并不会按照正确的方向进行，因此可以带来优化波动(扰动)；易于并行实现。

当批量梯度下降收敛到参数所在类似盆地区域（即很多局部极小值点）的极小值时，一方面SGD的波动使其能够跳到新的、可能更好的局部极小点。另一方面，最终使收敛到确切的最小值的过程变得复杂，因为SGD将持续震荡。然而，当我们缓慢降低学习速度时，SGD表现出与批量梯度下降相同的收敛特性，几乎可以肯定地分别收敛到非凸和凸优化的局部或全局最小值。

从迭代的次数上来看，SGD迭代的次数较多，在解空间的搜索过程看起来很盲目。其迭代的收敛曲线示意图可以表示如下：

随机梯度下降法，和1.4.1的批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解来回震荡。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

那么，有没有一个中庸的办法能够结合两种方法的优点呢？有！这就是小批量梯度下降法。

小批量梯度下降法MBGD(Mini-batch Gradient Descent)

小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于m个样本，我们采用x个样本来迭代，1<x<m。一般可以取x=10，当然根据样本的数据，可以调整这个x的值。对应的更新公式是：

$$\begin{eqnarray} \theta_i = \theta_i - \alpha \sum\limits_{j=t}^{t+x-1}(h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)}) - y_j)x_i^{(j)}\end{eqnarray}$$

相对于随机梯度下降，Mini-batch梯度下降降低了收敛波动性，即降低了参数更新的方差，使得更新更加稳定。相对于全量梯度下降，其提高了每次学习的速度。并且其不用担心内存瓶颈从而可以利用矩阵运算进行高效计算。一般而言每次更新随机选择$[50,256]$个样本进行学习，但是也要根据具体问题而选择，实践中可以进行多次试验，选择一个更新速度与更次次数都较适合的样本数。

mini-batch梯度下降虽然可以保证收敛性。mini-batch梯度下降常用于神经网络中。

梯度下降法总结

但是，梯度下降法有如下几个缺点：

• 选择合适的learning rate比较困难 - 对所有的参数更新使用同样的learning rate。对于稀疏数据或者不经常出现的特征，有时我们可能想更新快一些；对于常出现的特征更新慢一些，这时候SGD就不太能满足要求了。
• 学习速率调整(又称学习速率调度，Learning rate schedules)11试图在每次更新过程中，改变学习速率，如退火。一般使用某种事先设定的策略或者在每次迭代中衰减一个较小的阈值。无论哪种调整方法，都需要事先进行固定设置，这边便无法自适应每次学习的数据集特点10。
• 对于非凸目标函数，容易陷入那些次优的局部极值点中，如在神经网路中。那么如何避免呢。Dauphin19指出更严重的问题不是局部极值点，而是鞍点(These saddle points are usually surrounded by a plateau of the same error, which makes it notoriously hard for SGD to escape, as the gradient is close to zero in all dimensions.)。

在机器学习中的无约束优化算法，除了梯度下降以外，还有前面提到的最小二乘法，此外还有牛顿法和拟牛顿法。

梯度下降法和最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要。梯度下降法是迭代求解，最小二乘法是计算解析解。如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势。

梯度下降法和牛顿法/拟牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法/拟牛顿法是用二阶的海森矩阵的逆矩阵或伪逆矩阵求解。相对而言，使用牛顿法/拟牛顿法收敛更快。但是每次迭代的时间比梯度下降法长。

Momentum

SGD方法的一个缺点是，其更新方向完全依赖于当前的batch，因而其更新十分不稳定。如果在峡谷地区(某些方向较另一些方向上陡峭得多，常见于局部极值点)1，SGD会在这些地方附近振荡，从而导致收敛速度慢。

例如，在下面这个图中，可以看到，同一位置上，目标函数在竖直方向（x2轴方向）比在水平方向（x1轴方向）的斜率的绝对值更大。因此，给定学习率，梯度下降迭代自变量时会使自变量在竖直方向比在水平向移动幅度更大。那么，我们需要一个较小的学习率从而避免自变量在竖直方向上越过目标函数最优解。然而，这会造成自变量在水平方向上朝最优解移动变慢。

解决这一问题的一个简单的做法便是引入momentum2。

momentum即动量，它模拟的是物体运动时的惯性，即更新的时候在一定程度上保留之前更新的方向，同时利用当前batch的梯度微调最终的更新方向。这样一来，可以在一定程度上增加稳定性，从而学习地更快，并且还有一定摆脱局部最优的能力：

$$\begin{eqnarray} m_t=\mu*m_{t-1}+\eta_t*g_t\end{eqnarray}$$ $$\begin{eqnarray}\theta_{t+1}=\theta_t-m_t\end{eqnarray}$$

其中，$\mu$是动量因子，表示要在多大程度上保留原来的更新方向，这个值在0-1之间，在训练开始时，由于梯度可能会很大，所以初始值一般选为0.5；当梯度不那么大时，改为0.9。$\eta_t$是第$t$步的学习率，即当前batch的梯度多大程度上影响最终更新方向，跟普通的SGD含义相同。$g_t$同样是当前的梯度。$\mu$ 与 $\eta_t$ 之和不一定为1。

没有动量作用如下图所示：

加上动量作用如下图所示：

从这两个图中可以看出，加上动量之后，动量法在竖直方向上的移动更加平滑，且在水平方向上更快逼近最优解。

在这些图中，箭头表示当前参数更新的方向，而长度代表学习率，而每一个拐点都表示更新后的参数位置，圈表示等高线。下面的所有的类似的图含义相同。

加上动量项就像从山顶滚下一个球，求往下滚的时候累积了前面的动量(动量不断增加)，因此速度变得越来越快，直到到达终点。同理，在更新模型参数时，对于那些当前的梯度方向与上一次梯度方向相同的参数，那么进行加强，即这些方向上更快了；对于那些当前的梯度方向与上一次梯度方向不同的参数，那么进行削减，即这些方向上减慢了。因此可以获得更快的收敛速度与减少振荡。

理解这段话的关键在于理解，式子$({17})$等号右边的两项均为向量，可以简单的看做为二维向量，然后就可以使用图解法理解上面这段话的含义了。

特点：

• 下降初期时，使用上一次参数更新，下降方向一致，乘上较大的$\mu$能够进行很好的加速
• 下降中后期时，在局部最小值来回震荡的时候，gradient->0，$\mu$使得更新幅度增大，跳出陷阱
• 在梯度改变方向的时候，$\mu$能够减少更新

总而言之，momentum项能够在相关方向加速SGD，抑制振荡，从而加快收敛。

上面这些讨论都是基于直观的思想进行解释的，那么怎么从数学的角度进行解释呢？

指数加权移动平均

为了从数学上理解动量法，让我们先解释一下指数加权移动平均（exponentially weighted moving average）。给定超参数$0 \leq \gamma < 1$，当前时间步$t$的变量$y_t$是上一时间步$t-1$的变量$y_{t-1}$和当前时间步另一变量$x_t$的线性组合：

$$y_t = \gamma y_{t-1} + (1-\gamma) x_t.$$

我们可以对$y_t$展开：

$$\begin{aligned} y_t &= (1-\gamma) x_t + \gamma y_{t-1}\\ &= (1-\gamma)x_t + (1-\gamma) \cdot \gamma x_{t-1} + \gamma^2y_{t-2}\\ &= (1-\gamma)x_t + (1-\gamma) \cdot \gamma x_{t-1} + (1-\gamma) \cdot \gamma^2x_{t-2} + \gamma^3y_{t-3}\\ &\ldots \end{aligned}$$

令$n = 1/(1-\gamma)$，那么 $\left(1-1/n\right)^n = \gamma^{1/(1-\gamma)}$。因为

$$\lim_{n \rightarrow \infty} \left(1-\frac{1}{n}\right)^n = \exp(-1) \approx 0.3679,$$

所以当$\gamma \rightarrow 1$时，$\gamma^{1/(1-\gamma)}=\exp(-1)$，如$0.95^{20} \approx \exp(-1)$。如果把$\exp(-1)$当作一个比较小的数，我们可以在近似中忽略所有含$\gamma^{1/(1-\gamma)}$和比$\gamma^{1/(1-\gamma)}$更高阶的系数的项。例如，当$\gamma=0.95$时，

$$y_t \approx 0.05 \sum_{i=0}^{19} 0.95^i x_{t-i}.$$

因此，在实际中，我们常常将$y_t$看作是对最近$1/(1-\gamma)$个时间步的$x_t$值的加权平均。例如，当$\gamma = 0.95$时，$y_t$可以被看作对最近20个时间步的$x_t$值的加权平均；当$\gamma = 0.9$时，$y_t$可以看作是对最近10个时间步的$x_t$值的加权平均。而且，离当前时间步$t$越近的$x_t$值获得的权重越大（越接近1）。

由指数加权移动平均理解动量法

现在，我们对动量法的速度变量做变形：

$$\begin{eqnarray} m_t=\mu*m_{t-1}+(1-\mu)\left(\frac{\eta_t}{1-\mu}g_t \right)\end{eqnarray}$$

由指数加权移动平均的形式可得，速度变量$\boldsymbol{v}_t$实际上对序列$\{\eta_{t-i}\boldsymbol{g}_{t-i} /(1-\mu):i=0,\ldots,1/(1-\mu)-1\}$做了指数加权移动平均。换句话说，相比于小批量随机梯度下降，动量法在每个时间步的自变量更新量近似于将前者对应的最近$1/(1-\mu)$个时间步的更新量做了指数加权移动平均后再除以$1-\mu$。所以，在动量法中，自变量在各个方向上的移动幅度不仅取决当前梯度，还取决于过去的各个梯度在各个方向上是否一致。在本节之前示例的优化问题中，所有梯度在水平方向上为正（向右），而在竖直方向上时正（向上）时负（向下）。这样，我们就可以使用较大的学习率，从而使自变量向最优解更快移动。

Nesterov accelerated gradient（NAG）

解释一

这是对传统momentum方法的一项改进。nesterov项7在梯度更新时做一个校正，避免前进太快，同时提高灵敏度。 将上一节中的公式展开可得：

$$\begin{eqnarray}\theta_{t+1} =\theta_t-\eta*\mu*m_{t-1}-\eta*g_t\end{eqnarray}$$

可以看出，$m_{t-1}$并没有直接改变当前梯度$g_t$，所以Nesterov的改进就是让之前的动量直接影响当前的动量。即：

$$\begin{eqnarray} g_t=\nabla_{\theta_{t}}{f(\theta_{t}-\eta*\mu*m_{t-1})}\end{eqnarray}$$ $$\begin{eqnarray} m_t=\mu*m_{t-1}+g_t\end{eqnarray}$$ $$\begin{eqnarray} \Delta{\theta_t}=-\eta*m_t\end{eqnarray}$$

综合上式，可以得到最终公式为：

$$\begin{eqnarray}\theta_{t+1} =\theta_t-\eta*(\mu*m_{t}+\nabla_{\theta_{t}}{f(\theta_{t}-\eta*\mu*m_{t-1})})\end{eqnarray}$$

所以，加上nesterov项后，梯度在大的跳跃后，进行计算对当前梯度进行校正。如下图：

momentum算法首先计算一个梯度(短的蓝色向量)，然后在加速更新梯度的方向进行一个大的跳跃(长的蓝色向量)。而nesterov项首先，按照原来的更新方向更新一步（棕色线），然后在该位置计算梯度值（红色线），然后用这个梯度值修正最终的更新方向（绿色线）。上图中描述了两步的更新示意图，其中蓝色线是标准momentum算法更新路径。这样可以阻止过快更新来提高响应性，如在RNNs中8。

解释二

感觉上面这个解释想了很久，除了知道阻止过快更新外，并没有能够通俗的理解为什么这种方法能够work。在CS231n课程上有这样的解释（哇，感觉cs231n上有好多干货啊，怪不得好多人推荐这个课程。之前我都没有系统的学习过机器学习，感觉知识一点不成体系，东一棒槌，西一棒头，感觉有时间还是要系统的看看这些经典课程的）。

看下面这个图，左边是Momentum算法的更新示意图，右边是Nesterov accelerated gradient算法更新示意图。后者的核心思想为，在第$t$步的更新方向的时候（由该方向得到第$t+1$步的位置），已知了求第$t$步时用到的动量方向(可以理解为惯性方向)为$-\eta\mum_{t-1}$，那么在求梯度之前，可以根据动量方向对第$t+1$步的位置进行预测，然后求第$t+1$步梯度。这样显然比直接求第$t$步的梯度要更有意义。(可以不严谨的这么理解，我们根据动量方向对第$t+1$步的位置进行大概预测，利用$t+1$步的梯度进行更新，可以加快收敛速度)

Adagrad

上面提到的方法对于所有参数都使用了同一个更新速率。但是同一个更新速率不一定适合所有参数。比如有的参数可能已经到了仅需要微调的阶段，但又有些参数由于对应样本少等原因，还需要较大幅度的调动。

注意这里的不同学习率指的是针对不同参数而言的，而不是针对不同步而言的。

Adagrad就是针对这一问题提出的，自适应地为各个参数分配不同学习率的算法，其实就是对学习率进行了一个约束。即：

$$\begin{eqnarray}n_t=n_{t-1}+g_t \odot g_t\end{eqnarray}$$ $$\begin{eqnarray}\theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{n_t+\epsilon}} \odot g_t\end{eqnarray}$$

此处，对$g_t$从1到t进行一个递推形成一个约束项regularizer，$-\frac{1}{\sqrt{\sum_{r=1}^t(g_r)^2+\epsilon}}$，$\epsilon$用来保证分母非0。$g_t$同样是当前的梯度。另外如果分母不开根号，算法性能会很糟糕。

这里需要注意的是，因为我们的参数不止一个，所以$\theta$为向量，也就是说开方、除法和乘法都是元素级别的运算，而$\odot$表示点乘。这些按元素运算使得目标函数自变量中每个元素都分别拥有自己的学习率。如果不好理解的话，我们可以拆成标量的形式来叙述 ，也就是说

$$\begin{eqnarray}\theta_{t+1, i}=\theta_{t, i}-\frac{\eta}{\sqrt{n_{t, i, i}+\epsilon}} \cdot g_{t, i}\end{eqnarray}$$

其中，$n_{t} \in \mathfrak{R}^{d \times d}$为对角矩阵，其中第$i$行的对角元素为过去到当前第$i个$参数$θ_i$的梯度的平方和。

其含义是，对于每个参数，随着其更新的总距离增多，其学习速率也随之变慢。

Adagrad也是一种基于梯度的优化算法，它能够对每个参数自适应不同的学习速率，对稀疏特征，得到大的学习更新，对非稀疏特征，得到较小的学习更新，因此该优化算法适合处理稀疏特征数据。Dean等发现Adagrad能够很好的提高SGD的鲁棒性，google便用其来训练大规模神经网络(看片识猫：recognize cats in Youtube videos)。Pennington等在GloVe中便使用Adagrad来训练得到词向量(Word Embeddings)，频繁出现的单词赋予较小的更新，不经常出现的单词则赋予较大的更新。

Adagrad主要优势在于它能够为每个参数自适应不同的学习速率，只需要一般的人工的设定默认学习率为0.01。需要强调的是，小批量随机梯度按元素平方的累加变量$n_t$出现在学习率的分母项中。因此，如果目标函数有关自变量中某个元素的偏导数一直都较大，那么该元素的学习率将下降较快；反之，如果目标函数有关自变量中某个元素的偏导数一直都较小，那么该元素的学习率将下降较慢。然而，由于$n_t$一直在累加按元素平方的梯度，自变量中每个元素的学习率在迭代过程中一直在降低（或不变）。所以，当学习率在迭代早期降得较快且当前解依然不佳时，AdaGrad算法在迭代后期由于学习率过小，可能较难找到一个有用的解。下文中的Adadelta便是用来解决该问题的。

特点：

• 前期$g_t$较小的时候， regularizer较大，能够放大梯度
• 后期$g_t$较大的时候，regularizer较小，能够约束梯度
• 适合处理稀疏梯度

缺点：

• 由公式可以看出，仍依赖于人工设置一个全局学习率
• $\eta$设置过大的话，会使regularizer过于敏感，对梯度的调节太大
• 中后期，分母上梯度平方的累加将会越来越大，使$gradient\to0$，使得训练提前结束

Adadelta

Adadelta是对Adagrad的扩展，最初方案依然是对学习率进行自适应约束，但是进行了计算上的简化。 Adagrad会累加之前所有的梯度平方，学习速率衰减过快，而Adadelta取得是衰减平均值，并且也不直接存储这些项，仅仅是近似计算对应的指数加权移动平均（类似于滑动平均）。而且，$t$时刻的滚动平均值仅仅取决于上一个滚动平均值与当前梯度，即：

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

其中，$\gamma$类似于Momentum系数。如果这个式子不好理解，可以看下面这个式子更好理解，可以看出这里的区别仅仅在于负号的不同。核心运算是相同的。

$$\begin{eqnarray} n_t \leftarrow \gamma n_{t-1} + (1 - \gamma) \boldsymbol{g}_t \odot \boldsymbol{g}_t\end{eqnarray}$$

将公式$({26})$中的$n_t$换成$ E\left[g^{2}\right]_{t}$后得到下式：

$$\begin{eqnarray}\theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{E\left[g^{2}\right]_{t}+\epsilon}} \odot g_t\end{eqnarray}$$

$E\left[g^{2}\right]_t$可以简写为$g$的均方根。原文为：As the denominator is just the root mean squared (RMS) error criterion of the gradient, we can replace it with the criterion short-hand。因为我暂时没能理解这句话的深刻含义，所以暂时放在这。

在数据统计分析中，将所有值平方求和，求其均值，再开平方，就得到均方根值，即root mean squared (RMS)

所以可以改写为

$$\begin{eqnarray} \Delta \theta_{t}=-\frac{\eta}{R M S[g]_{t}}\odot g_{t}\end{eqnarray}$$

但是在这个式子中，还存在着全局学习率$\eta$。为了解决这个问题，他们首先定义了另一个指数衰减的平均值，这一次不是梯度的平方，而是参数更新的平方：

$$\begin{eqnarray} E[\Delta \theta^2]_t = \gamma E[\Delta \theta^2]_{t-1} + (1 - \gamma) \Delta \theta^2_t\end{eqnarray}$$

因此，参数更新的均方根误差为：

$$\begin{eqnarray} RMS[\Delta \theta]_{t} = \sqrt{E[\Delta \theta^2]_t + \epsilon}\end{eqnarray}$$

尽管$RMS[\Delta \theta]_{t}$未知，但是可以使用$RMS[\Delta \theta]_{t-1}$来近似。接着，我们使用$RMS[\Delta \theta]_{t-1}$来代替$\eta$得到更新公式：

$$\begin{align} \begin{split} \Delta \theta_t &= \dfrac{RMS[\Delta \theta]_{t-1}}{RMS[g]_{t}}\odot g_{t} \\ \theta_{t+1} &= \theta_t - \Delta \theta_t \end{split} \end{align}$$

此时，可以看出Adadelta已经不用依赖于全局学习率了。其中，超参数$\gamma$通常取0.9。

特点：

• 训练初中期，加速效果不错，很快
• 训练后期，反复在局部最小值附近抖动

RMSprop

RMSprop可以算作Adadelta的一个特例，区别就在于在后者，使用了$RMS[\Delta \theta]_{t-1}$来近似了学习率$\eta$：

$$\begin{eqnarray} n_t \leftarrow \gamma n_{t-1} + (1 - \gamma) \boldsymbol{g}_t \odot \boldsymbol{g}_t\end{eqnarray}$$

更新公式为：

$$\begin{align} \begin{split} \Delta \theta_t &= \dfrac{\eta}{\sqrt{n_t+\varepsilon}}\odot g_{t} \\ \theta_{t+1} &= \theta_t - \Delta \theta_t \end{split} \end{align}$$

这里之所以将RMSprop和Adadelta的公式没有统一，一方面是为了理解，另一方面我比较认可RMSprop中的公式，对于Adadelta中的公式可能需要更加深刻的统计学知识，我这里先都记下来，用于以后填坑。

特点：

• 其实RMSprop依然依赖于全局学习率
• RMSprop算是Adagrad的一种发展，和Adadelta的变体，效果趋于二者之间
• 适合处理非平稳目标 - 对于RNN效果很好

Adam

Adam(Adaptive Moment Estimation)本质上是带有动量项的RMSprop，它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。公式如下：

$$\begin{eqnarray}m_t=\mu*m_{t-1}+(1-\mu)*g_t\end{eqnarray}$$ $$\begin{eqnarray}n_t=\nu*n_{t-1}+(1-\nu)*g_t^2\end{eqnarray}$$ $$\begin{eqnarray}\hat{m_t}=\frac{m_t}{1-\mu^t}\end{eqnarray}$$ $$\begin{eqnarray}\hat{n_t}=\frac{n_t}{1-\nu^t}\end{eqnarray}$$ $$\begin{eqnarray}\Delta{\theta_t}=-\frac{\hat{m_t}}{\sqrt{\hat{n_t}}+\epsilon}*\eta\end{eqnarray}$$

我们将$m_0$和$n_0$中的元素都初始化为0，在时间$t$我们得到$m_t = (1-\mu) \sum_{i=1}^t \mu^{t-i} g_i$。将过去各时间步小批量随机梯度的权值相加，得到 $(1-\mu) \sum_{i=1}^t \mu^{t-i} = 1 - \mu^t$。需要注意的是，当$t$较小时，过去各时间步小批量随机梯度权值之和会较小。例如，当$\mu = 0.9$时，$m_1 = 0.1g_1$。为了消除这样的影响，对于任意时间步$t$，我们可以将$m_t$再除以$1 - \mu^t$，从而使过去各时间步小批量随机梯度权值之和为1。这也叫作偏差修正。在Adam算法中，我们对变量$m_t$和$n_t$均作偏差修正，即为式子$({39})$和式子$({40})$.

上面式子中，$m_t$，$n_t$分别是对梯度的一阶矩估计和二阶矩估计，可以看作对期望$E|g_t|，E|g_t^2|$的估计；$\hat{m_t}，\hat{n_t}$是对$m_t，n_t$的校正，这样可以近似为对期望的无偏估计。 可以看出，直接对梯度的矩估计对内存没有额外的要求，而且可以根据梯度进行动态调整，而$-\frac{\hat{m_t}}{\sqrt{\hat{n_t}}+\epsilon}$对学习率形成一个动态约束，而且有明确的范围。

特点：

• 结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点
• 对内存需求较小
• 为不同的参数计算不同的自适应学习率
• 也适用于大多非凸优化 - 适用于大数据集和高维空间

Adamax

Adamax是Adam的一种变体，此方法对学习率的上限提供了一个更简单的范围。公式上的变化如下：

$$n_t=max(\nu*n_{t-1},|g_t|)$$ $$\Delta{x}=-\frac{\hat{m_t}}{n_t+\epsilon}*\eta$$

可以看出，Adamax学习率的边界范围更简单

Nadam

Nadam类似于带有Nesterov动量项的Adam。公式如下：

$$\hat{g_t}=\frac{g_t}{1-\Pi_{i=1}^t\mu_i}$$ $$m_t=\mu_t*m_{t-1}+(1-\mu_t)*g_t$$ $$\hat{m_t}=\frac{m_t}{1-\Pi_{i=1}^{t+1}\mu_i}$$ $$n_t=\nu*n_{t-1}+(1-\nu)*g_t^2$$ $$\hat{n_t}=\frac{n_t}{1-\nu^t}\bar{m_t}=(1-\mu_t)*\hat{g_t}+\mu_{t+1}*\hat{m_t}$$ $$\Delta{\theta_t}=-\eta*\frac{\bar{m_t}}{\sqrt{\hat{n_t}}+\epsilon}$$

可以看出，Nadam对学习率有了更强的约束，同时对梯度的更新也有更直接的影响。一般而言，在想使用带动量的RMSprop，或者Adam的地方，大多可以使用Nadam取得更好的效果。

总结

经验之谈

• 对于稀疏数据，尽量使用学习率可自适应的优化方法，不用手动调节，而且最好采用默认值
• SGD通常训练时间更长，但是在好的初始化和学习率调度方案的情况下，结果更可靠
• 如果在意更快的收敛，并且需要训练较深较复杂的网络时，推荐使用学习率自适应的优化方法。
• Adadelta，RMSprop，Adam是比较相近的算法，在相似的情况下表现差不多，而由于偏差校正，Adam在接近优化结束的时候效果更好。总体而言，Adam可能是更好的选择。
• 在想使用带动量的RMSprop，或者Adam的地方，大多可以使用Nadam取得更好的效果

参考

梯度下降优化算法综述
An overview of gradient descent optimization algorithms
the process of learning the parameters and finding good hyperparameters.
d2l-zh
深度学习——优化器算法Optimizer详解（BGD、SGD、MBGD、Momentum、NAG、Adagrad、Adadelta、RMSprop、Adam）
[1] Sutton, R. S. (1986). Two problems with backpropagation and other steepest-descent learning procedures for networks. Proc. 8th Annual Conf. Cognitive Science Society.
[2] Qian, N. (1999). On the momentum term in gradient descent learning algorithms. Neural Networks : The Official Journal of the International Neural Network Society, 12(1), 145–151. http://doi.org/10.1016/S0893-6080(98)00116-6.
[7] Nesterov, Y. (1983). A method for unconstrained convex minimization problem with the rate of convergence o(1/k2). Doklady ANSSSR (translated as Soviet.Math.Docl.), vol. 269, pp. 543– 547.
[8] Bengio, Y., Boulanger-Lewandowski, N., & Pascanu, R. (2012). Advances in Optimizing Recurrent Networks. Retrieved from http://arxiv.org/abs/1212.0901.
[11] H. Robinds and S. Monro, “A stochastic approximation method,” Annals of Mathematical Statistics, vol. 22, pp. 400–407, 1951.
[10] Darken, C., Chang, J., & Moody, J. (1992). Learning rate schedules for faster stochastic gradient search. Neural Networks for Signal Processing II Proceedings of the 1992 IEEE Workshop, (September), 1–11. http://doi.org/10.1109/NNSP.1992.253713.
[19] Dauphin, Y., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014). Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. arXiv, 1–14. Retrieved from http://arxiv.org/abs/1406.2572.