支持向量机（SVM）基本原理详解

1.线性可分情况

SVM方法是从线性可分情况下的最优分类面（Optimal Hyperplane）发展而来的。所谓最优分类面就是要求分类线不但能将两类样本无错误地分开，而且要使两类之间的距离最大。图7-2所示的两维情况可以说明其基本思想。图中实心点和空心点代表两类样本，H为分类线，H₁、H₂分别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔（Margin）。所谓最优分类线就是要求分类线不但能将两类正确分开（训练错误率为0），而且使分类间隔最大。

图7-2 线性可分情况下的最优分类线

设线性可分样本集为（x_i，y_i），i=1，…，n，x∈R^d，y∈{+1，-1}是类别标号。d维空间中线性判别函数的一般形式为：g（x）=w·x+b，分类面方程为

w·x+b=0 （7-33）

式中，·是向量点积。当w·x+b≥0，y_i=+1，当w·x+b＜0，y_i=-1。将判别函数进行归一化，使两类所有样本都满足|g（x）|≥1，即使离分类面最近的样本的|g（x）|=1，这样分类间隔就等于2||w||，因此间隔最大等价于使||w||（或||w||²）最小；而要求分类线对所有样本正确分类，就是要求其满足

y_i[（w·x_i）+b]-1≥0 i=1，…，n （7-34）

因此，满足上述条件且使||w||²最小的分类面就是最优分类面。这两类样本中离分类面最近的点且平行于最优分类面的超平面上的训练样本，也就是使式（7-34）中等号成立的那些样本，叫做支持向量（Support Vector）。

使分类间隔最大，实际上就是对推广能力的控制，这是SVM的核心思想之一。统计学习理论指出，在N维空间中，设样本分布在一个半径为R的超球范围内，则满足条件||w||≤A的正则超平面构成的指示函数集f（x，w，b）=sgn{（w·x）+b}（sgn（）为符号函数）的VC维满足下面的界：

h≤min（[R²A²]，N）+1 （7-35）

因此使||w||²最小就是使VC维的上界最小，从而实现结构风险最小化（SRM）准则中对函数复杂性的选择。

根据上面的讨论，最优分类面问题可以表示成如下的约束优化问题，即在式（7-34）的约束下，求函数

的最小值。这是一个典型的二次规划问题，可由拉格朗日乘子法求解。引入拉格朗日乘子α_i＞0；i=1，2，…，n，得

求式（7-36）的极小值就是对w和b求拉普拉斯函数的极小值。可取L对w和b的最小值为w^*和b^*，及对α的最大值为α^*。求L对w和b的偏微分，并令其等于0，可得到对应的α^*和w^*为

经过变换，线性可分的原问题可转化为对偶问题。在约束条件

下对α_i求解下列函数的最大值：

在这类约束优化问题的求解和分析中，Karush-Kuhn-Tucher（KKT）条件将起重要作用，如式（7-38）这样的问题，其解必须满足

α_i{y_i（w·x_i+b）-1}=0 i=1，2，…，n （7-41）

从式（7-38）可以看出，只有系数α_i＞0的样本对w*起作用，即只有支持向量影响最终的划分结果。

求解上述问题后得到的最优分类函数是

式中，sgn（）为符号函数；b^*是分类的阈值，可以由任意一个支持向量样本x_i用下式求得

b^*=y_i-w·x_i （7-43）

或通过两类中任意一对支持向量取中值求得。对于给定的未知样本x，只需计算f（x），根据f（x）的符号即可判定x所属的分类。

2.线性不可分情况

由于在实际情况中，不存在精确的分类超平面，Vapnik通过引入正的松弛因子ξ_i来构造“软边缘”分类面，允许错分样本的存在。于是，求取最优分类面的二次规划问题就转变为在条件y_i[（w·x_i）+b]-1+ξ_i≥0，i=1，…，n和ξ_i≥0下最小化，即

式中，φ为将输入特征向量映射到某个高维特征空间的非线性变换函数；C为正常数，代表对错分样本的惩罚力度，即在边缘之内的样本对分类面的构造引起的作用是有限制的，这就是“软边缘”的含义。这样，Wolfe对偶问题可以写成在条件和0≤α_i≤C；i=1，…，n下的最大化；即

(www.xing528.com)

式中，K（x_i，x_j）为核函数。由于求最大值可以转化为取负求最小值，这一数学模型最终表达为在条件和0≤α_i≤C，i=1，…，n下：

式中，H是一个半正定的对称阵[y_iy_jK（x_i，x_j）]ⁿ_i，j=1。最终推导所得的Wolfe对偶问题与可分的情况类似，唯一的区别在于对α_i加了一个上限限制。这种软边缘分类面对于非线性支持向量机同样适用，使得支持向量机可以普遍适用于各种模式识别问题。

3.支持向量机

对于N维空间中的线性函数，其VC维为N+1，但根据式（7-35）的结论，在||w||≤A的约束条件下，其VC维可能大大减小，即使在十分高维的空间中，也可以得到较小VC维的函数集（比如参考文献[9]中介绍了在10¹³维空间中取得VC维在10³左右的分类面的例子），以保证有较好的推广性。同时可以看到，通过把原问题转化为对偶问题，计算的复杂度不再取决于空间维数，而是取决于样本数，尤其是样本中的支持向量数。这些特点使有效地对付高维问题成为可能。

对非线性问题，可以通过非线性变换转化为某个高维空间中的线性问题，在变换空间求最优分类面。这种变换可能比较复杂，因此这种思路在一般情况下不易实现。但是注意到，在上面的对偶问题中，不论是寻优函数式（7-40），还是分类函数式（7-42），都只涉及训练样本之间的内积运算（x_i·x_j），这样在高维空间实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数实现的，甚至没有必要知道变换的形式。根据泛函的有关理论，只要一种核函数K（x_i·x_j）满足Mercer条件，它就对应某一变换空间中的内积。

因此，在最优分类面中，采用适当的内积函数K（x_i·x_j）就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加，此时目标函数式（7-40）变为

而相应的分类函数也变为

这就是支持向量机。

构造类型判别函数的学习机称为支持向量机，在支持向量机中构造判别函数的复杂性取决于支持向量的数目，而不是特征空间的维数。因此支持向量机中形成的分类函数是一组以支持向量为参数的非线性函数的线性组合，分类函数的表达式仅和支持向量的数量有关，而独立于空间的维度。在处理高维输入空间的分类时，这种方法尤其有效。图7-3所示为支持向量机的结构示意图。

4.核函数

支持向量机的基本思想可以概括为：首先通过非线性变换，将输入空间变换到一个高维空间，然后在这个新空间中求取最优线性分类面，而这种非线性变换是通过定义适当的内积函数实现的。常用的核函数有以下几种：

（1）多项式核函数 多项式核函数为

图7-3 支持向量机结构示意图

K（x，x_i）=[（x，x_i）+1]^d （7-49）

所得到的是d阶多项式分类器。

（2）径向基核函数 径向基核函数通常为

对于任何σ值，径向基函数K_r（|x-x_i|）是一个非负的单调函数。当|x-x_i|训练样本数趋向于无穷大时，它趋向于零。

经典的径向基函数使用下面的判别规则：

其中，径向基函数K_r（|x-x_i|）取决于两个向量之间的距离。构造式（7-52）的判别规则，必须估计：

1）参数的σ值；

2）中心点x_i数目N；

3）描述中心点向量x_i；

4）参数的值α_i。

与传统的径向基函数方法的重要区别是，这里每个基函数的中心点对应一个支持向量，中心点本身和输出权值都是由支持向量机训练算法来自动确定的。

（3）Sigmoid核函数 支持向量机采用Sigmoid函数作为内积核函数，就实现了包含一个隐层的多层感知机。隐层节点数目由算法自动确定。满足Mercer条件的Sigmoid核函数为

K（x，x_i）=tanh（γx^T_ix_j+b） （7-53）