梯度下降综述

前言

梯度下降算法现在变的越来越流行，但是对于使用者来说，它的优化过程变的越来越黑盒。本文我们介绍下不通梯度下降算法的习性，使得我们能够更好的使用它们。本人每次复习这篇论文，或多或少都有一些收获，基础学习扎实了，后面的使用才会得心应手。

简介

梯度下降算法，不管在机器学习，还是在神经网络中，都是很常见的优化算法。所以不通的深度学习框架实现了各种不通的梯度下降算法，但是各种算法的优势和劣势对于普通的使用者来说是一个黑盒。

本文就是基于此来详细解释各种梯度算法的不同点，以及它们的优势和劣势。

梯度算法简单来说就是:
优化目标函数$J(\theta)$, 使得目标函数达到最小值时，求解得到参数$\theta \in R^d$

它的方式是首先求解梯度 $\nabla_{\theta} J(\theta)$, 然后每次往负梯度方向迭代一步，更新参数$\theta$.

01:

各种梯度下降

目前常用的有3种梯度下降，主要是根据计算梯度时使用的数据量。

batch gradient descent(BGD, 批量梯度下降)

每次计算梯度的时候都是使用全部的数据:
http://latex.codecogs.com/svg.latex?\begin{bmatrix}1&x&x^2\1&y&y2\1&z&z^2\\end{bmatrix}

http://latex.codecogs.com/svg.latex?a

这里可以看到每一步的参数 $\theta$ 更新都需要计算全部的数据，

所以BGD在数据量特别大的时候是很难处理的，同时也不能做到online更新model。
BGD在凸优化里面能够保证达到全局的最优点，如果在非凸优化里面能够达到局部最优点。

Stochastic gradient descent(SGD, 随机梯度下降)

SGD每次接收到一个训练数据$(x^{i}, y^{i})$时，都需要计算梯度，
然后更新模型参数，粒度非常小。
$\theta = \theta - \eta . \nabla_{\theta}J(\theta;x^{i};y{i})$

SGD在大数据应用上效果非常好，一方面它避免像BGD一样冗余的计算，因为每一次计算它都会去更新参数，所以收敛速度会快很多，而且它是实时更新参数，所以可以用作online 训练，但是SGD在训练的时候，loss的波动可能很大。

BGD最终会收敛到最优点，相对来说SGD是有波动的，一方面，它有机会跳出当前的局部最优点；另一方面，它可能会造成过拟合。但是只要保持学习率缓慢下降的情况下，不管在凸优化还是非凸优化上面，SGD和BDG的效果可以等价。

Mini-batch gradient descent(MBGD)

MBGD是 BGD 和SGD的一个折中，它是每一个小批次计算一次梯度，更新一次参数
$$\theta = \theta - \eta . \nabla_{\theta}J(\theta;x^{(i:i+n)};y{(i:i+n)})$$

它的好处

1. 减少参数的更新次数，使得模型更佳稳定。
   2）可以使用矩阵计算的形式，来优化计算速度。
   常见的Mini-batch 大小一般是 50-256，但是和应用有关，比如图像应用的batch小点，nlp任务的batch可以调整大些。

挑战

虽然MBGD还可以，但是它不是凸优化，有些问题需要处理

• 合适的学习率很难选择，太小了迭代慢，太大了很容易波动，甚至发散
• 预设学习率，比如：模拟退火，学习率衰减等，但是这个对数据集需要非常了解
• 对于每一步迭代，所有的参数更新是共享同一学习率的，但是如果我们数据稀疏，或者特征频次很不同，我们不需要更新每一个参数，对较少出现的特征更新幅度较大。
• 在神经网络中优化高度非凸的代价函数的一个挑战是，避免局部的次最优。这个难题不是局部最优点带来的，而是碰到非局部极值点的驻点，在某些维度它的梯度是上升的，在某些维度，它的梯度是下降的。这些鞍点的从每个方向出发，它附近的error值都是一样的，这就使得SGD非常难以从这样的地方迭代出来。

梯度下降优化算法

下面我们介绍多种优化梯度的算法，这里不介绍不适合大数据集和二次的算法。

Momentum(动量，惯性)

SGD在做梯度下降的时候，梯度陡的维度下降的幅度比梯度欢的维度更大，这会导致一个问题，在一个局部最优点的附近，更新的方式是有点类似走“之”字行的缓慢前进。如图a所示，垂直方向的梯度很陡，水平的很缓，这样在更新的时候，往垂直方向的更新粒度大，但是水平方向很缓慢。
[图片上传失败...(image-4dfee6-1511578384244)]

为了解决这个问题，引入Momentum，也就是引入动量来抑制震荡，如图b
$v_t = \gamma v_{t-1} + \eta \nabla_{\theta}J(\theta)$
$\theta=\theta-v_t$
通常$\gamma$设为0.9
它是通过保持上一步的梯度来实现抑制震荡，效果如b所示。

物理上来说，当我们从山上扔一个球，随着球的下落，动量是一直在增加的，
速度也是越来越快的，直到极限速度，$\gamma$代表阻力因子。同样的场景
适合解释参数的更新，如果梯度的方向相同，动量$v_t$是增加的，相反，
动量是降低的，这样就可以起到加速和抑制震荡的效果。

Nesterov accelerated gradient(Nesterov 加速梯度， NAG)

然而，如果一个球任由它自己盲目的沿着斜坡下落，结果是很不理想的，因为球在坡缓地地方下落的慢，在坡陡的地方下落的快，这个和我们迭代参数的理想情况是相反的。我们期望的是在坡陡(梯度大)的地方迭代更慢。

NAG是解决这个问题的一种方式，使用动量对我们的参数本身做一些修正，我们先预估参数应该变成什么样子？

按照惯性前进，我们会有有个参数update 后的预估位置，
它可能是：$\theta-\gamma v_{t-1}$，
然后在这个位置我们计算它的梯度，$\eta \nabla_{\theta}J(\theta-\gamma v_{t-1})$，
这样可以起到加速的作用。
整体的公式：
$$v_t = \gamma v_{t-1} + \eta \nabla_{\theta}J(\theta-\gamma v_{t-1})$$
$$\theta=\theta-v_t$$
[图片上传失败...(image-44a45-1511578384244)]

解释下这个图：
原来梯度的方向：
如果按当前的参数位置$\theta$来计算梯度，它是小的蓝色的向量
然后保持动量$\gamma v_{t-1}$是长的蓝色向量
NAG：
先保持动量走一步：$\gamma v_{t-1}$为棕色的长向量，和长的蓝色向量平行
在该位置的梯度为红色的长向量：$\eta \nabla_{\theta}J(\theta-\gamma v_{t-1})$
修正后的位置为左边绿色向量指定的位置。

这种方式就可以提前修正梯度方向，避免单次走的太快以致偏差太大，起到加速的作用
既然我们可以做到自适应的根据梯度大小来调整迭代的大小来加速计算。
我们也应该做到根据参数的重要性来独立的更新每一个参数。

Adagrad

Adagrad是一种梯度下降的算法：它是通过学习率来作用到参数更新，非频繁更新的参数更新力度大些，相反更新力度小点。
所以这个非常实用于sparse数据，
Dean et al 发现Adagrad在训练大数据集的时候可以极大的提升SGD的鲁棒性，
用Adagrad去训练Glove word Embedding 对于新词或者出现频率低的词效果很好

前面我们对所有的参数$\theta$共享一个学习率，Adagrad对于每个$\theta_i$都会训练出一个对应的学习率。
下面是计算过程：
首先计算参数$\theta_i$在step t的梯度：
$g_{t,i}=\nabla_{\theta_t}J(\theta_{t,i})$

普通的SGD对于每一个参数，更新公式为：
$\theta_{t+1,i}=\theta_{t,i}-\eta.g_{t,i}$

在这里Adagrad 对学习率$\eta$进行修正，这要视基于它过去已经计算过的梯度：
$\theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{G_{t,ii} + \epsilon}}.g_{t,i}$

$G_t \in R^{d x d}$ 是一个对角矩阵，只用对角的$i,i$有数据
$G_{t,ii}=\sum_{0,t} g_{t,i}^2 $
所以这个值会一直越来越大
$\epsilon$是个平滑极小项，避免出现除0的情况，一般设为1e-8.
很奇怪的是，如果不加平方计算，效果很差。

使用Adagrad的一个好处是，不需要很特意的去调整学习率，
只要设置一个初始的$\eta$比如0.01，然后就可以了，模型自己会调整。

它的确定很明显，需要计算累积的梯度平方和，这个值会越来越大，
这回是的步长一段时间后变得很小，这样再训练下去就没有什么意义了。
下面的方法来fix这个缺陷。

Adadelta

Adadelta是Adagrad的扩展，它主要是决绝Adagrad的过度下降学习率。它们的不同是Adagrad累积所有历史的梯度平方，但是Adadelta只是考虑过去一段是时间的梯度平方和。

为了避免每次计算都需要存储历史$w$个梯度，做了一种变种的方式，
有点类似衰减 decay：

$E[g^2]t = \gamma E[g^2]{t-1} + (1-\gamma)g_t^2$
同样$\gamma$可以设置为0.9，我们将整体公式列出来：

SGD 更新参数：
$\Delta \theta_t=-\eta.g_{t,i} $
$\theta_{t+1}=\theta_t + \Delta \theta_t $

Adagrad更新参数的element-wise 方式：
$\Delta \theta_t=-\frac{\eta}{\sqrt{G_{t} + \epsilon}}\bigodot g_{t}$

Adadelta就是将$G_t$改为 $E[g^2]_t $,得到
$\Delta \theta_t=-\frac{\eta}{\sqrt{E[g^2]t + \epsilon}}\bigodot g{t}$

其实 $E[g^2]_t $就是RMS(root mean squared)
$\Delta \theta_t=-\frac{\eta}{RMS(g)t}\bigodot g{t}$$

这个作者提到，像SGD，Momentum, 或者 Adagrad)的更新单元其实不适合Adadelta，
其实即使梯度再大，只要学习率很小，那么参数更新的幅度就很小，所以学习率的调整应该和参数的过去一段时间的调整幅度有关，而不是只是和梯度有关，所以我们引入另外一个累积公式为：

$E[\Delta \theta ^2]t = \gamma E[\Delta \theta ^2]{t-1} + (1-\gamma)\Delta \theta ^2$$
$$RMS[\Delta]_t=\sqrt{E[\Delta\theta^2]_t + \epsilon}$

这里$RMS[\Delta]t$依赖$\Delta \theta_t$是未知的，我们用$RMS[\Delta]{t-1}$近似代替
然后用 $\frac{RMS[\Delta \theta]{t-1}}{RMS[g]{t}}$ 来替代步长$\eta$
物理上可以这么理解：
$\Delta \theta_t = \eta g_t$
$\eta = \frac{\Delta \theta_t}{g_t}$ 然后用$RMS[\Delta]{t-1}$近似$\Delta \theta_t$,用$RMS[g]{t}近似 $g_t$

最终得到：
$\Delta \theta_t=-\frac{RMS[\Delta \theta]{t-1}}{RMS[g]{t}} g_{t}$
$\theta_{t+1}=\theta_t + \Delta \theta_t $

所以用这种算法，我们连初始值都不需要了。

RMSprop

RMSprop是一种非公布的算法，是Hinton提出的
RMSprop 和 Adadelta是独立提出的相同算法，他们都是用来解决Adagrad累积梯度平方和太快的问题：
$E[g^2]t= 0.9 E[g^2]{t-1} + 0.1 g_t^2 $
$\theta_{t+1}=\theta_{t} - \frac{\eta}{\sqrt{E[g^2]_t + \epsilon}}g_t$

建议 $\eta$设置为 0.001

Adam

Adaptive Moment Estimation 是两外一种自适应学习率算法，类似RMSprop 和 Adadelta，Adam还保存过去一段时间的梯度:

$m_t=\beta_1m_{t-1}+(1-\beta)g_t$
$v_t=\beta_2 v_{t-1}+(1-\beta_2)g_t^2$

$v_t$和上面的RMSprop类似，$m_t$是额外需要记忆的东西,
他们分别可以看成是第一动量(平均)，第二动量(方差)，
因为$v_t$和$m_t$都是由0初始化的，Adam的作者观察：
在0附近特别是开始的几步，偏置非常大，特别是衰减率非常小的时候，
$\beta_1和\beta_2是接近1的数字$。
为了修正这个偏置，作者稍微对这两个动量进行修正，得到：
$m_t^1 = \frac{m_t}{1-\beta_1^t}$
$v_t^1 = \frac{v_t}{1-\beta_2^t}$
这里的$\beta_1^t$是$\beta_1的t次方$
然后利用这个$m_t^1$去更新参数：
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{v_t^1} + \epsilon}m_t^1 $
作者建议：$\beta_1=0.9$， $\beta_2=0.999$, $\epsilon=10^{-8}$

原始论文：https://arxiv.org/pdf/1412.6980.pdf
[图片上传失败...(image-acdba3-1511578384244)]

AdaMax

上面提到的$v_t$计算$g_t^2$的时候用的其实是l2范数计算，可以写成形式：
$v_t=\beta_2 v_{t-1}+(1-\beta_2)|g_t|^2$
我们可以定义更加广泛的形式：
$v_t=\beta_2^p v_{t-1} + (1-\beta_2^p)|g_t|p$
这里使用的的是p范数。

这里我们引入一种无穷范数的形式，AdaMax:
$u_t=\beta_2^{\infty}v_{t-1} + (1-\beta_2^\infty)|g_t|\infty$
$=max(\beta_2.v_{t-1}, |g_t|)$

我们用$u_t$来代替Adam的$\sqrt(v_t^1 + \epsilon)$,得到：
$\theta_{t+1}=\theta_t-\frac{\eta}{u_t}m_t^1 $

$u_t$计算的时候取最大值，所有在接近于0的时候不会像Adam一样有这么大的偏置。

Nadam

前面提到，Adam 是RMSprop和动量的结合算法，RMSprop保证学习率会根据最近几步的梯度平方来衰减，这里我们再坐下升级，对动量使用NAG(Nesterov accelerated gradient),
首先我们回顾下动量的更新方式：
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$

$J$是我们的目标函数，$\gamma$是动量的衰减因子，$\eta$是步长，结合起来：
$\theta_{t+1}=\theta_t-\gamma m_{t-1}-\eta g_t$

NAG可以令我们走的更加精确，我们将NAG的特性加入上式得到：
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$

NAG可以做些修改，因为NAG中会迭代动量两次，
一次是计算$g_t$的时候，一次是更新参数$\theta$的时候.修改后也是两次，
只是动量更新两次，一次时上面的第二个式子，预估当前的动量，
然后沿着这个步子，再更新一次的动量，整体的式子为：
$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)$

这样其实是起到加速的作用，这个我们也可以作用到Adam上面，
首先回顾下Adam算法：

$m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t$
$m_t^{1=\frac{m_t}{1-\beta_1}t}$
$\theta_{t+1}=\theta_t - \frac{\eta}{\sqrt{v_t^1} + \epsilon }m_t^1 $
把这些式子合并成一个式子：
$\theta_{t+1}=\theta_t -\frac{\eta}{\sqrt{v_t^1} + \epsilon } (\frac{\beta_1 m_{t-1}}{1-\beta_1^t} + \frac{(1-\beta_1)g_t}{1-\beta_1^t})$

我们注意到 $\frac{m_{t-1}}{1-\beta_1^{t}$就是$m_{t-1}}1$,我们简化为
$\theta_{t+1}=\theta_t -\frac{\eta}{\sqrt{v_t^1} + \epsilon } (\beta_1 m_{t-1}^1 + \frac{(1-\beta_1)g_t}{1-\beta_1^t})$

这里我们像上面加速一样，将上一步的$m_{t-1}^1$动量，
直接用现在的预估来代替，起到加速的作用，很简单的替换，得到：
$\theta_{t+1}=\theta_t -\frac{\eta}{\sqrt{v_t^1} + \epsilon } (\beta_1 m_{t}^1 + \frac{(1-\beta_1)g_t}{1-\beta_1^t})$

算法可视化

[图片上传失败...(image-315d2a-1511578384244)]

a. 这是一个loss 曲面，每种算法的起始点是一样的，每个算法的优化路线是不一样的，可以看到，Adagrad, Adadelta, 和 RMSprop 很快的就开始下降，momentum和 NAG就走了很多的弯路。

b. 展示的是算法如何逃离鞍点的情况，这种鞍点啃可能是，一个维度的梯度是正的，其他维度的梯度是负的。这种情形对于SGD来说是很难逃离的 ，图中就可以看出，SGD，Momentum，NAG都很难突破，Adagrad, RMSprop, 和 Adadelta 很快找到负梯度方向了。

该怎么选择

如果数据分布很稀疏，最好选择自适应学习率的算法
RMSprop，Adadelta,Adam都是很相似的自适应学习率的算法，总体来说Adam效果是最好的。

很有趣的是，最近很多论文都是直接用SGD，没有使用动量和学习率调节，像上面说的那样，SGD可以找到一个最小值，但是它可能很慢，对初始值的要求更高，也可能在鞍点就停止了。

反正如果在更深或者更复杂的网络，最好使用自适应学习率的算法。

并行和分布式SGD

SGD的替代是逐步的，所以原始的SGD是很难做到并行的，下面的算法是关于SGD的并行和分布式化的。

Hogwild!

Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent.它是一种多CPU的并行处理方式，共享一块内存，这些内存是不加锁的，这个适合于数据参数比较稀疏，每个部分只更新内存的一个独立部分，

Downpour SGD

Downpour SGD是一种异步SGD，Google在Large Scale Distributed Deep NetworksDistBelief的时候提出来的，他们把数据分为几个部分，然后一个模型跑多份，然后每个模型将他们的参数发送给 parameter server。这个server可能是多机器的，每个机器复杂存储和更新一部分参数。但是他们每一个模型之间是没有通信和数据交换的，这样会带来鼓励和阻碍达到最优。

延时容忍的SGD

Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning论文中扩展了AdaGrad，使它成为一种可容忍延时和并行的算法，据说不错。

TensorFlow

TensorFlow是google的开源机器学习框架，它的分布式结构，主要是将graph分成子图的模式，然后通过rpc的机制通信，传递参数更新。

SGD的其他优化

训练数据乱序

使得模型不刻意去学习数据输入的顺序，特别是序列模型的时候

batch normalization

对每个min-batch 进行归一化，可以使我们更加自如的控制学习率，使得对初始输入不是很敏感，它还可以其他还可以起到正则化的作用。

Early stop

loss 下降如果基本不动，就早点停止吧

梯度噪音

对梯度加个噪音（比如正态分布的噪音）：
$g_{t,i}=g_{t,i} + N(0, \sigma_t ^2)$
$\sigma_t^{2=\frac{\eta}{(1+t)}\gamma}$

加上这个噪音，会使得网络更加的稳定，还有可能更有机会逃离局部最优。