梯度下降优化算法总结-翻译

原文地址：optimizing-gradient-descent。如果熟悉英文的话，强烈推荐阅读原文，毕竟翻译过程中因为个人理解有限，可能会有谬误，还望读者能不吝指出。另外，由于原文太长，分了两部分翻译，本篇主要是梯度下降优化算法的总结，下篇将会是随机梯度的并行和分布式，以及优化策略的总结。

梯度下降是优化中最流行的算法之一，也是目前用于优化神经网络最常用到的方法。同时，每个优秀的深度学习库都包含了优化梯度下降的多种算法的实现（比如，lasagne、caffe 和 keras 的文档）。然而，这些算法一般被封装成优化器，如黑盒一般，因此很难得到它们实际能力和缺点的解释。

本篇博客的目标是为读者提供不同梯度下降优化算法的直观解释，希望读者可以学以致用。我们会先了解下梯度下降的不同变种。然后会对训练过程的问题进行简单总结。接着，我们会介绍最常用的优化算法，展示它们解决这些问题的动机，以及它们对应更新规则变化的原因。我们也就会简单回顾在并行和分布式的情况下，梯度下降优化的算法和架构。最后，我们也会聊聊有助于优化梯度下降的其他策略。

梯度下降是最小化以模型参数 $\theta \in \mathbb{R}^d$ 构建的目标函数 $J(\theta)$ 的一种方法，它通过按目标函数 $\nabla_\theta J(\theta)$ 在参数梯度的相反方向更新参数。学习率 $\eta$ 决定了我们到达（局部）最小所需的步数的大小。换成通俗的话说，我们会沿着目标函数所构建的表面坡度的方向往下走，直到我们到达一个谷底。如果你还不熟悉梯度下降，你可以参考这篇优化神经网络的入门介绍。

一共有三种不同版本的梯度下降，它们的不同之处字啊与我们计算目标函数梯度时使用数据的多少。根据数据量的大小，我们会在参数更新的准确度和更新花费的时间之间进行权衡。

最普通的梯度下降，即批量梯度下降，使用整个训练数据根据参数 $\theta$ 计算目标函数的梯度：

$\theta = \theta - \eta \cdot \nabla_\theta J( \theta)$

因为我们需要计算完整个数据集的梯度才能更新，批量梯度下降非常的耗时，而且面对无法完全放入内容的数据集，处理起来也很棘手。批量梯度更新也无法让我们在线，即在运行时加入新的样本进行模型更新。

以代码的形式，批量梯度下降的形式如下：

for i in range(nb_epochs):
    params_grad = evaluate_gradient(loss_function, data, params)
    params = params - learning_rate * params_grad

对于预先设定好的训练迭代次数，我们首先对于整个数据集根据参数矢量 params 计算损失函数的梯度矢量 weight_grad。注意最新的深度学习库提供了自动微分的方法，可以根据参数高效计算梯度。如果你自己做梯度的微分，那么最好做一下梯度检查。（从这篇文章可以获取一些合理检查梯度的技巧。）

相反，随机梯度下降（stochastic gradient descent, SGD）对训练样本 $x^{(i)}$ 和类别 $y^{(i)}$ 做参数更新：

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

对于大型的数据集，批量梯度下降会出现冗余计算的情况，因为在每次参数更新前，对于相似的样本，它会重新计算梯度。SGD 可以单次更新，所以可以避免这个问题。因此，它常常速度更快，而且可以用于在线学习。

SGD 使用一个比较大的方差频繁更新，会导致目标函数剧烈波动，如图 1 所示。

图 1: SGD 波动

批量梯度下降会收敛在参数所在处的最小值，而SGD 的波动，使一方面得它可以跳过局部最小点，并有可能得到更好的局部最小点。另一方面，因为 SGD 将会一直保持波动，这使得最终收敛到真正的最小点变得复杂。然而，已经证明的情况是，当我们缓慢降低学习率时，SGD 和批量梯度下降有一样的收敛过程，对于非凸和凸优化，都会收敛到其对应的局部或者全局最小值。

SGD 的代码片段仅仅在训练样本时添加了一个循环，根据每个样本进行梯度估计。注意我们会在每次更新训练时会对训练数据进行随机洗牌处理，这会在后面进行解释：

for i in range(nb_epochs):
    np.random.shuffle(data)
    for example in data:
        params_grad = evaluate_gradient(loss_function, example, params)
        params = params - learning_rate * params_grad

Mini-batch 最终吸取了两种方法的优点，每次使用 mini-batch 的训练数据进行更新：

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

这样，它既可以减少参数更新的方差，让收敛更加的稳定；又可以利用常见最新的深度学习库中高度优化的矩阵进行优化，使更加 mini-batch 的梯度计算更加高效。一般 mini-batch 的大小在 50 和 256 之间，但可以根据不同的应用具体选择。mini-batch 梯度下降一般是训练神经网络的算法选择，而在使用 mini-batch 时也会选择使用 SGD。注意：在本文后面的 SGD 修改版中，我们使用参数 $x^{(i:i+n)}; y^{(i:i+n)}$ 作为简化。

在代码中，相比于在样本上迭代，现在我们以 mini-batch 为 50 进行迭代：

for i in range(nb_epochs):
    np.random.shuffle(data)
    for batch in get_batches(data, batch_size=50):
        params_grad = evaluate_gradient(loss_function, batch, params)
        params = params - learning_rate * params_grad

然而， 传统的 mini-batch 梯度下降，并无法保证好的收敛，但却有一些需要强调的挑战：

接下来，我们将会罗列一些深度学习社区广泛用于处理前面提到的挑战的算法。我们将不会讨论那些无法实际处理高维数据集的算法，即二阶方法，如牛顿法。

SGD 在经过低谷时会有问题，即那些在一个维度比另一个维度的表面曲线更加陡峭的区域1，而这种情况在局部最优处非常常见。在这些情况下，SGD 会在低谷的范围内左右震荡，正如图 2 所示，无法在局部最优处得到有效的结果。

SGD

动量2是帮助 SGD 在相关方向上进行加速的方法，可以避免振动，如图 3 所示。它会在当前更新的矢量上加上前一步矢量的更新值 $\gamma$：

$v_t = \gamma v_{t-1} + \eta \nabla_\theta J( \theta)$

$\theta = \theta - v_t$

注意：有些实现公式中的的符号不同。动量 $\gamma$ 常设为 0.9 或者近似的值。

本质上讲，在使用动量时，就像我们往山下推下一个球。球在下落的过程中累积动量，会在路上变得越来越快（直到在空气阻力的作用下达到速度的极值，即 $\gamma < 1$）。对于参数的更新亦是如此：动量在梯度指向同一方向上时会增加，而在梯度变化方向时会减小。这样，我们就可以更快收敛，并可以减小震荡。

然而，就像丢下山的球，盲目地沿着斜坡下降，这还是无法让人满意。我们希望可以有个更加智能的球，可以有它要去哪里的概念，这样再次上坡时就知道要减速了。

Nesterov 梯度加速（Nesterov accelerated gradient，NAG）7 就是可以给动量带来这种感知能力的方法。我们知道我们将会使用动量 $\gamma v_{t-1}$ 来移动参数 $\theta$。这样计算 $ \theta - \gamma v_{t-1} $ 可以得到参数在下个位置的近似值（对于完全更新来说是缺少梯度的），可以大略知道参数将会是什么。现在我们可以高效地不是依据当前梯度，而是依据参数的未来近似位置来计算梯度。

$v_t = \gamma v_{t-1} + \eta \nabla_\theta J( \theta - \gamma v_{t-1} )$

$\theta = \theta - v_t$

同样，我们把动量的值设为 0.9。动量首先计算当前的梯度（图 4 中的小小的蓝色箭头），然后会根据更新后累积的梯度方向前进一大步（大大的蓝色箭头），NAG 首先会在前面累积的梯度方法前进一大步（棕色箭头），然后会检测梯度并做修正（绿色箭头）。这种预更新就可以防止我们更新过快，并可以提高响应能力，它在一些任务上提高了 RNN 的性能8。

Image 4: Nesterov update (Source: <!-- raw HTML omitted -->G. Hinton&rsquo;s lecture 6c<!-- raw HTML omitted -->)

可以参考这篇文章了解 NAG 背后思想的另一种解释，而 Ilya Sutskever 在他的博士论文中给出了更加详细的总结9。

既然我们可以在误差函数的范围内自适应地更新，以此来加速 SGD，我们也可以对各个参数进行自适应更新，根据它们的重要性加大或者减小更新程序。

Adagrad3 是这样的基于梯度优化算法：根据参数自适应地更新学习率，对于不频繁更新的参数做较大更新，而对于频繁变化的参数做较小更新。因此，这个算法非常适合处理稀疏数据。Dean et al. 4发现 Adagrad 可以极大地提高 SGD 的鲁棒性，并在 Google 中用于训练大规模的神经网络，其中就包括了在 Youtube 视频中识别出猫的神经网络。而且，Pennington et al. 5使用 Adagrad 来训练词嵌入 GloVe，因为低频词比高频词需要更大的更新程度。

在前面，我们对每个参数 $\theta_i$ 使用相同的学习率 $\eta$ 来对所有参数 $\theta$ 进行更新。Adagrad 对每个参数 $\theta_i$ 在每个时间点 $t$ 使用不同的学习率，我们首先看下 Adagrad 的单参数更新，然后进行矢量化。为了简洁，我们根据各个时间点 $t$ 的参数 $\theta_i$ 设置 $g_{t, i}$ 为目标函数的梯度：

$g_{t, i} = \nabla_\theta J( \theta_i )$

SGD 对每个参数 $\theta_i$ 在每个时间点 $t$ 的更新就变成了：

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

在 Adagrad 的更新规则中，它会在每个时间点 $t$ 对每个参数 $\theta_i\t$ 基于上次已经计算过的梯度 $\theta_i$ 来修改学习率 $\eta$：

$\theta_{t+1, i} = \theta_{t, i} - \dfrac{\eta}{\sqrt{G_{t, ii} + \epsilon}} \cdot g_{t, i}$

其中，$G_{t} \in \mathbb{R}^{d \times d} $ 是一个对角矩阵，其对角元素 $i, i$ 是关于 $\theta_i$ 和时间步长 $t$ 的梯度的平方和24，而 $\epsilon$ 是一个平滑项，防止被零除（一般取值为 $1e-8$）。有意思的是，如果没有取平方根的操作，算法的效果会变得非常差。

因为 $G_{t}$ 包含了关于所有对角参数 $\theta$ 的过去梯度的平方和，现在我们可以通过对 $G_{t}$ 和 $g_{t}$ 使用矩阵矢量相乘 $\odot$ 进行矢量化实现：

$\theta_{t+1} = \theta_{t} - \dfrac{\eta}{\sqrt{G_{t} + \epsilon}} \odot g_{t}$

Adagrad 的主要优点是不需要在手动调整学习率。大多数的实现使用的默认值是 0.01，就不再管了。

Adagrad 的主要缺点是在分母上累积了梯度的平方：因为每个加上的值都是正的，训练时的累加和会一直增大。这会导致学习率的退化，最终变得非常的小，这时算法就无法再获取更多的知识了。下面的算法就是为了解决这个问题。

Adadelta 6 是 Adagrad 的扩展， 为了减小它激进单调地降低学习率的程度。Adadelta 把累加前面梯度的窗口 $w$ 限制在某个固定的大小上，而不是累加所有过去的梯度平方。

相比与低效地存储前面的梯度平方 $w$，梯度的和可以递归地由过去所有的梯度平方的平均值来替代。那么在时间点 $t$ 平均 $E[g^2]_t$ 仅依赖于（作为分数 $\gamma$ 和动量项相似）前面的平均值和当前的梯度值：

我们把 $\gamma$ 设为动量项相似的值，为 0.9 左右。为了清晰起见，现在我们重写传统 SGD 参数更新矢量 $ \Delta \theta_t $ 的情况：

$\Delta \theta_t = - \eta \cdot g_{t, i}$

$\theta_{t+1} = \theta_t + \Delta \theta_t $

我们前面求导的 Adagrad 的参数更新矢量形式如下：

$ \Delta \theta_t = - \dfrac{\eta}{\sqrt{G_{t} + \epsilon}} \odot g_{t}$

现在我们仅需把对角矩阵 $G_{t}$ 替换为前面梯度平方的平均值 $E[g^2]_t$：

因为分母仅是梯度误差标准的均方根（root mean squared，RMS），我们可以使用简要的标准替换：

$ \Delta \theta_t = - \dfrac{\eta}{RMS[g]_{t}} g_t$

作者提示说在这次更新的单元（也包括在 SGD、冲量，或者 Adagrad）并不匹配，即更新应该和参数有相同的假设单元。为了实现这个目标，他们首先定义了另一个指数延迟平均，这次不使用梯度平方，而是使用参数平方更新：

参数更新的均方根误差如下：

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

有了 Adadelta，我们甚至不需要设置一个默认的学习率，因为它已经在更新规则中被消除了。

RMSprop 是 Geoff Hinton 在Coursera 课堂的讲座上提出的一个未发表的自适应学习率方法。

RMSprop 和 Adadelta 都是同时被独立研究出来，用于解决 Adagrad 学习率消失的问题。事实上，RMSprop 和我们前面分解的 Adadelta 的第一个更新矢量是一样的：

RMSprop 也是通过一个指数延迟梯度平方的平均值来除以学习率。Hinton 建议 $\gamma$ 设置为 0.9，而学习率 $\eta$ 的较好的默认值为is 0.001。

自适应矩估计（Adaptive Moment Estimation，Adam）[15]是另一个计算各个参数的自适应学习率的方法。除了像 Adadelta 和 RMSprop 一样存储过去梯度平方 $v_t$ 的指数移动平均值外，Adam 还保留了一个类似动量的过去梯度 $m_t$ 的指数移动平均值：

$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$ and $v_t$ 以 0 值的矢量进行初始化，Adam 的作者发现它们向零偏差，尤其是在初始时间时，并在移动率非常小的情况下（即， $\beta_1$ 和 $\beta_2$ 接近 1 时）。

它们通过计算偏差修正一阶和二阶力矩估计来减小这些偏差：

$\hat{m}_t = \dfrac{m_t}{1 - \beta^t_1} $

$\hat{v}_t = \dfrac{v_t}{1 - \beta^t_2} $

接下来如通 Adedelat和 RMSprop 一样，它们使用这些值来更新参数，由此得到 Adam 的更新规则：

$\theta_{t+1} = \theta_{t} - \dfrac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t$

作者提出 $\beta_1$ 的默认值为 0.9， $\beta_2$ 的默认值是 0.999，而 $\epsilon$ 的默认值为 $10^{-8}$。他们以经验为依据，认为 Adam 在实践中有较好的效果，比其他的自适应学习算法更好。

由于大规模数据解决方案和低档集群的存在，使用分布式 SGD 进行进一步加速是明显的选择。

SGD 本身属性是串行的：一步一步地，我们逐渐靠近最小值。运行它可以提供较好的收敛结果，但在大数据集上会非常慢。相反，异步运行 SGD 更快，但各个 worker 间的非优交互会导致收敛结果变差。而且，我们也可以在一台机器上，而无需大量的计算集群来并行化 SGD。接下来的部分就是已经提出来的优化并行和分布式 SGD 的算法和架构。

Niu et al. [23] 引入了一个叫做 Hogwild! 的更新策略，可以使 SGD 可以在多 CPU 上并行更新。处理器在无需对参数加锁的情况下就可以访问共享内存。但仅在输入的是稀疏数据时才有效，因为每次更新仅修改所有参数的一小部分。他们展示了在这种情况下，更新策略几乎可以达到一个最优的收敛率，因为处理器不太可能覆盖掉有用的信息。

Downpour SGD 是 Dean et al. 4在 Google 的 DistBelief 框架中使用的一个异步 SGD 的变种（TensorFlow 的前身）。它在训练数据的子集上并行运行多个模型的复制。它们会把自己的更新发送到一个参数服务器上，而完整的参数被分发到许多的机器上。每个机器负责一小部分的模型参数的存储和更新。然而，因为各个复制模型直接并没有通信，即分享权重或者更新，它们的参数会持续遇到发散、妨碍收敛的问题。

McMahan 和 Streeter 12 在 AdaGrad 中加入了延迟容忍算法，进行了并行化扩展，这样不仅使用了过去的梯度，也使用了更新延迟。而这种技术在实践中效果非常好。

TensorFlow 13 是 Google 最近开源的大规模机器学习模型的实现和部署的框架。它是基于 DistBelief 的经验，不仅可以在大量的手机设备上运行，还可以在大规模的分布式系统上运行。对于分布式执行，计算图被每个设备分成一个子集，同时 Send/Receive 节点对之间会进行通信。然而，目前开源版本的 TensorFlow 并不支持分布式功能（详见这里）。13.04.16 更新：TensorFlow 的分布式版本已经发布了。

Zhang et al. [14] 提出了伸缩平均 SGD（Elastic Averaging SGD，EASGD），通过使用一个伸缩力来连接异步 SGD 的各个 worker 的参数，即参数服务器存储了一个中心变量。这可以让局部变量比中心变量波动更大，理论上可以允许探索更多的参数空间。实验表明该方法可以提高探索能力，进而提升找到新的局部最优的能力。

最后，我们介绍下可以进一步提升 SGD 性能，除了上面提到的以外的策略。对于一些其他常见的技巧总结，可以参考22。

一般而言，我们希望避免按照一定的顺序对模型提供训练样本，因为这样可能会使优化算法产生偏差。 因此，在每次的训练 epoch 时，对训练数据进行洗牌是一个好主意。

另一方面，在一些情况下，我们想要逐步解决较难的问题，按照一个合理的顺序提供训练样本可能确实会提高性能，得到一个更好的收敛结果。建立这种合理顺序的方法叫做课程学习16（Curriculum Learning）。

Zaremba 和 Sutskever 17 使用课程学习方法仅可以训练 LSTMs 来估计一些简单的程序，结果显示混合策略比单纯使用一种策略的效果好，因为对样本排序的难度会上升。

为了加快学习，我们一般会使用零均值和方差对参数进行初始化的归一化处理。随着训练的进行，我们会不同程度的更新参数，这样就失去了原有的归一化属性，这会导致训练速度变慢，并随着网络的变深而放大这些变化。

批量归一化（Batch normalization）18在每个 mini-batch 时重新建立起这些归一化属性，而变化也会随着操作进行反向传播。通过对模型架构进行归一化处理，我们就可以使用更高的学习率，而不用太过关注初始化参数。而且，批量归一化有正则化的能力，可以减少（有时甚至可以去除）Dropout 的需求。

根据 Geoff Hinton 所说：“Early stopping（是）华丽的免费午餐”（NIPS 2015 Tutorial slides，第 63 页）。因此你应该在训练时在验证数据集上监控误差，（保持耐心）如果验证误差并没有改善的情况就停止训练。

Neelakantan et al. 21 对各个梯度更新根据高斯分布 $N(0, \sigma^2_t)$ 添加了噪声：

$ g_{t, i} = g_{t, i} + N(0, \sigma^2_t)$

并根据下面的规则对方差进行更新：

$ \sigma^2_t = \dfrac{\eta}{(1 + t)^\gamma} $

结果显示这种添加噪声的方法让网络对较差的初始化更加的鲁棒，并有助于训练较深和复杂的网络。他们猜测添加的噪声让模型有更多的机会可以跳出并找到新的局部最小，而这在更深的模型中是很常见的。

在本篇博客中，我们先回归了梯度下降的三个变种方法，其中 mini-batch 是最流行的。接着我们深入探讨了 SGD 优化常用的算法：Momentum、Nesterov accelerated gradient、Adagrad、Adadelta、RMSprop、Adam，也包括了优化异步 SGD 的不同算法。最后，我们研究了提升 SGD 的其他策略，比如洗牌和课程学习方法、批量归一化和 early stopping。

我希望本文可以给你提供不同优化算法的本质和行为的一些基本认识。有没有我没有提高的其他算法？你在使用 SGD 加速训练时使用了什么技巧？麻烦写在评论中，一起探讨。

感谢Denny Britz 和 Cesar Salgodo 对草稿提供的建议。