《机器学习的数学基础》第12章"支持向量机分类"

第12章 支持向量机分类

在许多情况下，我们希望机器学习算法能够预测若干（离散）结果中的一个。例如，电子邮件客户端会将邮件分为个人邮件和垃圾邮件，这就有两个结果。另一个例子是望远镜识别夜空中的天体是星系、恒星还是行星。通常结果的数量较少，更重要的是，这些结果之间往往没有额外的结构。 在本章中，我们考虑输出二元值的预测器，也就是说，只有两种可能的结果。这种机器学习任务称为二分类（binary classification）。这与第 9 章形成对比，当时我们讨论的是连续值输出的预测问题。对于二分类，标签/输出可以取的值是二元的，本章中我们用 {+1,−1} 表示。换句话说，我们考虑的预测器形式为 \[ f:\mathbb{R}^D \to \{+1,-1\}. \tag{12.1} \]

回忆第 8 章，我们用 \(D\) 个实数的特征向量表示每个样本（数据点）\(x_n\)。标签通常分别称为正类（positive class）和负类（negative class）。但应当注意，不要根据“正”或“负”字面意义推断+1类的直观属性。例如，在癌症检测任务中，有癌症的患者往往被标记为+1。原则上可以使用任何两个不同的值，例如{True,False}、{0,1}或{red,blue}。二分类问题研究得比较充分，其他方法的综述我们放到 12.6 节再介绍。我们将介绍一种称为支持向量机（Support Vector Machine, SVM）的方法，它用于解决二分类任务。与回归类似，这是一个监督学习任务：我们有一组样本 \(x_n \in \mathbb{R}^D\)，以及对应的（二元）标签 \(y_n \in \{+1,-1\}\)。给定一个包含样本–标签对 \(\{(x_1,y_1),\dots,(x_N,y_N)\}\) 的训练数据集，我们希望估计模型参数，使分类错误率最小。类似第 9 章，我们考虑线性模型，并把非线性隐藏在对样本的一个变换 \(\phi\) 中（见式(9.13)）。我们将在 12.4 节重新讨论 \(\phi\)。

支持向量机（SVM）在许多应用中都能提供最先进的结果，并且具有坚实的理论保证（Steinwart 和 Christmann, 2008）。我们之所以选择用 SVM 来说明二分类问题，主要有两个原因。

首先，SVM 提供了一种几何方式来思考监督学习问题。 在第 9 章中，我们是从概率模型的角度来看待机器学习问题，并用极大似然估计和贝叶斯推断来解决。而在这里，我们考虑一种替代的方法，即从几何角度来推理机器学习任务。这种方法高度依赖于我们在第 3 章讨论过的内积和投影等概念。

第二个原因是，与第 9 章不同，SVM 的优化问题没有解析解，因此需要借助第 7 章介绍的各种优化工具。 SVM 对机器学习的理解与第 9 章的极大似然方法存在细微的差异：极大似然方法是基于数据分布的概率观点提出一个模型，再由此推导出一个优化问题；而 SVM 的方法则是从几何直觉出发，先设计一个需要在训练过程中被优化的函数。我们已经在第 10 章看到过类似的情况，当时我们从几何原理出发推导了 PCA。在 SVM 的例子中，我们通过设计一个损失函数来度量训练数据上的误差，并遵循经验风险最小化原则（第 8.2 节），在训练中加以最小化。

接下来，我们推导 SVM 的训练优化问题。 直观上，我们可以想象一个二分类数据，它们能够被一个超平面分开，如图 12.1 所示。

在这里，每个样本 \(x_n\)（一个二维向量）是一个二维位置（\(x^{(1)}_n, x^{(2)}_n\)），对应的二元标签 \(y_n\) 则是两种不同的符号（橙色叉号或蓝色圆点）。“超平面”（hyperplane）是机器学习中常用的术语，我们在第 2.8 节已经遇到过。超平面是一个仿射子空间，维度为 \(D-1\)（如果对应的向量空间维度是 \(D\)）。在二分类中，两个类别的样本（对应两种可能的标签）在特征空间中分布得刚好可以用一条直线（在二维情况下）来分开。

个人注：注意：在 \(n\) 维空间 (\(\mathbb{R}^n\)) 中，超平面（hyperplane）按定义就是一个 \((n-1)\) 维的仿射子空间。

个人注：引用前文2.8.1节的例子。

例 2.26（仿射子空间）

• 一维仿射子空间称为直线

可写为 \[ y = x_0 + \lambda b_1, \]

其中 \(\lambda \in \mathbb{R}\)，且 \(U=\text{span}[b_1]\subseteq \mathbb{R}^n\) 是 \(\mathbb{R}^n\) 的一维子空间。 这意味着一条直线由一个支撑点（support point）\(x_0\) 和一个定义方向的向量 \(b_1\) 决定。图 2.13 给出了示意图。

• \(\mathbb{R}^n\) 中的二维仿射子空间称为平面

其参数方程为

\[ y = x_0 + \lambda_1 b_1 + \lambda_2 b_2, \]

其中 \(\lambda_1,\lambda_2 \in \mathbb{R}\)，且 \(U=\text{span}[b_1,b_2]\subseteq \mathbb{R}^n\)。 这意味着一个平面由一个支撑点 \(x_0\) 和两个线性无关的向量 \(b_1,b_2\) 确定，这两个向量张成方向空间。

• 在 \(\mathbb{R}^n\) 中，\((n-1)\) 维的仿射子空间称为超平面（hyperplane）

其对应的参数方程为

\[ y = x_0 + \sum_{i=1}^{n-1} \lambda_i b_i, \]

其中 \(b_1,\dots,b_{n-1}\) 组成 \(\mathbb{R}^n\) 中一个 \((n-1)\) 维子空间 \(U\) 的一组基。 这意味着一个超平面由一个支撑点 \(x_0\) 和 \((n-1)\) 个线性无关的向量 \(b_1,\dots,b_{n-1}\) 确定，这些向量张成方向空间。

在 \(\mathbb{R}^2\) 中，一条直线也是一个超平面；在 \(\mathbb{R}^3\) 中，一个平面也是一个超平面。

在下面的推导中，我们将形式化“寻找一个线性分隔器”的思想。我们会引入间隔（margin）的概念，并进一步推广线性分隔器，使其允许某些样本落在“错误”的一侧，从而引入分类误差。我们将介绍两种等价的 SVM 形式化方式：

• 几何视角（第 12.2.4 节），
• 损失函数视角（第 12.2.5 节）。

随后，我们利用 拉格朗日乘子法（第 7.2 节）推导 SVM 的对偶形式。对偶 SVM 使我们能够看到第三种形式化 SVM 的方式：即从每个类别样本的凸包的角度来理解（第 12.3.2 节）。最后，我们会简要介绍核方法，以及如何数值化地求解非线性核 SVM的优化问题。

12.1 分离超平面

给定两个用向量 \(x_i\) 和 \(x_j\) 表示的样本，衡量它们相似度的一种方法是使用内积 \(\langle x_i, x_j\rangle\)。回忆第 3.2 节，内积与两个向量之间的夹角密切相关。两个向量内积的值不仅取决于它们之间的夹角，还取决于每个向量的长度（范数）。此外，内积还允许我们严格地定义几何概念，比如正交性和投影。

许多分类算法背后的主要思想是：把数据表示在 \(\mathbb{R}^D\) 空间中，然后对这个空间进行划分，理想情况下，同一标签的样本（且不包含其他样本）会位于同一个分区中。对于二分类，空间会被划分成两部分，分别对应正类和负类。我们考虑一种特别方便的划分方式：用一个超平面将空间（线性地）分成两半。设样本 \(x\in \mathbb{R}^D\) 是数据空间中的一个元素，考虑一个函数

\[ f:\mathbb{R}^D \to \mathbb{R} \tag{12.2a} \]

\[ x \mapsto f(x):=\langle w,x\rangle+b \tag{12.2b} \]

其中参数 \(w\in\mathbb{R}^D\)，\(b\in\mathbb{R}\)。回忆第 2.8 节，超平面是一个仿射子空间。因此，我们可以将二分类问题中分隔两类的超平面定义为：

\[ \{ x\in\mathbb{R}^D: f(x)=0. \} \tag{12.3} \]

图 12.2 给出了这个超平面的示意图，其中向量 \(w\) 是超平面的法向量，\(b\) 是截距。

我们可以证明，\(w\) 确实是 (12.3) 中超平面的法向量。方法是：任选两个在超平面上的样本 \(x_a\) 和 \(x_b\)，证明它们的差向量与 \(w\) 正交。

写成方程形式：

\[ \begin{align} f(x_a)-f(x_b) &= \langle w,x_a\rangle+b - \big(\langle w,x_b\rangle+b\big) \tag{12.4a}\\ &=\langle w,x_a-x_b\rangle, \tag{12.4b} \end{align} \]

第二行利用了内积的线性性（第 3.2 节）。由于我们选择了 \(x_a\) 和 \(x_b\) 在超平面上，这意味着 \(f(x_a)=0\) 且 \(f(x_b)=0\)，因此 \(\langle w,x_a-x_b\rangle=0\)。回忆：当两个向量的内积为 0 时，它们正交。因此，我们得到 \(w\) 与超平面上任意向量都正交，也就是说 \(w\) 是超平面的法向量。

注释:回忆第 2 章，我们可以从不同角度理解向量。在本章中，我们把参数向量 \(w\) 看作一个表示方向的箭头，也就是说，我们把 \(w\) 当作几何向量来理解。相反，我们把样本向量 \(x\)看作一个数据点（由其坐标表示），也就是说，我们把 \(x\) 当作相对于标准基的一个向量坐标来理解。

在给定一个测试样本时，我们根据它位于超平面的哪一侧将其分类为正例或负例。注意，式 (12.3) 不仅定义了一个超平面，还定义了一个方向。换句话说，它规定了超平面的正侧和负侧。因此，为了分类测试样本 \(x_{test}\)，我们计算函数 \(f(x_{test})\) 的值，如果 \(f(x_{test}) ≥ 0\) 则判为 +1，否则判为 −1。从几何角度看，正例位于超平面“上方”，负例位于“下方”。

在训练分类器时，我们希望带有正标签的样本位于超平面的正侧，即

\[ \langle w, x_n \rangle + b \ge 0 \quad \text{当} \; y_n = +1 \tag{12.5} \]

并且希望带有负标签的样本位于超平面的负侧，即

\[ \langle w, x_n \rangle + b < 0 \quad \text{当} \; y_n = -1 \tag{12.6} \]

参见图 12.2 来获得关于正负样本的几何直观。这两个条件常常可以写成一个式子：

\[ y_n \,(\langle w, x_n \rangle + b) \ge 0 \tag{12.7} \]

式 (12.7) 与 (12.5) 和 (12.6) 是等价的，因为我们分别把 (12.5) 和 (12.6) 两边乘上 \(y_n = +1\) 和 \(y_n = -1\)。

12.2 原始支持向量机

基于点到超平面的距离概念，我们现在可以讨论支持向量机了。对于一个线性可分的数据集\(\{(x_1, y_1), \ldots, (x_N, y_N)\}\)，我们有无穷多候选超平面（见图 12.3），也就有无穷多候选分类器，可以在没有（训练）错误的情况下解决分类问题。为了找到唯一解，一个思路是选择能够最大化正例和负例之间间隔（margin）的分离超平面。换句话说，我们希望正负样本被一个“间隔很大”的超平面分开（第 12.2.1 节）。下面我们将计算样本与超平面的距离，从而推导出 margin 的定义。回忆给定点（样本 \(x_n\)）到超平面最近的点是通过正交投影获得的（第 3.8 节）。

12.2.1 间隔的概念

Margin

间隔的概念直观上非常简单：它是分离超平面到数据集中最近样本的距离（假设数据集线性可分）。然而，在形式化这个距离时有一个技术小问题，可能会让人困惑。这个小问题是我们需要定义一个测量距离的尺度。一个潜在的尺度是数据本身的尺度，即 \(x_n\) 的原始值。但这样做有问题：我们可以改变 \(x_n\) 的度量单位而改变 \(x_n\) 的值，从而改变到超平面的距离。正如我们很快将看到的，我们用超平面方程 (12.3) 本身来定义尺度。考虑一个超平面 \(\langle w,x\rangle + b\)，以及一个样本 \(x_a\)，如图 12.4 所示。不失一般性，我们可以假设样本 \(x_a\) 在超平面的正侧，即 \(\langle w, x_a\rangle + b > 0\)。我们希望计算 \(x_a\) 到超平面的距离 \(r>0\)。我们通过考虑 \(x_a\) 到超平面的正交投影（第 3.8 节）来实现，投影点记为 \(x_a'\)。

由于 \(w\) 垂直于超平面，我们知道距离 \(r\) 只是向量 \(w\) 的一个缩放。如果 \(w\) 的长度已知，我们就可以用这个缩放因子 \(r\) 求出 \(x_a\) 和 \(x_a'\) 之间的绝对距离。为了方便，我们选择使用一个单位长度的向量（范数为 1），通过将 \(w\) 除以它的范数得到：\(\frac{w}{\|w\|}\)。使用向量加法（第 2.4 节），我们得到：

\[ x_a = x_a' + r \,\frac{w}{\|w\|} \tag{12.8} \]

另一种理解 \(r\) 的方式是：它是 \(x_a\) 在由 \(\frac{w}{\|w\|}\) 张成的子空间中的坐标。现在我们把 \(x_a\) 到超平面的距离表达为 \(r\)。如果我们选择 \(x_a\) 是距离超平面最近的点，那么这个距离 \(r\) 就是 margin（间隔）。回忆我们希望正例在超平面正方向上距离至少为 \(r\)，负例在超平面负方向上距离至少为 \(r\)。与把 (12.5) 和 (12.6) 合并为 (12.7) 类似，我们将这个目标写为：

\[ y_n\bigl(\langle w,x_n\rangle + b\bigr) \;\geq\; r \tag{12.9} \]

换句话说，我们把样本在正负方向上都至少距离超平面 \(r\) 的要求合并到了一条不等式里。

由于我们只关心方向，我们在模型中加一个假设：参数向量 \(w\) 是单位长度的，即 \(\|w\|=1\)，其中 \(\|w\|=\sqrt{w^\top w}\) 是欧几里得范数（第 3.1 节）。这个假设也使得 (12.8) 中距离 \(r\) 有了更直观的解释，因为它是一个长度为 1 的向量的缩放因子。

注：熟悉其他 margin 定义的读者会注意到，我们这里取 \(\|w\|=1\) 的方式与 Schölkopf 和 Smola (2002) 等书中的标准表述不同。在第 12.2.3 节我们会展示两种方法的等价性。

将三个要求收集到一个带约束的优化问题中，我们得到目标函数：

\[ \max_{w,b,r} \; r \tag{12.10} \]

满足约束：

• \(y_n(\langle w,x_n\rangle + b)\;\geq\;r\) （数据满足约束），
• \(\|w\|=1\) （归一化），
• \(r>0\)，

这表示我们要在保证所有数据在超平面正确一侧的前提下，最大化间隔 \(r\)。

注：margin 的概念在机器学习中无处不在。Vladimir Vapnik 和 Alexey Chervonenkis 利用这个概念证明了当 margin 很大时，函数类的“复杂度”较低，因此学习是可行的（Vapnik, 2000）。事实证明，这个概念在许多不同的理论分析泛化误差的方法中都非常有用（Steinwart 和 Christmann, 2008；Shalev-Shwartz 和 Ben-David, 2014）。

12.2.2 边界的传统推导

Margin

在前一节中，我们通过观察只关心 \(w\) 的方向而不关心其长度，得到了假设 \(\|w\|=1\)，并由此推导出式 (12.10)。在本节中，我们将通过另一种假设来推导边界最大化问题。我们不再选择参数向量归一化，而是选择对数据进行缩放。我们通过这样的缩放，使得预测器 \(\langle w,x\rangle + b\) 在距离超平面最近的样本处等于 1。我们将数据集中距离超平面最近的样本记作 \(x_a\)。

图 12.5 与图 12.4 相同，只是现在我们重新缩放了坐标轴，使得样本 \(x_a\) 正好位于边界上，即

\[ \langle w,x_a\rangle + b = 1. \]

由于 \(x'_a\) 是 \(x_a\) 在超平面上的正交投影，按定义它必定位于超平面上，即

\[ \langle w,x'_a\rangle + b = 0. \tag{12.11} \]

将 (12.8) 代入 (12.11)，我们得到

\[ \langle w,\;x_a - \frac{r}{\|w\|} w \rangle + b = 0. \tag{12.12} \]

利用内积的双线性性质（见第 3.2 节），我们得到

\[ \langle w,x_a\rangle + b - r \frac{\langle w,w\rangle}{\|w\|} = 0. \tag{12.13} \]

注意，根据我们的缩放假设，第一项为 1，即 \(\langle w,x_a\rangle + b=1\)。根据第 3.1 节的式 (3.16)，\(\langle w,w\rangle = \|w\|^2\)。因此，第二项可简化为 \(r\|w\|\)。利用这些简化，我们得到

\[ \frac{1}{r} = \|w\|. \tag{12.14} \]

这意味着我们将距离 \(r\) 表示为了超平面的法向量 \(w\) 的形式。乍一看，这个等式似乎不直观，因为我们好像是用向量 \(w\) 的长度来表示超平面的距离，但我们还不知道这个向量。一种理解方式是，将距离 \(r\) 看作一个临时变量，仅用于推导。因此，在本节余下部分，我们用 \(\frac{1}{\|w\|}\) 表示到超平面的距离。在第 12.2.3 节中，我们将看到“边界等于 1”这一选择与第 12.2.1 节中假设 \(\|w\|=1\) 是等价的。类似于推导式 (12.9) 的思路，我们希望正例和负例都至少距离超平面 1 个单位，因此得到条件

我们还可以把这个距离理解为当 \(x_a\) 投影到超平面上时产生的投影误差。

\[ y_n(\langle w,x_n\rangle + b)\ge 1. \tag{12.15} \]

将边界（margin）最大化与“样本需要位于超平面正确一侧（依据其标签）”这一事实结合起来，就得到

\[ \max_{w,b}\;\frac{1}{\|w\|} \tag{12.16} \]

满足约束条件

\[ y_n(\langle w,x_n\rangle + b)\ge 1,\quad \text{对于所有 }n=1,\dots,N. \tag{12.17} \]

与其像式 (12.16) 那样最大化范数的倒数，我们通常最小化范数的平方。同时我们还经常加入一个常数 \(\tfrac{1}{2}\)，它不会影响最优的 \(w,b\)，但在计算梯度时能使形式更简洁。于是我们的目标变为

\[ \min_{w,b}\;\frac{1}{2}\|w\|^2 \tag{12.18} \]

满足约束条件

\[ y_n(\langle w,x_n\rangle + b)\ge 1,\quad \text{对于所有 }n=1,\dots,N. \tag{12.19} \]

式 (12.18) 被称为硬间隔支持向量机（hard margin SVM）。“硬（hard）”这一说法是因为这种形式不允许任何违反边界条件的情况。 我们将在第 12.2.4 节看到，如果数据不是线性可分的，这个“硬”条件可以放宽，以容纳一些违反边界条件的样本。

12.2.3 为什么我们可以把间隔设为 1

在第 12.2.1 节，我们提出我们希望最大化某个值 \(r\)，它表示距离超平面最近的样本点到超平面的距离。在第 12.2.2 节，我们通过缩放数据，使得最近的样本点到超平面的距离正好为 1。在本节，我们把这两种推导联系起来，并展示它们是等价的。

定理 12.1:在 (12.10) 中考虑归一化权重的情况下，最大化间隔 \(r\)： \[ \max_{w,b,r} \; r \quad\text{（margin）} \]

满足

\[ y_n(\langle w,x_n\rangle + b) \ge r \quad\text{（data fitting）},\qquad \|w\|=1 \quad\text{（normalization）},\qquad r>0, \tag{12.20} \]

等价于对数据进行缩放，使得间隔为 1：

\[ \min_{w,b} \;\frac{1}{2}\|w\|^2 \quad\text{（margin）} \]

满足

\[ y_n(\langle w,x_n\rangle + b) \ge 1 \quad\text{（data fitting）}. \tag{12.21} \]

证明 考虑 (12.20)。因为平方对于非负自变量是严格单调的，所以在目标函数中把 \(r\) 换成 \(r^2\) 最大值保持不变。由于 \(\|w\|=1\)，我们可以通过引入一个未归一化的新权重向量 \(w'\) 重新参数化：显式写成 \(w=w'/\|w'\|\)。于是得到： \[ \max_{w',b,r} r^2 \quad \text{s.t.}\quad y_n\Bigl( \frac{w'}{\|w'\|},x_n\Bigr)+b \ge r,\quad r>0. \tag{12.22} \]

式 (12.22) 明确表明距离 \(r\) 是正的。因此，我们可以将第一个约束除以 \(r\)，得到：

\[ \max_{w',b,r} r^2 \quad \text{s.t.}\quad y_n\!\left( \frac{w'}{\|w'\|r},x_n +\frac{b}{r}\right)\ge 1,\quad r>0, \tag{12.23} \]

然后把参数重命名为 \(w''\) 和 \(b''\)。因为 \(w''=\frac{w'}{\|w'\|r}\) 得到\(\|w''\|=\frac{1}{r}\cdot r\)。将这一结果代入 (12.23)，我们得到：

\[ \max_{w'',b''} \frac{1}{\|w''\|^2} \quad \text{s.t.}\quad y_n(\langle w'',x_n\rangle + b'')\ge 1. \tag{12.24} \]

最后一步是注意到，最大化 \(\frac{1}{\|w''\|^2}\) 与最小化 \(\frac{1}{2}\|w''\|^2\) 得到的解是相同的，这就完成了定理 12.1 的证明。

\[ \begin{equation} \begin{aligned} & \max_{\boldsymbol{w}'', b''} \frac{1}{\|\boldsymbol{w}''\|^2} \\ & \text{subject to} \quad y_n \left( \langle \boldsymbol{w}'', \boldsymbol{x}_n \rangle + b'' \right) \geq 1. \end{aligned} \tag{12.25} \end{equation} \]

12.2.4 软间隔 SVM：几何视角

当数据不是线性可分时，我们可能希望允许某些样本落在间隔区域内，甚至位于超平面的错误一侧，如图 12.6 所示。允许一定分类错误的模型称为软间隔 SVM（Soft Margin SVM）。在本节中，我们用几何方法推导其优化问题。在第 12.2.5 节，我们将用损失函数的思想推导一个等价的优化问题。在第 12.3 节中，我们将利用拉格朗日乘子（第 7.2 节）推导 SVM 的对偶优化问题。

这个对偶优化问题使我们能够从第三种角度理解 SVM：即作为一个超平面，它平分了正样本和负样本对应的凸包之间的线段（第 12.3.2 节）。关键的几何思想是：为每个样本—标签对 \((x_n,y_n)\) 引入一个松弛变量 \(\xi_n\)，允许某个样本位于间隔之内，甚至在超平面的错误一侧（参见图 12.7）。我们从间隔中减去 \(\xi_n\) 的值，并约束 \(\xi_n\) 为非负。为了鼓励样本的正确分类，我们在目标函数中加入 \(\xi_n\)： \[ \min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C\sum_{n=1}^N \xi_n \tag{12.26a} \]

约束条件为

\[ y_n(\langle w,x_n\rangle+b)\ge 1-\xi_n \tag{12.26b} \]

\[ \xi_n \ge 0 \tag{12.26c} \]

其中 \(n=1,\dots,N\)。与硬间隔 SVM 的优化问题 (12.18) 相比，这里称为软间隔 SVM。参数 \(C>0\) 在间隔大小与总松弛量之间进行权衡。这个参数称为正则化参数，因为（如我们在下一节将看到的那样）目标函数中的间隔项 (12.26a) 实际上是一个正则化项。其中的 \(\|w\|^2\) 被称为正则器，在许多数值优化的书籍中，正则化参数会乘在这一项上（第 8.2.3 节）。这与我们在本节的表述不同。在这里，较大的 \(C\) 值意味着较低的正则化，因为我们给松弛变量更大的权重，从而更优先考虑那些没有落在正确间隔一侧的样本。

备注：在软间隔 SVM (12.26a) 的表述中，\(w\) 被正则化，而 \(b\) 没有被正则化。我们可以通过观察正则化项不包含 \(b\) 来看出这一点。未正则化的 \(b\) 会使理论分析更加复杂（Steinwart 和 Christmann, 2008，第 1 章），并降低计算效率（Fan 等人, 2008）。

个人注：

软间隔 SVM 中参数 \(C\) 的几何意义，并和前面章节的正则化写法对比。

1. 软间隔 SVM 的目标函数

在书的 12.2.4 里，软间隔 SVM 写成：

\[ \min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C\sum_{n=1}^N \xi_n \]

其中

• \(\frac{1}{2}\|w\|^2\) 是正则化项（控制间隔的宽度）；
• \(\xi_n\) 是松弛变量（表示第 \(n\) 个样本违反间隔或分错的程度）；
• \(C\) 是惩罚系数。

2. 两种等价的写法

有的书（或有的章节）把目标函数写成：

\[ \min_{w,b,\xi} \lambda\frac{1}{2}\|w\|^2 + \sum_{n=1}^N \xi_n \]

这时 \(\lambda\) 越大，正则化越强。

而在《Mathematics for Machine Learning》这一节，写法是：

\[ \frac{1}{2}\|w\|^2 + C\sum \xi_n \]

它把 \(C\) 放在松弛项前面，而不是正则项前面。于是

• 这里 \(C\) 大 不表示正则化强，反而表示对松弛变量的惩罚更大；
• 也就是模型会“尽量减少”违反间隔的点，宁可让 \(\|w\|\) 增大（间隔变窄）。

因此 正则化的程度与 \(C\) 反比：

• \(C\) 大：更重视分类正确（少违例），放松正则化（间隔窄一些）；

• \(C\) 小：更重视间隔宽（强正则化），允许更多点在间隔内或分错。

  3. 书中那句话的意思

Here a large value of C implies low regularization, as we give the slack variables larger weight, hence giving more priority to examples that do not lie on the correct side of the margin.

翻译＋解释：

• “在这一节的写法里，\(C\) 越大意味着正则化越弱，因为我们给松弛变量更大的权重”；
• “这样模型就更关注那些不在正确间隔一侧的样本（尽量减少违例），而不是保持大间隔”。

这和前面章节把 \(\lambda\) 乘在 \(\|w\|^2\) 上的写法相反，所以要特别注意。

4. 几何直观

• \(C\) 大： 惩罚违例强 → 尽量让所有点都分对 → 容忍小间隔（\(\|w\|\) 大） → 正则化弱。
• \(C\) 小： 惩罚违例弱 → 可以容忍点进入间隔或分错 → 追求大间隔（\(\|w\|\) 小） → 正则化强。

所以几何上看：\(C\) 控制了“宽间隔”与“少违例”之间的折中。

12.2.5 软间隔 SVM：从损失函数的角度

让我们考虑一种推导 SVM 的不同方法，遵循经验风险最小化的原则（第 8.2 节）。对于 SVM，我们选择超平面作为假设类，也就是说：

\[ f(x)=\langle w,x\rangle+b. \tag{12.27} \]

我们将在本节看到，间隔对应于正则化项。剩下的问题是：损失函数是什么？与第 9 章不同，在第 9 章我们考虑的是回归问题（预测器的输出是一个实数），而在本章我们考虑的是二分类问题（预测器的输出是两个标签 \(\{+1,-1\}\) 之一）。因此，每一个样本–标签对的误差/损失函数需要适合二分类。例如，回归所用的平方损失（公式 9.10b）并不适合二分类。

注：二元标签之间的理想损失函数是统计预测与真实标签不一致的次数。这意味着，对于某个预测器 \(f\) 作用在样本 \(x_n\) 上，我们将输出 \(f(x_n)\) 与标签 \(y_n\) 进行比较。如果二者一致，则定义损失为 0；不一致，则定义为 1。记为 \(1(f(x_n)\neq y_n)\)，称为“0-1 损失”。不幸的是，0-1 损失会导致求最优参数 \(w,b\) 时出现组合优化问题。组合优化问题（与第 7 章讨论的连续优化问题不同）一般更难求解。

那么，SVM 对应的损失函数是什么？考虑预测器 \(f(x_n)\) 的输出与标签 \(y_n\) 之间的误差。损失描述了在训练数据上产生的错误。推导 (12.26a) 的等价方法是使用铰链损失（hinge loss）

\[ \ell(t)=\max\{0,1-t\},\quad \text{其中}\ t=yf(x)=y(\langle w,x\rangle+b). \tag{12.28} \]

如果 \(f(x)\) 落在超平面对应标签 \(y\) 的正确一侧，且距离大于 1，也就是说 \(t\ge 1\)，则铰链损失返回 0。如果 \(f(x)\) 在正确一侧但离超平面太近（\(0<t<1\)），样本 \(x\) 处于间隔区内，铰链损失返回一个正值。当样本在超平面的错误一侧（\(t<0\)）时，铰链损失返回更大的值，且值线性增加。换句话说，一旦我们距离超平面小于间隔，即使预测正确也要支付代价，而且代价随距离线性增加。

另一种表达铰链损失的方法是把它看成两个线性分段：

\[ \ell(t)=\begin{cases} 0 & \text{如果 } t\ge 1\\[4pt] 1-t & \text{如果 } t<1 \end{cases}\tag{12.29} \]

如图 12.8 所示。

对应硬间隔 SVM (公式 12.18) 的损失函数定义为：

\[ \ell(t)=\begin{cases} 0 & \text{如果 } t\ge 1\\[4pt] \infty & \text{如果 } t<1 \end{cases}\tag{12.30} \]

这个损失可以理解为：绝不允许任何样本进入间隔之内。

对于一个给定的训练集 \(\{(x_1,y_1),\ldots,(x_N,y_N)\}\)，我们希望在正则化目标函数的同时最小化总损失，其中正则化采用 \(\ell_2\)-正则化（参见第 8.2.3 节）。使用铰链损失 (12.28) 可以得到如下无约束优化问题：

\[ \min_{w,b} \;\;\frac{1}{2}\|w\|^2 \quad \text{（正则化项）} + C\sum_{n=1}^N \max\{0,1-y_n(\langle w,x_n\rangle+b)\} \quad \text{（误差项）}. \tag{12.31} \]

(12.31) 中的第一项称为正则化项（或正则器，见第 8.2.3 节），第二项称为损失项或误差项。回忆第 12.2.4 节，项 \(\frac{1}{2}\|w\|^2\) 直接来自于间隔。换句话说，最大化间隔可以解释为正则化。

原则上，(12.31) 中的无约束优化问题可以直接用（子）梯度下降方法求解（参见第 7.1 节）。要看出 (12.31) 和 (12.26a) 等价，只需注意铰链损失 (12.28) 本质上由两段线性部分组成，如 (12.29) 所示。考虑单个样本–标签对的铰链损失 (12.28)，我们可以把对 \(t\) 的铰链损失最小化，等价地替换成对一个松弛变量 \(\xi\) 的最小化，并加上两个约束。公式形式为：

\[ \min_t \max\{0,1-t\} \tag{12.32} \]

等价于

\[ \min_{\xi,t}\;\xi \quad \text{subject to } \xi\ge 0,\;\xi\ge 1-t. \tag{12.33} \]

把这个表达式代入 (12.31)，并重排其中一个约束，我们就能得到软间隔 SVM (12.26a) 的形式。

注：让我们对比一下本节选择的损失函数和第 9 章线性回归中的损失函数。回忆第 9.2.1 节，对于求最大似然估计，我们通常最小化负对数似然。此外，因为带高斯噪声的线性回归的似然项是高斯分布，所以每个样本的负对数似然就是一个平方误差函数。平方误差函数正是我们在寻找最大似然解时最小化的损失函数。

12.3 对偶支持向量机

前面几节中，我们用变量 \(w\) 和 \(b\) 来描述 SVM，这种形式被称为原始（primal）SVM。回忆我们考虑的输入 \(x\in \mathbb{R}^D\) 有 \(D\) 个特征。由于 \(w\) 与 \(x\) 维度相同，这意味着在优化问题中参数的数量（即 \(w\) 的维度）会随着特征数量线性增长。接下来，我们考虑一个等价的优化问题（所谓的对偶形式），它与特征数无关。相反，参数的数量随着训练集中的样本数增长。我们在第 10 章中已经看到过类似的思想，当时我们将学习问题表达为一种不随特征数扩展的形式。这对于特征数远多于训练样本数的问题尤其有用。对偶 SVM 还有一个额外的优点，就是它很容易引入核函数（kernel），我们将在本章末尾看到这一点。“对偶”这个词在数学文献中经常出现，在本例中它指的是凸对偶性。接下来的各小节本质上是第 7.2 节中讨论过的凸对偶理论的一个应用。

12.3.1 通过拉格朗日乘子看凸对偶

回忆软间隔 SVM 的原始形式 (12.26a)。我们称与原始 SVM 对应的变量 \(w\)、\(b\) 和 \(\xi\) 为原始变量（primal variables）。我们使用 \(\alpha_n \ge 0\) 作为拉格朗日乘子，对应于约束 (12.26b) 中“样本被正确分类”的要求；使用 \(\gamma_n \ge 0\) 作为拉格朗日乘子，对应于松弛变量非负性的约束 (12.26c)。拉格朗日函数为：

\[ \begin{aligned} L(w,b,\xi,\alpha,\gamma) &= \frac{1}{2}\|w\|^2 + C \sum_{n=1}^N \xi_n \\ &\quad - \sum_{n=1}^N \alpha_n \bigl( y_n (\langle w,x_n\rangle + b) - 1 + \xi_n \bigr) \\ &\quad - \sum_{n=1}^N \gamma_n \xi_n \end{aligned} \tag{12.34} \]

其中

• 第一行是原目标，
• 第二行对应约束 (12.26b)，
• 第三行对应约束 (12.26c)。

分别对三个原始变量 \(w\)、\(b\) 和 \(\xi\) 求偏导，我们得到：

\[ \frac{\partial L}{\partial w} = w^\top - \sum_{n=1}^N \alpha_n y_n x_n^\top \tag{12.35} \]

\[ \frac{\partial L}{\partial b} = - \sum_{n=1}^N \alpha_n y_n \tag{12.36} \]

\[ \frac{\partial L}{\partial \xi_n} = C - \alpha_n - \gamma_n \tag{12.37} \]

通过令这些偏导数分别为零来求解拉格朗日函数的极值。将 (12.35) 置零，可得：

\[ w = \sum_{n=1}^N \alpha_n y_n x_n \tag{12.38} \]

这是“表示定理（representer theorem）”的一个具体实例（Kimeldorf 和 Wahba, 1970）。式 (12.38) 表明，在原始形式下最优的权重向量是样本 \(x_n\) 的线性组合。回忆 2.6.1 节的内容，这意味着优化问题的解位于训练数据的线性张成空间内。此外，由 (12.36) 置零得到的约束意味着最优权重向量是样本的一个仿射组合。

表示定理在非常一般的“正则化经验风险最小化”设定下都成立（Hofmann 等, 2008; Argyriou 和 Dinuzzo, 2014）。该定理还有更一般的版本（Schölkopf 等, 2001），其存在的充要条件可见 Yu 等 (2013)。

注释： 表示定理（式 12.38）还解释了“支持向量机”这一名称的来源。对于那些对应参数 \(\alpha_n = 0\) 的样本 \(x_n\)，它们对解 \(w\) 完全没有贡献。而其他满足 \(\alpha_n > 0\) 的样本则被称为“支持向量”，因为它们“支撑”了超平面。

将 \(w\) 的表达式代入拉格朗日函数（12.34）后，我们得到对偶式

\[ \begin{align} D(\xi,\alpha,\gamma) & = \frac{1}{2}\, y_i y_j \alpha_i \alpha_j \langle x_i, x_j\rangle - \sum_{i=1}^N y_i\alpha_i + C\sum_{i=1}^N \xi_i + \sum_{i=1}^N \alpha_i \\ & -\sum_{i=1}^N y_i \alpha_i -\sum_{i=1}^N\sum_{j=1}^N \alpha_i \xi_i -\sum_{i=1}^N y_j\alpha_j \langle x_j,x_i\rangle - \sum_{i=1}^N \gamma_i \xi_i. \tag{12.39} \end{align} \]

注意，现在不再有任何涉及原始变量 \(w\) 的项。通过将式（12.36）设为零，我们得到 \(\sum_{n=1}^N y_n \alpha_n = 0\)。因此，涉及 \(b\) 的项也消失了。回忆内积是对称且双线性的（见 3.2 节），所以（12.39）中前两项（蓝色部分）是针对同样对象的，可以进行简化，于是我们得到拉格朗日函数

\[ D(\xi,\alpha,\gamma) = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N y_i y_j \alpha_i \alpha_j \langle x_i, x_j\rangle +\sum_{i=1}^N \alpha_i +\sum_{i=1}^N (C-\alpha_i-\gamma_i)\xi_i. \tag{12.40} \]

这个式子的最后一项包含了所有带有松弛变量 \(\xi_i\) 的项。通过将（12.37）设为零，我们看到（12.40）中最后一项也为零。此外，利用同一个方程并回忆拉格朗日乘子 \(\gamma_i\) 非负，我们可以推出 \(\alpha_i \leq C\)。于是我们得到支持向量机的对偶优化问题，它仅用拉格朗日乘子 \(\alpha_i\) 表示。根据拉格朗日对偶性（定义 7.1），我们要最大化对偶问题。这等价于最小化负的对偶问题，从而得到对偶 SVM：

\[ \begin{align} & \min_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N y_i y_j \alpha_i \alpha_j \langle x_i, x_j\rangle -\sum_{i=1}^N \alpha_i \\[6pt] & \text{subject to}\quad \sum_{i=1}^N y_i \alpha_i = 0,\\[4pt] & 0\leq \alpha_i \leq C,\quad i=1,\dots,N. \end{align} \tag{12.41} \]

其中，等式约束 \(\sum_{i=1}^N y_i \alpha_i = 0\) 来自将（12.36）设为零；不等式约束 \(\alpha_i \ge 0\) 是对不等式约束的拉格朗日乘子的条件（见 7.2 节）；不等式约束 \(\alpha_i \le C\) 则是上一段中讨论的结果。

在 SVM 中的不等式约束集合被称为“盒约束（box constraints）”，因为它们限制拉格朗日乘子向量

\[ \boldsymbol{\alpha} = [\alpha_1,\dots,\alpha_N]^\top \in \mathbb{R}^N \]

在每个坐标轴上都位于由 0 和 \(C\) 定义的盒子内。这样的轴对齐盒子在数值求解器中实现起来特别高效（Dostál，2009，第 5 章）。一旦我们得到了对偶参数 \(\alpha\)，就可以通过表示定理（12.38）恢复原始参数 \(w\)。我们把最优的原始参数称为 \(w^*\)。不过，仍然存在如何得到参数 \(b^*\) 的问题。考虑一个恰好位于间隔边界上的样本 \(x_n\)，即

\[ \langle w^*,x_n\rangle + b = y_n. \]

回忆 \(y_n\) 只能取 +1 或 −1。因此唯一未知的是 \(b\)，它可以通过下式计算：

\[ b^* = y_n - \langle w^*,x_n\rangle. \tag{12.42} \]

注释。 原则上，可能没有样本恰好落在间隔上。在这种情况下，我们应该对所有支持向量计算\(|y_n - \langle w^*,x_n\rangle|\)，然后取这个绝对值差的中位数作为 \(b^*\) 的值。推导可以在http://fouryears.eu/2012/06/07/the-svm-bias-term-conspiracy/ 找到。

12.3.2 对偶 SVM：凸包视角

获得对偶 SVM 的另一种方法是考虑一个替代性的几何论证。考虑所有标签相同的样本 \(x_n\) 的集合。我们希望构建一个包含所有样本的凸集，并且这个集合尽可能小。这就是所谓的“凸包（convex hull）”，如图 12.9 所示。

我们先直观理解一下点的凸组合。考虑两个点 \(x_1\) 和 \(x_2\)，以及对应的非负权重 \(\alpha_1,\alpha_2 \ge 0\)，并且 \(\alpha_1+\alpha_2=1\)。方程 \(\alpha_1x_1+\alpha_2x_2\) 描述了 \(x_1\) 和 \(x_2\) 之间的每一个点。接下来考虑加入第三个点 \(x_3\) 以及权重 \(\alpha_3\ge 0\)，满足\(\sum_{n=1}^{3}\alpha_n=1\)。这三个点 \(x_1,x_2,x_3\) 的凸组合张成了一个二维区域。这个区域的凸包就是由每一对点连成的三角形边界。随着我们加入更多的点，并且点的数量大于维度时，其中一些点将会位于凸包内部，如图 12.9(a) 所示。一般来说，构造一个凸包可以通过为每个样本 \(x_n\) 引入非负权重 \(\alpha_n \ge 0\) 来完成。这样，凸包可以表示为集合

\[ \text{conv}(X)= \sum_{n=1}^N \alpha_n x_n \quad \text{其中} \quad \sum_{n=1}^N \alpha_n=1,\;\alpha_n\ge 0, \tag{12.43} \]

对于所有 \(n=1,\dots,N\) 都成立。如果正类和负类对应的两组点云是分开的，那么它们的凸包就不会重叠。给定训练数据 \((x_1,y_1),\dots,(x_N,y_N)\)，我们分别构造正类和负类的两个凸包。

个人注：直观理解

• 两个点 \(x_1,x_2\)： 取 \(\alpha_1=t,\alpha_2=1-t,t\in[0,1]\)，得到 \(\alpha_1x_1+\alpha_2x_2\) 是这两个点连线上的所有点；这就是它们的凸包。
• 三个点 \(x_1,x_2,x_3\)： 同理，权重非负且和 1，就得到三角形内部所有点；这就是三个点的凸包。
• 更多点： 就是把所有点“包”起来的多面体。

我们在正类样本凸包中选取一个点 \(c\)，它距离负类分布最近；同样，我们在负类样本凸包中选取一个点 \(d\)，它距离正类分布最近；见图 12.9(b)。我们将 \(d\) 与 \(c\) 的差定义为 \[ w := c - d. \tag{12.44} \]

像上面那样选取 \(c\) 和 \(d\)，并要求它们彼此尽可能接近，这等价于最小化 \(w\) 的长度/范数，从而得到相应的优化问题

\[ \arg\min_w \|w\| = \arg\min_w \frac{1}{2}\|w\|^2. \tag{12.45} \]

由于 \(c\) 必须在正类凸包中，它可以表示为正类样本的凸组合，即对于非负系数 \(\alpha_n^+\)：

\[ c = \sum_{n:\,y_n=+1}\alpha_n^+ x_n. \tag{12.46} \]

在 (12.46) 中，我们使用记号 \(n: y_n=+1\) 来表示标签 \(y_n=+1\) 的索引集合。类似地，对于负类样本我们有

\[ d = \sum_{n:\,y_n=-1}\alpha_n^- x_n. \tag{12.47} \]

将 (12.44)、(12.46) 和 (12.47) 代入 (12.45)，我们得到目标函数

\[ \min_{\alpha} \frac{1}{2}\left\| \sum_{n:\,y_n=+1}\alpha_n^+x_n - \sum_{n:\,y_n=-1}\alpha_n^-x_n \right\|^2. \tag{12.48} \]

设 \(\alpha\) 是所有系数的集合，即 \(\alpha^+\) 和 \(\alpha^-\) 的拼接。回忆我们要求每个凸包内的系数之和为 1：

\[ \sum_{n:\,y_n=+1}\alpha_n^+=1,\quad \sum_{n:\,y_n=-1}\alpha_n^-=1. \tag{12.49} \]

这意味着约束条件

\[ \sum_{n=1}^N y_n\alpha_n=0. \tag{12.50} \]

通过将每一类分别展开可以看到这一点：

\[ \sum_{n=1}^N y_n\alpha_n = \sum_{n:\,y_n=+1}(+1)\alpha_n^+ +\sum_{n:\,y_n=-1}(-1)\alpha_n^- \tag{12.51a} \]

\[ =\sum_{n:\,y_n=+1}\alpha_n^+-\sum_{n:\,y_n=-1}\alpha_n^- =1-1=0. \tag{12.51b} \]

目标函数 (12.48) 与约束 (12.50)，再加上 \(\alpha \ge 0\) 的假设，给我们一个受约束的（凸）优化问题。可以证明这个优化问题与对偶硬间隔 SVM 的优化问题是相同的（Bennett 和 Bredensteiner，2000a）。

注释。 要得到软间隔对偶问题，我们考虑缩减凸包（reduced hull）。缩减凸包与凸包类似，但对系数 \(\alpha\) 的大小有一个上界。 \(\alpha\) 的元素最大可能值限制了凸包所能取的大小。换句话说，对 \(\alpha\) 的上界将凸包缩小到一个更小的体积（Bennett 和 Bredensteiner，2000b）。

12.4 核函数

Kernels

考虑对偶 SVM（式 12.41）的形式。注意到，目标函数中的内积只出现在样本 \(x_i\) 和 \(x_j\) 之间；并没有样本与参数之间的内积。因此，如果我们用一组特征 \(\phi(x_i)\) 来表示 \(x_i\)，在对偶 SVM 中唯一的变化就是把内积替换掉。这种模块化的形式，使得分类方法（SVM 的选择）与特征表示 \(\phi(x)\) 的选择可以分开考虑，从而为我们独立探索这两个问题提供了灵活性。本节我们讨论 \(\phi(x)\) 的表示，并简要介绍核函数的概念，但不深入技术细节。

由于 \(\phi(x)\) 可以是一个非线性函数，我们就可以使用假设线性分类器的 SVM 来构造在样本 \(x_n\) 上非线性的分类器。这为处理非线性可分的数据集提供了第二条途径（第一条是软间隔）。事实证明，有许多算法和统计方法也具有我们在对偶 SVM 中看到的这种性质：内积只出现在样本之间。我们无需显式定义非线性特征映射 \(\phi(\cdot)\) 并计算样本 \(x_i\) 与 \(x_j\) 之间的内积，而是定义样本 \(x_i\) 与 \(x_j\) 之间的相似度函数 \(k(x_i,x_j)\)。对于某一类相似度函数（称为核函数），相似度函数隐式地定义了一个非线性特征映射 \(\phi(\cdot)\)。

个人注：

• 软间隔 SVM + 无核函数 → 仍然是线性分割（超平面）。
• 软间隔 SVM + 核函数 → 在原空间里是非线性分割（在特征空间里仍然是线性超平面）。

核函数按定义是函数 \(k: \mathcal{X}\times\mathcal{X}\to\mathbb{R}\)，满足存在一个希尔伯特空间 \(\mathcal{H}\) 以及一个特征映射 \(\phi: \mathcal{X}\to\mathcal{H}\)，使得

\[ k(x_i,x_j)=\langle\phi(x_i),\phi(x_j)\rangle_{\mathcal{H}}. \tag{12.52} \]

每个核函数 \(k\) 都有一个唯一的再生核希尔伯特空间（RKHS）与之对应（Aronszajn, 1950；Berlinet 和 Thomas-Agnan, 2004）。在这种唯一对应下，\(\phi(x)=k(\cdot,x)\) 被称为规范特征映射（canonical feature map）。从内积推广到核函数（式 12.52）被称为核技巧（kernel trick），它把显式的非线性特征映射隐藏了起来，（Schölkopf 和 Smola, 2002；Shawe-Taylor 和 Cristianini, 2004）。

个人注：注意核函数（kernel function）和核密度函数（kernel density function）的区别。详见《核函数和核密度函数的区别.md》,特别是高斯核（RBF核）\(k(x,x')=\exp(-\|x-x'\|^2/2\sigma^2)\) 和 高斯核密度函数 \(K(u)=\frac{1}{\sqrt{2\pi}}e^{-u^2/2}\)

例子：

• 线性核 \(k(x,x')=x^\top x'\)
• 多项式核 \(k(x,x')=(x^\top x'+c)^d\)
• 高斯核（RBF核）\(k(x,x')=\exp(-\|x-x'\|^2/2\sigma^2)\)

注意：这里的“核”只是指“内积核（Mercer核）”，与概率密度没有关系。

矩阵 \(K \in \mathbb{R}^{N \times N}\)，由内积或将 \(k(\cdot,\cdot)\) 应用于一个数据集而得到，被称为Gram 矩阵，通常也直接称为核矩阵。核函数必须是对称且半正定的函数，这样每一个核矩阵 \(K\) 都是对称且半正定的（见 3.2.3 节）：

\[ \forall z\in\mathbb{R}^N: \quad z^\top K z \ge 0. \tag{12.53} \]

对于多元实值数据 \(x_i\in\mathbb{R}^D\)，一些常见的核函数包括多项式核、Gaussian 径向基函数核（RBF 核），以及有理二次核（Schölkopf 和 Smola, 2002；Rasmussen 和 Williams, 2006）。图 12.10 展示了不同核函数对分离超平面的影响。请注意，我们仍然在求解超平面，也就是说，假设空间里的函数依然是线性的；那些非线性分割面是由核函数造成的。（个人注：正如本节开头说的模块化！）

注： 对于刚接触机器学习的人来说，不幸的是，“核”这个词有多种含义。在本章中，“核”一词来自再生核希尔伯特空间（RKHS）的概念（Aronszajn, 1950；Saitoh, 1988）。我们已经在 2.7.3 节线性代数中讨论过“kernel”的另一种含义，即核空间或零空间（null space）。在机器学习中，“kernel”还有第三种常见的用法，即核密度估计（11.5 节）中的平滑核（smoothing kernel）。

由于显式表示 \(\phi(x)\) 在数学上与核表示 \(k(x_i,x_j)\) 等价，实践中往往会设计核函数使其比显式特征映射之间的内积计算更高效。例如，多项式核（Schölkopf 和 Smola, 2002），当输入维度很大时，即便是低阶多项式，其显式展开的项数也会迅速增长；而核函数每个输入维度只需要一次乘法，从而显著节省计算量。另一个例子是 Gaussian 径向基核函数（Schölkopf 和 Smola, 2002；Rasmussen 和 Williams, 2006），其对应的特征空间是无限维的。在这种情况下，我们无法显式表示特征空间，但仍然可以通过核函数计算任意一对样本之间的相似度。

核技巧的另一个有用之处在于：原始数据不必已经表示为多元实值数据。注意，内积是定义在函数 \(\phi(\cdot)\) 的输出上的，但并不限制输入必须是实数。因此，函数 \(\phi(\cdot)\) 和核函数 \(k(\cdot,\cdot)\) 可以定义在任意对象上，例如集合、序列、字符串、图、分布等（Ben-Hur 等, 2008；Gärtner, 2008；Shi 等, 2009；Sriperumbudur 等, 2010；Vishwanathan 等, 2010）。

12.5 数值求解

我们通过考察如何将本章推导出的 SVM 问题用第 7 章介绍的概念来表达，来结束对 SVM 的讨论。我们考虑两种不同的方法来求解 SVM 的最优解。首先，我们考虑 SVM 的损失函数视角（8.2.2 节），并把它表达为一个无约束优化问题。然后，我们把 SVM 的原始形式和对偶形式的约束版本都表示为标准形式（7.3.2 节）的二次规划问题。

考虑 SVM 的损失函数视角（公式 12.31）。这是一个凸的无约束优化问题，但铰链损失（公式 12.28）不可微。因此，我们采用次梯度方法来求解它。不过，铰链损失几乎在所有地方都是可微的，除了铰链处 \(t=1\) 的单一点。在该点处，梯度是一组可能值，介于 0 和 -1 之间。因此，铰链损失的次梯度 \(g\) 表示为：

\[ g(t)= \begin{cases} -1, & t<1\\[4pt] [-1,0], & t=1\\[4pt] 0, & t>1 \end{cases} \tag{12.54} \]

利用这个次梯度，我们可以应用第 7.1 节介绍的优化方法。

SVM 的原始形式和对偶形式都可以归结为一个凸二次规划问题（带约束的优化问题）。注意，公式 (12.26a) 中的原始 SVM 的优化变量大小为输入样本的维度 \(D\)；而公式 (12.41) 中的对偶 SVM 的优化变量大小为样本数 \(N\)。

为了将原始 SVM（primal SVM）写成标准二次规划（7.45）的形式，我们假设内积使用的是点积 (3.5)。我们重新排列原始 SVM (12.26a) 的公式，使得所有的优化变量都位于右边，并且约束的不等式形式与标准形式匹配。这样得到如下的优化问题：

\[ \begin{aligned} \min_{w,b,\xi} \quad & \frac{1}{2}\|w\|^2 + C\sum_{n=1}^{N}\xi_n \\ \text{s.t.}\quad & -y_n x_n^\top w - y_n b - \xi_n \le -1, \\ & -\xi_n \le 0, \quad n=1,\dots,N. \end{aligned} \tag{12.55} \]

通过把变量 \(w,b,\xi\) 合并成一个单一的向量，并小心地收集各个项，我们得到软间隔 SVM 的如下矩阵形式：

\[ \begin{align} \min_{w,b,\xi} \quad & \begin{bmatrix} b\\[3pt] w\\[3pt] \xi \end{bmatrix}^{\!\top} \begin{bmatrix} I_D & 0_{D,N+1}\\[3pt] 0_{N+1,D} & 0_{N+1,N+1} \end{bmatrix} \begin{bmatrix} b\\[3pt] w\\[3pt] \xi \end{bmatrix} \\[5pt] \text{s.t.}\quad & \begin{bmatrix} -Y X - y - I_N & 0_{N,D+1} - I_N \end{bmatrix} \begin{bmatrix} b\\[3pt] w\\[3pt] \xi \end{bmatrix} + \begin{bmatrix} 0_{D+1,1}\\[3pt] C\,1_{N,1} \end{bmatrix} \le \begin{bmatrix} -1_{N,1}\\[3pt] 0_{N,1} \end{bmatrix}. \tag{12.56} \end{align} \]

在上述优化问题中，最小化是针对参数

\[ [w^\top,b,\xi^\top]^\top \in \mathbb{R}^{D+1+N}, \]

并且我们用以下记号：

• \(I_m\) 表示大小为 \(m\times m\) 的单位矩阵，
• \(0_{m,n}\) 表示大小为 \(m\times n\) 的全零矩阵，
• \(1_{m,n}\) 表示大小为 \(m\times n\) 的全 1 矩阵。

此外，\(y\) 是标签向量 \([y_1,\dots,y_N]^\top\)，\(Y=\mathrm{diag}(y)\) 是一个 \(N\times N\) 的对角矩阵，其对角元素来自 \(y\)，而 \(X\in \mathbb{R}^{N\times D}\) 是将所有样本拼接得到的矩阵。

我们同样可以对 SVM (12.41) 的对偶形式进行项的收集。为了将对偶 SVM 写成标准形式，我们首先必须表示核矩阵 \(K\)，其中每个元素为 \(K_{ij}=k(x_i,x_j)\)。如果我们有显式的特征表示 \(x_i\)，那么我们定义\(K_{ij}=\langle x_i,x_j\rangle\)。为了方便记号，我们引入一个矩阵 \(Y=\mathrm{diag}(y)\)，它在对角线上存储标签，其余位置全为 0。对偶 SVM 可以写为： \[ \begin{align} \min_{\alpha}\quad & \frac{1}{2}\,\alpha^\top YKY\alpha - \mathbf{1}_{N,1}^\top \alpha \\ \text{s.t.}\quad & \begin{bmatrix} y^\top\\[3pt] - y^\top\\[3pt] - I_N\\[3pt] I_N \end{bmatrix} \alpha \;\le\; \begin{bmatrix} 0_{N+2,1}\\[3pt] C\mathbf{1}_{N,1} \end{bmatrix}. \tag{12.57} \end{align} \]

备注： 在 7.3.1 和 7.3.2 节，我们介绍了标准形式的约束均写成不等式约束。我们将对偶 SVM 的等式约束表示为两个不等式约束，即 \[ Ax=b\quad \text{被替换为}\quad Ax\le b \quad \text{和}\quad Ax\ge b。 \tag{12.58} \]

某些凸优化算法的软件实现可能直接支持等式约束。

由于对 SVM 存在多种不同的视角，因此求解相应优化问题的方法也有很多。这里介绍的这种将 SVM 问题写成标准凸优化形式的方法在实践中并不常用。SVM 求解器的两个主要实现分别是 Chang 和 Lin (2011)（开源）以及 Joachims (1999)。由于 SVM 具有清晰且定义良好的优化问题，因此可以应用许多基于数值优化技术（Nocedal 和 Wright, 2006）的方法（Shawe-Taylor 和 Sun, 2011）。

12.6 延伸阅读

支持向量机（SVM）只是研究二分类问题的众多方法之一。其他方法包括感知机、逻辑回归、Fisher 判别、最近邻、朴素贝叶斯以及随机森林（Bishop，2006；Murphy，2012）。Ben-Hur 等（2008）给出了一个关于离散序列上 SVM 与核方法的简短教程。

SVM 的发展与第 8.2 节讨论的经验风险最小化密切相关，因此 SVM 拥有坚实的理论性质（Vapnik，2000；Steinwart 和 Christmann，2008）。关于核方法的书（Schölkopf 和 Smola，2002）包含了大量有关支持向量机及其优化的细节。Shawe-Taylor 和 Cristianini（2004）撰写的一本更广泛的核方法书籍，也包含了许多针对不同机器学习问题的线性代数方法。

SVM 的对偶形式可以用 Legendre–Fenchel 变换（第 7.3.3 节）的思想推导出来。该推导将 SVM 的无约束形式 (12.31) 中的每一项分别考虑，并计算其凸共轭（Rifkin 和 Lippert，2007）。对 SVM 感兴趣的读者（尤其是函数分析视角或正则化方法视角）可参考 Wahba（1990）的工作。核方法的理论阐述（Aronszajn，1950；Schwartz，1964；Saitoh，1988；Manton 和 Amblard，2015）需要线性算子（Akhiezer 和 Glazman，1993）的基本知识作为基础。核方法的思想已推广到巴拿赫空间（Zhang 等，2009）和克雷因空间（Ong 等，2004；Loosli 等，2016）。

需要注意的是，hinge 损失（铰链损失）有三种等价表示，如 (12.28) 和 (12.29)，以及 (12.33) 中的约束优化问题。公式 (12.28) 常用于比较 SVM 损失函数与其他损失函数（Steinwart，2007）。两段式表示 (12.29) 便于计算次梯度，因为每一段都是线性的。第三种表示 (12.33)，如 12.5 节所示，使得可以使用凸二次规划（第 7.3.2 节）工具。

由于二分类在机器学习中是一个研究得非常充分的任务，人们有时也会使用其他词语来描述它，例如“判别”“分离”和“决策”。此外，二分类器的输出可以有三种不同的形式：

• 第一种是线性函数本身的输出（通常称为“分数”score），它可以取任意实数值。这个输出可以用来对样本进行排序，而二分类可以被看作是在排好序的样本上选择一个阈值（Shawe-Taylor 和 Cristianini，2004）。

• 第二种常被视为二分类器输出的，是将线性输出经过一个非线性函数后得到的结果，用来将取值限制在一个有界范围内，例如区间 \([0,1]\)。常见的非线性函数是 sigmoid 函数（Bishop，2006）。当这种非线性转换得到的是经过良好校准的概率（Gneiting 和 Raftery，2007；Reid 和 Williamson，2011）时，这称为类别概率估计（class probability estimation）。

• 第三种输出是最终的二元决策 \(\{+1, -1\}\)，这也是最常被假设为分类器输出的形式。

支持向量机（SVM）是一种二分类器，它本身并不自然地对应于概率解释。有多种方法可以将线性函数（分数）的原始输出转化为一个经过良好校准的类别概率估计 \(P(Y=1|X=x)\)，这需要一个额外的校准步骤（Platt，2000；Zadrozny 和 Elkan，2001；Lin 等，2007）。

从训练的角度看，有许多与概率相关的方法。我们在 12.2.5 节的末尾提到过损失函数与似然之间的关系（也可比较 8.2 节和 8.3 节）。在训练过程中对应于良好校准的转换的最大似然方法称为逻辑回归，它来自一类称为广义线性模型（generalized linear models）的方法。从这一视角看逻辑回归的细节可参见 Agresti（2002，第 5 章）以及 McCullagh 和 Nelder（1989，第 4 章）。

当然，人们也可以用更贝叶斯的视角来看待分类器输出，即通过贝叶斯逻辑回归来估计后验分布。贝叶斯视角还包括先验的设定，这其中包含了与似然的共轭性（第 6.6.1 节）等设计选择。此外，人们还可以将潜在函数视为先验，这样就得到高斯过程分类（Rasmussen 和 Williams，2006，第 3 章）。