常见梯度下降算法学习

本文介绍几种常见的梯度下降算法，以及基于参数服务器的三种训练模式。

梯度下降

梯度下降是用来计算函数最小值的，它的直观思路就是，假设我们在在山顶，但是我们不知道如何最快下山，那么我们就一步一步走，每一步按当前最陡峭的方向前进，直到走到我们认为是山脚下的地方。为什么是“认为是山脚下”呢，因为我们可能走到半山腰的低处，认为它是山脚下。

梯度下降不一定能够找到全局的最优解，有可能是局部最优解。不过如果损失函数是凸函数，梯度下降法得到的解就是全局最优解了。

梯度下降通过不断朝目标函数梯度负方向更新参数，从而最小化目标函数  的一种方式，其中  是模型参数。

梯度下降的停止条件通常是：

1. 设置了固定的迭代轮数，达到一定轮数后退出
2. 当两次迭代的目标函数之差小于某一阈值

几种梯度下降算法框架

通常有三种形式的梯度下降算法框架：

Batch Gradient Descent

Batch Gradient Descent也叫作批梯度下降。它每次对整个训练集计算参数θ的梯度:

其中η是学习率。由于每次更新都需要计算整个训练集的梯度，因此速度较慢。如果训练集较大而内存装不下，则该方法也行不通了。

Stochastic Gradient Descent

Stochastic Gradient Descent也叫作随机梯度下降，简称为SGD。它是对每条样本更新一次参数：

SGD通常来说更快，并可以用来做在线训练（Online Learning，使用实时产生的样本做训练）。SGD的随机性也有助于找到更优的局部最优点。

Mini-batch Gradient Descent

Mini-batch Gradient Descent也叫作小批量梯度下降，它是上面两种方式的折中，也是应用最广的方法。Mini-batch方法每次从训练集中选取n个样本来更新参数。

挑战

接下来让我们看一下实际应用中面临的一些挑战：

1. 选择一个合适的学习率(learning rate)很难， 过小则收敛的慢，过大则导致损失函数的值在最小值附近左右波动，甚至发散。
2. 所有特征是否一定采用同样的学习率。
3. 对于非凸的目标函数，如何尽量避免陷入局部最小值。
4. 如果是动态调整学习率或者设置一个阈值，通常都是事先确定好的规则，因此可能不适用所有数据集。

对于第3点，这里提一下模拟退火。当梯度下降到达局部最优时，依然有一定概率跳出局部最优值，经过几次类似的移动后，也许会到达一个更优的解。若没有找到更加优秀的解，则次数达到限制后结束算法。

我们看一个比喻，帮助理解。一群兔子为了找出地球上最高的山，有两个办法：

1. 兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法(或局部搜索法)，它不能保证局部最优值就是全局最优值。
2. 兔子喝醉了，它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高点跳去。这就是模拟退火。

模拟退火算法其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。

下文也列出了几种常见的梯度下降算法，用来解决上面的某些问题。

Momentum（动量）

Momentum方法可以加速SGD。SGD通常在穿过峡谷（切面在某个维度比其他维度陡的多）的时候发生振荡现象，经常在局部极小值周围出现，SGD会沿着峡谷的斜坡缓慢的朝局部最优走。

为了解决这个问题，可以引入动量，加速朝局部最优走的速度。然后更新  

首先计算动量，加上动量项就像从山顶滚下一个球，求往下滚的时候累积了前面的动量(动量不断增加)，因此速度变得越来越快：

然后更新θ：

其中momentum项γ 一般设置成0.9。可以看出该项对于那些当前的梯度方向与上一次梯度方向相同的参数进行加强，即这些方向上更快了。

对于那些当前的梯度方向与上一次梯度方向不同的参数进行削减， 即这些方向上减慢了。因此可以获得更快的收敛速度，并在相关方向进行加速从而抑制振荡。

Nesterov Accelerated Gradient

从山顶往下滚的球会盲目地选择斜坡。更好的方式应该是在遇到倾斜向上之前应该减慢速度。因此如果提前的考虑了后一步的情况，就可以阻止过快更新来提高响应性：

然后更新θ ：

通过以上两种方法，我们可以做到动态调整参数更新，从而加快SGD。接下来看如何针对不同的参数，根据参数的重要程度来分别调整更新的幅度。

Adagrad

Adagrad针对每个参数动态调整学习率，对于频繁出现的特征（非稀疏的特征）进行较小的更新， 而对不频繁出现的特征（稀疏特征）。因此该方法适合处理稀疏特征的数据。

现在是针对参数向量θ 的每个分量单独更新，设第t+1次更新时， i第个分量为 ，则有：

其中 ,  。式子中的参数ε是平滑项，避免出现分母为0的情况，可以取作1e−8。

Adagrad的一个好处就是学习率一般不用再人为调整了，参数η一般取作0.01。它的缺点就是会逐渐增大，使得学习率逐渐减小，最终达到非常小的值。下面的Adadelta就是解决该问题的。

Adadelta

Adadelta是Adagrad的扩展，为了避免学习率一直单调递减。Adagrad使用所有历史的梯度的平方和，而Adadelta则是固定为前w个梯度。

第t+1次更新时，的计算方法如下：

参数更新的公式为：

以上式子有个问题是更新的单位与前几种方法一样，都是与 θ（可以假设参数单位是m，梯度即 ，然后带入式子看一下），因此改写E为如下式子, 即不再是梯度的平方和，而是参数的平方和：

记 ， 以及 ，那么更新参数的公式如下：

然后更新θ ：  

可以看出Adadelta不需要设置学习率了。

Adam

可以认为，Adam结合了Momentum以及每个参数单独更新，并且解决了由于起始时参数初始化为0而且Momentum中的 γ (下面公式的  β1、 β2 )通常设置的较大，使得参数朝0偏倚的比较厉害的问题。

其中是第t次更新后的参数m，下面的是第t次更新后的参数梯度平方和。

如下这样一除，也就解决了上面说的起始一段时间参数趋于0的情况：

那么更新参数公式为：

通常设置β1为0.9，β20.999，ε 为1e-8.

我们注意到，如果使用Adam算法，需要存储的参数 + 优化器状态（ 、  ）的总量是参数大小的三倍。一种实践是将稀疏参数embedding的优化器状态压缩到一维（比如取平均），即每个embedding的优化器状态只有一个和，这是一种工程优化和算法效果的折中。对于Adagrad算法的工程优化也是类似。

介绍到这里，基本上常见的梯度下降算法就掌握啦。我们进一步看看，在参数服务器架构中的三种训练模式，参数是在什么时候更新。

训练方式

在基于参数服务器的训练框架中，通常采用mini-batch的训练方式来更新梯度。对于异步的控制，有三种方式：

1. BSP（Bulk Synchronous Parallel） 在每一轮迭代中都需要等待所有的worker计算完成，得到所有worker平均梯度后更新参数，优点是每一轮迭代收敛质量高，缺点是存在慢节点的问题
2. SSP（Stalness Synchronous Parallel） 允许一定程度的worker进度不一致，但这个不一致有一个上限，我们称之为 staleness 值， 即最快的worker最多领先最慢的worker staleness 轮迭代。优点是一定程度减少了worker之间的等待时间，缺点是每一轮迭代的收敛质量不如BSP，达到同样的收敛效果可能需要更多轮的迭代。
3. ASP（Asynchronous Parallel） worker之间完全不用相互等待，先完成的worker，直接把梯度异步发送给server，由server异步更新参数，worker此时继续下一轮的训练。优点是速度快，缺点是适用性差，在一些情况下并不能保证收敛性。

这里贴一张腾讯angel的三种训练方式：

在并行训练中，常见的Hogwild与DownpourSGD就是ASP的模式，即全异步的进行深度学习训练，其中Hogwild是单机多线程，DownpourSGD是多机多线程。也就是说，DownpourSGD可以看成多机的Hogwild。

另外在实际训练中，除了不同的梯度下降算法，还有很多可以提高训练效果的方法，例如对数据做shuffle从而打破样本时间顺序依赖，以及达到一定的迭代轮数后做early stop等方法。

文章转载自公众号：深度学习笔记