梯度下降

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

简介

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

梯度下降基于目标函数的求解,如果多变量函数F(x)在点a处存在且可导,则F(x)在a点沿着梯度的负方向处下降最快,因此当学习率$\gamma$足够小时:

$b=a-\gamma \bigtrianledown F(a)$

F(a)>=F(b)成立。

根据上式,在求解极小值的过程中,程序可以从函数F的局部极小值$x_0$出发,并且根据下式对x的值进行更新:

$x_{n+1}=x_n-\gamma_b \bigtriangledown F(x_n), n>=0$

x的值可能最终收敛至期望的极值,值得注意的是迭代步长可以在搜索过程中是可变的。

下图说明了整个梯度下降的过程,这里函数F定义在平面上,并且其图形具有碗形状。蓝色曲线是等高线。红色箭头显示了该点上负梯度的方向,且某点的(负)梯度与通过该点的等高线线正交。沿着梯度下降的方向,我们逐渐到达碗的底部,即函数F的极小值。

[图片来源:https://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95#/media/File:Gradient_descent.png]

渐变下降也被称为最速下降,但应注意梯度下降与用于近似积分的最速下降方法是有所不同的。

[描述来源: Vapnik V. N. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag.]

[描述来源:维基百科 URL: https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_theory]

发展历史

描述

根据用来计算目标函数梯度的数据量的区别,梯度下降有三种类型,批量梯度下降(batch gradient descent)根据整个数据集计算目标函数的梯度,随机梯度下降(stochastic gradient descent,SGD)根据每一例数据的结果更新目标函数的梯度,小批量梯度下降(mini batch gradient descent)则将上面两种类型结合起来,根据提前决定的批量的大小更新目标函数的梯度,从而由研究者自己在参数更新的准确性和执行更新所需的时间之间权衡。小批量梯度下降是目前训练神经网络时非常常用的方法,SGD这个术语也经常用来指代这个方法。

1986年Sutton指出当函数平面在一个维度上比另一个维度陡得多——这种情况实际上很常见——SGD会在不同的维度之间摇摆,其更新十分不稳定,因而导致整个搜索的效率十分低下。其中一种改进算法是SGD引入动量 momentum,1999年Qian在发表的论文中推导了学习速率和动量参数趋于一致的界限,并且证明动量项可以增加系统收敛的学习速率范围,还分析了收敛的最优条件。momentum可以使得算法在更新的时候在一定程度上保留之前更新的方向,增加稳定性。

Nesterov扩展的梯度下降算法(Nesterov accelerated gradient,NAG),可以对momentum方法进行进一步改进,通过在每一步更新时计算梯度并根据得到的梯度修正更新方向,NAG算法能够根据梯度适应性的调整步幅。

Duchi等人发明的Adagrad算法不再为所有参数都使用一个学习速率 (learning rate),而是为出现频率高的参数的使用较小的学习率,为出现频率低的参数使用较大的学习率。由于Adagrad算法的学习率是单调递减的,训练后期学习率会非常小,即参数几乎得不到更新。Zeiller于2012年提出的Adadelta算法针对这个问题对Adagrad算法进行了改进。2015年Kingma等人提出的Adam算法(Adaptive Moment Estimation)是计算每个参数的自适应学习率的另一种方法,他们在论文中对Adam算法进行了实证检验,其结果与其他随机优化方法相比更有优势。2016年Dozat提出的Nadam(Nesterov-accelerated Adaptive Moment Estimation)算法试图结合Adam和NAG两种算法的优点。目前比较新的一个研究是由Sashank等人提出的,他们认为前文提到的算法无法收敛到全局最优解的原因是算法中使用的指数移动平均值,并且提出了Adam算法的新变体AMSGrad,解决收敛问题并经常也提高了经验性能。

主要事件

年份事件相关论文/Reference
1983Nesterov提出了NAG算法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.), 269: 543– 547.
19861986年Sutton指出当函数平面在一个维度上比另一个维度陡得多SGD会在不同的维度之间摇摆,其更新十分不稳定,因而导致整个搜索的效率十分低下Sutton, R. S. (1986). Two problems with backpropagation and other steepest-descent learning procedures for networks. Proc. 8th Annual Conf. Cognitive Science Society.
1999Qian在发表的论文中推导了学习速率和动量参数趋于一致的界限,并且证明动量项可以增加系统收敛的学习速率范围,还分析了收敛的最优条件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.
2011Duchi等人发明了Adagrad算法Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159.
2012Zeiller提出Adadelta算法Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method. Retrieved from http://arxiv.org/abs/1212.5701
2015Kingma等人提出Adam算法Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13.
2016Dozat提出Nadam算法Dozat, T. (2016). Incorporating Nesterov Momentum into Adam. ICLR Workshop, (1), 2013–2016.
2018Sashank等人认为上文提到的算法无法收敛到全局最优解的原因是算法中使用的指数移动平均值,并且提出了Adam算法的新变体AMSGradSashank J. R.; Satyen K.; Sanjiv K.(2018). On the Convergence of Adam and Beyond. Proceedings of ICLR 2018.

发展分析

瓶颈

即使目前有关梯度下降的算法已经非常多,目前梯度优化的难点仍然存在不少。如调参是一件非常困难的事,目前没有任何关于学习率的准确的设置方法。另外梯度下降算法消耗内存大、计算速度慢。以及在非凸优化问题中,梯度下降不能保证收敛于全局最优解,当然目前也没有任何优化算法可以做到这一点。

未来发展方向

有关梯度下降的研究还远远没有成熟,能够对当前算法的任一性能进行改进都是非常值得研究的,如更快的收敛速度,更高质量的最优解等等。

By Yuanyuan Li

相关人物
理查德S.萨顿
理查德S.萨顿
Richard S. Sutton 教授博士毕业于马萨诸塞大学安姆斯特分校,现任阿尔伯塔大学计算机科学教授。Sutton 教授被认为是现代计算的强化学习创立者之一。他为该领域做出了许多重大贡献,包括:时间差分学习(temporal difference learning)、策略梯度方法(policy gradient methods)、Dyna 架构
Durk Kingma
Durk Kingma
Timothy Dozat
Timothy Dozat
John C. Duchi
John C. Duchi
尤里·涅斯捷罗夫
尤里·涅斯捷罗夫
马修泽勒
马修泽勒
钱宁
钱宁
简介
相关人物