《统计学习方法》——第七章 支持向量机

前言

本文只要记录一些书中的一些小知识点，挑一些本人认为重要的地方进行总结。

各位道友！道长(zhǎng) 道长(chǎng)

一、支持向量机SVM

SVM在机器学习领域的在神经网络真正流行起来之前，支持向量机这种分类器还是很火热的。

• 支持向量机是一个种二分类模型。
• 他的模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使他有别于感知机。
• 他还包含核技巧，这可以让他成为非线性分类器。
• 学习策略是间隔最大化
• 学习算法是求解凸二次规划规划的问题
• 模型：线性可分支持向量机，线性支持向量机，非线性支持向量机
• 核函数：表示将输入从输出空间映射到特征空间得到的特征向量之间的内积。

二、线性可分支持向量机

2.1定义

给定线性可分的训练数据集，通过间隔最大化或等价的求解相应的凸二次规划问题学习得到的分离超平面为
$$w^{\ast }\cdot x+b^{\ast }=0$$
相应的决策函数为
$$f(x)=sign(w^{\ast }\cdot x+b^{\ast })$$
称为线性可分支持向量机

2.2函数间隔

图中每个点都是$(x,y)$,$x$代表输入实例，$y$代表类标记。
‘x’代表负例，‘o’代表正例。假设中间的实线是将两类数据正确划分且间隔最大的直线。

举例说，图上有A、B、C三个点，A距离超平面最远且在正例的一边，表示他是正类的更加确信些，C距离超平面更近，表示正类的预测没那么可信。

在超平面$w\cdot x+b=0$确定，
$|w\cdot x+b|$表示点距离超平面的远近，
类标记$y$和$w\cdot x+b$的符号表示是否分类正确。

函数间隔：
对于给定数据集T和超平面$(w,b)$，定义超平面关于样本点$(x,y)$的函数间隔为
$${\hat{\gamma }}_i=y(w\cdot x+b)$$
定义超平面关于数据集T的函数间隔为超平面关于T中所有样本点$(x,y)$的函数间隔的最小值
$$\hat{\gamma }=\underset{i=1,\mathrm{2...}N}{\min }{\gamma }_i$$

2.3几何间隔

对于给定数据集T和超平面$(w,b)$，定义超平面关于样本点$(x,y)$的几何间隔为
$${\gamma }_i=y(\frac{w}{||w||}\cdot x+\frac{b}{||w||})$$
定义超平面关于数据集T的几何间隔为超平面关于T中所有样本点$(x,y)$的几何间隔的最小值
$$\hat{\gamma }=\underset{i=1,\mathrm{2...}N}{\min }{\gamma }_i$$

2.4间隔最大化

1.最大间隔分离超平面

即求解下面这个约束最优化问题

即几何间隔至少是$\gamma$

• 也可改成函数间隔的形式

由于函数间隔不影响最优化问题的解（函数间隔是相对的，如果吧w和b都放大若干倍，函数间隔也会放大若干倍，所以没有影响）。

所以这个问题可以再变～（最小化$\frac{1}{||w||}$和最大化$\frac{1}{2}||w|{|}^2$等价，这样做是为了方便求导计算）

这样就变成了一个凸二次规划问题

凸二次规划问题形式

即一个目标函数f(x),不等式约束g(x),等式约束h(x)

2.最大间隔法

输入：$T=(...(x_i,y_i)...)$
输出：最大间隔分离超平面和分类决策函数
（1）构造并求解约束最优化问题：
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}||w|{|}^2 \\ s.t.y_i(w\cdot x_i+b)-1\ge 0,i=1,2,...,N \end{gathered}$$
求得最优解$w^{\ast }$和$b^{\ast }$
（2）由此得到分离超平面
$$w^{\ast }\cdot x+b^{\ast }=0$$
分类决策函数为
$$f(x)=sign(w^{\ast }\cdot x+b^{\ast })$$

3.间隔最大化的分离超平面是唯一的

4.支持向量和间隔边界

支持向量： 线性可分情况下，训练数据集的样本点中，与分离超平面距离最近的样本点的实例称为支持向量（图中$H_1$和$H_2$上的点就是支持向量）

间隔边界： $H_1$和$H_2$称为间隔边界。$H_1$和$H_2$之间的距离称为间隔，它依赖于超平面的法向量$w$,等于$\frac{2}{||w||}$

决定分离超平面时只有支持向量起作用，且是决定性作用

5.学习的对偶算法

为了求解线性可分支持向量机的最优化问题，如下图，将它作为原始最优化问题。应用拉格朗日对偶法，通过求解对偶问题得到原始问题的最优解，这就是线性可分支持向量机的对偶算法。

使用对偶算法的优点是：1.更容易求解 2.自然引入核函数，进而推广到非线性分类问题。

话不多说，先上干活。

首先构造拉格朗日函数，引入拉格朗日乘子${\alpha }_i\ge 0$,定义拉格朗日函数
$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _{i=1}^N{\alpha }_i{y}_i(w\cdot x_i+b)+\sum _{i=1}^N{\alpha }_i$$

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
$$ma{x}_{\alpha }mi{n}_{w,b}L(w,b,\alpha )$$
故为了求解，我们需要先对w,b求极小，再对$\alpha$求极大。

5.1求$mi{n}_{w,b}L(w,b,\alpha )$

对$L(w,b,\alpha )$分别对w，b求偏导数并令其等于0。得：
$$\begin{gathered} w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i \\ \sum _{i=1}^N{\alpha }_i{y}_i=0 \end{gathered}$$
将这两个式子带入$L(w,b,\alpha )$中，得到

整理得：
$$mi{n}_{w,b}L(w,b,\alpha )=-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^N{\alpha }_i$$

5.2求$ma{x}_{\alpha }mi{n}_{w,b}L(w,b,\alpha )$对$\alpha$的极大

即构造出了对偶问题

将上式由求极大转为求极小，得

解这个优化问题，得出${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_l^{\ast }{)}^T$

有了${\alpha }^{\ast }$，w和b也求出来了:
$$\begin{gathered} w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i \\ {b}^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j) \end{gathered}$$

由此，超平面可以写成
$$\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\cdot x_i)+b^{\ast }=0$$
分类决策函数可以写成
$$f(x)=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\cdot x_i)+b^{\ast })$$
也就是说，分类决策函数只依赖于输入$x$和训练样本输入的内积。上式$f(x)$称为线性可分支持向量机的对偶形式。

2.5.线性可分支持向量机学习算法

s

三、线性支持向量机与软间隔最大化

3.1线性支持向量机

线性可分支持向量机学习方法，对于线性不可分训练数据是不适用的，因为这是上述方法的不等式约束不能成立。

线性不可分意味着某些样本点$(x_i,y_i)$不满足函数间隔大于等于1的约束条件。如果将这些特异点去掉之后，剩下的大部分样本点是线性可分的。
于是可以引进一个松弛变量$\xi \ge 0$,使得函数间隔加上这个松弛变量大于等于1。这样约束条件就变成了
$$y_i(w\cdot x_i+b)\ge 1-{\xi }_i$$
对于每一个${\xi }_i$，都支付一个代价${\xi }_i$,目标函数就变成了
$$\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i$$
这里$C>0$是惩罚参数，C大的时候，对于误分类的惩罚增大，C小的时候对误分类的惩罚小。
上式包含两层含义，$\frac{1}{2}||w|{|}^2$尽量小(间隔尽量大)，同时使误分类点的个数尽量小。（C是调和两者的系数）

有了求线性可分支持向量机的经验，我们很容易得出线性不可分的线性支持向量机的学习问题。（原始问题）

3.2学习的对偶算法

对上面的原始问题构造拉格朗日函数：

对拉格朗日函数求极大极小问题。先对$w,b,\xi$求极小（求偏导并令其等于0）得：

带入拉格朗日函数$L(w,b,\xi ,\alpha ,\mu )$中

在对$\alpha$求极大。

最终得出对偶问题：

3.3定理

对偶问题的解是${\alpha }^{\ast }$，如果存在${\alpha }^{\ast }$的一个分量${\alpha }_j^{\ast }$使得$0<{\alpha }_j^{\ast }<C$,那么原始问题的解$w^{\ast },b^{\ast }$的解为
$$\begin{gathered} w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i \\ {b}^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j) \end{gathered}$$

看到这里会不会有一个问题呢？那就是这个求出来的w和b的解和线性可分支持向量机的解不是一样的么？
如果有这个问题，就说嘛要细心了，两种情况中，虽然形式一样，但是其中的${\alpha }^{\ast }$的值是不一样的。因为线性不可分的情况中，多了一个松弛变量$\xi$嘛！

3.4线性支持向量机学习算法

注意，步骤(2)中求出的b可能不唯一，因为是对于任意适合$0<{\alpha }_j^{\ast }<C$求出来的$b^{\ast }$。但在实际应用中，往往只会出现算法叙述的情况。

四、非线性支持向量机与核函数

4.1核技巧

1.非线性分类问题

如图，左图是非线性分类问题，我们无法找到一条直线将正例负例分割开来，但是可以用一条椭圆曲线分开他们。
怎么办呢？
我们可以采取一种非线性变换的方法，把非线性问题变换成线性问题，如右图所示，把左图中的椭圆变换成了右图中的直线，非线性问题就变成了线性分类问题了。

为此我们继续进行分析。设原空间是$x=(x^{(1)},x^{(2)}{)}^T$,设新空间是$z=(z^{(1)},z^{(2)}{)}^T$。原空间到新空间的映射是
$$z=\varphi (x)=((x^{(1)}{)}^2,(x^{(2)}{)}^2{)}^T$$
这样，原空间就变成了新空间。

上面的例子说明，使用线性分类方法求解非线性分类问题分为两步：1.使用一个变换将原空间的数据映射到新空间2.在新空间用线性分类学习方法从训练数据中学习分类模型

核技巧就属于这样的方法。核技巧的想法就是通过非线性变换将输入空间对应于一个特征空间（希尔伯特空间），使得在输入空间中的超曲面模型对应于特征空间中的超平面模型。

2.核函数定义

设输入空间$X$是欧氏空间或离散集合，新空间$H$是特征空间（希尔伯特空间，一般维度更高），如果存在一个输入空间到特征空间的一个映射:
$$\varphi (x)=X\to H$$
使得所有的$x,z\in X$,函数$K(x,z)$满足
$$K(x,z)=\varphi (x)\cdot \varphi (z)$$
则称$K(x,z)$为核函数，$\varphi (x)$为映射函数。

核技巧的想法是，学习与预测中，只定义核函数$K(x,z)$，不显式定义映射函数。因为直接计算核函数是比较容易的，但是通过映射函数的内积计算核函数是比较困难的。

3.核技巧在支持向量机中的应用

我们注意到线性支持向量机的对偶问题中，无论目标函数还是决策函数，都只涉及了输入实例与实例之间的内积$x_i\cdot x_j$，使用核技巧的情况下，可以使用核函数$K(x,z)$代替这个内积。
于是对偶问题的目标函数就成为了：

分类决策函数变成了

这等价于经过映射函数将原来的输入空间变换到了一个新的特征空间，将输入空间的内积$x_i\cdot x_j$变成了新的特征空间中的内积$K(x,z)=\varphi (x)\cdot \varphi (z)$，在新的特征空间里从训练样本中学习线性支持向量机。

学习是隐式的在特征空间中进行的，不需要显式的定义特征空间和映射函数。这种技巧成为核技巧。实际应用中，往往依赖领域知识直接选择和函数，核函数选择的有效性需要通过实验验证。

4.2正定核

已知可以通过$\varphi (x)\cdot \varphi (z)$求的核函数。那么不用构造映射$\varphi (x)$能否直接判断一个给定的核函数$K(x,z)$是不是核函数呢？

正定核的充要条件

我们所说的核函数，就是正定核函数。

$K(x,z)$为正定核的充要条件是对于任意的$x_i$，$K(x,z)$对应的Gram矩阵是半正定矩阵

• Gram矩阵是描述内积的矩阵，他的形式如下（其中$({\alpha }_i,{\alpha }_j)表示向量内积$）
  

4.3常用核函数

1.多项式核函数

$$K(x,z)=(x\cdot z+1{)}^p$$

对应的支持向量机是一个p次多项式分类器。对应的决策函数为
$$f(x)=sign(\sum _{i=1}^{N_s}{a}_i^{\ast }{y}_i(x_i\cdot x+1{)}^p+b^{\ast })$$

2.高斯核函数

$$K(x,z)=\exp (-\frac{||x-z|{|}^2}{2{\sigma }^2})$$
对应的支持向量机是高斯径向核函数分类器。对应的决策函数为：
$$f(x)=sign(\sum _{i=1}^{N_s}{a}_i^{\ast }{y}_i\exp (-\frac{||x-z|{|}^2}{2{\sigma }^2})+b^{\ast })$$

3.字符串核函数

$$k_n(s,t)=\sum _{u\in {\sum }^n}\sum _{(i,j):s(i)=t(j)=u}{\lambda }^{l(i)}{\lambda }^{l(j)}$$

• s,t为字符串，$\lambda$是衰减系数，$l(i)$表示字符串i的长度，${\sum }^n$表示长度为n的字符串集合。

4.4非线性支持向量机及其学习算法

1.非线性支持向量机

$$f(x)=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K(x,x_i)+b^{\ast })$$
称为非线性支持向量机。

2.非线性支持向量机学习算法

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

当样本容量很大的时候，上述算法很低效。所以序列最小最优化(SMO)算法就是快速实现的算法之一。
SMO要求解如下凸二次规划的对偶问题。

SMO是一个启发式算法。思路是：如果所有变了都满足此最优化问题的KKT条件，那么解就满足了。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件而自动确定。这样，SMO算法就可以将原问题不断的分解为子问题，并对子问题求解，从而达到求解原问题的目的。
假设${\alpha }_1,{\alpha }_2$是变量，其余的${\alpha }_i$固定。那么由等式约束可知：
$${\alpha }_1=-y_1\sum _{i=2}^N{\alpha }_i{y}_i$$

• 这里$y_1$实际是$\frac{1}{y_1}$，因为y的取值是1和-1.所以倒数和他本身相同。

算法如下：

-SMO的特点是不断的把原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行求解。直到所有的变量都满足KKT条件为止。虽然这样会分解出很多子问题，但是每个子问题都很快，总体上还是很高效的。

总结

通过本文的介绍，相信您已经对支持向量机有了初步的了解和认识。然而，要想真正掌握SVM并灵活运用它解决实际问题，还需要进一步的学习和实践。建议您阅读相关的教材、论文和博客文章，深入了解SVM的原理、算法和优化方法。
加油！！