文档介绍:该【特选支持向量机原理及应用(doc) 】是由【朱老师】上传分享,文档一共【18】页,该文档可以免费在线阅读,需要了解更多关于【特选支持向量机原理及应用(doc) 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。支持向量机原理及应用(DOC)
3
支持向量机简介
摘要:支持向量机方法是建立在统计学****理论的VC维理论和结构风险最小原理根底上的,根据有限的样本信息在模型的复杂性〔即对特定训练样本的学****精度〕和学****能力〔即无错误地识别任意样本的能力〕之间寻求最正确折衷,以求获得最好的推广能力。我们通常希望分类的过程是一个机器学****的过程。这些数据点是n维实空间中的点。我们希望能够把这些点通过一个n-1维的超平面分开。通常这个被称为线性分类器。有很多分类器都符合这个要求。但是我们还希望找到分类最正确的平面,即使得属于两个不同类的数据点间隔最大的那个面,该面亦称为最大间隔超平面。如果我们能够找到这个面,那么这个分类器就称为最大间隔分类器。
关键字:VC理论结构风险最小原那么学****能力
1、SVM的产生与开展
自1995年Vapnik在统计学****理论的根底上提出SVM作为模式识别的新方法之后,SVM一直倍受关注。同年,Vapnik和Cortes提出软间隔(softmargin)SVM,通过引进松弛变量度量数据的误分类(分类出现错误时大于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等。此后,台湾大学林智仁
3
(LinChih-Jen)教授等对SVM的典型应用进行总结,并设计开发出较为完善的SVM工具包,也就是LIBSVM(ALibraryforSupportVectorMachines)。上述改进模型中,v-SVM是一种软间隔分类器模型,其原理是通过引进参数v,来调整支持向量数占输入数据比例的下限,以及参数来度量超平面偏差,代替通常依靠经验选取的软间隔分类惩罚参数,改善分类效果;LS-SVM那么是用等式约束代替传统SVM中的不等式约束,将求解QP问题变成解一组等式方程来提高算法效率;LIBSVM是一个通用的SVM软件包,可以解决分类、回归以及分布估计等问题,它提供常用的几种核函数可由用户选择,并且具有不平衡样本加权和多类分类等功能,此外,交叉验证(crossvalidation)方法也是LIBSVM对核函数参数选取问题所做的一个突出奉献;SVM-1ight的特点那么是通过引进缩水(shrinking)逐步简化QP问题,以及缓存(caching)技术降低迭代运算的计算代价来解决大规模样本条件下SVM学****的复杂性问题。
2、支持向量机根底
与传统统计学理论相比,统计学****理论(Statisticallearningtheory或SLT)是一种专门研究小样本条件下机器学****规律的理论。该理论是针对小样本统计问题建立起的一套新型理论体系,在该体系下的统计推理规那么不仅考虑了对渐近性能的要求,而且追求在有限信息条件下得到最优结果。Vapnik等人从上世纪六、七十年代开始致力于该领域研究,直到九十年代中期,有限样本条件下的机器学****理论才逐渐成熟起来,形成了比较完善的理论体系——统计学****理论。
统计学****理论的主要核心内容包括:(1)经验风险最小化准那么下统计学****一致性条件;(2)这些条件下关于统计学****方法推广性的界的结论;(3)这些界的根底上建立的小样本归纳推理准那么;(4)发现新的准那么的实际方法(算法)。
5
SVM方法是20世纪90年代初Vapnik等人根据统计学****理论提出的一种新的机器学****方法,它以结构风险最小化原那么为理论根底,通过适当地选择函数子集及该子集中的判别函数,使学****机器的实际风险到达最小,保证了通过有限训练样本得到的小误差分类器,对独立测试集的测试误差仍然较小。
支持向量机的根本思想是:首先,在线性可分情况下,在原空间寻找两类样本的最优分类超平面。在线性不可分的情况下,参加了松弛变量进行分析,通过使用非线性映射将低维输入空间的样本映射到高维属性空间使其变为线性情况,从而使得在高维属性空间采用线性算法对样本的非线性进行分析成为可能,并在该特征空间中寻找最优分类超平面。其次,它通过使用结构风险最小化原理在属性空间构建最优分类超平面,使得分类器得到全局最优,并在整个样本空间的期望风险以某个概率满足一定上界。
其突出的优点表现在:(1)基于统计学****理论中结构风险最小化原那么和VC维理论,具有良好的泛化能力,即由有限的训练样本得到的小的误差能够保证使独立的测试集仍保持小的误差。(2)支持向量机的求解问题对应的是一个凸优化问题,因此局部最优解一定是全局最优解。(3)核函数的成功应用,将非线性问题转化为线性问题求解。(4)分类间隔的最大化,使得支持向量机算法具有较好的鲁棒性。由于SVM自身的突出优势,因此被越来越多的研究人员作为强有力的学****工具,以解决模式识别、回归估计等领域的难题。
3支持向量机相关理论
产生器〔G〕,随机产生向量,它带有一定但未知的概率分布函数F(x)
训练器〔S〕,条件概率分布函数F(y|x),期望响应y和输入向量x关系为y=f(x,v)
5
学****机器〔LM〕,输入-输出映射函数集y=f(x,w),wW,W是参数集合。
学****问题就是从给定的函数集f(x,w),wW中选择出能够最好的逼近训练器响应的函数。而这种选择是基于训练集的,训练集由根据联合分布F(x,y)=F(x)F(y|x)抽取的n个独立同分布样本
(xi,yi),i=1,2,…,n 组成。
学****的目的就是,在联合概率分布函数F(x,y)未知、所有可用的信息都包含在训练集中的情况下,寻找函数f(x,w0),使它〔在函数类f(x,w),(wW〕上最小化风险泛函
模式识别问题
(ERM)
1、最小化经验风险(训练样本错误率):
函数集Fk={F(x,w);w∈Wk},k=1,2,…,n
F1F2…Fn
VC维:h1≤h2≤…≤hn
在使保证风险〔风险的上界〕最小的子集中选择使经验风险最小的函数
6
2、ERM的缺点
用ERM准那么代替期望风险最小化并没有经过充分的理论论证,只是直观上合理的想当然做法。
这种思想却在多年的机器学****方法研究中占据了主要地位。人们多年来将大局部注意力集中到如何更好地最小化经验风险上。
实际上,即使可以假定当n趋向于无穷大时经验风险也不一定趋近于期望风险,在很多问题中的样本数目也离无穷大相去甚远,如神经网络。
-Chervonenkis(VC)维
1、定义:VC维是对由学****机器能够实现的分类函数族的容量或表达力的测度。
分类函数集={f(x,w):w∈W}的VC维是能被机器对于分类函数的所有可能二分标志无错学****的训练样本的最大数量,描述了学****机器的复杂性
2、学****机器实际风险的界
其中n样本数量,h是VC维,Φ是递减函数
两种方法:
神经网络:保持置信范围固定〔通过选择一个适当构造的机器〕并最小化经验风险。
支持向量机(SVM):保持经验风险固定〔比方等于零〕并最小化置信范围。
结构风险最小化原那么
函数集Fk={F(x,w);w∈Wk},k=1,2,…,n
F1F2…Fn
VC维:h1≤h2≤…≤hn
7
SVM本身是针对经典的二分类问题提出的,支持向量回归机〔SupportVectorRegression,SVR〕是支持向量在函数回归领域的应用。SVR与SVM分类有以下不同:SVM回归的样本点只有一类,所寻求的最优超平面不是使两类样本点分得“最开〞,而是使所有样本点离超平面的“总偏差〞最小。这时样本点都在两条边界线之间,求最优回归超平面同样等价于求最大间隔。
对于线性情况,支持向量机函数拟合首先考虑用线性回归函数拟合,为输入量,为输出量,即需要确定和。
图3-3aSVR结构图图3-3b不灵敏度函数
惩罚函数是学****模型在学****过程中对误差的一种度量,一般在模型学****前己经选定,不同的学****问题对应的损失函数一般也不同,同一学****问题选取不同的损失函数得到的模型也不一样。常用的惩罚函数形式及密度函数如表3-1。
表3-1常用的损失函数和相应的密度函数
损失函数名称
损失函数表达式
噪声密度
-不敏感
拉普拉斯
高斯
8
鲁棒损失
多项式
分段多项式
标准支持向量机采用-不灵敏度函数,即假设所有训练数据在精度下用线性函数拟合如图〔3-3a〕所示,
〔〕
式中,是松弛因子,当划分有误差时,,都大于0,误差不存在取0。这时,该问题转化为求优化目标函数最小化问题:
〔〕
式〔〕中第一项使拟合函数更为平坦,从而提高泛化能力;第二项为减小误差;常数表示对超出误差的样本的惩罚程度。求解式〔〕和式〔〕可看出,这是一个凸二次优化问题,所以引入Lagrange函数:
〔〕
式中,,,,,为Lagrange乘数,。求函数对,,,的最小化,对,,,的最大化,代入Lagrange函数得到对偶形式,最大化函数:
9
〔〕
其约束条件为:
〔〕
求解式〔〕、〔〕式其实也是一个求解二次规划问题,由Kuhn-Tucker定理,在鞍点处有:
〔〕
得出,说明,不能同时为零,还可以得出:
〔〕
从式〔〕可得出,当,或时,可能大于,与其对应的称为边界支持向量〔BoundarySupportVector,BSV〕,对应图3-3a中虚线带以外的点;当时,,即,,与其对应的称为标准支持向量〔NormalSupportVector,NSV〕,对应图3-3a中落在管道上的数据点;当,时,与其对应的为非支持向量,对应图3-3a中管道内的点,它们对没有奉献。因此越大,支持向量数越少。对于标准支持向量,如果,此时,由式〔〕可以求出参数:
同样,对于满足的标准支持向量,有
10
一般对所有标准支持向量分别计算的值,然后求平均值,即
〔〕
因此根据样本点求得的线性拟合函数为
〔〕
非线性SVR的根本思想是通过事先确定的非线性映射将输入向量映射的一个高维特征空间〔Hilbert空间〕中,然后在此高维空间中再进行线性回归,从而取得在原空间非线性回归的效果。
首先将输入量通过映射映射到高维特征空间中用函数拟合数据,。那么二次规划目标函数〔〕式变为:
〔〕
式〔〕中涉及到高维特征空间点积运算,而且函数是未知的,高维的。支持向量机理论只考虑高维特征空间的点积运算,而不直接使用函数。称为核函数,核函数的选取应使其为高维特征空间的一个点积,核函数的类型有多种,常用的核函数有:
多项式核:;
高斯核:;
RBF核:;
B样条核:;