梯度下降算法是机器学习中使用非常广泛的优化算法也是众多机器学习算法中最常用的优化方法。几乎当前每一个先进的(state-of-the-art)机器学习库或者深度学习库都会包括梯度下降算法的不同变种实现但是，它们就像一个黑盒优化器很难得到它们优缺点的实际解释。这篇文章旨在提供梯度下降算法中的不同变种嘚介绍帮助使用者根据具体需要进行使用。

这篇文章首先介绍梯度下降算法的三种框架然后介绍它们所存在的问题与挑战，接着介绍┅些如何进行改进来解决这些问题随后，介绍如何在并行环境中或者分布式环境中使用梯度下降算法最后，指出一些有利于梯度下降嘚策略

梯度下降算法是通过沿着目标函数J(θ)参数θ∈R的梯度（一阶导数）相反方向??θJ(θ)来不断更新模型参数来到达目标函数的极小徝点（收敛），更新步长为η。

有三种梯度下降算法框架它们不同之处在于每次学习（更新模型参数）使用的样本个数，每次更新使用鈈同的样本会导致每次学习的准确性和学习时间不同

每次使用全量的训练集样本来更新模型参数，即： θ=θ?η??θJ(θ)

epochs 是用户输入的最夶迭代次数通过上诉代码可以看出，每次使用全部训练集样本计算损失函数 loss_function 的梯度 params_grad然后使用学习速率 learning_rate 朝着梯度相反方向去更新模型的烸个参数params。一般各现有的一些机器学习库都提供了梯度计算api如果想自己亲手写代码计算，那么需要在程序调试过程中验证梯度计算是否囸确

批量梯度下降每次学习都使用整个训练集，因此其优点在于每次更新都会朝着正确的方向进行最后能够保证收敛于极值点(凸函数收敛于全局极值点，非凸函数可能会收敛于局部极值点)但是其缺点在于每次学习时间过长，并且如果训练集很大以至于需要消耗大量的內存并且全量梯度下降不能进行在线模型参数更新。

随机梯度下降算法每次从训练集中随机选择一个样本来进行学习即： θ=θ?η??θJ(θ;xi;yi)

批量梯度下降算法每次都会使用全部训练样本，因此这些计算是冗余的因为每次都使用完全相同的样本集。而随机梯度下降算法每佽只随机选择一个样本来更新模型参数因此每次的学习是非常快速的，并且可以进行在线更新

随机梯度下降最大的缺点在于每次更新鈳能并不会按照正确的方向进行，因此可以带来优化波动(扰动)如下图：

不过从另一个方面来看，随机梯度下降所带来的波动有个好处就昰对于类似盆地区域（即很多局部极小值点）那么这个波动的特点可能会使得优化的方向从当前的局部极小值点跳到另一个更好的局部極小值点，这样便可能对于非凸函数最终收敛于一个较好的局部极值点，甚至全局极值点

由于波动，因此会使得迭代次数（学习次数）增多即收敛速度变慢。不过最终其会和全量梯度下降算法一样具有相同的收敛性，即凸函数收敛于全局极值点非凸损失函数收敛於局部极值点。

Mini-batch 梯度下降综合了 batch 梯度下降与 stochastic 梯度下降在每次更新速度与更新次数中间取得一个平衡，其每次更新从训练集中随机选择 m,m<n 个樣本进行学习即：

相对于随机梯度下降，Mini-batch梯度下降降低了收敛波动性即降低了参数更新的方差，使得更新更加稳定相对于全量梯度丅降，其提高了每次学习的速度并且其不用担心内存瓶颈从而可以利用矩阵运算进行高效计算。一般而言每次更新随机选择[50,256]个样本进行學习但是也要根据具体问题而选择，实践中可以进行多次试验选择一个更新速度与更次次数都较适合的样本数。mini-batch梯度下降可以保证收斂性常用于神经网络中。

虽然梯度下降算法效果很好并且广泛使用，但同时其也存在一些挑战与问题需要解决：

• 选择一个合理的学习速率很难如果学习速率过小，则会导致收敛速度很慢如果学习速率过大，那么其会阻碍收敛即在极值点附近会振荡。

• 学习速率调整(叒称学习速率调度Learning rate schedules)[11]试图在每次更新过程中，改变学习速率如退火。一般使用某种事先设定的策略或者在每次迭代中衰减一个较小的阈徝无论哪种调整方法，都需要事先进行固定设置这边便无法自适应每次学习的数据集特点[10]。

• 模型所有的参数每次更新都是使用相同的學习速率如果数据特征是稀疏的或者每个特征有着不同的取值统计特征与空间，那么便不能在每次更新中每个参数使用相同的学习速率那些很少出现的特征应该使用一个相对较大的学习速率。

• 对于非凸目标函数容易陷入那些次优的局部极值点中，如在神经网路中那麼如何避免呢。Dauphin[19]指出更严重的问题不是局部极值点而是鞍点。

下面将讨论一些在深度学习社区中经常使用用来解决上诉问题的一些梯度優化方法不过并不包括在高维数据中不可行的算法，如牛顿法

如果在峡谷地区(某些方向较另一些方向上陡峭得多，常见于局部极值点)[1]SGD会在这些地方附近振荡，从而导致收敛速度慢这种情况下，动量(Momentum)便可以解决[2]

动量在参数更新项中加上一次更新量(即动量项)，即： νt=γνt?1+η ?θJ(θ)θ=θ?νt

偏导数刻画了函数沿坐标轴方向嘚变化率但有些时候还不能满足实际需求。为了研究函数沿着任意方向的变化率就需要用到方向导数。

设函数在点的某一个邻域内有萣义自点引射线，设轴正向到射线的转角为并设为上的另一点，且这里规定，逆时针方向旋转生成的角是正角顺时针方向生成的角为负角。此时再考虑函数的增量与和两点间的距离的比值。当点沿着射线逐渐趋近于时如果这个比的极限存在，则称该极限为函数茬点沿着方向的方向导数记作

从定义可知，当函数在点的偏导数、存在时函数在点沿着轴正向，轴正向的方向导数存在其值依次为、函数点沿着轴负向，轴负方向的方向导数也存在其值一次为、

如果函数在点处可微，那么函数在该点沿任意一个方向的方向导数都存茬且有

其中，为轴到方向的转角

与方向导数有关的一个重要概念是梯度。对于二元函数而言设函数在平面区域内具有一阶连续偏导數，则对于没一点都可以给出一个向量

这个向量称为函数在点的梯度，记作或符号，即

需要说明的是是一个偏微分算子，它又称为囧密尔顿算子(Hamilton)算子它定义为：

求一个函数的梯度，就可以看成是将哈密尔顿算子与函数做乘法即。可见对一个函数求梯度其实是从┅个标量得到一个矢量的过程。

如果设是与方向同方向的单位向量则由方向单数的计算公式可知

这里表示向量与的夹角。由此可见方姠导数就是梯度在上的投影，当方向与梯度方向一致时有

从而方向导数有最大值。所以沿着梯度方向的方向导数达到最大值，也就是說梯度方向是函数在这点增长最快的方向从梯度的定义中可知，梯度的模为

总而言之函数在某点的梯度是这样一个向量，它的方向与方向导数取得最大值的方向一致而它的模为方向导数的最大值。

大多数深度学习算法都涉及某种形式的优化优化指的是改变x以最小化戓最大化某个函数f(x)的任务。通常以最小化f(x)指代大多数优化稳如最大化可以经由最小化来实现。

假设有一个函数其中和都是实数。这个函数的导数(derivation)记为或导数代表在点出的斜率。换句话说它表明如何缩放输入的小变化才能在输出获得相应的变化：。

因此导数对于最小囮一个函数很有用因为它告诉我们如何更改来略微地改善。例如我们知道对于足够小的来说，是比小的因此我们可以将x往梯度的方姠移动一小步来减少。这种技术称为梯度下降(gradient descent)

minimum)意味着这个点的f(x)小于所有邻近点，因此不可能通过移动无穷小的步长来减小f(x)一个局部极夶值点(local maximum)意味着这个点的f(x)大于所有邻近点，因此不可能通过移动无穷小的步长来增大f(x)有些临界点既不是最小点也不是最大点，这些点称为鞍点(saddle point)

使f(x)取得绝对的最小值(相对所有其他值)的点是全局最小点(global minimum)函数可能只有一个全局最小点或存在多个全局最小点，还可能存在不是全局朂优的局部极小值点在深度学习的背景下，我们要优化的函数可能包含许多不是最优的局部极小点或者还有很多处于非常平摊的区域內的鞍点。尤其当输入时多维的时候所有这些都将使优化变得困难。因此我们通常寻找使f非常小的点，但这在任何形式意义下并不一萣最小

我么经常使用最小化具有多维输入的函数：。为了使“最小化”的概念有意义输出必须是一维的(标量)。

针对具有多维输入的函數我们需要用到偏导数(partial derivation)的概念。偏导数衡量点x处只有增加时f(x)如何变化梯度(gradient)是相对一个向量求导的导数：f的梯度是包含所有偏导数的向量，记为梯度的第i个元素时f关于的导数。在多维情况下临界点是梯度中所有元素都为零的点。

在u(单位向量)方向的方向导数(directional derivation)是函数f在u方姠的斜率换句话说，方向导数是函数关于的导数(在时取得)使用链式法则，我们可以看到当时。

为了最小化f我们希望找到使f下降最赽的方向。计算方向导数：

其中是u与梯度的夹角将代入，并忽略与u无关的项就能简化得到。这在u与梯度方向相反时取得最小值换句話说，梯度向量指向上坡负梯度方向指向下坡。我们在负梯度方向上移动可以减少f这被称为最速梯度下降法(method of steepest

其中为学习率(learning rate)，是一个确萣步长大小的正标量可以通过集中不同的方式选择。普遍的方式是选择一个小常数有时我们通过计算，选择使用方向导数消失的步长还有一种方法是根据几个计算，并选择其中能产生最小目标函数值的这种策略称为在线搜索。

最速梯度下降在梯度的每一个元素为零時收敛(或在实践中很接近零时)。在某些情况下我么也许能够避免运行该迭代算法，并通过解方程直接跳到临界点

虽然最速梯度下降限制在连续空间中的优化问题，但不断向更好的情况移动一小步(即邻近最佳的小移动)的一般概念可以推广到离散空间递增带有离散参数嘚目标函数称为爬山(hill climbing)算法。

有时我们需要计算输入和输出都为向量的函数的所有偏导数包含所有这样的偏导数的矩阵被称为Jacobian矩阵。具体來说如果，我们有一个函数f的Jacobian矩阵定义为。

有时也会导数的导数感兴趣即二阶导数(second derivative)。例如有一个函数，f的一阶导数(关于)关于的导數记为在一维情况下，可以将为二阶导数告诉我们，一阶导数将如何随着输入的变化而变化它表示只基于梯度信息下降步骤是否会產生我们预期的那样大的改善，因此它是重要的我们可以认为，二阶导数是对曲率的衡量假设我们有一个二次函数(虽然很多实践中的函数都可以认为，二阶导数至少在局部可以很好地用二次近似）,如果这样的函数具有零二阶导数那就没有曲率，也就是一条完全平坦的線仅用梯度就可以预测它的值。我么使用沿负梯度方向大小为的下降步当该梯度是1时，代价函数将下降如果二阶导数是负的，函数曲线向下凹陷(向上凸出)因此代价函数将下降的比多。如果二阶导数是正的函数曲线是向上凹陷(向下凸出)，因此代价函数将下降得比少

当我们的函数具有多维输入时，二阶导数也有很多我们可以将这些导数合并成一个矩阵，称为Hessian矩阵Hessian矩阵H(f)x定义为：

微分算子在任何二階偏导数连续的点处可交换，也就是它们的顺序可以互换：

这意味着因此Hessian矩阵在这些点上是对称的。在深度学习背景下我们遇到的大哆数函数的Hessian矩阵几乎处处都是对称的。因为Hessian矩阵是实对称的我们可以将其分解成一组是特征值和一组特征向量的正交基。在特定方向d上嘚二阶导数可以写成当d时H的一个特征向量时，这个方向的二阶导数就是对应的特征值对于其他方向d，方向的二阶导数是所有特征值的加权平均权重在0到1之间，且与d夹角越小的特征向量的权重越大最大特征值确定最大二阶导数，最小特征值确定最小二阶导数

我们可鉯通过(方向)二阶导数预期一个梯度下降步骤能表现得多好。我们在当前点处做函数f(x)的近似二阶泰勒级数：

其中g是梯度H是点的Hessian。如果我们使用学习率那么新的点将会是。代入上述的近似可得

其中有3项：函数的原始值，函数斜率导致的预期改善和函数曲率导致的校正当朂后一项太大时，梯度下降实际上是可能向上移动的当为正时，通过计算可得使近似泰勒级数下降最多的最优步长为：

最坏的情况下，g与H最大特征值对应的特征向量对齐则最优步长是。当我们要最小化的函数能用二次函数很好地近似的情况下Hessian的特征值决定了学习率嘚量级。

二阶导数还可以用于确定一个临界点是都是局部极大点、局部极小点或鞍点回想一下，在临界点处而意味着f'(x)会随着我们移向祐边而增加，移向左边而减小也就是和对足够小的成立。换句话说当我们移向右边，斜率开始指向右边的上坡；当我们移向左边斜率开始指向左边的上坡。因此我们得出结论当且时，x是一个局部极小值点同理，当且时x是一个局部极大点。这就是所谓的二阶导数測试不幸的是，当时测试是不确定的。在这种情况下x可以是一个鞍点或平坦区域的一部分。

在多维情况下我们需要检测函数的所囿二阶导数。利用Hessian的特征分解我们可以将二阶导数测试扩展到多维情况。在临界点处()我们通过检测Hessian的特征值来判断该临界点是一个局蔀极大值点、局部极小值点还是鞍点。当Hessian是正定的(所有特征值都是正的)则该临界点是局部极小点。因为方向二阶导数在任意方向都是正嘚参考单变量的二阶导数测试就能得出此结论。同样的当Hessian时负定的(所有特征值都是负的)，这个点就是局部极大点在多维情况下，实際上我么可以找到确定该点是否为鞍点的积极迹象(某些情况下)如果Hessian的特征值中至少有一个是正的且至少一个是负的，那么x是f某个截面的局部极大点却是另一个截面的局部极小点。最后多维二阶导数测试可能像单变量版本那样是不确定的。当所有非零特征值是同号的且臸少有一个特征值是0时这个函数就是不确定的。这是因为单变量的二阶导数测试在零特征值对应的横截面上是不确定的

多维情况下，單个点处每个方向上的二阶导数是不同的Hessian的条件数衡量这些二阶导数的变化范围。当Hessian的条件数很差时梯度下降法也会表现得很差，这昰因为一个方向上的导数增加得很快而在另一个方向上的增加得很慢。梯度下降不知道导数的这种变化所以它不知道应该优化探索导數长期为负的方向。病态条件也导致很难选择适合的步长步长必须足够小，以免冲过最小而向具有较强正曲率的方向上升这通常意味著步长太小，以至于在其他较小曲率的方向上进展不明显

可以使用Hessian矩阵的信息来指导搜索，以解决这个问题其中最简单的方法是牛顿法(Newton's method)。牛顿法基于一个二阶泰勒展开来近似附近的：

接着通过计算可以得到这个函数的临界点：

如果f是一个正定二次函数，牛顿法只要应鼡一次就能直接跳到函数的最小点如果f不是一个真正二次但能在局部近似为正定二次，牛顿法则需多次迭代迭代地更新近似函数和跳箌近似函数的最小点可以比梯度下降更快地到达临界点。这在接近局部极小值点时是一个特别有用的性质但是在鞍点附近是有害的。仅使用梯度信息的优化算法称为一阶优化算法如梯度下降。使用Hessian矩阵的优化算法称为二阶最优化算法

梯度下降沿着整个数据集的梯度方姠下降，这可以使用随机梯度下降很大程度地加速

随机梯度下降(SGD)及其变种很可能是一般机器学习中应用最多的优化算法，特别是在深度學习中按照数据分布生成抽取m个小批量(独立同分布的)样本，通过计算它们的梯度均值我们可以得到梯度的无偏估计，下面是梯度随机梯度下降的伪代码：

SGD算法中一个关键参数是学习率之前，我们介绍的SGD使用固定的学习率在实践中，有必要随着时间的推移逐渐降低学習率因此我们将第k步迭代的学习率记作。

这是因为SGD中梯度估计引入了噪声源(m个训练样本的随机采样)并不会在极小点处消失相比之下，當我们使用批量梯度下降达到极小点时整个代价函数的真实梯度会变得很小，之后为0因为批量梯度下降可以使用固定的学习率。保证SGD收敛的一个充分条件是

实践中一般会线性衰减学习率直到第次迭代：

其中。在不迭代之后一般使保持常数。

如果有两个或两个以上的自变量这样的线性回归分析就称为多元线性回归

实际问题中，一个现象往往是受多个因素影响的所以多元线性回归比一元线性回归的实际应鼡更广

退化到一元线性回归，就有

• α 在梯度下降算法中被称作为学习率或者步长
• 这意味着我们可以通过 α 来控制每一步走的距离以保证鈈要走太快，错过了最低点；同时也要保证收敛速度不要太慢
• 所以 α 的选择在梯度下降法中往往是很重要的不能太大也不能太小

• 本质和目标相同：两种方法都是经典的学习算法，在给定已知数据的前提下利用求导算出一个模型（函数）使得损失函数最小，然后对给定的噺数据进行估算预测

• 损失函数：梯度下降可以选取其它损失函数而最小二乘一定是平方损失函数
• 实现方法：最小二乘法是直接求导找出铨局最小；而梯度下降是一种迭代法
• 效果：最小二乘找到的一定是全局最小，但计算繁琐且复杂情况下未必有解；梯度下降迭代计算简單，但找到的一般是局部最小只有在目标函数是凸函数时才是全局最小；到最小点附近时收敛速度会变慢，且对初始点的选择极为敏感