写在前面

从大学就开始接触SVM，李航老师在《统计机器学习方法》中讲的很到位，下文是结合李航老师书中的内容进行的理解和整理，便于回顾和加深印象。

概述

支持向量机（SVM）是一种二类分类器，是最为广泛使用的分类器之一。其基本模型是定义在特征空间上的间隔最大化线性分类器，使用核技巧使其可以求解非线性分类问题。其学习策略是间隔最大化，可形式化为一个求解凸二次规划问题，也等价于正则化的合页损失函数的最小化问题，支持向量机的学习算法是求解凸二次规划的最优化算法。

下面将由简入繁分线性可分支持向量机、线性支持向量机、非线性支持向量机及序列最小最优化算法四部分进行详细介绍。

线性可分支持向量机

假设给定一个特征空间上的训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N))\}$，其中$x_i \in \mathcal{X}=\mathbf{R}^n, y_i \in \mathcal{Y}=\{+1,-1\}, i=1,2,...,N $，$x_i$为第i个特征向量，也称为实例，$y_i$为$x_i$的类标记。

线性可分意味着存在分离超平面（$w \cdot x+b=0$）可以将正负例完全分开。一般地，当数据集线性可分时，存在无数个分离超平面，线性可分支持向量机利用间隔最大化来求最优分离超平面。下面先介绍一下间隔。

函数间隔与几何间隔

一般来说，一个点距离分离超平面的远近可以表示分类的确信程度，在超平面$w \cdot x+b=0$确定的情况下，$|w \cdot x+b|$能够相对的表示点$x$距离超平面的远近，而$w \cdot x+b$的符号与类标记$y$的符号是否一致能够表示分类是否正确，所以可用量$y(w \cdot x+b)$来表示分类的正确性和确信度，这就是函数间隔的概念。

定义（函数间隔）：对于给定的训练数据集$T$和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x_i,y_i)$的函数间隔为:

$$\hat{\gamma_i}=y_i(w \cdot x_i+b)$$

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

$$\hat{\gamma}=\min_{i=1,...,N}{\hat{\gamma_i}}$$

但只有函数间隔还不够，只要成比例改变$w$和$b$，超平面没变，但间隔变为原来的2倍，于是启示我们可以对超平面法向量增加某些约束，如规范化$||w||=1$，此时得到的即为几何间隔。

定义（几何间隔）：对于给定的训练数据集$T$和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x_i,y_i)$的几何间隔为:

$$\gamma_i=y_i(\frac{w}{\parallel w\parallel} \cdot x_i+\frac{b}{\parallel w\parallel})$$

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

$$\gamma=\min_{i=1,...,N}{\gamma_i}$$

几何间隔可以理解为几何中点到直线的距离，即，设直线$L$的方程为$Ax+By+C=0$，点$P$坐标为$(x_i,y_i)$，则$P$到$L$的距离为$\frac{\mid Ax_i+By_i+C\mid }{\sqrt{A^2+B^2}}$。

从定义可知，看出函数间隔和几何间隔有以下关系：

$$\gamma_i=\frac{\hat{\gamma_i}}{\parallel w \parallel}$$

$$\gamma=\frac{\hat{\gamma}}{\parallel w \parallel}$$

间隔最大化

间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。具体的，最大间隔分类超平面问题可以表示为下面的约束最优化问题：

$$\max_{w,b}\;\;\gamma$$

$$s.t.\;\; y_i(\frac{w}{\parallel w\parallel} \cdot x_i+\frac{b}{\parallel w\parallel}) \geq \gamma,\;\; i=1,2,...,N$$

考虑几何间隔$\gamma$和函数间隔$\hat{\gamma}$的关系，上式可以改写为：

$$\max_{w,b}\;\;\frac{\hat{\gamma}}{\parallel w \parallel}$$

$$s.t.\;\; y_i(w \cdot x_i+b) \geq \hat{\gamma}, \;\;i=1,2,...,N$$

函数间隔$\hat{\gamma}$的取值并不影响最优化问题的解。实际上在超平面固定的情况下，函数间隔可以取任意值，同时$w,b$也会做等比例缩放。当函数间隔取$\lambda \hat{\gamma}$时，$w,b$此时的取值（超平面固定）分别为$\lambda w, \lambda b$，可以看出并不影响最优化的解。于是我们取$\hat{\gamma}=1$。则上述最优化可以改写为：

$$\max_{w,b}\;\;\frac{1}{\parallel w \parallel}$$

$$s.t.\;\; y_i(w \cdot x_i+b) \geq 1, \;\;i=1,2,...,N$$

即在相应约束条件条件$y_i(w \cdot x_i+b) \geq 1, \;\;i=1,2,...,N$下，最大化$\frac{1}{\parallel w \parallel}$的值，而$\frac{1}{\parallel w \parallel}$便是几何间隔（函数间隔为1）。

支持向量和间隔边界

在线性可分情况下，训练样本中与分类超平面最近的样本点的实例即为支持向量，也就是约束条件式等号成立的点，即$y_i(w \cdot x_i+b)-1=0$的点。

正负样本所在超平面的距离称为间隔，间隔依赖于分离超平面的法向量，等于$\frac{2}{\parallel w \parallel}$。

更直观的理解可以参加下图：

线性可分支持向量机学习算法-最大间隔法

算法：线性可分支持向量机学习算法-最大间隔法

输入训练数据集$T$，输出最大间隔分类超平面和分类决策函数。

(1) 构造并求解约束最优化问题：

$$\min_{w,b}\;\;\frac{1}{2}\parallel w \parallel^2$$

$$s.t.\;\; y_i(w \cdot x_i+b) \geq 1, \;\; i=1,2,...,N$$

求得最优解$w^{*},b^{*}$

(2) 由此得到分类超平面：

$$w^{*} \cdot x + b^{*}=0$$

分类决策函数

$$f(x)=sign(w^{*} \cdot x+b^{*})$$

注：最大化$\frac{1}{\parallel w \parallel}$和最小化$\frac{1}{2}\parallel w \parallel ^2$是等价的。

线性可分支持向量机学习的对偶算法

为了求解线性可分支持向量机的最优化问题，将他作为原始优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，这就是线性可分直线向量机的对偶算法。这样做的优点，一方面对偶问题更容易求解，另一方面自然引入核函数，进入推广到非线性分类问题。‘

首先构建拉格朗日函数，为此，对每一个不等式约束引进拉格朗日乘子$\alpha_i \geq 0, \;\; i=1,2,...,N$，定义拉格朗日函数：

$$L(w,b,\alpha)=\frac{1}{2}\parallel w \parallel ^2-\sum_{i=1}^{N}\alpha_iy_i(w_i \cdot x_i+b)+\sum_{i=1}^{N}\alpha_i$$

其中$\alpha=(\alpha_1,\alpha_2,...,\alpha_N)$为拉格朗日乘子向量。根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

$$\max_{\alpha}\min_{w,b}L(w,b,\alpha)$$

为了求对偶问题的解，需要先求$L(w,b,\alpha)$对$w,b$的极小（分别对$w,b$求偏导，并令其等于0），再求对$\alpha$的极大。求得对偶最优化问题对$\alpha$的解$\alpha^{*}$后，可由$\alpha^{*}$求得原始最优化问题对$(w,b)$的最优解$(w^{*},b^{*})$。

算法：线性可分支持向量机学习算法-对偶算法 输入训练数据集$T$，输出最大间隔分类超平面和分类决策函数。

(1) 构造并求解约束最优化问题：

$$\min\_{\alpha}\;\;\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^{N}\alpha_i$$

$$s.t. \;\; \sum_{i=1}^{N}\alpha_iy_i=0, \; \alpha_i \geq 0, \;\; i=1,2,...,N$$

求得最优解$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},...,\alpha_N^{*})$。

(2) 计算

$$w^{*}=\sum_{i=1}^{N}\alpha_i^{*}y_ix_i$$

并选择$\alpha^{*}$的一个正分量$\alpha_j^{*} > 0$ 计算

$$b^{*}=y_i-\sum_{i=1}^{N}\alpha_i^{*}y_i(x_i \cdot x_j)$$

(3) 求得分类超平面

$$w^{*} \cdot x +b^{*}=0$$

分类决策函数：

$$f(x)=sign(w^{*} \cdot x+b^{*})$$

对偶问题的支持向量

由对偶问题算法可知，$w^{*}$和$b^{*}$只依赖于训练数据中$\alpha_i^{*} > 0$的样本点$(x_i,y_i)$，而其他样本点没有影响，将训练数据中对应$\alpha_i^{*} > 0$的实例点称为支持向量。

线性支持向量机

当训练数据不是线性可分的时候（通常情况是训练数据有一些特异点，去除后剩下大部分样本点组成的集合是线性可分的），就要使用软间隔最大化来代替线性可分情况下的硬间隔最大化。解决方法对每一个样本点引入一个松弛变量$\xi_i \geq 0$，使函数间隔加上松弛变量大约等于1，同时对每一个松弛变量，支付一个代价$\xi_i$，则线性不可分的线性支持向量机学习问题变为了如下最优化问题：

$$\min_{w,b,\xi}\;\;\frac{1}{2}\parallel w \parallel^2 + C\sum_{i=1}^{N}\xi_i$$

\begin{equation} \begin{split} s.t.\;\; y_i(w \cdot x_i+b) & \geq 1 - \xi_i, \;\; i=1,2,...,N \\ \xi_i & \geq 0, \;\; i=1,2,...,N \end{split} \end{equation}

线性支持向量机学习算法

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

输入训练数据集$T$，输出最大间隔分类超平面和分类决策函数。

(1) 选择惩罚系数$C > 0$，构造并求解凸二次规划问题：

$$\min\_{\alpha}\;\;\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^{N}\alpha_i$$

$$s.t. \;\; \sum_{i=1}^{N}\alpha_iy_i=0, \; 0 \leq \alpha_i \leq C, \;\; i=1,2,...,N$$

求得最优解$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},...,\alpha_N^{*})$。

(2) 计算

$$w^{*}=\sum_{i=1}^{N}\alpha_i^{*}y_ix_i$$

并选择$\alpha^{*}$的一个正分量$0 < \alpha_j^{*} < C$ 计算

$$b^{*}=y_i-\sum_{i=1}^{N}\alpha_i^{*}y_i(x_i \cdot x_j)$$

(3) 求得分类超平面

$$w^{*} \cdot x +b^{*}=0$$

分类决策函数：

$$f(x)=sign(w^{*} \cdot x+b^{*})$$

对任意适合条件$0 < \alpha_j^{*} < C$的$\alpha_j*{*}$都可以求出$b^{*}$，但由于原始问题对$b$的解并不唯一，所以实际计算时可以去所有符合条件的样本点上的平均值。

支持向量和软间隔

在线性不可分的情况下，将对偶问题的解$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},...,\alpha_N^{*})$中对应于$\alpha_i^{*} > 0$的样本点$(x_i,y_i)$的实例称为支持向量（软间隔的支持向量）。如下图所示，这种情况下的支持向量比线性可分要复杂一些，可能在间隔边界（图中虚线），可能在分类超平面（图中实线）与间隔边界之间，也可能在分类超平面误分一侧。

图中图示了四个实例$x_i, \;i=1,2,3,4$到间隔边界的距离$\frac{\xi_i}{\parallel w \parallel}$。若$\alpha_i^{*} < C$，则$\xi_i = 0$ (可由参考文献[1] P111 7.53 7.54得出)，此时支持向量恰好在间隔边界上；若$\alpha_i^{*} = C， 0 < \xi_i < 1$，则分类正确，支持向量$x_i$落在间隔边界和分类超平面之间；若$\alpha_i^{*} = C， \xi_i = 1$, 则落在分离超平面上；若若$\alpha_i^{*} = C， \xi_i > 1$，则$x_i$位于分类超平面误分一侧。

非线性支持向量机

当分类问题是非线性的时候，支持向量机可以通过利用核技巧来将非线性的问题转换为线性的问题进行求解。下面首先介绍核技巧。

核技巧

下图是一个简单的示例，可以看出，通过将原空间$\mathcal{X} \subset \mathbf{R}^2, \; x=(x^{(1)},x^{(2)})^T \in \mathcal{X} $映射到新空间$\mathcal{Z} \subset mathbf{R}^2, \; z=(z^{(1)}, z^{(2)}) \in \mathcal{Z}$ （映射函数为$z=\phi(x)=(((x^{(1)})^2,(x^{(2)})^2)^T$），非线性分类的问题可以转换为线性分类的问题，从而通过在新空间使用线性分类学习方法从训练数据中学习分类模型来做到非线性问题的分类。核技巧就是这样的方法。

定义（核函数）:设$\mathcal{X}$是输入空间（欧式空间$\mathbf{R}^{n}的子集或者离散集合$），又设$\mathcal{H}$为特征空间（希尔伯特空间），如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射

$$\phi(x):\mathcal{X}\rightarrow \mathcal{H}$$

使得对于所有的$x,z \in \mathcal{X}$，函数$K(x,z)$满足

$$K(x,z)=\phi(x) \cdot \phi(z)$$

则称$K(x,z)$为核函数，$\phi(x)$为映射函数，式中$\phi(x) \cdot \phi(z)$为$\phi(x)$和$\phi(z)$的内积。

我们注意到，在线性支持向量机的对偶问题中，无论是目标函数还是决策函数都只涉及输入实例和实例之间的内积。在对偶问题中我们用核函数$K(x,z)=\phi(x_i) \cdot \phi(x_j)$来代替$x_i \cdot x_j$，通过这种核技巧，来使用支持向量机解决非线性分类的问题。

可以通过判断一个函数$K(x,z)$是不是正定核函数来判断其是不是核函数，这里不再详细阐述，可以参考文献[1]中P118页7.3.2小节。常用的核函数有多项式核函数、高斯核函数和字符串核函数。

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

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

输入训练数据集$T$，输出分类决策函数。

(1) 选择适当的核函数$K(x,z)$和惩罚系数$C > 0$，构造并求解最优化问题：

$$\min\_{\alpha}\;\;\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum_{i=1}^{N}\alpha_i$$

$$s.t. \;\; \sum_{i=1}^{N}\alpha_iy_i=0, \; 0 \leq \alpha_i \leq C, \;\; i=1,2,...,N$$

求得最优解$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},...,\alpha_N^{*})$。

(2) 选择$\alpha^{*}$的一个正分量$0 < \alpha_j^{*} < C$ 计算

$$b^{*}=y_i-\sum_{i=1}^{N}\alpha_i^{*}y_iK(x_i \cdot x_j)$$

(3) 求得分类决策函数：

$$f(x)=sign(\sum_{i=1}^{N}\alpha_i^{*}y_iK(x \cdot x_i)+b^{*})$$

当$K(x,z)$是正定核函数时，上述最优化问题是凸二次规划问题，解释存在的。

序列最小最优化算法

序列最小最优化算法（SMO）是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT的条件为止。参考文献[1]中P124，7.4节已经讲的很清楚，想详细了解的可以进行扩展推导阅读。

小结

文章大部分参考了文献[1]，针对SVM进行了一个简要明了的整理，展现了支持向量机的主干，想要了解推导更为细节的枝叶可自行根据以下参考文献进行阅读。

参考文献

[1] 统计学习方法.李航

[2] 支持向量机通俗导论

[3] 拉格朗日对偶性