Hacks on Computer Vision

[翻译]梯度下降优化算法总结(1)

2016.09.14

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

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

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

梯度下降是最小化以模型参数 $\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 最终吸取了两种方法的优点,每次使用 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 梯度下降,并无法保证好的收敛,但却有一些需要强调的挑战:

  • 选择一个合适的学习率很困难。学习率太小导致收敛巨慢,而学习率过大又会妨碍收敛,导致损失函数在最小值附件波动,甚至发散出去。
  • 学习率的调度11尝试使用如模拟退火等方法在训练时可以根据预先定义的调度方式,或者当两次训练中目标的变化在阈值之下时,可以自动的调整学习率。然而,这些调度方式和阈值需要提前定义,因此无法适用于数据集的特征10
  • 另外,同一个学习率应用到所有的参数更新。如果我们的数据非常稀疏,特征具有完全不同的频率,我们可能不希望以相同的方式对它们进行更新,更希望对少量出现的特征进行较大的更新。
  • 另一个关键的挑战在于最小化神经网络中常见的非凸误差函数时,要避免陷入大量的局部最小值。Dauphin et al. [19]声称实际上难度并非由局部最小值引起,而是由鞍点导致,鞍点就是那些在一个维度是上坡,另一个维度是下坡的点。这些鞍点一般由稳定的相同错误值围绕,这就让 SGD 很难从鞍点逃逸,因为梯度在各个维度都接近于零。

梯度下降优化算法

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

动量

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 梯度加速(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: G. Hinton’s lecture 6c)

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

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

Adagrad

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

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

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

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

我们把 $\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$:

$\Delta \theta_t = - \dfrac{\eta}{\sqrt{E[g^2]_t + \epsilon}} g_{t} $

因为分母仅是梯度误差标准的均方根(root mean squared,RMS),我们可以使用简要的标准替换:

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

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

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

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

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

因为$RMS[\Delta \theta]_{t}$是未知的,我们在前一个时间点使用更新参数的均方根作为近似。在前面的更新规则中,把学习率 $\eta$ 替换为 $RMS[\Delta \theta]_{t-1}$ 就得到了 Adadelta 的更新规则:

$ \Delta \theta_t = - \dfrac{RMS[\Delta \theta]_{t-1}}{RMS[g]_{t}} g_{t}$

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

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

RMSprop

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

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

$E[g^2]_t = 0.9 E[g^2]_{t-1} + 0.1 g^2_t$

$\theta_{t+1} = \theta_{t} - \dfrac{\eta}{\sqrt{E[g^2]_t + \epsilon}} g_{t}$

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

Adam

自适应矩估计(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 在实践中有较好的效果,比其他的自适应学习算法更好。

References

  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

  3. Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159. Retrieved from http://jmlr.org/papers/v12/duchi11a.html

  4. Dean, J., Corrado, G. S., Monga, R., Chen, K., Devin, M., Le, Q. V, … Ng, A. Y. (2012). Large Scale Distributed Deep Networks. NIPS 2012: Neural Information Processing Systems, 1–11. http://doi.org/10.1109/ICDAR.2011.95

  5. Pennington, J., Socher, R., & Manning, C. D. (2014). Glove: Global Vectors for Word Representation. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, 1532–1543. http://doi.org/10.3115/v1/D14-1162

  6. Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method. Retrieved from http://arxiv.org/abs/1212.5701

  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

  9. Sutskever, I. (2013). Training Recurrent neural Networks. PhD Thesis.

  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

  11. H. Robinds and S. Monro, “A stochastic approximation method,” Annals of Mathematical Statistics, vol. 22, pp. 400–407, 1951.

  12. Mcmahan, H. B., & Streeter, M. (2014). Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning. Advances in Neural Information Processing Systems (Proceedings of NIPS), 1–9. Retrieved from http://papers.nips.cc/paper/5242-delay-tolerant-algorithms-for-asynchronous-distributed-online-learning.pdf

  13. Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., … Zheng, X. (2015). TensorFlow : Large-Scale Machine Learning on Heterogeneous Distributed Systems.

  14. Zhang, S., Choromanska, A., & LeCun, Y. (2015). Deep learning with Elastic Averaging SGD. Neural Information Processing Systems Conference (NIPS 2015), 1–24. Retrieved from http://arxiv.org/abs/1412.6651

  15. Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13.

  16. Bengio, Y., Louradour, J., Collobert, R., & Weston, J. (2009). Curriculum learning. Proceedings of the 26th Annual International Conference on Machine Learning, 41–48. http://doi.org/10.1145/1553374.1553380

  17. Zaremba, W., & Sutskever, I. (2014). Learning to Execute, 1–25. Retrieved from http://arxiv.org/abs/1410.4615

  18. Ioffe, S., & Szegedy, C. (2015). Batch Normalization : Accelerating Deep Network Training by Reducing Internal Covariate Shift. arXiv Preprint arXiv:1502.03167v3.

  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

  20. Sutskever, I., & Martens, J. (2013). On the importance of initialization and momentum in deep learning. http://doi.org/10.1109/ICASSP.2013.6639346

  21. Neelakantan, A., Vilnis, L., Le, Q. V., Sutskever, I., Kaiser, L., Kurach, K., & Martens, J. (2015). Adding Gradient Noise Improves Learning for Very Deep Networks, 1–11. Retrieved from http://arxiv.org/abs/1511.06807

  22. LeCun, Y., Bottou, L., Orr, G. B., & Müller, K. R. (1998). Efficient BackProp. Neural Networks: Tricks of the Trade, 1524, 9–50. http://doi.org/10.1007/3-540-49430-8_2

  23. Niu, F., Recht, B., Christopher, R., & Wright, S. J. (2011). Hogwild ! : A Lock-Free Approach to Parallelizing Stochastic Gradient Descent, 1–22.

  24. Duchi et al. [3] give this matrix as an alternative to the full matrix containing the outer products of all previous gradients, as the computation of the matrix square root is infeasible even for a moderate number of parameters \(d\).

    __EOF__

    本文作者HackCV
    版权声明本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
    本文链接https://hackcv.com/posts/%E7%BF%BB%E8%AF%91%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%931/

发表评论