统计学习方法BR-CH7：支持向量机（SVM）

By arthur503 -- 15 Oct 2013

一、支持向量机总览

支持向量机（Support Vector Machine，SVM）是一种二类分类模型。

1. 模型

支持向量机的基本模型是：定义在特征空间上的间隔最大的线性分类器。

支持向量机与感知机的不同

感知机是采用误分类最小策略，求得分离超平面，这时的解是无穷多个；支持向量机是间隔最大策略，求得最优分离超平面，这时的解是唯一的。

支持向量机的学习是在特征空间进行的

输入都由输入空间转换到特征空间。其中，线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量；非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。

支持向量机适用的数据集

支持向量机可用于线性可分数据集，利用硬间隔最大化得到线性可分支持向量机；可以用于近似线性可分数据集（即：有线性不可分的特异点，去除后数据集线性可分），利用软间隔最大化得到线性支持向量机（即：包含线性可分和线性不可分情况）；还可以用于线性不可分数据集（即：非线性可分数据集），利用定义一个从原空间到特征空间的非线性转换（映射），将非线性问题变换成线性问题，通过求解变换后的线性问题来解出原来的非线性问题（可以通过核技巧和软间隔最大化进行求解），得到非线性支持向量机。

这个过程是一个构建由简入繁的模型的过程。模型逐渐复杂，但适用的数据集范围不断扩大。后者均可以看做前者的推广，前者可以看做后者的特例。

2. 策略

支持向量机的学习策略就是间隔最大化。

通过数学推导，间隔最大化问题可以形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的合页损失函数的最小化问题。

3. 算法

支持向量机的学习算法是求解凸二次规划的最优化算法。

下面单独介绍三种支持向量机。

二、线性可分支持向量机

1. 定义

给定一个数据集如下：

T = {(x1,y1),(x2,y2),···,(xn,yn)}
其中，xi ∈ R<sup>n</sup>, yi ∈ {+1,-1}, i = 1,2,...,N。

我们假定数据集是线性可分的（注意：这是一个很强的条件，与其他支持向量机的区别也在于此）。

给定线性可分训练数据集，通过间隔最大化或等价的求解相应的凸二次规划问题学习得到的分离超平面为：

w* · x + b* = 0

及相应的分类决策函数：

f(x) = sign(w* · x + b*)

称为线性可分支持向量机。

其中，根据List of mathematical symbols，w* 表示w的共轭复数。【存疑：为何要用共轭复数？】

那么，间隔是什么间隔？间隔最大化是怎么最大化？相应的凸二次规划问题又是什么？我们下面分别来讲。

2. 函数间隔和几何间隔

函数间隔（functional margin）

一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面：w·x + b = 0确定的情况下，|w·x+b|能够相对的表示点x距离超平面的远近，而w·x+b的符号与类标记y的符号是否一致能够表示分类是否准确。因此，我们可以用量y(w·x+b)来表示分类的正确性及确信度（结果为正表示分类正确，为负表示分类错误；结果越接近于0表示分类确信度越高），这就是函数间隔的概念。

函数间隔的表示符号为γ^{^}。对于给定的训练数据集T和超平面(w,b)：

定义超平面(w,b)关于样本点(xi,yi)的函数间隔为：

γ_{i}^{^} = y_{i}(w·x_{i} + b)

定义超平面(w,b)关于训练数据集T的函数间隔为，超平面(w,b)关于T中所有样本点的函数间隔的最小值，即：

γ^{^} = min_{i=1,…,N}γ_{i}^{^}

几何间隔（geometric margin）

函数间隔可以表示分类预测的正确性及确信度。但是，选择分离超平面时，只有函数间隔还不够。因为只要成比例的改变w和b（例如：将他们改变成为2w和2b），超平面本身没有发生改变（因为超平面为w·x+b=0，故w和b成比例改变后，超平面本身并不改变），但是函数间隔确实原来的2倍。这启示我们，可以对分离超平面的法向量w加以某种约束，如规范化，||w||=1，使得间隔是确定的。这时的间隔成为几何间隔。

几何间隔的表示符号为γ。对于给定的训练数据集T和超平面(w,b)：

定义超平面(w,b)关于样本点(xi,yi)的几何间隔为：

γ_{i} = y_{i}(\frac{w}{||w||}·x_{i} + \frac{b}{||w||})

定义超平面(w,b)关于训练数据集T的几何间隔为，超平面(w,b)关于T中所有样本点的几何间隔的最小值，即：

γ = min_{i=1,…,N}γ_{i}

函数间隔和几何间隔的关系

我们可以看出，函数间隔γ^{^}与几何间隔γ的关系为：

γ_{i} = \frac{γ^{^}}{||w||}

γ = \frac{γ^{^}}{||w||}

如果||w||=1，那么函数间隔与几何间隔相等。如果超平面的参数w和b等比例的改变（此时超平面没有改变），则函数间隔也等比例改变，而几何间隔不变。因此，一般计算中使用几何间隔而非函数间隔。

3. 间隔最大化

对线性可分数据集而言，线性可分分离超平面有无穷多个（等价于感知机。由于数据集线性可分，若采用误分类最小策略，误分类数目为0，但结果无穷多个）；但是，采用间隔最大化策略，得到几何间隔最大的分离超平面是唯一的（证明见下面）。

间隔最大化的直观解释是：不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将他们分开。这样的哦超平面应该对未知的新实例有很好的分类预测能力。

最大间隔分离超平面

如何求得一个几何间隔最大的分离超平面？这个问题可以表示为下面的约束最优化问题：

max_{w,b} γ

s.t. y_{i}(\frac{w}{||w||}·x_{i} + \frac{b}{||w||}) ≥ γ, i=1,2,…,N

理解如下：约束条件表示超平面(w,b)关于每个样本点的几何间隔至少是γ，而我们希望最大化超平面(w,b)关于训练数据集的几何间隔γ（即：求得γ的最大值）。

将此式转换为函数间隔形式，如下：

max_{w,b} \frac{γ^{^}}{||w||}

s.t. y_{i}(w·x_{i} + b) ≥ γ^{^}, i=1,2,…,N

上面已经讲过，函数间隔γ^{^}的取值并不会影响最优化问题的解（若w和b改变，则函数间隔改变，超平面和几何间隔不变），这样，可以对上式取γ^{^}=1，代入上式。同时，又由于最大化\frac{1}{||w||}与最小化\frac{1}{2}||w||^{^}相同，转换上式，我们可以得到：

min_{w,b} \frac{1}{2}||w||^{^}

s.t. y_{i}(w·x_{i} + b) - 1 ≥ 0, i=1,2,…,N

这是一个凸二次优化问题（convex quadratic programming）。之前的转化也都是为了达成这一步。如果求解出约束最优化问题的w* ,b* ，那么就可以得到最大间隔分离超平面w* · x + b* = 0和分类决策函数f(x) = sign(w* · x + b* )，即可以得到线性可分支持向量机模型。

最大间隔分离超平面的存在唯一性

《统计学习方法》书中P100页证明了线性可分数据集的最大间隔分离超平面的存在性和唯一性。我们在此证明略过，需要时可以查阅书。

支持向量和间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。支持向量是使约束条件式的等号成立的点，即：

y_{i}(w·x_{i} + b) - 1 = 0

分离超平面在正负支持向量实例中间。分别经过正负支持向量，并且平行于分离超平面的平面称为间隔边界。间隔边界之间的距离称为间隔（margin）。

间隔依赖于分离超平面的法向量w。我们知道，在支持向量时，几何间隔达到最小。由上可知，此时函数间隔r^{^}定义为1，由此可得：

γ^{^} = 1

∴ γ · ||w|| = 1 即： γ = \frac{1}{||w||}

此时，几何间隔(margin)为\frac{1}{||w||}，间隔为2γ = \frac{2}{||w||}。

在决定分离超平面时只有支持向量起作用，其他实例点并不起作用。正因为如此，所以将这种分类模型成为支持向量机。支持向量的个数一般很少，因此，支持向量机是由很少的“重要的”训练样本决定。

4. 学习的对偶算法

对原始的优化问题，通过拉格朗日对偶性，求解对偶问题从而得到原始问题的最优解，这就是线性可分支持向量机的对偶算法。

这样做的优点：1. 对偶问题往往更容易求解；2. 自然引入核函数，进而推广到非线性分类问题。

此处不讲了，因为我对偶算法我还没看懂。有需要的请参考《统计学习方法》P103页。

三、线性支持向量机

1. 软间隔最大化

线性可分支持向量机中，要求数据集是线性可分的。但这种情况在实际情况中很少，更一般的情况是：训练数据中有一些特异点，将这些特异点去除后，剩下大部分的样本点组成的集合是线性可分的。

这意味着某些样本点不能满足函数间隔大于等于1的约束条件。为此，可以对每个样本点引入一个松弛变量ξ_{i}≥0，使得函数间隔加上松弛变量大于等于1.这样，约束条件变为：

y_{i}(w·x_{i} + b) ≥ 1 - ξ_{i}

同时，由于对于每一个松弛变量ξ_{i}，支付一个代价ξ_{i}。所以，目标函数由原来的\frac{1}{2}||w||^{2}，变成了：

\frac{1}{2}||w||^{2} + C∑_{i=1}^{N}ξ_{i}

其中，C＞0称为惩罚参数。一般由应用问题决定，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。

最小化目标函数包括两层含义：1. 使\frac{1}{2}||w||^{2}尽量小，即间隔尽量大；2. 同时使误分类点的个数尽量小。C是调和二者的参数。

这样，我们可以和训练数据集线性可分时一样来考虑训练数据集线性不可分时的线性支持向量机的学习问题。相应于硬间隔最大化，它称为软间隔最大化。

相应凸二次规划（convex quadratic programming）问题

线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题（原始问题）：

min_{w,b,ξ} \frac{1}{2}||w||^{2} + C∑_{i=1}^{N}ξ_{i}

s.t. y_{i}(w·x_{i} + b) ≥ 1 - ξ_{i}, i=1,2,…,N 其中，ξ_{i}≥0, i=1,2,…,N

可以证明，在此凸二次规划问题中，w的解是唯一的，b的解不唯一，但存在于一个区间。

这样，我们可以给出线性支持向量机的定义。如下：

3. 线性支持向量机的定义

对于给定的线性不可分的训练数据集，通过求解凸二次规划问题，即软间隔最大化问题，得到分离超平面为：

w* · x + b* = 0

以及相应的分类决策函数：

f(x) = sign(w* · x + b* )

称为线性支持向量机。

对于线性支持向量机学习来说，其模型为分离超平面：w* · x + b* = 0 及决策函数：f(x) = sign(w* · x + b* )，其学习策略为：软间隔最大化，学习算法为：凸二次规划。

4. 学习的对偶算法

还没看拉格朗日对偶形式，因此略。

5. 合页损失函数

线性支持向量机的学习还有另一种解释，就是最小化以下目标函数：

∑_{i=1}^{N}[1-y_{i}(w·x_{i}+b)]_{+} + λ||w||^{2}

目标函数的第一项是经验损失或经验风险，函数：

L(y(w·x+b)) = [1-y_{i}(w·x_{i}+b)]_{+}

称为合页损失函数，下标”+”表示取正值的函数。

相比之下，合页损失函数不仅要求分类正确，而且确信度足够高时损失才是0.也就是说，合页损失函数对学习有更高的要求。

四、非线性支持向量机

1. 非线性分类问题

如果训练数据集线性可分，可以使用线性可分支持向量机；如果训练数据集中有特异点，去除后线性可分，可以使用线性支持向量机。那么，如果训练数据集线性不可分呢？

在某些数据集中，数据可以使用一个超曲面将正负例分开则称这个问题为非线性可分问题。

非线性问题往往不好求解，因此，我们希望能找到一种方法，将非线性问题对应到线性问题中来，从而用线性分类问题的方法解决。比如，可以将一个椭圆曲面映射到成为新空间的直线，这样，就可以对新空间的点进行线性分类。

那么问题出现了，如何进行非线性变换，来把原空间中的非线性问题映射为新空间中的线性问题？

我们通过核技巧来进行变换。

2. 核技巧和核函数

核技巧应用到支持向量机，基本想法就是通过一个非线性变换将输入空间（欧式空间R^{n}或离散集合）对应于一个特征空间（希尔伯特空间H），使得在输入空间R^{n}中的超曲面模型对应于特征空间H中的超平面模型（支持向量机）。这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。

在核技巧中，关键的一点就是非线性变换。这个非线性变换，也就是一种映射，称为核函数。我们先来看一下核函数的定义：

设X是输入空间（欧式空间R^{n}的子集或离散集合），又设H为特征空间（希尔伯特空间），如果存在一个从X到H的映射：

φ(x): X → H

使得，对于所有x,z∈X，函数K(x,z)满足条件：

K(x,z) = φ(x)·φ(z)

则称K(x,z)为核函数，φ(x)为映射函数，式中φ(x)·φ(z)为φ(x)和φ(z)的内积。

核技巧的想法是：在学习和预测中，之定义核函数K(x,z)，而不显式的定义映射函数φ（后面会证明，这样对计算并无影响）。通常，直接计算K(x,z)比较容易，而通过φ(x)和φ(z)计算K(x,z)并不容易。注意：φ是输入空间R^{n}到特征空间H的映射，特征空间H一般是高维的，甚至是无穷维的。

我们从核函数定义中可以看到，对于给定的核K(x,z)，特征空间H和映射函数的取法并不唯一，可以取不同的特征空间，即便是同一个特征空间里也可以取不同的映射。

在P117页例7.3中，示例计算了核函数为K(x,z)=(x·z)^2时，相关的特征空间H和映射φ不止一个。

在这个例子里，映射是作者拼凑出来的。那么，应该如何去拼凑映射φ(x)？更进一步，如何选取核函数呢？

实际上，我们之前也提到了，核技巧的想法就是：不显式的定义映射函数φ，而是使用核函数K(w,z)进行计算。为什么可以这样？因为在线性支持向量机的对偶问题中，无论是目标函数还是决策函数，都只涉及输入实例与实例之间的内积运算。因此，对偶问题的目标函数中的内积可以用核函数K(x,z) = φ(x)·φ(z)来代替。从而，无需显式的设定映射函数φ即可得到两个实例在特征空间中对应点的内积，这样，学习是隐式的在特征空间进行的，而特征空间中的内积计算可以使用原空间中的核函数K(x,z)来替代。从而，不需要显式定义或者拼凑出映射函数来即可求出结果。这样的技巧成为核技巧，它是巧妙的利用线性分类学习方法和核函数解决非线性问题的技术。

好，既然无序显式定义映射函数φ，那我们考虑下一个问题：应该如何选取核函数？

3. 核函数的选取、构建

在实际应用中，核函数的选取还没有理论指导，往往依赖领域知识直接选择核函数，核函数选择的有效性还需要通过实验验证。

那么，不用构建映射φ(x)，能否直接判断一个给定的函数K(x,z)是否是核函数呢？或者说，K(x,z)满足什么条件才能成为核函数？

书中P121页给了正定核函数（即之前所说的核函数）的充要条件：

对任意x_{i}∈X，i=1,2,…,m，K(x,z)对应的Gram矩阵：

K = [K(x_{i},y_{i})]_{m×m}

是半正定矩阵。

不过，这一定义在构造核函数时很有用，但对一个具体的函数K(x,z)进行判断是否为核函数时并不容易，因为需要对任意有限输入集{x_{1},x_{2},…,x{m}}验证K对应的Gram矩阵是否为半正定的。因此，在实际问题中，往往应用已有的核函数。那么，常用的核函数有哪些呢？

4. 常见核函数

常见核函数包括：

1 多项式核函数（polynomial kernel function）

K(x,z) = (x·z+1)^{p}

2 高斯核函数（Gaussian kernel function）

K(x,z) = exp(-\frac{||x-z||^{2}}{2σ^{2}})

3 字符串核函数（string kernel function）

略。需要时查看P123页。

4 内积的正整数幂函数

K(x,z)=(x·z)^{p}

这个是习题1.4中的证明，也是例7.3中的核函数的推广。

5. 非线性支持向量机

了解了前面的原理，最后我们给出非线性支持向量机的定义：

从非线性分类训练集，通过核函数与软间隔最大化，或凸二次优化，学习得到的分类决策函数：

f(x) = sign(∑_{i=1}^{N}α_{i}^{}y_{i}K(x,x_{i}) + b^{})

称为非线性支持向量，K(x,z)是正定核函数。

序列最小最优化算法（SMO算法）

支持向量机的学习问题可以形式化为求解凸二次规划问题。但是，当训练样本容量很大时，这些算法往往效率很低。书中给出了非线性支持向量机的一种快速实现算法，即SMO算法。内容略。

五、总结

支持向量机的模型是由简入繁的，适用的数据集从线性可分数据集到线性数据集，再到非线性数据集，适用范围逐步扩大。在前二者中，间隔最大化是最重要的思想，包括线性可分数据集的硬间隔最大化和线性数据集的软间隔最大化。非线性数据集的处理，是引入了核函数，将非线性数据映射到特征空间（希尔伯特空间H）中，从而变成线性数据集，使用前二者进行分类。在这个映射中，通过核技巧，可以无需显式的定义映射函数φ，使用核函数K(x,z)即可对特征空间的间隔最大化进行求解。对于核函数的选取，现在还没有明确的选取理论，一般需要根据领域知识进行选取。另外，上面列出了四种常见的核函数。

参考资料：

* 《统计学习方法》- 李航