《机器学习的数学基础》（7/7）

7、连续优化

Continuous Optimization

由于机器学习算法是在计算机上实现的，其中许多数学方程式都表示为数值优化方法。本章描述了训练机器学习模型的基本数值方法。训练机器学习模型通常归结为找到一组好的参数。“好”的概念是由目标函数或概率模型来决定的，我们将在本书的第二部分看到这些例子。给定一个目标函数，使用优化算法来寻找最佳值。\(\mathbb{R}^{D}\) 中考虑数据和模型，所以我们面临的优化问题是连续优化问题，而不是离散变量的组合优化问题。

一般情况下，机器学习中的大多数目标函数都是要被最小化的，即最优值就是最小值。直观上，梯度为目标函数每个点的上坡方向，而我们的目的是下坡（与梯度方向相反），希望找到最深的点。

我们将学习一类称为凸函数的函数，它们对优化算法的起点没有依赖性。对于凸函数，局部最小值就是全局最小值。事实证明，许多机器学习目标函数的设计都是凸的.

一般研究最小值，所以对应研究的也是凸函数（数学定义上是开口向上的函数）。

7.1 使用梯度下降法优化

梯度下降法是一种一阶优化算法。为了用梯度下降法寻找函数的局部最小值，我们取与函数在当前点的梯度的一定比例的负值调整\(x\)。回想第5.1节，梯度指向最陡的上升方向。另一个直观的表现是考虑函数的等高线。梯度指向与我们希望优化的函数的等高线正交的方向。

梯度一定是指向上升的方向：
严格来说，梯度确实指向函数在某一点上“最陡上升”的方向。梯度的符号和大小告诉我们函数值局部上升最快的方向和速率。对于一元函数，梯度的正负直接指明函数上升的方向。
梯度的几何意义：

• 梯度方向是函数值增加最快的方向。
• 梯度的大小 \(\|\nabla f(\boldsymbol{x})\|\) 表示该方向上函数上升的速率。
• 如果沿着梯度的负方向移动 \(-\nabla f(\boldsymbol{x})\)，则是下降最快的方向（常用于梯度下降算法）。

梯度是函数上升最快的方向。但它只描述局部方向，想找最大值还需要结合函数整体信息。
例如 \(y=x^2\),导数是\(2x\)，针对负轴，导数<0;所以沿\(x\)轴负方向是函数值上升最快的方向，反之也能推导出。

自适应梯度方法能根据函数的局部性质，在每次迭代时重新调整步长。有两种简单的方法（Toussaint，2012）：

• 当采用梯度下降后函数值增大了，则表明步长过大了。这时我们可以撤消并减小步长。
• 当函数值减小时，我们可以尝试增大步长。

尽管“撤消”步骤似乎是浪费资源，但使用这种启发式方法可以保证单调收敛。

7.1.1 动量梯度下降

如图7.3所示，如果优化的曲面的存在缩放效果不佳的区域，那么梯度下降的收敛速度可能非常慢。改进收敛性的一个方法是给梯度下降添加记忆项。动量梯度下降法（Rumelhart et al.，1986）引入了附加项来记忆上一次迭代中发生了什么。这种记忆可以抑制振荡，平滑梯度更新。继续用球做类比，动量项模拟了重球从斜坡滚下不会轻易改变方向的现象。其思想是使用记忆进行梯度更新，以实现滑动平均( moving average)。基于动量的方法记忆了每次迭代的更新量\(\Delta \boldsymbol{x}_{i}\),下一次更新则用当前和之前梯度的线性组合确定：

7.1.2 随机梯度下降法

计算梯度非常耗时。然而，通常可以找到梯度的“cheap”近似值。只要近似梯度指向与真实梯度大致相同的方向，那么它就是有用的。

随机梯度：它不是确切的梯度，而是一个基于随机采样得到的噪声版本（随机近似）。

随机梯度下降法（Stochastic gradient descent，通常简称为SGD）是梯度下降法的一种随机近似方法，用于最小化目标函数，且目标函数应是可微函数之和。这里的“随机”一词指的是这样一个事实，即我们承认我们并不精确地知道梯度，而是只知道它的噪声近似值。通过约束近似梯度的概率分布，我们仍然可以从理论上保证SGD收敛。

如前所述，标准梯度下降法是一种“批量”优化方法，即选取合适的步长参数 \(gamma_i\)，并使用所有训练集，然后通过以下公式更新向量参数： \[ \boldsymbol{\theta}_{i+1} = \boldsymbol{\theta}_{i} - \gamma_{i} \left( \nabla L(\boldsymbol{\theta}_{i}) \right)^{\top} = \boldsymbol{\theta}_{i} - \gamma_{i} \sum_{n=1}^{N} \left( \nabla L_{n}(\boldsymbol{\theta}_{i}) \right)^{\top} \qquad (7.15) \] 求梯度和可能需要对所有\(L_n\)的梯度进行计算。当训练集是巨大的，或者（并且）损失函数不是简单的公式时，计算梯度和需要消耗巨大的计算资源。

考虑 (7.15) 中的\(\sum_{n=1}^{N}\left(\nabla L_{n}\left(\boldsymbol{\theta}_{i}\right)\right),\)我们可以取较小的 \(L_n\) 集合来求它们的梯度和以减少计算量。与批量梯度下降法使用 \(n=1,\ldots,N\) 的所有 \(L_n\) 不同，小批量梯度下降随机选取 \(L_n\) 的子集。在极端情况下，我们还可以随机选择一个 \(L_n\) 来估计梯度。

关于为什么选取数据子集是明智的，关键的见解是要认识到，为了使梯度下降收敛，我们只要求梯度是真实梯度的无偏估计。事实上，(7.15) 中的\(\sum_{n=1}^{N}\left(\nabla L_{n}\left(\boldsymbol{\theta}_{i}\right)\right)\)是梯度期望值（第 6.4.1 节）的经验估计。因此，对期望值的任何其他无偏经验估计，例如使用数据的任何子样本，将足以使梯度下降收敛。

备注： 当学习率以适当的速率下降时，在相对不严格的假设下，随机梯度下降必然收敛到局部最小值（Bottou, 1998）。

为什么要考虑使用近似梯度？一个主要原因是硬件的限制，例如中央处理器（CPU）/图形处理器（GPU）内存大小或计算时间的限制。我们可以像在估计经验平均数时考虑样本的大小一样（第 6.4.1 节），来考虑用来估计梯度的子集的大小。 较大的小批量将提供准确的梯度估计，减少参数更新中的方差。此外，较大的小批量可以使代价和梯度向量化，从而能使用高度优化的矩阵运算。方差的减少导致更稳定的收敛性，但每次梯度计算的计算量都很大。

相比之下，较小的小批量可以很快估计。如果我们保持较小的小批量，梯度估计中的噪声将允许我们脱离局部最优解。在机器学习中，优化方法是利用训练数据，通过最小化目标函数来进行训练的，但总体目标是提高泛化性能（第 8 章）。由于机器学习的目标不一定需要精确估计目标函数的最小值，所以使用小批量方法的近似梯度被广泛使用。

7.2 约束优化与拉格朗日乘子

拉格朗日对偶( Lagrangian duality)的概念。一般来说，对偶优化的思想是将一组变量\(\boldsymbol{x}\)（称为原始变量）的优化问题转化为另一组变量\(\boldsymbol{\lambda}\)（称为对偶变量）的优化问题。我们将会介绍两种不同的对偶方法：在本节中，我们讨论的是拉格朗日对偶；在第7.3.3节中，我们将讨论Legendre-Fenchel对偶。

对偶问题计算上的好处

• 有时原问题不好解，但对偶问题更容易（例如约束简单、凸结构更明显）。
• 在大规模问题（如支持向量机 SVM）中，通常是通过对偶问题求解的。

不等式约束对应的拉格朗日乘子约束为非负，而等式约束对应的拉格朗日乘子则不加约束。

通过引入与每个不等式约束分别对应的拉格朗日乘子 \(\lambda_i \geq 0\) （Boyd 和 Vandenberghe，2004，第 4 章），得到：

\[ \begin{equation} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) + \sum_{i=1}^{m} \lambda_i g_i(\boldsymbol{x}) = f(\boldsymbol{x}) + \boldsymbol{\lambda}^{\top} \boldsymbol{g}(\boldsymbol{x}) \qquad (7.20) \end{equation} \]

其中我们将所有约束 \(g_i(\boldsymbol{x})\) 写成一个向量 \(\boldsymbol{g}(\boldsymbol{x})\)； 把所有拉格朗日乘子也写成向量 \(\boldsymbol{\lambda} \in \mathbb{R}^{m}\)。

我们现在介绍拉格朗日对偶 (Lagrangian duality)}的概念。 一般来说，对偶优化的思想是将一组变量 \(\boldsymbol{x}\)（称为原始变量）的优化问题转化为另一组变量 \(\boldsymbol{\lambda}\)（称为对偶变量）的优化问题。 定义7.1 问题 \[ \begin{equation} \min_{\boldsymbol{x}} f(\boldsymbol{x}) \quad \text{subject to} \quad g_i(\boldsymbol{x}) \leqslant 0, \quad i=1,\ldots,m \end{equation} \] 被称为 原始问题 (primal problem)，对应原始变量 \(\boldsymbol{x}\)。

与它对应的拉格朗日对偶问题 (Lagrangian dual problem)由下式给出： \[ \begin{equation} \max_{\boldsymbol{\lambda} \in \mathbb{R}^m} \; \mathfrak{D}(\boldsymbol{\lambda}) \quad \text{subject to} \quad \boldsymbol{\lambda} \geqslant \mathbf{0}, \end{equation} \] 其中 \(\boldsymbol{\lambda}\) 为对偶变量，且 \[ \begin{equation} \mathfrak{D}(\boldsymbol{\lambda}) = \min_{\boldsymbol{x} \in \mathbb{R}^d} \; \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}). \end{equation} \]

7.3 凸优化

让我们我们重点讨论一类特别有用的优化问题上，因为在这类问题上我们可以保证得到全局最优解。

目标函数\(f(·)\)是一个凸函数，且约束\(g(·)\)和\(h(·)\)是凸集的问题称为凸优化问题( convex optimization problem)。

哪些约束会产生“凸集”？：

约束类型	产生的可行集	是否凸
线性不等式 \(a^\top x \le b\)	半空间	✔凸
线性等式 \(Ax=b\)	仿射子空间	✔凸
二次凸约束 \(x^\top Qx \le 1\)	椭球	✔凸
范数约束 \(\|x\|\le r\)	球或圆盘	✔凸
Box 约束	超立方体	✔凸
任意凸函数 \(g(x)\le 0\)	凸集	✔凸

在这种情况下，称它具有强对偶性(strong duality)：对偶问题的最优解与原问题的最优解相同。在机器学习文献中，凸函数和凸集通常是不严格区别的，但是人们通常可以从上下文中推断出隐含的含义。

注：凸函数的非负加权和是凸的.

7.3.1 线性规划

考虑所有函数都是线性的特殊情况，即： \[ \begin{equation} \min_{\boldsymbol{x} \in \mathbb{R}^{d}} \boldsymbol{c}^{\top} \boldsymbol{x} \qquad (7.39) \end{equation} \]

\[ \text{subject to } \quad \boldsymbol{A}\boldsymbol{x} \leqslant \boldsymbol{b} \] 其中 \(\boldsymbol{A} \in \mathbb{R}^{m \times d}, \ \boldsymbol{b} \in \mathbb{R}^{m}\)。

取 \(\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})\) 对 \(\boldsymbol{x}\) 的导数并将其设为零(因为是\(x\)的一次函数，求导消去了\(x\))，得到对偶优化问题，是关于\(\lambda\)的线性规划问题，但有\(m\)个变量。我们可以选择求解原始规划问题（7.39）或其对偶规划问题（7.43），这取决于\(m\)和\(d\)哪个更大。

7.3.2 二次规划

考虑凸二次目标函数的情况，其中约束是仿射的，即： \[ \min_{\boldsymbol{x} \in \mathbb{R}^{d}} \frac{1}{2} \boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}^{\top} \boldsymbol{x} \]

\[ \text{subject to} \quad \boldsymbol{A}\boldsymbol{x} \leqslant \boldsymbol{b} \] 其中 \(\boldsymbol{A} \in \mathbb{R}^{m \times d},\ \boldsymbol{b} \in \mathbb{R}^{m},\ \boldsymbol{c} \in \mathbb{R}^{d}\)。

对称方阵 \(\boldsymbol{Q} \in \mathbb{R}^{d \times d}\) 是正定的，因此目标函数是凸的。这就是所谓的二次规划。注意它有 \(d\) 个变量和 \(m\) 个线性约束。

一般定义二次规划（QP）时，只要求 \(Q\) 半正定（positive semidefinite, PSD），这样目标函数就是凸的；

同线性规划，取 \(\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})\) 对 \(\boldsymbol{x}\) 的导数，并将其设为零(因为是\(x\)的二次函数，求导得到关于\(x\)的一次方程，可以用\(\lambda\)替换\(x\)代入对耦优化问题)，得到对偶优化问题，是关于\(\lambda\)的二次规划问题。

7.3.3 Legendre-Fenchel变换和凸共轭

这一节没深入看！

全书的读书笔记（共7篇）如下：
《机器学习的数学基础》读书笔记之一 ：导言
《机器学习的数学基础》读书笔记之二 ：线性代数
《机器学习的数学基础》读书笔记之三 ：解析几何
《机器学习的数学基础》读书笔记之四 ：矩阵分解
《机器学习的数学基础》读书笔记之五 ：向量微积分
《机器学习的数学基础》读书笔记之六 ：概率与分布
《机器学习的数学基础》读书笔记之七 ：连续优化