梯度下降算法总结

1.概述

梯度下降（Gradient Descent）是应用非常广泛的优化算法之一，其应用范围涵盖经典机器学习算法、神经网络、深度学习。机器学习问题很大程度上来说其实就是找到一个合适的目标函数，然后不断优化参数的最优化过程，而梯度下降正是最优化过程中的重要算法，由此可见梯度下降在机器学习中的重要性。现在很多知名的深度学习库都已经包含了各种梯度下降优化算法的实现（如 Tensorflow，Cafe，Keras），但依然很有必要去了解梯度下降的底层逻辑，熟知梯度下降不同变种、不同算法之间的区别，并能够根据它们各自的优缺点选择最合适的方法和参数来应用于相应的场景。

2.为什么要用梯度下降

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

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

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

1）计算量大

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

2）需要全部数据

很多时候我们没有办法直接离线的拿到足够多的数据来直接计算；

3）必须有解析解

不是所有的目标函数都能够求得解析解；

4）偏数学逻辑而非计算机的逻辑

梯度下降的逻辑更符合计算机科学的程序设计逻辑，通过不断迭代优化，获取最优解；

5）更像数学而非机器学习

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

@ 最优化

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

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

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

目前主要有三种最优化算法：

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

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

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

梯度下降是机器学习和深度学习中最常用的优化算法。它属于一阶优化算法，参数更新时只考虑一阶导数。

3.梯度下降算法原理

绝大部分优化问题都可以转化成如下的问题：给定一个关于 $\theta \in R$ 的目标函数 $J(\theta)$，求使得 $J(\theta)$ 最小的参数 $\theta$。如下图，A 点是随机初始给定的 $\theta$ 的目标函数值，B 点是目标函数值 $J(\theta)$ 最小的地方，我们目的是求 B 点处的 $\theta$。梯度下降就是从 A 点开始，不断沿着下降最快的方向（负梯度方向）迭代，更新后的 $\theta$ 能够使 $J(\theta)$ 更小，直至到达 B 点。

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

当然这样走下去，有可能我们不能走到真正的山脚，而是到了某一个局部的山峰低处。梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。

这里的下山最陡的方向就是梯度的负方向。

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

首先来了解一下什么是梯度？通俗来说，梯度就是表示某一函数在该点处的方向导数沿着该方向取得较大值，即函数在当前位置的导数：

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

其中，$\theta$ 是参数（自变量），$J(\theta)$ 是关于 $\theta$ 的目标函数。

知道了梯度，又有了上面的铺垫，不难得出梯度下降的公式：

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

其中，$\theta_0$ 需要事先给定，可以是一个随机初始化的 $\theta$，接下来的 $\theta$ 则是需要沿着负梯度方向迭代更新后得到，$\alpha$ 是学习率，也就是每次迭代的步长。

接下来，我们从数学角度来推导梯度下降公式到底是怎么来的，来了解梯度下降最本质的深层原理。

在上一小节中，我们已经知道，不是所有的目标函数都能得到解析解，因此就无法通过数学计算来直接求得其最优解，这个求解最优化参数的过程成为了一个 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]：

上图中，凸函数 $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$ 的值了。

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

上图中，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} $$

关于二阶泰勒展开的牛顿法，可参考 《Logistic 回归》牛顿法。

梯度下降的优化过程

从优化的整个过程来看，梯度下降思想可以用数学表述如下：

$$\begin{equation} \theta_{k+1}=\theta_k-\alpha_k \nabla J(\theta_k)\Rightarrow J(\theta_{k})\geq J(\theta_{k+1}) ,\;\;\; 0\leq k\leq n \end{equation} $$

其中，$\theta$ 是参数（自变量），$J(θ)$ 是关于 $θ$ 的目标函数，一般是存在下界的可导函数。$k$ 是第 $k$ 次迭代，$\alpha$ 是学习率，也就是每次迭代的步长。第一个 $θ$ 需要事先随机给定，可记做 $\theta_0$。

根据该思路，如果我们从 $\theta_0$ 为出发点，每次沿着当前函数梯度反方向移动一定距离 $\alpha_k$，得到序列 $\theta_0, \theta_1,\cdots,\theta_n$，对应的各点函数值序列之间的关系为：

$$\begin{equation} J(\theta_0)\geq J(\theta_1)\geq J(\theta_2)\geq\cdots\geq J(\theta_n) \end{equation}$$

很显然，当 $n$ 达到一定值时，函数 $J(x)$ 是会收敛到局部最小值的。

梯度下降的过程如下图所示 ^[2]：

从梯度下降公式可以看出，梯度下降法和两个因素息息相关，一个是梯度，也就是方向（$\nabla J(\theta)$），一个是学习率（$\alpha$）。

方向

通过上面的了解，我们知道梯度下降是沿着负梯度的方向进行下降的，因为这个方向是下降最快的方向。接下来，我们从损失面的角度来分析梯度方向。请看下图，在曲面的任何一点，我们都能够定义一个与其相切的平面。在更高维度，我们总能够定义一个超平面（下图以三维空间为例）。然后，在这个平面与曲面的切点处可以有无限个方向。其中只有一个使函数上升最快的方向，根据梯度的定义以及其几何意义，我们知道这个方向就是梯度方向 ^[6]，与之相反的方向就是下降最快的方向。这就是梯度下降算法名称的来源，我们沿着梯度的方向进行下降，所以就叫做梯度下降^[2]。

梯度方向是 Loss 等高线的法线方向，如下图：

一般情况下，我们是求最小化损失函数，也就是求最小值，其实是沿着负梯度方向进行下降，所以是用梯度下降法。不过有时候是求最大目标函数，即求最大值，这种情况就是梯度上升了，就是沿着正梯度方向进行上升，其思路和方法和梯度下降一模一样，只是换了个方向而已。习惯上，若是目标函数求最大值，会在目标函数前面加一负号转为求最小值，依然使用梯度下降法来得到最优解。

梯度的方向告诉我们哪个方向上升的最快，它的值则表示最陡峭的方向上升/下降有多陡。所以，在最小值或最大值的地方，曲面轮廓几乎是平坦的，我们期望得到几乎为零的梯度。事实上，最小值点的梯度就是 0。

学习率

学习率是一个超参数，用于控制下降或上升步幅的大小。在梯度确定之后，学习率是梯度下降算法中唯一一个必须足够重视的参数。实际上，学习率的设定是梯度下降算法中的一大挑战，学习率设定过小会导致收敛太慢，也可能让算法陷入局部极小值跳不出来；设定过大又容易导致收敛震荡甚至偏离最优点，学习率的设定可参考 《梯度下降学习率的设定策略》。

上图中，学习率设置过大，导致目标函数值沿着 “山谷” 周围大幅震荡，可能永远都到达不了最小值。

4.梯度下降必须注意的几个点

4.1.梯度下降的收敛

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

4.2.梯度下降真正的轨迹

我们经常看到的梯度下降的可视化图，很可能是在一个曲面上起于一个点、终于最小值点的轨迹，就像上文中绝大多数图中所展示的那样。然而，这个关于梯度下降的描述并不准确，这个轨迹实际上是损失函数或者是目标函数下降或上升的轨迹，而不是梯度下降的轨迹。真正的梯度下降轨迹如下图所示，是局限在 X-Y 平面上的一条线，并没有在 Z 轴方向移动 ^[2]。

实际上，真正的梯度下降轨迹是损失函数下降轨迹在参数维度上的投影，在该投影上的每一个点都代表着唯一的参数θ组合（表现为一个矩阵），我们的目的是可以找到一组合适的θ组合能够使得损失函数取得最小值，即损失函数取最小值时投影在参数维度上的那个点的参数θ组合。

4.3.标准化后再进行梯度下降

如果数据尺度不一，那就要对数据进行尺度缩放。如果我们不缩放数据，那么等高线（轮廓）会变得越来越窄，意味着它需要更长的时间来达到收敛， 下图说明了梯度下降在数据标准化后的等高线与未进行标准化的对比 ^[1]。

标准化可以使用 z-score 标准化方式，即使数据分布满足μ=0 和σ=1，故也称零-均值标准化。公式如下：

$$\frac{x-\mu}{\sigma}$$

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

梯度下降算法主要有三种变种，它们之间的主要区别在于每个学习步骤中计算梯度时使用的数据量，是对每个参数更新（学习步骤）时的梯度准确性与时间复杂度的折衷考虑，即在准确性和优化速度间做权衡 ^[3]。 

5.1.批量梯度下降（BGD）

批量梯度下降（BGD, Batch gradient descent）又名香草梯度下降（Vanilla gradient descent ，香草 “vanilla” 是一种常见的 “常规” 或 “没有任何花哨的东西” 的委婉说法，所以可以理解为普通的、常规梯度下降），批量梯度下降在对参数执行更新时，在每次迭代中使用所有的样本。即：

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

示例代码:

主要优点:

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

主要缺点：

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

5.2.随机梯度下降（SGD）

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

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

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

示例代码：

$ 为什么叫随机梯度下降？

一个不严格的解释：

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

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

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

主要优点：

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

主要缺点：

• • SGD 的随机性给学习过程增加了更多的噪声，并且学习过程不断以高方差的方式频繁更新，导致目标函数大幅波动。
  • 随机性可能导致收敛复杂化，即使到达最优点仍然会进行过度优化，因此 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 时候，这种方法就相当于批量梯度下降。 

示例代码：

（这里设定的是 50 个样本为 1 个小批量）

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

主要优点:

• • 对比 BGD，速度更快，因为它少用了很多样本，并且可以利用现有的线性代数库高效的计算多个样本的梯度。
  • 对比 SGD，参数更新时的动荡变小，收敛过程更稳定，降低收敛难度；
  • 随机选择样本有助于避免对学习没有多大贡献冗余样本或非常相似的样本的干扰。
  • 当批量的大小小于训练集大小时，会增加学习过程中的噪声，有助于改善泛化误差。

主要缺点：

• • 在每次迭代中，学习步骤可能会由于噪声而来回移动。 因此它可能会在最小值区域周围波动，一时半会儿不收敛。
  • 由于噪声的原因，相比于 BGD，学习步骤会有些许的振荡，并且随着我们越来越接近最小值，需要增加学习衰减来降低学习速率。

5.4.小结

每次迭代更新：

    BGD 拿到所有数据并把所有样本的梯度加起来，然后下降。

    SGD 遍历样本，每拿到一个样本就计算一次梯度，然后下降一次；

    MSGD 积累一部分样本后，计算这些样本的平均梯度，作为更新方向下降一次。

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

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

6.梯度下降算法的挑战

到目前为止，梯度下降算法的一切听起来似乎很美好，它是如此强大如此迷人，当你兴高采烈地将梯度下降算法作为强有力的武器，某一天在实战中准备披荆斩棘的时候就很可能会发现，这玩意儿似乎并不那么的 “听话 “。现实总是有那么点不理想，正如很多时候，我们要处理的问题得到的目标函数并不是凸函数。尤其在神经网络中，其目标函数很难是凸的。

这就会遇到一些令人不爽的问题，也为梯度下降算法带来一些挑战。

挑战一：局部极小值

当目标函数是凸函数时，梯度下降法的解是全局最优解。然而很多情况下，尤其是处理较复杂问题时，目标函数是非凸的。这时就不会像上面看到的图像那样完美了，会存在一些局部极值点，梯度下降算法也不能够一下子确定是最优解。如下图 ^[2]：

在上图中，假设初始参数θ对应的损失值在 A 点，那么它将会收敛到附近的局部极小值点。因为梯度下降是由梯度驱动的，它在任何一个极小值点的梯度都会为 0，这与最小值处的表现是一样的。所以一旦收敛到这个极小值点，它会误以为这个极小值点就是全局最小值点，便会欣然停止继续搜寻的脚步，停留在这个自以为是最低的地方安于现状，殊不知，真正的最低点就在不远处。

局部极小值之所以被称作局部极小值，是因为损失函数在该点的值在局部区域是最小的。而全局最小值被称作全局最小值，是因为在损失函数在该点的值在整个区域最小。我们真正要找的是全局最小值，然而实际应用中，经常会遇到很多局部极小值，尤其在神经网络和深度学习中，几乎遍地都是局部极小值，这就给梯度下降法带来了很大的挑战。 

挑战二：鞍点

关于梯度下降的局限性，我们得到的基本教训是：一旦到达梯度为 0 的区域，不管极小值点的质量如何，它都几乎无法逃离。我们面临的另一种问题是鞍点（Saddle Point），它们的形状如下 ^[2]：

鞍点得名于它的形状类似于马鞍。尽管它在 x 方向上是一个最小值点，但是它在另一个方向上是局部最大值点，并且，如果它沿着 x 方向变得更平坦的话，梯度下降会在 x 轴振荡并且不能继续根据 y 轴下降，这就会给我们一种已经收敛到最小值点的错觉。

$ 如果遇到这些问题，该如何解决呢？

    1）上一小节中提到的随机梯度下降和小批量随机梯度下降这两个变种，因为引入了个体样本的噪声，带来一定的随机性，在某些情况，是可以跳出局部极小值和鞍点的，不过效果很一般；

    2）深度学习中，数据科学家们提供了更多解决方案，包括引入动量、动态调整学习率等方法，部分方法可以非常有效的解决上述问题，在下一小节我们具体展开；

    3）学习率是梯度下降算法的重要参数，通过调整学习率，很大程度上可以解决上述问题，详见 《梯度下降学习率的设定策略》。

7.深度学习的梯度下降优化算法

对于上面遇到的一些挑战，实际上在深度学习中会更敏感，下面介绍一些在深度学习中常用的用以解决上述问题的梯度下降优化方法， 权当做梯度下降算法基础之外的拓展。

一些对高维数据不可行的方法不再讨论，如二阶方法中的牛顿法 ^[3][4]。

7.1.Momentum

以下图 a 为例，面对某一方向上特别陡峭的目标函数曲面，SGD 可能会表现得踌躇不前 (来回波动)。

Momentum 实际上是带动量的 SGD，动量的引入是为了加速 SGD 的优化过程。

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

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

分析上式就会明白动量的作用原理：利用惯性，即当前梯度与上次梯度进行加权，如果方向一致，则累加导致更新步长变大；如果方向不同，则相互抵消中和导致更新趋向平衡。

动量 $\gamma$ 常被设定为 0.9 或者一个相近的值。

7.2.NAG

带动量的 SGD 可以加速超车，但是却不知道快到达终点时减速。 NAG（Nesterov accelerated gradient）就是用来解决这个问题的。

$$ \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}$) 计算梯度。 (已经确定会移动 $\gamma\nu_{t-1}$，那不如之前去看移动后的梯度)。

这个改进的目的就是为了提前看到前方的梯度。如果前方的梯度和当前梯度目标一致，那我直接大步迈过去； 如果前方梯度同当前梯度不一致，那我就小心点更新。

下面是一个示意图：

蓝色线表示正常的带动量 SGD 的两次移动； 棕色线是计划移动的量 ( $\gamma\nu_{t-1}$ ); 红色线是在移动后位置计算的移动量； 棕色线和红色线的合并效果就是绿色线 NAG。

7.3.Adagrad

针对上述所有参数使用同一学习率的问题，Adagrad 做了一些改善，为出现频率不高的参数提供一个大学习率，为经常出现的参数提供较小的学习率。

Adagrad 为每一个参数 $\theta_i$ 提供了一个与自身相关的学习率：

$$\theta_{t+1,i} = \theta_{t,i} – \frac{\eta }{\sqrt{G_{t,ii} + \epsilon}}\nabla_{\theta}J(\theta_{t,i})$$

其中 $G_{t}$ 为一个对角矩阵，其对角上的每一个元素 $G_{t,ii}$ 为 t 时刻前所有施加到参数 $\theta_i$ 上的梯度的平方的和。 $\epsilon$ 用来防止除 0 操作，通常设置为 $10^{-8}$。 实验表明，如果分母不开方，性能会很差。

简单分析上式，有三点结论：

    1) 经常出现 (累积梯度大) 的参数的学习率会被拉低，较少出现 (累积梯度小) 的参数的学习率会被拉高；

    2) 随着训练次数增加，累积梯度肯定会上升，导致分母变大，则学习率会自动下降。因此，Adagrad 可以自动调节学习率，而我们只需给其一个初始学习率即可；

    3) 同样是随着训练参数增加，学习率会下降的很快，这可能导致后期学习率过低而学不到东西。 

7.4.Adadelta

由于 Adagrad 采用了以往所有梯度平方之和，因此会导致累计梯度持续增加，最后因为学习率过低而学不到东西。为了解决该问题，这里引入 Adadelta： 仅采用一个窗口范围内的梯度平方之和。

具体地，采用滑动窗口的方法计算梯度平方和的滑动平均值：

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

其中 $\gamma$ 为滑动系数，通常被设置为 0.9。

  于是，最终的 Adadelta 的更新策略为：

$$ \Delta\theta_{t} = – \frac{\eta }{\sqrt{E[g^2]_t + \epsilon}}g_t$$

$$\theta_{t} = \theta_{t} + \Delta\theta_{t}$$

此外，上面计算 $\Delta\theta_{t}$ 的等式中等号两边的单位并不一致。 左边为 $\theta$ 的单位，而右边的单位却是 $\frac{g 的单位\;\;}{g 的单位\;\;} = 1$ 这一问题同样存在于 SGD、Momentum 以及 Adagrad 中。

解决方案如下，人为给等号右边增加一个单位：

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

$$ \Delta\theta_{t} = – \frac{\sqrt{E[\Delta\theta^2]_{t} + \epsilon}}{\sqrt{E[g^2]_t + \epsilon}}g_t $$

  由于 t 时刻的 $\Delta\theta_t$ 不知道，因此用 t-1 时刻近似。

$$E[\Delta\theta^2]t \rightarrow E[\Delta\theta^2]_{t-1}$$

$$\Delta\theta_{t} = – \frac{\sqrt{E[\Delta\theta^2]_{t-1} + \epsilon}}{\sqrt{E[g^2]_t + \epsilon}}g_t$$

由上式可以看出，Adadelta 已经无需设置初始学习率了，其可以自动计算并更新学习率。

7.5.RMSprop

RMSprop 是一种未公开发表的方法，来自于 Hinton 的 Coursera 公开课。 RMSprop 基本上等同于未做” 单位统一 “的 Adadelta。

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

$$\theta_{t+1} = \theta_{t} – \frac{\eta }{\sqrt{E[g^2]_t + \epsilon}}g_t$$

Hinton 建议滑动系数 $\gamma$ 设置为 0.9， 初始学习率 $\eta$ 设置为 0.001。

7.6.Adam

Adaptive Moment Estimation (自适应矩估计 Adam) 是另外一种为每个参数提供自适应学习率的方法。 

同 RMSprop、Adadelta 相比，Adam 在对梯度平方 (二阶矩) 估计的基础上增加了对梯度 (一阶矩) 的估计，使得整个学习过程更加稳定。

$$E[g]t=\beta_1 E[g]_{t-1} + (1-\beta_1)g_t$$

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

由于 $ E[g]_t $ 和 $E[g^2]_t$ 通常都初始化为 0， 因此在训练初期或者 $\beta_1$，$\beta_2$ 接近 1 时，估计的期望往往偏向于 0。

为了解决这种偏置，增加了偏基矫正：

$$\hat{E[g]_t} = \frac{E[g]_t}{1-\beta_1}$$

$$\hat{E[g^2]_t} = \frac{E[g^2]_t}{1-\beta_2}$$

于是最终的更新公式为：

$$\theta_{t+1} = \theta_{t} – \frac{\eta }{\sqrt{\hat{E[g^2]_t} + \epsilon}}\hat{E[g]_t}$$

通常 $\beta_1$，$\beta_2$ 分别被设置为 0.9 和 0.999。

7.7.AdaMax

AdaMax 是 Adam 的一种变种。主要是对原来的二阶矩估计扩展到无穷阶矩。(高阶矩往往不稳定，但无穷阶矩通常趋于稳定)

通过替换 Adam 中的分母项:

$$\sqrt{\hat{E[g^2]_t} + \epsilon} \quad\leftarrow \quad\mu_t = \beta_2^{\infty}\mu_{t-1}+(1-\beta_2^{\infty})g_t^{\infty} = max(\beta_2\mu_{t-1},|g_t|)$$

于是最终的更新公式为：

$$\theta_{t+1} = \theta_{t} – \frac{\eta }{\mu_t}\hat{E[g]_t}$$

注意，由于 $\mu_t$ 采用了 max 操作，因此无需进行偏置矫正。 通常 $\beta_1$，$\beta_2$ 分别被设置为 0.9 和 0.999， $\eta$ 设置为 0.001。

7.8.小结

本小节介绍的几种关键算法的特点，可以从下面两张图看出：

上图中展示了几种算法在损失曲面（Beale 函数）的等值线上梯度下降的路径和过程。 所有算法从从同一点开始，采取不同的路径达到最低点。 可以发现，Adagrad、Adadelta、以及 RMSprop 立即朝着正确的方向前进并且快速收敛，而 Momentum 和 NAG 在开始时却被引导偏离了正确轨道，造成了滚向另一边的山坡然后又滚下来的现象，不过，Momentum 和 NAG 后来的表现非常好，它们很快地纠正路线迅速收敛到最低点。

上图展示的是算法在鞍点处的行为，鞍点就是某一维具有正斜率，而另一维具有负斜率的点，上面提到过，鞍点是梯度下降算法的一大挑战。从图中可以看出，SGD，Momentum 和 NAG 很难打破对称性曲面，虽然后两者最终设法摆脱了鞍点。而 Adagrad、RMSprop 和 Adadelta 沿负斜率迅速降低，且 Adadelta 的速度远远领先于其他算法 ^[3]。

8.参考资料

[1] Imad Dabbura. Gradient Descent Algorithm and Its Variants. Towards Data Science

[2] Ayoosh Kathuria. Intro to optimization in deep learning: Gradient Descent. PaperspaceBlog

[3] Sebastian Ruder. An overview of gradient descent optimization algorithms. arxiv

[4] shuzfan. 梯度下降优化算法总结. CSDN

[5] 红色石头. 简单的梯度下降算法，你真的懂了吗. AI 有道

[6]【扩展】忆臻. 为什么梯度反方向是函数值局部下降最快的方向. 知乎