1、第第8 8章章 支持向量机支持向量机 n支持向量机SVM(Support Vector Machines)是由Vanpik领导的AT&T Bell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术，SVM是一种基于统计学习理论的模式识别方法，主要应用于模式识别领域。n由于当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩，因此这些研究一直没有得到充的重视。n90年代，一个较完善的理论体系统计学习理论(Statistical Learning Theory，简称SLT)的实现和由于神经网络等较新兴的机器学习方法的研究遇到一些重要的困难，比如如何确定网络结构的问
2、题、过学习与欠学习问题、局部极小点问题等，使得SVM迅速发展和完善，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中，从此迅速的发展起来，现在已经在在模式识别、回归分析、函数估计、时间序列预测等领域都得到了长足的发展，并被广泛应用于文本识别、手写字体识别、人脸图像识别、基因分类、时间序列预测等。节次安排n8.1 概述概述n8.2 统计学习理论统计学习理论 n8.3 支持向量机（支持向量机（SVM）n8.4 核函数核函数n8.5 SVM的算法及多类的算法及多类SVMn8.6 SVM的应用现状的应用现状n8.7 小结小结8.1 概述概述n基
3、于数据的机器学习，需要从观测数据(样本)出发寻找数据中的模式和数据见的函数依赖规律，利用这些模式和函数依赖对未来数据或无法观测的数据进行分类、识别和预测。其实现方法大致可以分为三种：n第一种方法是经典的(参数)统计估计算法，在这种方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局限性，首先，它需要已知样本分布形式，其次传统统计学研究的是样本数目趋于无穷大时的渐进理论，现有学习方法也多是基于此假设，但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。n第二种方法是人工神经网络(ANN)，这种方法利用已知样本建立非线性模型，克服了传
4、统参数估计方法的困难，在过去的十几年中，神经网络受各个领域学者的广泛研究，技术上得到很大的发展，提出了许多神经网络结构，其中常用的有多层感知器(MLP)、径向基函数网络(RBF)、Hopfield网络等，也被成功地用来解决许多实际问题，但是现在的神经网络技术研究理论基石不足，有较大的经验成分，在技术上仍存在一些不易解决的问题。n为了克服以上所说的那些难题，Vapnik提出了一种新的神经网络支持向量机(SVM)，也是所说的第三种方法统计学习理论，SVM是统计学习理论中最年轻的内容，也是最实用的部分，它目前已经成为神经网络和机器学习的研究热点之一，并已经得到很好的研究成果。支持向量机的基本思想支持
5、向量机的基本思想n训练数据集非线性地映射到一个高维特征空间，这个非线性映射的目的是把在输入空间中的线性不可分数据集映射到高维特征空间后变为是线性可分的数据集，随后在特征空间建立一个具有最大隔离距离的最优分隔超平面，这也相当于在输入空间产生一个最优非线性决策边界，如下图所示：n存在多个分类超平面可以把两个类分离开来，但是只有一个是最优分类超平面，它与两个类之间最近向量的距离最大。n支持向量机的目的就是要把这个最优的分类超平面找出来。8.2 统计学习理论统计学习理论n统计学习理论诞生于20世纪6070年代，其主要创立者是Vladimir N.Vapnik，到90年代中期发展到比较成熟并受到世界机器
6、学习界的广泛重视。n统计学习理论是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。8.2.1 学习问题的表示学习问题的表示n样本学习的一般模型n产生器(G)：产生随机向量，它们是从固定但未知的概率分布函数F(x)中独立抽取的。n训练器(S)：对每个输入向量x返回一个输出值y，产生输出的根据是同样固定但未知的条件分布函数F(y|x)。n学习机器(LM)：它能够实现一定的函数集，其中是参数集合。n在学习过程中，学习机器LM观察数据对(x,y)。在训练之后，学
7、习机器必须对任意输入x，使之接近训练器的响应y。8.2.2 期望风险和经验风险期望风险和经验风险n给定输入x下训练器响应y与学习机器给出的响应 之间的损失记作n 就是风险泛函，即预测的期望(实际)风险。n 称为经验风险。),(axf),(,(axfyL),(),(,()(yxdFaxfyLaRliiiempaxfyLlaR1),(1)(8.2.3 学习过程一致性的条件学习过程一致性的条件n学习过程一致性(Consistency)是指训练样本无限时，经验风险的最优值收敛于真实风险最优值(期望风险值)。其严格定义如下：n定义定义 8.1 设f(x,a)是使经验风险最小化的函数，如果下面两个序列概率
8、收敛于同一极限，即 及 则称ERM原则(或方法)对函数集 和概率分布函数F(x,y)一致的。如果对函数集的任意非空子集 ，都有 则称ERM原则(或方法)对函数集 和概率分布函数F(x,y)非平凡一致的。)(inf)(aRaRall)(inf)(aRaRallemp aaxf),(),(),(cc)(inf)(inf)(aRaRcallempa aaxf),(n非平凡一致性对预测函数集中的所有函数都必须满足经验风险一致地收敛于真实风险。n定理定理 8.1 对于有界损失函数，ERM原则一致性的充分必要条件是：经验风险 在如下意义下一致收敛于实际风险 ：这种一致收敛被称作单边收敛；这种一致收敛被称作
9、双边收敛。)(aRemp)(wR0,0)()(sup(limaRaRPempl0,0|)()(|suplimaRaRPempl7.2.4 VC维理论维理论 n模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的 种形式分开，则称函数集能够把h个样本打散，函数集的VC维是无穷大。n有界实函数的VC维可以通过用一定的阀值将它转化成指示函数来定义。平面中直线的VC维等于3，因为它们能打散3个向量而不能打散4个。h2n定理定理8.2 对于 中的m个点集，选择任何一个点作为原点，m个点能被超平面打散当且仅当剩余点的位置向量是线形独立的。n推论推论 中有向超
10、平面集的VC维是n+1，因为总能从n+1个点中选择其中一个作为原点，剩余n个点的位置向量是线形独立的，但不能选择n+2个这样的点(因为在 中没有n+1是线形独立的)。nVC维反映了函数集的学习能力，VC维越大则学习机器越复杂(容量越大)，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。nR nRnR7.2.5 推广性的界推广性的界n定理定理8.3 所有函数集的生长函数或者与样本数成正比，即 或者以下列样本数的某个对数函数为上界，即 其中，h是一个整数，它是从生长函数满足 到满足 的转折点，即当h=1时，有 而 。n由定理7.3可以看出，VC维对于一个指示函数集
11、，如果其生长函数是线性的，则它的VC维为无穷大；而如果生长函数以参数为h的对数函数为界，则函数集的VC维是有界的且等于h。2ln)(llGhlhhlG),11(ln)(2ln)(llGhlhhlG),11(ln)(2ln)(hhG2ln)1()1(hhGn定理定理8.4 对于前面定义的两类分类问题，对指示函数集中的所有函数(当然也包括是经验风险最小的函数)，经验风险和实际风险之间至少以 概率满足如下关系：其中h为函数集 的VC维，为训练集的规模。右侧第二项通常称为VC置信度。n由上式可以看出，在学习系统VC维与训练集规模的比值很大时，即使经验风险较小，也无法保证期望风险较小，即无法保证学习系统
12、具有较好的泛化能力。因此，要获得一个泛化性能较好的学习系统，就需要在学习系统的VC维与训练集规模之间达成一定的均衡。lhlhfRfRemp4ln)12(ln)()(1aaxf),(lhlhfRfRemp4ln)12(ln)()(ln由于定理8.4所给出的是经验风险和实际风险之间误差的上界，它们反映了根据经验风险最小化原则得到的学习机器的推广能力，因此称作推广性的界。这一结论从理论上说明了学习机器的实际风险是有两部分组成的：一是经验风险（训练误差），另一部分称作置信范围，它和学习机器的VC维及训练样本数有关。可以简单地表示为：n它表明，在有限的训练样本下，学习机器VC维越高(复杂度越高)，则置信
13、范围越大，导致真实风险与经验风险之间可能的差别越大。机器学习过程不但要经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。)()()(nhfRfRemp8.2.6 结构风险最小化结构风险最小化nERM原则在样本有限时是不合理的，需要同时最小化经验风险和置信范围。其实，在传统方法中，选择学习模型和算法的过程就是调整置信范围的过程。比如在神经网络中，需要根据问题和样本的具体情况选择不同的网络结构维(对应不同的VC)，然后进行经验风险最小化。在模式识别中选定了一种分类器形式就确定了学习机器的VC维。n因为缺乏理论指导，这种选择只能依赖先验知识和经验，造
14、成了神经网络等方法对使用者的“技巧”的过分依赖。n统计学习理论提出了一种新的策略来解决这个问题。n首先把函数集 分解为一个函数子集序列 使各子集能够按照VC维的大小排列，即 这样在同一子集中置信范围就相同；在每一个子集中寻找最小经验风险和置信范围，取得实际风险的最小，如下图：n这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。aaxfS),(SSSSk 21 khhh21 n这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。n实现SRM原则可以有两种思路，一是在每个子集中求最小经验风险，然后
15、选择使最小经验风险和置信范围之和最小的子集。n显然这种方法比较费时，当子集数目很大甚至是无穷时不可行。因此有第二种思路，即设计函数集的某种结构使每个子集中都能取得最小的经验风险(如使训练误差为0)。n然后只需选择适当的子集使置信范围最小，则这个子集中经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思想的具体实现。8.3 支持向量机（支持向量机（SVM）n要在学习算法中执行SRM原则，必须在一个给定的函数集中使风险最小化，这要通过控制两个因素来完成：经验风险的值和置信范围的值。在学习的历史中，人们大多采用两种方法来完成学习过程：（1）保持置信范围固定(通过选择一个适当构造的机器)并最
16、小化经验风险。（2）保持经验风险值固定(比如等于零)并最小化置信范围。n本节我们讨论一种新的学习机器支持向量机，它采用的是第二种构造方法，下面我们严格按照SRM原则来构造这种学习机。8.3.1 线性可分支持向量机线性可分支持向量机n从理论上来讲，线性函数集只能处理线性可分的情况，我们也是从这种最简单的情况开始讨论。因为线性可分，经验风险始终为0，所以只最小化置信范围即可，故问题就是对于给定的样本数据 ，在保证其经验风险为0的前提下，选择使 置信范围最小的子集。从 可以看出，样本数固定时，子集的置信范围最小，也就是子集的VC维最小，而本函数集的子集的VC维只与权值 有关，并且是 的增函数，所以在
17、几何上，这个问题就是用权值最小的超平面把属于两个不同类 的样本集 分开，这个超平面叫做最优超平面，如下图：),(,),(11llyxyx )()()(hlaRaRemp)()()(hlaRaRemp|w|w1,1y),(,),(11llyxyx n最优超平面是以最大间隔将两类数据分开的平面，这个最大间隔意味着推广性最好。n支持向量机问题可以等价为求解下面的二次规划问题：最小化泛函 约束条件为不等式类型 这个问题的解是由下面的拉格朗日泛函的鞍点给出的：其中 为拉格朗日乘子。问题的对偶问题为：最大化泛函约束条件为：这样原问题的解为：)(21)(www libwxyii,2,1,1)(1)()(21
18、),(1bwxyawwabwLiiliiia)(21)(1,1jijijljiiliixxyyaaaaWliai,2,1,0 01iliiyaiiliixayw1n由拉格朗日可得到原问题的Karush-Kuhn-Tucker(KKT)条件：n根据优化理论，是原问题的解当且仅当 满足KKT条件。n在对偶问题或KKT条件中，每个训练数据 都对应一个拉格朗日乘子 ，其中与 对应的数据成为支持向量。0wL 0bLlibwxyii,2,1,01)(liai,2,1,0 libwxyaiii,2,1,01)(),(bw),(abwix0ia0ian利用任一支持向量和KKT条件 ，可求出 一般情况下，为了准
19、确，常求出多个b值，然后取平均值，或者 其中，用 表示属于第一类的任一支持向量，用 表示属于第二类的任一支持向量。最后的最优超平面方程：最终完成学习过程。01)(bwxyaiii iiyxwb)()1()1(21*xwxwb)1(*x)1(*x0bxxayiiSVxii=+).(8.3.2 线性不可分支持向量机线性不可分支持向量机n首先我们引入松弛变量 来表示经验风险，将原约束条件变为：这样，样本数据的经验风险在一定程度上可以表示为：其中 参数，代表经验风险的某种度量方式。n给定样本数据 后，我们在容许结构的某个子集下最小化经验风险，问题可以描述为：最小化泛函：约束条件为：libwxyiii,
20、2,1,1)(liiF1)(0lzzz,21 liiF1)(iiibwxy1)(kcww)(n这个问题可以等价为在约束条件下最小化泛函：这里的C是一个给定的值。n原问题的对偶形式为：n只是约束条件变为：n这样原问题的解为：)().(21),(1liiCwww).(21)(1,1jijijljiiliixxyyaaaaWliCai,2,1,0 01iliiyaiiliixayw18.4 核函数核函数n支持向量机的关键在于核函数。低维空间向量集通常难于划分，解决的方法是将它们映射到高维空间，但这个办法带来的困难就是计算复杂度的增加，而核函数正好巧妙地解决了这个问题。也就是说，只要选用适当的核函数，
21、我们就可以得到高维空间的分类函数。在SVM理论中，采用不同的核函数将导致不同的SVM算法。n首先定义映射 ，是输入空间，H是高维内积空间，称为特征空间，称为特征映射，然后在H中构造最优超平面。在特征空间中的学习过程同前面一样，对偶问题为：约束条件不变：HRd:dR)()(21)(1,1jijijljiiliixxyyaaaaWliCai,2,1,0 01iliiya 核函数的思想是在是使用输入空间的变量直接计算特征空间中的内积，即 其中 ，属于输入空间，函数即为核函数 这样，只要定义了核函数，我们就不必真的进行非线性变换，更没有必要知道采用的非线性变换的形式，所以我们只要构造输入空间的一个核函
22、数即可。),()()(xxkxx xx),(xxkn定理定理 8.6 对于任意的对称函数 ，它是某个特征空间的内积运算的充分必要条件是，对于任意的 且 ，有 事实上这一条件并不难满足。这样我们就可以得到输入空间中的非线性决策函数 它等价于在高维特征空间中的线性决策函数。),(xxk)0(xdxx)(20)()(),(xdxdxxxxK),(sgn()(bxxKayxfiiSVi8.4.2 核函数的分类核函数的分类n多项式核函数 所得到的是阶多项式分类器：n径向基函数 经典的径向基函数的判别函数为：最通常采用的核函数为高斯函数：qiixxxxK1),(),()1(sgn(),(*bxxayaxf
23、diiSVi)|)(|sgn()(1bxxKaxfirnii22|)(|exp|)(|iirxxxxKn多层感知机 SVM采用Sigmoid函数作为内积，这时就实现了包含一个隐层的多层感知机，隐层节点数目由算法自动确定。满足mercer条件的Sigmoid函数为：)(tanh(),(cxxvxxKjTiji8.5 SVM的算法及多类的算法及多类SVMn目前SVM的训练算法一般采用循环迭代解决对偶寻优问题：将原问题分解成为若干子问题，按照某种迭代策略，通过反复求解子问题，最终使结果收敛到原问题的最优解。根据子问题的划分和迭代策略的不同，大致可以分为：n块算法块算法Chunking Algorit
24、hm：考虑到去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用选择一部分样本构成工作样本集进行训练，剔除其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合KKT条件的样本与此次结果的支持向量合并成为一个新的工作样本集，然后重新训练，如此重复下去直到获得最优结果。nChunking算法将矩阵规模从训练样本数的平方减少到具有非零Lagrange乘数的样本数的平方，在很大程度上降低了训练过程对存储容量的要求。Chunking算法能够大大提高训练速度，尤其是当支持向量的数目远远小于训练样本的数目时。然而，如果支持向量个数比较多，随着算法迭代次数的增多，所选的块也会越来越大，算法的
25、训练速度依旧会变得十分缓慢。n(2)分解算法分解算法(Decomposition Algorithm)分解算法最早由Osuna等人提出，是目前有效解决大规模问题的主要方法。分解算法将二次规划问题分解成一系列规模较小的二次规划子问题，进行迭代求解。在每次迭代中，选取拉格朗日乘子分量的一个子集做为工作集，利用传统优化算法求解一个二次规划的子问题。该算法的关键在于选择一种最优的工作集选择算法，但是Osuna在工作集的选取中采用了随机的方法，因此限制了算法的收敛速度。Joachims在Osuna分解算法的基础上，关于工作集的选择做了重要改进。其主要思想是，如果存在不满足KTT条件的样本，利用最速下降法
26、，在最速下降方向中存在 个样本，然后以这 个样本构成工作集，在此工作集上解决QP问题，直到所有样本满足KTT条件。Joachims的改进大幅度提高了分解算法的收敛速度，并且他利用这些方法实现了SVMlight算法。n 由John C.Platt提出的序列最小优化（Sequential Minimal Optimization,SMO）算法可以说是Osuna分解算法的一个特例，工作集中只有2个样本，其优点是针对2个样本的二次规划问题可以有解析解的形式，从而避免了多样本情况下的数值解不稳定及耗时问题，同时也不需要大的矩阵存储空间，特别适合稀疏样本。其工作集的选择不是传统的最陡下降法，而是启发式。通
27、过两个嵌套的循环来寻找待优化的样本，然后在内环中选择另一个样本，完成一次优化，再循环，进行下一次优化，直到全部样本都满足最优条件。SMO算法主要耗时在最优条件的判断上，所以应寻找最合理即计算代价最低的最优条件判别式。n(3)(3)增量学习增量学习 增量学习是机器学习系统在处理新增样本时，能够只对原学习结果中与新样本有关的部分进行增加修改或删除操作，与之无关的部分则不被触及。增量训练算法的一个突出特点是支持向量机的学习不是一次离线进行的，而是一个数据逐一加入反复优化的过程。新型SVMn（1 1）粒度支持向量机）粒度支持向量机GSVMGSVM GSVM最早是由Tang Y C于2004年提出的，它
28、的主要思想是通过常用的粒度划分方法构建粒度空间获得一系列信息粒，然后在每个信息粒上进行学习，最后通过聚合信息粒上的信息（或数据、规则知识、属性等）获得最终的支持向量机决策函数。这一学习机制通过数据的粒化可以将一个线性不可分问题转化为一系列线性可分问题，从而获得多个决策函数；同时，这一学习机制也使得数据的泛化性能增强，即可在SVM的训练中得到间隔更宽的超平面。n（2 2）模糊支持向量机）模糊支持向量机FSVMFSVM 为了克服噪声和野值点对支持向量机的影响，台湾学者Chunfu Lin和Shengde Wang将模糊数学和支持向量机相结合，提出了模糊支持向量机，主要用来处理训练样本中的噪声数据。
29、其主要思想是：针对支持向量机对训练样本内的噪音和孤立点的敏感性，在训练样本集中增加一项：隶属度，并赋予支持向量较高的隶属度，而非支持向量及噪声野值点赋予较小的隶属度，从而降低了非支持向量、噪声和野值点对最优超平面的影响。n（3 3）孪生支持向量机）孪生支持向量机TSVMsTSVMs 2007年，Jayadeva 和Khemchandani R提出了一种二值数据的分类器孪生支持向量机(又称双分界面支持向量机)。TWSVMs在形式上类似于传统的支持向量机，不仅具有传统支持向量机的优点，而且对大规模数据具有更好的处理能力。TWSVMs为两个类各自得到一个分类平面，属于每个类的数据尽量围绕在与之相对应
30、的分类平面周围，然后TWSVMs通过优化一对分类平面来构建分类超平面。也就是说TWSVMs需要解决一对QP问题，而SVM则是解决一个QP问题，但是在TWSVMs中，其中一个类的数据要作为另一个QP问题的约束条件，反之亦然。8.5.2 多类问题中的多类问题中的SVMn 类模式识别问题是为 个样本 构成一个决策函数。由于SVM是解决两类问题的有效方法，因此用SVM解多类问题的方法通常将问题转化为两类问题，然后对结果进行处理。一般常用的方法有以下几种：One-against-the-rest方法：在第 类和其他 类之间构建超平面。One-against-one方法：为任意两个类构建超平面，共需 个
31、。K-class SVM：同时为所有的类构造一个分类超平面。klkyRxliyxiriii,2,1,2,1),(k1k2)1(KKsMSV8.6 SVM的应用现状的应用现状 人脸检测、验证和识别 Osuna最早将SVM应用于人脸检测，并取得了较好的效果。其方法是直接训练非线性SVM分类器完成人脸与非人脸的分类。大量实验结果表 明这种方法不仅具有较高的检测率和较低的误检率，而且具有较快的速度。说话人/语音识别 建立SVM和HMM（隐式马尔可夫模型）的混合模型。HMM适合处理连续信号，而SVM适合于分类问题；HMM的结果反映了同类样本的相似度，而SVM的输出结果则体现了异类样本间的差异。8.6 S
32、VM的应用现状的应用现状 文字/手写体识别 贝尔实验室对美国邮政手写数字库进行的实验，人工识别平均错误率为2.5%，专门针对该特定问题设计的5层神经网络错误率为5.1%（其中利用率大量先验知识），而用3种SVM方法（采用3种核函数）得到的错误率分别为4.0%、4.1%和4.2%，且是直接采用1616的字符点阵作为输入，表明了SVM的优越性能。8.6 SVM的应用现状的应用现状 图像处理：a 图像过滤,支持向量机分类和最近邻方法校验的多层系图像处理框架，达到85%以上的准确率。b 视频字幕提取,首先将原始图像帧分割为NN的子块，提取每个子块的灰度特征；然后使用预先训练好的SVM分类机进行字幕子块
33、和非字幕子块的分类；最后结合金字塔模型和后期处理过程，实现视频图像字幕区域的自动定位提取。c 图像分类和检索,以SVM为分类器，在每次反馈中对用户标记的正例和反例样本进行学习，并根据学习所得的模型进行检索，使用由9918幅图像组成的图像库进行实验，结果表明，在有限训练样本情况下具有良好的泛化能力。8.6 SVM的应用现状的应用现状 目前，国际上关于SVM理论的讨论和深入地研究逐渐广泛，我国国内在此领域的研究尚处在萌芽状态。我们需要及时学习掌握有关的理论知识，开展有效的研究工作，使我们在这个具有重要意义的领域中尽快赶上国际水平，跟上国际发展步伐。8.7 小结小结nSVM是基于统计学习理论中的经验风险最小化原则的一种机器学习，解决了对非线性函数求解超平面的问题。SVM可以有效地解决小样本、非线性及高维模式识别问题。nSVM用于模式分类的观点可以简单地阐述为：首先，无论问题是否为线性的，选择相应的核函数，均可将输入向量映射到一个高维空间；其次，用最优化理论方法寻求最优超平面将二类分开。n现在，统计学习理论和SVM方法尚处在发展阶段，很多方面还不完善，许多理论在算法中尚未实现；SVM算法的某些理论解释并非完美，SVM的应用目前仅是在有限的实验中观察到的现象，期待着理论证明。
