2.2.5 支持向量机

支持向量机简称SVM，是统计学习理论中最新的内容，也是最实用的部分。SVM是一种新的非常有发展前景的分类技术，可以替代多层感知机，RBF神经网络和多项式神经网络等已有的学习算法。其核心内容是在1992～1995年间提出的，目前仍处在不断发展的阶段。

SVM以结构风险最小化准则为理论基础，通过适当的选择函数子集以及该函数子集中的判别函数，使得学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试集的测试误差仍然较小。因而，SVM是一个具有最优分类能力和推广能力的学习机器。

1.支持向量机理论

（1）线性可分的最优分类面

SVM是从线性可分情况下的最优分类面发展而来的，基本思想如图2-11所示。图中圆形和三角形代表两类样本，H 为它们之间的分类超平面，H1，H2分别为过各类中离分类面最近的样本且平行于分类面的超平面，它们之间的距离Δ称为分类间隔（Margin）。

当分类面发生变化时，分类间隔Δ也随之发生变化。反之，给定分类间隔Δ的值，也可以确定相应的分类超平面（也可能对应着许多超平面，统称为超平面集合）。在Δ间隔下，超平面集合的VC维h应满足下面关系：

式中，f ( . )是单调增函数，即h与Δ2成反比关系。因此，当训练样本给定时，分类间隔越大，则对应的分类超平面集合的VC维就越小。使分类间隔最大，实际上就是对推广能力的控制，这是SVM的核心思想之一。

最优分类面就是要求分类面不但能将两类样本正确分开（训练错误率为0），而且要使两类的分类间隔最大。根据结构风险最小化原则，前者是保证经验风险最小，而后者使得分类间隔最大，导致VC维最小，实际上就是使推广性的界中的置信范围最小，从而达到使得真实风险最小的目的。

分类面方程为wT x+b=0，如果线性可分，则样本集(xi,yi)，i=1,2,…,n，x∈Rd，y∈{-1,1}满足：此时分类间隔等于2/||w||，使分类间隔最大等价于使||w||2最小。满足条件式（2-129）且使最小的分类面就称为最优分类面，图2-12为各分类面与最优分类面的示意图，其中，H1，H2上的训练样本点就称为支持向量（SV）。

线性可分情况下，在结构风险最小化准则下的最优超平面问题，可以表示为如下的约束优化问题。即求函数

的最小化。为此，可以定义如下的Lagrange函数：

式中，αi≥0为各样本对应的Lagrange系数。

求解式（2-131）的最小值，可以令该泛函对w和b求偏导，并令它们等于0，这样就可以把上述求最优分类面的问题转化为较简单的对偶问题，即在约束条件

下，求下列函数最大值时的解αi：

αi为原问题中与每个约束条件即式（2-129）对应的Lagrange乘子。这是一个不等式约束下二次函数寻优的问题，存在唯一解。容易证明，解将只有一部分（通常是少部分）不为零，该部分对应的样本就是支持向量。

假设为最优解，则最优分类面的权系数向量为

即最优分类面的权系数向量是训练样本中支持向量的线性组合。得到支持向量及向量w*后，分类器中的阈值b*，可以通过两类中任意一对支持向量取中值得到。

式中，x*(1)、x*(-1)分别表示两类中任意一个支持向量。

根据前面所得到的支持向量以及其相关的系数，就可以得到上述问题的最优分类判别函数（指示函数）：

（2）线性不可分的最优分类面

上面的方法是训练样本在线性可分的情况下，保证全部样本能被正确地分类，即经验风险Remp为0的前提下，通过对分类间隔最大化，使分类器获得最好的推广能力。若训练集是线性不可分的，或事先不知道它是否线性可分的，我们可以通过引入非负松弛变量(ξi,i=1,2,…,n)来允许错分样本的存在。这时，式（2-129）变为

容许错分的分类超平面称为软间隔分类超平面。图2-13为训练集在线性不可分的情况下软间隔分类超平面示意图。由于允许存在错分样本，此时的软间隔分类超平面表示在剔除那些错分样本后最大分类间隔的超平面。

此时，最小泛函由式（2-130）变为

式中，C >0是一个自定义的惩罚因子，它控制对错分样本惩罚的程度，用来控制样本偏差与机器推广能力之间的折中。C越大，惩罚就越大，对错分样本的约束程度就越大。

用与求解最优分类面时同样的方法求解式（2-139）的优化问题，同样得到一个求二次函数的极值问题，其结果与线性可分情况下得到的式（2-132）～式（2-137）几乎完全相同，只是条件式（2-133）变为

（3）支持向量机的概念

前面分别介绍了在线性分类和非线性情况下，如何求解最优超平面。而在实际应用中，分类问题往往是一个非线性的问题，理想的分类面应该是非线性的。对非线性问题，可以通过非线性变换，将非线性问题转化为某个高维空间中的线性问题，在变换后的高维空间中求其最优分类面。支持向量机方法处理非线性问题的方法是，首先将训练集从原始模式空间经过特定函数的非线性变换，映射到高维特征空间，然后，在高维特征空间中，寻找最优分类超平面，该超平面实际上对应着原始模式空间中的非线性分类面，如图2-14所示。

因此，支持向量机方法在处理非线性分类问题时，仅比线性情况多了一个非线性映射环节。假定该非线性映射为

则式（2-134）中的优化问题就可以转变为

式（2-141）的非线性变换可能比较复杂，从而使式（2-142）的计算非常困难以至于难以实现。但是注意到，在上面的对偶问题中，训练算法仅使用了高维特征空间中的点积，即ϕ(xi)·ϕ(x j)，而没有单独的映射ϕ(xi)出现。因此，如果能够找到一个函数K，使得定理（Mercer条件）：对于任意的对称函数K(x, x＇ )，它是某个特征空间中的内积运算的充分必要条件是，对于任意的ϕ(x)≠0且∫ϕ2(x)dx<∞有

这样，在高维特征空间中，实际上只需要进行内积运算，而这种内积运算是可以用原空间中的函数来实现的，我们甚至没有必要知道变换映射ϕ(⋅)的形式。根据泛函的有关理论，只要一种内积函数K(xi,xj)满足如下定理中的Mercer条件，它就对应某一变换空间中的内积。

因此在求最优分类面时，采用适当的内积函数K(xi, xj)就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加，此时目标函数式（2-134）与式（2-142）变为

而相应的最优分类面的判别函数式（2-137）也变为

这就是支持向量机（SVM）。概括地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，在这个空间中求（广义）最优分类面。最优向量机分类函数形式上类似于一个神经网络，输出是中间结点的线性组合，每个中间结点对应一个支持向量，如图2-15所示。

2.支持向量机模型的建立

SVM中可供调整的参数不多，其模型的确立主要是核函数的形式及其参数，如采用多项式核函数就要确定q的值，而对于高斯径向基核函数则要确定σ的值。关于核函数的特性与选择的问题，在前面已经做了分析和说明。对于分类问题，标准SVM的另一个可调节的参数是惩罚系数C。

本节主要讨论惩罚系数C的问题，另外还将讨论SVM的实现算法和多类问题解决方法。

（1）惩罚系数C

已知，在线性不可分的情况下，求最优分类面问题等同于求解下列问题。

式中，C >0，为惩罚系数。

这是一个二次规划问题，可通过Lagrange方法求解，转化为如下问题。

最优分类面的权系数为

可见，最优分类面的权系数向量是训练样本向量的线性组合。

对比式（2-151）和式（2-133），可以看出，由于C的引入，αi的值受到限制，C越小，αi的值也就越小，又由式（2-152）可知，||w||也变小，而2/||w||是两类之间的间隔，它的大小也体现了SVM泛化能力的强弱，间隔越大，泛化能力越强，反之，则泛化能力越弱。所以C越小，两类之间的间隔越大，SVM泛化能力越强，但显然这时SVM的分类准确率要降低。同理，C越大，两类之间的间隔越小，SVM泛化能力就越差，但这时的SVM分类准确率可以得到提高。

从上面的分析知道，惩罚系数C可以控制SVM的泛化性能和错分率之间的折中。C不宜太大，也不宜太小。C的值太大时，虽然此时样本的识别率高，SVM的分类性能很好（如果不出现过适应的话），但此时的泛化性能较低。再看看对偶问题，惩罚系数C的值越大，Lagrange算子αi的约束力就越大，这就意味着要花更长的训练时间。这两个现象是互相联系的，过长的训练时间，往往意味着过适应和低下的泛化能力。其解决办法就是减小C。但是C的值也不宜太小。注意到线性不可分的情况下，0≤αi≤C，C的值太小时，所有的αi自然也会很小，泛化能力虽然高，但准确率无法保证。

（2）SVM学习算法的步骤

SVM学习算法的步骤如下：

（a）获取学习样本(xi,yi)，i=1,2,…,n；

（b）选择进行非线性变换的核函数及对错分（误差）进行惩罚的惩罚因子C；

（c）形成二次优化问题；

（d）用优化方法（如Chunking，SMO算法）解该优化问题；

（e）获得α，α*及b的值，代入方程中，获得分类的支持向量机；

（f）将需要预测或分类的数据代入支持向量机方程中获得结果。

（3）SVM多类分类器算法

由前面的内容可知，标准SVM最基本的理论是针对二分类问题的，然而，在实际应用中有许多多分类问题，要解决多分类问题必须辅以一定的策略，常用的方法有以下几种：

·标准算法。对于k-类问题应构造k个分类器，第i个SVM用第i类中的训练样本作为正的训练样本，将其他的样本作为负的训练样本。这个算法称为一对多方法(one-against-rest )。

·一对一算法(one-against-one)。该算法在 k 类训练样本中构造所有可能的二类分类器，每类仅在k类中的二类训练样本上训练，结果共构造个分类器。组合这些二类分类器很自然地用到了投票法，得票最多的类为新点所属的类。

·k-类SVM算法。该算法对所有的样本使用同一个二次规划，只需要一次就可以决定分类。Weston提出了两种新的k-类SVM算法：QP-MC-SV算法和LP-MC-SV算法。这种算法很自然地在构造决策函数时同时考虑所有的类。

·决策导向循环图算法。Platt等提出了一个新的学习构架——决策导向循环图（Decision Directed Acyclic Graph，DDAG），该方法将多个二类分类器组合成k-类分类器。对于k-

·类问题，DDAG含有个分类器，每个分类器对应二类。

3.支持向量机模型的特点

支持向量机方法的几个主要特点为：

·支持向量机方法是基于统计学习理论的结构风险最小化准则，与传统的机器学习方法不同，它不仅使经验风险最小而且通过寻找最大间隔分解面来控制模型的复杂度，从而有效地避免了过拟合现象，为模型选择的问题提供了良好的思路；

·支持向量机法专门针对有限样本情况，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优解；

·支持向量机方法最终转化为在线性条件下的凸二次优化问题，从理论上说，找到的极值点是全局最优点，解决了在神经网络方法中无法避免的局部极值问题。

支持向量机方法将实际问题通过非线性映射变换到高维的特征空间，在高维空间中，通过构造线性判别函数来实现原空间中的非线性判别，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数问题，这在一定程度上解决了特征维数过大所导致的维数灾难问题。

4.支持向量机在Visual C++环境中的实现

由于支持向量机的算法实现比较复杂，本书提供一个Visual C++下的支持向量机实现程序，具体见所附光盘。