优化算法 - 简书

优化算法框架

优化算法经历了SGD->SGDM->NAG->AdaGrad->AdaDelta->Adam->Nadam的发展。

定义框架：待优化参数 $\omega$ ，目标函数 $f(\omega )$ ，初始学习率 $\alpha$

开始迭代每个epoch $t$ ：

1. 计算目标函数关于当前参数的梯度： $g_{t}=\nabla f(w_{t})$

2. 根据历史梯度计算一阶动量和二阶动量： $m_{t}=\phi (g_{1}, g_{2},...,g_{t}); V_{t}=\psi (g_{1}, g_{2},...,g_{t})$

3. 计算当前时刻的下降梯度： $\eta _{t}=\alpha \cdot m_{t}/\sqrt{V_{t}}$

4. 根据下降梯度进行更新： $\omega _{t+1}=\omega _{t}-\eta _{t}$

步骤3、4对各个算法都是一致的，差别体现在1、2上。

SGD

SGD没有动量的概念。 $m_{t}=g_{t}， V_{t}=I^2$ 。

代入步骤3、4，得到 $\eta _{t}=\alpha\cdot g_{t}， \omega _{t+1}=\omega _{t}-\alpha\cdot g_{t}$ 。

SGD with Momentum

SGDM全称是SGD with momentum，在SGD基础上引入了一阶动量。 $m_{t}=\beta _{1}m_{t-1}+(1-\beta _{1})g_{t}， V_{t}=I^2$

代入步骤3、4，得到 $\omega _{t+1}=\omega _{t}-\alpha \cdot m_{t}$

一阶动量是各个时刻梯度方向的指数移动平均值，约等于最近 $1/(1-\beta _{1})$ 个时刻的梯度向量和的平均值。

SGD是蓝线，每次迭代更新取决于当前batch的下降梯度，震荡严重，下降速度慢。

如果使用较大的学习率，如紫色线，结果可能会偏离函数范围，停留在一个局部最优点。

SGDM的参数 $\beta _{1}$ 的经验值为0.9，这就意味着，t时刻的下降方向主要是此前累积的下降方向，并略微偏向当前时刻的下降方向。

加上momentum的 SGD 算法在更新模型参数时，对于当前梯度方向与上一次梯度方向相同的参数，则会加大更新力度；而对于当前梯度方向与上一次梯度方向不同的参数，则会进行消减，即在当前梯度方向的更新减慢了。因此，相较于 SGD，SGDM可以收敛得更快，并且减少震荡。红线，纵轴方向摆动变小了，横轴方向运动更快。

SGD with Nesterov Acceleration

NAG全称Nesterov Accelerated Gradient，改进点在于步骤1。

SGD 还有一个问题是困在局部最优的沟壑里面震荡。

此时与其看当前梯度方向，不如先看看如果跟着累积动量走了一步，那个时候再怎么走。

$g_{t}=\nabla f(w_{t} - \alpha \cdot m_{t-1}/\sqrt{V_{t-1}} )$

然后再使用 $g_{t}$ 与历史累积动量相结合，计算步骤2的累积动量。

步骤3、4， $\omega _{t+1}=\omega _{t}-\alpha \cdot m_{t}/\sqrt{V_{t}}$

AdaGrad

此前都没有用到二阶动量，SGD及其变种以同样的学习率更新每个参数。

对于经常更新的参数，我们已经积累了大量关于它的知识，不希望被单个样本影响太大，希望学习速率慢一些；对于偶尔更新的参数，我们了解的信息太少，希望能从每个偶然出现的样本身上多学一些，即学习速率大一些。比如深度神经网络中大规模的embedding参数，并不是总会用得到。

二阶动量的出现，才是“自适应学习率”优化算法。它是所有时刻的梯度值的平方和。

$V_{t} = \sum_{\tau =1}^{t} g_{\tau }^{2}$

步骤3中的下降梯度 $\eta _{t}=\alpha \cdot m_{t}/\sqrt{V_{t}}$ ，可以看出学习率由 $\alpha$ 变成了 $\alpha/\sqrt{V_{t}}$ 。

参数更新越频繁（每个时刻都有梯度），二阶动量越大，学习率就越小。

一般为了避免分母为0，会在分母上加一个小的平滑项， $\sqrt{V_{t}+\varepsilon }$ 是恒大于0的。

存在问题： $\sqrt{V_{t}}$ 是单调递增的，会使得学习率单调递减至0，可能会使得训练过程提前结束，即便后续还有数据也无法学到必要的知识。

AdaDelta / RMSProp

由于AdaGrad单调递减的学习率变化过于激进，考虑不累积全部历史梯度，而只关注过去一段时间窗口的下降梯度。这也就是AdaDelta名称中Delta的来历。相对 Adagrad 梯度下降得较慢，避免了二阶动量持续累积，导致训练过程提前结束的问题。

RMSprop 是 AdaDelta 的一个特例，使用指数移动平均来计算二阶累积动量。

$V_{t}=\beta _{2}\ast V_{t-1}+(1-\beta _{2})g_{t}^{2}$

步骤2 $m_{t}=g_{t}$

步骤3、4， $\omega _{t+1}=\omega _{t}-\alpha \cdot g_{t}/\sqrt{V_{t}+\varepsilon }$

Adam

使用一阶动量和二阶动量，就是Adam——Adaptive + Momentum。

一阶动量： $m_{t}=\beta _{1}m_{t-1}+(1-\beta _{1})g_{t}$

二阶动量： $V_{t}=\beta _{2}\ast V_{t-1}+(1-\beta _{2})g_{t}^{2}$

步骤3、4， $\omega _{t+1}=\omega _{t}-\alpha \cdot m_{t}/\sqrt{V_{t}+\varepsilon}$

参数的经验值是 $\beta _{1}=0.9，\beta _{2}=0.999$

Nadam

Nadam = Nesterov + Adam，加上NAG的步骤1

指数移动平均

$v_{t}=\beta v_{t-1}+(1-\beta)\theta _{t}$

当 $\beta$ =0.9时，

$v_{100}=0.9v_{99}+0.1\theta _{100}=0.1\theta _{100}+0.9(0.1\theta _{99}+0.9v_{98})$

$=0.1\theta _{100}+0.1*0.9\theta _{99}+0.1*(0.9)^2\theta _{98}+...$

因为 $0.9^{10}\approx 0.35\approx\frac{1}{e}$ ， $\theta _{90}$ 的权重下降到1/3，因此指数移动平均约等于最近1/(1- $\beta$ )个历史数据的平均值（越近的历史数据，权重越大，每次迭代以 $\beta$ 系数衰减）。

红色线 $\beta$ =0.9，平均了10个历史数据。

绿色线 $\beta$ =0.98，曲线更加平缓，因为平均了50个历史数据。

偏差修正

原始使用 $v_{0}=0$ ，初期估计会有问题，现使用 $v_{t}/(1-\beta ^{t})$ 修正。

当 $\beta$ =0.98时，

原始： $v_{0}=0$

$v_{1}=0.98v_{0}+0.02\theta _{1}=0.02\theta _{1}$

$v_{2}=0.98v_{1}+0.02\theta _{2}=0.0196\theta _{1}+0.02\theta _{2}$

修正：

$v_{1}=\frac{0.02\theta _{1}}{1-0.98} =\frac{0.02\theta _{1}}{0.02}$

$v_{2}=\frac{0.0196\theta _{1}+0.02\theta _{2}}{1-0.98^2} =\frac{0.0196\theta _{1}+0.02\theta _{2}}{0.0396}$

分母 $1-\beta ^{t}$ 在初期较小，扩大 $v_{t}$ ，经过多次迭代，分母接近1， $v_{t}$ 基本不变

紫色线是存在偏差，绿色线是修正偏差。

参考：

一个框架看懂优化算法之异同 SGD/AdaGrad/Adam