今天要和大众分享的是梯度下降算法的综述，咱们将结合2016年的一篇梯度下降算法的综述文案An overview of gradient descent optimization
algorithms进行介绍并这里基本上进行必定的分析和弥补。
背景介绍梯度下降算法最经典的优化算法之一，在最优化行业占据非常重要的地位。它最早被柯西[Cauchy, 1847]首要提出，是最基本的一阶优化算法。假设咱们的目的寻找光滑目的函数的极小值点，其中是模型的参数。梯度下降算法的更新公式为其中，暗示算法在第次迭代中得到的数值解，暗示目的函数关于参数的一阶导数(即梯度)，超参数0" data-formula-type="inline-equation" style="visibility: visible;">叫作为步长(step size)或学习率(learning rate)。所说梯度下降，便是沿着目的函数的负梯度方向(当前点目的函数值下降趋势最大的方向)前进搜索极小值点，走多远由学习率参数决定，见图1。因为在极小值点处梯度为0，因此呢直觉上梯度下降算法最后会停在梯度为0的点，而这个点在必定假设要求下便是极小值点。由此，产生了一系列和梯度下降算法关联的理论问题，如收敛速率(convergence rate)、学习率的选择以及怎样加速算法的收敛等[Curry, 1944, Nemirovski et al., 2009, Rakhlin et al., 2012, Chen et al., 2016, Toulis and Airoldi, 2017, Gitman et al., 2019]。 图1：梯度下降算法示意图
随着近年来深度学习行业的蓬勃兴起，梯度类算法作为了优化神经网络的最重要的办法。各样深度学习的框架(如Caffe, Keras, TensorFlow and PyTorch)中，均支持各样各样的梯度类优化器。梯度类办法在深度学习中如此重要的重点原由是深度神经网络中数以百万、千万级别的待优化参数使得诸如牛顿法和拟牛顿法等高阶优化办法再也不可行，而梯度类办法借助GPU计算资源的支持能够进行有效的运算。然而天下无免费的午餐，当咱们运用一阶优化算法获取其计算可行性上的好处时，付出的代价便是一阶算法较慢的收敛速率。尤其是当目的函数接近病态系统时，梯度类算法的收敛速度会变得更加缓慢。除此之外，因为深度神经网络的损失函数极其繁杂且非凸，梯度类算法优化得到的模型参数的性质未知，依赖于算法的参数选择和初值的选择。因此呢，日前深度学习中的梯度类算法实质上是某种道理上的黑箱算法，其可解释性仍然面临着巨大挑战。
梯度下降算法的变体在第1部分的背景介绍中，咱们将叫作为目的函数，这儿的是一个确定的函数形式，例如. 在实质的设备学习问题中，咱们常常思虑随机优化问题。详细来讲，假设服从某一分布，给定损失,其中是咱们感兴趣的参数。参数的真值满足如下的等式:因为分布是未知的，以上优化问题没法直接被计算。假设咱们获取了一组观测样本(常常假设独立同分布)，那样咱们转而思虑危害极小化问题：此时一般被叫作为损失函数，例如平方损失、交叉熵损失等等。本身是的一个估计量，而咱们的经过算法寻找的其实是。相比较于确定性目的函数，这儿的损失函数引入了一个新的超参数，即样本量。而计算梯度时运用的样本量区别，带来了区别的梯度下降算法。批量梯度下降批量梯度下降(Batch gradient descent, BGD)，某些文献中亦叫作为(Full gradient, FG)，其本质便是运用全样本数据计算梯度。假设参数，全样本为，则BGD算法单次迭代的繁杂度约为。BGD算法的优缺点非常鲜明。其重点优点在于理论性质良好，保准能够找到极小值点。倘若损失函数是凸(强凸)函数，BGD算法能以次线性(线性)的收敛速率找到全局极小值点。缺点则是，当样本量很大时计算效率很低。例如计算机视觉中的ImageNet[Deng et al., 2009] 数据集，训练样本量超过一百万，即使忽略的影响亦是非常巨大的计算成本。另外，BGD算法因为要运用全样本数据，亦不适用于在线学习(Online learning)的情形。随机梯度下降随机梯度下降(Stochastic gradient descent, SGD)与BGD区别，SGD每次更新时仅仅是用一个样本来计算梯度，因此呢SGD算法单次迭代的繁杂度约为，与BGD相比计算效率大大提高，况且SGD适用于在线学习的情形，来一个样本就能够经过SGD更新一次。SGD付出的代价在于它在梯度中引入了额外的方差。尽管在给定全样本的要求下，单个样本计算的梯度是全样本的无偏估计，然则单个样本梯度方向很难和全样本方向一致，因此呢SGD的更新是极其波动的。在常数学习率下，SGD算法即使在损失函数为凸(强凸)函数的要求下亦不可准确找到极小值点，最后的解和极小值点之间的距离受到学习率和梯度方差上界的影响。小批量梯度下降小批量梯度下降(Mini-batch gradient descent, MGD)能够看做是BGD和SGD的一种折中的选取，它亦是日前在深度学习中实质上运用最为广泛的梯度下降算法，许多文案中所指的SGD实质上为MGD算法。每次更新时运用样本量为batch size, 的样本来计算梯度，因此呢MGD算法单次迭代的繁杂度约为，与BGD相比计算效率有所提高，同期引入的梯度噪声方差少于SGD，稳定性更好。当然MGD算法亦有自己的问题，它引入了新的超参数。在实质深度学习任务中，学者发掘的选择不仅影响算法的收敛效率，一样影响最后的外样本精度。通常而言的取值范围在之间。最后，咱们给出三种运用不一样本量的梯度下降算法的对比示意图。 图2：三种梯度下降算法的对比示意图
梯度下降算法的改进算法
如前所说，梯度下降算法做为一阶算法有其固有的局限性，仅仅运用损失函数的一阶信息进行更新是比较“短视”的做法，在病态系统下收敛速度极为缓慢。学者们亦提出了一系列办法来加速梯度下降算法，重点的思路是对梯度下降法的两个重点构成部分进行修改，即更新方向和学习率。咱们接下来重点介绍其中几种非常重要的算法。请重视，以下算法原始版本均是在非随机优化或BGD的要求下讨论的，然则在实质深度学习的应用中常常是运用了MGD的版本，咱们在下文的介绍中并不区分这些细节。
动量梯度下降
动量梯度下降(Gradient Descent with Momentum)法 [Polyak, 1964, Ning, 1999]，亦被叫作为重球(Heavy Ball, HB)办法，是对梯度下降算法的经典改进算法，其更新公式如下： 其中被叫作为动量参数，文献中的举荐值为0.9。它的核心思想是对梯度下降的更新方向进行调节，思虑运用历史梯度信息的指数加权平均做为参数更新的方向。动量梯度下降算法重点带来了两个方面的改进：(1) 加速梯度下降算法。动量一词源于理学学，咱们能够很形象的理解为物体沿山坡下滑的过程中的任意时刻的速度能够分解为当前位置的坡度下降的方向(当前梯度方向)和物体的惯性(历史速度方向)的矢量和。因此呢当咱们思虑历史梯度信息后，梯度下降算法会下降得更快；(2) 控制震荡。梯度下降算法会受到损失函数海森矩阵的要求数(海森矩阵的最大特征根与最小特征根的比值)的影响 [Sutton, 1986]，要求数越大海森矩阵的病态程度越高，此时梯度方向对参数空间的某些方向极度敏锐，咱们能够观察到参数的更新路径震荡剧烈。动量梯度下降法能够累计在正确前进方向的梯度，并且抵消部分敏锐方向的震荡幅度。在理论科研方面，能够证明动量梯度下降法重点是修正了海森矩阵要求数的影响，即将最优收缩系数中的变为了，从而加速收敛。Nesterov动量梯度
Nesterov动量梯度(Nesterov accelerated gradient, NAG)办法 [Nesterov, 1983]，是动量梯度下降法的改进版本，其更新公式如下： 其中动量参数的举荐值仍为0.9。NAG思虑的是一个更加“聪明”的小球，它并不是短视地思虑当前时刻的梯度，而是超前思虑将来时刻的梯度，即根据动量方向前进至处的梯度。当梯度方向出现变化时，动量梯度的纠正机制常常需要累积几步，而NAG能够更早的进行纠正。这种超前的思路使得NAG能够进一步控制震荡，从而加速收敛。当损失函数为凸函数时，能够证明NAG算法的收敛速率由提高为。 图3：动量梯度下降与NAG的对比示意图
AdaGradAdaGrad[Duchi et al., 2011]从学习率的方向思虑加速梯度下降算法，传统的梯度下降算法之因此受制于病态系统的影响，归根结底是由于所有的参数共享了相同的学习率。为保准算法收敛，学习率受制于海森矩阵特征值很强的参数方向而变得很小，引起其他方向更新步长过小优化缓慢。倘若咱们能够给每一个参数赋予区别的学习率，那样就有可能极重地加速梯度下降算法的收敛。同期，AdaGrad能够在迭代过程中自动调节参数的学习率，这被叫作为自适应学习率(Adaptive learning rate)办法。其更新公式如下：这儿暗示对应元素相乘，根号亦是功效在向量的每一个元素上，是为了保准除法的数值稳定性添加的小量。能够看到AdaGrad记录了历史梯度的逐元素累积平方和，并运用该累积和的平方根的逆做为学习率权重。AdaGrad的重点贡献在于能够进行学习率的自适应调节，同期对梯度下降法略有加速。然则它亦有很显著的缺点，更新公式的分母是所有历史信息的求和，因此呢会随着迭代变得越来越大，从而使得学习率衰减过快。AdaGrad算法在实质操作中常常会显现算法找到极小值点之前提前停止的状况。AdaDeltaAdaDelta[Zeiler, 2012]是AdaGrad的延伸和改进版本，它重点是为认识决Adagrad中历史梯度累积平方和单调递增的问题。AdaDelta再也不运用所有历史信息，而是提出运用某个固定窗宽内的历史梯度信息计算累计平方和。因为计算固定窗宽内的梯度累积平方和需要存储个历史梯度平方的信息，AdaDelta转而运用指数加权的方式累积历史信息：其中指数加权参数的举荐值为0.9。从而有迭代公式：作者在文案中指出，之前的梯度类算法(包含原始梯度下降、动量梯度下降和AdaGrad)更新公式中参数的单位并无一致。这儿详细指的是，和各自有自己的单位和尺度，在之前的算法里并无思虑这个问题。作者思虑修正这个问题，因此呢AdaDelta最后的更新公式变为：能够看到，分子运用保准了单位的一致性，同期代替了学习率的功效。因此，AdaDelta算法再也不需要设定学习率。RMSprop
RMSprop[Tieleman and Hinton, 2012]和AdaDelta的思路非常类似，两个算法同年分别被Hinton和Zeiler提出，有趣的是Hinton正是Zeiler的导师。RMSprop最早出此刻Hinton在Coursera的课程中，这一算法成果并未发布。其更新公式与第1周期的AdaDelta一致： 其中指数加权参数的举荐值为0.9，学习率的举荐值为0.001。Adam
自适应矩估计算法(Adaptive Moment Estimation, Adam)[Kingma and Ba, 2015]是将搜索方向和学习率结合在一块思虑的改进算法，其原论文引用量为ICLR官方引用最高的文案。Adam的思路非常清晰：搜索方向上，借鉴动量梯度下降法运用梯度的指数加权；学习率上，借鉴RMSprop运用自适应学习率调节。所说矩估计，则是修正采用指数加权带来的偏差。其更新公式详细如下： 作者举荐参数的取值为，以及小量。在实质应用中，Adam的收敛速度一般优于其他梯度类优化算法，这亦是Adam非常受欢迎的一大原由。相比于之前的算法，Adam需要记录两个历史信息和，这使得Adam和AdaDelta同样，需要多储存一个长度为的向量。AdaMax 与 Nadam咱们在这一小节简要介绍一下Adam的两个重要变体：AdaMax与Nadam。AdaMax是Adam作者在原论文后面自动提出的拓展。其重点思路便是保持搜索方向保持不变，调节自适应学习率的权重，从逐元素2范数推广到逐元素范数，乃至是无穷范数：针对无穷范数的情形，作者意见再也不对进行纠偏。Nadam[Dozat, 2016]则是将Adam中关于搜索方向的部分改为运用Nesterov动量。在引入其更新公式之前，咱们首要给出NAG的等价更新形式。 能够看到，NAG得到等价形式与动量梯度下降法的区别仅仅在最后一步，动量梯度下降法参数的更新量为，而NAG中则是。回顾Adam的更新公式(忽略的部分)：仿照NAG的等价形式，咱们将以上等式中的替换为 就可得到Nadam的更新公式：有些可视化结果
咱们展示两幅照片来对比区别的优化算法的表现，如图4所示。
 图4：梯度下降算法的可视化结果
图4-(a)展示的是六种梯度下降改进算法在Beale函数的函数曲面的优化路径。等高线由红变蓝的过程暗示函数值由大到小，最小值点在图中由五角星标出。所有的算法均从同一点出发，能够看到自适应学习率类的算法(AdaGrad, AdaDelta和RMSprop)的优化路径直接走向了右边的极小值点，然则动量梯度法(绿色曲线)和NAG(紫色曲线)均是先步行到了另一处狭长的区域，再转向极小值点，且NAG的纠正速度快于动量梯度法。
图4-(b)展示的是六种梯度下降改进算法在鞍点周边的优化路径。所说鞍点便是，满足一阶要求等于0然则海森矩阵的特征值有正有负的点。因为梯度下降算法仅仅思虑一阶要求，理论上会受到鞍点的困惑。能够看到，SGD(红色曲线)在鞍点处停止，动量梯度法(绿色曲线)和NAG(紫色曲线)在鞍点处停留一会后逐步脱离鞍点，而三种自适应学习率算法则能够快速摆脱鞍点。
梯度类算法关联科研
并行SGD和分布式SGD
在当今无处不在的大数据时代，数据的分布方式和运用方式都再也不像原来同样单一。与之对应的，当数据仍然保留在本地，学者们起始科研怎样在单机上实现并行SGD[Niu et al., 2011]来进行加速；当数据分散地保留在区别的节点，怎样实现分布式SGD[Jeffrey Dean and Ng., 2012, Mcmahan and Streeter, 2014, Sixin Zhang and LeCun, 2015]；更进一步地，针对数据节点非常庞大而又需要守护用户隐私的时代，联邦学习(Federated Learning)版本的SGD[H. Brendan McMahan and y Arcas, 2016]一样亦是学者们关注的问题。因为篇幅原由，咱们不在这儿进行展开。
梯度类算法的训练策略
除了算法层面的改进，与算法相配套的训练策略或其他技术一样对训练模型有很大的影响。例如： 数据打乱和课程式学习. 有学者指出避免让数据以固定单一的方式进入模型训练能够提高模型的泛化能力，因此呢在深度学习模型的训练中人们在每一次遍历全样本后都会进行数据打乱(Shuffling)。另一方面，有学者指出让数据以某种有道理的次序参与模型训练能够使模型更快收敛且表现不错，这般的办法被叫作为课程式学习(Curriculum Learning)[Yoshua Bengio and Weston, 2009].批量归一化. 批量归一化(Batch normalization)[Ioffe and Szegedy, 2015]是卷积神经网络中经常运用的技术，它能够对每一个小批量的数据在模型的某些节点进行归一化。海量实验显示，这种技术能够加速梯度类算法的收敛、让梯度类算法运用更大的初始学习率以及减少参数初始化的影响。早停. 经过监控验证集的精度指标来决定是不是要提前终止算法训练。梯度噪声. [Neelakantan et al., 2015]提出在梯度上增多独立的高斯噪声，来帮忙梯度类算法增多稳健性。她们猜测，增多的梯度噪声能够帮忙算法跳过局部鞍点和次优的极小值点。梯度类算法仍然面临的挑战
尽管咱们已然介绍了非常多的梯度类算法的改进算法，然则梯度类算法仍然面临着许多挑战。 选取合适的学习率是非常困难的事情。尽管在传统的优化行业和咱们之前说到的自适应学习率算法供给了非常多处理这个问题的办法。在深度模型的训练中，这些已有的办法仍然会遇到问题，因此呢这仍是一个需要小心思虑和许多尝试的问题。尽管梯度下降算法在理论上有许多性质和结论，但实质得到神经网络常常不满足已有结论的前提假设。在咱们优化超高维非凸的损失函数时，怎样保准算法不被鞍点 [Zeiler, 2014]、平坦区域所困惑，依然是非常挑战的问题。针对超高维得到损失函数，梯度类算法表现地像黑箱优化器，日前上无尤其好的办法对这种超高维优化进行可视化分析。参考文献Augustin-Louis Cauchy. Mode grale pour la rlution des systs d’ations simultan. Comptes rendus des sces de l’ Acade des sciences de Paris, pages 536–538, 10 1847.
Xi Chen, Jason D Lee, Xin T Tong, and Yichen Zhang. Statistical inference for model parameters in stochastic
gradient descent. arXiv preprint arXiv:1610.08637, 2016.
Haskell B. Curry. The method of steepest descent for non-linear minimization problems. Quarterly of Applied
Mathematics, pages 258–261, 2 1944.
Jia Deng, Wei Dong, Richard Socher, Li Jia Li, and Fei Fei Li. Imagenet: A large-scale hierarchical image
database. In IEEE Conference on Computer Vision and Pattern Recognition, 2009.
Timothy Dozat. Incorporating nesterov momentum into adam. ICLR Workshop, 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic
optimization. Journal of Machine Learning Research, 12(7):257–269, 2011.
Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods. In Proceedings of 33rd Conference and Workshop on Neural Information Processing Systems,
2019.
Daniel Ramage Seth Hampson H. Brendan McMahan, Eider Moore and Blaise Aguera y Arcas.
Communication-efficient learning of deep networks from decentralized data. In International Conference on
Machine Learning (ICML), 2016.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing
internal covariate shift. In Proceedings of the 32nd annual international conference on machine learning, 2015.
Rajat Monga Kai Chen Matthieu Devin Quoc V. Le Mark Z. Mao Marc Aurelio Ranzato Andrew Senior Paul
Tucker Ke Yang Jeffrey Dean, Greg S. Corrado and Andrew Y. Ng. Large scale distributed deep networks. In
Neural Information Processing Systems Conference (NIPS 2012), pages 1–11, 2012.
Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In International Conference
on Learning Representations, pages 1–13, 2015.
H. Brendan Mcmahan and Matthew Streeter. Delay-tolerant algorithms for asynchronous distributed online
learning. In Neural Information Processing Systems Conference (NIPS 2014), pages 1–9, 2014.
A. Neelakantan, L. Vilnis, Q. V. Le, I. Sutskever, and J. Martens. Adding gradient noise improves learning for
very deep networks. arXiv preprint arXiv:1511.06807., 2015.
Arkadii S. Nemirovski, Anatoli Juditsky, Guanghui Lan, Shapiro, and A. Robust stochastic approximation
approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009.
Y. E. Nesterov. A method for solving the convex programming problem with convergence rate o(1/ ). Dok-
l.akad.nauk Sssr, 269, 1983.
Q. Ning. On the momentum term in gradient descent learning algorithms. Neural Netw, 12(1):145–151, 1999.
F. Niu, B. Recht, C. Re, and S. J. Wright. Hogwild!: A lock-free approach to parallelizing stochastic gradient
descent. In Neural Information Processing Systems Conference (NIPS 2011), pages 1–22, 2011.
B. T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr Computational Mathe-
matics Mathematical Physics, 4(5):1–17, 1964.
A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic
optimization. In International Conference on Machine Learning, 2012.
Anna Choromanska Sixin Zhang and Yann LeCun. Deep learning with elastic averaging sgd. In Neural Information Processing Systems Conference (NIPS 2015), pages 1–9, 2015.
R.S. Sutton. Twoproblemswith backpropagationand other steepest-descent learning proceduresfor networks.
proc cognitive sci soc, 1986.
T. Tieleman and G. Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, pages 26–31, 2012.
Panos Toulis and Edoardo M. Airoldi. Asymptotic and finite-sample properties of estimators based on stochastic gradients. Eprint Arxiv, 45(4):1694–1727, 2017.
Ronan Collobert Yoshua Bengio, Jme Louradour and Jason Weston. Curriculum learning. In Proceedings of the
26th annual international conference on machine learning, pages 41–48, 2009.
Matthew D. Zeiler. Adadelta: An adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012.
Matthew D. Zeiler. Identifying and attacking the saddle point problem in high-dimensional nonconvex optimization. arXiv preprint arXiv:1406.2572, 2014. - END -
| 
发表于 2024-8-31 11:31:37