0x00 什么是优化算法？

优化算法就是一种最小化或最大化目标函数（有时也称为损失函数）的一类算法，它可以根据定义好的损失函数优化神经网络中参数的取值，从而使神经网络模型在训练数据集上的损失函数达到一个较小值。

无论什么优化算法，最后都可以用一个简单的公式抽象：

$$w = w + \Delta w$$

其中，$w$ 是参数，$\Delta w$ 是参数的增量，不同优化算法的区别仅在于 $\Delta w$ 的计算方式不同。

本文总结了下面三类优化算法的原理、特点、代码实现，并进行了对比分析，尽请享用。

0x01 梯度下降法

梯度下降法是最基本的一类优化器，目前主要分为三种梯度下降法：标准梯度下降法（GD, Gradient Descent），批量梯度下降法（BGD, Batch Gradient Descent）以及随机梯度下降法（SGD, Stochastic Gradient Descent）。

1. 标准梯度下降法（GD）

【原理】

梯度下降法是最重要的一种方法，也是很多其他优化算法的基础，其基本形式如下：

$$\Delta w = - \eta ~ \nabla J(w)$$

其中，$\eta$ 是学习率， $J(w)$ 是代价函数， $\nabla J(w)$ 是代价函数关于模型参数的偏导数，即梯度。

从表达式来看，模型参数的更新调整，仅与代价函数关于模型参数的梯度有关，即沿着梯度的反方向不断优化模型参数，从而最小化代价函数。

【理解策略】

该方法的基本思想可以理解为「在有限视距内寻找最快路径下山」，因此每一步都会选择当前位置的最陡方向（即梯度）前进。

image-20210422170751362

【特点】

标准梯度下降法有两个难以克服的缺点：

  • 训练速度慢：由于是在整个数据集上进行计算，在大型数据集中，每输入一个样本都要更新一次参数，且每次迭代都要遍历所有的样本。这会使得训练过程及其缓慢，需要花费很长时间才能得到收敛解。
  • 容易陷入局部最优解：由于是在有限视距内寻找下山的方向。当陷入平坦的洼地，会误以为到达了山地的最低点，从而不会继续往下走。所谓的局部最优解就是鞍点。落入鞍点，梯度为0，使得模型参数不在继续更新。

2. 批量梯度下降法（BGD）

【原理】

假设批量训练样本总数（batch size）为 $N$ ，每次输入和输出的样本分别为 $X^i, Y^i$ ，每输入一个样本 $i$ 代价函数关于 $w$ 的梯度为 $\nabla J_i(w, X^i, Y^i)$ ，则使用批量梯度下降法更新参数表达式为：

$$g_t = \frac{1}{N} (\sum_i^N \nabla J(w, X^i, Y^i))$$

$$\Delta w = - \eta ~ g_t$$

其中，$g_t$ 表示第 $t$ 轮代价函数的均值，下同。

从表达式来看，模型参数的调整更新，与该批量输入样本的代价函数的均值有关。每次权值调整发生在批量样本输入之后，而不是每输入一个样本就更新一次模型参数，这样就会大大加快训练速度。

【理解策略】

该方法的基本思想可以理解为：「在下山之前掌握了附近的地势情况，并选择总体平均梯度最小的方向下山」。

【特点】

  • 批量梯度下降法比标准梯度下降法训练时间短，且每次选择的方向都很正确。

3. 随机梯度下降法（SGD）

【原理】

相比BGD，随机梯度下降法（Stochastic Gradient Descent）每次从一批样本中随机选择一个样本 $k$ 来更新参数：

$$\Delta w = - \eta ~ \nabla J(w, X^k, Y^k)$$

其中，$k \in {1, 2, \dots, N}$ 表示随机选择的一个梯度方向。

【理解策略】

该方法的基本思想可以理解为：像是一个盲人下山，不用每走一步计算一次梯度，但是他总能下到山底，只不过过程会显得扭扭曲曲。

【特点】

  • 优点：

    • 虽然SGD似乎需要走的步子更多了，但由于其每次只选择一个样本计算梯度，更新速度很快。

      在应用大型数据集时，训练速度很快。比如每次从百万数据样本中，取几百个数据点，算一个SGD梯度，更新一下模型参数。相比于标准梯度下降法的遍历全部样本要快得多。

  • 缺点：

    • SGD在随机选择梯度的同时会引入噪声，使得权值更新的方向不一定正确，但大量的理论和实践工作证明，只要噪声不是特别大，SGD都能很好地收敛。
    • 此外，SGD同样无法克服局部最优解的问题。

【代码实现】

$\nabla J(w)$ 和 $g_i$ 在下面及之后的优化算法实现中，都将直接作为输入参数，其具体计算由其他模块负责，感兴趣可以参考下面两篇文章：

1
2
3
4
5
6
7
8
class Momentum(object):
    def __init__(self, lr=1e-3):
        self.lr = lr	# 学习率
	
    # Input: g = J'(w) 为本轮训练参数的梯度
    # Outpu: 参数的增量，下同
    def update(self, g: np.ndarray):
        return - self.lr * g

0x02 动量优化法

动量优化方法是在梯度下降法的基础上进行的改进，能够加速梯度下降的过程。常用的方法有标准动量优化方法（Momentum）、牛顿加速梯度算法（NAG，Nesterov accelerated gradient）动量优化方法。

1. Momentum

【原理】

使用动量（Momentum）的随机梯度下降法（SGD），主要思想是引入一个积攒历史梯度信息动量来加速SGD，其基本形式如下：

$$v_t = \alpha v_{t-1} + \eta ~ \nabla J(w, X^k, Y^k)$$

$$\Delta w = - ~ v_t$$

其中，$v_t$ 表示第 $t$ 轮积攒的历史梯度信息动量，$\alpha$ 表示动力的大小，一般取值为 0.9。

这是基于指数衰减的实现方式。

【理解策略】

该方法的基本思想可以理解为：由于当前权值的改变会受到上一次权值改变的影响，类似于小球向下滚动的时候带上了惯性，这样可以加快小球向下滚动的速度。

【特点】

动量主要解决SGD的两个问题：

  • 一是随机梯度的方法（引入的噪声）；
  • 二是Hessian矩阵病态问题（可以理解为SGD在收敛过程中和正确梯度相比来回摆动比较大的问题）。

2. NAG

【原理】

牛顿加速梯度（NAG, Nesterov accelerated gradient）算法，是Momentum动量算法的变种。与Momentum唯一区别就是，NAG 先用当前的速度 $v_{t-1}$ 更新一遍参数，得到一个临时参数这个临时参数计算本轮训练的梯度。其基本形式如下：

$$v_t = \alpha v_{t-1} + \eta ~ \nabla J(w - \alpha v_{t-1})$$

$$\Delta w = - ~ v_t$$

【理解策略】

该方法的基本思想可以理解为：

  • 在Momentum中，小球会盲目地跟从下坡的梯度，容易发生错误。所以需要一个更聪明的小球，能提前知道它要去哪里，还要知道走到坡底的时候速度慢下来而不是又冲上另一个坡。
  • 通过计算 $w - \alpha t_{t-1}$ 可以知道小球下一个位置大概在哪里，然后提前一个时刻用它来更新参数。

【特点】

  • 在凸批量梯度的情况下，NAG将额外误差收敛率从 $O(1/k)$ （k步后）改进到 $O(1/k^2)$ 。
  • 然而，在随机梯度情况下，NAG动量对收敛率的作用却不是很大。

0x03 自适应优化算法

自适应（Adaptive）学习率优化算法，主要针对于学习率进行优化。学习率对模型的性能有着显著的影响，然而传统的优化算法要么将学习率设置为常数要么根据训练次数调节学习率，忽视了学习率其他变化的可能性。因此需要采取一些策略来想办法更新学习率，从而提高训练速度。

目前的自适应学习率优化算法主要有：AdaGrad算法，RMSProp算法，AdaDelta算法以及Adam算法。

1. AdaGrad算法

【原理】

自适应性梯度算法（AdaGrad, Adaptive Sub-gradient），其主要特点在于不断累加每次训练中梯度的平方，公式如下：

$$r_t = r_{t-1} + g_t^2$$

$$\Delta w = - \frac{\eta}{\sqrt{\epsilon + r_t}} g_t$$

其中，$\epsilon$ 是一个极小的正数，用来防止除0， $g_t^2 = g_t \odot g_t$ ，$\odot$ 是矩阵的哈达码积运算符。

从公式中可以看出，随着算法不断迭代，$r_t$ 会越来越大，整体的学习率会越来越小。因此，一般来说AdaGrad算法一开始是激励收敛，到了后面就慢慢变成惩罚收敛，速度越来越慢。

【特点】

  • Adagrad 的主要优势在于不需要人为的调节学习率，它可以自动调节；缺点在于，随着迭代次数增多，学习率会越来越小，最终会趋近于0
  • 此外，AdaGrad算法虽然在凸函数(Convex Functions)上表现较好，但是当目标函数非凸时，算法梯度下降的轨迹所经历的结构会复杂的多，因为早期梯度对当前训练没有太多意义。

2. RMSProp算法

【原理】

均方根传播（RMSProp，Root Mean Square Prop）是AdaGrad的改进算法，把AdaGrad的梯度积累改为指数加权的移动平均，其基本形式如下：

$$r_t = \beta r_{t-1} + (1 - \beta)g_t^2$$

$$\Delta w = - \frac{\eta}{\sqrt{\epsilon + r_t}} g_t$$

从公式可以看出，与AdaGrad不同，RMSProp只会累积近期的梯度信息，对于“遥远的历史”则会以指数衰减的形式慢慢放弃。

【特点】

  • RMSProp借鉴了Adagrad的思想，由于取了个加权平均，避免了学习率越来越低的的问题，而且能自适应地调节学习率。
  • RMSProp算法在经验上已经被证明是一种有效且实用的深度神经网络优化算法。目前它是深度学习从业者经常采用的优化方法之一。

3. AdaDelta算法

【原理】

AdaDelta是与RMSProp相同时间对立发展出来的一个算法，在实现上可以看作是RMSProp的一个变种，先看公式：

$$r_t = \beta r_{t-1} + (1 - \beta)g_t^2$$

$$s_t = \beta s_{t-1} + (1 - \beta) \Delta w^2$$

$$\Delta w = - \frac{\sqrt{\epsilon + s_t}}{\sqrt{\epsilon + r_t}} g_t$$

可以看到该算法不需要设置学习率 $\eta$，这是该算法的一大优势。除了同样以 $r_t$ 来累积梯度的信息之外，该算法还使用一个 $s_t$ 以指数衰减的形式来累积 [公式] 的信息。

【特点】

  • 在模型训练的初期和中期，AdaDelta表现很好，加速效果不错，训练速度快。
  • 在模型训练的后期，模型会反复地在局部最小值附近抖动。

4. Adam算法

前面我们从最经典的梯度下降法开始，介绍了几个改进版的梯度下降法：

  • Momentum方法通过添加动量，提高收敛速度；
  • Nesterov方法在进行当前更新前，先进行一次预演，从而找到一个更加适合当前情况的梯度方向和幅度；
  • Adagrad让不同的参数拥有不同的学习率，并且通过引入梯度的平方和作为衰减项，而在训练过程中自动降低学习率；
  • AdaDelta则对Adagrad进行改进，让模型在训练后期也能够有较为适合的学习率。

既然不同的参数可以有不同的学习率，那么不同的参数是不是也可以有不同的Momentum呢？

Adam方法就是根据上述思想而提出的，对于每个参数，其不仅仅有自己的学习率，还有自己的Momentum量，这样在训练的过程中，每个参数的更新都更加具有独立性，从而提升了模型训练速度和训练的稳定性。

【原理】

Adam的全称为 Adaptive Momentum，可以看作是Momentum与RMSProp的一个结合体。该算法通过计算梯度的一阶矩估计和二阶矩估计而为不同的参数设计独立的自适应性学习率，公式如下：

$$s_t = \alpha s_{t-1} + (1 - \alpha) g_t$$

$$r_t = \beta r_{t-1} + (1 - \beta) g_t^2$$

$$\hat{s_t} = \frac{s_t}{1 - \alpha^t}$$

$$\hat{r_t} = \frac{r_t}{1 - \beta^t}$$

$$\Delta w = - \eta ~\frac{\hat{s_t}}{\sqrt{\epsilon + r_t}}$$

其中，$s_t$ 和 $r_t$ 分别为一阶动量项和二阶动量项，$\hat{s_t}$ 和 $\hat{r_t}$ 分别为各自的修正值。

【特点】

Adam 算法同时获得了 AdaGrad 和 RMSProp 算法的优点。

  • Adam 不仅如 RMSProp 算法那样基于一阶矩均值计算适应性参数学习率，它同时还充分利用了梯度的二阶矩均值（即有偏方差/uncentered variance）。具体来说，算法计算了梯度的指数移动均值（exponential moving average），超参数 $\alpha$ 和 $\beta$ 控制了这些移动均值的衰减率。
  • 移动均值的初始值和 $\alpha$ 、$\beta$ 值接近于 1（推荐值），因此矩估计的偏差接近于 0。该偏差通过首先计算带偏差的估计而后计算偏差修正后的估计而得到提升。

Adam works well in practice and outperforms other Adaptive techniques.

0x04 各种优化器对比分析

1. 可视化比较

示例1

optimizer-eg1

上图描述了在一个曲面上，6种优化器的表现，从中可以大致看出：

① 下降速度：

  • 三个自适应学习优化器Adagrad、RMSProp与AdaDelta的下降速度明显比SGD要快，其中，Adagrad和RMSProp齐头并进，要比AdaDelta要快。
  • 两个动量优化器Momentum和NAG由于刚开始走了岔路，初期下降的慢；随着慢慢调整，下降速度越来越快，其中NAG到后期甚至超过了领先的Adagrad和RMSProp。

② 下降轨迹：

  • SGD和三个自适应优化器轨迹大致相同。两个动量优化器初期走了“岔路”，后期也调整了过来。

示例2

optimizer-eg2

上图在一个存在鞍点的曲面，比较6中优化器的性能表现，从图中大致可以看出：

  • 三个自适应学习率优化器没有进入鞍点，其中，AdaDelta下降速度最快，Adagrad和RMSprop则齐头并进。
  • 两个动量优化器Momentum和NAG以及SGD都顺势进入了鞍点。但两个动量优化器在鞍点抖动了一会，就逃离了鞍点并迅速地下降，后来居上超过了Adagrad和RMSProp。
  • 很遗憾，SGD进入了鞍点，却始终停留在了鞍点，没有再继续下降。

示例3

optimizer-eg3

上图比较了6种优化器收敛到目标点（五角星）的运行过程，从图中可以大致看出：

① 下降速度

  • 两个动量优化器Momentum和NAG的速度最快，其次是三个自适应学习率优化器AdaGrad、AdaDelta以及RMSProp，最慢的则是SGD。

② 下降轨迹

  • 两个动量优化器虽然运行速度很快，但是初中期走了很长的”岔路”。
  • 三个自适应优化器中，Adagrad初期走了岔路，但后来迅速地调整了过来，但相比其他两个走的路最长；AdaDelta和RMSprop的运行轨迹差不多，但在快接近目标的时候，RMSProp会发生很明显的抖动。
  • SGD相比于其他优化器，走的路径是最短的，路子也比较正。

0x05 参考文章

[1] 机器学习：各种优化器Optimizer的总结与比较

[2] 从SGD到NadaMax，十种优化算法原理及实现

[3] 神经网络中的各种优化方法