第 4 章：数值计算（Numerical Computation）

4.1 溢出和下溢（Overflow and Underflow）

在数字计算机上做连续数学的根本困难在于：我们只能用有限多个比特模式去表示无穷多的实数。这意味着对几乎所有实数而言，在计算机中表示它时都会引入某种近似误差。许多情况下这只表现为舍入误差。舍入误差是麻烦的——特别是当它跨多个运算累积时，本来理论上能用的算法若没有在设计上尽量减少舍入误差的累积，到实践中就会失败。

一种尤其具有破坏性的舍入误差形式是下溢。下溢发生在接近零的数被舍入到零时。许多函数在参数为零与为一个小的正数时行为有质的差别。例如，我们通常要避免除以零（有的软件环境会抛异常，有的会返回一个 not-a-number 占位值），也要避免对零取对数（对零取对数通常被当作 \(-\infty\)，这一值再参与后续算术又会变成 not-a-number）。另一种破坏力极强的数值误差是溢出。溢出发生在具有大数量级的数被近似为 \(\infty\) 或 \(-\infty\) 时，进一步的算术往往会把这些无穷值变成 not-a-number。

softmax 函数就是必须对下溢和溢出做数值稳定化的一个例子。softmax 常被用来预测与 multinoulli 分布相关联的概率，其定义为 \(\text{softmax}(x)_i = \frac{\exp(x_i)}{\sum_{j=1}^{n} \exp(x_j)}\)。考虑所有 \(x_i\) 都等于某个常数 \(c\) 的情形。解析上可知所有输出都应为 \(\frac{1}{n}\)；数值上，当 \(c\) 的量级很大时这一点可能不再成立。若 \(c\) 非常负，\(\exp(c)\) 会下溢，意味着 softmax 的分母变成 0，最终结果未定义。当 \(c\) 非常大且为正，\(\exp(c)\) 会溢出，同样使整个表达式未定义。两种困难都可以通过改为计算 \(\text{softmax}(z)\)，其中 \(z = x - \max_i x_i\) 来解决。简单的代数显示，从输入向量中加或减一个标量，softmax 的解析值不变。减去 \(\max_i x_i\) 后，最大的那个 exp 参数变为 0，这便排除了溢出的可能；类似地，分母中至少有一项为 1，这排除了分母下溢导致除零的可能。还有一个小问题：分子中的下溢仍可能让整个表达式被求值为零。这意味着若先调用 softmax 子例程再把结果传给 log 函数来实现 \(\log \text{softmax}(x)\)，就会错误地得到 \(-\infty\)。正确的做法是单独实现一个以数值稳定方式计算 \(\log \text{softmax}\) 的函数。\(\log \text{softmax}\) 函数可使用与稳定化 softmax 完全相同的技巧。

作者在书中并不打算显式地逐个罗列实现各种算法时的数值考量。底层库的开发者在实现深度学习算法时应当把数值问题放在心上；多数读者完全可以信赖那些提供了稳定实现的底层库。在某些情况下，可以让一种新算法在落地时自动被稳定化。Theano（Bergstra 等, 2010; Bastien 等, 2012）就是一个能自动检测并稳定化深度学习中常见的多种数值不稳定表达式的软件包。

4.2 条件数（Poor Conditioning）

条件数（conditioning）刻画的是函数相对于输入的微小变化而变化的快慢程度。当输入有微小扰动时函数变化剧烈的情形，对科学计算是有问题的——输入中的舍入误差会导致输出出现大变化。考虑函数 \(f(x) = A^{-1} x\)。当 \(A \in \mathbb{R}^{n \times n}\) 具有特征值分解时，其条件数是 \(\max_{i,j} \left| \frac{\lambda_i}{\lambda_j} \right|\)，即最大与最小特征值量级之比。当这个数很大时，矩阵求逆对输入误差特别敏感。这种敏感性是矩阵自身的内禀性质，而不是矩阵求逆过程中舍入误差的结果。病态矩阵在我们乘以真逆矩阵时会放大原本就存在的误差；实践中，误差还会在求逆过程本身中因数值误差被进一步放大。

4.3 基于梯度的优化（Gradient-Based Optimization）

大多数深度学习算法都涉及某种优化。优化指的是通过改变 \(x\) 来最小化或最大化某个函数 \(f(x)\) 的任务。我们通常把大多数优化问题都用最小化 \(f(x)\) 的形式来表达；最大化则可以通过最小化 \(-f(x)\) 的方式交由最小化算法完成。

我们想要最小化或最大化的函数被称为目标函数（objective function）或准则（criterion）。当我们最小化它时，也可以称它为代价函数、损失函数或误差函数。书中这些术语是混用的，不过某些机器学习出版物会给其中某些术语赋予特殊含义。我们常用上标 \(*\) 来标记使函数取到最小值或最大值的那个值，例如 \(x^* = \arg\min f(x)\)。

假设我们有一个函数 \(y = f(x)\)，其中 \(x\) 和 \(y\) 都是实数。该函数的导数记为 \(f'(x)\) 或 \(\frac{dy}{dx}\)，它给出 \(f(x)\) 在点 \(x\) 处的斜率。换言之，它告诉我们如何缩放输入的微小变化以得到相应的输出变化：\(f(x + \epsilon) \approx f(x) + \epsilon f'(x)\)。因此导数对于最小化函数是有用的——它告诉我们该如何改变 \(x\) 以使 \(y\) 取得一个微小的改进。例如，我们知道 \(f(x - \epsilon \, \text{sign}(f'(x)))\) 在 \(\epsilon\) 充分小时严格小于 \(f(x)\)。于是我们可以通过让 \(x\) 以与导数符号相反的方向做微小步进来减小 \(f(x)\)。这一技术称为梯度下降（Cauchy, 1847）。

当 \(f'(x) = 0\) 时，导数不再提供方向信息。满足 \(f'(x) = 0\) 的点称为临界点或驻点。局部极小值是这样一个点，\(f(x)\) 在该点处低于所有邻点，因此已不可能通过无穷小步进一步降低 \(f(x)\)。局部极大值则相反。有些临界点既非极大值也非极小值，这些点称为鞍点。一维情形下三种临界点的例子见图 4.2。

一个取得 \(f(x)\) 绝对最小值的点称为全局最小值。函数可能有唯一全局最小值，也可能有多个全局最小值；还可能存在不是全局最优的局部极小值。在深度学习的语境中，我们优化的函数可能有许多并非最优的局部极小值，也有许多被非常平坦的区域所包围的鞍点。所有这些都让优化变得困难，特别是当函数的输入是多维的时候。因此我们通常满足于找到一个 \(f\) 非常低但未必是任何严格意义下最小的值。深度学习中优化算法可能停在某个"足够低"的局部极小值上，这种做法的例子见图 4.3。

我们经常最小化有多个输入的函数 \(f: \mathbb{R}^n \to \mathbb{R}\)。要让"最小化"的概念有意义，输出仍必须是唯一的（标量）。对多输入函数，我们必须使用偏导数的概念。偏导数 \(\frac{\partial}{\partial x_i} f(x)\) 度量的是在点 \(x\) 处仅当变量 \(x_i\) 增加时 \(f\) 如何变化。梯度把导数的概念推广到导数是关于向量来取的情形：\(f\) 的梯度是包含所有偏导数的那个向量，记为 \(\nabla_x f(x)\)。梯度的第 \(i\) 个元素就是 \(f\) 关于 \(x_i\) 的偏导数。在多维情形下，临界点定义为梯度每个元素都为 0 的那些点。

方向导数（在方向 \(\mathbf{u}\) 上、\(\mathbf{u}\) 为单位向量）是函数 \(f\) 在 \(\mathbf{u}\) 方向上的斜率。换言之，方向导数是函数 \(f(\mathbf{x} + \alpha \mathbf{u})\) 关于 \(\alpha\) 在 \(\alpha = 0\) 处的导数。利用链式法则，\(\frac{\partial}{\partial \alpha} f(\mathbf{x} + \alpha \mathbf{u})\) 在 \(\alpha = 0\) 处的取值为 \(\mathbf{u}^\top \nabla_\mathbf{x} f(\mathbf{x})\)。要最小化 \(f\)，我们想找到 \(f\) 下降最快的方向，这可以借由方向导数得到：\(\min_{\mathbf{u}, \mathbf{u}^\top \mathbf{u} = 1} \mathbf{u}^\top \nabla_\mathbf{x} f(\mathbf{x}) = \min_{\mathbf{u}, \mathbf{u}^\top \mathbf{u} = 1} \|\mathbf{u}\|_2 \|\nabla_\mathbf{x} f(\mathbf{x})\|_2 \cos\theta\)，其中 \(\theta\) 是 \(\mathbf{u}\) 与梯度之间的夹角。代入 \(\|\mathbf{u}\|_2 = 1\) 并丢掉与 \(\mathbf{u}\) 无关的因子，问题化简为 \(\min_{\mathbf{u}} \cos\theta\)。它在 \(\mathbf{u}\) 指向与梯度相反方向时取到最小值。换言之，梯度指向正上坡，负梯度指向正下坡。我们可以通过沿负梯度方向移动来减小 \(f\)。这称为最速下降法或梯度下降法。

最速下降法建议一个新点 \(\mathbf{x}' = \mathbf{x} - \epsilon \nabla_\mathbf{x} f(\mathbf{x})\)，其中 \(\epsilon\) 是学习率，一个决定步长大小的正常数。\(\epsilon\) 的选取有多种方式：一种流行做法是把 \(\epsilon\) 设为一个小的常数；有时也可以解出让方向导数消失的那个步长；另一种做法是对若干个 \(\epsilon\) 值评估 \(f(\mathbf{x} - \epsilon \nabla_\mathbf{x} f(\mathbf{x}))\)，并选取使目标函数值最小的那一个——这种策略称为线搜索。最速下降法在梯度的每个元素都为 0（实践中非常接近 0）时收敛。在某些情况下，我们可以不跑这个迭代算法而直接通过解方程 \(\nabla_\mathbf{x} f(\mathbf{x}) = 0\) 来跳到临界点。

虽然梯度下降仅限于连续空间中的优化，"反复做一个小的（且近似为最优的）移动、走向更好的构型"这一总思想可以推广到离散空间。在离散参数上对目标函数做上升称为爬山法（Russel and Norvig, 2003）。

4.3.1 超越梯度：Jacobian 和 Hessian 矩阵（Beyond the Gradient: Jacobian and Hessian Matrices）

有时我们需要找到所有偏导数，而函数本身是输入和输出都为向量的那种。包含所有这种偏导数的矩阵称为 Jacobian 矩阵。具体地，若我们有函数 \(f: \mathbb{R}^m \to \mathbb{R}^n\)，则 \(f\) 的 Jacobian 矩阵 \(J \in \mathbb{R}^{n \times m}\) 定义为 \(J_{i,j} = \frac{\partial}{\partial x_j} f(\mathbf{x})_i\)。

我们有时也会对"导数的导数"感兴趣，这就是二阶导数。例如对函数 \(f: \mathbb{R}^n \to \mathbb{R}\)，先对 \(x_j\) 求导再对 \(x_i\) 求导，记为 \(\frac{\partial^2}{\partial x_i \partial x_j} f\)。在一维情况下，\(\frac{d^2}{dx^2} f\) 可记为 \(f''(x)\)。二阶导数告诉我们一阶导数随输入变化时会如何变化。它的重要性在于告诉我们：仅根据梯度信息，梯度步是否真能带来我们预期的那一改善。我们可以把二阶导数视为对曲率的度量。假设我们有一个二次函数（实际中出现的很多函数虽然不是二次的，但至少在局部可以被相当好地近似为二次）。如果这样的函数的二阶导数为 0，那就没有曲率——它是一条完全平直的线，其值只凭梯度就能预测。若梯度为 1，我们可以沿负梯度方向走一步 \(\epsilon\)，代价函数将减少 \(\epsilon\)。如果二阶导数为负，函数向下弯，代价函数实际上减少得比 \(\epsilon\) 多。最后，若二阶导数为正，函数向上弯，代价函数减少得比 \(\epsilon\) 少（见图 4.4）。

当函数有多个输入维度时，存在许多个二阶导数。这些导数可以被收集到一个矩阵中，称为 Hessian 矩阵。Hessian 矩阵 \(H^{(f)}(\mathbf{x})\) 的定义为 \(H^{(f)}(\mathbf{x})_{i,j} = \frac{\partial^2}{\partial x_i \partial x_j} f(\mathbf{x})\)。等价地，Hessian 是梯度的 Jacobian。在二阶偏导数连续的任何地方，微分算子可交换——\(\frac{\partial^2}{\partial x_i \partial x_j} f(\mathbf{x}) = \frac{\partial^2}{\partial x_j \partial x_i} f(\mathbf{x})\)。这意味着 \(H_{i,j} = H_{j,i}\)，因此 Hessian 矩阵在这些点处是对称的。深度学习中遇到的大多数函数几乎处处都有对称的 Hessian。由于 Hessian 是实对称矩阵，我们可以将其分解为一组实特征值和一个正交的特征向量基。在由单位向量 \(\mathbf{d}\) 表示的特定方向上的二阶导数由 \(\mathbf{d}^\top H \mathbf{d}\) 给出。当 \(\mathbf{d}\) 是 \(H\) 的特征向量时，那个方向上的二阶导数等于相应的特征值。对于 \(\mathbf{d}\) 的其他方向，方向二阶导数是所有特征值的一个加权平均，权重在 0 和 1 之间，与 \(\mathbf{d}\) 夹角更小的特征向量分得更多权重。最大特征值决定最大二阶导数，最小特征值决定最小二阶导数。

（方向）二阶导数能让我们预期梯度下降步能取得多大的效果。我们可以在当前点 \(\mathbf{x}^{(0)}\) 附近对 \(f(\mathbf{x})\) 做二阶 Taylor 展开：\(f(\mathbf{x}) \approx f(\mathbf{x}^{(0)}) + (\mathbf{x} - \mathbf{x}^{(0)})^\top \mathbf{g} + \frac{1}{2} (\mathbf{x} - \mathbf{x}^{(0)})^\top H (\mathbf{x} - \mathbf{x}^{(0)})\)，其中 \(\mathbf{g}\) 是梯度、\(H\) 是 \(\mathbf{x}^{(0)}\) 处的 Hessian。若使用学习率 \(\epsilon\)，则新点为 \(\mathbf{x}^{(0)} - \epsilon \mathbf{g}\)。代回近似式得到 \(f(\mathbf{x}^{(0)} - \epsilon \mathbf{g}) \approx f(\mathbf{x}^{(0)}) - \epsilon \mathbf{g}^\top \mathbf{g} + \frac{1}{2} \epsilon^2 \mathbf{g}^\top H \mathbf{g}\)。这里有三项：函数本身的取值、由函数斜率给出的预期改善、以及用于修正函数曲率的校正项。当最后一项过大时，梯度下降步实际上可能向山上移动。当 \(\mathbf{g}^\top H \mathbf{g}\) 为 0 或为负时，Taylor 近似预测出：让 \(\epsilon\) 无限增大将让 \(f\) 无限减小。但实践中 Taylor 级数不太可能对很大的 \(\epsilon\) 保持准确，因此这种情况下必须用更启发式的方法选 \(\epsilon\)。当 \(\mathbf{g}^\top H \mathbf{g}\) 为正时，使 Taylor 近似的函数减小最多的最优步长为 \(\epsilon^* = \frac{\mathbf{g}^\top \mathbf{g}}{\mathbf{g}^\top H \mathbf{g}}\)。在最坏情况下，当 \(\mathbf{g}\) 与 \(H\) 最大特征值 \(\lambda_{\max}\) 对应的特征向量对齐时，这个最优步长为 \(\frac{1}{\lambda_{\max}}\)。在我们最小化的函数能被很好地近似为二次函数的范围内，Hessian 的特征值从而决定了学习率的尺度。

二阶导数还能用来判定一个临界点是局部极大、局部极小还是鞍点。回忆在临界点处 \(f'(x) = 0\)。当二阶导数 \(f''(x) > 0\) 时，一阶导数 \(f'(x)\) 在向右走时增加、向左走时减少。这意味着对足够小的 \(\epsilon\)，\(f'(x - \epsilon) < 0\)、\(f'(x + \epsilon) > 0\)。换言之，向右移动时斜率开始向右指向上坡，向左移动时斜率开始向左指向上坡。因此当 \(f'(x) = 0\) 且 \(f''(x) > 0\)，可以判定 \(x\) 是局部极小值；类似地，\(f'(x) = 0\) 且 \(f''(x) < 0\) 时 \(x\) 是局部极大值。这称为二阶导数检验。遗憾的是，当 \(f''(x) = 0\) 时，检验无定论——此时 \(x\) 可能是鞍点，也可能属于某个平坦区域的一部分。

在多维情形下，我们需要检查函数所有的二阶导数。利用 Hessian 的特征分解，可以把二阶导数检验推广到多维。在 \(\nabla_\mathbf{x} f(\mathbf{x}) = 0\) 的临界点处，我们可以考察 Hessian 的特征值以判定该临界点是局部极大、局部极小还是鞍点。当 Hessian 正定（所有特征值为正）时，该点是局部极小——这可以通过观察任意方向上的方向二阶导数都为正、并结合单变量二阶导数检验来得出。类似地，当 Hessian 负定（所有特征值都为负）时，该点是局部极大。在多维情形下，实际上可以找到鞍点的正例——当至少有一个特征值为正、至少有一个为负时，\(\mathbf{x}\) 在 \(f\) 的一个横截面上是局部极大、在另一个横截面上是局部极小（例子见图 4.5）。最后，多维的二阶导数检验也可能是无定论的，与单变量版本一样。当所有非零特征值同号、但至少有一个特征值为 0 时，检验无定论；这是因为在对应于零特征值的那个横截面上，单变量二阶导数检验是无定论的。

在多维情形下，单个点上的每个方向都有一个二阶导数。Hessian 在该点处的条件数度量的是这些二阶导数彼此之间的差异有多大。当 Hessian 的条件数很差时，梯度下降表现不好——这是因为在一个方向上导数增长很快，在另一个方向上导数增长很慢。梯度下降意识不到导数的这种变化，因此不知道需要优先探索那个使导数能保持为负更久的方向。这也使选取一个好的步长变得困难——步长必须足够小以避免在具有强正曲率的方向上过冲最小值、上山。这通常意味着步长太小，以至于在曲率较小的其他方向上无法取得有意义的进展。例子见图 4.6。

这一困难可以通过使用 Hessian 矩阵中的信息来引导搜索方向而解决。最简单的方法是 Newton 法。Newton 法基于使用二阶 Taylor 展开来近似点 \(\mathbf{x}^{(0)}\) 附近的 \(f(\mathbf{x})\)：\(f(\mathbf{x}) \approx f(\mathbf{x}^{(0)}) + (\mathbf{x} - \mathbf{x}^{(0)})^\top \nabla_\mathbf{x} f(\mathbf{x}^{(0)}) + \frac{1}{2} (\mathbf{x} - \mathbf{x}^{(0)})^\top H^{(f)}(\mathbf{x}^{(0)}) (\mathbf{x} - \mathbf{x}^{(0)})\)。若接着求这个近似函数的临界点，得到 \(\mathbf{x}^* = \mathbf{x}^{(0)} - H^{(f)}(\mathbf{x}^{(0)})^{-1} \nabla_\mathbf{x} f(\mathbf{x}^{(0)})\)。当 \(f\) 是正定二次函数时，Newton 法只对方程 (4.12) 应用一次就跳到该函数的最小值。当 \(f\) 不是真正的二次函数但可在局部近似为正定二次时，Newton 法对方程 (4.12) 做多次应用。迭代地更新近似并跳到近似的最小点，可以比梯度下降更快地到达临界点。在局部极小附近这是个有用的性质，但在鞍点附近则是有害的。正如将在 8.2.3 节中讨论的，Newton 法只在附近的临界点是最小值（Hessian 的所有特征值都为正）时才适用；而梯度下降只要梯度不指向鞍点，就不会受其吸引。

只使用梯度的优化算法（如梯度下降）称为一阶优化算法。同时也使用 Hessian 矩阵的优化算法（如 Newton 法）称为二阶优化算法（Nocedal and Wright, 2006）。本书大多数语境下使用的优化算法可应用于各种各样的函数，但几乎不附带任何保证。深度学习算法往往缺乏保证，是因为深度学习中使用的函数族相当复杂。许多其他领域中的主流优化方法是为一类受限的函数族专门设计优化算法。

在深度学习的语境中，我们有时通过把自身限制在 Lipschitz 连续或具有 Lipschitz 连续导数的函数上，可以获得某些保证。Lipschitz 连续函数是指其变化率被某个 Lipschitz 常数 \(L\) 所界定的函数 \(f\)：\(\forall \mathbf{x}, \forall \mathbf{y}, |f(\mathbf{x}) - f(\mathbf{y})| \le L \|\mathbf{x} - \mathbf{y}\|_2\)。这一性质是有用的，因为它允许我们把"由梯度下降这类算法所造成的输入的小变化会导致输出的小变化"这一假设定量化。Lipschitz 连续也是相当弱的约束，深度学习中的许多优化问题只要做相对小的改动就能被改造成 Lipschitz 连续的。

也许最成功的专门优化领域是凸优化。凸优化算法能通过对函数做更强的限制提供多得多的保证。凸优化算法只适用于凸函数——这些函数的 Hessian 处处半正定。凸函数行为良好，因为它们不存在鞍点，且所有局部极小值都必然是全局极小值。然而，深度学习中的大多数问题难以用凸优化表达。凸优化仅作为某些深度学习算法的一个子例程被使用。凸优化算法的分析思想对证明深度学习算法的收敛性是有用的。不过，总体而言，凸优化在深度学习语境中的重要性大大降低了。更多关于凸优化的信息可参见 Boyd and Vandenberghe (2004) 或 Rockafellar (1997)。

4.4 有约束优化（Constrained Optimization）

有时我们并不想对 \(x\) 的所有可能取值最大化或最小化 \(f(x)\)，而是希望在某个集合 \(\mathbb{S}\) 中的那些 \(x\) 上找 \(f(x)\) 的极大或极小值。这称为有约束优化。在有约束优化的术语中，位于集合 \(\mathbb{S}\) 中的点 \(\mathbf{x}\) 称为可行点。

我们经常希望找到在某种意义下"小"的解。这种情形下的一种常见方法是对解施加范数约束，比如 \(\|\mathbf{x}\| \le 1\)。有约束优化的一种简单方法是把梯度下降做出修改以考虑约束。若用小的常数步长 \(\epsilon\)，可以做梯度下降步，再把结果投影回 \(\mathbb{S}\)；若用线搜索，则可以只搜那些给出新可行 \(\mathbf{x}\) 点的 \(\epsilon\)，或者把线上的每一点都投影回约束区域。当可能时，更高效的做法是在做步或开始线搜索之前，把梯度投影到可行区域的切空间上（Rosen, 1960）。

一种更复杂的方法是设计一个不同的无约束优化问题，其解可以被转换为原约束优化问题的解。例如我们想对 \(\mathbf{x} \in \mathbb{R}^2\) 最小化 \(f(\mathbf{x})\)，但 \(\mathbf{x}\) 被限制为具有单位 L2 范数，那么可以改为关于 \(\theta\) 最小化 \(g(\theta) = f([\cos\theta, \sin\theta]^\top)\)，再把 \([\cos\theta, \sin\theta]\) 作为原问题的解返回。这一方法需要创造力，每个具体问题都要专门设计原问题与新问题之间的变换。

Karush–Kuhn–Tucker（KKT）方法给出了一个非常一般的求解有约束优化的方案。在 KKT 方法中，我们引入一个叫作广义 Lagrangian 或广义 Lagrange 函数的新函数。要定义 Lagrangian，首先要根据等式和不等式描述 \(\mathbb{S}\)。我们希望把 \(\mathbb{S}\) 用 \(m\) 个函数 \(g^{(i)}\) 和 \(n\) 个函数 \(h^{(j)}\) 来描述，使得 \(\mathbb{S} = \{\mathbf{x} \mid \forall i, g^{(i)}(\mathbf{x}) = 0 \text{ 且 } \forall j, h^{(j)}(\mathbf{x}) \le 0\}\)。涉及 \(g^{(i)}\) 的方程称为等式约束，涉及 \(h^{(j)}\) 的不等式称为不等式约束。

我们为每个约束引入新变量 \(\lambda_i\) 和 \(\alpha_j\)，称为 KKT 乘子。广义 Lagrangian 由此定义为 \(L(\mathbf{x}, \lambda, \alpha) = f(\mathbf{x}) + \sum_i \lambda_i g^{(i)}(\mathbf{x}) + \sum_j \alpha_j h^{(j)}(\mathbf{x})\)。

现在可以通过对广义 Lagrangian 做无约束优化来求解有约束极小化问题。注意到，只要至少有一个可行点存在，且 \(f(\mathbf{x})\) 不被允许为 \(\infty\)，那么 \(\min_{\mathbf{x}} \max_{\lambda} \max_{\alpha, \alpha \ge 0} L(\mathbf{x}, \lambda, \alpha)\) 的最优目标函数值与最优点的集合 \(\mathbf{x}\) 都与 \(\min_{\mathbf{x} \in \mathbb{S}} f(\mathbf{x})\) 相同。原因是当所有约束都被满足时 \(\max_{\lambda} \max_{\alpha, \alpha \ge 0} L(\mathbf{x}, \lambda, \alpha) = f(\mathbf{x})\)，而当任一约束被违反时 \(\max_{\lambda} \max_{\alpha, \alpha \ge 0} L(\mathbf{x}, \lambda, \alpha) = \infty\)。这些性质保证没有任何不可行点能成为最优、且可行点内的最优解不变。

要做有约束最大化，可以构造 \(-f(\mathbf{x})\) 的广义 Lagrange 函数，得到 \(\min_{\mathbf{x}} \max_{\lambda} \max_{\alpha, \alpha \ge 0} \left( -f(\mathbf{x}) + \sum_i \lambda_i g^{(i)}(\mathbf{x}) + \sum_j \alpha_j h^{(j)}(\mathbf{x}) \right)\)。也可以转换为外层取最大化的形式 \(\max_{\mathbf{x}} \min_{\lambda} \min_{\alpha, \alpha \ge 0} \left( f(\mathbf{x}) + \sum_i \lambda_i g^{(i)}(\mathbf{x}) - \sum_j \alpha_j h^{(j)}(\mathbf{x}) \right)\)。等式约束项的符号无关紧要——可以加也可以减，因为优化过程能自由选择每个 \(\lambda_i\) 的符号。

不等式约束特别有趣。我们说若 \(h^{(i)}(\mathbf{x}^*) = 0\) 则该约束是活动的。若一个约束不活动，那么即使去掉该约束，使用原约束求得的解至少仍是局部解。不活动约束也可能把别的解排除在外。例如一个凸问题若具有一整片全局最优点（一片宽且平坦的等代价区域），其子集可能被约束剔除；而一个非凸问题中更好的局部驻点也可能被一个在收敛时并不活动的约束排除。然而，无论是否包含不活动约束，收敛时找到的那个点都仍是驻点。因为不活动的 \(h^{(i)}\) 取负值，\(\min_\mathbf{x} \max_\lambda \max_{\alpha, \alpha \ge 0} L(\mathbf{x}, \lambda, \alpha)\) 的解会让 \(\alpha_i = 0\)。由此可以观察到在解处 \(\alpha \cdot h(\mathbf{x}) = 0\)。换言之，对所有 \(i\)，约束 \(\alpha_i \ge 0\) 与 \(h^{(i)}(\mathbf{x}) \le 0\) 中至少有一个在解处活动。可以这样直观地理解：要么解处于由不等式给出的边界上，必须借助其 KKT 乘子影响 \(\mathbf{x}\) 的解；要么该不等式对解无影响，我们用把它的 KKT 乘子置零来表达这一点。

一组简单的性质刻画了有约束优化问题的最优点。这些性质称为 Karush–Kuhn–Tucker（KKT）条件（Karush, 1939; Kuhn and Tucker, 1951）。它们是必要的而非总是充分的条件。具体条件有：广义 Lagrangian 的梯度为 0；\(\mathbf{x}\) 与 KKT 乘子上的所有约束都满足；不等式约束满足"互补松弛"：\(\alpha \cdot h(\mathbf{x}) = 0\)。更多关于 KKT 方法的信息参见 Nocedal and Wright (2006)。

4.5 示例：线性最小二乘（Example: Linear Least Squares）

假设我们想找使 \(f(\mathbf{x}) = \frac{1}{2} \|A\mathbf{x} - \mathbf{b}\|_2^2\) 取最小值的 \(\mathbf{x}\)。有专门的线性代数算法可以高效地解决这个问题。但我们也可以探索如何用基于梯度的优化来解，作为这些技术如何工作的简单示例。首先需要求梯度：\(\nabla_\mathbf{x} f(\mathbf{x}) = A^\top(A\mathbf{x} - \mathbf{b}) = A^\top A \mathbf{x} - A^\top \mathbf{b}\)。然后可以沿这个梯度下山、做小步，详见算法 4.1。算法 4.1 给出的迭代式为：当 \(\|A^\top A \mathbf{x} - A^\top \mathbf{b}\|_2 > \delta\) 时，更新 \(\mathbf{x} \leftarrow \mathbf{x} - \epsilon(A^\top A \mathbf{x} - A^\top \mathbf{b})\)，其中 \(\epsilon\) 与 \(\delta\) 是小的正数。

这个问题也可以用 Newton 法求解。此时因为真实函数是二次的，Newton 法所采用的二次近似是精确的，算法用一步就收敛到全局最小值。

现在假设我们想最小化同一个函数，但附加约束 \(\mathbf{x}^\top \mathbf{x} \le 1\)。为此引入 Lagrangian \(L(\mathbf{x}, \lambda) = f(\mathbf{x}) + \lambda(\mathbf{x}^\top \mathbf{x} - 1)\)，并求解 \(\min_\mathbf{x} \max_{\lambda, \lambda \ge 0} L(\mathbf{x}, \lambda)\)。

无约束最小二乘问题的最小范数解可以用 Moore–Penrose 伪逆求出：\(\mathbf{x} = A^+ \mathbf{b}\)。若这个点是可行的，它就是有约束问题的解。否则我们必须找到约束活动的那种解。对 Lagrangian 关于 \(\mathbf{x}\) 求导，得到方程 \(A^\top A \mathbf{x} - A^\top \mathbf{b} + 2\lambda \mathbf{x} = 0\)。这告诉我们解将具有形式 \(\mathbf{x} = (A^\top A + 2\lambda I)^{-1} A^\top \mathbf{b}\)。\(\lambda\) 的大小必须取得使结果满足约束。可以通过对 \(\lambda\) 做梯度上升来找到这个值。注意到 \(\frac{\partial}{\partial \lambda} L(\mathbf{x}, \lambda) = \mathbf{x}^\top \mathbf{x} - 1\)。当 \(\mathbf{x}\) 的范数超过 1 时，这个导数为正，因此为沿着导数方向上坡、增加 Lagrangian 关于 \(\lambda\) 的值，我们增大 \(\lambda\)。由于 \(\mathbf{x}^\top \mathbf{x}\) 惩罚项的系数增大，解该线性方程所得到的 \(\mathbf{x}\) 的范数将会更小。解线性方程并调整 \(\lambda\) 的过程持续进行，直到 \(\mathbf{x}\) 具有正确的范数且 \(\lambda\) 处的导数为 0。

作者以"以上即我们用来发展机器学习算法所需的数学预备知识"作为本章的收束，并过渡到下一章开始构建和分析完整的学习系统。

本章个人批注

这一章在 Goodfellow 整本书里的位置很关键：它把第一章铺下的"应用数学与机器学习交叠"具体化为"在数字计算机上做这件事时，会被哪些数值和优化问题咬到"。前两节（4.1、4.2）讲的是"算都算不对"：下溢让分母为 0、溢出让结果变成 NaN、舍入误差被病态矩阵放大。读到这里我立刻想回头去检查自己以前写过的 softmax/log-softmax 实现——教科书里那一行 x - x.max() 看起来琐碎，但意义就在于"在量级差异巨大时它是真的会救命的"；病态条件数那一节则把"为什么 \(\kappa(A)\) 大的矩阵求逆要小心"这件事从纯线代层面挑明了，对我做需要算逆矩阵或解线性系统的工作是一个长存的提醒。

4.3 与 4.3.1 是本章的理论核心，但作者在叙述上有很自觉的取舍：4.3 给的是优化在深度学习语境下的"必要但已经够用"的概念——驻点、局部极小、鞍点、方向导数、最速下降——而把"为什么我们通常只能拿到一个低值而非真正的最小值"明确归因于"深度学习要优化的函数通常有大量鞍点和局部极小"。这部分我用一句话就能讲给同行听："我们不再追求 global optimum，鞍点和 plateau 才是主要障碍。" 然后 4.3.1 顺势引入 Jacobian 和 Hessian，并把它们都锚在"二阶 Taylor 展开 + 学习率 \(\epsilon\)"这条主线上——\(\epsilon^* = \frac{\mathbf{g}^\top \mathbf{g}}{\mathbf{g}^\top H \mathbf{g}}\) 这一行公式，加上"在 worst case 是 \(1/\lambda_{\max}\)"，把"为什么不同方向需要不同步长"这件事说得很干净。我喜欢作者在这里没有一上来就甩 Newton 法，而是先用"\(\mathbf{g}^\top H \mathbf{g}\) 过大让梯度步实际上山"做铺垫、再把 Newton 法的更新式 \(H^{-1} \nabla f\) 解释成"在二次近似下直接跳到临界点"。

但我也有保留。4.3.1 把 Hessian 几乎和 Newton 法画等号，对二阶方法在 deep learning 中"为什么大家其实不用"的现实只给了非常克制的一句话——"deep learning 的函数族太复杂，几乎没有保证"。这与第 8 章里实际展开的 SGD、动量、Adam 等一阶方法形成了一个微妙的张力：理论工具（Hessian/Newton）摆出来一整套，但实际生产却是一阶方法的天下。如果将来某次重读或教学需要补一句，最自然的注脚就是"计算 Hessian 的代价与存储代价在 \(n\) 大时不可承受"，但这一句作者没写，可能因为这正是 8.2.3 节要展开的内容——这也让"4.3.1 末尾直接 forward reference 到 8.2.3"显得很顺理成章。

KKT 那一节（4.4）我读得最累，但内容相对独立：它把"\(\min_\mathbf{x} \max_{\lambda,\alpha \ge 0} L\)"这种 min-max 结构解释成"违反约束就让目标变成 \(\infty\)，所以最优解必然可行"，这在逻辑上是干净的。真正让我停下来想的是"互补松弛"——\(\alpha_i \ge 0\) 与 \(h^{(i)}(\mathbf{x}) \le 0\) 中至少有一个是活动的。作者用"要么解在边界上需要乘子作用、要么不等式无关所以乘子为 0"做了直观解释，但 4.5 的示例让这件事变得具体：当 \(\mathbf{x}\) 范数超过 1 时 \(\partial L / \partial \lambda > 0\)，所以我们增 \(\lambda\)，增大后 \((A^\top A + 2\lambda I)^{-1} A^\top \mathbf{b}\) 的范数变小——这种"对偶上升把范数压回 1"的过程读起来特别让人有"在看着一个方程自我修正"的感觉。

4.5 收尾的线性最小二乘示例选择得很聪明：它不是凭空构造的玩具，而是"前文每一个理论点都能用上"的小场景——梯度、Lipschitz 连续、最速下降、Newton 一步到位、KKT Lagrangian 投影。这里也暗藏了和 2.4 节伪逆那一节的对称关系：无约束时 \(A^+ b\) 给出最小范数解、有约束时若 \(A^+ b\) 不可行再走 KKT——这意味着一个看似"特殊问题"的解实际上可以分阶段地走两种通用方法，是一种很优雅的"特例作为理论收束"。

与上下章的衔接（一段话）

第 4 章夹在第 3 章（概率与信息论，给出"目标函数的不确定性表达"）和第 5 章（机器学习基础，开始真正进入学习问题）之间，承担的角色是"机器学习的数学预备的最末一站"：3 章把目标函数写成期望或对数似然之类的形式，4 章则把"在数字计算机上如何求这类函数的最小/最大值"这件事讲透——从最基本的数值稳定性（4.1、4.2）到优化理论（4.3、4.3.1）再到带约束的推广（4.4）和最小二乘实例（4.5）。作者在 4.5 末尾明确写到"以上即我们用来发展机器学习算法所需的数学预备知识"，是把第 4 章定位为第 1–4 章这一"数学背景"四联章的终章、同时为第 5 章开始的"学习问题"做最后一根承重柱——这一承重柱的关键是让读者在读后面任何优化算法（SGD、动量、Adam、二阶方法、约束优化如投影梯度）时都已经具备"梯度/Hessian/KKT/条件数"这些底层词汇。