神经网络优化算法总结

本篇博文内容主要来自Sebastian Ruder的经典论文An Overview of gradient descent optimization algorithms，论文原文可以在这里找到。

一、简介

神经网络中最常用的优化算法就是梯度下降算法，但是对于大部分研究者，都将梯度下降算法作为黑盒在使用，对不同优化算法的特点并没有一个直观的感受，本文作者通过系统性的介绍，希望读者能够对梯度下降算法及其衍生出的各种优化算法有一个更清晰的感受和认识，从而更好的使用。

梯度下降算法是一种通过调整参数$\theta$来最小化目标函数$J(\theta)$的算法，调整的方向为参数$\theta$的负梯度方向。学习率$\eta$表示每次更新的步长，梯度下降算法可以按照每次使用的数据量划分为批量梯度下降算法，随机梯度下降算法和小批量梯度下降算法。

1.批量梯度下降算法

批量梯度下降算法是使用全部的训练数据计算梯度，更新公式为：

$\theta = \theta - \eta . \Delta_{\theta} J(\theta)$

使用批量梯度下降算法，每次需要在全部的训练数据上计算梯度后更新一次参数，所以参数更新的速度很慢，而且大量的训练数据很可能无法全部载入内存。批量梯度下降算法也不可能完成在线训练。批量梯度下降算法收敛稳定，容易陷入局部最优解。

2.随机梯度下降算法

随机梯度下降算法每次只使用一条训练数据计算梯度，然后更新一次参数。其更新公式可以表示为：

$\theta = \theta - \eta.\Delta_{\theta}J(\theta;x^{(i)};y^{(i)})$

其中$x^{(i)},y^{(i)}$代表一个训练样本。

相比于随机梯度下降算法，批量梯度下降算法使用了过多的数据计算梯度，计算开销过大。随机梯度下降算法使用每个训练样本计算梯度后更新参数，适合在线训练。相比于批量梯度下降算法，随机梯度下降算法不够稳定，损失函数的数值会剧烈波动，但也是这种波动，让随机梯度下降算法可能跳出局部最优点。一般使用随机梯度下降算法，不论对于凸函数还是非凸函数都能取得相对较优的解。

3.小批量梯度下降算法

小批量梯度下降算法是批量梯度下降算法和随机梯度下降算法的折中，一般采用固定样本数作为一个整体，统一计算梯度。小批量梯度下降算法是最优最常用的算法，目前神经网络一般都采用小批量梯度下降算法进行梯度计算。有时SGD表示的也是小批量梯度下降算法。其更新公式可以表示为：

$\theta = \theta - \eta.\Delta_{\theta}J(\theta;x^{(i:i+n)};y^{(i:i+n)})$

小批量梯度下降算法有如下优势：

减小了参数更新的方差，使参数更新更加稳定。
方便利用高度优化的矩阵并行计算，使计算更加有效率。

一般，小批量梯度下降算法每次计算的样本数选择50到256个不等。

二、随机梯度下降算法面临的挑战

使用小批量梯度下降算法，虽然在理论上能取得较好的拟合效果，但是实际中还有很多问题需要去优化。

选择合适的学习率是一件非常困难的事情，如果学习率选择的太小会导致拟合速度过于缓慢，如果学习率选择的过大则会阻碍拟合，引起损失函数在最优值附近剧烈震荡甚至偏离最优值。
也可以通过预先设置的规则或算法，在训练过程中，动态的调整学习率。例如模拟退火算法等，当两次训练间梯度值小于某个阈值时就降低学习率。但是阈值和学习率降低的幅度等都必须预先定义好，没有办法根据实际情况更灵活的处理。
相同的学习率应用在所有的参数上其实也是不合理的，如果数据是离散的，那么不同的参数对应的更新频率可能差异会非常大。更好的做法是，对于频繁更新的参数，使用较小的学习率，而对于更新频率低的参数使用更大的学习率。
还有一个更大的问题是，对于高阶非凸函数的优化，使用梯度下降算法容易陷入到局部最优解中。Dauphin et al指出，其实相对于局部最优解，真正的挑战是鞍点。鞍点是指那些在某一个维度上上升在另一个维度上下降的点。更通用的定义：一个不是局部极值点的驻点称为鞍点。关于鞍点的更详细解释可以查看wikipedia。鞍点通常被高原所包裹，其在所有方向上的梯度接近，这使SGD很难从鞍点逃出。

三、梯度下降优化算法

下面介绍一些SGD的优化算法用于解决上面提到的一些问题。

1. Momentum动量法

普通SGD算法很难越过沟壑，沟壑的定义是那些在一个方向比另一个方向陡峭的多的区域。SGD算法容易在一个深沟中摆动却无法跳出，所以最终陷入局部最优点。

动量法是一种加速SGD优化的方法，其通过在原来的更新向量上乘以一个衰减$\gamma$，再与现在的梯度相加，作为新的更新向量。更新公式如下：

$\begin{aligned} v_{t} &= \gamma v_{t-1} + \eta \Delta_{\theta}J(\theta)\\ \theta &= \theta - v_{t} \end{aligned}$

一般$\gamma$的值设置为0.9或者类似的值。

为了理解动量法，可以把参数更新的过程想象成一个小球从山顶滚到山底的过程。在小球滚动的过程中，其速度不断加快（这个过程与动量发参数更新的幅度符合），保留过去时间的动量，使梯度方向与过去动量方向一致的分量得到增强，不一致的分量得到减弱。这里可以参考上图。如果遇到了一个沟壑，在惯性作用下更也更容易冲过去。最终，动量法得到了比SGD法更快的收敛速度。

2.Nesterov accelerated gradient

接着上文提到的滚小球的例子，如果一个小球仅仅是沿着山坡盲目的滚动，那么得到的结果很可能是不理想的。假如我们有一个更聪明一点的小球，它可以在一定的程度上，判断出它即将滚去方向的情况，比如，当坡度即将重新开始上升的时候，它知道提前减速。NAG就是这样一个算法，它给与动量项一定的预知能力，其更新公式如下：

$\begin{aligned} v_{t} &= \gamma v_{t-1} + \eta \Delta_{\theta}J(\theta-\gamma v_{t-1})\\ \theta &= \theta - v_{t} \end{aligned}$

其中，$\theta-\gamma v_{t-1}$表示下次$\theta$不考虑梯度只考虑动量的近似位置，通过对其求导，可以粗略估算出下次所在位置周围的坡度（对应梯度），这个梯度和前一时刻的动量构成这一次更新的动量。一般$\gamma$的值设置为0.9。

注意图中展示了一次Momentum更新和两次NAG更新

上图3可以解释Momentum和NAG的更新过程。

Momentum首先计算当前位置的梯度进行更新（短蓝线），然后根据以前的动量（累积梯度）进行更新（长蓝线）。

NAG首先根据动量进行更新（棕线），然后计算梯度（红线），在根据计算的梯度对动量进行了修正后进行更新（绿线）。

NAG算法相比于Momentum提高了响应能力，同时防止动量作用下更新过快。在RNN网络结构中，NAG在很多任务上都有明显更好的表现。

3.Adagrad

Adagrad会更根据不同的参数调整学习率，对于高频更新的参数使用较小的学习率而对于低频更新的参数则使用较大的学习率。所以，Adagrad更适合处理稀疏的数据。Dean et al.发现Adagrad大幅度提高了SGD的稳定性，尤其适合大规模神经网络的训练。

之前的算法对于所有的参数，有一个固定的学习率$\eta$，而Adagrad对于每个$\theta_i$在每一步更新t时都有一个学习率。为了后续方便表示，设置$g_{t,i}$为$\theta_i$在步骤t时对应的梯度。参数更新公式如下：

$g_{t,i} = \Delta_{\theta_{t}}J(\theta_{t,i})$

这样，SGD对于每个参数$\theta_i$在步骤t的更新公式可以表示为：

$\theta_{t+1,i} = \theta_{t,i}-\eta.g_{t,i}$

Adagrad修改了学习率，使其与过去的更新梯度相关：

$\theta_{t+1,i} = \theta_{t,i}-\frac{\eta}{\sqrt[]{G_{t,ii}+\varepsilon}}.g_{t,i}$

其中$G_{t} \in \mathbb{R}^{d*d}$是一个对角矩阵(主对角线外元素都为0)，对角线上的元素i,i为从0到t时刻$\theta_{i}$梯度的平方累加值，参数$\varepsilon$的其平滑作用，防止除0越界。有趣的是，平方根非常的重要，如果不使用平方根，效果会变得很差。

参数更新可以写成如下的形式：

$\theta_{t+1} = \theta_{t}-\frac{\eta}{\sqrt[]{G_{t}+\varepsilon}} \odot g_{t}$

Adagrad的一个好处是不再需要手动调整学习率，只需要给定一个初始值$\eta \approx 0.01$即可。但是Adagrad也有明显的不足，因为累加项都是正数，这会导致学习率会不断降低，最终降低到一个趋近于0的值，这时算法会丧失继续学习的能力。

4.Adadelta

Adadelta是对Adagrad的扩展，为了解决Adagrad学习率会快速降低的问题，Adadelta提出用过去$\omega$个梯度平方累加取代过去所有梯度平方累加。在实现上，Adadelta并没有采用维护一个长度为$\omega$的梯度队列这种相对低效的方式，而是采用一种近似计算的方式。

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

一般$\gamma$的取值为0.9。我们把Adagrad中的对角矩阵$G_t$用过去梯度平均衰减累加均值$E[g^2]_t$替代。

$\Delta \theta_t = - \frac{\eta}{\sqrt[]{E[g^2]_t+\varepsilon}}g_t$

因为分母项恰好是梯度的均方误差，可以将公式重写成如下形式：

$\Delta \theta_t = -\frac{\eta}{RMS[g]_t}g_t$

最终，作者认为参数$\eta$也应该有类似的形式，最终的参数更新公式为：

$\begin{aligned} \Delta \theta_t &= - \frac{RMS[\Delta \theta]_{t-1}}{RMS[g]_t}g_t\\ \theta_{t+1} &= \theta_t+\Delta \theta_t \end{aligned}$

5.RMSprop

RMSprop与Adadelta十分类似，只是最终没有替换$\eta$。参数更新公式如下：

$\begin{aligned} \Delta \theta_t &= - \frac{\eta}{RMS[g]_t}g_t\\ \theta_{t+1} &= \theta_t+\Delta \theta_t \end{aligned}$

6.Adam

Adaptive Moment Estimation是一个十分优秀的算法，在各种任务中表现出色。对于不同的参数，它也有不同的学习率。Adam同样维持一个衰减累积项。

$m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t\\ v_t = \beta_2 v_{t-1} + (1-\beta_2)g_t^2$

$m_t$和$v_t$分别是梯度的一阶和二阶累积项。$m_t$和$v_t$在初始化时为全0向量，作者注意到它们偏向于0，尤其是在刚开始训练的时候和当衰减率很小（$\beta_1$和$\beta_2$接近1）的时候，所以引入了修正项。

$\hat{m_t} = \frac{m_t}{1-\beta_1^t}\\ \hat{v_t} = \frac{v_t}{1-\beta_2^t}$

最终的参数更新公式如下：

$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt[]{\hat{v_t}}+\varepsilon}\hat{m_t}$

7.AdaMax

AdaMax是Adam的变形，在Adam中$v_t$是梯度$l_2$归一化，及：

$v_t = \beta_2 v_{t-1} + (1-\beta_2)|g_t|^2$

可以将2阶扩展成p阶，形式如下：

$v_t = \beta_2^p v_{t-1} + (1-\beta_2^p)|g_t|^p$

一般p阶正则项是不稳定的，这也是为什么1阶和2阶正则项使用最为频繁的原因，但是无穷阶正则项的行为却相对稳定。公式可以写为：

$\begin{aligned} v_t &= \beta_{2}^{\infty} v_{t-1} + (1-\beta_2^{\infty})|g_t|^{\infty}\\ &=max(\beta_2.v_{t-1},|g_t|) \end{aligned}$

最终的参数更新公式如下：

$\theta_{t+1} = \theta_t-\frac{\eta}{u_t}\hat{m_t}$

一般的取值$\eta=0.002$，$\beta_1=0.9$，$\beta_2=0.999$。

8.Nadam

Adam可以看做是RMSprop和Momentum的结合，其中RMSprop贡献了$v_t$,Momentum贡献了$m_t$。

Nadam可以看做是Adam和NAG的结合，为了将NAG和Adam结合，需要改写Momentum项$m_t$，首先回忆下Momentum的更新公式：

$\begin{aligned} g_t &= \Delta_{\theta_{t}}J(\theta_{t})\\ m_t &= \gamma m_{t-1} + \eta g_t\\ \theta_{t+1} &= \theta_t - m_t \end{aligned}$

这里J代表了目标函数，$\gamma$代表动量衰减项，$\eta$是学习率。

将上面的第三个公式进行展开，可以的到：

$\theta_{t+1} = \theta_t - (\gamma m_{t-1} + \eta g_t)$

这个公式再次证明，Momentum包含了之前动量项和当前梯度项。NAG通过预先更新动量项，使梯度项的计算更加精确。这时，只要修改梯度$g_t$使其符合NAG即可。

$\begin{aligned} g_t &= \Delta_{\theta_t}J(\theta_t-\gamma m_{t-1})\\ m_t &= \gamma m_{t-1} + \eta g_t\\ \theta_{t+1} &= \theta_t-m_t \end{aligned}$

上面的公式1和公式2中均出现了$m_{t-1}$，分别用于计算梯度$g_t$和计算动量项$m_t$，我们可以直接从前面的动量中更新参数，公式变化如下：

$\begin{aligned} g_t &= \Delta_{\theta_t}J(\theta_t)\\ m_t &= \gamma m_{t-1} + \eta g_t\\ \theta_{t+1} &= \theta_t - (\gamma m_t + \eta g_t) \end{aligned}$

这个最后一个公式与开始时相比，只是将$m_{t-1}$替换成了$m_t$，从考虑当前梯度受到过去动量的影响改变为当前动量对将来梯度的影响。Adam也可以做类似的变换。

首先回顾下Adam的完整公式：

$\begin{aligned} m_t &= \beta_1 m_{t-1} + (1-\beta_1)g_t\\ v_t &= \beta_2 v_{t-1} + (1-\beta_2)g_t^2\\ \hat{m_t} &= \frac{m_t}{1-\beta_1^t}\\ \hat{v_t} &= \frac{v_t}{1-\beta_2^t}\\ \theta_{t+1} &= \theta_t - \frac{\eta}{\sqrt[]{\hat{v_t}}+\varepsilon}\hat{m_t} \end{aligned}$

最后一个公式可以展开为：

$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt[]{\hat{v_t}}+\varepsilon}(\beta_1 \hat{m}_{t-1}+\frac{(1-\beta_1)g_t}{1-\beta_1^t})$

可以仿照上面推到出的变换将$m_{t-1}$替换成了$m_t$，最终的参数更新计算公式为：

$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt[]{\hat{v_t}}+\varepsilon}(\beta_1 \hat{m}_t+\frac{(1-\beta_1)g_t}{1-\beta_1^t})$

四、可视化效果展示

下面的三张图片直观的展示了各个优化算法在实际问题中的表现。

图1是Beale函数的图像
图2展示了各个算法在Beale函数上的优化情况，所有算法都从相同点出发，最终到达最小值点
图3展示了各个算法逃出鞍点的情况。

从图2可以看出，Adagrad、Addelta和RMSprop立刻找到了正确的方向，拟合速度最快。而Momentum和NAG却在惯性作用下偏离了轨道，不过NAG由于提前预判，很快重新找到了方向。SGD方向没有问题，速度却是最慢的，其余算法均到达最优点时其还距离最优点较远。

图3展示了各个算法逃出鞍点的情况。可以看出，SGD、Momentum和NAG的确很难脱离对称轴，虽然后两种算法最终逃出了鞍点。然而Adagrad，RMSprop和Adadelta非常迅速的朝着正确方向前进，其中Adadelta最快。

最终，那些调整学习率的算法（不仅仅调整方向）例如Adagrad、Adadelta、RMSprop和Adam是这些场景中最适合拟合最快的算法。

五、算法选择

最终该如何选择算法呢？作者也给出了一些建议。如果输入的数据时稀疏的，那么最好选择那些能够根据参数调整学习率的算法，这样做还有一个好处是不需要手动设计学习率更新规则了，使用默认的参数一般就能取得较好的结果。

总结下来，RMSprop是Adagrad算法的扩展，它处理了Adagrad算法学习率剧烈降低的问题。Adadelta和RMSprop几乎是一样的，唯一的区别是，Adadelta在算法迭代过程中使用了RMS参数值作为学习率。 Adam在RMSprop的基础上，添加了偏差矫正和动量。RMSprop、Adadelta和Adam是十分类似的算法，适用的场景也十分相似。由于添加的偏差矫正，Adam的表现略优于其他算法，可以说是平均表现最优的算法。

如果只使用普通的SGD算法，主要有足够长的训练时间和合适的学习率，往往也能得到一个最小值。但是，与其他优化算法相比，SGD使用的时间会明显延长，SGD更依赖于好的初始化值，设计良好的学习率调整规则且更容易陷入鞍点。如果你希望在较短的时间内取得好的训练结果，那么往往需要选择一个优化后的SGD算法。