支持向量机原理及应用

支持向量机简介

摘要:支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以求获得最好的推广能力 。我们通常希望分类的过程是一个机器学习的过程。这些数据点是n维实空间中的点。我们希望能够把这些点通过一个n-1维的超平面分开。通常这个被称为线性分类器。有很多分类器都符合这个要求。但是我们还希望找到分类最佳的平面,即使得属于两个不同类的数据点间隔最大的那个面,该面亦称为最大间隔超平面。如果我们能够找到这个面,那么这个分类器就称为最大间隔分类器。

关键字:VC理论 结构风险最小原则 学习能力

1、SVM的产生与发展

自1995年Vapnik在统计学习理论的基础上提出SVM作为模式识别的新方法之后,SVM一直倍受关注。同年,Vapnik和Cortes提出软间隔(soft margin)SVM,通过引进松弛变量?i度量数据xi的误分类(分类出现错误时?i大于0),同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数),SVM的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程;1996年,Vapnik等人又提出支持向量回归 (Support Vector Regression,SVR)的方法用于解决拟合问题。SVR同SVM的出发点都是寻找最优超平面,但SVR的目的不是找到两种数据的分割平面,而是找到能准确预测数据分布的平面,两者最终都转换为最优化问题的求解;1998年,Weston等人根据SVM原理提出了用于解决多类分类的SVM方法(Multi-Class Support Vector Machines,Multi-SVM),通过将多类分类转化成二类分类,将SVM应用于多分类问题的判断:此外,在SVM算法的基本框架下,研究者针对不同的方面提出了很多相关的改进算法。例如,Suykens提出的最小二乘支持向量机 (Least Square Support Vector Machine,LS—SVM)算法,Joachims等人提出的SVM-1ight,张学工提出的中心支持向量机 (Central Support Vector Machine,CSVM),Scholkoph和Smola基于二次规划提出的v-SVM等。此后,台湾

1

大学林智仁(Lin Chih-Jen)教授等对SVM的典型应用进行总结,并设计开发出较为完善的SVM工具包,也就是LIBSVM(A Library for Support Vector Machines)。上述改进模型中,v-SVM是一种软间隔分类器模型,其原理是通过引进参数v,来调整支持向量数占输入数据比例的下限,以及参数?来度量超平面偏差,代替通常依靠经验选取的软间隔分类惩罚参数,改善分类效果;LS-SVM则是用等式约束代替传统SVM中的不等式约束,将求解QP问题变成解一组等式方程来提高算法效率;LIBSVM是一个通用的SVM软件包,可以解决分类、回归以及分布估计等问题,它提供常用的几种核函数可由用户选择,并且具有不平衡样本加权和多类分类等功能,此外,交叉验证(cross validation)方法也是LIBSVM对核函数参数选取问题所做的一个突出贡献;SVM-1ight的特点则是通过引进缩水(shrinking)逐步简化QP问题,以及缓存(caching)技术降低迭代运算的计算代价来解决大规模样本条件下SVM学习的复杂性问题。

2、支持向量机基础

2.1 统计学习理论基础

与传统统计学理论相比,统计学习理论(Statistical learning theory或SLT)是一种专门研究小样本条件下机器学习规律的理论。该理论是针对小样本统计问题建立起的一套新型理论体系,在该体系下的统计推理规则不仅考虑了对渐近性能的要求,而且追求在有限信息条件下得到最优结果。Vapnik等人从上世纪六、七十年代开始致力于该领域研究,直到九十年代中期,有限样本条件下的机器学习理论才逐渐成熟起来,形成了比较完善的理论体系——统计学习理论。

统计学习理论的主要核心内容包括:(1)经验风险最小化准则下统计学习一致性条件;(2)这些条件下关于统计学习方法推广性的界的结论;(3)这些界的基础上建立的小样本归纳推理准则;(4)发现新的准则的实际方法(算法)。

2.2 SVM原理

SVM方法是20世纪90年代初Vapnik等人根据统计学习理论提出的一种新的机

2

器学习方法,它以结构风险最小化原则为理论基础,通过适当地选择函数子集及该子集中的判别函数,使学习机器的实际风险达到最小,保证了通过有限训练样本得到的小误差分类器,对独立测试集的测试误差仍然较小。

支持向量机的基本思想是:首先,在线性可分情况下,在原空间寻找两类样本的最优分类超平面。在线性不可分的情况下,加入了松弛变量进行分析,通过使用非线性映射将低维输入空间的样本映射到高维属性空间使其变为线性情况,从而使得在高维属性空间采用线性算法对样本的非线性进行分析成为可能,并在该特征空间中寻找最优分类超平面。其次,它通过使用结构风险最小化原理在属性空间构建最优分类超平面,使得分类器得到全局最优,并在整个样本空间的期望风险以某个概率满足一定上界。

其突出的优点表现在:(1)基于统计学习理论中结构风险最小化原则和VC维理论,具有良好的泛化能力,即由有限的训练样本得到的小的误差能够保证使独立的测试集仍保持小的误差。(2)支持向量机的求解问题对应的是一个凸优化问题,因此局部最优解一定是全局最优解。(3)核函数的成功应用,将非线性问题转化为线性问题求解。(4)分类间隔的最大化,使得支持向量机算法具有较好的鲁棒性。由于SVM自身的突出优势,因此被越来越多的研究人员作为强有力的学习工具,以解决模式识别、回归估计等领域的难题。

3 支持向量机相关理论

3.1 学习问题

G

x S LM y _ y ? 产生器(G),随机产生向量 ,它带有一定但未知的概率分布函数F(x) ? 训练器(S),条件概率分布函数F(y|x) ,期望响应y和输入向量x关系为

y=f(x,v)

? 学习机器(LM),输入-输出映射函数集y=f(x,w),w W,W是参数集合。 ? 学习问题就是从给定的函数集f(x,w),w W中选择出能够最好的逼近训练

器响应的函数。而这种选择是基于训练集的,训练集由根据联合分布

3

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4