机器学习-梯度下降算法汇总（2）

Oct 12, 2019 · 机器学习  ·
分享到:

梯度下降算法（2）

上一篇文章我们理解到了Adagrad算法，即一个逐渐降低学习率的算法。它带来一个弊端，学习率可能过早的太小，以致于离最优点还很远就收敛了。因此有人提出了RMSprop算法来缓解这个问题，我们这篇文章从这里开始讲起。原文中先将Adadelta，但是我觉得原文这里有些难以理解，所以先从RMSprop说起。

梯度优化算法

Adagrad

Adagrad在原来基础上，做了这样一个优化：让学习率适应参数，对于出现次数较少的特征，我们对其采用更大的学习率，对于出现次数较多的特征，我们对其采用较小的学习率。因此，Adagrad非常适合处理稀疏数据。

之前的方法中，我们对于所有的参数\(\boldsymbol{\theta}\)，都是用相同的学习速率η。而在Adagrade算法中，对于每一个维度的参数\({\theta}_i\)，采用不同的学习速率。我们先看看\({\theta}_i\)每一个维度的更新过程，然后再把它向量化。简单来看，我们使用\(\boldsymbol{g_t}\)来表示t时刻的梯度向量，\(g_{t,i}\)表示某一维度参数\({\theta}_i\)在t时刻的偏导数。 \[g_{t,i}=\frac{{\partial}J(\boldsymbol{\theta_t)}}{d\theta_{t,i}}\] 对于一般SGD算法，每一个周期t内，\(\theta_{i}\)在更新是采用相同的学习率：\(\theta_{t+1,i}=\theta_{t,i}-\eta\cdot{g_{t,i}}\). 但是对于Adagrad算法，学习率的更新的规则如下所示： \[\theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{G_{t,ii}}+\epsilon}\cdot g_{t,i}\] 其中，\(\boldsymbol{G_t}\)是d*d的对角矩阵，其中元素\(G_{t,ii}\)表示表示之前此维度偏导数的平方和。而\(\epsilon\)的存在是为了防止分母为0，一般取值为1e-8.有意思的是，如果没有平方根这个算法的效果会很差。 由于参数\(G_t\)包含过去梯度的平方和，我们可以向量化这个表达式： \[\boldsymbol{\theta_{t+1}}=\boldsymbol{\theta_{t}}-\frac{\eta}{\sqrt{\boldsymbol{G_{t}}+\epsilon\cdot\boldsymbol{I}}}\odot\boldsymbol{g_{t}}\] 其中，\(\odot\)表示矩阵和向量的积。这样随着矩阵\(\boldsymbol{G_t}\)元素逐渐变大，学习率η会逐渐减少。Adagrad算法最大的问题在于：由于每增加一个正项，在整个训练过程中，累加的和会持续增长。这会导致学习率变小以至于最终变得无限小，在学习率无限小时，Adagrad算法将无法取得额外的信息，导致算法停止。尤其是初始值的梯度很大，导致算法提前收敛。接下来的算法旨在解决这个不足。

Adagrad based MBGD
图1 Adagrad效果(batch=5)Adagrad算法提前停止

RMSprop(均方根传播)

RMSprop算法对学习率的自适应做出了修改。之前Adagrad算法中，学习率是一只下降的，为了避免过早收敛，Geoff Hinton 提出了一种新的学习率自动更新方式，类似TCP协议中平滑计算RTT的方式： \[TCP的平均RTT : SRTT = \alpha \times SRTT + (1-\alpha)\times RTT\] \[RMSprop 学习率自适应参数: E[g^2]_t = \gamma E[g^2]_{t-1} + (1-\gamma)g^2_t\] 通常，\(\gamma\)取0.9，基础学习率\(\eta\)取0.001。我在实际使用中发现用0.001收敛的速度很慢，可以尝试使用0.2。而且损失函数的曲线明显平滑了许多。\(E[g^2]_{t}\)是0->t时刻梯度的平滑值。综上所述，RMSprop的梯度更新算法为： \[{\Delta}{\theta}_t=-\frac{\eta}{\sqrt{E[g^2]_t+{\epsilon}}}g_t\] 另一个重要的建议是mini-batch的值选区的大一些，否在防止震荡不收敛。

RMSprop based MBGD
图2 RMSprop效果(batch=5)

Adadelta

Adadelta算法是Adagrad算法的拓展,它能够降低Adagrad算法在学习率上单项的过度下降。相对于一直累加过去所有的梯度的平方，Adadelta算法管理了一个窗口,将过去梯度相加的个数固定为\(\omega\)。

但是相较于低效率地存储前\(\omega\)个梯度的平方，“梯度的和”被递归定义为逐渐衰减的之前所有梯度平方的和。这个定义有点像TCP协议中计算RTT的方式： \[E[g^2]_t=\gamma E[g^2]_{t-1}+(1-\gamma)g^2_t\] 在t时刻的实时平均\(E[g^2]_{t}\)只取决于之前的均值和当前的梯度。\(\gamma\)的作用和RMSprop中的类似，一般可以取0.9。为了清楚起见，我们重新写一般SGD算法的参数更新过程： \[{\Delta}{\theta}_t = -{\eta}{\cdot}g_{t,i}\] \[{\theta}_{t+1} = {\theta}_t + {\Delta}{\theta}_t\] 然后，我们再重写下Adagrad更新参数向量的公式： \[\boldsymbol{\theta_{t+1}}=\boldsymbol{\theta_{t}}-\frac{\eta}{\sqrt{\boldsymbol{G_{t}}+\epsilon\cdot\boldsymbol{I}}}\odot\boldsymbol{g_{t}}\] 现在，我们只要把对角矩阵\(G_t\)换成逐渐衰减的梯度平方的均值\({E[g^2]_t}\): \[{\Delta}{\theta}_t=-\frac{\eta}{\sqrt{E[g^2]_t+{\epsilon}}}g_t\] 如果我们认为\({\sqrt{E[g^2]_t+{\epsilon}}}\)近似等于均方根值RMS，也可以用下式表示： \[\Delta\theta_t=-\frac{\eta}{RMS[g]_t}g_t\] 到这里读者一定会很奇怪，这不是RMSprop算法吗？到这里如果把\(\gamma\)设置为0.9，确实和RMSprop算法一样，所以下面才说的Adadelta的独创。

我们看到目前的部分还存在两个明显问题，第一超参数学习率\(\eta\)还得手动设置；第二表达式的量纲不统一。我们假设\(\theta\)的单位是\(x\)。那么BGD、SGD、Momentum、NAG的量纲就是\(1/x\)。 \[\Delta\theta单位\propto \boldsymbol{g}某一维度单位\propto\frac{\partial{f}}{\partial{\theta_i}}\propto\frac{1}{x}\] 而Adagrad的\(\Delta\theta\)是无量纲数。如果我们想要获得匹配的量纲，必须使用二阶信息例如使用Hessian信息（或其他近似）的牛顿法： \[\Delta\theta单位\propto \frac{\boldsymbol{g}}{\boldsymbol{H}}\propto\frac{\frac{\partial{f}}{\partial{\theta_i}}}{\frac{\partial^2f}{\partial{\theta^2}}}\propto{x}\] 我们知道二阶的牛顿是正确的（这点先不去证明，反正是对的），但是二阶信息的计算量大大增加了，所以我们考虑如下变化： \[\Delta\theta\propto\frac{\frac{\partial{f}}{\partial{\theta_i}}}{\frac{\partial^2f}{\partial{\theta^2}}}\Rightarrow\frac{\Delta\theta}{{\frac{\partial{f}}{\partial{\theta_i}}}}\propto\frac{1}{\frac{\partial^2f}{\partial{\theta^2}}}\propto\frac{1}{\boldsymbol{{H}}}\propto{x^2}\] 再根据： \[\frac{1}{\boldsymbol{H}}\cdot\boldsymbol{g}\propto{x}\] \(\boldsymbol{g}\)即为当前梯度，分母中的\(\frac{\partial{f}}{\partial{\theta_i}}\)就是\(RMS[g]_t\)。关键分子还缺少一个\(\Delta\theta\)。Adadelta算法使用了平滑的均方根值\(RMS[\Delta\theta]_{t-1}\)来作为分子代替\(\eta\)，即： \[\Delta\theta_t=-\frac{RMS[\Delta\theta]_{t-1}}{RMS[g]_t}g_t\] \[其中：RMS[\Delta \theta]_{t} = \sqrt{E[\Delta \theta^2]_t + \epsilon}\] \[其中：E[\Delta \theta^2]_t = \gamma E[\Delta \theta^2]_{t-1} + (1 - \gamma) \Delta \theta^2_t\] 这样，Adadelta算法不用再设置超参数学习率，量纲也得到了统一。 Adadelta based MBGD
图3 RMSprop效果(batch=5)

Adam

自适应矩算法（Adaptive monent），是一种对随机目标函数执行一阶梯度优化的算法。其主要利用了自适应性低阶矩估计。Adam 算法很容易实现，并且有很高的计算效率和较低的内存需求。Adam 算法梯度的对角缩放（diagonal rescaling）具有不变性，因此很适合求解带有大规模数据或参数的问题。该算法同样适用于解决大噪声和稀疏梯度的非稳态（non-stationary）问题。超参数可以很直观地解释，并只需要少量调整。

Adam算法的核心更新规律是： \[\theta_{t+1} = \theta_t-\frac{\eta}{\sqrt{\hat v_t}+\epsilon}\hat m_t\] 和过去一样，\(\eta\)是学习率，\(\hat m_t\)是梯度的一阶矩，\(\hat v_t\)是梯度的二阶矩。我们用\(g_t\)表示t时刻的梯度。那么一阶矩\(\hat m_t\)和二阶矩\(\hat v_t\)分别可以指数移动平均表示： \[m_t \leftarrow \beta_1\cdot m_{t-1}+(1-\beta_1)\cdot g_t\] \[v_t \leftarrow \beta_2\cdot v_{t-1}+(1-\beta_2)\cdot g_t^2\] 但是，再初始的时候，一阶矩\(m_0\)和\(v_0\)都是从0开始，因此矩估计会偏向0（因为\(1-\beta\)接近0，所以初始阶段矩大约都接近0），因此我们在初始阶段需要用它除以一个小数： \[\hat m_t = \frac{m_t}{1-\beta_1^t}\] \[\hat v_t = \frac{v_t}{1-\beta_2^t}\] t表示参数\(\beta_1\)、\(\beta_2\)的t次方，在编程中表示t次迭代，这样在最开始的时候\(1-\beta\)是一个小数，可以抵消最开始移动平均矩很小的缺点，随着迭代次数t增加，\(1-\beta^t\)逐渐趋近于1，实际的移动平均矩会逐渐占据更新过程的主导权。 论文作者建议超参数取值：\(\eta=0.001,\beta_1=0.9,\beta_2=0.999,\epsilon=10^{-8}\)。

我自己的实验到这里速度很慢了，根本到不了一个理想值

AdaMax

Adamax是Adam的一种变体，此方法对学习率的上限提供了一个更简单的范围。从Adam算法可以算是二范数的比较，如果我们把二范数变成无穷范数，那么： \[v_t \leftarrow \beta_2^p\cdot v_{t-1}+(1-\beta_2^p)\cdot g_t^p \\ where\quad p\rightarrow\infty\] 为了防止混淆，我们用\(u_t\)代替\(v_t\),通过无穷范数是最大值性质，我们可以推得： \[u_t = max(\beta_2\cdot u_{t-1},|g_t|)\] 相应的，更新公式为： \[\theta_{t+1} = \theta_{t} - \dfrac{\eta}{u_t} \hat{m}_t\] 其中，\(\eta = 0.002,\beta_1=0.9,\beta_2=0.999\)。

Nadam

Nadam可以看作是Nesterov和Adam方法的结合。Nadam对学习率有了更强的约束，同时对梯度的更新也有更直接的影响。一般而言，在想使用带动量的RMSprop，或者Adam的地方，大多可以使用Nadam取得更好的效果。

AMSGrad

Lookahead(新优化算法)

算法可视化图

优化器选择

那么，我们应该选择使用哪种优化算法呢？如果输入数据是稀疏的，选择任一自适应学习率算法可能会得到最好的结果。选用这类算法的另一个好处是无需调整学习率，选用默认值就可能达到最好的结果。

总的来说，RMSprop是Adagrad的扩展形式，用于处理在Adagrad中急速递减的学习率。RMSprop与Adadelta相同，所不同的是Adadelta在更新规则中使用参数的均方根进行更新。最后，Adam是将偏差校正和动量加入到RMSprop中。在这样的情况下，RMSprop、Adadelta和Adam是很相似的算法并且在相似的环境中性能都不错。Kingma等人[9]指出在优化后期由于梯度变得越来越稀疏，偏差校正能够帮助Adam微弱地胜过RMSprop。综合看来，Adam可能是最佳的选择。

有趣的是，最近许多论文中采用不带动量的SGD和一种简单的学习率的退火策略。已表明，通常SGD能够找到最小值点，但是比其他优化的SGD花费更多的时间，与其他算法相比，SGD更加依赖鲁棒的初始化和退火策略，同时，SGD可能会陷入鞍点，而不是局部极小值点。因此，如果你关心的是快速收敛和训练一个深层的或者复杂的神经网络，你应该选择一个自适应学习率的方法。

并行与分布式SGD

当存在大量的大规模数据和廉价的集群时，利用分布式SGD来加速是一个显然的选择。SGD本身有固有的顺序：一步一步，我们进一步进展到最小。SGD提供了良好的收敛性，但SGD的运行缓慢，特别是对于大型数据集。相反，SGD异步运行速度更快，但客户端之间非最理想的通信会导致差的收敛。此外，我们也可以在一台机器上并行SGD，这样就无需大的计算集群。以下是已经提出的优化的并行和分布式的SGD的算法和框架。

Hogwild

Niu等人[14]提出称为Hogwild!的更新机制，Hogwild!允许在多个CPU上并行执行SGD更新。在无需对参数加锁的情况下，处理器可以访问共享的内存。这种方法只适用于稀疏的输入数据，因为每一次更新只会修改一部分参数。在这种情况下，该更新策略几乎可以达到一个最优的收敛速率，因为CPU之间不可能重写有用的信息。

Downpour_SGD

Downpour SGD是SGD的一种异步的变形形式，在Google，Dean等人[6]在他们的DistBelief框架（TensorFlow的前身）中使用了该方法。Downpour SGD在训练集的子集上并行运行多个模型的副本。这些模型将各自的更新发送给一个参数服务器，参数服务器跨越了多台机器。每一台机器负责存储和更新模型的一部分参数。然而，因为副本之间是彼此不互相通信的，即通过共享权重或者更新，因此可能会导致参数发散而不利于收敛。

Delay-tolerant_Algorithms_for_SGD

通过容忍延迟算法的开发，McMahan和Streeter[11]将AdaGraad扩展成并行的模式，该方法不仅适应于历史梯度，同时适应于更新延迟。该方法已经在实践中被证实是有效的。

TensorFlow

TensorFlow[1]是Google近期开源的框架，该框架用于实现和部署大规模机器学习模型。TensorFlow是基于DistBelief开发，同时TensorFlow已经在内部用来在大量移动设备和大规模分布式系统的执行计算。在2016年4月发布的分布式版本依赖于图计算，图计算即是对每一个设备将图划分成多个子图，同时，通过发送、接收节点对完成节点之间的通信。

Elastic_Averaging_SGD

Zhang等人[22]提出的弹性平均SGD（Elastic Averaging SGD，EASGD）连接了异步SGD的参数客户端和一个弹性力，即参数服务器存储的一个中心变量。EASGD使得局部变量能够从中心变量震荡得更远，这在理论上使得在参数空间中能够得到更多的探索。经验表明这种增强的探索能力通过发现新的局部最优点，能够提高整体的性能

优化SGD的其他策略

最后，我们介绍可以与前面提及到的任一算法配合使用的其他的一些策略，以进一步提高SGD的性能。对于其他的一些常用技巧的概述可以参见[10]。

数据集的洗牌和课程学习

总的来说，我们希望避免向我们的模型中以一定意义的顺序提供训练数据，因为这样会使得优化算法产生偏差。因此，在每一轮迭代后对训练数据洗牌是一个不错的主意。

另一方面，在很多情况下，我们是逐步解决问题的，而将训练集按照某个有意义的顺序排列会提高模型的性能和SGD的收敛性，如何将训练集建立一个有意义的排列被称为课程学习[3]。

Zaremba and Sutskever[20]只能使用课程学习训练LSTM来评估简单程序，并表明组合或混合策略比单一的策略更好，通过增加难度来排列示例。

批量归一化

为了便于学习，我们通常用0均值和单位方差初始化我们的参数的初始值来归一化。 随着不断训练，参数得到不同的程度的更新，我们失去了这种归一化，随着网络变得越来越深，这种现象会降低训练速度，且放大参数变化。

批量归一化[8]在每次小批量数据反向传播之后重新对参数进行0均值单位方差标准化。通过将模型架构的一部分归一化，我们能够使用更高的学习率，更少关注初始化参数。批量归一化还充当正则化的作用，减少（有时甚至消除）Dropout的必要性。

Early_stopping

如Geoff Hinton所说：“Early Stopping是美丽好免费午餐”（NIPS 2015 Tutorial slides）。你因此必须在训练的过程中时常在验证集上监测误差，在验证集上如果损失函数不再显著地降低，那么应该提前结束训练。

梯度噪音

Neelakantan等人[12]在每个梯度更新中增加满足高斯分布\(N(0,σ^2_t)\)的噪音： \[g_{t,i}=g_{t,i}+N(0,σ_t^2)\] 高斯分布的方差需要根据如下的策略退火： \[σ_t^2=\frac{η}{(1+t)^γ}\] 他们指出增加了噪音，使得网络对不好的初始化更加鲁棒，同时对深层的和复杂的网络的训练特别有益。他们猜测增加的噪音使得模型更优机会逃离当前的局部最优点，以发现新的局部最优点，这在更深层的模型中更加常见。

总结

在这篇博客文章中，我们初步研究了梯度下降的三个变形形式，其中，小批量梯度下降是最受欢迎的。 然后我们研究了最常用于优化SGD的算法：动量法，Nesterov加速梯度，Adagrad，Adadelta，RMSprop，Adam以及不同的优化异步SGD的算法。 最后，我们已经考虑其他一些改善SGD的策略，如洗牌和课程学习，批量归一化和early stopping。