【译】梯度下降优化算法概览（gradient descent o

2019-11-21 本文已影响0人 ce0b74704937

之前一直想总结一下深度学习中常用的梯度下降算法的，后来发现有人做了，那好吧，直接翻译吧。

一、变量的更新方法

1.1 Batch gradient descent

这种变量的更新方法是利用整个数据集的数据，也就是一个batch来计算出损失函数的梯度，进而来更新网络中的参数 $\theta$ ，公式如下：
$\theta = \theta -\eta\cdot\nabla_{\theta}J(\theta)$
因为这种更新方法，我们更新一次参数需要对整个数据集进行计算，所以更新一次参数的速度很慢。而且这种方式也不允许我们进行线上更新，比如随时有新的图片输入的情况。

这种batch的梯度下降更新方式的伪代码如下所示：

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

上面表示的过程是对于预先定义的迭代次数nb_epochs，先通过损失函数和整个数据集计算出各个参数的梯度值，然后利用所得的梯度和预定义学习率更新参数。batch gradient descent能保证在凸损失函数曲面取得全局最优解，对于非凸曲面能取得局部最优解。

1.2 Stochastic gradient descent

这个方法叫做随机梯度下降，简称SGD。该方法是为一个样例（样例包含训练样本 $x^{(i)}$ 和标注 $y^{(i)}$ ）来更新一次参数，如下式所示：
$\theta = \theta -\eta\cdot\nabla_{\theta}J(\theta; x^{(i)}, y^{(i)})$
因为该更新方法是对每一个样例而言的，所以参数更新比Batch的方式快。但这种方式可能会导致参数更新波动较大，如下图所示。

1.png

相对于Batch方式，SGD的更新方式，波动大可能能使得梯度下降到更好的另一个局部最优解，但另一方面来讲，SGD的更新可能导致梯度一直在局部最优解附近波动。然而，训练时不断的缓慢减小学习率，SGD能和Batch方法一样，在凸损失函数曲面取得全局最优解，对于非凸曲面能取得局部最优解。

SGD的伪代码如下所示：

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

1.3 Mini-batch gradient descent

这种更新方式是目前用的最多的一种更新方式，如下式所示：
$\theta = \theta -\eta\cdot\nabla_{\theta}J(\theta; x^{(i:i+n)}, y^{(i:i+n)})$
这种方式有两个优点：
a) 相对于SGD来说可以减小参数更新的波动
b) 能够利用矩阵操作，来提高参数的更新效率
一般minibatch的值在50～256之间选择，不同的应用选择不同，这个也是一个超参数。

Mini-batch gradient descent的伪代码如下所示：
for i in range(nb_epochs):
np.random.shuffle(data)
for batch in get_batches(data, batch_size):
params_grad = evaluate_gradient(loss_function, batch, params)
params = params - learning_rate * params_grad

二、挑战

上述的方法不一定能保证好的收敛性，而且还有下面一些挑战：

learning rate这个超参数不好选择。太小收敛速度慢，太大容易在局部最优附近波动。
learning rate的变化规则不好定。预先定好的规则不能很好的适应数据集的特征。
同一个learning rate对所有的参数进行更新。不同的参数可能需要更新的步长不一致，但是上述方法都是按照相同的步长更新。
对于非凸损失函数，参数的更新不能很好的使得梯度更新跳出高纬函数的多个局部最优，甚至是遇到某些鞍点（可以想象一个马鞍的形状，一个纬度坡度是上升的，其他的坡度是下降的）的区域，不能很快的跳出鞍点。

三、梯度下降优化算法

为了解决上述一些问题，下面介绍一些常用的优化算法。

3.1 Momentum

SGD容易在一些类似于沟壑的曲面上震荡，可以想象一个小球在一个沟上滑动，这个沟壑一个纬度比其他纬度更陡，SGD更新方法在更陡的坡上震荡较大，导致算法更新到达局部最优的时间较长。为了解决这种问题，Momentum梯度优化算法提出来了，可以想象在坡度更不陡的方向上给小球加上一个动量，使得小球更快的跑到局部最优点。如下图所示

2.png

Momentum是SGD的一种改进方法，该算法新增一个 $\gamma$ 的超参数，根据以前的动量和新的梯度来计算新的动量，公式如下所示：
$v_t = \gamma v_{t-1} + \eta\cdot\nabla_{\theta}J(\theta)$
$\theta = \theta -v_t$
通常 $\gamma$ 设置为0.9左右的数值。
类似与一个球从u形山谷形状的坡度滚下，它向最低点方向的速度是越来越快的，上述中的参数 $v_t$ 就会使得同一个方向的梯度叠加，不断变化方向的梯度会相互抵消，所以可以使得梯度可以更快的收敛。

3.2 Nesterov accelerated gradient

假象一个球让它没有指导的自由的沿着山坡滚到山谷，这样做法非常的不安全。我们希望有一个更为聪明的小球，当它快要滚到山谷的时候，它速度减慢。

Nesterov accelerated gradient下面简称NAG就是这样一种梯度更新算法。在上述的momentum算法中，我们会使用 $\gamma v_{t-1}$ 来更新参数，这样就可以得到新的参数位置 $\theta-\gamma v_{t-1}$ 。下面我们可以通过即将得到的新参数位置先一步的得到我们要更新的参数大小，如下式所示：
$v_t=\gamma v_{t-1}+\eta\nabla_{\theta}J(\theta-\gamma v_{t-1})$
$\theta=\theta-v_t$
如下图所示，假设我们设 $\gamma$ 为0.9。对于momentum来说，优化器先计算出参数的梯度，如图中的短蓝线所示，然后momentum要更新的动量为图中的长蓝线。对于NAG来说，先计算出梯度，然后指导带更新的动量大小如下图的长灰线所示，根据所得的灰线再计算要修改真正要更新动量的大小和方向，最后得到长的绿色线。通过这种更新方式可以防止参数更新过快的问题，这种算法对RNNs来说有较好的效果。

3.png

3.3 Adagrad

Adagrad是这样的一种更新算法，它对于不同的参数有不同的更新参数，对于频繁更新参数采用小的更新值，不频繁的更新参数采用较大的更新值进行更新。

之前所提到的算法，对于所有参数 $\theta$ 中的每个参数 $\theta_i$ 来说，使用的都是相同的学习率 $\eta$ 来更新的。而Adagrad优化算法，对于t时刻，每个参数 $\theta_i$ 使用的学习率是不同的。为了方便理解，对于每个参数 $\theta_i$ 来解释一下它的原理。下面规定使用符号 $g_{t,i}$ 来表示目标函数对于在t时刻，参数 $\theta_i$ 的梯度值。
$g_{t,i}=\nabla_{\theta_t}J_{\theta_{t,i}}$
对于SGD来说，在在t时刻，参数 $\theta_i$ 的更新方式如下：
$\theta_{t+1,i}={\theta_{t,i}}-\eta\cdot g_{t,i}$
而Adagrad在t时刻对 $\theta_i$ 参数的更新值是更新 $\theta_i$ 过去的梯度来求得的：
$\theta_{t+1,i}={\theta_{t,i}}-\frac{\eta}{\sqrt{G_{t,ii}+\epsilon}}\cdot g_{t,i}$
上式中 $G\in R^{d\times d}$ ，是一个对角矩阵，该矩阵中每个对角线上的元素（i,i）为过去0-t时刻参数 $\theta_i$ 梯度的平方和。 $\epsilon$ 是为了防止除零设置的一个参数，一般设置为1e-8。这个算法还有个有趣的事情，公式中不加入平方根，会导致算法效果不好。
因为 $G_t$ 包含了过去的梯度值的平方，对于所有参数来说，上述公式可以写成矩阵的形式：
$\theta_{t+1}={\theta_{t}}-\frac{\eta}{\sqrt{G_{t}+\epsilon}}\odot g_{t}$
$\odot$ 表示矩阵元素间相乘。

使用Adagrad算法的一个好处就是可以不用手动调节训练率，一般 $\eta$ 默认设置为0.01。
而它也有不太好的地方，因为该算法不断的在分母加过去的梯度平方值，导致随着训练次数的增加，训练的步长越来越小，可能最后模型还没收敛，参数确不怎么更新了。

3.4 Adadelta

Adadelta是Adagrad的升级版，它的提出是为了解决Adagrad梯度不停减小的问题。
Adadelta采用的不是将过去所有的梯度平方相加，而是引入了指数平均来做的。
$E[g^2]_t=\gamma E[g^2]_{t-1}+(1-\gamma)g^2_{t}$
这里 $\gamma$ 和momentum里设置的一样，为0.9。

下面为了更好理解，先把SGD公式抄过来
$\Delta\theta_{t}=-\eta\cdot g_{t,i}$
$\theta_{t+1}=\theta_t+\Delta\theta_{t}$
对于Adagrad来说是过去所有梯度平方和
$\Delta\theta_{t}=-\frac{\eta}{\sqrt{G_{t}+\epsilon}}\odot g_{t}$
现在将分母替换为指数平均数得到下式
$\Delta\theta_{t}=-\frac{\eta}{\sqrt{E[g^2]+\epsilon}}g_{t}$
上式中因为分母为梯度的均方根形式，所以可以简写为
$\Delta\theta_{t}=-\frac{\eta}{RME[g]_t}g_{t}$

Adadelta作者发现上式的更新（也包括SGD，momentum，Adagrad）中， $\Delta$ 值和待更新的参数假设的单位（hypothetical units）不同(这里的单位是假设的，如果有单位的话，adagrad的更新参数的单位分子和分母抵消了)，为了解决这个问题，文章又引入下面一个指数平均：
$E[\Delta \theta^2]_t=\gamma E[\Delta\theta^2]_{t-1}+(1-\gamma)\Delta\theta^2_{t}$
上式的均方根误差的形式如下
$RMS[\Delta\theta]_t=\sqrt{E[\Delta\theta^2]_t+\epsilon}$
因为在求 $\Delta\theta_t$ 时， $RMS[\Delta\theta]_t$ 还没求出来，所以使用 $\Delta\theta_{t-1}$ 作为代替，参数的更新规则如下：
$\Delta\theta_{t}=-\frac{RME[\Delta\theta]_{t-1}}{RME[g]_t}g_{t}$
$\theta_{t+1}=\theta_t+\Delta\theta_{t}$
从上面公式可以看出，使用Adadelta不需要设置学习率。

3.5 RMSProp

RMSProp通过文章而公布的一个算法，它是在Geoff Hinton课堂上提出的算法。

和Adadelta一样，RMSProp也是Adagrad一个改进版本，只是它和Adadelta是独立提出来的。它的公式其实上面已经介绍过了，下面再抄一遍：
$E[g^2]_t=\gamma E[g^2]_{t-1}+(1-\gamma)g^2_{t}$
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{E[g^2]+\epsilon}}g_{t}$
一般的 $\gamma$ 设置为0.9， $\eta$ 设置为0.001。

3.6 Adam

Adam全称Adaptive Moment Estimation，Adam不仅像Adadelta和RMSprop一样计算过去梯度平方的指数平均值 $v_t$ ，还会计算过去梯度的指数平均值 $m_t$ 。
$m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t$
$v_t=\beta_2 v_{t-1}+(1-\beta_2)g^2_t$
从上式可以看出，当 $m_t$ 和 $v_t$ 初始化为0，且在 $\beta_1$ 和 $\beta_2$ 值接近1的情况下，这两个指数平均值一直在0附近。
Adam为了消除这种影响，使用下面两式来代替上述两个momentum：
$\hat{m_t}=\frac{m_t}{1-\beta^t_1}$
$\hat{v_t}=\frac{v_t}{1-\beta^t_2}$
然后类似与Adadelta和RMSprop，Adam参数更新算法如下所示：
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat v_t}+\epsilon}\hat m_t$
通常，上式中 $\beta_1$ 设为0.9， $\beta_2$ 设为0.999， $\epsilon$ 设为 $10^{-8}$

3.7 AdaMax

不同于Adam，在计算 $v_t$ 时使用的是过去的梯度平方也就是 $l_2$ norm，更为广义的可以计算过去梯度的 $l_p$ norm。
$v_t=\beta^p_2 v_{t-1}+(1-\beta^p_2)|g_t|^p$

AdaMax就是将之前的1范数和2范数替换成了无穷范数，下面为了防止符号与之前的符号混淆，使用 $u_t$ 代替 $v_t$ :
$u_t=\beta^{\infty}_2 u_{t-1}+(1-\beta^{\infty}_2)|g_t|^{\infty}\\=max(\beta_2\cdot u_{t-1}, |g_t|)$
于是，AdaMax的参数更新规则为
$\theta_{t+1}=\theta_t-\frac{\eta}{u_t}\hat{m_t}$
通常， $\eta$ 设为0.002， $\beta_1$ 设为0.9， $\beta_2$ 设为0.999。

4.8 Nadam

因为Adam优化器可以看作RMSprop与momentum的结合，而NAG又是来源于原始的momentum，那Nadam可以看作是将NAG和Adam结合的一个算法。

为了使公式能和Adam统一，下面momentum项用 $m_t$ 表示。下面先来用新的符号重写一下momentum算法：
$g_t=\nabla\theta_t J(\theta_t)$
$m_t = \gamma m_{t-1}+\eta g_t$
$\theta_{t+1}=\theta_t-m_t$
将上面三个式子合并得
$\theta_{t+1}=\theta_t-(\gamma m_{t-1}+\eta g_t)$
而NAG算法可以表示如下：
$g_t=\nabla\theta_t J(\theta_t-\gamma m_{t-1})$
$m_t = \gamma m_{t-1}+\eta g_t$
$\theta_{t+1}=\theta_t-m_t$
下面Dozat提出将NAG做一些修改，不同于原来的NAG算法，先更新梯度，然后更新参数。这里直接通过look-ahead momentum直接更新参数：
$g_t=\nabla\theta_t J(\theta_t)$
$m_t = \gamma m_{t-1}+\eta g_t$
$\theta_{t+1}=\theta_t-(\gamma m_t+\eta g_t)$
从上式可以看出，不同于以往是通过 $m_{t-1}$ 来更新参数，这里是使用 $m_{t}$ 来更新参数。

为了将NAG应用到Adam中，先抄写Adam公式：
$m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t$
$v_t=\beta_2 v_{t-1}+(1-\beta_2)g^2_t$
$\hat{m_t}=\frac{m_t}{1-\beta^t_1}$
$\hat{v_t}=\frac{v_t}{1-\beta^t_2}$
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat v_t}+\epsilon}\hat m_t$
将 $\hat m_t$ 展开得到下式：
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat v_t}+\epsilon}(\frac{\beta_1m_{t-1}}{1-\beta^t_1}+\frac{(1-\beta_1)g_t}{1-\beta^t_1})$
上式又可写为：
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat v_t}+\epsilon}(\beta_1\hat{m}_{t-1}+\frac{(1-\beta_1)g_t}{1-\beta^t_1})$
这个式子与上面写的momentum式子很像，类似于将momentum做一个NAG的优化，得到Nadam。
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat v_t}+\epsilon}(\beta_1\hat{m}_t+\frac{(1-\beta_1)g_t}{1-\beta^t_1})$