高级统计方法 第一轮学习 Chapter 9 支持向量机#

什么是超平面#

在 $p$ 维空间中，$p-1$ 维的子空间称为超平面（Hyperplane）。

一般来说，超平面的方程有如下形式：

其中，$\beta_0$ 是截距项，$\beta_1, \beta_2, ..., \beta_p$ 是各个变量的系数。

在二维空间中，超平面就是一条直线；在三维空间中，超平面是一个平面。

向量 $\beta = (\beta_1, \beta_2, ..., \beta_p)$ 是超平面的法向量，决定了超平面的方向。

分割超平面#

如果 $f(x) = \beta_0 + \beta_1 X_1 + \beta_2 X_2 + ... + \beta_p X_p$ 则 $f(x) = 0$ 定义了一个超平面，将空间分割为两个部分：

• 当 $f(x) > 0$ 时，点位于超平面的一个侧面。

• 当 $f(x) < 0$ 时，点位于超平面的另一个侧面。

设 $y_i = sgn(f(x_i))$. 则 $y_i$ 可以表示点 $x_i$ 所在的类别, $\forall i, y_i * f(x_i) > 0$。

$f(x) = 0$ 就定义了一个分割超平面。

分割超平面#

一个分割超平面的上下移或旋转，只要不接触观测点，仍然是可以将数据分开的超平面。

需要有一种方法能合理的从众多超平面中选出分类效果好的超平面。

解决方案：

超平面 $\rightarrow$ 最大间隔超平面 $\rightarrow$ 最大间隔分类器

最大间隔分类器#

在所有分割超平面中，找出使两类之间的间隙或间隔最大的超平面。

首先，计算每个训练观测到一个分割超平面的距离，取最小值，称为间隔（margin）。

这个间隔值最大的那个分割超平面即为最大间隔超平面（又称最优分离超平面）。

然后，用此最大间隔超平面判断测试样本落在哪一侧，就可以分类。此为最大间隔分类器。

通俗说：最大间隔超平面是能插入两个类别之间的最宽的“平板”的中线。

训练观测到最大间隔超平面的距离最小，它们形成的向量被称为“支持向量”。他们的改变会明显影响最大间隔超平面走向，其它点不会。

如何找出最大间隔超平面？$\rightarrow$ 约束优化问题

$y_i$ 的取值为 $\{ -1, 1 \}$

点 $x_i$ 到超平面的距离为 $\frac{y_i (\beta_0 + \sum_{j=1}^p \beta_j x_{ij})}{\sqrt{\sum_{j = 1}^{p} \beta_j^2}}$，约束 $\sum_{j = 1}^{p} \beta_j^2 = 1$，保证了分母为 $1$，从而 $y_i (\beta_0 + \sum_{j=1}^p \beta_j x_{ij})$ 即为点 $x_i$ 到超平面的距离。

这是一个凸二次规划问题，可以用拉格朗日乘子法求解。

线性不可分的数据#

前述内容的隐藏假设：实际上确实是存在一个超平面可以分割这些数据的。但实际情况大多不满足。数据本身就不能被线性边界分离，是经常发生的情况，除非 $N<p$。

解决方案：使用软间隔，使得几乎能分类正确即可 $\rightarrow$ 支持向量分类器

软间隔还可以包容噪声和避免过拟合：

• 有时数据是可分离的，但噪声很大。这可能会导致最大间隔分类器的解决方案比较差。

• 对单个观测的变化极其敏感也说明可能过拟合

支持向量分类器#

支持向量分类器又称软间隔分类器，软化的含义：

1. 允许个别训练观测在间隔以内（穿越间隔但超平面分类正确，距离比间隔小）。

2. 允许个别训练观测在超平面分类错误的一侧（距离直接变成“负数”）

如何找到支持向量分类器？

其中，$\varepsilon_i$ 是松弛变量，表示观测 $i$ 违反间隔的程度。

松弛变量 $\varepsilon_i$ 的含义：允许间隔冲突：

$\varepsilon_i = 0$ 说明观测点在间隔正确的一侧。$1 > \varepsilon_i > 0$ 说明观测点介于超平面和间隔之间（穿越间隔但超平面分类正确）。$\varepsilon_i > 1$ 说明观测点在超平面分割错误的一侧。

调节参数 $C$ 的含义：能容忍的穿过间隔的观测数目的严重程度。

1. 其值为 $0$ 意味着 $\varepsilon_i$ 都为 $0$，等效为最大间隔超平面问题。

2. $C > 0$ 表示有不超过 $C$ 个观测可以落在超平面错误的一侧。

3. $C$ 越大，允许的违反间隔（甚至穿越超平面）的观测数目越多，间隔越软，模型越容易过拟合。

4. $C$ 一般通过交叉验证来选择，控制方差-偏差权衡。

该优化问题的性质：只有落在间隔或穿过间隔（间隔上、穿越间隔但超 平面分类正确、超平面分类错误）的观测会影响超平面，根据这些观测就能得到分类器。落在间隔正确侧的观测没有任何影响。

则在该问题中，刚好落在间隔和落在间隔错误（含超平面错误）一侧的观测都叫支持向量。

1. 这些观测的 $\varepsilon_i$ 都不为 $0$（间隔上除外），由调节参数 $C$ 控制其总和，是 $C$ 在结果上的反映。

2. 计算流程上，调节参数 $C$ 决定了哪些点是支持向量。$C$ 越大，间隔越宽，穿越间隔的观测也较多，支持向量的数量也更多，此时方差较低（因为支持向量多），偏差较大。

3. 如果 $C$ 较小，支持向量个数会比较少，分类器的偏差较小、方差较大。

4. 支持向量分类器的判定规则只由训练观测的一部分（支持向量）确定，使得它对距离超平面较远的观测而言，是十分稳健的。这也是此分类器与 LDA 等分类器的重要区别。

支持向量分类器（特征扩展）#

有时不论 $C$ 如何取值，线性边界根本不起作用。

可以通过将对样本变换（多项式、交互项等）加入预测变量来扩大特征空间，如 $X_1^2, X_1^3, X_1 X_2, X_1 X_2^2, \ldots$，从而将特征空间从一个 $p$ 维空间扩展到一个 $M > p$ 维空间。

然后在这个扩展后的 $M$ 维空间中应用支持向量分类器。

本质上仍然是基于原始空间的方程。拟合获得参数后，在原始空间求解得 $X_1$ 和 $X_2$，这些 $X_1$ 和 $X_2$ 的取值就形成了在原始空间中的非线性决策边界，如二次圆锥截面。

• 多项式之外，也可以使用预测变量的其他函数扩大特征空间。但应避免特征数量过于庞大，以致无法求解。

支持向量分类器（另一种表达）#

可以证明，线性支持向量分类器可以表示为：

其中，$\langle x, x_i \rangle = \sum_{j=1}^{p} x_j x_{ij}$ 是 $x$ 和 $x_i$ 的内积。

$\alpha_i$ 是拉格朗日乘子，通俗解释可以理解为，训练样本 $x_i$ 在决定分类边界时的 “重要性权重”或“发言权” 。只有支持向量的 $\alpha_i$ 不为 $0$，非支持向量的 $\alpha_i$ 都为 $0$。

可以证明，大部分 $\alpha_i$ 都为 $0$，只有支持向量的 $\alpha_i$ 不为 $0$，故而也可写为：

其中，$SV$ 是支持向量的索引集合。

进一步考虑，上式中的内积 $\langle x, x_i \rangle$ 可以进行泛化，变成一个核函数 $K(x, x_i)$。

核函数和支持向量机#

可以使用更一般的形式，即核函数（kernel）代替内积 $\langle x, x_i \rangle$，从而得到支持向量机（Support Vector Machine, SVM）：

如果选择 $K(x, x_i) = \langle x, x_i \rangle$，则得到线性支持向量分类器。

对于一个新的观测点 $x$，分类步骤（理论上）依然是：计算其与已知训练集的核函数结果的加权求和，判断 $f(x)$ 的符号，进行分类。

对于其参数（权重 $\alpha$），使用训练集进行估计，结果为 $\hat{\alpha}$。

典型的核函数是多项式核函数（自由度为 $d$），可以生成光滑的决策边界：

如果选择 $d = 1$，即 $K(x_i, x_{i^{'}}) = 1 + \sum_{j = 1}^p x_{ij} x_{i^{'}j}$，则得到线性支持向量分类器。

径向核函数#

径向基核函数：

其中，$\gamma > 0$ 可控制方差，$\gamma$ 越大，每个点的作用范围就越被压缩，模型的灵活性越高，方差越大，偏差越小。

本质上，径向基核函数是将每个训练观测点 $x_i$ 映射到一个无穷维空间中，在该空间中，每个观测点对应一个函数，函数值随着与 $x_i$ 的距离增大而指数级衰减。通过径向基核函数，可以便捷的计算这些函数之间的内积，而无需显式地进行高维映射。

核函数的优势#

使用核函数，我们只需要为 $\binom{n}{2}$ 个不同样本配对计算核函数 $K$，并估计权重 $\alpha$，且有大量的 $\alpha = 0$。

而原始的特征扩展方法，可能需要计算 $M$ 维空间中的内积，特征数膨胀速度极快。

两者的分类步骤是一样的：计算其与已知训练集的核函数结果的加权 求和，判断 $f(x)$ 的符号，进行分类。

SVMs：不只是二分类？#

按照上述定义的支持向量机只能处理二分类问题。

在实际应用中，可以通过以下两种常用方法将支持向量机扩展到多分类问题：

1. 一对一（One-vs-One, OvO） 拟合所有共 $\binom{K}{2}$ 对的二分类分类器 $\hat{f}_{kl}(x)$。$x^*$ 会被分类到获得预测次数最多的类别。

2. 一对多（One-vs-Rest, OvR or One-vs-All, OvA） 对于每个类别，训练一个二分类支持向量机，将该类别作为正类，其他所有类别作为负类。对于 $K$ 个类别，总共需要训练 $K$ 个分类器。$x^*$ 会被分类到 $\hat{f}_k(x^*)$ 最大的一类。

如果 $K$ 不太大，采用 OvO。

支持向量分类器 vs. 逻辑斯谛回归#

支持向量分类器可以改写为：

上式的第一项是损失函数，表示分类错误的惩罚；第二项是正则化项，防止过拟合。

即为损失函数 $L(X, y, \beta)$ + 惩罚项 $P(\beta)$ 的形式。

损失函数

的形式即为铰链损失（hinge loss），非常类似逻辑斯谛回归中的对数损失（logistic loss）：

对于支持向量分类器，间隔以外且被正确分类的观测样本的 $\max (0, 1 - y_i f(x_i)) = 0$，不会对损失函数产生影响。即只有支持向量在构建分类器时有用。

而与之不同，逻辑斯蒂回归的损失函数在任何时候都不为 $0$。