关于梯度下降优化算法的概述

ゝ一纸荒年。 2022-06-13 08:52 206阅读 0赞

本译文关于各种梯度下降优化算法的概述，原文：[An overview of gradient descent optimization algorithms][]  
论文下载地址：[点击这里][Link 1]

# 摘要 #

梯度下降算法是最流行的优化算法之一，并且是迄今为止最常见的优化神经网络的方法。同时，每个最先进的深度学习库包含各种梯度下降优化算法的实现，（例如： lasagne，caffe和keras）。然而，这些算法通常用作黑盒优化器，因为它们的优点和缺点的实际解释很难实现。  
本文旨在为您提供不同的梯度下降优化算法最直观的作用，这将有助于您更好的使用它们。我们首先要看梯度下降的不同变体。 然后，我们将简要总结训练过程中的挑战和困难。 随后，我们将通过两个方面引入常见的优化算法：1.这些算法提出的动机是什么，需要解决的问题是什么？2.这些算法关于权系数更新规则的推导过程。我们还将简要介绍算法和架构，以优化并行和分布式设置中的梯度下降。 最后，我们将考虑有助于优化梯度下降的其他策略。  
梯度下降是通过向负梯度方向 ▽ θ J ( θ ) \\triangledown \_\{\\theta \}J(\\theta) ▽θJ(θ)更新参数，使目标函数 （损失函数） J ( θ ) J(\\theta) J(θ)最小化的一种方法，其中参数为 θ \\theta θ。**（注意这个公式第一个θ是一个下角标，是关于θ的函数的意思）**。学习率（步长） η决定了每一步的大小。话句话说，梯度下降算法是沿着目标函数计算得到的下降方向，直到达到一个最低点（局部最小/全局最小）。如果您还不熟悉梯度下降，您可以在[这里][Link 2]找到一个关于优化神经网络的很好的介绍。

# 梯度下降算法 #

下面介绍三种梯度下降算法，他们之间的不同之处在于有多少样本被用于计算目标函数的梯度。根据样本数目的多少，我们在参数更新的准确性与执行更新所需的时间之间进行一个权衡。  
这部分内容在[理解梯度下降在机器学习模型优化中的应用][Link 3]中已有涉及，但是为了翻译的完整性，还是把该内容翻译了。

## 批量梯度下降 ##

Vanilla梯度下降，也叫作批量梯度下降。在整个训练数据集范围，计算损失函数的梯度，并用于更新参数 θ \\theta θ：  
 θ = θ − η ⋅ ▽ θ J ( θ ) \\theta = \\theta-\\eta \\cdot \\triangledown \_\{\\theta \}J(\\theta) θ=θ−η⋅▽θJ(θ)

那么，在每一次更新中我们都需要计算全部的数据集，所以批次梯度下降的速度是非常慢的，而且难以处理并不适合存储的数据集。批次梯度下降也不允许我们在线更新模型，即运行时新增实例。

批次梯度下降的代码如下：

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

对于预先设定的周期（迭代次数），我们首先在整个数据集范围内计算损失函数的梯度向量 —params\_grad，需要优化的参数为变量—params。注意，当下先进的深度学习库提供了多种自动计算梯度的有效方法。但是如果您要自己设计一种新的方法，那么梯度检验（gradient checking）是一个很好的方式去验证新方法的可行性。（请参阅[这里][Link 4]关于如何正确检查梯度的一些提示）。

然后，我们按梯度方向更新我们的参数，学习速率决定了我们每一步执行时更新的程度。 批量梯度下降能够保证更好的收敛到误差平面全局最小值，并且到达一个非凸误差平面的局部最小值。

## 随机梯度下降 ##

随机梯度下降（SGD）根据任意一个（随机）样本的特征 x ( i ) x(i) x(i)及其标签 y ( i ) y(i) y(i)进行参数的更新：

θ = θ − η ⋅ ▽ θ J ( θ ; x ( i ) ; y ( i ) ) \\theta = \\theta-\\eta \\cdot \\triangledown \_\{\\theta \}J(\\theta;x(i);y(i)) θ=θ−η⋅▽θJ(θ;x(i);y(i))

批次梯度下对大型数据集执行冗余计算，因为它在下一步参数更新之前重复计算了很多相似样本的的梯度。随机梯度下降避免了这种冗余通过每一次更新时只执行一次计算（随机的单个样本的计算）。因此，它相比于批次梯度下降通常要快得多，也可以用来在线学习。  
随机梯度下降在以一个比较大差异进行频繁更新，这就了导致目标函数（损失函数）下降过程中产生剧烈的波动，如下图。  
![这里写图片描述][aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwNzAzMTcwMzIxMDQy]

然而批次梯度下降算法收敛到一个局部最小点后，参数就不会再改变（参数确定，认为达到条件，参数被放置于该点，就是这个意思）。随机梯度下降的较大波动一方面能够让参数跳出这个局部最小值，转而寻找更好的局部最小值点。另一方面，当这个更加复杂化的收敛达到理想最小值点时，随机梯度下降算法也可能使它继续跳过这个点（有利总有弊么，没毛病！）。然后经过验证，当我们根据步数的增加逐步降低学习速率（步长）时，随机梯度下降一定会最终收敛到非凸误差平面的局部最小值和凸优化的全局最小值（在大多数情况下是非凸的），这种效果和批次下降是一样的（最后的效果一样，计算代价还小，所以好用，就酱！）。  
在下面的代码中，简单的加入了循环为了训练和计算任意一个样本的梯度。主要注意在每一次迭代中要对训练数据随机洗牌。

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

## 小批量梯度下降 ##

小批量梯度下降结合了前两者的优点，在每次更新依据训练数据集中的选择出的一个小批量（n）数据：

θ = θ − η ⋅ ▽ θ J ( θ ; x ( i : i + n ) ; y ( i : i + n ) ) \\theta = \\theta-\\eta \\cdot \\triangledown \_\{\\theta \}J(\\theta;x(i:i+n);y(i:i+n)) θ=θ−η⋅▽θJ(θ;x(i:i\+n);y(i:i\+n))

在这个方法中，第一可以降低每次更新时的波动，可以更稳定的收敛；第二在很多现金的深度学习库中经过高度优化过的矩阵计算使小批量梯度下降算法变得更加高效。通常情况下batch size为50到256，但是也可以根据不同的需要做出调整。小批量梯度下降算法是训练神经网络模型的最常见的选择。需要注意的是，使用小批量梯度下降算法时也用这个术语—SGD（毕竟我是没有看到过Mini-SGD这个说法），在本文其他部分修改SGD时，为了简单起见，会省略参数 x ( i : i + n ) ; y ( i : i + n ) x(i:i+n);y(i:i+n) x(i:i\+n);y(i:i\+n)。  
代码如下，batch size 为50：

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

## 困难和挑战 ##

然而，小批量梯度下降并不能保证良好的收敛性，还有一些需要解决的挑战：  
1.选择一个合适的学习率比较困难，学习率过小会导致收敛很慢，学习率过大会妨碍收敛，导致损失函数在最小值点出波动设置导致发散。  
2.学习率表（就好比一个根据时间或步数规划好的表）尝试在训练期间调整学习率，比如退火算法。即根据预先设定好的计划表逐步降低学习率；或者当目标函数低于某些设定好的阈值的时候改变学习率。然而这种根据步数或者阈值的方法都需要提前定义好，因为无法自适应不同数据集的特征。  
3.此外，相同的学习率应用到所有的参数。但是如果我们的数据是稀疏的，特征有非常不同的频率，这样的话我们并不想把每一个特征都更新到相同的程度。  
4.最后一个很关键的困难在于在神经网络中最小化非凸误差函数面要避免陷入诸多的局部最小值中，而Dauphin等人认为困难实际上不是来自于局部最小值的问题，而是来自于鞍点，鞍点即一个维度向上倾斜并且在另一个维度向下倾斜的点。 这些鞍点通常被相同误差的平面所围绕，这使得SGD很容易陷入鞍点，因为在鞍点处的每一个维度的梯度都接近于零。

# 梯度下降优化算法 #

下面，我们将列举一些在深度学习领域等到宽泛使用的算法去处理上述问题。我们不会讨论那些在实践中对于高维数据集而言不可行计算的算法。比如二阶方法中的[牛顿法][Link 5]。

## 动量 ##

随机梯度下降算法在经过峡谷(navigating ravines)时候会碰到问题。意思是说，画出目标函数的等值面，那些在某些方向（维度）上的梯度很大，在其他方向（维度）上的梯度很小的地方，就叫做ravine。在这些点上，SGD算法在收敛到局部最优点的过程中容易产生振荡。如下图：  
![这里写图片描述][aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwNzA0MTM1ODQ1NzQ2]  
动量法可以使加速SGD收敛速度并在相关方向上抑制振荡，如上图所示。这是因为在更新当前的参数向量时加入了一个分数（系数） γ \\gamma γ与过去的参数向量的乘积。（翻译的很拗口，直接看公式吧，注意加的是上一步改变的权系数的值 ▽ θ \\triangledown \_\{\\theta \} ▽θ，而不是 θ \\theta θ)。

v t = γ v t − 1 + η ⋅ ▽ θ J ( θ ) v\_\{t\} = \\gamma v\_\{t-1\}+\\eta \\cdot \\triangledown \_\{\\theta \}J(\\theta) vt=γvt−1\+η⋅▽θJ(θ)

θ = θ − v t \\theta = \\theta-v\_\{t\} θ=θ−vt

注意：在不同的文章中符号 γ \\gamma γ可能会有不同，他的一般取值为0.9左右。  
基本上，当使用动量时，可以想象成球滚下山的过程：在向下滚动的过程中，球不断的积累动量，也就变得越拉越快（直到达到最终的速度，如果有空气阻力，即系数 γ \\gamma γ<1）。动量式的参数更新也是一样的：当两次某维数的梯度同向，那么相加之后会变大，相反则会在该维度上变小，这样的结果就是获得更快的收敛和减少振荡。  
论文有时就是这样，话比较偏学术一些，不太直白，简单说，如果没有 γ v t − 1 \\gamma v\_\{t-1\} γvt−1这一项，动量法和SGD没有区别，所以动量其实就是加上了上一步的权值改变，注意加上的不是上一时刻的权值，而是上一时刻的**权值变化**，乘以系数 γ \\gamma γ。

## Nesterov 加速梯度 ##

然而，一个盲目跟随斜坡向下滚的球，是非常不令人满意的。 我们想要一个更聪明的球——它应该有向哪里走的概念，这样的话在山坡再次升起之前球可以做减速（这样就不会冲过最小值点）。  
Nesterov 加速梯度（NAG）算法提供了一种对动量预测的方法。我们知道依靠动量 γ v t − 1 \\gamma v\_\{t-1\} γvt−1来改变参数 θ \\theta θ。计算 θ − γ v t − 1 \\theta- \\gamma v\_\{t-1\} θ−γvt−1给出了参数的下一个位置的近似值（完全更新缺失的梯度），这种估计方法比较粗略。然而，我们不计算关于当前参数的梯度而是计算关于参数的大致未来位置的梯度，这样的话能够有效的预测。

v t = γ v t − 1 + η ⋅ ▽ θ J ( θ − γ v t − 1 ) v\_\{t\} = \\gamma v\_\{t-1\}+\\eta \\cdot \\triangledown \_\{\\theta \}J(\\theta - \\gamma v\_\{t-1\}) vt=γvt−1\+η⋅▽θJ(θ−γvt−1)

θ = θ − v t \\theta = \\theta-v\_\{t\} θ=θ−vt  
![这里写图片描述][aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwNzIwMTM0NzE0ODM1]

动量法首先计算了当前的梯度（上图中短的蓝色的线） ，然后在在更新的累积梯度的方向上有一段大的跳跃（长的蓝色的线），NAG首先在先前计算得到的梯度方向上做一个大的跨越（短棕色），计算并矫正梯度（绿色的线）。这种带有预测性的更新阻止我们过快，导致响应性增加，这大大增加了RNN在一些任务上的性能。  
现在我们可以根据损失函数的斜坡调整参数的更新适应，并依次加速SGD，之后我们也希望调整每个参数的更新以执行更大或更小的更新。（这句话是这样来的，上面两种更新方法，都是所有的权系数在共享一个学习率，而下面的方法使每个权系数有一个自己的学习率。）

## Adagrad ##

Adagrad 是一种基于梯度优化的算法，它只能实现这一点：它根据每一个参数调整学习速率，主要表现在：对于原来不怎么更新的参数，提高它们的学习率，对于原来经常更新的参数，降低它们的学习率（这里的更新说的是学习率）。 因此，它非常适合处理稀疏数据。 Dean等人 \[6\]发现，Adagrad大大提高了SGD的鲁棒性，并将其用于训练Google的大规模神经网络， 在Youtube视频中学习识别猫。 此外，Pennington等 使用Adagrad训练GloVe词嵌入，因为不常见的单词需要比常用的更多的更新。  
先前，我们在一次更新的过程中对所有的参数都使用了同一个学习率 η \\eta η。而在Adagrad中，在**每一步** t t t中都对**每一个参数**使用不同的学习率。首先展示梯度如何很对每一个参数更新。为了简洁，设 g t , i g\_\{t,i\} gt,i为目标函数中第 i i i个参数在第 t t t步时的梯度。即：  
 g t , i = ▽ θ t J ( θ t , i ) g\_\{t,i\} = \\triangledown \_\{\\theta\_\{t\} \} J(\\theta \_\{t\},i) gt,i=▽θtJ(θt,i)

在SGD中，每个参数在任何步数时变化都是一致，因为 η \\eta η没有随着 t t t和 i i i的变化而变化，即：  
 θ t + 1 , i = θ t , i − η ⋅ g t , i \\theta \_\{t+1\},i = \\theta \_\{t\},i - \\eta \\cdot g\_\{t,i\} θt\+1,i=θt,i−η⋅gt,i

而在Adagrad的更新规则中，初始的学习率 η \\eta η在每一步对于每一个参数 θ i \\theta\_\{i\} θi都会根据过去计算得到的梯度值改变：

θ t + 1 , i = θ t , i − η G t , i i + ϵ ⋅ g t , i \\theta \_\{t+1\},i = \\theta \_\{t\},i - \\frac\{\\eta\}\{\\sqrt\{G\_\{t,ii\}+\\epsilon \}\} \\cdot g\_\{t,i\} θt\+1,i=θt,i−Gt,ii\+ϵη⋅gt,i

其中 G t , i i G\_\{t,ii\} Gt,ii 是对角矩阵，其中每个对角元素 i i i是 t t t步内（包含之前的梯度）某一个参数的梯度的平方的总和。 ϵ \\epsilon ϵ是一个平滑项，可以避免分母为0（通常取1e-8）。  
Adagrad的主要优点之一是无需手动调整学习率。 大多数情况下只需要一个初始值——0.01。  
然后Adagrad的主要缺陷在于梯度的平方和作为分母，并随着t积累，而由于是平方，所有每一次增加的值都是个正数，这意味着分母会越来越大，累积的数额在训练过程中不断增长。导致学习率逐步缩小，最终趋近于0。 以下算法旨在解决这个缺陷。

[An overview of gradient descent optimization algorithms]: http://sebastianruder.com/optimizing-gradient-descent/index.html#minibatchgradientdescent
[Link 1]: https://arxiv.org/abs/1609.04747
[Link 2]: http://cs231n.github.io/optimization-1/
[Link 3]: http://blog.csdn.net/chaipp0607/article/details/72683375
[Link 4]: http://cs231n.github.io/neural-networks-3/
[aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwNzAzMTcwMzIxMDQy]: /images/20220613/4a62e24e0a8d4636b97e8ce0cd9f6ec6.png
[Link 5]: https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization
[aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwNzA0MTM1ODQ1NzQ2]: /images/20220613/a2106498a4bf40f0b91cbc70b090c886.png
[aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwNzIwMTM0NzE0ODM1]: /images/20220613/f1a6e42926a540408565284f8c368060.png