12.3 支持向量机与核函数

上文介绍的支持向量分类器在输入变量特征空间上寻找线性的判别边界。与其他线性的模型类似，通过多项式和样条函数等的基扩展（第五章）扩大特征空间，从而使原线性模型更灵活。一般来说，在扩大特征空间上的线性边界有更好的训练样本类别区分，并且在原特征空间上得到的是非线性边界。选择好基函数 $h_{m} (x), m = 1, \dots, M$ 之后，计算方法与上节一样。输入特征变量为 $h (x_{i}) = (h_{1} (x_{i}), h_{2} (x_{i}), \dots, h_{M} (x_{i}))$ ， $i = 1, \dots, N$ ，构建的（非线性）函数为 $\hat{f} (x) = h (x)^{T} \hat{β} + {\hat{β}}_{0}$ ，模型的分类器与上节一样 $\hat{G} (x) = sign (\hat{f} (x))$ 。

支持向量机（support vector machine，SVM） 分类模型是这个思路的一个扩展，它的扩大特征空间的维度可达到非常大，有可能是无穷大。那么它的计算量可能大到无法实际操作；另外当基函数足够多时，虽然样本类别可区分但可能产生过拟合的问题。本节将先介绍 SVM 方法如何解决这些问题，然后将说明 SVM 分类器实际上是一个利用了特定的准则（函数）和正则项形式的函数拟合问题。而且 SVM 和第 5.4 节的平滑样条（smoothing splines），都同样可归属于同一类的模型中。读者可回看第 5.8 节，其中有一些背景知识和与下两节互相呼应的内容。

12.3.1 分类问题 SVM 的计算

我们可以将最优化问题 12.8 和它的解改写为输入特征向量只以内积出现的形式。这里的输入特征向量为变换后的特征向量 $h (x_{i})$ 。下面将会看到一些特定的 $h$ 可非常快速地计算出所需要的内积。

拉格朗日对偶函数（12.13）可写为：

\begin{matrix} (12.19) & L_{D} = \sum_{i = 1}^{N} α_{i} - \frac{1}{2} \sum_{i = 1}^{N} \sum_{i^{'} = 1}^{N} α_{i} α_{i^{'}} y_{i} y_{i^{'}} ⟨ h (x_{i}), h (x_{i^{'}}) ⟩ \end{matrix}

从式 12.10 可得，判别函数 $f (x)$ 可写为：

\begin{aligned} f (x) & = h (x)^{T} β + β_{0} \\ (12.20) & = \sum_{i = 1}^{N} α_{i} y_{i} ⟨ h (x), h (x_{i}) ⟩ + β_{0} \end{aligned}

与之前类似¹，给定 $α_{i}$ 后，带入任意（或所有）的满足 $0 < α_{i} < C$ 的 $x_{i}$ 到 12.20 中，即可求出 $β_{0}$ 。

由此可见，式 12.19 和 12.20 中 $h (x)$ 只以内积的形式出现。事实上，我们其实并不需要明确 $h (x)$ 的具体形式，而只需要明确用于计算变换空间上的内积的核函数（kernel function）即可。

\begin{matrix} (12.21) & K (x, x^{'}) = ⟨ h (x_{i}), h (x_{i^{'}}) ⟩ \end{matrix}

$K$ 为一个对称的半正定（semi-positive definite）函数，参考第 5.8.1 节。

SVM 领域中的三个常用 $K$ 为：

\begin{aligned} dth-Degree polynomial & : K (x, x^{'}) = (1 + ⟨ x, x^{'} ⟩)^{d} \\ Radial basis & : K (x, x^{'}) = \exp (- γ ‖ x - x^{'} ‖^{2}) \\ Neural network & : K (x, x^{'}) = \tanh (κ_{1} ⟨ x, x^{'} ⟩ + κ_{2}) \end{aligned}

\begin{matrix} (12.22) \end{matrix}

例如，在两个输入变量 $X_{1}$ 和 $X_{2}$ 的特征空间上，使用次数为 2 的多项式核函数，则有：

\begin{aligned} K (X, X^{'}) = & (1 + ⟨ X, X^{'} ⟩)^{2} \\ = & (1 + X_{1} X_{1}^{'} + X_{2} X_{2}^{'})^{2} \\ = & 1 + 2 X_{1} X_{1}^{'} + 2 X_{2} X_{2}^{'} + \\ (12.23) & (X_{1} X_{1}^{'})^{2} + (X_{2} X_{2}^{'})^{2} + 2 X_{1} X_{1}^{'} X_{2} X_{2}^{'} \end{aligned}

则 $M = 6$ ，而且当选定以下基函数形式后， $K (X, X^{'}) = ⟨ h (X), h (X^{'}) ⟩$ 。

$h_{1} (X) = 1$
$h_{2} (X) = \sqrt{2} X_{1}$
$h_{3} (X) = \sqrt{2} X_{2}$
$h_{4} (X) = X_{1}^{2}$
$h_{5} (X) = X_{2}^{2}$
$h_{6} (X) = \sqrt{2} X_{1} X_{2}$

根据式 12.20，判别函数的解可写为：

\begin{matrix} (12.24) & \hat{f} (x) = \sum_{i = 1}^{N} {\hat{α}}_{i} y_{i} K (x, x_{i}) + {\hat{β}}_{0} \end{matrix}

在扩大的特征空间上通常可实现（类别）完全可分，因此参数 $C$ 的作用在这里会更突出。一个大的 $C$ 值会使 $ξ_{i}$ 难以取到非零的正数值，得到一个在原特征空间上过拟合的弯曲的边界；一个小的 $C$ 值会使 $‖ β ‖$ 尽可能小，从而得到一个更平滑的边界。图 12.3 展示了应用在第二章的混合分布例子上的两个分线性支持向量机。两个模型都分别选择了可得到较好测试误差（test error）的正则项参数。在这个例子中，径向基函数核可得到与贝叶斯最优决策边界非常相近的边界。对比第 2.4 节中的图 2.5。

**图 12.3**：混合分布数据上的两个非线性支持向量机。上图使用了次数为 4 的多项式核，下图使用了径向基核（$\gamma=1$）。两个模型都将 $C$ 调整为接近取得最佳测试误差表现的值，在两个模型中 $C=1$ 都表现很好。径向基核的表现最好（接近于贝叶斯最优），考虑到数据生成的方式是高斯分布的混合这个结果也并不意外。图中紫色虚线即为贝叶斯决策边界。 — **图 12.3**：混合分布数据上的两个非线性支持向量机。上图使用了次数为 4 的多项式核，下图使用了径向基核（ $γ = 1$ ）。两个模型都将 $C$ 调整为接近取得最佳测试误差表现的值，在两个模型中 $C = 1$ 都表现很好。径向基核的表现最好（接近于贝叶斯最优），考虑到数据生成的方式是高斯分布的混合这个结果也并不意外。图中紫色虚线即为贝叶斯决策边界。

支持向量机的早期文献中认为，核函数的特性是支持向量机特有的而且可以据此解决维数灾难（curse of dimensionality）。这两个判断都是错误的，接下来的三个小节中将对此加以讨论。

12.3.2 从惩罚项方法理解 SVM

令 $f (x) = h (x)^{T} β + β_{0}$ ，考虑这个最优化问题

\begin{matrix} (12.25) & min_{β_{0}, β} \sum_{i = 1}^{N} [1 - y_{i} f (x_{i})]_{+} + \frac{λ}{2} ‖ β ‖^{2} \end{matrix}

其中的“+”下标代表正部（positive part）函数。上式也可看成是“损失函数+惩罚项”的形式，这和函数估计有相似的模式。不难推导出当 $λ = 1 / C$ 时 12.25 的解与 12.8 的解相同（练习 12.1）。

**图 12.4**：支持向量损失函数（合页损失）、对数几率回归中的负对数似然损失函数（二项偏差）、平方误差损失函数、和休伯（Huber）化的平方合页损失。由于（二分类的损失函数中）$y=+1$ 和$y=-1$ 的对称性，图中展示的是各个函数对 $yf$ 的曲线。二项偏差和休伯损失都与支持向量损失在两侧有一样的渐进趋势，但在中间的区域是平滑的。所有的函数经过调整使得其左侧的极限斜率为 -1。 — **图 12.4**：支持向量损失函数（合页损失）、对数几率回归中的负对数似然损失函数（二项偏差）、平方误差损失函数、和休伯（Huber）化的平方合页损失。由于（二分类的损失函数中） $y = + 1$ 和 $y = - 1$ 的对称性，图中展示的是各个函数对 $y f$ 的曲线。二项偏差和休伯损失都与支持向量损失在两侧有一样的渐进趋势，但在中间的区域是平滑的。所有的函数经过调整使得其左侧的极限斜率为 -1。

“合页”（hinge）损失函数 $L (y, f) = [1 - y f]_{+}$ 相较于其他更传统的损失函数它更适用于两个类别的分类问题。图 12.4 将其与对数几率回归的对数似然损失函数、平方误差损失函数及其一个变体进行了对比。（负）对数似然函数（negative log-likelihood）或二项偏差（binomial deviance）的尾部与支持向量损失类似，对处在深入间隔内部的点给予零损失，对处在间隔误分类且距离较远的点给予线性的损失。而平方误差则会（无差别地）赋予二次的损失，那些处在深入间隔内部的点也会对模型有很大的影响。平方合页损失函数 $L (y, f) = [1 - y f]_{+}^{2}$ 也是二次的损失，不过它对间隔内部的点为零。它在左侧仍然以二次的形式上升，因此在存在误分类样本的情况下没有合页损失和二项偏差稳健。Rosset and Zhu (2007) 近期提出了一个“休伯”（Huber）化的平方合页损失，这样可以使 $y f = - 1$ 的区域上有线性的损失函数。

Loss Function	$L [y, f (x)]$	Minimizing Function
Binomial Deviance	$\log [1 + e^{- y f (x)}]$	$f (x) = \log \frac{\Pr (Y = + 1 \| x)}{\Pr (Y = - 1 \| x)}$
SVM Hinge Loss	$[1 - y f (x)]_{+}$	$f (x) = sign [\Pr (Y = + 1 \| x) - \frac{1}{2}]$
Squared Error	$[y - f (x)]^{2} = [1 - y f (x)]^{2}$	$f (x) = 2 \Pr (Y = + 1 \| x) - 1$
“Huberised” Squared Hinge Loss	${\begin{cases} - 4 y f (x) & y f (x) < - 1 \\ [1 - y f (x)]_{+}^{2} & otherwise \end{cases}$	$f (x) = 2 \Pr (Y = + 1 \| x) - 1$

表 12.1：图 12.4 中的各个损失函数的总体（population）最小化函数解。对数几率回归使用的是二项对数似然函数或偏差函数。线性判别分析使用的是平方误差损失（练习 4.2）。支持向量机的合页损失函数得到的估计是后验类别概率的众数，而其他损失函数则是这些概率的某个线性转换。

我们可以从其在总体（population）上所得到的估计结果的角度来理解这些损失函数。现在对 $E L (Y, f (X))$ 求最小化，表 12.1 列出了结果。合页损失函数估计的结果是分类函数 $G (x)$ 本身，除此之外的其他所有函数的估计结果都是后验类别概率的一个变换。休伯（Huber）平方合页损失具备一些与对数几率回归和 SVM 的合页损失一样的优势：平滑的损失函数以及对概率的估计。

式 12.25 将支持向量机表述为一个带正则项的函数估计问题，其线性扩展函数 $f (x) = β_{0} + h (x)^{T} β$ 的系数（除常数项外）会向零的方向收缩。如果 $h (x)$ 为含有某种排序结构的层级基函数（hierarchical basis）,例如按函数平滑程度的排序，那么均匀收缩（uniform shrinkage）意味着向量 $h$ 中越不平滑的 $h_{j}$ 对应越小的范数（norm）。

表 12.1 中除平方误差外的所有损失函数都可称为“间隔最大化损失函数”（margin maximizing loss-functions，Rosset et al., 2004b）。也就是说如果数据是可分的，则当 $λ \to 0$ 时 12.25 中的极限解 ${\hat{β}}_{λ}$ 即为最优分离超平面中的 $β$ 。²

12.3.3 函数估计和再生核 😱

本节以再生核希尔伯特空间中的函数估计，以及核的性质，的角度描述支持向量机。这些内容在第 5.8 节有细节的介绍，本节将从另一个角度说明支持向量分类器，可以更好地说明它的工作原理。

假设核函数 $h$ 来自于一个正定核 $K$ 的（有限的）特征展开（eigen-expansion），

\begin{matrix} (12.26) & K (x, x^{'}) = \sum_{m = 1}^{\infty} ϕ_{m} (x) ϕ_{m} (x^{'}) δ_{m} \end{matrix}

并 $h_{m} (x) = \sqrt{δ_{m}} ϕ_{m} (x)$ 。那么令 $θ_{m} = \sqrt{δ_{m}} β_{m}$ ，则式 12.25 可写为

\begin{matrix} (12.27) & min_{β_{0}, θ} \sum_{i = 1}^{N} [1 - y_{i} (β_{0} + \sum_{m = 1}^{\infty} θ_{m} ϕ_{m} (x_{i}))]_+ + \frac{λ}{2} \sum_{m = 1}^{\infty} \frac{θ_{m}^{2}}{δ_{m}} \end{matrix}

可见式 12.27 与第 5.8 节中的式 5.49 有一样的形式，并且根据之前介绍过的再生核希尔伯特空间中的理论，一定存在一个有限维度的可写为下式形式的解

\begin{matrix} (12.28) & f (x) = β_{0} + \sum_{i = 1}^{N} α_{i} K (x, x_{i}) \end{matrix}

特别地，下式是最优化准则 12.19 的一个等价的形式（参考第 5.8.1 节中的 5.67，以及 Waha et al. 2000）。

\begin{matrix} (12.29) & min_{α_{0}, α} \sum_{i = 1}^{N} (1 - y_{i} f (x_{i}))_{+} + \frac{λ}{2} α^{T} K α \end{matrix}

其中 $K$ 为所有训练集数据上核函数取值的 $N \times N$ 矩阵（练习 12.2）。

这些模型是非常通用的，它可适用于例如第五章和第九章中的平滑样条、加性（additive）样条和交互（interaction）样条等所有样条类型的模型，以及更多细节可参考 Wahba (1990) 和 Hastie and Tibshirani (1990)。这些模型还可以更广泛地写为

\begin{matrix} (12.30) & min_{f \in H} \sum_{i = 1}^{N} [1 - y_{i} f (x_{i})]_{+} + λ J (f) \end{matrix}

其中 $H$ 为一个特定结构的函数的空间， $J (f)$ 为空间上一个合适的正则项矩阵。例如，假设 $H$ 为加性函数空间 $f (x) = \sum_{j = 1}^{p} f_{j} (x_{j})$ ，且 $J (f) = \sum_{j} \int {f_{j}^{″} (x_{j})}^{2} d x_{j}$ 。则式 12.30 的解是一个加性三次样条，并且可写为式 12.28 的核表达方式，其中的 $K (x, x^{'}) = \sum_{j = 1}^{p} K_{j} (x_{j}, x_{j}^{'})$ ，每个 $K_{j}$ 为 $x_{j}$ 的单变量平滑样条中相应的核函数。（Wahba, 1990）

**图 12.5**：对数几率回归版本的支持向量机模型（[图 12.3](#figure-f1203)），使用了同样的核函数即同样的惩罚项，但使用了对数几率损失函数而不是支持向量机损失函数。两条虚线曲线代表了“+1”类别的 0.75 和 0.25 的后验概率（“-1”类别反之亦然）。紫色虚线为贝叶斯决策边界。 — **图 12.5**：对数几率回归版本的支持向量机模型（图 12.3），使用了同样的核函数即同样的惩罚项，但使用了对数几率损失函数而不是支持向量机损失函数。两条虚线曲线代表了“+1”类别的 0.75 和 0.25 的后验概率（“-1”类别反之亦然）。紫色虚线为贝叶斯决策边界。

从另一方面，上述讨论也可说明例如之前式 12.22 中列举的任意核函数可以与任意的凸性的损失函数搭配使用，也会得到式 12.28 形式的有限维度的表达形式。图 12.5 中使用了与图 12.3 一样的核函数，但使用了二项的对数似然函数作为损失函数³。所以拟合的函数是对数几率（log-odds）的估计，

\begin{aligned} \hat{f} (x) & = \log \frac{\hat{\Pr} (Y = + 1 | x)}{\hat{Pr} (Y = - 1 | x)} \\ (12.31) & = {\hat{β}}_{0} + \sum_{i = 1}^{N} {\hat{α}}_{i} K (x, x_{i}) \end{aligned}

或者反之我们可以推导出类别概率的估计

\begin{matrix} (12.32) & \hat{\Pr} (Y = + 1 | x) = \frac{1}{1 + e^{- {\hat{β}}_{0} - \sum_{i = 1}^{N} {\hat{α}}_{i} K (x, x_{i})}} \end{matrix}

拟合模型的边界形状和表现（与之前的）非常相似。示例和更多细节参考第 5.8 节。

在支持向量机中， $N$ 个 $α_{i}$ 中有相当大比例的取值可能为零（非支持点）。在图 12.3 的两个例子中，这个比例分别是 42% 和 45%。这是准则函数 12.25 前半部分的分段线性特征所产生的结果。（训练集上）类别的重叠程度越低，这个（取值为零的）比率就会越大。降低 $λ$ 一般会降低重叠的程度（因为对 $f$ 的限制更少）。较少的支持点也意味着可以更快地计算 $\hat{f} (x)$ ，可有利于减少拟合的时间。当然过度减少重叠程度会削弱模型的范化表现。

12.3.4 SVM 与维数灾难

本节将会讨论支持向量机是否在某种程度上可应对维数灾难（curse of dimensionality）。注意到在式 12.23 中，（核函数 $K$ ）并不是在幂和交叉积空间上完全无限制的内积。例如，所有的 $X_{j} X_{j}^{'}$ 项的权重都是一样的，而且核函数无法自适应地（把权重）聚焦在一个子空间上。如果特征的个数 $p$ 很大，但类别的分离仅需要在例如 $X_{1}$ 和 $X_{2}$ 两个特征的线性子空间上就可实现，那么使用这个核函数的模型很难找到真实的分离结构，可能会因为有太多维度需要考虑而表现不佳。这就需要将这个子空间的结构体现在核函数中，具体来说就是让核函数只需要考虑前两个输入变量。如果能先验地知道这种背景知识，很多统计学习都会更容易地实现。自适应方法（adaptive method）的主要目的就是去发掘这样的结构。

我们用一个示例来说明上述结论。为两个类别各自生成 100 个样本。第一个类别有四个标准正态分布的独立特征变量 $X_{1}$ 、 $X_{2}$ 、 $X_{3}$ 、 $X_{4}$ 。第二个类别也有四个标准正态分布的特征变量⁴，但是分布于条件 $9 \leq X_{j}^{2} \leq 16$ 。这是个第一个相对简单的问题。在第二个难一些的问题中，我们加入了 6 个标准高斯分布的噪声特征变量。因此在一个四维的子空间上，第二个类别几乎总是包围着第一个类别，就像橘子外的橘子皮。这个问题的贝叶斯错误率为 0.029（无论维度是 4 还是 10）。我们生成了 1000 个测试样本用于对比不同的方法。表 12.2 展示了不含噪声和含有噪声的情况下，50 次模拟平均的测试误差。

		Test Error (SE)	Test Error (SE)
	Method	No Noise Features	Six Noise Features
1	SV Classifier	0.450 (0.003)	0.472 (0.003)
2	SVM/ploy 2	0.078 (0.003)	0.152 (0.004)
3	SVM/ploy 5	0.180 (0.004)	0.370 (0.004)
4	SVM/ploy 10	0.230 (0.003)	0.434 (0.002)
5	BRUTO	0.084 (0.003)	0.090 (0.003)
6	MARS	0.156 (0.004)	0.173 (0.005)
	Bayes	0.029	0.029

表 12.2: “橘子皮”数据：表中为 50 次模拟中的测试误差的均值（和标准差）。BRUTO 自适应地拟合一个加性样条模型，MARS 自适应地拟合一个低次的交互模型。

第 1 行是在原始特征空间上的支持向量分类器。第 2-4 行是使用了次数为 2、5、和 10 的多项式核函数的支持向量机模型。在所有的支持向量方法中，我们选择最小化测试误差的成本参数 $C$ ，尽可能公平地对待各个模型。第 5 行用 $(- 1, + 1)$ 的输出变量和最小二乘法拟合一个加性线条模型，使用了 Hastie and Tibshirani (1990) 中加性模型的 BRUTO 算法。第 6 行使用了第九章中的 MARS（多元自适应回归样条），允许所有次数之间的交互从而可与“SVM/poly 10”相比较。BRUTO 和 MARS 都有可以忽略冗余变量的能力。第 5-6 行中没有使用测试误差来选择平滑参数。

在原始特征空间上，没有可分离类别的超平面，因此支持向量分类器（第 1 行）表现不佳。多项式扩展的支持向量机在测试误差率上有显著的提升，但会受到六个噪声特征变量的影响。它也对核函数的选择非常敏感，二次多项式核函数（第 2 行）表现最佳，这是因为真实的决策边界就是一个二次的多项式（曲面）。然而更高次数的多项式核函数（第 3-4 行）表现变差。BRUTO 表现较好，这是因为边界表达式是加性的形式。BRUTO 和 MARS 都很好地进行了自适应，他们的表现并没有被噪声的引入而衰退。

12.3.5 SVM 分类器的路径算法 😱

SVM 分类器的正则参数为成本参数 $C$ ，或在式 12.25 中为它的倒数 $λ$ 。使用中大多会设置一个较高的 $C$ ，结果通常会造成一定程度过拟合的分类器。

**图 12.6**：混合分布数据中径向基 SVM 分类器的测试误差对成本参数 $C$ 的曲线。每个图上方为径向基 $K_\gamma(x,y)=\exp(\gamma\\|x-y\\|^2)$ 的尺度参数 $\gamma$。$C$ 的最优值非常依赖于基函数的尺度参数。贝叶斯错误率为水平虚线。 — **图 12.6**：混合分布数据中径向基 SVM 分类器的测试误差对成本参数 $C$ 的曲线。每个图上方为径向基 $K_{γ} (x, y) = \exp (γ ‖ x - y ‖^{2})$ 的尺度参数 $γ$ 。 $C$ 的最优值非常依赖于基函数的尺度参数。贝叶斯错误率为水平虚线。

图 12.6 展示了在混合分布数据中，不同径向基参数 $γ$ 的测试误差对 $C$ 的函数曲线。当 $γ = 5$ 时（基函数的峰较窄），应使用最强的正则（取小的 $C$ 值）。当 $γ = 1$ 时（图 12.3 中使用的值），应选择适中的 $C$ 值。显然在类似这样的情况下，我们可能需要通过交叉验证来选择合适的 $C$ 值。本节介绍一个用来高效地拟合在 $C$ 变化下产生的一系列 SVM 模型的路径算法（path algorithm，类似于第 3.8 节）。

方便起见，使用式 12.25 的“损失函数+惩罚项”形式以及图 12.4。给定某个 $λ$ 值，可得 $β$ 的解为：

\begin{matrix} (12.33) & β_{λ} = \frac{1}{λ} \sum_{i = 1}^{N} α_{i} y_{i} x_{i} \end{matrix}

$α_{i}$ 仍然为拉格朗日乘子，但这里它们都取值于 $[0, 1]$ 。

**图 12.7**：演示 SVM 路径算法的简单示例。左图为模型在 $\lambda=0.5$ 时的状态。橙色点为“+1”的点，蓝色点为“-1”的点。间隔的宽度为 $2/\\|\beta\\|=2\times0.587$。两个蓝色点 $\\{3,5\\}$ 被误分类，两个橙色点 $\\{10,12\\}$ 分类正确但处于间隔 $f(x)=+1$ 的错误一侧，这些点都满足 $y_if(x_i)<1$。三个方形的点 $\\{2,6,7\\}$ 恰好处于间隔上。右图为 $\alpha_i(\lambda)$ 的分段线性趋势。位于 $\lambda=1/2$ 的水平虚线标记着对应着左图中 $\alpha_i$ 的状态。 — **图 12.7**：演示 SVM 路径算法的简单示例。左图为模型在 $λ = 0.5$ 时的状态。橙色点为“+1”的点，蓝色点为“-1”的点。间隔的宽度为 $2 / ‖ β ‖ = 2 \times 0.587$ 。两个蓝色点 ${3, 5}$ 被误分类，两个橙色点 ${10, 12}$ 分类正确但处于间隔 $f (x) = + 1$ 的错误一侧，这些点都满足 $y_{i} f (x_{i}) < 1$ 。三个方形的点 ${2, 6, 7}$ 恰好处于间隔上。右图为 $α_{i} (λ)$ 的分段线性趋势。位于 $λ = 1 / 2$ 的水平虚线标记着对应着左图中 $α_{i}$ 的状态。

图 12.7 演示了这个计算过程。KKT 最优条件意味着类别点 $(x_{i}, y_{i})$ 只可能属于下面三个不同的组：

被正确分类并处于间隔区域外的观测点。它们满足 $y_{i} f (x_{i}) > 1$ ，拉格朗日乘子 $α_{i} = 0$ 。例如图中橙色的点 8、9、和 11，以及蓝色的点 1 和 4。
处于间隔（边缘）上的点，满足 $y_{i} f (x_{i}) = 1$ ，拉格朗日乘子 $α_{i} \in [0, 1]$ 。例如图中橙色的点 7，以及蓝色的点 2 和 8。
处于间隔内的点，满足 $y_{i} f (x_{i}) < 1$ ，拉格朗日乘子 $α_{i} = 1$ 。例如图中橙色的点 10 和 12，以及蓝色的点 3 和 5。

以下为路径算法的基本思想。初始时选择一个较大的 $λ$ ，间隔 $1 / ‖ β_{λ} ‖$ 较宽，所有的点都处于间隔中并且都有 $α_{i} = 1$ 。随着 $λ$ 变小， $1 / ‖ β_{λ} ‖$ 也变小，间隔边窄。一些点将从间隔内部“移动”到间隔外部，他们的 $α_{i}$ 会从 1 变为 0。由于 $α_{i} (λ)$ 的连续性，在这个转变过程中这些点会停留在间隔线上一段时间。从式 12.33 可见，那些 $α_{i} = 1$ 的点对 $β (λ)$ 的贡献是固定的，那些 $α_{i} = 0$ 的点则没有贡献。所以当 $λ$ 变小时，随之变化的只有那些少数处于间隔上的点的 $α_{i} \in [0, 1]$ 值。由于这些点都满足 $y_{i} f (x_{i}) = 1$ ，所以一小组线性等式即可确定 $α_{i} (λ)$ 和 $β_{λ}$ 在这个过程中如何变动。因此每个 $α_{i} (λ)$ 都表现出分段线性的路径。当样本点穿过间隔时，对应了路径中的结点。图 12.7 的右图展示了左图中少数示例点的 $α_{i} (λ)$ 路径。

虽然上文描述的针对的是线性 SVM，但同样的思想也适用于非线性的模型，需要将式 12.33 替换为

\begin{matrix} (12.34) & f_{λ} (x) = \frac{1}{λ} \sum_{i = 1}^{N} α_{i} y_{i} K (x, x_{i}) \end{matrix}

更多细节可参考 Hastie et al. (2004)。可从 CRAN 获取用于拟合这些模型的 R 扩展包 svmpath。

12.3.6 回归问题的 SVM

本节将把 SVM 适用在对一个数值输出变量的回归中，它也会有一些 SVM 分类模型中的性质。我们先从下面的线性回归模型开始介绍，然后将推广到非线性的模型。

\begin{matrix} (12.35) & f (x) = x^{T} β + β_{0} \end{matrix}

为了估计 $β$ ，可以对下式求最小化

\begin{matrix} (12.36) & H (β, β_{0}) = \sum_{i = 1}^{N} V (y_{i} - f (x_{i})) + \frac{λ}{2} ‖ β ‖^{2} \end{matrix}

其中的

\begin{matrix} (12.37) & V_{ϵ} = {\begin{cases} 0 & 如果 | r | < ϵ \\ | r | - ϵ & 其他 \end{cases} \end{matrix}

**图 12.8**：左图为支持向量回归模型中使用的 $\epsilon$-不敏感误差函数。右图蓝色曲线为休伯（Huber）稳健回归中使用的误差函数。在 $|c|$ 的区域外，函数从二次变为线性。 — **图 12.8**：左图为支持向量回归模型中使用的 $ϵ$ -不敏感误差函数。右图蓝色曲线为休伯（Huber）稳健回归中使用的误差函数。在 $| c |$ 的区域外，函数从二次变为线性。

这是一种“ $ϵ$ -不敏感”误差度量，忽略绝对值小于 $ϵ$ 的误差（图 12.8 的左图）。这与支持向量分类器存在一些基本的相似处，在 SVM 中在决策边界正确分类一侧且距离较远的点不会对最优化问题产生影响。在回归问题中，这些“低误差”的点即为残差小的点。

这种误差与统计学中稳健回归使用的误差度量有一些相似之处。其中最常用的是来自 Huber (1964) 的误差函数

\begin{matrix} (12.38) & V_H (r) = {\begin{cases} r^{2} / 2 & 如果 | r | \leq c \\ c | r | - c^{2} / 2 & 如果 | r | > c \end{cases} \end{matrix}

见图 12.8 的右图。这个函数将残差绝对值大于一个选定常数 $c$ 的样本点的误差贡献从二次降低为线性。这使拟合的结果对离群样本点没那么敏感。支持向量误差度量 12.37 式在尾部也是线性的（ $ϵ$ 之外），不过它进一步将那些小残差的样本点的误差贡献降低到零。

假设 $\hat{β}$ 和 ${\hat{β}}_{0}$ 为 $H$ 的最小化解，可证明这个解和函数解可写为

\begin{aligned} (12.39) & \hat{β} & = \sum_{i = 1}^{N} ({\hat{α}}_{i}^{*} - {\hat{α}}_{i}) x_{i} \\ (12.40) & \hat{f} (x) & = \sum_{i = 1}^{N} ({\hat{α}}_{i}^{*} - {\hat{α}}_{i}) ⟨ x, x_{i} ⟩ + β_{0} \end{aligned}

其中的 ${\hat{α}}_{i}$ 和 ${\hat{α}}_{i}^{*}$ 都为正，而且它们是下面这个二次规划问题的解

\begin{aligned} min_{α_{i}, α_{i}^{*}} & ϵ \sum_{i = 1}^{N} ({\hat{α}}_{i}^{*} + {\hat{α}}_{i}) - \sum_{i = 1}^{N} y_{i} ({\hat{α}}_{i}^{*} - {\hat{α}}_{i}) + \\ \frac{1}{2} \sum_{i, i^{'} = 1}^{N} (α_{i}^{*} - α_{i}) (α_{i^{'}}^{*} - α_{i^{'}}) ⟨ x_{i}, x_{i^{'}} ⟩ \end{aligned}

最小化的约束条件为：

\begin{matrix} (12.41) & \begin{matrix} 0 \leq α_{i}, α_{i}^{*} \leq 1 / λ \\ \sum_{i = 1}^{N} (α_{i}^{*} - α_{i}) = 0 \\ α_{i} α_{i}^{*} = 0 \end{matrix} \end{matrix}

根据这些约束条件的性质，通常只有一部分的解有非零的 $({\hat{α}}_{i}^{*} - {\hat{α}}_{i})$ ，它们所对应的样本点被称为支持向量。与分类问题中的情况类似，输入变量只通过它们的内积 $⟨ x_{i}, x_{i}^{'} ⟩$ 对解产生影响。因此我们可以通过定义一个适合的内积函数，例如式 12.22 中列出的三个，而将这个方法扩展到更丰富的空间中。

需要注意准则函数 12.36 中出现了两个参数， $ϵ$ 和 $λ$ 。这两个参数起着不同的作用。 $ϵ$ 是损失函数 $V_{ϵ}$ 的参数，类比于 $V_{H}$ 的参数 $c$ 。注意 $V_{ϵ}$ 和 $V_{H}$ 依赖于 $y$ 以及 $r$ 的尺度。如果对输出变量取值进行标准化处理，比如改为 $V_{ϵ} (r / σ)$ 和 $V_{H} (r / σ)$ 则可以考虑用一些预设的 $ϵ$ 和 $c$ 的取值。（ $c = 1.345$ 对应了高斯分布 95% 的范围。）而参数 $λ$ 则是一个更惯用的正则化参数，通常用例如交叉验证的方法估计得出。

12.3.7 回归问题和核函数

如在第 12.3.3 节中所述，这种核函数性质并不是支持向量机所特有的。假设我们用一组基函数 ${h_{m} (x)}, m = 1, 2, \dots, M$ 逼近一个回归函数：

\begin{matrix} (12.42) & f (x) = \sum_{m = 1}^{M} β_{m} h_{m} (x) + β_{0} \end{matrix}

为了估计 $β$ 和 $β_{0}$ ，对下式求最小化

\begin{matrix} (12.43) & H (β, β_{0}) = \sum_{i = 1}^{N} V (y_{i} - f (x_{i})) + \frac{λ}{2} \sum β_{m}^{2} \end{matrix}

其中 $V (r)$ 为某个一般的误差度量。对任意形式的 $V (r)$ ，函数解 $\hat{f} (x) = \sum {\hat{β}}_{m} h_{m} (x) + {\hat{β}}_{0}$ 可写为这种形式

\begin{matrix} (12.44) & \hat{f} (x) = \sum_{i = 1}^{N} {\hat{α}}_{i} K (x, x_{i}) \end{matrix}

其中 $K (x, y) = \sum_{m = 1}^{M} h_{m} (x) h_{m} (y)$ 。注意这与第五章和第六章中介绍的径向基函数扩展和正则项的估计是同样的结构。

具体地，我们以 $V (r) = r^{2}$ 为例。令 $H$ 为一个 $N \times M$ 的基函数矩阵，其中的 $i m$ 位置元素为 $h_{m} (x_{i})$ ，并假设 M 很大（ $M > N$ ）。简单起见我们假设 $β_{0} = 0$ ，或 $h$ 已经包含了常数项；另一种处理常数项的方法参考练习 12.3。

为了估计 $β$ ，对这个带惩罚项的最小二乘准则最小化

\begin{matrix} (12.45) & H (β) = (y - H β)^{T} (y - H β) + λ ‖ β ‖^{2} \end{matrix}

它的解为

\begin{matrix} (12.46) & \hat{y} = H \hat{β} \end{matrix}

其中的 $\hat{β}$ 满足

\begin{matrix} (12.47) & - H^{T} (y - H \hat{β}) + λ \hat{β} = 0 \end{matrix}

若要解上式，我们需要计算 $M \times M$ 的基函数变换空间上内积矩阵。不过，两边同时乘以 $H$ 可得

\begin{matrix} (12.48) & H \hat{β} = (H H^{T} + λ I)^{- 1} H H^{T} y \end{matrix}

$N \times N$ 的矩阵 $H H^{T}$ 是由一对样本点 $i$ 和 $i^{'}$ 的内积组成的。也就是说 ${H H^{T}}_{i, i^{'}} = K (x_{i}, x_{i^{'}})$ 。在这个例子中则容易直接推导出式 12.44，任意点 $x$ 上的函数预测值满足：

\begin{aligned} \hat{f} (x) & = h (x)^{T} \hat{β} \\ (12.49) & = \sum_{i = 1}^{N} {\hat{α}}_{i} K (x, x_{i}) \end{aligned}

其中 $\hat{α} = (H H^{T} + λ I)^{- 1} y$ 。与在支持向量机中类似，我们并不需要明确那么多基函数 $h_{1} (x), h_{2} (x), \dots, h_{M} (x)$ 的形式或计算它们的取值。只需要计算每个样本对 $i$ 和 $i^{'}$ 的内积核函数 $K (x_{i}, x_{i^{'}})$ ，以及需要预测的点 $x$ 与每个训练样本的内积核函数。一些特殊的 $h_{m}$ 选择（例如一些特别容易计算的核函数 $K$ 的本征函数）可以大幅降低计算量，可能只需要 $N^{2} / 2$ 次 $K$ 的取值计算就可得到 $H H^{T}$ ，而不是 $N^{2} M$ 。

不过需要注意的是，这个性质依赖于使用了范数平方作为惩罚项。如果使用了例如 $L_{1}$ 范数 $| β |$ ，则不再成立，但可能会得到一个更优的模型。

12.3.8 讨论

通过解决多个二分类问题的方式，可以将支持向量机扩展到多类别的问题上。也就是对每两个类别构建一个分类模型，最终的分类模型为“取胜”最多次的那个类别。（参考 Kressel, 1999、Friedman, 1996、Hastie and Tibshirani, 1998）。或者，可以使用一个多项分布损失函数和一个适配的核函数，参考第 12.3.3 节。SVM 在其他的监督和非监督学习问题中有很多的应用。在本书成书的阶段，一些实证证据表明 SVM 在很多现实的学习问题中表现良好。

最后，我们简略说明支持向量机与第 7.9 节的结构风险最小化（structural risk minimization）方法的关联。假设样本点（或它们的基扩展）都处于一个半径 $R$ 的球体之内，令 $G (x) = sign [f (x)] = sign [β^{T} x + β_{0}]$ （如 12.2）。则可证明函数的集合 ${G (x), ‖ β ‖ \leq A}$ 的 VC 维度 $h$ 满足

\begin{matrix} (12.50) & h \leq R^{2} A^{2} \end{matrix}

若 f(x) 为满足 $‖ β ‖ \leq A$ 条件的在训练集上可分离的最优解，那么在训练集上至少 $1 - η$ 的概率下式成立（Vapnik 1996，139 页）。

\begin{matrix} (12.51) & Error_Test \leq 4 \frac{h [\log (2 N / h) + 1] - \log (η / 4)}{N} \end{matrix}

支持向量分类器是可获得有意义的 VC 维度边界最早的实用学习方法其中之一，因此可以应用 SRM（结构风险最小化）方法。不过在推导过程中，使用球体包含数据点的过程依赖了样本的特征变量取值。因此严格来说，函数集合的 VC 维度并不是在没有特征变量信息之前的时候先验固定的。

正则化参数 $C$ 决定了分类器 VC 维度的上界。按照 SRM 的方法，我们应该通过最小化 12.51 中的测试误差上界来选择 $C$ 。但是在选择 $C$ 的方法上，并不确定这种方法比交叉验证是否有任何优势。

本节练习

练习 12.1

证明准则 12.25 和 12.8 是等价的。

练习 12.2

证明对某个特定的核函数，式 12.29 的解与式 12.25 的解是一样的。

练习 12.3

Consider a modification to (12.43) where you do not penalize the constant. Formulate the problem, and characterize its solution.

练习 12.10

Kernels and linear discriminant analysis.

Suppose you wish to carry out a linear discriminant analysis (two classes) using a vector of transformations of the input variables $h (x)$ . Since $h (x)$ is high-dimensional, you will use a regularized within-class covariance matrix $W_{h} + γ I$ . Show that the model can be estimated using only the inner products $K (x_{i}, x_{i^{'}}) = ⟨ h (x_{i}), h (x_{i^{'}}) ⟩$ . Hence the kernel property of support vector machines is also shared by regularized linear discriminant analysis.

参考第 4.5 节中的 4.53 式。 ↩︎
原文脚注 1：在数据可分的对数几率回归中， ${\hat{β}}_{λ}$ 是发散的，但 ${\hat{β}}_{λ} / ‖ {\hat{β}}_{λ} ‖$ 收敛到最优分离超平面的方向向量上。 ↩︎
原文脚注 2：Ji Zhu assisted in the preparation of these examples. ↩︎
原文中仍为“独立特征变量”，但既然有了平方和的条件约束，是否还是独立变量？ ↩︎