优化算法系列（3）：SGD改进之梯度估计修正

在SGD中，我们提到过每次选取批量样本计算梯度和实际的梯度存在误差，这个梯度误差的直观体现是损失曲线呈现震荡下行。于是，为了缓解这个SGD中梯度误差我们可以通过最近一段时间内的平均梯度来代替当前时刻的梯度，进而缓解梯度带来的随机性。文本就从这个方向着手解决问题。

梯度估计

搜索梯度估计（Gradient Estimation）相关的资料，发现梯度估计还真是个大领域，很多理论性很强的内容，目前还没有遇到这样的需要，因此这里深入不了这个领域，而是谈谈优化算法中梯度估计的思想。

我们在SGD中提到，用训练集的子集来计算梯度和真实的梯度有差异，那么我们肯定会想到能否有些什么技巧来减少这个计算的差异吧。由于这个误差是随机的，因此减缓差异的方式就是降低估计梯度和真实梯度的方差。一个很好的思路是加权平均。拿全量数据的子集进行梯度估计，为让估计更稳定，利用历史数据拟合（修正）当前的梯度。

在展开此讨论之前，我们先谈谈梯度截断。

梯度截断

梯度估计最容易让人想到的是梯度截断（有称梯度裁剪），它不需要特别的迭代技巧。当然，它的目的性也是很强的，如为缓解梯度爆炸问题而截断梯度。

当梯度的模大于一定阈值时，梯度截断方法对梯度按一定规则进行截断。比如按值截断，期望梯度的取值限制在区间$[a, b]$内，那么截断方法为，

$$\boldsymbol{g}_{t} = \max(a, \min ( \boldsymbol{g}_{t},b))$$

类似地，按模截断，当梯度大于某个值是，截断$\boldsymbol{g}_{t} = \eta \frac{\boldsymbol{g}_{t} }{\left | \boldsymbol{g}_{t} \right |}$，具体地，

$$\boldsymbol{g}_{t} = \begin{cases} \boldsymbol{g}_{t} & \text{ if } \Vert \boldsymbol{g}_{t} \Vert \le \eta \\ \\ \eta \frac{\boldsymbol{g}_{t}}{\Vert \boldsymbol{g}_{t} \Vert} & \text{ if } \Vert \boldsymbol{g}_{t} \Vert > \eta \end{cases}$$

代入到梯度下降中，

$$\theta_{n} = \theta_{n-1} - \gamma \boldsymbol{g}_{n}(\theta_{n-1})$$

直观理解，梯度裁剪能假设训练过程。因为训练过程中梯度突然增大，反而容易让更新参数远离局部最优点，进而导致梯度路径曲折迂回。不过，这只是直观理解，并没有数学上的证明。

SGDM

SGDM = SGD + Momentum，所谓Momentum即趋势，沿着某个方向运动的趋势。

加权移动平均

我们来看看加权移动平均的计算方式，

$$S_{t}= \begin{cases} Y_{1},& \;t=1 \\ \alpha Y_{t}+(1-\alpha )\cdot S_{t-1},& \;t>1 \end{cases}$$

展开来看，

$$\begin{aligned} S_{t}=\alpha & \left[Y_{t}+(1-\alpha )Y_{t-1}+(1-\alpha )^{2}Y_{t-2}+\cdots \right.\\ & \left.\cdots +(1-\alpha )^{k}Y_{t-k}\right]+(1-\alpha )^{k+1}S_{t-(k+1)} \end{aligned}$$

迭代式和展开式在数学上是等价的，不过在实践上，展开式的实现需要更大的存储空间的记录窗口内的权重，这时迭代的形式就发挥优势了。由于$1 - \alpha \lt 1$，因此，当离当前时刻越远的取值获得的权重也就越少，因此加权移动平均可以理解成是一种遗忘策略。

SGD加Momentum

SGDM实际上就是SGD加Momentum。这里Momentum是借用物理上的动量概念，指物体的运动在其原有的方向上保持趋势。其实我们可以不太关注其真实的物理意义，只需要知道Monentum对应的数学操作就是对历史梯度进行加权移动平均，而这个平均的结果作为当前时刻的梯度。类比下，我们看K线波动总是很大，而均值趋势线却很平稳，梯度也是这个效果。

由于客观条件限制，无法使用全量数据计算梯度，那就估计吧。拿全量数据的子集进行梯度估计，为让估计更稳定，利用历史数据拟合（修正）当前的梯度。加权平均更新梯度的方式如下，

$$\theta_{n} = \theta_{n-1} - \gamma \sum_{i=1}^{n}\beta^{n-i} \boldsymbol{g}_{i}$$

第$i$个梯度$\boldsymbol{g}_{i}$的权重为$\beta^{t-i}$，动量因子$\beta \lt 1$，所以离当前越近的梯度重要性越大。不过你会发现，在工程实现上，记录一个时间窗口内的梯度并不实际，因此这需要的内存或显存太大了。为此，以上方式我们可以改为如下为迭代的形式，

$$\begin{aligned} &\boldsymbol{\theta}_{n+1} = \boldsymbol{\theta}_{n} + \boldsymbol{g}_{n+1} \\ &\boldsymbol{g}_{n+1} = \alpha \boldsymbol{g}_{n} - \gamma \nabla_{\boldsymbol{\theta}} L_{R_{i}}(\boldsymbol{\theta}_n) \end{aligned}$$

$\alpha \ge 0$​称为动量因子，当然不同材料以上的表述不一定相同，能够表达其加权移动平均即可，当动量因子取0时，退化成普通的SGD算法。

在Keras中，SGD中使用Momentum只需要把momentum参数改为大于0即可，

keras.optimizers.SGD(
    learning_rate=0.01, momentum=0.0, nesterov=False, name='SGD', **kwargs
)

分析

可以看到，每个模型参数的实际值都是时间窗口内梯度的加权平均。这样可以平滑某个时刻的参数异常：

• 在一个时间窗口内，某个参数的梯度方向不一致时, 在加权平均作用下其真实的参数更新幅度变小
• 在一个时间窗口内，相对以上情况，参数更新幅度变更大，起到加速的作用

Nesterov Accelerated Gradient

Nesterov Acceleration Gradient，简称NAG，对Momentum法的改进。SGDM表明，当前的参数的更新方向$\Delta \boldsymbol{\theta}_{n+1}$为上一步参数更新方向$\alpha \boldsymbol{g}_n$与当前梯度的反方向叠加$- \gamma \nabla_{\boldsymbol{\theta}} L_{R_{i}}(\boldsymbol{\theta}_n) $​，第二步的更新其实不太合理，应该改为参数上的梯度，因此有，

$$g_{n+1} = \alpha g_{n} - \gamma\nabla_{\theta}L(\theta_n + \alpha g_n) \\ \theta_{n+1} = \theta_{n} + g_{n+1}$$

取$\theta_n \leftarrow \theta_n + \alpha g_n$容易改为如下形式，

$$g_{n+1} = \alpha g_{n} - \gamma \nabla_{\theta}L(\theta_{n}) \\ \theta_{n+1} = \theta_{n} + \alpha g_{n+1} - \gamma \nabla_{\theta}L(\theta_{n})$$

NAG的思路不是来自加权平均历史梯度来降方差，而是出于对SGDM梯度更新不合理的改进。

总结

随机梯度下降为，

$$\begin{align} \theta_{n+1} = \theta_{n} - \gamma \nabla_{\theta}L_{R_{i}}(\theta_{n}) \end{align}$$

引入Momentum后，改为，

$$g_{n+1} = \alpha g_{n} - \gamma \nabla_{\theta}L(\theta_{n}) \\ \theta_{n+1} = \theta_{n} + g_{n+1}$$

称为SGDM，直观来说是用平滑的梯度$g_{n+1}$​来替代梯度进行参数更新。

引入Nesterov加速后，改为，

$$g_{n+1} = \alpha g_{n} - \gamma \nabla_{\theta}L(\theta_{n}) \\ \theta_{n+1} = \theta_{n} + \alpha g_{n+1} - \gamma \nabla_{\theta}L(\theta_{n})$$

改进SGDM参数更新的不合理。