2.3 支持向量机

支持向量机是Vapnik等^［16-18］以统计学习理论为基础，结合优化理论、核理论等提出的一种监督学习方法，可以广泛地应用于统计分类和回归分析。支持向量机通过寻找一个既能保证分类精度，又使两类数据间隔最大化的超平面来实现监督学习。支持向量机的特点是能同时最小化经验误差和最大化分类间隔。本书第1章1.3.2小节概述了支持向量机的概念和近几年的主要研究成果，本节将对支持向量机的理论基础进行介绍，并详细介绍几种常用的支持向量机模型。

2.3.1 支持向量机理论基础

支持向量机是在统计学习理论的基础上建立起来的监督学习模型，是统计学习理论中最新颖、最具实用性的方法之一。此外，优化理论和最优分类超平面的思想也是支持向量机建立的理论基础。本小节将从这3个方面对支持向量机的理论基础进行介绍。

（1）统计学习理论基础

支持向量机是在统计学习理论基础上发展起来的通用监督学习方法。与传统统计学相比，统计学习理论（Statistical Learning Theory，SLT）是一种专门研究小样本情况下机器学习规律的理论。概括地说，统计学习理论主要内容包括4个方面^［16］：

1）在经验风险最小化准则基础上统计学习的一致性条件。

2）在一致性条件基础上关于统计学习方法推广性的界的结论。

3）在推广性的界的结论的基础上建立的小样本归纳推理准则。

4）实现新准则的实际算法。

其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是VC维。VC维（Vapnik-Chervonenkis，VC）被认为是数学和计算机科学中非常重要的定量化概念，它可以用来刻画学习过程的一致收敛的速度和推广性。VC维的直观定义是：对一个指示函数集，如果存在N个样本能够被函数集中的函数按所有可能的2^N种形式分开，则称函数集能把N个样本打散，函数集的VC维就是它能够打散的最大样本数目N。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。对于有界实函数来说，它的VC维可以通过用一定的阈值将它转化为指示函数来定义。VC维反映函数集的学习能力，同时也反映学习器的复杂程度^［16］，VC维越大说明学习器越复杂。遗憾的是，目前尚没有关于任意函数集VC维的计算理论，而仅可以确定一些特殊函数集的VC维。例如，在m维实数空间中线性分类器和线性实函数的VC维是m+1。而对于一些比较复杂的学习器来讲，VC维则很难确定。

在机器学习中，可以提供学习经验信息的只有样本，这会使得损失函数的期望值（期望风险）无法计算，因此传统的学习方法中使用样本定义的经验风险作为期望风险的估计，设计学习算法使其获得最小值，这便是经验风险最小化准则。

而真实风险中除了考虑经验风险外，还要考虑所得结果的置信度问题，也就是置信风险。置信风险用一个估计的区间度量分类结果的可信程度，其大小受样本数量和分类函数VC维影响。给定的样本数量越大，学习结果越有可能正确，此时置信风险越小；分类函数的VC维越小，泛化能力越好，置信风险也越小，而经验风险的大小则与其相反。所以在实际风险中，想要使经验风险与置信风险同时达到最小是不现实的。

统计学习理论提出了一种新的策略，试图寻求经验风险与置信风险的和最小，即把函数集构造为一个函数子集序列，在每个子集中寻找最小经验风险，在子集间折中考虑经验风险和置信范围，取得实际风险的最小，这种思想就称为结构风险最小化准则。

（2）支持向量机中的优化理论

在支持向量机中，为求解方便，通常将优化问题的原始问题转变为与之对应的对偶问题进行求解。可以认为，支持向量机算法的本质是对原始问题以及与之对应的对偶问题的凸二次规划的求解^［19］。为此，以下分别对支持向量机中的凸规划问题和Wolfe对偶问题进行介绍。

1）凸约束优化问题解的充分必要条件——KKT（Karush-Kuhn-Tucker）条件^{［20，21］}。

定理2.1^［22］（凸约束优化问题） 考虑以下约束优化问题，即

若目标函数f（x）和约束函数c_i（x）（i=1，…，p）都是凸函数，而c_i（x）（i=p+1，…，p+q）是线性函数，那么该约束优化问题为凸约束优化问题或凸最优化问题。

定理2.2^［22］（凸约束优化问题解的充分必要条件） 考虑式（2.9）所示的凸约束优化问题，其中f∶Rⁿ→R和c_i∶Rⁿ→R（i=1，…，p）都是可微凸函数，c_i（x）（i=p+1，…，p+q）是线性函数，则x是该优化问题解的充分必要条件是存在着使得

此充分必要条件被称为Karush-Kuhn-Tucker条件。在定理2.2的基础上，可以直接推出定理2.3和定理2.4。

定理2.3^［22］（凸二次规划解的充分必要条件） 考虑凸二次规划问题，即

式中：G为n×n阶半正定矩阵；A为p×n阶矩阵。r∈Rⁿ，则x是该问题解的充分必要条件是存在使得

定理2.4^［22］（线性规划解的充分必要条件） 考虑线性规划问题

其中，r∈Rⁿ，d∈R^d，A是p×n阶矩阵，则是该问题解的充分必要条件是存在使得

2）Wolfe对偶问题^［22］。

在支持向量机中使用对偶表示形式一方面可以为支持向量机理论在高维空间中的应用提供便利，另一方面可以为从最优化理论中得出支持向量机的具体算法铺平道路，因此对偶问题是支持向量机研究中非常重要的环节。

首先考虑只含有不等式约束的凸约束优化问题，即

其中，f和每一个c_i都是连续可微的凸函数，则问题式（2.16）的Wolfe对偶问题为

定理2.5^［22］（Wolfe对偶定理） 如果问题式（2.16）有解，则它的Wolfe对偶问题式（2.17）也有解；如果问题式（2.16）和其Wolfe对偶问题式（2.17）分别有可行解x和α，则这两个可行解分别为原始问题和对偶问题的最优解的充分必要条件是它们对应的原始问题和对偶问题的目标函数值相等。

将上述结论推广到式（2.10）所示的一般凸约束优化问题，可以得到以下相应结论。

定理2.6^［22］（凸约束优化问题的Wolfe对偶定理） 考虑式（2.10）的凸约束优化问题，其中f∶Rⁿ→R和c_i∶Rⁿ→R（i=1，…，p）都是可微凸函数，c_i（x）（i=p+1，…，p+q）是线性函数，则可推出：若问题式（2.10）有解，它的Wolfe对偶问题也有解；若问题式（2.10）和它的Wolfe对偶问题分别有可行解x和（α，β），则这两个可行解分别为原始问题和对偶问题的最优解的充分必要条件是它们的原始问题和对偶问题的目标函数值相等。

对二次规划问题和线性规划问题的Wolfe对偶，分别有以下结论：

定理2.7^［22］ 考虑二次规划问题，即

式中：G为正定矩阵；x，r∈Rⁿ；A∈R^m×n；d∈R^m。则该问题的Wolfe对偶为

定理2.8^[22] 如果问题式（2.18）有可行解，则x^*=-G^-1（A^Tα*+r）是它的解的充分必要条件是α^*是对偶问题式 （2.19）的解。

定理2.9^［22］ 考虑线性规划问题，即

其中，x，c∈Rⁿ，A∈R^m×n，b∈R^m，则该问题的Wolfe对偶为^［23］

定理2.10^［22］ 考虑式（2.20）的线性规划问题，如果x∈Rⁿ是此问题的最优解，w∈R^m是其对偶问题式（2.21）的最优解的充分必要条件是：存在r∈Rⁿ满足以下KKT条件，即

（3）最大间隔分类超平面

支持向量机是从线性可分情况下的最优分类面发展而来的，最优分类面的基本思想可用图2.4所示的二维分类问题进行阐述。图中，点和圈代表不同的两类样本，H为分类线，H₁和H₂分别为过各类中离H最近的样本点且平行于H的直线，H₁与H₂之间的距离称为分类间隔（Margin）。

图2.4 线性可分情况下的最优分类线

给定训练样本集S={（x₁，y₁），…，（x₁y₁）}X×{-1，+1}，其中XRⁿ表示输入空间或特征空间，y_i∈{-1，+1}表示样本数据的类别标记，通过寻找一个最优分类超平面将正负两类样本完全分开以完成分类问题的求解。

设}表示所有能够 “完全正确分类”的超平面的集合，其中 “·”代表进行内积运算。“完全正确分类”是指对于任意一个由常数和法向量构建的分类超平面H，它对训练样本集S的分类结果满足

这里训练样本 （x_i，y_i）∈S到超平面H 的距离为）。设d⁺=min{d_i|y_i=+1}和d^-=min{d_i|y_i=-1}，分别代表训练样本集中的正类样本集和负类样本集到分类超平面的最小距离，并且可利用式（2.24）计算两个与分类超平面平行的超平面H₁和超平面H₂的位置，即

由分析可知，超平面H₁和H₂分别与正样本和负样本相切，S中的训练样本不出现于它们之间的区域。同时，位于超平面H₁和H₂正中间且与它们均平行的超平面H₀：可以将两类训练样本等距离地划分开来，因而H₀比H的分类性能更为优良。

取，将超平面H₀、H₁、H₂进行规范化表示，其具体形式为

很明显，超平面H₀∶w·x+b=0仍然在集合G内。此时称超平面H₁到超平面H₂的距离为超平面H₀的“分类间隔Δ”，同时，称超平面H₁和H₂为超平面H₀的“间隔边界”，这两个超平面上的训练样本点就是支持向量。容易计算得到分类间隔为。而 “最大分类间隔超平面”是指在满足约束条件y_i（w·x_i+b）≥1的基础上，能够使得Δ取得最大值的超平面，依据Vapnik的理论，最大分类间隔超平面是解决分类问题的最优超平面^[16]。

定理2.11^［16］ 最大分类间隔超平面是唯一存在的。

对分类间隔进行最大化处理本质上就是控制算法的泛化能力，而这正是支持向量机的关键思想之一。统计学习理论指出，在m维空间中，设样本分布在一个半径为R的超球范围内，则间隔为Δ的正则超平面构成的指示函数集f（x，w，b）=sgn{（w·x）+b}（sgn（）为符号函数）的VC维满足下面的界，即

因此使间隔Δ最大就是使VC维的上界最小，即使得分类间隔最大化实际上是对算法泛化能力的控制，从而实现结构风险最小化准则中对函数复杂性的选择。

2.3.2 常用支持向量机学习方法

从2.3.1小节可以看出，在支持向量机的学习过程中，构建最大间隔分类超平面是极其重要的。对不同类型的样本，构建的超平面有所不同，所得到的支持向量机的类型也不同，大致可分为硬间隔支持向量机、软间隔支持向量机和非线性支持向量机等，本小节将对这几类基本的支持向量机进行介绍。

（1）硬间隔支持向量机

硬间隔支持向量机（Hard Margin Support Vector Machine）^［22］是指在使用支持向量机对样本进行分类时，所有样本线性可分，且能构建出使分类间隔Δ取正值的超平面。在正确划分训练集的超平面中，根据最大间隔原则，找出最优的决策超平面。

为了求解线性可分问题的最大间隔超平面，需要在满足约束y_i（w·x_i+b）≥1的前提下最大化间隔Δ，等价于以下的优化问题，即

式（2.27）是一个典型的线性约束的凸规划问题，它唯一确定了最大间隔分类超平面，为解决该约束优化问题，引入Lagrange函数，即

式中α_i>0，为Lagrange乘子。约束优化问题的解由Lagrange函数的鞍点决定，并且最优化问题的解在鞍点处满足对w和b的偏导为0，由Δ_bL（w，b，α）=0和Δ_wL（w，b，α）=0得到

同时将该二次规划问题转换为相应的对偶问题，即

可见，对偶问题仍是线性约束的凸二次优化问题，且唯一最优解为α^*=。

根据约束优化问题的Karush-Kuhn-Tucker条件，最优解α^*应满足以下条件，即

其中，最优权值向量w^*和最优偏置b^*分别为

其中，下标j∈{j|α_j*＞0}。

由于只有少部分观测样本x_i满足y_i（w^*·x_i+b^*）=1，它们对应的La grange乘子α^*＞0，而其余的样本满足f（x）={[sin（1）x]²+[sin（x）]²（x∈［-π，π］），解α^*的这种性质被称为“稀疏性”。其中α^*>0的观测样本便是位于图2.4中超平面H₁和H₂上的支持向量，可知最优权值向量w^*和最优偏置b^*均由支持向量决定。因此，最大间隔超平面w^*·x_i+b^*=0完全由支持向量决定，而与其余的观测样本无关。

此时，得到最优分类判别函数为

（2）软间隔支持向量机

软间隔支持向量机（Softmargin Support Vector Machine）^［19］是相对于硬间隔支持向量机而言的。当样本线性不可分时，使用支持向量机对所有样本进行分类，就不能直接使用“硬间隔”的方法构建出使得分类间隔Δ取正值的超平面。也就是说，必须对硬间隔支持向量机中的约束条件进行适当松弛。将松弛变量ξ_i≥0（i=1，…，l）引入算法当中，便可以得到以下软间隔支持向量机的约束条件，即

显然，当ξ_i足够大时，样本（x_i，y_i）总可以满足上述软化的约束条件。但从另一个角度来说，项与样本的分类误差相关同时体现经验风险，因此必须对它的大小进行控制。这样便得到最大软间隔支持向量机的优化问题，即

其中，正实常数C>0称为正则化系数或“罚参数”。参数C的取值越大，对训练集上的识别错误数越敏感，错误数越少，但泛化能力下降。参数C可平衡泛化能力和训练误差，换句话说，罚参数C在支持向量机的复杂度和经验风险之间进行权衡。C的选取与训练集的噪声有关，通常由用户设定或通过交叉检验等方法确定。下面对软间隔支持向量机优化问题的对偶问题进行推导，首先引入原始问题的Lagrange函数，即

其中，α、β为Lagrange乘子，α_i≥0，β_i≥0，求Lagrange函数关于w、b、ξ的偏导数。由极值条件可得

进而可以得到

经过推导得到对偶问题为

式中：α为Lagrange乘子；x为训练样本；y为训练样本标记；C为罚参数。

由以上推导过程可以发现，软间隔支持向量机与硬间隔支持向量机对偶问题的差别仅仅在于Lagrange乘子受到了“盒约束”，即对偶问题中向量α被约束到边长为C的盒子里。而罚参数直接控制了α_i的大小。盒约束可限制离群点的影响，因离群点的Lagrange乘子通常很大。同时，盒约束也可确保可行域的界，使得原问题总有非空可行域^［24］。

（3）非线性支持向量机

非线性支持向量机的引入是考虑到样本存在线性不可分的情况^［25］，其主要思想是将输入向量映射到一个高维的特征向量空间，并在该特征空间中构造最优分类超平面。当选用适当的映射函数时，大多数低维空间线性不可分的问题可以转化为高维特征空间中的线性可分问题。

但是在将低维输入空间映射到高维特征空间的过程中，空间的维数将急速增长，导致很难直接在特征空间中计算最优分类超平面。支持向量机通过定义核函数（Kernel Function），巧妙地将这一问题转化到输入空间进行计算^［26］，其具体机理如下：

将x从输入空间Rⁿ映射到特征空间H中，有

特征向量Φ（x）代替输入向量x，当在特征空间中构造最优分类超平面时，仅使用特征空间中的点积，即Φ（x_i） ·Φ（x_j）。所以，若能找到一个函数K（）使得K（x_i，x_j）=Φ（x_i） ·Φ（x_j），甚至不必知道非线性变换Φ的具体形式。

根据有关泛函理论，只要一种函数K（x_i，x_j）满足Mercer条件，它就对应某一变换空间的内积。

定理2.12（Mercer）^［27］ 对称函数K（u，v）∈L²能够以正系数α_k>0展开成K（u，v）=形式的充分必要条件是：对所有满足∫^g2（u）du＜∞，且g≠0的函数g（u），有∫∫K（u，v）g（u）g（v）dudv≥0成立。

满足Mercer条件的内积函数K（x_i，x_j）称为核函数，不同的内积核函数将形成不同的算法^［28］。

因此，在最优分类超平面中采用满足Mercer条件的内积函数K（x_i，x_j）就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加，此时的Lagrange函数变为

其对应的对偶问题为

求解上述问题后，则可以得到最优分类函数为

式中：m为支持向量的数目。在上面的对偶问题中，目标函数和决策函数都只利用训练样本之间的内积运算和求和运算（图2.5），这样便巧妙地避免了复杂的高维运算，且支持向量的个数直接决定学习过程的计算复杂度。

图2.5 支持向量机网络示意图

由图2.5可以看出，可用一个前馈网络来表示支持向量机所构建的决策函数，其输出是若干中间层节点的线性组合，而每一个中间层对应于输入样本的一个支持向量的内积。