支持向量机原理及应用

1支持向量机简介摘要：支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以求获得最好的推广能力。我们通常希望分类的过程是一个机器学习的过程。这些数据点是n维实空间中的点。我们希望能够把这些点通过一个n-1维的超平面分开。通常这个被称为线性分类器。有很多分类器都符合这个要求。但是我们还希望找到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面，该面亦称为最大间隔超平面。如果我们能够找到这个面，那么这个分类器就称为最大间隔分类器。关键字：VC理论结构风险最小原则学习能力1、SVM的产生与发展自1995年Vapnik在统计学习理论的基础上提出SVM作为模式识别的新方法之后，SVM一直倍受关注。同年，Vapnik和Cortes提出软间隔(softmargin)SVM，通过引进松弛变量i度量数据ix的误分类(分类出现错误时i大于0)，同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数)，SVM的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年，Vapnik等人又提出支持向量回归(SupportVectorRegression，SVR)的方法用于解决拟合问题。SVR同SVM的出发点都是寻找最优超平面，但SVR的目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年，Weston等人根据SVM原理提出了用于解决多类分类的SVM方法(Multi-ClassSupportVectorMachines，Multi-SVM)，通过将多类分类转化成二类分类，将SVM应用于多分类问题的判断：此外，在SVM算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如，Suykens提出的最小二乘支持向量机(LeastSquareSupportVectorMachine，LS—SVM)算法，Joachims等人提出的SVM-1ight，张学工提出的中心支持向量机(CentralSupportVectorMachine，CSVM)，Scholkoph和Smola基于二次规划提出的v-SVM等。此后，台湾2大学林智仁(LinChih-Jen)教授等对SVM的典型应用进行总结，并设计开发出较为完善的SVM工具包，也就是LIBSVM(ALibraryforSupportVectorMachines)。上述改进模型中，v-SVM是一种软间隔分类器模型，其原理是通过引进参数v，来调整支持向量数占输入数据比例的下限，以及参数来度量超平面偏差，代替通常依靠经验选取的软间隔分类惩罚参数，改善分类效果；LS-SVM则是用等式约束代替传统SVM中的不等式约束，将求解QP问题变成解一组等式方程来提高算法效率；LIBSVM是一个通用的SVM软件包，可以解决分类、回归以及分布估计等问题，它提供常用的几种核函数可由用户选择，并且具有不平衡样本加权和多类分类等功能，此外，交叉验证(crossvalidation)方法也是LIBSVM对核函数参数选取问题所做的一个突出贡献；SVM-1ight的特点则是通过引进缩水(shrinking)逐步简化QP问题，以及缓存(caching)技术降低迭代运算的计算代价来解决大规模样本条件下SVM学习的复杂性问题。2、支持向量机基础2.1统计学习理论基础与传统统计学理论相比，统计学习理论(Statisticallearningtheory或SLT)是一种专门研究小样本条件下机器学习规律的理论。该理论是针对小样本统计问题建立起的一套新型理论体系，在该体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在有限信息条件下得到最优结果。Vapnik等人从上世纪六、七十年代开始致力于该领域研究，直到九十年代中期，有限样本条件下的机器学习理论才逐渐成熟起来，形成了比较完善的理论体系——统计学习理论。统计学习理论的主要核心内容包括：(1)经验风险最小化准则下统计学习一致性条件；(2)这些条件下关于统计学习方法推广性的界的结论；(3)这些界的基础上建立的小样本归纳推理准则；(4)发现新的准则的实际方法(算法)。2.2SVM原理SVM方法是20世纪90年代初Vapnik等人根据统计学习理论提出的一种新的机3器学习方法，它以结构风险最小化原则为理论基础，通过适当地选择函数子集及该子集中的判别函数，使学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试集的测试误差仍然较小。支持向量机的基本思想是：首先，在线性可分情况下，在原空间寻找两类样本的最优分类超平面。在线性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维输入空间的样本映射到高维属性空间使其变为线性情况，从而使得在高维属性空间采用线性算法对样本的非线性进行分析成为可能，并在该特征空间中寻找最优分类超平面。其次，它通过使用结构风险最小化原理在属性空间构建最优分类超平面，使得分类器得到全局最优，并在整个样本空间的期望风险以某个概率满足一定上界。其突出的优点表现在：(1)基于统计学习理论中结构风险最小化原则和VC维理论，具有良好的泛化能力，即由有限的训练样本得到的小的误差能够保证使独立的测试集仍保持小的误差。(2)支持向量机的求解问题对应的是一个凸优化问题，因此局部最优解一定是全局最优解。(3)核函数的成功应用，将非线性问题转化为线性问题求解。(4)分类间隔的最大化，使得支持向量机算法具有较好的鲁棒性。由于SVM自身的突出优势，因此被越来越多的研究人员作为强有力的学习工具，以解决模式识别、回归估计等领域的难题。3支持向量机相关理论3.1学习问题产生器（G），随机产生向量，它带有一定但未知的概率分布函数F(x)训练器（S）,条件概率分布函数F(y|x)，期望响应y和输入向量x关系为y=f(x,v)学习机器（LM）,输入-输出映射函数集y=f(x,w)，wW，W是参数集合。学习问题就是从给定的函数集f(x,w),wW中选择出能够最好的逼近训练器响应的函数。而这种选择是基于训练集的，训练集由根据联合分布xxy_yGSLM4F(x,y)=F(x)F(y|x)抽取的n个独立同分布样本(xi,yi)，i=1,2,…,n组成。3.2学习问题的表示学习的目的就是，在联合概率分布函数F(x,y)未知、所有可用的信息都包含在训练集中的情况下，寻找函数f(x,w0)，使它（在函数类f(x,w)，(wW）上最小化风险泛函模式识别问题3.3经验风险最小化原则(ERM)1、最小化经验风险(训练样本错误率)：函数集Fk={F(x,w);w∈Wk},k=1,2,…,nF1F2…FnVC维：h1≤h2≤…≤hn在使保证风险（风险的上界）最小的子集中选择使经验风险最小的函数2、ERM的缺点用ERM准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法。这种思想却在多年的机器学习方法研究中占据了主要地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上。实际上，即使可以假定当n趋向于无穷大时经验风险也不一定趋近于期望风险，在很多问题中的样本数目也离无穷大相去甚远，如神经网络。),()),(,()(yxdFwxfyLwRw)f(x,y1w)f(x,y,0)),(,(，若若wxfyLNiiiempwxfdLnwR1)),(,(1)(53.4Vapnik-Chervonenkis(VC)维1、定义：VC维是对由学习机器能够实现的分类函数族的容量或表达力的测度。分类函数集={f(x,w):w∈W}的VC维是能被机器对于分类函数的所有可能二分标志无错学习的训练样本的最大数量，描述了学习机器的复杂性2、学习机器实际风险的界其中n样本数量，h是VC维，Φ是递减函数两种方法：神经网络:保持置信范围固定（通过选择一个适当构造的机器）并最小化经验风险。支持向量机(SVM):保持经验风险固定（比如等于零）并最小化置信范围。结构风险最小化原则函数集Fk={F(x,w);w∈Wk},k=1,2,…,nF1F2…FnVC维：h1≤h2≤…≤hn3.5支持向量回归机SVM本身是针对经典的二分类问题提出的，支持向量回归机（SupportVectorRegression，SVR）是支持向量在函数回归领域的应用。SVR与SVM分类有以下不同：SVM回归的样本点只有一类，所寻求的最优超平面不是使两类样本点分得“最开”，而是使所有样本点离超平面的“总偏差”最小。这时样本点都在两条边界线之间，求最优回归超平面同样等价于求最大间隔。3.5.1SVR基本模型对于线性情况，支持向量机函数拟合首先考虑用线性回归函数bxxf)(拟合niyxii,...,2,1),,(，niRx为输入量，Ryi为输出量，即需要确定和b。)()()(hnwRwRemp6图3-3aSVR结构图图3-3b不灵敏度函数惩罚函数是学习模型在学习过程中对误差的一种度量，一般在模型学习前己经选定，不同的学习问题对应的损失函数一般也不同，同一学习问题选取不同的损失函数得到的模型也不一样。常用的惩罚函数形式及密度函数如表3-1。表3-1常用的损失函数和相应的密度函数损失函数名称损失函数表达式()ic噪声密度()ip-不敏感i1exp()2(1)i拉普拉斯i1exp()2i高斯212i21exp()22i鲁棒损失21(),if;2,otherwise;2iii2exp(),2exp(),2iiiifotherwise多项式1pipexp()2(1/)pipp分段多项式11,1,piipiifppotherwisep1exp(),1exp(),piipiifppotherwisep标准支持向量机采用-不灵敏度函数，即假设所有训练数据在精度下用线性函数拟合如图（3-3a）所示，7**()()1,2,...,,0iiiiiiiiyfxfxyin（3.11）式中，*,ii是松弛因子，当划分有误差时，，*i都大于0，误差不存在取0。这时，该问题转化为求优化目标函数最小化问题：niiiCR1**)(21),,(（3.12）式（3.12）中第一项使拟合函数更为平坦，从而提高泛化能力；第二项为减小误差；常数0C表示对超出误差的样本的惩罚程度。求解式（3.11）和式（3.12）可看出，这是一个凸二次优化问题，所以引入Lagrange函数：*11****111()[()]2[()]()nniiiiiiiinniiiiiiiiiiLCyfxyfx（3.13）式中，，0*i，i，0*i，为Lagrange乘数，ni,...,2,1。求函数L对，b，i，*i的最小化，对i，*i，i，*i的最大化，代入Lagrange函数得到对偶形式，最大化函数：***1,1**111(,)()()()2()()niijjijijnniiiiiiiWxxy（3.14）其约束条件为：*1*()00,niiiiiC（3.15）求解式（3.14）、（3.15）式其实也是一个求解二次规划问题，由Kuhn-Tucker定理，在鞍点处有：****[()]0[()]000iiiiiiiiiiiiyfxyfx（3.16）得出0*ii，表明i，*i不能同时为零，还可以得出：8**()0()0iiiiCC（3.1