梯度下降算法总结

1.概述

梯度下降是应用非常广泛的优化算法,也是目前最常见的优化神经网络的方法之一。从简单的线性回归到当下火热的深度学习,处处可见梯度下降的身影,由此可见梯度下降的重要性。现在很多知名的深度学习库都已经包含了各种梯度下降优化算法的实现(如 Tensorflow,Cafe,Keras),但依然很有必要去了解梯度下降的底层逻辑,熟知梯度下降不同变种之间的区别,并能够根据它们各自的优缺点选择最合适的方法和参数来应用于相应的场景。

文本对梯度下降算法以及各类衍生优化算法进行了详尽的总结归纳,包括梯度下降原理的深入解读、梯度下降的变种优化算法、梯度下降的一些理解误区,以及深度学习中各种优化算法的原理、发展历程、主流模型使用的优化算法。

(注:本篇为第二版,有很多更新,初版发布时间为:2018-07-25)

2.为什么要用梯度下降

《线性回归》一文中,经过不断将目标函数计算简化,我们终于得到了一个非常理想的θ的解析式:

$$ \theta_\lambda = (X^TX+\lambda I )^{-1} \cdot X^T \cdot y $$

然而实际在求解最优解的过程中,依然可能会遇到下面的问题:

  1. 计算量大

    如果 X 维度特别大,比如是上千上万维的,计算量会非常大;

  1. 需要全部数据

    很多时候我们没有办法直接离线的拿到足够多的数据来直接计算 $\theta$,梯度下降不要求必须是全量数据;

  1. 必须有解析解

    不是所有的目标函数都能够求得解析解,梯度下降不要求必须有解析解;

  1. 偏数学逻辑而非计算机的逻辑

    梯度下降的逻辑更符合计算机科学的程序设计逻辑,通过不断迭代优化,获取最优解,而不是消耗大量算力直接计算;

  1. 更像数学而非机器学习

    直接求逆,然后带公式,或者 SVD 来求伪逆这些传统的办法已经不现实了,这样做会显得很 “low”,我们更希望θ是学习来的,而不是直接算出来的,就像人一样,通过一步步的学习和成长达到最终目的,期间有成功的正反馈也有失败的负反馈,这才是机器 “学习” 的真谛。

在机器学习的任务中,绝大部分优化问题都可以转化成下面的问题:

给定一个关于 $\theta \in R$的损失函数 $J(\theta)$,求使得 $J(\theta)$最小的参数 $\theta$。

而梯度下降的作用就是不断沿着负梯度方向迭代,每次更新后的 $\theta$能够使 $J(\theta)$更小,这个过程就是机器学习的最优化。(如下图所示,图中的 X、Y 为参数,即θ=[X, Y])

梯度下降算法总结_插图

@最优化

最优化是指对关于参数 $x$的目标函数 f(x) 进行最小化或最大化的过程。在机器学习或深度学习术语中,通常指最小化损失函数 $J(\theta)$,其中模型参数 $\theta \in R^d$。最优化算法具有以下的目标:

1)如果目标函数是凸的,那么任何的局部最小值都是全局最小值。

2)通常情况下,在大多数深度学习问题中,目标函数是非凸的,那就只能找到目标函数邻域内的最低值。

常见的三类最优化问题:

1)对单点问题,最优化算法不用进行迭代和简单求解。

2)对于凸损失函数中用到的梯度下降法,这类最优化算法本质上是迭代,不管参数初始化好坏都能收敛到可接受的解。

3)对于一系列具有非凸损失函数的问题中,如神经网络。为保证收敛速度与低错误率,最优化算法中的参数初始化中起着至关重要的作用。

3.梯度下降算法原理

梯度下降优化算法的核心思想是 “最优迭代”,迭代很容易理解,就是通过多次迭代来逐渐靠近最优解,而最优就是要求每次迭代一定是最好的优化方向。

直观的理解,可以将梯度下降的过程理解成下山,当前在高山的某个位置,我们要到山的最低(目标函数最小)处,怎样才能找到最优的下山路径呢?这个时候就可以利用梯度下降的思想。具体来讲,就是走一步算一步,每走一步都以他当前所处的位置为基准,沿着当前位置最陡峭最易下山的方向前进一小步,然后继续沿下一个位置最陡方向前进一小步,这样一步步走下去,直到山的最低处。

梯度下降算法总结_插图1

这里的提到的下山最陡的方向就是梯度的负方向。以下图为例,在把损失函数可视化后,在损失函数与参数构成的等值线上找任意一点,我们可以定义一个与该点相切的平面(这里以三维为例,在更高的维度中,我们总是可以定义一个超平面)。在这个平面上我们可以有无穷多个方向。其中,恰好有一个方向是损失函数上升最快的方向(Steepest Ascent),这个方向是由计算梯度得出的,而与之相反的方向就是最陡下降的方向(Steepest Descent)。所以说梯度的负方向(Opposite of Gradient)就是损失函数下降最快的方向。因为优化过程是让损失函数最小,是沿着负梯度方向进行的,所以这个优化方法称为梯度下降(Gradient Descent)

梯度下降算法总结_插图2

梯度下降的数学定义

那么为什么局部下降最快的方向就是梯度的负方向呢?其本质的原理又是什么呢?

首先来了解一下什么是梯度?梯度是一个向量,用于指示函数在给定点上的变化率和方向。对于一个多元函数,梯度是一个向量,其中每个分量表示函数在相应变量上的偏导数。

参数 $\theta$ 在损失函数 $J(\theta)$ 上的的梯度,可以写作:

$$\nabla f(\theta)=\frac{\partial J(\theta)}{\partial \theta}$$

梯度具备以下性质:

对于函数 $f:R^{n} \rightarrow R$ ,满足 $f(\text{x}) = c, \text{x} \in R^{n} $的所有 $\text{x}$ 组成的集合,称为函数 $f$ 的水平集。如下图所示:

梯度下降算法总结_插图3

如果函数在 $\text{x}_{0}$ 处的梯度 $\nabla f(\text{x}_{0})$ 不是 0 向量,那么它与水平集 $f(\text{x})=c$ 中任意一条经过 $\text{x}_{0}$ 的曲线的切向量正交。因此一个实值可微函数在某点处的函数值增加最快的方向正交于经过该点的函数水平集。

基于以上性质可知,梯度向量的方向指示了函数增加最快的方向,而梯度的大小表示了增长的速率。如果梯度的某个分量为正,表示函数在相应变量上增加;如果梯度的某个分量为负,表示函数在相应变量上减小。

既然函数增加最快的方向是梯度,那么负梯度就是损失函数减小最快的方向。

由此可以写出梯度下降的迭代公式

$$\theta =\theta_0 – \alpha \cdot \nabla f(\theta_0) = \theta_0 – \alpha \cdot \frac{\partial J(\theta)}{\partial \theta_0} $$

这里首先定义一个初始点 $\theta_0$,由该点出发沿着该点的负梯度方向更新一段距离 $\alpha$($\alpha$ 是每次迭代的步长,称为学习率),构造出新的点 $\theta$,如此往复迭代。

一阶泰勒展开式

上面的迭代公式是通过性质定义的,接下来,我们从泰勒展开的角度来推导梯度下降公式到底是怎么来的,以此了解梯度下降最本质的深层原理。

根据前面的信息我们已经知道,不是所有的目标函数都能得到解析解,因此就无法通过数学计算来直接求得其最优解,这个求解最优化参数的过程成为了一个 NP 难问题。既然无法直接求解,那我们可以利用贪心算法的思想,通过不断逼近最优解,来求得其近似值。而对于近似计算,泰勒公式是一个非常好的工具,因此,梯度下降法和牛顿法便被发明了出来,梯度下降法本质其实是泰勒公式的一阶展开,而牛顿法则是泰勒公式的二阶展开。

@泰勒公式

设 $n$是一个正整数。如果定义在一个包含 $a$ 的区间上的函数 $f$ 在 $a$ 点处 $n+1$ 次可导,那么对于这个区间上的任意 $x$ 都有:$f(x)=\sum_{n=0}^N \frac{f^{(n)}(a)}{n!}(x-a)^n + R_n(x)$,其中的多项式称为函数在 $a$ 处的泰勒展开式,$R_n(x)$是泰勒公式的余项且是 $(x-a)^n$ 的高阶无穷小。(维基百科)

泰勒公式展开表示为:

$$f(x)=\frac{f(a)}{0!}+\frac{f'(a)}{1!}(x-a)+\frac{f{”}(a)}{2!}(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n+R_n(x)$$

泰勒公式可以用若干项连加式来表示一个函数,这些相加的项由函数在某一点的导数求得。

泰勒公式在不同的场景又称泰勒展开,泰勒展式,泰勒多项式,泰勒级数(无穷多项);若在零处展开,又可称为麦克劳林公式(Maclaurin 公式),麦克劳林公式平常还是习惯表达成泰勒公式。

简单地来说,泰勒展开利用的就是函数的局部线性近似这个概念。为了便于理解,我们先从一阶泰勒展开式说起,高阶展开原理基本一样。泰勒多项式的项数越多(阶数越高)则函数局部线性近似就越精确,不过阶数越高也就意味着算法的复杂度越高,对于追求泛化性能的机器学习来说,通过增加很高的复杂度多出来的一丁点精确度几乎没有什么实际意义。因此,优化算法常用的就是一阶和二阶展开,即梯度下降和牛顿法,因牛顿法使用二阶展开,收敛速度要更快一些。

根据上面泰勒公式,一阶泰勒展开式可写作:

$$f(\theta) \approx f( \theta_0 ) +(\theta – \theta_0) \cdot \nabla f(\theta_0) $$

我们利用下面这张图来帮助理解^[5]^:

梯度下降算法总结_插图4

上图中,凸函数 $f(θ)$的某一小段 $[θ_0,θ]$由上图黑色曲线表示,可以利用线性近似的思想求出 $f(θ)$的值,如上图红色直线。该直线的斜率等于 $f(θ)$在 $θ_0$处的导数。则根据直线方程,很容易得到 $f(θ)$的近似表达式为:

$$f(\theta) \approx f( \theta_0 ) +(\theta – \theta_0) \cdot \nabla f(\theta_0) $$

这就是一阶泰勒展开式的推导过程,主要利用的数学思想就是曲线函数的线性拟合近似。

梯度下降数学原理

知道了一阶泰勒展开式之后,接下来就是重点了!我们来看一下梯度下降算法是如何推导的。

$$f(\theta) \approx f( \theta_0 ) +(\theta – \theta_0) \cdot \nabla f(\theta_0) ​$$

实际上,泰勒公式本身含有微分思想在里面,比如上式中,$f(\theta)$等同于上面提到的目标函数 $J(\theta)$, $\theta – \theta_0$是微小矢量,它的大小就是我们之前讲到的步进长度,即学习率 $\alpha $,$\alpha$是一个标量,而 $\theta – \theta_0$的单位向量用 $v$表示,因此 $\theta – \theta_0$可表示为:

$$\theta – \theta_0 = \alpha v​$$

特别需要注意的是,$\theta – \theta_0​$不能太大,因为太大的话,线性近似就不够准确,一阶泰勒近似也不成立了,替换之后,$f(\theta)​$的表达式为:

$$f(\theta) \approx f( \theta_0 ) +\alpha v \cdot \nabla f(\theta_0) ​$$

重点来了,局部下降的目的是希望每次 $\theta​$更新,都能让函数值 $f(\theta)​$变小。也就是说,上式中,我们希望 $f(\theta) \lt f(\theta_0)​$。则有:

$$f(\theta) – f(\theta_0) \approx \alpha v \cdot \nabla f(\theta_0) \lt 0​$$

因为 $\alpha$为标量,且一般设定为正值,所以可以忽略,不等式变成了:

$$ v \cdot \nabla f(\theta_0) \lt 0​$$

上面这个不等式非常重要!$v$和 $ \nabla f(\theta_0)$都是向量,$$ \nabla f(\theta_0)$$是当前位置的梯度方向,$v$表示下一步前进的单位向量,是需要我们求解的,有了它,就能根据 $\theta – \theta_0 = \alpha v$来确定 $\theta$的值了。

想要两个向量的乘积小于零,我们先来看一下两个向量乘积包含哪几种情况:

梯度下降算法总结_插图5

上图中,A 和 B 均为向量,α为两个向量之间的夹角。A 和 B 的乘积为:

$$A \cdot B = ||A|| \cdot||B||\cdot cos(\alpha)$$

$||A||$和 $||B||$均为标量,在 $||A||$和 $||B||$确定的情况下,只要 $cos(\alpha)=-1$,即 $A$和 $B$完全相反,就能让 $A$和 $B$的向量乘积最小(负最大值)。

顾名思义,当 $v$和 $\nabla f(\theta_0) $互为反向,即当 $v$为当前梯度方向的负方向的时候,能让 $v \cdot \nabla f(\theta_0)$最大程度地小,也就保证了 $v$的方向是局部下降最快的方向。

知道了 $v$是 $\nabla f(\theta_0)$的反方向后,可直接得到:

$$v = -\frac {\nabla f(\theta_0)} {||\nabla f(\theta_0)||}​$$

之所以要除以 $\nabla f(\theta_0)$ 的模 $||\nabla f(\theta_0)||$,是因为 $v$是单位向量。

求出最优解 $v$之后,带入到中 $$\theta – \theta_0 = \alpha v$$中,得:

$$\theta = \theta_0-\alpha\frac {\nabla f(\theta_0)} {||\nabla f(\theta_0)||}​$$

一般的,因为 $||\nabla f(\theta_0)||$是标量,可以并入到学习率 $ \alpha $中,即简化为:

$$\theta = \theta_0-\alpha \nabla f(\theta_0) ​$$

把 $f(\theta)$换为目标函数 $J(\theta)$,就是我们上面的梯度下降公式了:

$$\theta = \theta_0-\alpha \nabla J(\theta_0) =\theta_0 – \alpha \cdot \frac{\partial J(\theta)}{\partial \theta_0} $$

梯度下降是机器学习和深度学习中最常用的优化算法。它属于一阶优化算法,参数更新时只考虑一阶导数。关于二阶泰勒展开的牛顿法,推导思路类似,可参考 《Logistic 回归》牛顿法

梯度下降不一定能够找到全局的最优解,也有可能最终结果是一个局部最优解。当然,如果损失函数是凸函数,梯度下降法得到的解就一定是全局最优解,此时在在损失最小值点梯度会变成零。

4.梯度下降的几个理解误区

4.1.梯度下降的迭代不总是收敛到最小值

在实践应用中,因为各种各样的原因,我们可能很难精确地达到最小值,不过如果能够在最小值附近的平坦区域震荡,并且不会有很大的变化,也可以提前停止迭代,并将这个近似值作为梯度下降的收敛。因为此时的损失值几乎是我们能够达到的最小值,再迭代下去花费代价很大,效果却几乎没有提升,而且,一个近似的收敛值在某种程度上可以提高泛化能力,因此并没有必要追求真正的最小值。通常,当损失值在预定的数字内没有提升的时候我们会停止迭代,例如 10 次或者 20 次迭代。当这种情况发生时,我们就说训练已经收敛了,或者说收敛已经实现了,这个时候梯度下降就真正完成了它的使命。

4.2.梯度下降的真实轨迹

平时我们看到讲解梯度下降的图示中大多标注的是损失函数曲面上的一条轨迹线,类似于那个下山的路线图,所以我们很容易把这个轨迹线理解成梯度下降的轨迹,但这是错误的。梯度下降是对参数的优化,只发生在参数空间,它的作用是使损失函数下降,但其本身并不会涉及在损失函数方向上的移动。真实的梯度下降轨迹如下图所示1

梯度下降算法总结_插图6

在参数空间中,损失函数可以被看作是一个曲面或者是一个超平面(如果参数的维度较低)。梯度下降算法通过迭代更新参数,使损失函数逐渐减小,梯度下降的轨迹可以被理解为在这个参数空间中的路径,其轨迹在参数空间中沿着损失函数等值线的等高线方向移动。所以梯度下降的真实轨迹,可以理解成在优化过程中,损失函数的变化轨迹在参数空间上的投影。

4.3.多参数情况下梯度下降的更新规则

对于多个参数的情况,梯度下降使用偏导数进行梯度计算,由于偏导的计算特性,每一个参数的梯度计算都是各自独立进行的,每一个迭代过程中,多参数各自的梯度计算以及参数更新互不重叠,不会出现先计算完一个参数的梯度更新完再计算第二个。

在梯度下降算法的迭代过程中,通常是先计算所有参数的梯度,然后同时更新所有参数的值。

梯度下降完整的迭代步骤如下:

  1. 初始化参数:设置初始参数值。
  2. 计算梯度:对于每个参数,计算损失函数对该参数的偏导数,得到参数的梯度。
  3. 更新参数:一旦计算完所有参数的梯度,就可以同时更新所有参数的值。更新公式通常为:新参数值 = 旧参数值 – 学习率 * 梯度值。
  4. 计算新的损失函数值:使用更新后的参数计算新的损失函数值。
  5. 判断停止条件:检查是否满足停止条件,例如达到最大迭代次数或损失函数的变化小于预定阈值。
  6. 重复迭代:如果不满足体质条件,从第二步开始重复进行上述步骤,计算所有参数的梯度,然后同时更新所有参数的值,直到满足停止条件。

梯度下降算法总结_插图7

在迭代过程中,同时更新所有参数可以更高效地进行计算,因为可以利用并行计算的优势。此外,同时更新所有参数还可以确保在每次迭代中使用的梯度是在同一个时间点计算得到的,从而保证参数的更新是基于相同的梯度信息。

5.梯度下降算法的三个变种

最基础的梯度下降算法主要有三种变种,它们之间的主要区别在于每个学习步骤中计算梯度时使用的数据量,是对每个参数更新(学习步骤)时的梯度准确性与时间复杂度的折衷考虑,即在准确性和优化速度间做权衡。(在深度学习中,为了适应更复杂的模型结构,衍生出了更多复杂的优化算法,但基本思想大多围绕梯度下降展开的。)

5.1.批量梯度下降(BGD)

批量梯度下降(BGD, Batch gradient descent)是最基本的梯度下降算法,因此也被称为基础梯度下降算法(Vanilla gradient descent),批量梯度下降在对参数执行更新时,在每次迭代中使用所有的样本。即:

$$\theta = \theta – \alpha \cdot \nabla_{\theta}J(\theta)$$

示例代码

主要的优点:

  1. 训练期间,我们可以使用固定的学习率,而不用考虑学习率衰减的问题。
  1. 它具有朝向最小值的直线轨迹,并且如果损失函数是凸的,则保证理论上收敛到全局最小值,如果损失函数不是凸的,则收敛到局部最小值。
  1. 梯度是无偏估计的。样本越多,标准误差就越低。

主要的缺点:

  1. 尽管我们可以用向量的方式计算,但是可能仍然会很慢地遍历所有样本,特别是数据集很大的时候算法的耗时将成为严重的问题。
  1. 学习的每一步都要遍历所有样本,这里面一些样本可能是多余的,并且对更新没有多大贡献。

5.2.随机梯度下降(SGD)

随机梯度下降(SGD,Stochastic gradient descent)也叫增量梯度下降,就是一次次循环下降。 每次迭代只对一个样本 $(x^{(i)},y^{(i)})$执行参数更新,而不是所有样本。因此,学习发生在每个样本上,即:

$$\theta = \theta – \alpha \cdot \nabla_{\theta}J(\theta; x^{(i)};y^{(i)})$$

随机梯度下降需要打乱训练数据集以避免样本预先存在顺序。

示例代码:

为什么叫随机梯度下降?有一个不严格的解释:

如果全部拿到样本再进行下降的话,肯定是直接下降,而且过程很平稳,见下图:

梯度下降算法总结_插图8

如果每拿到一个样本下降一次,用一个样本的梯度去代替整体样本的梯度,因此梯度中夹杂了个体样本的噪声,就会带有随机震荡性(随机性),不过总体趋势依然是下降的,见下图:

梯度下降算法总结_插图9

有结论表明,当我们慢慢降低学习速率时,SGD 表现出与批量梯度下降很相似的收敛效果,几乎肯定会分别收敛到非凸和凸优化的局部或全局最小值。2

优点:

  1. 更新频次快,优化速度更快;
  1. 可以在线优化(可以处理动态产生的新样本,这个在一些在线生产坏境非常重要);
  1. 一定的随机性导致有几率跳出局部最优(随机性来自于用一个样本的梯度去代替整体样本的梯度)。

缺点:

  1. SGD 的随机性给学习过程增加了更多的噪声,并且学习过程不断以高方差的方式频繁更新,导致目标函数大幅波动;
  1. 随机性可能导致收敛复杂化,即使到达最优点仍然会进行过度优化,因此 SGD 得优化过程相比 BGD 充满动荡。

5.3.小批量梯度下降(MBGD)

小批量梯度下降(Mini-batch gradient descent ,MBGD)有时也会写作小批量随机梯度下降(Mini-batch stochastic gradient descent,mini-batch SGD),实践中往往也把 mini-batch SGD 简称 SGD,所以需要注意的是,有些文献和资料中,会用 SGD 代表 mini-batch SGD,而不是真的 SGD(随机梯度下降)。

为了克服上述两个变种的缺点,所以人们提出了小批量梯度下降,MBGD 算是上面两个变种的折中。在每一次更新参数时,既不使用所有样本,也不是一个样本一个样本地进行更新,而是使用一部分样本来进行更新。

即:

$$\theta = \theta – \alpha \cdot \nabla_{\theta}J(\theta; x^{(i:i+n)};y^{(i:i+n)})$$

与随机梯度下降一样,小批量梯度下降也需要打乱训练数据集以避免样本预先存在顺序结构,另外还要根据批量的规模将训练数据集分为 b 个小批量。如果训练集大小不能被批量大小整除,则将剩余的部分单独作为一个小批量。当批量大小 b 等于训练样本数 m 时候,这种方法就相当于批量梯度下降。

示例代码:

批量的大小我们可以调整,习惯上选 2 的幂次方,例如 32、64、128、256、512 等。其背后的原因是一些像 GPU 这样的硬件也是以 2 的幂次方的批量大小来获得更好的运行时间。

MBGD 综合了 BGD 和 SGD 的一些特性,可以带来更好的效果,所以 MBGD 也是应用最多的梯度下降变种,也成为机器学习迭代训练模型的一个基本方法。

主要的优点:

  1. 更快的收敛速度:相对于 BGD,MBGD 通常具有更快的收敛速度。这是因为 MBGD 在每次迭代时仅使用一小批量的样本来计算梯度和更新模型参数。与使用整个训练集进行计算相比,这样的计算开销更小,可以更频繁地更新模型参数,从而加速收敛过程。而且而相对于 SGD,模型参数更新时的动荡变小,收敛过程更稳定,也降低了收敛难度;
  2. 更好的泛化能力:MBGD 可以在一定程度上增加模型的泛化能力。由于 MBGD 在每次迭代中使用的是部分样本,而不是单个样本(SGD)或整个训练集(BGD),它可以更好地逃离局部最小值,并减少过拟合的风险。通过引入一定的随机性和噪声,MBGD 有助于模型更好地泛化到未见过的数据;
  3. 更好的计算效率:相对于 BGD,MBGD 在计算效率方面更具优势。虽然 MBGD 需要处理比 SGD 更多的样本,但与 BGD 相比,它仍然具有更小的计算开销。特别是在大型数据集上,MBGD 可以平衡计算资源的利用和模型性能的提升;
  4. 更好的收敛稳定性:MBGD 相对于 SGD 具有更好的收敛稳定性。SGD 基于单个样本进行梯度计算,因此其梯度估计可能更加嘈杂和不稳定。相比之下,MBGD 使用一小批量样本的平均梯度,可以减少梯度估计的方差,并提高收敛的稳定性。

主要缺点:

  1. 多了一个超参数,需要设置合适的批大小(Batch_Size),甚至需要进行调优;
  2. 对于小型数据集可能没有显著的优化效果;
  3. 容易收到批数据的噪声影响,尤其是接近最小值的时候,噪声导致的振荡可能会影响收敛;
  4. MBGD 的收敛速度和性能还受到学习率和其他超参数的选择的影响。

三种变种算法的简单总结对比

每次迭代更新:

  • BGD 拿到所有数据并把所有样本的梯度加起来,然后下降。
  • SGD 遍历样本,每拿到一个样本就计算一次梯度,然后下降一次;
  • MSGD 积累一部分样本后,计算这些样本的平均梯度,作为更新方向下降一次。

三种梯度下降变种方法朝向最小值的轨迹

梯度下降算法总结_插图10

从上图可以清楚地看出,SGD 波动最大,MBGD 次之,BGD 波动最小。

6.梯度下降几个挑战

6.1.学习率

学习率(learning rate)是梯度下降算法中的一个重要超参数,它决定了参数在每次更新时的步长。选择过大的学习率可能导致算法发散(如下图),而选择过小的学习率则可能导致算法收敛缓慢。合适的学习率选择是一个关键的挑战,尤其在复杂模型的参数优化中,学习率的设定影响梯度下降的整体效果,甚至于关系着模型的最终训练效果,灵活地设定学习率非常重要,我单独写了一篇文章来介绍学习率的一些设定策略,详情可参考 《梯度下降学习率的设定策略》

梯度下降算法总结_插图11

6.2.特征差异较大

当不同特征的取值范围差异较大时,梯度下降算法可能会受到影响。具有较大取值范围的特征可能会主导损失函数,而对于取值范围较小的特征,其梯度对参数的更新贡献较小,这不符合实际情况,因为样本数值的大小和贡献大小是没有关系的。而且如果多个特征的取值范围差异极大,也会造成训练得到的参数在数量级上差别也很大,这样会使梯度下降参数优化过程变得非常困难,很容易损失函数振荡导致收敛缓慢或无法收敛到最优解。所以在很多情况下,需要先用归一化或标准化的方法对特征进行缩放,让不同的特征保持相同的范围。

下图是不进行特征缩放和进行特征缩放的对比,可见在进行特征缩放前,损失函数和参数的关系可能是一个非常狭长的椭圆形,梯度下降的轨迹会呈现 Z 形振荡,这样会使迭代很慢,而标准化后特征缩放为相同级别,损失函数和参数的关系图较为规整,收敛路径更加平缓直接。

梯度下降算法总结_插图12

6.3.局部最小值

我们前面看到的损失函数图像大都很漂亮,很规则像碗一样,这些损失函数是凸函数,梯度下降也很容易找出最小值点。但现实中的那些解决实际问题的模型,尤其是深层神经网络,大部分损失函数不是凸函数,而且通常情况下特征维度比较高,其损失函数的有非常多的局部最小值,梯度下降的一大挑战是会把这些局部最小值误判为全局最优解,最终收敛到局部最小值。

梯度下降算法总结_插图13

6.4.鞍点

另外一个挑战是鞍点(Saddle Point),顾名思义,就是像马鞍一样的地方,虽然它在一个方向(X)上是最小值,但它在另一个方向(Y)上是局部最大值,如果损失函数的等值线在 X 方向上更平坦,梯度下降将在 X 方向上来回振荡且不会沿 Y 方向继续下降,这就会造成收敛到最小值的错觉。梯度下降的驱动力是梯度,但像局部最小值和鞍点处,都可能存在着梯度为零的情况,一旦到达梯度为零的区域,无论极小值的质量如何,梯度下降的收敛进度就会困在那里,几乎不可能从里面逃脱。

梯度下降算法总结_插图14

7.深度学习中的各种优化算法

局部最小值和鞍点在深度学习模型的优化过程中很常见,为了解决这类问题,业界也对基础的梯度下降算法进行了一系列改进,发展衍生出了一系列相关的优化策略和技巧,其中有些逐渐成为更为实用的梯度下降优化算法,也称优化器(Optimizer)。

优化算法大概经历了 SGD -> SGDM -> NAG ->AdaGrad -> AdaDelta ->RMSProp-> Adam -> Nadam->AdamW 这样的发展历程。

7.1.Momentum

梯度下降在梯度为零的地方会失去动力,容易陷入到局部最小值区域停止参数更新。我们更希望在梯度为零的区域,梯度下降依然有一定的动力去尝试突破困局。借鉴物理学中惯性的概念,在梯度下降中引入动量(Momentum),成为一种带动量的随机梯度下降(SGD with momentum,SGDM/SGD-M)优化算法。

和惯性类似,简单理解动量,就是让梯度下降在没有阻力的时候进行能量累积,它的动量会越来越大,如果遇到了阻力,速度会变慢,但不是直接停止失去动力,所以在梯度为零的地方带动量的梯度下降不会立刻停止参数更新,而是利用积累的动量进行进一步的尝试,这样便有跳出局部最小值的机会。

来看公式,SGD-M 在 SGD 基础上引入了一阶动量,中间多了一步:

$$\nu_t = \gamma\nu_{t-1} + \eta \nabla_{\theta}J(\theta)$$

$$\theta = \theta – \nu_t$$

可以看出,动量梯度下降是通过维护一个动量向量(momentum vector)$v$($v_t$和 $v_{t-1}$)来实现的,SGD-M 引入的是一阶动量,当前动量向量 $v_t$是由前一个时刻的动量向量 $v_{t-1}$乘以一个衰减率 $\gamma$ 加上当前时刻的梯度,前一个动量向量累积了历史动量的信息,动量其实就各个时刻梯度值的指数加权移动平均值。

衰减因子 $\gamma$ 决定了过去梯度值的权重衰减程度,较大的 $\gamma$ 值表示较少的衰减,更重视过去的梯度值;较小的 $\gamma$ 值表示更快的衰减,更加关注当前的梯度值。$\gamma$ 常被设定为 0.9 的经验值,这就意味着更新过程中较大程度上保留此前积累的更新的方向,而当前更新梯度则用于微调最终的更新方向。这样,就可以在一定程度上增加稳定性,从而可以更快地学习,并且还具有摆脱局部优化的能力。考虑极端情况,如果 $\gamma$ 为 0,则等同于普通梯度下降,$\gamma$ 为 1,可能会出现来回摇摆的情况,就像一颗重力小球在无摩擦完全光滑的碗中来回摇摆(假设学习率相当小),很难停下来。所以衰减因子通常会选择在 0.8~0.9 范围,这样可以增加点摩擦力,让梯度下降能够最终减慢并停止。

指数加权移动平均值(Exponential Weighted Moving Average,EWMA)或指数加权平均值(Exponential Weighted Average,EWA)

这两个术语在实际中经常被用来描述相同的概念。

指数加权移动平均值是一种平滑时间序列数据的方法,通过对数据进行指数加权处理,使得最近的观测值具有更高的权重,而过去的观测值则具有较低的权重。这种加权方法可以减少数据中的噪声和波动,同时保留数据的趋势信息。

指数加权移动平均值的计算,针对序列数据,比如 $t$ 时刻的观测值为 $x(t)$,那么评估 $t$ 时刻的移动平均值为:

$$v(t)\leftarrow\beta\cdot v(t-1)+(1-\beta)\cdot x(t)$$

通过对每个新的观测值进行加权平均来更新平均值。每个观测值的权重由衰减因子(也称为平滑因子)决定,衰减因子越大,对之前的观测值的权重越高,衰减得越慢。

一阶动量和二阶动量

在优化算法中,常引入动量实现一些自适应机制,动量分为一阶动量和二阶动量。一阶动量用一阶矩计算,具体是过去各个时刻梯度的线性组合,来控制模型更新的方向;二阶动量用二阶矩计算,具体是各个时刻梯度的平方的线性组合,用来控制调整学习率。动量迭代过程中主要是通过指数加权移动平均来实现线性组合,因为梯度下降的算法特性,并不要求线性权值之和为 1,只要是线性组合即可,所以只设计一个权值作为衰减因子,控制对过去信息的信任度。

一阶动量(First Moment)通常指的是梯度的一阶矩,也称为梯度的平均值。在梯度下降算法中,一阶动量可以用来指示梯度的方向,并在参数更新时提供动量。”SGD with momentum” 中的动量就是一阶动量的一种形式,它通过在梯度更新中引入先前梯度的指数移动平均,以在参数更新中提供更平滑的路径。

二阶动量(Second Moment)通常指的是梯度的二阶矩,也称为梯度的方差或协方差矩阵。二阶动量可以提供关于梯度的更丰富信息,包括描述梯度的方差或曲率,梯度中不同维度之间的相关性。常用的计算方式是梯度的平方的指数移动平均。二阶动量被用来自适应地调整学习率或者参数更新的步长。在自适应学习率算法常用,如 Adam 和 RMSprop。

一阶动量和二阶动量在优化算法中起到不同的作用。一阶动量主要关注梯度的方向,可以帮助优化算法更快地收敛,并减少震荡。而二阶动量则提供了关于梯度的额外信息,特别是梯度的方差和相关性,可以用来调整学习率或参数更新的步长,以适应不同的优化问题和数据特征。

由上可以发现引入动量的另外一个好处是,因为主要由历史积累的动量主导下降方向,当前梯度的影响变弱,抗噪能力变强,在一定程度上增加了优化过程的稳定性,从而减少振荡加快收敛,对比如下图:

梯度下降算法总结_插图15

优缺点

  • 优点

    相比普通的梯度下降,动量梯度下降有以下优势:

    1. 动量有机会逃离局部最小值

      因为动量可能会将其推出局部最小值,缓解了 SGD 在局部最优点梯度为 0,无法持续更新的问题和振荡幅度过大的问题。

    1. 动量梯度下降收敛更快,收敛路径更加直接稳定

      因为动量的累积,如果前期梯度下降方向差别不大,带动量的梯度下降速度会更快。

      动量有移动指数加权平均的加持,整体优化迭代更加稳定,抗噪能力加强,振荡降低,下降路径也更加平滑,收敛速度更快。

  • 缺点

    1. 因为动量的关系,容易在最优解附近震荡。
    1. 不过如果局部沟壑比较深,动量加持用完了,依然会困在局部最小值区域中来回振荡。

7.2.NAG

NAG(Nesterov accelerated gradient)即 Nesterov 加速梯度,是由计算机科学家 Yurii Nesterov(尤里·涅斯捷罗夫)于 1983 年提出的。NAG 也被称为 Nesterov momentum 或 Nesterov momentum gradient descent。

NAG 实际上是对 Momentum 方法的进一步改进,动量有一个问题是在到达终点时不知道减速,如果在终点处还有太多能量,就会出现下图这种参数在最优解附近震荡,可能需要较长时间才能停下来。

梯度下降算法总结_插图16

NAG 就是用来解决这个问题的,它的主要思想是在更新梯度之前,先根据当前的动量进行一步 “预测”,然后计算梯度并利用这个 “预测” 进行参数更新。我们知道在时刻 $t$的主要下降方向是由累积动量决定的,当前时刻的梯度方向只是微调的作用,那与其看当前梯度方向,不如先看看如果跟着累积动量走了一步,那个时候再怎么走。因此,NAG 不计算当前位置的梯度方向,而是计算如果按照累积动量走了一步,那个时候的下降方向:

$$\nu_t = \gamma\nu_{t-1} + \eta \nabla_{\theta}J(\theta-\gamma\nu_{t-1})$$

$$\theta = \theta – \nu_t$$

很明显,同带动量的 SGD 相比,梯度不是根据当前位置 $\theta$ 计算出来的,而是在移动之后的位置($\theta-\gamma\nu_{t-1}$)计算梯度,首先,它使用当前的动量来计算下一个位置的梯度。然后,通过将当前动量与下一个位置的动量进行线性组合,得到一个估计的动量,这个估计动量可以看作是对下一个位置动量的预测。然后,使用这个估计动量来计算参数的更新方向和大小。

就是因为每次更新都有下一个位置的预估动量参与,这就实现了一种自适应的动量调整策略,如果前方的梯度和当前梯度目标一致,那就直接大步迈过去; 如果前方梯度同当前梯度不一致,那就减小步子慢慢更新。虽然 NAG 没有直接调整学习率,但某种程度上实现了自适应学习速率的效果。NAG 的自适应的动量调整策略,使其能够更好地适应不同的目标函数形状。

下面是一个过程示意图:

梯度下降算法总结_插图17

动量法首先计算当前梯度(图中的小蓝色向量),然后在更新累积梯度(updated accumulated gradient)方向上大幅度的跳跃(图中的大蓝色向量)。与此不同的是,NAG 首先在先前的累积梯度(previous accumulated gradient)方向上进行大幅度的跳跃(图中的棕色向量),评估这个梯度并做一下修正(图中的红色向量),这就构成一次完整的 NAG 更新(图中的绿色向量)。

优缺点

  • 优点

    相比 SGD-M,动量梯度下降有以下优势:

    1. 更快的收敛速度:NAG 通常比 SGD with momentum 更快地收敛到最优解。这是因为 NAG 在更新参数时会预先计算下一个位置的梯度,从而更准确地朝向最优解的方向更新参数。
    2. 更好的抑制震荡:SGD with momentum 在参数更新时,会根据当前梯度和上一次的动量来更新参数。这可能导致参数在最优解附近震荡,减缓收敛速度。NAG 通过在计算梯度时考虑动量项,可以更好地抑制这种震荡现象。
    3. 更好的适应性:NAG 通过估计动量项,可以更好地适应不同的目标函数形状。在目标函数存在弯曲和窄谷的情况下,NAG 通过预估动量能够更快地调整学习速率,并更精确地更新参数。
  • 缺点

    1. 高计算成本:相对于基本的随机梯度下降(SGD)算法,NAG 需要更多的计算开销。这是因为它需要在每次参数更新之前计算下一个位置的梯度,这涉及到额外的梯度计算操作。在大规模数据集和复杂模型的情况下,这可能会导致额外的计算负担。
    2. 自适应能力弱:NAG 的自适应能力是通过调节动量来实现的,只是实现了加速和控制,各个参数的学习速率也是统一的,这种自适应能力较弱,面对高维复杂模型效果非常有限。

7.3.AdaGrad

SGD 系列的都没有用到二阶动量。二阶动量的出现,才意味着 “自适应学习率” 优化算法时代的到来。SGD 及其变种以同样的学习率更新每个参数,但深度神经网络往往包含大量的参数,这些参数并不是总会用得到。对于经常更新的参数,我们已经积累了大量关于它的知识,不希望被单个样本影响太大,希望学习速率慢一些;对于偶尔更新的参数,我们了解的信息太少,希望能从每个偶然出现的样本身上多学一些,即学习速率大一些。

自适应梯度算法(Adaptive Gradient algorithm,AdaGrad)引入了二阶动量,实现了对每个参数维度学习率的自适应调节,因此 Adagrad 非常适用于稀疏数据。

Dean 等人发现 Adagrad 能够大幅提高 SGD 的鲁棒性,并在 Google 用其训练大规模神经网络,这其中就包括在 YouTube 中学习识别猫。除此之外,Pennington 等人用 Adagrad 来训练 GloVe 词嵌入,因为罕见的词汇需要比常见词更大的更新。

AdaGrad 算法就是将每一个参数的每一次迭代的梯度取平方累加后在开方,用全局学习率除以这个数,作为学习率的动态更新。对于不同的参数动态地采取不同的学习率,让目标函数更快的收敛。为了简洁,我们用 $g_{t}$来表示 t 时刻的梯度,$g_{t,i}$就是目标函数的偏导数:

$$g_{t,i}=\nabla_{\theta}J(\theta_{t,i})$$

SGD 在在每个时刻 t 对参数 $\theta_{i}$的更新为:

$$\theta_{t+1,i}=\theta_{t,i}-\eta \cdot g_{t,i}$$

Adagrad 修改了 t 时刻对于每个参数 $\theta_{i}$的学习率 $\eta$:

$$\theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{G_{t,ii}+\epsilon}} \cdot g_{t,i}$$

其中,

  • $G_{t}\in R^{d \times d}$是对角矩阵,AdaGrad 算法维护了一个累积梯度平方和的对角矩阵 $G_t$来实现二阶动量,每一个对角元素 $G_t^{(i,i)}$ 是 $\theta_{i}$在时刻 t 之前累积的梯度平方和,用公式表示为:

    $$G_t^{(i,i)}=\sum_{\tau=1}^t(g_\tau^{(i)})^2$$

    在迭代中,$G_t$的更新公式为:

    $$G_t=G_{t-1}+g_t\odot g_t$$

    其中,$\odot$ 表示元素逐元素相乘。

  • 一般为了避免分母为 0,会在分母上加一个小的平滑项,用符号 $\epsilon$表示,通常为 $10^{-8}$ 左右。因此 $\sqrt{G_{t}+\epsilon} $恒大于 0,而且参数更新越频繁,二阶动量越大,学习率就越小。有趣的是,如果去掉开方操作,算法性能会大幅下降。

这里之所以使用对角矩阵,主要是出于降低计算复杂度考虑的,使用对角矩阵可以更高效率地计算平方根和倒数。

为了看得更清楚,上式展开式这样的:

梯度下降算法总结_插图18

优缺点

  • 优点

    1. 自适应学习率:AdaGrad 算法根据参数的历史梯度信息来自适应地调整学习率。它会为梯度较大的参数使用较小的学习率,而为梯度较小的参数使用较大的学习率。这使得算法能够更好地处理不同参数的变化范围,加快收敛速度。
    2. 无需手动调整学习率:相对于传统的梯度下降算法,AdaGrad 算法不需要手动调整学习率。它会根据参数的历史梯度自动进行调整,减少了参数调优的工作量。
    3. 适用于稀疏数据:AdaGrad 算法对于稀疏数据的处理效果较好。由于稀疏数据中只有少量的非零梯度,AdaGrad 能够根据这些非零梯度自适应地调整学习率,更准确地更新参数。
  • 缺点

    1. 累积梯度平方和:AdaGrad 算法累积了参数历史上的梯度平方和,因为 $\sqrt{G_{t}+\epsilon}$是单调递增的,这意味着随着训练的进行,累积的平方梯度会越来越大。这可能导致学习率过早地衰减,甚至会使得学习率单调递减至 0,使得算法在后期训练中收敛较慢甚至停止学习。
    2. 不适用于非凸问题:AdaGrad 算法在处理非凸问题时可能会遇到困难。由于累积梯度平方和的缘故,学习率会随着训练的进行逐渐降低,这使得算法在非凸问题中容易陷入局部最优解。
    3. 参数依赖性:AdaGrad 算法的性能对于初始学习率和全局学习率的选择较为敏感。选择不当的初始学习率和全局学习率可能导致算法收敛缓慢或不稳定。

7.4.AdaDelta

由于 AdaGrad 单调递减的学习率变化过于激进,考虑一个改变二阶动量计算方法的策略:不累积全部历史梯度,而只关注过去一段时间窗口的下降梯度。这也就是 AdaDelta 名称中 Delta 的来历。Adadelta 是 Adagrad 的扩展,旨在帮助缓解后者学习率单调下降的问题。

借鉴动量中的方式,AdaDelta 也用指数移动平均值来统计之前时刻的梯度平方线性组合来计算二阶累积动量:

$$E[g^2]_{t}=\gamma E[g^2]_{t-1}+(1-\gamma) g_{t}^2$$

其中 $\gamma$类似于动量中的衰减因子,大约是 0.9。

在 Adagrad 中,参数变化向量 $\Delta \theta_{t}$是:

$$\Delta \theta_{t}=-\frac{\eta}{\sqrt{G_{t}+\epsilon}}\cdot g_{t,i}$$

现在用 $E[g^2]_{t}$简单代替原来的对角矩阵 $G_{t}$:

$$\Delta \theta_{t}=-\frac{\eta}{\sqrt{E[g^2]_{t}+\epsilon}}\cdot g_{t,i}$$

将分母简记为 RMS,表示梯度的均方根误差:

$$\Delta \theta_{t}=-\frac{\eta}{RMS[g]_{t}}\cdot g_{t}$$

根据作者所说,迭代更新过程中,定义指数衰减均值,代替梯度平方:

$$E[\Delta \theta^2]_{t}=\gamma E[\Delta \theta^2]_{t-1}+(1-\gamma)\Delta \theta_{t}^2$$

均方根误差变为:

$$RMS[\Delta \theta]_{t}=\sqrt{E[\Delta \theta^2]_{t}+\epsilon}$$

$RMS[\Delta \theta]_{t}$是未知的,我们近似用前一个时间步 RMS 值来估计:

$$\Delta \theta_{t}=-\frac{RMS[\Delta \theta]_{t-1}}{RMS[g]_{t}}g_{t}$$ $$\theta_{t+1}=\theta_{t}-\Delta \theta_{t}$$

经过近似牛顿迭代法之后,从更新规则中消去了全局学习率,所以 Adadelta 不用设置学习率。

优缺点

  • 优点

    1. 无需手动设置学习率:AdaDelta 算法不需要手动设置全局学习率,而是通过自适应学习率的方式来调整参数的更新步长。这样可以减少对学习率的敏感性,简化了超参数调整的过程。
    2. 自适应性:AdaDelta 算法能够根据参数的梯度情况自适应地调整学习率。对于梯度较大的参数,会采用较小的学习率,从而避免过大的参数更新;对于梯度较小的参数,会采用较大的学习率,加快参数收敛的速度。
    3. 解决学习率衰减过快的问题:AdaDelta 通过引入累积更新平方和的概念,控制学习率的衰减速度。相比于 AdaGrad 算法,AdaDelta 的学习率衰减更加平缓,避免了学习率过快衰减导致训练过程过早停止的问题。
    4. 减少超参数的数量:相对于其他优化算法,AdaDelta 算法的超参数数量较少。只需要设置一个衰减系数 $\rho$和一个小常数 $\epsilon$,减少了调参的复杂性。
  • 缺点

    1. 算法解释性差:AdaDelta 算法的数学公式较为复杂,包括累积梯度平方和和累积更新平方和的引入方式,会增加算法的理解和解释的难度。
    2. 计算复杂度高:AdaDelta 需要维护额外的累积梯度平方和和累积更新平方和这两个变量。在每次参数更新时,AdaDelta 算法需要计算这两个累积和,并且还需要计算用于参数更新的自适应学习率。这些计算涉及对梯度和平方梯度的累积、平均和开方等操作。特别是在处理大规模数据和高维参数空间时,这些计算的开销可能会变得更加显著。

7.5.RMSProp

RMSProp 算法(Hinton,2012)修改 AdaGrad 以在非凸情况下表现更好,它改变梯度累积为指数加权的移动平均值,从而丢弃距离较远的历史梯度信息。RMSProp 与 Adadelta 的移动均值更新方式十分相似:

$$E[g^2]_{t}=0.9 E[g^2]_{t-1}+0.1 g_{t}^2$$

RMSProp 参数更新公式如下,其中 $\eta$是学习率, $g_{t}$是当前参数的梯度

$$\theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{E[g^2]_{t}+\epsilon}}g_{t}$$

RMSprop 将学习速率除以梯度平方的指数衰减平均值。Hinton 建议 $\gamma$设置为 0.9,默认学习率 $\eta$为 0.001。

优缺点

和 AdaDelta 非常类似,可自适应调整学习率,且解决了学习率衰减过快的问题,更新算法也容易理解,不过 RMSprop 并没有摆脱对于全局学习率的依赖。

7.6.Adam

Adam 最开始是由 OpenAI 的 Diederik Kingma 和多伦多大学的 Jimmy Ba 提出的。Adam 使用动量和自适应学习率来加快收敛速度。SGD-M 在 SGD 基础上增加了一阶动量,AdaGrad 和 AdaDelta 在 SGD 基础上增加了二阶动量(二阶矩估计)。把一阶动量和二阶动量都用起来,就是 Adam 了——Adaptive + Momentum。

SGD 的一阶矩的估计,即 mean 均值:

$$m_{t}=\beta_{1} \cdot m_{t-1}+(1-\beta_{1}) \cdot g_{t}$$

加上 AdaDelta 的二阶动量,二阶距的估计,即 variance,和方差类似,都是二阶距的一种:

$$v_{t}=\beta_{2} \cdot v_{t-1}+(1-\beta_{2})\cdot g_{t}^2$$

对 mean 和 var 进行校正,因为 mean 和 var 的初始值为 0,所以它们会向 0 偏置,这样处理后会减少这种偏置影响。

$$\hat m_{t}=\frac{m_{t}}{1-\beta_{1}^t}$$ $$\hat v_{t}=\frac{v_{t}}{1-\beta_{2}^t}$$

Adam 参数更新公式如下:

$$\theta_{t+1}=\theta_{t}-\eta \cdot \hat m_{t}/(\sqrt{\hat v_{t}}+\epsilon)$$

其中 $\eta$是学习率, $g_{t}$是当前参数的梯度,$\beta_{1}$为一阶矩估计的指数衰减率(如 0.9),$\beta_{2}$二阶矩估计的指数衰减率(如 0.999),前者控制一阶矩估计,后者控制二阶矩估计。该超参数在稀疏梯度(如在 NLP 或计算机视觉任务中)中应该设置为接近 1 的数,$\beta_{1}^t$和 $\beta_{2}^t$是 $\beta_{1}$和 $\beta_{2}$的 t 次方

优缺点

  • 优点

    1. 通过一阶动量和二阶动量,有效控制学习率步长和梯度方向,防止梯度的振荡和在鞍点的静止。
    1. 实现简单,计算高效,对内存需求少
    1. 参数的更新不受梯度的伸缩变换影响
    2. 超参数具有很好的解释性,且通常无需调整或仅需很少的微调
    3. 更新的步长能够被限制在大致的范围内(初始学习率)
    4. 能自然地实现步长退火过程(自动调整学习率)
    5. 很适合应用于大规模的数据及参数的场景
    6. 适用于不稳定目标函数
    7. 适用于梯度稀疏或梯度存在很大噪声的问题

    Adam 在很多情况下算作默认工作性能比较优秀的优化器。

缺点

  1. 可能不收敛:二阶动量是固定时间窗口内的累积,随着时间窗口的变化,遇到的数据可能发生巨变,使得 $V_{t}$可能会时大时小,不是单调变化。这就可能在训练后期引起学习率的震荡,导致模型无法收敛。

    修正的方法。由于 Adam 中的学习率主要是由二阶动量控制的,为了保证算法的收敛,可以对二阶动量的变化进行控制,避免上下波动。

    $$v_{t}=max(\beta_{2} \cdot v_{t-1}+ (1-\beta_{2})g_{t}^2,v_{t-1})$$

  1. 可能错过全局最优解:自适应学习率算法可能会对前期出现的特征过拟合,后期才出现的特征很难纠正前期的拟合效果。后期 Adam 的学习率太低,影响了有效的收敛。

7.7.Adamax

AdaMax 是 Adam 的一种变体,此方法对学习率的上限提供了一个更简单的范围。公式上的变化如下:

$$v_{t}=\beta_{1} \cdot m_{t-1}+(1-\beta_{1}) \cdot g_{t}$$

我们可以将此推广到 $l_{p}$范数。

$$v_{t}=\beta_{2}^{p}v_{t-1}+(1-\beta_{2}^{p})|g_{t}|^p$$

当 $p$ 非常大的时候通常会导致数值上的不稳定,这也是实际中通常使用 $l_{1}$和 $l_{2}$的原因。然而,$l_{\infty}$通常也会比较稳定。因此,作者提出了 AdaMax,显示了结合了 $v_{t}$和 $l_{\infty}$也能够收敛到下面的更稳定的值。为了避免与 Adam 混淆,我们使用 $u_{t}$来表示无限范数约束的 $v_{t}$:

$$u_{t}=beta_{2}^{infty}v_{t-1}+(1-beta_{2}^{infty})|g_{t}|^{infty} = max(beta_{2} cdot v_{t-1},|g_{t}|) $$

现在可以将此加进 Adam 的更新规则里,用 $u_{t}$代替 $\sqrt{\hat v_{t}}+\epsilon$,得到 AdaMax 的更新规则:

$$\theta_{t+1}=\theta_{t}-\frac{\eta}{u_t} \hat m_{t}$$

其中 $u_{t}$依赖于 max 操作,这不像 Adam 中的 $m_{t}$和 $v_{t}$那样容易趋于 0,这也是我们不需要为 $u_{t}$计算偏差纠正的原因。建议的默认值是 $\eta=0.002$,$\beta_{1}=0.9$和 $\beta_{2}=0.999$

7.8.Nadam

Adam 可以被看作是融合了 RMSProp 和 momentum,RMSprop 贡献了历史平方梯度的指数衰减的平均值 $v_{t}$,而动量则负责历史梯度的指数衰减平均值 $m_{t}$,Nadam 在 Adam 的基础上加入了一阶动量的累积,即 Nesterov + Adam = Nadam,为了把 NAG 融入到 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}$$

其中 $\gamma$是动量的衰减项,$\eta$是步长,J 是目标函数。将 $m_{t}$代入上面的第三个式子展开得到:

$$\theta_{t+1}=\theta_{t}-(\gamma m_{t-1}+\eta g_{t})$$

动量包括在前面的动量向量方向上的一步和在当前梯度方向上的一步。

NAG 允许我们在计算梯度之前通过动量步长更新参数,从而在梯度方向上执行更精确的步长。然后我们只需要更新梯度 $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 :与应用动量步骤两次不同的是:一次用来更新梯度 $g_{t}$和一次用来更新参数 $\theta_{t+1}$,直接对当前参数应用一个向前看的(look-ahead)动量向量:

$$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}$来向前看, 为了把 Netsterov Momentum 融入到 Adam,我们把旧的动量向量用新的动量向量代替,Adam 的更新规则为(注意不用修改 $\hat v_{t}$):

$$m_{t}=\beta_{1}m_{t-1}+(1-\beta_{1})g_{t}$$ $$\hat m_{t}=\frac{m_{t}}{1-\beta_{1}^t}$$ $$\theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{\hat v_{t}}+\epsilon}\hat m_{t}$$

上式子展开为:

$$\theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{\hat v_{t-1}}+\epsilon}(\frac{\beta_{1}m_{t-1}}{1-\beta_{1}^t}+\frac{(1-\beta_{1})g_{t}}{1-\beta_{1}^t})$$

$$\theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{\hat v_{t-1}}+\epsilon}(\beta_{1}\hat m_{t-1}+\frac{(1-\beta_{1})g_{t}}{1-\beta_{1}^t})$$

这个方程跟 momentum 的展开式类似,用 $\hat m_{t-1}$替换 $\hat m_{t-2}$,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_{1}^t})$$

7.9.AMSGrad

AMSGrad 在 ICLR 2018 年被提出来,并获得了最佳论文。AMSGrad 是一个随机梯度下降优化方法,它试图解决基于 Adam 的优化器的收敛问题。AMSGrad 使用最大化过去平方梯度 $v_{t}$来更新参数,而不是使用指数平均,这样就降低了指数衰减平均,造成重要历史信息快速丢失的影响。

$$m_{t}=\beta_{1}m_{t-1}+(1-\beta_{1})g_{t}$$ $$v_{t}=\beta_{2}v_{t-1}+(1-\beta_{2})g_{t}^2$$

上面的两个公式跟 Adam 是一样的,求的是一阶矩和二阶矩,$g_{t}$ 是当前参数的梯度,$\beta_{1}$为一阶矩估计的指数衰减率,$\beta_{2}$是二阶矩估计的指数衰减率,前者控制一阶矩估计,后者控制二阶矩估计。

$$\hat v_{t}=max(\hat v_{t-1},v_{t})$$

上式求过去最大的平方梯度 $\hat v_{t}$,参数的更新公式如下:

$$\theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{\hat v_{t}}+\epsilon}m_{t}$$

从上面的公式可以看出,参数更新公式与 Adam 没有啥区别,但是求 $\hat v_{t}$有区别。AMSGRAD 不增加步长,避免了 ADAM 和 RMSPROP 算法的缺陷。

7.10.AdaBound

AdaBound 算法训练速度比肩 Adam,性能媲美 SGD。SGD 现在后期调优时还是经常使用到,但 SGD 的问题是前期收敛速度慢。SGD 前期收敛慢的原因: SGD 在更新参数时对各个维度上梯度的放缩是一致的,并且在训练数据分布极不均很时训练效果很差。而因为收敛慢的问题应运而生的自适应优化算法 Adam、AdaGrad、RMSprop 等,但这些自适应的优化算法虽然可以在训练早期展现出快速的收敛速度,但其在测试集上的表现却会很快陷入停滞,并最终被 SGD 超过。

具体做法是对学习率进行动态裁剪,在这一设置下,在训练早期由于上下界对学习率的影响很小,算法更加接近于 Adam;而随着时间增长裁减区间越来越收紧,模型的学习率逐渐趋于稳定,在末期更加贴近于 SGD。

$$m_{t}=\beta_{1}m_{t-1}+(1-\beta_{1})g_{t}$$

$$v_{t}=\beta_{2}v_{t-1}+(1-\beta_{2})g_{t}^2$$

上面的两个公式跟 Adam 是一样的,求的是一阶矩和二阶矩,$g_{t}$ 是当前参数的梯度,$\beta_{1}$为一阶矩估计的指数衰减率,$\beta_{2}$是二阶矩估计的指数衰减率,前者控制一阶矩估计,后者控制二阶矩估计。

$$V_{t}=diag(v_{t})$$ $$\hat \eta_{t}=Clip(\alpha/\sqrt(V_{t}),\eta_{l}(t),\eta_{u}(t))$$ $$\eta_{t}=\hat \eta_{t}/\sqrt{t}$$

上述 3 个公式是把学习率限定在 $[\eta_{l},\eta_{u}]$之间,这个公式是对 SGD+momentum 和 Adam 的一般化,其中 $\eta_{l}$=$\eta_{u}=\alpha^*$ 时,就变成了 SGD+momentum 的公式了,因为学习率固定了参数只与一阶动量有关;如果 $\eta_{l}=0$和 $\eta_{u}=\infty $整个公式就变成了 Adam,因为 Adam 既与一阶矩有关也与二阶矩有关。其中 $\eta_{l}^t$是一个非递减函数,从 0 逐渐的收敛到 $\alpha$,而 $\eta_{u}^t$ 是一个非递增函数,从 $\infty$逐渐收敛到 $\alpha$。

$$\theta_{t+1}=\theta_{t}-\eta_{t} \odot m_{t}$$

在这种设置下,AdaBound 在最开始表现的像 Adam,因为最开始学习率的边界对更新公式影响很小,渐渐的表现的像 SGD+momentum,因为学习率逐渐被限制住了。

7.11.AdamW

L2 正则化是减少过拟合的经典方法,它会向损失函数添加由模型所有权重的平方和组成的惩罚项,并乘上特定的超参数以控制惩罚力度。加入 L2 正则以后,损失函数就变为:

$$L_{l_{2}}(\theta)=L(\theta)+1/2\gamma||\theta||^2$$

SGD 就变为:

$$\theta_{t}=\theta_{t-1}-\nabla L_{l_{2}}(\theta_{t-1})=\theta_{t-1}-\nabla L(\theta_{t-1})-\gamma\theta_{t-1}$$

SGD+momentum 就变为:

$$\theta_{t}=\theta_{t-1}-\gamma m_{t-1}-\eta(\nabla L(\theta_{t-1})+\gamma \theta_{t-1})$$ $$m_{t}=\gamma m_{t-1}+\eta(\nabla L(\theta_{t-1})+\gamma \theta_{t-1})$$ $$m_{t}=\gamma m_{t-1}+\eta(\nabla L{\theta_{t-1}})$$

最后一项是正则项产生。但是 $m_{t}$的计算有上面两种,都可以。adamw 的论文验证 $m_{t}=\gamma m_{t-1}+\eta(\nabla L{\theta_{t-1}})$ 效果好。

Adam 就变为:

$$m_{t}=\gamma m_{t-1}+\eta(\nabla L(\theta_{t-1}))$$ $$v_{t}=\beta_{2}v_{t-1}+(1-\beta_{2})(\nabla L(\theta_{t-1})+\gamma \theta_{t-1})$$ AdamW 最终的形式:

$$m_{t}=\beta_{1}m_{t-1}+(1-\beta_{1})\nabla L(\theta_{t-1})$$ $$v_{t}=\beta_{2}v_{t-1}+(1-\beta_{2})(\nabla L(\theta_{t-1}))^2$$ $$\theta_{t}=\theta_{t-1}-\eta(\frac{1}{\sqrt{\hat v_{t}}+\epsilon}\hat m_{t}-\gamma\theta_{t-1})$$

从上面的公式可以看出,AdamW 本质上就是在损失函数里面加入了 L2 正则项,然后计算梯度和更新参数的时候都需要考虑这个正则项。AdamW 使用在 hugging face 版的 transformer 中,BERT、XLNET、ELECTRA 等主流的 NLP 模型也都是用了 AdamW 优化器。

7.12.4RAdam

RAdam(Rectified Adam)是 Adam 优化器的一个变体,它引入了一项来纠正自适应学习率的方差,试图解决 Adam 的收敛性差的问题。作者认为收敛性差的原因是自适应学习率在早期的模型训练的过程中有较大的方差,这是因为训练使用的数据有限。为了减小方差,在训练前几个 epoch 的时候使用一个较小的学习率,这证明了热身启发式(warmup)的合理性。warmup 的方式启发了 RAdam 来纠正方差问题。 $$g_{t}=\nabla_{\theta}f_{t}(\theta_{t-1})$$ $$v_{t}=\frac{1}{\beta_{2}}v_{t-1}+(1-\beta_{2})g_{t}^2$$ $$m_{t}=\beta_{1} m_{t-1}+(1-\beta_{1})g_{t}$$ $$\hat m_{t}=\frac{m_{t}}{1-\beta_{1}^t}$$

$$\rho_{t}=\rho_{\infty}-\frac{2t\beta_{2}^2}{1-\beta_{2}^t}$$ $$\rho_{\infty}=\frac{2}{1-\beta_{2}}-1$$

其中 $m_{t}$是一阶矩(动量),$v_{t}$是二阶矩 (自适应学习率),$\eta$是学习率。

当 $\rho_{t} > 4$的时候: 自适应的学习率的计算公式为:

$$l_{t}=\sqrt{(1-\beta_{2}^t)/v_{t}}$$

方差矫正项计算公式为:

$$r_{t}=\sqrt{\frac{(\rho_{t}-4)(\rho_{t}-2)\rho_{\infty}}{(\rho_{\infty}-4)(\rho_{\infty}-2)\rho_{t}}}$$

我们使用自适应的 momentum 方法来更新参数

$$\theta_{t}=\theta_{t-1}-\alpha_{t} r_{t}\hat m_{t} l_{t}$$

如果方差不容易得到(tractable),我们采用下面的公式:

$$\theta_{t}=\theta_{t-1}-\alpha_{t} \hat m_{t}$$

7.13.Lookahead

Lookahead 是一种梯度下降优化器,它迭代的更新两个权重集合,”fast” 和”slow”。直观地说,该算法通过向前看由另一个优化器生成的快速权值序列来选择搜索方向。 梯度下降的时候,走几步会退回来检查是否方向正确。避免突然掉入局部最低点。

Lookahead 的算法描述如下:

  1. 初始化参数 $\phi_{0}$和目标函数 L

  2. 同步周期 k,slow 权重步长 $alpha$和优化器 A

    1. for t=1,2,…

    2. 同步参数 $\theta_{t,0}=\phi_{t-1}$

    3. for i=1,2,…,k

      1. 采样一个 minibatch 的数据:$d \sim D$
      2. $\theta_{t,i}=\theta_{t,i-1}+A(L,\theta_{t,i-1},d)$
    4. 外部更新 $\phi_{t}=\phi_{t-1}+\alpha(\theta_{t,k}-\phi_{t-1})$ 返回参数

  • Fast weights

    它是由内循环优化器(inner-loop)生成的 k 次序列权重;这里的优化器就是原有的优化器,如 SGD,Adam 等均可;其优化方法与原优化器并没有区别,例如给定优化器 A,目标函数 L,当前训练 mini-batch 样本 d,这里会将该轮循环的 k 次权重,用序列都保存下来。

  • Slow Weights:

    在每轮内循环结束后,根据本轮的 k 次权重,计算等到 Slow Weights;这里采用的是指数移动平均(exponential moving average, EMA)算法来计算,最终模型使用的参数也是慢更新(Slow Weights)那一套,因此快更新(Fast Weights)相当于做了一系列实验,然后慢更新再根据实验结果选一个比较好的方向,这有点类似 Nesterov Momentum 的思想。3

7.14.优化算法对比

  1. 跳出鞍点

    梯度下降算法总结_插图19

  2. 收敛速度

    梯度下降算法总结_插图20

7.15.优化算法选择建议

  1. 如果数据是稀疏的,就用自适用方法,即 Adagrad, Adadelta, RMSprop, Adam。RMSprop, Adadelta, Adam 在很多情况下的效果是相似的。
  2. 整体而言,Adam 系列优化器(如 Adam、Adamax、AdamW)是最好的选择:Adam 系列优化器在很多情况下表现良好,并且在实践中广泛使用。它们具有自适应学习率的特性,能够适应不同参数的更新要求,对于大多数问题都能提供较好的优化效果。
  3. 无论选择哪种优化器,合适的学习率衰减策略都很重要。常见的衰减策略有固定衰减、指数衰减、余弦衰减等。根据问题的特点和训练过程的需求,选择适合的学习率衰减策略可以提高优化效果。

8.优化算法发展历史

1847 年,Augustin-Louis Cauchy, 在 Méthode générale pour la résolution des systèmes d’équations simultanées. pp. 536–538 中提出提出梯度下降算法(GD)。

1951 年,由 Robbins 和 Monro 提出的随机梯度下降(SGD),至今已有 60 年历史。在当前的深度学习研究中,这种方法至关重要,一般被用在反向传播过程中。1952 年,J. Kiefer and J. Wolfowitz 也提出了 SGD 的方法随机逼近是一种参数的估计方法。它是在有随机误差干扰的情况时,用逐步逼近的方式估计参数的方法。

1964 年,Polyak 提出 momentum 算法,也称为 Polyak’s Heavy-ball method。

1983 年,Yurii Nesterov 提出 Nesterov accelerated gradient 算法。

2011 年,Duchi, J., Hazan, E., 对随机梯度算法进行修改提出提出 Adagrad 算法。

2012 年,Matthew D. Zeiler. 提出了 Adadelta 算法,对 Adagrad 算法进行改进。

2014 年,近年来,研究人员提出一些新的优化算法,使用了不同方程来更新模型参数。Kingma, D. P., & Ba, J. 提出 Adam 算法,可看作是目前最常用的优化算法之一。这表明,从机器学习工作者的角度来说,深度学习优化中的最佳方法在很大程度上是保持不变的。

2016 年,Dozat, T. 将 momentum 算法应用于 Adam 算法中,提出 Nadam 算法。

2017 年,Ilya Loshchilov 和 Frank Hutter 在他们的论文《Fixing Weight Decay Regularization in Adam》中指出所有的深度学习库中的 Adam optimizer 中实现的 weight decay 方法似乎都是错误的,并提出了一种简单的方法(他们称之为 AdamW)来解决它。

2018 年,在 Adam 方法收敛到一个次优解时,观察到一些小批次样本贡献了大幅且有效的信息梯度,但是这种情况很少发生,指数平均后减小了它们的影响,导致模型收敛性差。Reddi 等人提出 AMSGrad 算法对 SGD 算法进行改进。

2019 年,由 Michael R. Zhang 和 James Lucas 提出了 Lookahead 算法,通过结合两个优化器的思想,实现了更快速的收敛和更好的泛化性能。

9.深度学习主流模型使用的优化算法

下表列举了自然语言处理(NLP),计算机视觉(CV),推荐系统(Recommendation System,RS),强化学习(Reinforcement Learning,RL)这四个方向的主流模型使用优化器的情况3

可以看出在 NLP 领域 AdamW(AdamWeightDecayOptimizer)使用比较普遍,CV 领域 SGD 和 momentum 使用比较普遍,推荐领域比较杂,强化学习领域 Adam 使用比较普遍。

模型优化器领域
BERTAdamWeightDecayOptimizerNLP
ELECTRAAdamWeightDecayOptimizerNLP
XLNetAdamWeightDecayOptimizer,AdamOptimizerNLP
ZFNetMomentumOptimizerCV
VGGNetSGDCV
GoogLeNetSGDCV
ResNetmomentumCV
EfficientNetrmspropCV
DenseNetNesterov, momentumCV
Faster R-CNNmomentumCV
Mask R-CNNSGDCV
YOLOv3,YOLOv5Adam,SGDCV
RetinaNetSGDCV
YoutubeDNNAdamRS
DSSMadagradRS
DeepFMadam,adagrad,gd,momentumRS
DQNAdamRL
DDPGAdamRL
A2CAdamRL

10.参考资料

© 除特别注明外,本站所有文章均为卢明冬的博客原创 , 转载请联系作者。
© 本文链接:https://lumingdong.cn/summary-of-gradient-descent-algorithm.html
相关文章
评论 ( 6 )
  1. SHANE
    2019-08-29 16:22
    回复

    博主你好,看到你的文章,受益匪浅,总结的很全面。我想打印出来,方便查阅,不知道您是否能提供 markdown 或者其他格式版本?

    • 卢明冬
      卢明冬
      2019-08-30 19:02
      回复

      建议你直接使用 Chrome 浏览器打印,如果无法直连打印机,可以先用 Chrome 浏览器打印功能将网页保存为 PDF 版本再去打印纸质,我这边试了下效果还不错,在打印预览的时候可以根据效果调整一下页面的元素,比如关闭侧边目录的悬浮窗再打印。

      • SSSSQD
        2019-10-29 11:53
        回复

        CHROME 上有个更好的插件,叫 FULL PAGE SCREEN CAPTURE

  2. HUNTER
    2020-02-18 17:22
    回复

    感谢你的总结,收获良多

  3. haygf
    2020-06-04 13:56
    回复

    请教个问题,对于 GD 算法在 beale function 的应用,有没有可能在特定的点和 tolerance 下面,会出现 GD 算法的结果既不是局部最优,全局最优,也不是鞍点。
    因为在【-6;-3】以及 tolerance=1e-7 条件下,发现 beale function 收敛在 x=【-17.9;1.05】, 此时的一阶导数 gradient 不为 0

    • 卢明冬
      卢明冬
      2020-06-05 20:58
      回复

      没有专门研究过 GD 在 Beale Function 上的应用,不敢妄下断言,建议多查查资料,然后改几个参数多看看试验结果。我个人感觉你说的也不是没有可能,举个特别极端的例子,如果初始化位置选取的不太好,致使梯度朝着一个只有局部最优但不是全局最优的方向去优化,而这个局部最优恰好是一个对称性曲面(一个对称的小坑),学习率在当前时刻又是短期固定不变的,导致在对称面上均匀震荡,就会出现你说的情况,当然,这种情况太不容易碰到了。
      我觉得更大的可能是因为 Beale Function 本身是一个非常浅梯度的平坦区域,在这种情况下,GD 很难达到最小值,因为在这种几乎平坦的曲面上,GD 几乎不能够完成有效的学习,没有动力前进就会导致优化过程停滞在某个地方。

发布一条评论吧