7.1基于梯度下降的优化

7.1 基于梯度下降的优化

现在考虑求解一个实值函数最小值的问题：

其中 f: \mathbb{R}^{d} \rightarrow \mathbb{R} 是一个函数，它刻画了我们手中的机器学习问题。我们假设函数 f 是可微的，并且我们无法找到上述问题的解析解。

梯度下降是一个一阶优化算法。它的每次迭代都将估计点做一个正比于函数在该点处的负梯度向量的移动，以逐步找到一个局部最小值点。回顾第 5.1 节，梯度方向是函数值增长最快的方向。另一个有用的直观理解是考虑函数处于某个特定值处的那组线（即 f(\boldsymbol{x})=c ，其中某个值 c \in \mathbb{R} ），这些线被称为等高线。梯度方向与我们希望优化的函数的等高线方向正交。

让我们考虑多变量函数。想象一个曲面（由函数 f(\boldsymbol{x}) 描述），并设想一个球从某个特定位置 \boldsymbol{x}_0 开始。当球被释放时，它会沿着最陡峭的下坡方向向下滚动。梯度下降利用了这样一个事实：从 \boldsymbol{x}_0 出发，若朝着函数 f 在 \boldsymbol{x}_0 处负的梯度方向 -\left((\nabla f)(\boldsymbol{x}_0)\right)^{\top} 移动，f(\boldsymbol{x}_0) 的值将最快地减小。本书假设所涉及的函数都是可微的，并引导读者参考第 7.4 节中更一般的设置。于是假如我们考虑下面的更新：

若 \gamma \geqslant 0 是一个很小的 步长，就有 f(\boldsymbol{x}_{1}) \leqslant f(\boldsymbol{x}_{0})。注意我们在梯度的部分使用了转置记号，这是因为我们在本书中默认梯度时行向量——如果不转置的话维度对不上。

有了这个发现，我们就能提出一个简单的梯度下降算法：我们想要找到一个函数 f: \mathbb{R}^{n} \rightarrow \mathbb{R}, \boldsymbol{x} \mapsto f(\boldsymbol{x}) 的局部最优解 f(\boldsymbol{x}_{*}) ，我们从一个初始估计 \boldsymbol{x}_{0} 开始，然后按照下面的更新规则不断迭代

假设我们每次迭代选择的步长足够合适，我们得到的序列就是一个下降的 “链”：f(\boldsymbol{x}_{0}) \geqslant f(\boldsymbol{x}_{1}) \geqslant \cdots 它最终会趋于函数的局部最小值。

示例 7.1
考虑下面的二维二次函数

f\left(\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}\right) = \frac{1}{2}\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}^{\top}\begin{bmatrix}2&1\\1&20\end{bmatrix}\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix} - \begin{bmatrix}5\\3\end{bmatrix}^{\top}\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}\tag{7.7}

它对 \boldsymbol{x} 的梯度是

\nabla f\left(\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}\right) = \begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}^{\top}\begin{bmatrix}2&1\\1&20\end{bmatrix} - \begin{bmatrix}5\\3\end{bmatrix}^{\top}\tag{7.8}

如图 7.3 所示，我们从初始估计 \boldsymbol{x}_{0} = [-3, -1]^{\top} 开始用公式 (7.6) 不断迭代，以得到一个收敛于函数最小值的估计值序列。可见 \boldsymbol{x}_{0} 处的负梯度指向右上方，从而得到第二个估计 \boldsymbol{x}_{1} = [-1.98, 1.21]^{\top} （令 \gamma = 0.085，并将 \boldsymbol{x}_{0} 代入 (7.8) ）。再迭代一次，我们得到 \boldsymbol{x}_{2} = [-1.32, -0.42]^{\top}，以此类推。

图 7.3 梯度下降算法的示例

注释
梯度下降算法趋近局部最小值的速度可以很慢，它的渐近收敛速度弱于很多其他算法。在面临一些性质不甚好的凸函数时，我们可以想象一个从很长但很窄的斜坡滚下的球：梯度下降的更新轨迹将会是像图 7.3 那样的锯齿形，每次更新的方向甚至会与该点与局部最小值点的直接连线几乎垂直。

7.1.1 步长（学习率）

前文提到，步长大小在梯度下降算法中十分重要：如果步长太小，梯度下降的速度会很慢；如果步长太大，梯度下降算法有可能射出原本的 “峡谷” 区域，难以收敛，甚至发散。解决方法之一——动量法是通过平滑不稳定的更新行为并抑制更新中的震荡现象的方法，我们将在下一节介绍它。

另一种解决方法是所谓 自适应梯度法。它们在每次梯度更新时都会根据函数在局部的行为对梯度进行缩放。下面是两个简单的启发方法 (Toussaint, 2012)

• 梯度更新后函数值变大了，这说明步长太大走得太远。回退这一步然后选一个更小的步长
• 梯度更新后函数值变小了，说明还可以走更远，因此可以尝试更大的步长
  虽然 “回退” 这个做法看起来浪费资源，但这可以保证每次更新都会降低目标函数值。

示例 7.2（解线性方程）
假如我们用的范数是 Euclidean 范数，当我们解像 \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b} 这样的方程时，我们其实是通过找最小化

\| \boldsymbol{A}\boldsymbol{x} - \boldsymbol{b} \| ^{2} = (\boldsymbol{A}\boldsymbol{x} - \boldsymbol{b})^{\top}(\boldsymbol{A}\boldsymbol{x} - \boldsymbol{b})\tag{7.9}

以找到 \boldsymbol{A}\boldsymbol{x} - \boldsymbol{b} = \boldsymbol{0} 的近似解 \boldsymbol{x}_{*} 来完成的。公式 (7.9) 对 \boldsymbol{x} 的梯度是

\nabla_{\boldsymbol{x}} = 2(\boldsymbol{A}\boldsymbol{x} - \boldsymbol{b})^{\top}\boldsymbol{A}, \tag{7.10}

我们可以用它直接导出梯度下降算法。但对于这个例子本身，我们有一个解析解——令梯度为零就可得到。我们将在第九章介绍更多求解平方损失的内容。

注释
用上述方法解 \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b} 形式的方程在某些情况下并不高效。梯度下降算法的收敛速度取决于矩阵的 条件数 \displaystyle \kappa = \frac{\sigma(\boldsymbol{A})_{\max}}{\sigma(\boldsymbol{A})_{\min}}，它的值为矩阵 \boldsymbol{A} 的最大奇异值 （见 4.5 节）和最小奇异值之比。换句话说，条件数刻画了目标函数最陡峭的方向和最平缓方向的 "差距"。这和我们之前提到的情形相似：窄且长的 “峡谷” 对应着高的条件数：沿着峡谷行进的方向坡度平缓，而垂直于它的方向坡度陡峭。实际操作中我们不会直接求解 \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}，而是转而求解 \boldsymbol{P}^{-1}(\boldsymbol{A}\boldsymbol{x} - \boldsymbol{b}) = 0，其中 \boldsymbol{P} 称为 预条件子，它可以降低新得到的线性方程系数矩阵的条件数，且 \boldsymbol{P} 本身需要容易得到。更多信息请参见 Boyd and Vandenberghe (2004，第九章)。

7.1.2 动量梯度下降

如图 7.3 所示，如果优化曲面的曲率使得某些区域的性质不好，梯度下降的收敛速度可能会非常慢。曲率使得梯度下降更新在 ”峡谷“ 两侧跳跃，只能一小步一小步地接近最优值。为提高收敛性，我们可以赋予梯度下降一些 "记忆"。

注释
Goh（2017）撰写了一篇关于动量梯度下降的直观博客文章。

动量梯度下降（Rumelhart et al., 1986）是一种引入与上一次迭代的相关项的方法。这种记忆可以抑制振荡并使得梯度更新更加平滑。我们像之前一样考虑一个很重的滚动的球，动量项就模拟了它的惯性——很难轻易改变运动方向。这个方法也同时通过记忆梯度的更新以实现移动平均。具体而言，基于动量的方法会储存第 i 次迭代的更新 \Delta \boldsymbol{x}_{i}，然后加在第 i+1 次的梯度更新上；这相当于将第 i 次迭代和第 i+1 次迭代中得到的梯度做线性组合：

其中 \alpha \in [0, 1]。有时我们只知道梯度的一个估计值，此时上面的动量项作为移动平均会帮我们抹除梯度估计中的噪声，因此十分有用。下面介绍的随机梯度下降就是一个动量法大展身手的例子。

7.1.3 随机梯度下降

精确地计算梯度十分费时费力，但我们往往可以找到更快速地计算梯度估计值的方法 —— 只要我们估计的梯度和真实的梯度方向大致相同。随机梯度下降（SGD）是一种用于最小化可被写成一系列可微函数的目标函数，并给出梯度的随机估计的梯度下降算法。”随机“ 一词指的是我们每次更新不知道梯度的真实值，而只有一个带噪声的梯度估计值。如果限制梯度估计值的分布，在理论上我们依然可以保证 SGD 的收敛性。

在机器学习中，给定 n = 1, \dots, N 个数据点，我们通常将每个数据的损失 L_{n} 的求和作为目标函数：

其中 \boldsymbol{\theta} 是我们关心的参数向量 —— 我们要找出最小化 L 的参数 \boldsymbol{\theta}。第九章中我们将见到来自回归问题的 负对数似然函数，它是每个数据的负对数似然函数的求和：

其中 \boldsymbol{x}_{n} \in \mathbb{R}^{D} 是训练中的输入数据，y_{n} 是训练中的目标数据，\boldsymbol{\theta} 是回归模型的参数。

前文提到，经典的梯度下降是一个 ”整批“ 的优化方法，这是说每次我们都要选一个合适的 \gamma_{i}，并用 所有的 训练集来完成下面的迭代：

计算上面对所有 L_{n} 的梯度之和是个大工程。当训练集很大，或是没有显式的梯度可以求解的时候，这么做显然是极其昂贵的。

考虑 (7.15) 中的一项 \displaystyle \sum\limits_{n=1}^{N} [\nabla L_{n}(\boldsymbol{\theta})]，我们可以通过只算一小部分 L_{n} 的梯度之和来降低计算成本。相较于用上全部 L_{n}, n = 1, \dots, N 的经典梯度下降算法，我们只选择小部分 L_{n} ，这样我们就得到了 小批次梯度下降；该算法最极端的情况是每次只考虑一个 L_{n}。我们这么做是有道理的：我们只需要拿到一个对真实梯度的 无偏估计，而公式 (7.15) 中的 \displaystyle \sum\limits_{n=1}^{N} [\nabla L_{n}(\boldsymbol{\theta})] 事实上就是对梯度期望值 (见 6.4.1) 的经验估计，因此任何对梯度的无偏估计都可以拿来用。不论我们的小批次中的数据量是多少它都是对梯度的无偏估计，SGD 也总会收敛。

注释
在相对较弱的假设下，如果学习率以适当的幅度逐步降低，SGD 几乎必然 (almost surely) 收敛到局部最优解。 (Bottu, 1998)

译者注
几乎必然是一个专有名词，它属于概率论，指的是事件发生的概率为 1，或 Lebesgue 测度为 1；有时也简记为 a.s.

我们为什么要估计梯度的值呢？主要的原因是实践中的 CPU 和 GPU 的存储空间或是计算时间有限。我们可以考虑不同大小的批次。较大的批次不但可以利用高效的矩阵算法快速计算结果，还会给出梯度更加精确的估计，降低了参数更新的方差，算法的收敛也会更稳定。相比之下较小的批次可以更快的算出，但牺牲了估计的精确性，这可能会让我们陷入更差的局部最优而无法脱离。

机器学习中，我们用优化算法解决我们的短期目标：训练集上的目标函数，以期完成增强模型泛化性能的长期目标 (第八章)。机器学习实践中也不需要对目标函数的最小值有多么精确地估计，因此类似上文中的小批量算法被大量使用，且在大规模机器学习问题 (Bottou et al., 2018) 例如训练神经网络为几十万张图片进行分类 (Dean et al., 2012)、主题模型 (Hoffman et al., 2013)、强化学习 (Mnih et al., 2015) 或是训练大规模 Gauss 过程模型 (Hensman et al, 2013; Gal et al, 2014) 中效果拔群。