ISL 真是好书！

资料

An Introduction to Statistical Learning，下文简称 ISL

Maximal Margin Classifier

What Is a Hyperplane?

超平面 (hyperplane) 是指在 p 维空间中维度为 p-1 的子空间。例如，对于二维空间，超平面就是一条线；在三维空间，超平面就是一个二维的平面。

超平面的数学定义很简单，但与一个二维空间的超平面，定义如下： \[ \beta_{0}+\beta_{1} X_{1}+\beta_{2} X_{2}=0 \] 我们可以看到这就是一条直线的表达式。

因此，我们可以推断出 p 维空间的超平面的一般表达式如下：如果一个点满足下列式子，则在超平面上。 \[ \beta_{0}+\beta_{1} X_{1}+\beta_{2} X_{2}+\ldots+\beta_{p} X_{p}=0 \] 如果一个点 X 不在超平面上，即上面的这个式子不为0（大于0 或 小于0），我们称这个点在超平面的一侧。因此，超平面将这个空间分为了两半，下图为二维空间超平面划分出的两个空间示意图。

Classification Using a Separating Hyperplane

假设我们有一个 n×p 的数据集 X，包好 n 条观测值 和 p 个特征。这些观测值只有两个水平，-1 和 1。我们同时还有一个验证集。我们的目的是通过训练集构建一个 classfier，可以正确地对验证集进行分类。这里我们有很多方法可以用，经典地方法有线性判别分析和逻辑回归，决策树方法有分类树、bagging、boosting 。现在我们剔除一个基于 separating hyperplane 概念的新方法。

假设我们可以构建一个超平面，可以完美地区分训练集中不同的观测值，例如下图的左图就显示了3种 separating hyperplane 的例子。

左图划分的公式如下： \[ \beta_{0}+\beta_{1} x_{i 1}+\beta_{2} x_{i 2}+\ldots+\beta_{p} x_{i p}>0 \text { if } y_{i}=1 \text { , } \] \[ \beta_{0}+\beta_{1} x_{i 1}+\beta_{2} x_{i 2}+\ldots+\beta_{p} x_{i p}<0 \text { if } y_{i}=-1 \]

因此，这里的一个 separating hyperplane 均具有下面的属性： \[ y_{i}\left(\beta_{0}+\beta_{1} x_{i 1}+\beta_{2} x_{i 2}+\ldots+\beta_{p} x_{i p}\right)>0 \] 如果我们能构建一个 separating hyperplane，我们就可以用它作为一个 classifier ，直接用在验证集中，效果如上图9.2 右图，预测值取决于上面的式子的符号，大于0则预测为1，小于0则预测为-1。我们同时可以利用上面式子的大小，越大说明预测值越可信。

通过这个例子，我们可以看到，通过 separating hyperplane 这种思想，我们最终构建的是一个线性决策线。

The Maximal Margin Classifier

一般来说，如果我们可以通过一个超平面来完美地划分我们的数据，那么实际上存在无数条这样的可能的超平面。如果需要通过 separating hyperplane 方法来构建一个 classfier ，那么我们需要决定使用哪一个 separating hyperplane 。

一个自然的方法是 the maximal margin classifier ，也称为 optimal separating hyperplane ，即选择与训练集所有的观测点距离最远的 separating hyperplane 。我们可以计算所有观测点到一个给定的 separating hyperplane 的直线距离，所有点的直线距离的最小值称为 margin 。the maximal margin classifier 是 margin 最大的超平面（即所有点的最小直线距离 margin 最大）。虽然这种方法一般很成功，但是当p很大，可能会造成 overfitting。

下图展示了用上图9.2训练集数据计算的最大边际分类器的结果。margin 体现为虚线和实线的直线距离，我们可以看到有3个点与分类器的距离最小，这三个点一般也被称为 support vectors ，因为它们是 p 维空间的向量，而且它们 “support” 我们的最大边际分类器的结果，如果我们把这些点稍微移动了一些位置，那么我们最终的分类器结果也会跟着改变。其实，最大边际分类器的构建仅取决于这几个点，和其他点毫不相关。

Construction of the Maximal Margin Classifier

简单地说，对于n × p 的训练集，反应变量只有两个水平 -1 和 1，最大边际超平面就是下面问题的解。 \[ \begin{aligned} &\underset{\beta_{0}, \beta_{1}, \ldots, \beta_{p}, M}{\operatorname{maximiize}} M \\ &\text { subject to } \sum_{j=1}^{p} \beta_{j}^{2}=1, \\ &y_{i}\left(\beta_{0}+\beta_{1} x_{i 1}+\beta_{2} x_{i 2}+\ldots+\beta_{p} x_{i p}\right) \geq M \quad \forall i=1, \ldots, n . \end{aligned} \] 首先假定 M 大于0，那个式子就保证了训练集中所有的观测值均会正确地分类。基于上式第二行的条件，可以推断出，点到超平面的直线距离就是下式。（未证明） \[ y_{i}\left(\beta_{0}+\beta_{1} x_{i 1}+\beta_{2} x_{i 2}+\ldots+\beta_{p} x_{i p}\right) \] 因此，这个式子确保了所有观测值均被正确分类了，并且与超平面的距离至少为 M，即 M 就是 margin 。然后，我们需要挑出一组 β ，使得 M 的值最大。

The Non-separable Case

上面的方法有一个缺点，有些时候根本不存在 separating hyperplane ，所以也就不存在最大边际超平面。带入上式即为，找不到 M > 0 的解，下图为一个例子。

我们可以把这个思路扩展一下，改成找到一个能正确分类大多数观测点的超平面，这个方法称为 support vector classifier 。

Support Vector Classifier

如上图所示，有些时候我们无法找到一个能把所有观测值正确分开的超平面。事实上，即便真的存在 separating hyperplane ，有时这个超平面构建成的分类器可能也不理想。由于要将所有观测值均要正确分开，因此 separating hyperplane 会对于个体观测值非常敏感。下图为一个例子，右图中仅仅是新增了一个观测值就导致最大边际超平面发生了很大的改变，新的超平面其实并不理想，比如说这个超平面的 margin 非常小。

由于最大边际超平面对于单个观测值的变化非常敏感，因此非常容易造成过拟合的现象。

因此这种情况下，我们可能更希望想要一个不是完美分类的分类器，优点在于更加稳健，不容易受到个别极端值的影响。也就是说，训练集中一小撮的观测值被错误分类是允许的，这是为了让剩下的大部分观测值的预测更加稳定。

上述思想一般就称为 support vector classifier ，有时也称为 soft margin classifier ，效果见下图。左图我们可以看到大部分点在划分的margin 线以外，有几个点在划分的 margin 线以内；右图甚至有几个点直接判别错误（在超平面的另一边），如 11 和 12 。

Details of the Support Vector Classifier

support vector classifier 方法的数学式子如下： \[ \begin{aligned} &\underset{\beta_{0}, \beta_{1}, \ldots, \beta_{p}, \epsilon_{1}, \ldots, \epsilon_{n}, M}{\operatorname{maximize}} M \\ &\text { subject to } \sum_{j=1}^{p} \beta_{j}^{2}=1, \\ &y_{i}\left(\beta_{0}+\beta_{1} x_{i 1}+\beta_{2} x_{i 2}+\ldots+\beta_{p} x_{i p}\right) \geq M\left(1-\epsilon_{i}\right), \\ &\epsilon_{i} \geq 0, \sum_{i=1}^{n} \epsilon_{i} \leq C \end{aligned} \] 这里的 C 是一个调整参数。同上，M 表示 margin ，需要寻找最大值。ε_i 为松弛变量，使得有些个体可以在错误的margin 甚至是错误的 hyperplane 上；如果 ε_i 等于0，那么这个观测值就在正确的 margin 一侧；如果 ε_i > 0 ，那么这个观测值就在 错误的 margin 一侧；如果 ε_i > 1 ，那么这个观测值就在错误的 超平面一侧。

这里的 C 限制了 ε_i 之和，因此这个参数表示我们能允许多少观测值被错误分类。如果 C = 0, 那么这就是最大边际超平面。C 的范围在 0 ~ n 之间，下图为不同 C 值的结果，左上图C值最大，之后不断减少。

在实际情况中，我们一般用交叉验证来决定 C 值的大小。

support vector classifier 有一个特性：只有在 margin 线上或在错误的margin线一侧的点才会影响 support vector classifier 结果；对于那些处于正确的 margin 线一侧的点，移动这些点的位置不会影响分类器。

因此在 margin 线上或在错误的margin线一侧的点称为 support vectors 。这和我们说 C 值控制 bias-variance trade-off 也是一致的，当 C 值很大时，存在很多观测值在错误的 margin 线一侧，即support vectors 很多，即构建分类器用到的点很多，所以 variance 较低（由于用到了很多的 support vectors ），但是可能 bias 很高，如上图左上图。当 C 值很小时，构建分类器用到的点较少，因此 variance 较高，但是 bias 较低，如右图右下图，这里其实只有 8 个 support vectors 。

这种分类器几乎不受到离超平面很远的点的影响，这个性质和其他分类方法不太一样，比如前面提到的线性判别方法 (LDA 方法需要计算每个水平所有观测值的均值，以及使用所有观测值计算水平内的方差矩阵) 。与之相反，逻辑回归对于远离决策线的观测值的敏感性很低。

Support Vector Machines

我们之前提到过如何将一个线性的分类器转为非线性的分类器。这里 support vector machines 实现了同样的效果。

Classification with Non-linear Decision Boundaries

有时我们会面临非线性的决策线，如下图。此时，support vector classifier 结果基本毫无用处。

类似于线性模型的作法，这里我们也可以加入多项式来解决这个问题，比如对 p 个特征都添加二次型。 \[ X_{1}, X_{1}^{2}, X_{2}, X_{2}^{2}, \ldots, X_{p}, X_{p}^{2} \] 此时的分类器算法变为： \[ \begin{aligned} &\underset{\beta_{0}, \beta_{11}, \beta_{12} \ldots, \beta_{p 1}, \beta_{p 2}, \epsilon_{1}, \ldots, \epsilon_{n}, M}{\operatorname{maximize}} M \\ &\text { subject to } y_{i}\left(\beta_{0}+\sum_{j=1}^{p} \beta_{j 1} x_{i j}+\sum_{j=1}^{p} \beta_{j 2} x_{i j}^{2}\right) \geq M\left(1-\epsilon_{i}\right), \\ &\sum_{i=1}^{n} \epsilon_{i} \leq C, \quad \epsilon_{i} \geq 0, \sum_{j=1}^{p} \sum_{k=1}^{2} \beta_{j k}^{2}=1 \end{aligned} \] 这里我们可以加入更高的项，或者加入互作效应（X_iX_j）等。我们可能会添加了太多的变量，导致计算量失控。support vector machines 方法可以有效管控这一点。

The Support Vector Machine

SVM 方法是上面 support vector classifier 方法的拓展，使用 kernels 方法来拓展变量空间。思路见上，但是 kernels 方法是一个有效的实现这个思路的计算方法。ISL 这里没有详细介绍 SVM 的算法。

下面这些论断全没有证明。

support vector classifier 求解需要用到内积 (结果为一个标量)， 标量公式如下： \[ \langle a, b\rangle=\sum_{i=1}^{r} a_{i} b_{i} \] 因此两个观测值x_i ，x_i’ 的内积为 \[ \left\langle x_{i}, x_{i^{\prime}}\right\rangle=\sum_{j=1}^{p} x_{i j} x_{i^{\prime} j} \] support vector classifier 可以表示为下式。这里有n 个参数 α_i ，每个观测值一个参数。为了估计 f(x) ，我们需要计算新点 x 和训练集中所有的点 x_i 的内积。 \[ f(x)=\beta_{0}+\sum_{i=1}^{n} \alpha_{i}\left\langle x, x_{i}\right\rangle \] 为了估计参数 α₁, …… ，α_n 和 β₀ ，我们需要计算训练集中所有观测值之间可能的配对的内积（需要计算 C²_n 次）

实际上，大多数点的 α_i 都是0，只有 support vector 的 α_i 不为0 。因此，假定 S 是所有这些 support points 的索引的集合，我们可以将上面的解函数写成 \[ f(x)=\beta_{0}+\sum_{i \in \mathcal{S}} \alpha_{i}\left\langle x, x_{i}\right\rangle \] 总结一下，support vector classifier 方法中估计参数和求解，都是用了求内积的方法。这里我们可以把所有求内积的地方改为一个一般化的形式： \[ K\left(x_{i}, x_{i^{\prime}}\right), \] 这里的 K 指某种函数，一般称为 kernel 。kernel 函数是一个度量两个观测值之间的相似性的指标。例如，我们可以使用下式，这就是内积的公式，一般也称为 linear kernel ，因为 support vector classifier 方法是线性的。 linear kernel 实际是采用皮尔逊相关的方法来衡量观测值之间的相似性。 \[ K\left(x_{i}, x_{i^{\prime}}\right)=\sum_{j=1}^{p} x_{i j} x_{i^{\prime} j} \] 我们可以换别的 kernel ，例如下式，这一般称为 polynomial kernel of degree d ，这里 d 是一个正整数。这时候构建的决策线就不再是线性的。 \[ K\left(x_{i}, x_{i^{\prime}}\right)=\left(1+\sum_{j=1}^{p} x_{i j} x_{i^{\prime} j}\right)^{d} \] 当采用非线性的 kernel 时，这时便称为 support vector machine 。预测函数如下：

\[ f ( x ) = \beta _ { 0 } + \sum _ { i \in S } \alpha _ { i } K ( x , x _ { i } ) \]

下图中的左图显示了SVM采用多项式 kernel 的效果。

多项式 kernel 仅仅是其中的一个例子，另一个可选的 kernel 为 radial kernel ，形式如下。其中的 γ 为一个正数。上图中的右图就是使用了 radial kernel 的效果。 \[ K ( x _ { i } , x _ { i ^ { \prime } } ) = \operatorname { exp } ( - \gamma \sum _ { j = 1 } ^ { p } ( x _ { i j } - x _ { i ^ { \prime } j } ) ^ { 2 } ) . \]

radial kernel 如何工作的呢？假设我们有一个验证集观测值 x^* ，这个点与一个训练集的点 x_i 距离很远，那么经过一个简单的数学推理，我们知道这两个点配对的 radial kernel 非常小，接近于0，因此这个训练集的点对这个验证集的预测几乎没有作用。

使用不同的 kernel 函数，相较于使用旧的特征往特征空间中添加新的特征（比如加入二次项），优势在哪里呢？一个主要的优势就是计算量的优势。

An Application to the Heart Disease Data

ROC curve

对于一个二分类的反应变量，预测结果和真实结果比对统计如下：

ROC 曲线是用来展现不同的阈值下两种错误的错误概率的变化。下图就是 ROC 图 ，纵坐标是 sensitivity /power/ 1- Type Ⅱ error，就是零假设被正确拒绝的概率（真实值为1的个体中预测值也为1的概率，结合上表为 TP/P）；横坐标为 Type Ⅰ error / 1-specificity ，为零假设被错误拒绝的概率，即假阳性概率（真实值为0的个体中预测值为1的概率，计算公式为 FP/N）。

ROC 可以比较预测二分类变量的不同方法的预测效果。ROC 曲线越接近左上侧越好，或者说 ROC 曲线下方的面积越大越好。

这里我们采用13个特征预测个体是否有心脏疾病，总共297个样本，随机挑选207个样本作为训练集，90个样本作为验证集。下图中的左图为采用 LDA 和 support vector classifier 方法的效果，二者差不多，support vector classifier 方法略有优势；右图为与采用 radial kernel 的 SVM 方法的比较，这里随着 γ 的增加，决策线越曲折，ROC 曲线越好。但是看清楚，这里的图是训练集的效果，会有误导作用，我们要看验证集的效果。

下图为验证集的效果，我们左图差不多，右图 γ = 0.1 在训练集上效果最好，但是在验证集上效果最差，再一次证明模型并不是越灵活越好。

SVMs with More than Two Classes

上面的讨论都只是针对二分类的反应变量，那么我们能不能将 SVMs 方法应用到有更多的水平的反应变量上呢？事实上 SVMs 方法基于的 separating hyperplanes 理念本身并不能自动地推导到多个水平的分析。目前也有很多方法将 SVMs 方法拓展到多水平反应变量的分析，最著名的两个就是 one-versus-one 和 one-versus-all 方法。

One-Versus-One Classification

假设反应变量是 K 个水平，那么我们构建 C_K² 次 SVMs ，每一次包含一对水平。预测的时候，我们会计算这 C_K² 次的预测值，然后将所有预测结果中出现频率最频繁的水平作为最终的预测值。

One-Versus-All Classification

这个方法我们拟合 K 次 SVMs，每一次比对其中一个水平（设为1）和剩下的 K-1 个水平（设为-1）。预测时，我们分配所有 SVMs 中下式最大的 SVM 的水平，因为这个式子越大，说明这个观测值属于这个水平的可行程度越高。

\[ \beta _ { 0 k } + \beta _ { 1 k } x _ { 1 } ^ { * } + \beta _ { 2 k } x _ { 2 } ^ { * } + \ldots +\beta _ { p k } x _ { p } ^ { * } \]

Relationship to Logistic Regression

support vector classifier 的拟合条件可以重新写为

\[ \operatorname { minimize } _ { \beta _ { 0 } , \beta _ { 1 } , \ldots , \beta _ { p } } \{ \sum _ { i = 1 } ^ { n } \operatorname { max } [ 0,1 - y _ { i } f ( x _ { i } ) ] + \lambda \sum _ { j = 1 } ^ { p } \beta _ { j } ^ { 2 } \} \] 其中 λ 是一个非负数，后面的式子就类似于岭回归的惩罚项。总的式子就是 “Loss + Penalty” 的形式。这里的 Loss 项拓展开来如下：

\[ L ( X , y , \beta ) = \sum _ { i = 1 } ^ { n } \operatorname { max } [ 0,1 - y _ { i } ( \beta _ { 0 } + \beta _ { 1 } x _ { i 1 } + \ldots + \beta _ { p } x _ { i p } ) ] \] 这也称为 hinge loss 。如下图所示，SVM 的 Loss 项和逻辑回归相关程度很高。SVM 的 Loss 项还有一个特点，对于处于正确的margin 一侧的点对模型结果没有影响，这体现在下式如果大于1，那么 Loss 项就正好是 0 。但是，逻辑回归不会正好是 0 ，会是一个很小的值，同样见下图。 \[ y _ { i } ( \beta _ { 0 } + \beta _ { 1 } x _ { i 1 } + \ldots + \beta _ { p } x _ { i p } ) \]

因此 support vector classifier 和 逻辑回归的结果很相似，当两个水平之间分得较开，support vector classifier 结果更好一点；如果两个水平之间重叠区域较多，那么逻辑回归效果更好。

因此在描述线性关系的过程中，SVM 和逻辑回归等经典方法是高度相关的。那么是否在描述非线性关系时 SVM 采用特殊的 kernels 的做法就是独一无二的呢？答案也是否定的，我们同样可以对逻辑回归或者其他经典的分类方法采用非线性的 kernels 。但是由于历史原因，一般 non-linear kernels 用于SVMs 方法比经典的逻辑回归等方法更加广泛。

SVM 方法的思路同样可以用于回归问题中，称为 support vector regression ，这里的 Loss 项是超过某个常数的残差绝对值之和，低于给定常数的残差绝对值则直接忽略。

R代码

略