（十七）通俗易懂理解——梯度下降算法

梦里寻梦

发布时间 2022.03.10阅读数 3229 评论数 0

以下内容针对梯度下降算法的概述，但是仍没有涉及到各个优化算法的优化场景，有待以后看到补充。

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

首先介绍梯度下降算法的三种框架，然后介绍它们存在的问题和挑战，接着介绍如何进行改进来解决存在的问题即算法的优化。

一、梯度下降算法三大框架

批量梯度下降（Batch gradient descent）

旨在每次使用全量的训练集样本来更新模型参数，即：θ=θ−η⋅∇θJ(θ)
伪码如下：

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

nb_epochs是用户输入的最大迭代次数。使用全量的训练集样本计算损失函数loss_function的梯度params_grad，然后使用学习速率learning_rate朝着梯度相反方向去更新模型的每一个参数params。

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

随机梯度下降（Stochastic gradient descent）

旨在每次从训练集中随机选择一个样本来进行学习，即：θ=θ−η⋅∇θJ(θ;xi;yi)
伪码如下：

for i in range(nb_epochs):
     np.random.shuffle(data)
     for example in data:
        params_grad = evaluate_gradient(loss_functon,example,params)
        params = params - learning_rate * params_grad

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

我们可以对不同的参数方案和他们如何快速优化有一个直观的认识：

特别观察一下SGD，红色的那条线，从图中可以看出SGD实际上是所有方法中最慢的一个，所以在实际中很少应用它，我们可以使用更好的方案。

那我们来分析一下SGD的问题，是什么原因导致它的的速度这么慢？

举个栗子：

我们可以从水平方向上可以看出，它的梯度很是非常小的，因为处于在一个比较浅的水平里；但是垂直有很大的速率，因为它是一个非常陡峭的函数，所以出现了这种状况：

在这种情况下使用SGD，在水平方向上进行比较缓慢，而在垂直方向上进展的很快，所以产生了很大的上下震荡。
* 小批量梯度下降（Mini-batch gradient descent）

旨在综合了 batch 梯度下降与 stochastic 梯度下降，在每次更新速度与更新次数中间取得一个平衡，其每次更新从训练集中随机选择 m,m

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

二、Challenges

虽然梯度下降算法效果很好，并广泛使用，但是也存在着问题和挑战需要解决：
1. 选择一个合理的学习速率很难。如果学习速率过小，则会导致收敛速度很慢；如果学习速率过大，那么就会阻碍收敛，即在极值点附近会震荡。
学习速率调整（又称学习速率调度，Learning rate schedules），在每次更新过程中，改变学习速率，如退火。一般使用某种事先设定的策略或者在每次迭代中衰减一个较小的阈值。无论哪种调整方法，都需要事先进行固定设置，这便无法自适应每次学习的数据集特点。

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

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

三、梯度下降优化算法

Momentum

如果把要优化的目标函数看成山谷的话，可以把要优化的参数看成滚下山的石头，参数随机化为一个随机数可以看做在山谷的某个位置以0速度开始往下滚。目标函数的梯度可以看做给石头施加的力，由力学定律知：F=m∗a，所以梯度与石头下滚的加速度成正比。因而，梯度直接影响速度，速度的累加得到石头的位置，对这个物理过程进行建模，可以得到参数更新过程为

# Momentum update
  v = momentum * v - learning_rate * dx # integrate velocity
  x += v # integrate position

代码中v指代速度，其计算过程中有一个超参数momentum，称为动量（momentum）。虽然名字为动量，其物理意义更接近于摩擦，其可以降低速度值，降低了系统的动能，防止石头在山谷的最底部不能停止情况的发生。如果没有momentum * v，那么小球就永远都不会停下了，会在平面上滚动，不会有能量的损失，损失函数就很难最小化。动量的取值范围通常为[0.5, 0.9, 0.95, 0.99]，一种常见的做法是在迭代开始时将其设为0.5，在一定的迭代次数（epoch）后，将其值更新为0.99。

加上动量项就像从山顶滚下一个球，球往下滚的时候累积了前面的动量(动量不断增加)，因此速度变得越来越快，直到到达终点。同理，在更新模型参数时，对于那些当前的梯度方向与上一次梯度方向相同的参数，那么进行加强，即这些方向上更快了；对于那些当前的梯度方向与上一次梯度方向不同的参数，那么进行削减，即这些方向上减慢了。即在陡峭的方向上削弱这些动荡，在一致的浅的方向激励此过程。因此可以获得更快的收敛速度与减少振荡。

Nesterov Momentum Update（又称之为Nesterov Accelerated Gradient-NAG）

回头看一下原始的Momentum：

v = momentum * v - learning_rate * dx

图中的momentum step（绿色的变量）代表代码中的动能项(momentum * v)，gradient step （红色的变量）代表梯度也就是损失函数减少的方向( - learning_rate * dx)，蓝色的线就是他们俩的向量和。

Nesterov Momentum要比Momentum的效果会好一些，我们先不管现输入是什么，所以在我们还没有计算出gradient step（红色的变量）情况下，我们已经建立了momentum step（绿色的变量），并得到了未知的梯度。也就是说，Nesterov Momentum想让我们来预测结果–gradient step，也就是计算在momentum step绿色箭头这一点的梯度确定gradient step，这样得到了和之前细微不同的更新结果，理论上，这一方法有着更好的收敛效果，在实际上确实要比Momentum好得多。

通俗的解释一下，由于从山顶往下滚的球会盲目地选择斜，Nesterov Momentum是在遇到倾斜向上之前应该减慢速度。

Nesterov Momentum和Momentum的差别在这里：

和之前Momentum不同的是，Nesterov Momentum在计算的梯度的时候，加上了μ*Vt-1，这种方式预估了下一次参数所在的位置，选择了和之前计算梯度不同的位置，称之为预测位置（lookahead position），所以Nesterov Momentum的效果会更好。

Adagrad

Adagrad也是一种基于梯度的优化算法。

cache += dx**2
x += - learning_rate * dx / (np.sqrt(cache) + le-7)

相比于SGD，增加了个附加变量—-cache来放缩梯度，并且是不停的增加这一附加变量。这里的变量cache是一个联合矢量，和主向量是一样大的，因为cache在每一维度计算其相应梯度的平方和，我们将这些cache构造起来，然后逐项用这一函数去除以cache的平方，使得对每个参数自适应不同的学习速率，对稀疏特征，得到大的学习更新，对非稀疏特征，得到较小的学习更新，因此该优化算法适合处理稀疏特征数据。

So，举个栗子：

Adagrad在垂直方向上的梯度会加到cache中，然后相应的会除以越来越大的数，所以在垂直方向上会得到越来越小的更新。当我们在垂直方向上看到许多大的梯度，Adagrad就会衰减学习速率，使垂直方向的更新步长越来越小。在水平方向上的梯度是很小的，所以分母会变小，相比于垂直方向，水平方向更新更快。这就是对每个参数自适应不同的学习速率，针对不同梯度方向的补偿措施。

但是，此时，我们思考一个问题，如果我们训练整个神经网络，更新过程中步长大小会发生什么变化？
A：在Adagrad算法中，不断有正数加到分母的cache变量中，步长就会逐渐衰减到0，最后完全停止学习。

但是在神经网络中，我们需要整个网络不断变化从而修正数据，这才是正确的思考方式。它需要持续的活力来不断更新数据，而不是衰退到停止。所以，针对这一问题，Geoff Hinton对Adagrad做了个小小的改变，也被称之为RMSProp算法。

RMSProp

RMSProp是由Adagrad演化过来的：

RMSProp主要的思想是：cache不再是每一维度计算平方和，而是变成一个“泄露”的变量，利用衰减率（decay_rate）这个超参数，通常将decay_rate设置为0.99，接着计算引入衰减率发生“泄露”的平方和。所以我们仍然保持了在梯度较大或较小方向上，对于更新步长的补偿效果，但是不会再发生更新停止的情况。

Adam

Adam也是一种不同参数自适应不同学习速率方法，它是Adagrad算法和Momentum算法的结合体，可称之为“极品”，哈哈。正如你所见：

# Adam
m = beta1 * m + (1-beta1) * dx
v  = beta2 * v  + (1-beta2) * (dx**2)
x += - learning_rate * m / (np.sqrt(v)) + le-7)

m与v分别是梯度的带权平均和带权有偏方差，初始为0向量，Adam的作者发现他们倾向于0向量(接近于0向量)，特别是在衰减因子(衰减率)β1,β2接近于1时。为了改进这个问题，对m与v进行偏差修正(bias-corrected)，偏差修正取决于时间步长t：

# Adam
m = beta1 * m + (1-beta1) * dx
v  = beta2 * v  + (1-beta2) * (dx**2)
m /= 1-beta1**t
v /= 1-beta2**t
x += - learning_rate * m / (np.sqrt(v)) + le-7)

牛顿法

牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。

根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。

迭代公式：

我们可以通过公式可以看出二阶收敛的优势，没有学习速率，没有超参数，只要知道方向和曲率，就能达到近似的最低值，牛顿法的具体推导过程在此不再赘述。但在实际应用中，牛顿法不是很受欢迎，在迭代公式中的H是指Hessian矩阵，比如你有1亿的数据，Hessian矩阵是1亿行和1亿列，然后进行逆运算，Good Luck!这是不可能发生的。

还有一些二阶的梯度下降算法，我们不准备使用它们，在此一并简单介绍：

BGFS

BGFS算法不用对Hessian矩阵进行逆运算，通过秩为1的矩阵连续更新得到一个近似的Hessian矩阵，但是依然要存储Hessian矩阵的值，所以对大型神经网络仍然不适用。

最后找到一篇文章能够对以上内容做进一步深入的理解

SGD

此处的SGD指mini-batch gradient descent，关于batch gradient descent, stochastic gradient descent, 以及 mini-batch gradient descent的具体区别就不细说了。现在的SGD一般都指mini-batch gradient descent。

SGD就是每一次迭代计算mini-batch的梯度，然后对参数进行更新，是最常见的优化方法了。即：

$g_t=\nabla_{\theta_{t-1}}{f(\theta_{t-1})}$

$\Delta{\theta_t}=-\eta*g_t$

其中， $\eta$ 是学习率， $g_t$ 是梯度 SGD完全依赖于当前batch的梯度，所以 $\eta$ 可理解为允许当前batch的梯度多大程度影响参数更新

缺点：（正因为有这些缺点才让这么多大神发展出了后续的各种算法）

选择合适的learning rate比较困难 - 对所有的参数更新使用同样的learning rate。对于稀疏数据或者特征，有时我们可能想更新快一些对于不经常出现的特征，对于常出现的特征更新慢一些，这时候SGD就不太能满足要求了

SGD容易收敛到局部最优，并且在某些情况下可能被困在鞍点【原来写的是“容易困于鞍点”，经查阅论文发现，其实在合适的初始化和step size的情况下，鞍点的影响并没这么大。感谢@冰橙的指正】

Momentum

momentum是模拟物理里动量的概念，积累之前的动量来替代真正的梯度。公式如下：

$m_t=\mu*m_{t-1}+g_t$

$\Delta{\theta_t}=-\eta*m_t$

其中， $\mu$ 是动量因子

特点：

下降初期时，使用上一次参数更新，下降方向一致，乘上较大的 $\mu$ 能够进行很好的加速
下降中后期时，在局部最小值来回震荡的时候， $gradient\to0$ ， $\mu$ 使得更新幅度增大，跳出陷阱
在梯度改变方向的时候， $\mu$ 能够减少更新总而言之，momentum项能够在相关方向加速SGD，抑制振荡，从而加快收敛

Nesterov

nesterov项在梯度更新时做一个校正，避免前进太快，同时提高灵敏度。将上一节中的公式展开可得：

$\Delta{\theta_t}=-\eta*\mu*m_{t-1}-\eta*g_t$

可以看出， $m_{t-1}$ 并没有直接改变当前梯度 $g_t$ ，所以Nesterov的改进就是让之前的动量直接影响当前的动量。即：

$g_t=\nabla_{\theta_{t-1}}{f(\theta_{t-1}-\eta*\mu*m_{t-1})}$

$m_t=\mu*m_{t-1}+g_t$

$\Delta{\theta_t}=-\eta*m_t$

所以，加上nesterov项后，梯度在大的跳跃后，进行计算对当前梯度进行校正。如下图：

momentum首先计算一个梯度(短的蓝色向量)，然后在加速更新梯度的方向进行一个大的跳跃(长的蓝色向量)，nesterov项首先在之前加速的梯度方向进行一个大的跳跃(棕色向量)，计算梯度然后进行校正(绿色梯向量)

其实，momentum项和nesterov项都是为了使梯度更新更加灵活，对不同情况有针对性。但是，人工设置一些学习率总还是有些生硬，接下来介绍几种自适应学习率的方法

Adagrad

Adagrad其实是对学习率进行了一个约束。即：

$n_t=n_{t-1}+g_t^2$

$\Delta{\theta_t}=-\frac{\eta}{\sqrt{n_t+\epsilon}}*g_t$

此处，对 $g_t$ 从1到 $t$ 进行一个递推形成一个约束项regularizer， $-\frac{1}{\sqrt{\sum_{r=1}^t(g_r)^2+\epsilon}}$ ， $\epsilon$ 用来保证分母非0

特点：

前期 $g_t$ 较小的时候， regularizer较大，能够放大梯度
后期 $g_t$ 较大的时候，regularizer较小，能够约束梯度
适合处理稀疏梯度

缺点：

由公式可以看出，仍依赖于人工设置一个全局学习率
$\eta$ 设置过大的话，会使regularizer过于敏感，对梯度的调节太大
中后期，分母上梯度平方的累加将会越来越大，使 $gradient\to0$ ，使得训练提前结束

Adadelta

Adadelta是对Adagrad的扩展，最初方案依然是对学习率进行自适应约束，但是进行了计算上的简化。 Adagrad会累加之前所有的梯度平方，而Adadelta只累加固定大小的项，并且也不直接存储这些项，仅仅是近似计算对应的平均值。即：

$n_t=\nu*n_{t-1}+(1-\nu)*g_t^2$

$\Delta{\theta_t} = -\frac{\eta}{\sqrt{n_t+\epsilon}}*g_t$

在此处Adadelta其实还是依赖于全局学习率的，但是作者做了一定处理，经过近似牛顿迭代法之后：

$E|g^2|_t=\rho*E|g^2|_{t-1}+(1-\rho)*g_t^2$

$\Delta{x_t}=-\frac{\sqrt{\sum_{r=1}^{t-1}\Delta{x_r}}}{\sqrt{E|g^2|_t+\epsilon}}$

其中， $E$ 代表求期望。

此时，可以看出Adadelta已经不用依赖于全局学习率了。

特点：

训练初中期，加速效果不错，很快
训练后期，反复在局部最小值附近抖动

RMSprop

RMSprop可以算作Adadelta的一个特例：

当 $\rho=0.5$ 时， $E|g^2|_t=\rho*E|g^2|_{t-1}+(1-\rho)*g_t^2$ 就变为了求梯度平方和的平均数。

如果再求根的话，就变成了RMS(均方根)：

$RMS|g|_t=\sqrt{E|g^2|_t+\epsilon}$

此时，这个RMS就可以作为学习率 $\eta$ 的一个约束：

$\Delta{x_t}=-\frac{\eta}{RMS|g|_t}*g_t$

特点：

其实RMSprop依然依赖于全局学习率
RMSprop算是Adagrad的一种发展，和Adadelta的变体，效果趋于二者之间
适合处理非平稳目标 - 对于RNN效果很好

Adam

Adam(Adaptive Moment Estimation)本质上是带有动量项的RMSprop，它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。公式如下：

$m_t=\mu*m_{t-1}+(1-\mu)*g_t$

$n_t=\nu*n_{t-1}+(1-\nu)*g_t^2$

$\hat{m_t}=\frac{m_t}{1-\mu^t}$

$\hat{n_t}=\frac{n_t}{1-\nu^t}$

$\Delta{\theta_t}=-\frac{\hat{m_t}}{\sqrt{\hat{n_t}}+\epsilon}*\eta$

其中， $m_t$ ， $n_t$ 分别是对梯度的一阶矩估计和二阶矩估计，可以看作对期望 $E|g_t|$ ， $E|g_t^2|$ 的估计； $\hat{m_t}$ ， $\hat{n_t}$ 是对 $m_t$ ， $n_t$ 的校正，这样可以近似为对期望的无偏估计。可以看出，直接对梯度的矩估计对内存没有额外的要求，而且可以根据梯度进行动态调整，而 $-\frac{\hat{m_t}}{\sqrt{\hat{n_t}}+\epsilon}$ 对学习率形成一个动态约束，而且有明确的范围。