梯度下降算法综述

梯度下降算法是目前神经网络中最流行的优化算法。同时也是目前每个深度学习框架中都包含了各种各样的优化的优化梯度下降算法(例如:lasagne,caffe和keras)。然而始终者通常对这些优化算法的优缺点并不了解,他们只是作为黑盒子提供给用户使用。

本文旨在介绍不同的梯度下降优化算法的不同点以帮助你更好的使用这些算法。我们首先介绍了不同种类的梯度下降算法。然后我们简要的对梯度下降算法面临的挑战进行了总结。接下来,我们介绍了应对梯度下降算法当前面临挑战的常用优化算法。我们夜对梯度下降算法并行和分布式架构进行了简要的介绍。最后,我们还指出了其他一些梯度下降算法的优化策略。

梯度下降算法是最小化参数为$\theta$的目标函数$J(\theta)$的方法。在梯度下降中通常通过更新与梯度相反方向的参数来实现目标函数的优化。学习率$\eta$决定了梯度下降的步伐大小。换句话说,我们沿着平面的梯度下山知道我们到达到一个山谷。如果你对梯度下降算法不太熟悉,你可以在[这里]找到关于梯度下降在优化神经网络中的详细介绍。

梯度下降算法分类

梯度下降算法根据用来计算目标函数梯度数据数量的不同可以分为三类。根据数据规模的大小我们对参数更新的精确度和更新所用时间之间的趋势线。

批梯度下降算法(Batch Gradient Descent)

Vanilla梯度下降和Aka批梯度下降算法通过所有训练样本来计算目标函数的梯度,参数更新公式如下:
$$\theta = \theta - \eta\cdot \Detla_{\theta}J(\theta)$$
由于在批梯度下降算法中每次参数更新需要计算所有数据集的梯度,批梯度下降算法速度会十分缓慢,在数据集太大不能一次读入内存的时候会更加麻烦。批梯度下降算法不能保证在每个新样本来的时候对模型进行更新。
批梯度下降算法的伪代码如下:

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

在预定的迭代时间内,首先利用假定的目标函数的参数$params$和所有的训练样本计算目标函数的梯度向量 $params_grad$。值得注意的是目前所有的深度学习的库都提供了关于某些参数的梯度的改进计算方法。如果你打算自己计算梯度,梯度检验是个不错的注意(具体可以看这里提供了一些梯度检验的技巧)。

计算得到目标函数的梯度后,根据梯度方向和学习率更新更新参数。批处理梯度下降在凸平面上能收敛到全局最优,在非凸平面上能够收敛到局部最优。

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

与批梯度下降算法相反,随机梯度下降算法会对每个样本 $x^{(i)}$和标签$y^{(i)}$更新参数,更新公式如下:

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

批梯度下降算法在每次参数更新时都需要对数据集中所有样本重新计算。随机梯度下降算法通过每次选取一个样本更新参数来避免这种计算冗余。它通常比BSG速度更快,可以用于在线场景。SGD由于频繁的更新会导致参数变化大,从而引起目标函数值会波动的非常厉害,如图1所示。

迷你批梯度下降(Mini-Batch Gradient Descent)

Mini梯度下降算法综合结合了批梯度下降和随机梯度下降的优点,每次利用样本集中的$n$个样本来更新梯度下降的参数,更新公式如下:
$$\theta = \theta - \eta \cdot \Delta_{\theta}J(\theta;x^{(i:i+n)};y^{(i:i+n)}$$
通过选取部分样本来更新参数,Mini批梯度下降算法具有以下优点:
a) 可以减小参数更新过程中的波动,这能够确保优化过程更加稳定的收敛;
b) 能够像当前的深度学习框架中那样利用矩阵优化来计算目标函数梯度那样高校。通常Mini批梯度下降算法的尺寸为50和256,但是根据应用的不同可以变化。Mini梯度下降算法是深度学习中最为常用的优化算法。即使有些网络训练中使用了Mini批梯度下降算法,但可能还是采用了SGD来进行描述。注意:在后文中我们描述SGD时为了简洁,省略了参数$x^{(i:i+n)};y^{(i:i+n)}$.

Mini-Batch的伪代码如下:

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梯度下降算法已经得到了广泛的应用,但是它并不能保证很好的收敛性,并且还有一些重要的挑战需要强调:

  • 选择合适的学习率比较困难。当学习率太小时,目标函数收敛太慢,当学习率太大又容易造成目标函数值在最小值附近波动,甚至跳出收敛区域。
  • 学习率更新计划试图通过诸如蚁群算法或者预先定义的更新策略或者当迭代特定次数后。这些更新计划和阈值的定义应当更加高级,不能根据数据集的特点进行自适应。
  • 另外,对所有的参数使用同样的学习率夜又问题 。如果当我们的数据是稀疏的或者频率不同,我们或许不想所有的参数用同样的学习率更新,而需要对一些稀有的特征采用更大的更新参数。
  • 另外一个重要的挑战是对于优化非凸函数时容易陷入局部最优中。Dauphin指出局部最优的困难不是由于局部最小区域而是由于鞍点的存在,即一维是上升的,而另一维是下降的。鞍点周围通常是错误率相同的稳定状态点,这使得SGD算法很难跳出局部最优,因为它在所有的维度上都接近与等于0。

随机下降优化算法

接下来,我们对深度学习社区中用来应对上文提到的挑战的一些常用算法。我们不会讨论那些不适用于高阶数据优化的算法,比方说二阶方法,如牛顿法

并行与分布式随机梯度下降

Momentum

Nesterov 加速梯度

Adagrad

Adadelta

RMSprop

Adam

优化过程可视化

选用什么优化算法

Hogwild

Downpour SGD

Delay-tolerant Algorithms for SGD

TensorFlow

Elastic Averaging SGD

其他优化策略

Shuffling and Curriculum Learning

Batch normalization

Early stopping

Gradient noise

## 结论

致谢

感谢 Denny BritzCesar Salgado阅读本文的草稿并提出了建议。

打印版本引用

本文夜可以在arXiv上找到,如果你觉得本文对你有帮助,可以考虑引用本文:

Sebastian Ruder (2016). An overview of gradient descent optimisation algorithms. arXiv preprint arXiv:1609.04747.

翻译

本博文被翻译成了以下语言:
日语
中文
2016年6月21更新,本博客也发布在了Hacker News上,这些讨论提出了一些有趣的点和相关工作。

参考文献

Sutton, R. S. (1986). Two problems with backpropagation and other steepest-descent learning procedures for networks. Proc. 8th Annual Conf. Cognitive Science Society.
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
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
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
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
Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method. Retrieved from http://arxiv.org/abs/1212.5701
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.
Bengio, Y., Boulanger-Lewandowski, N., & Pascanu, R. (2012). Advances in Optimizing Recurrent Networks. Retrieved from http://arxiv.org/abs/1212.0901
Sutskever, I. (2013). Training Recurrent neural Networks. PhD Thesis.
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
H. Robinds and S. Monro, “A stochastic approximation method,” Annals of Mathematical Statistics, vol. 22, pp. 400–407, 1951.
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
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., … Zheng, X. (2015). TensorFlow : Large-Scale Machine Learning on Heterogeneous Distributed Systems.
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
Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13.
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
Zaremba, W., & Sutskever, I. (2014). Learning to Execute, 1–25. Retrieved from http://arxiv.org/abs/1410.4615
Ioffe, S., & Szegedy, C. (2015). Batch Normalization : Accelerating Deep Network Training by Reducing Internal Covariate Shift. arXiv Preprint arXiv:1502.03167v3.
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
Sutskever, I., & Martens, J. (2013). On the importance of initialization and momentum in deep learning. http://doi.org/10.1109/ICASSP.2013.6639346
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
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
Niu, F., Recht, B., Christopher, R., & Wright, S. J. (2011). Hogwild! : A Lock-Free Approach to Parallelizing Stochastic Gradient Descent, 1–22.
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.


捐赠

如果我的文章对您有启迪,而您的经济条件许可,您可以扫描下方二维码,向我进行小额奖励,您的认可是我创作的最大动力!

© 2017 风陵渡 All Rights Reserved. 本站访客数人次 本站总访问量
Theme by hiero