支持向量机 - 小涛的博客|Wuwt-blog

1.什么是支持向量SVM

要明白什么是SVM，便得从分类说起。

分类作为数据挖掘领域中一项非常重要的任务，它的目的是学会一个分类函数或是分类模型(或者叫做分类器)，而支持向量机本身便是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。

支持向量机是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好的统计规律的目的。

通俗来讲，它是一种二分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

2.线性分类的一个例子

下面举个简单的例子，一个二维平面（一个超平面，在二维空间中的例子就是一条直线），如下图所示，平面上有两种不同的点，分别用两种不同的颜色表示，一种为红颜色的点，另一种则为蓝颜色的点，蓝颜色的线表示一个可行的超平面。

从上图中我们可以看出，这条蓝颜色的线把红颜色的点和蓝颜色的点分开来了。而这条蓝颜色的线就是我们上面说的超平面，也就是说，这个所谓的超平面的的确确便把这两种不同颜色的数据点分隔开来，在超平面一边的数据点所对应的y全是-1，而在另外一边全是1.

接着，我们可以令分类函数

$f(x)=w^Tx+b$ (1)

显然，如果$f(x)=0$,那么x是位于超平面上的点。我们不妨要求对于所有满足$f(x)<0$的点，其对应的y等于-1，而$f(x)>0$则对应$y=1$的数据点,如下图所示。

在进行分类的时候，遇到一个新的数据点x，将x代入f(x)中，如果f(x)小于0则将x的类别赋为-1，如果f(x)大于0则将x的类别赋为1。

$\begin {cases} w^Tx_i+b \geq+1, y_i=+1 \\ w^Tx_i+b \leq-1. y_i=-1\end {cases} 式（1）$

接下来的问题是，是如何确定这个超平面呢？从直观上而言，这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着最大间隔的超平面。如上图所示，距离超平面最近的这几个训练样本点使图中公式(1)的等号成立，它们被称为“支持向量”，两个异类支持向量到超平面的距离之和为

$\gamma= \frac{2}{ \mid\omega \mid}$

它被称为“间隔”。

欲找到具有“最大间隔”的划分超平面，也就是要找到能满足式(1)中约束的参数$w$和$b$，使得$γ$最大。即

$max_{\omega,x} \frac{2}{\mid \omega \mid} \quad式(2)\\ s.t. y_i(w^Tx_i+b) \geq1,i=1,2,···m$

显然，为了最大化间隔，仅需最大化$ \mid \omega \mid^{-1}$，这等价于最小化$ \mid \omega \mid^2$.于是式(2)可重写为

$min_{\omega,x} \frac{1}{2} \mid \omega \mid ^2 \quad式(3)\\ s.t. y_i(w^Tx_i+b) \geq1,i=1,2,···m$

这就是支持向量机的基本型。

3.对偶问题

我们希望求解式(3)来得到最大间隔划分超平面所对应的模型。

$f(x)=w^Tx+b$

其中$ \omega$和$b$是模型参数。上述问题转换成式(3)这个形式后，我们的问题变成了一个凸优化问题，或者更具体的说，因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题，这个问题可以用任何现成的QP的优化包进行求解，归结为一句话就是：在一定的约束条件下，目标最优，损失最小。虽然这个问题确实一个标准的QP问题，但是它有它的特殊结构，通过拉格朗日对偶变换到对偶变量的优化问题之后，可以找到一种更加有效的方法来求解，而且通常情况下这种方法比直接使用通用的QP优化包进行优化要高效得多。

也就说，除了用解决QP问题的常规方法之外，还可以通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。

上述提到，关于什么是“拉格朗日对偶”？简单的来说，通过每一个约束条件加上一个“拉格朗日乘值”，即引入拉格朗日乘子$ \alpha$,如此我们便可以通过拉格朗日函数将约束条件融和到目标函数里去(也就是说把条件融合到一个函数里头，现在只用一个函数表达式便能清楚地表达出我们的问题)：

\[L(ω,b,α)=\frac{1}{2}\mid ω \mid^2+\sum^m_{i=1}\alpha(1-y_i(ω^Tx_i+b)) \quad 式(4)\]

其中，$ \alpha=(α_1,\alpha_2,···\alpha_m)$.令$L(ω,b,α)$对$\omega$和$b$的偏导为零可得

$\omega=\sum^m_{i=1}\alpha_iy_ix_i \quad式(5)$

$0=\sum^m_{i=1}\alpha_iy_i \quad 式(6)$

将式(5)代入式(4)，即可将$L(ω,b,α)$中的$ \omega$和$b$消去，在考虑式(6)的约束，就得到式(3)的对偶问题

\[\mathop{max}\limits_\alpha \sum^m_{i=1}\alpha_i-\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_iy_jx^T_ix_j \quad式(7)\] \[s.t \sum^m_{i=1}α_iy_i=0,\quad α_i\geq0,i=1,2···,m\]

解出$ \alpha$后，求出$ \omega$和$b$即可得到模型

$\begin{align}f(x)&=ω^Tx+b\\ &=\sum^m_{i=1}α_iy_ix_i^Tx+b\quad式(8) \end{align}$

从对偶问题式(7)解出的$ \alpha_i$式(4)中额拉格朗日乘子，它恰对应着训练样本$(x_i,y_i)$，注意式(3)中有不等式约束，因此上述过程需满足KTT(Karush-Kuhn-Tucker)条件，即要求

\[α_i\geq0; \\y_if(x_i)-1\geq0\quad 式(9)\\ α_i(y_if(x_i)-1)=0\]

于是，对任意训练样本$ (x_i,y_i)$，总有$ \alpha_i=0或y_if(x_i)=1$.若$\alpha_i=0$，则这样本将不会出现式(8)的求和中出现，也就不会对$f(x)$有任何影响;若$\alpha_i\gt 0$,则必有$y_if(x_i)=1$，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。

那么，如何求解式(7)呢？不难发现，这是一个二次规划问题，可使用通用的二次规划算法来求解；然而，该问题的规模正比于训练样本，这会在实际任务中造成很大的开销。为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高效算法，SMO(序列最小最优化)是其中一个著名代表。

SMO的基本思路是先固定$\alpha_i$之外的所有参数，然后求$α_i$上的极值。由于存在约束$ \sum^m_{i=1}α_iy_i=0$，若固定$α_i$之外的其他变量，则$α_i$可由其他变量导出，于是，SMO每次选择两个变量$ \alpha_i$和$\alpha_j$，并固定其他参数，这样，在参数初始化后，SMO不断执行如下两个步骤直至收敛：

选取一对需要更新的变量$ \alpha_i和\alpha_j$;
固定$ \alpha_i和\alpha_j$以外的参数，求解式(7)获得更新后的$\alpha_i和\alpha_j$.

注意到只需选取的$ \alpha_i和\alpha_j$中有一个不满足KKT条件式(9)，目标函数就会在迭代后减小。直观来看，KKT条件违背的程度越大，则变量更新后可能导致的目标函数值减幅越大。于是。SMO先选取违背了KKT条件程度最大的变量。第二个变量应该选择一个使目标函数值减小最快的变量，但由于比较各变量所对应的目标函数值减幅的复杂度过高，因此SMO采用了一个启发式：使选取的两变量所对应样本之间的间隔最大。一种直观解释是，这样的两个变量有很大差别，与对两个相似的变量进行更新相比，对它们进行更新会带给目标函数值更大的变化。

SMO算法之所以高效，恰由于在固定其他参数后，仅优化两个参数的过程能做到非常高效。具体来说，仅考虑$ \alpha_i和\alpha_j$时，式(7)中约束可重写为

\[\alpha_iy_i+\alpha_jy_j$=c,\alpha_i\geq0,\alpha_j\geq0 \quad 式(10)\]

其中

\[c=-\sum_{k≠i,j}\alpha_ky_k \quad 式(11)\]

是使$ \sum^m_{i=1}\alpha_iy_i=0$成立的常数。用

\[\alpha_iy_i+\alpha_jy_j=c\quad 式(12)\]

消去式(7)中的变量$α_j$,则得到一个关于$\alpha_i$的单变量二次规划问题，仅有的约束$ \alpha_i\geq0$.不难发现，这样的二次规划问题具有闭式解，于是不必调用数值优化算法即可高效地计算出更新后的$\alpha_i和\alpha_j$。

如何确定偏移项b呢？注意到对任意支持向量$(x_s,y_s)$都有$y_sf(x_s)=1$,即

$y_s\big(\sum_{i∈S}\alpha_iy_ix^T_ix_s+b\big)=1\quad 式(13)$

其中$ S={i\mid\alpha_i＞0,i=1,2····m}$为所有支持向量的下标集。理论上，可选任意支持向量并通过式(13)获得b，但现实任务中常采用一种更健壮的做法，使所有支持向量求解的平均值

\[b=\frac{1}{\mid S\mid}\sum_{s∈S}\big(y_s-\sum_{i∈S}\alpha_iy_ix^T_is_s\big) \quad式(14)\]

4.核函数

在上文中，我们假设训练样本是线性可分的，即存在一个可划分超平面能将训练样本正确分类。然而现实任务中，原始样本空间也许并不存在一个能正确划分两类样本的超平面。例如下图中的“异或”问题就不是线性可分的。

对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。若将原始的二维空间映射到一个合适的三维空间，就能找到一个合适的划分超平面。幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。

令$Φ(x)$表示将x映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为

\[f(x)=w^TΦ(x)+b,\quad (式15)\]

其中$ \omega和b$是模型参数。类似式(3),有

$min_{\omega,x} \frac{1}{2} \mid \omega \mid ^2 \quad式(16)\\ s.t. y_i(w^TΦ(x_i)+b) \geq1,i=1,2,···m$

其对偶问题

\[\mathop{max}\limits_\alpha \sum^m_{i=1}\alpha_i-\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_iy_jΦ(x_i)^TΦ(x_j) \quad式(17)\] \[s.t \sum^m_{i=1}α_iy_i=0,\quad α_i\geq0,i=1,2···,m\]

求解式(17)涉及到计算$ Φ(x_i)^TΦ(x_j)$,这是样本$x_i和x_j$映射到特征空间之后的内积。由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算$Φ(x_i)^TΦ(x_j)$通常是困难的。为了避开这个障碍，可以设想这样一个函数：

\[κ(x_i,x_j)=\langleΦ(x_i),Φ(x_j)\rangle=Φ(x_i)^TΦ(x_j)\quad 式(18)\]

即$x_i和x_j$在特征空间的内积等于它们在原始样本空间中通过函数$κ(·，·)$计算的结果。有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中的内积，于是式(17)可重写为

\[\mathop{max}\limits_\alpha \sum^m_{i=1}\alpha_i-\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_iy_jκ(x_i,x_j) \quad式(19)\] \[s.t \sum^m_{i=1}α_iy_i=0,\quad α_i\geq0,i=1,2···,m\]

求解后即可得到

\[\begin{align} f(x)&=\omega^TΦ(x)+b\\&=\sum_{i=1}^m α_iy_iΦ(x_i)^TΦ(x_j)+b\\ &=\sum_{i=1}^mα_iy_iκ(x,x_i)+b\end{align}\quad 式(20)\]

这里的函数$κ(·,·)$就是核函数。式(20)显示出模型最优解可通过训练样本的核函数展开，这一展式亦称“支持向量展式”.

核函数的价值在于它虽然也是将特征从低维到高维的转换,但核函数事实上在低维上进行计算,而将实质上的分类效果表现在了高维,避免了直接在高维空间中的复杂计算.

只要一个对称函数所对应的核矩阵半正定,它就能作为核函数使用.事实上,对于一个半正定核矩阵,总能找到一个与之对于的映射$ Φ$.换言之，任何一个核函数都隐式的定义了一个称谓“再生核希尔伯特空间”的特征空间。

通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需要注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，而核函数也仅是隐式的定义了这个特征空间。于是“核函数选择”成为支持向量机的最大变数。若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。下表列出了几种常用的核函数

名称	表达式	参数
线性核	$κ(x_i,x_j)=x^T_ix_j$
多项式核	$ κ(x_i,x_j)=(x^T_i.x_j)^d	$d\geq1$为多项式的次数
高斯核(又称RBF核)	$ κ(x_i,x_j)=exp \big(\frac{\mid x_i-x_j \mid^2}{2δ^2}\big)$	$ δ＞ 0$为高斯核的带宽
拉普拉斯核	$ κ(x_i,x_j)=exp \big(\frac{\mid x_i-x_j \mid}{δ}\big)$	$δ＞ 0$
Sigmoid核	$κ(x_i,x_j)=tanh(βx^T_ix_j+Θ)$	tanh为双曲正切函数，$ β＞0,Θ＜0$

此外，还可以通过函数组合得到，例如：

若$κ_1和k_2$为核函数，则对于任意正数$γ_1,γ_2$,其线性组合

$γ_1κ_1+γ_2κ_2$也是核函数；
若$κ_1和k_2$为核函数，则核函数的直积

$k_1\otimes k_2(\boldsymbol{x},\boldsymbol{z})=k_1(\boldsymbol{x},\boldsymbol{z})k_2(\boldsymbol{x},\boldsymbol{z})$也是核函数
若$ κ_1$为核函数，则对于任意函数$ g(x)$，

$k(x,z)=g(x)κ_1(x,z)g(z)$也是核函数

5.软间隔与正则化

在前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分，数据有噪音，对于偏离正常位置很远的数据点，我们称之为outliner.退一步说，即便找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。

缓解这个问题的一个办法是允许支持向量机在一些样本上出错。为此，要引入“软间隔”的概念。如下图所示。