`
happmaoo
  • 浏览: 4309603 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

基于统计学习理论的支持向量机算法研究

阅读更多

转自网友blog:

http://www.blog.edu.cn/user2/25835/archives/2005/210242.shtml

基于统计学习理论的支持向量机算法研究 1 理论背景基于数据的机器学习是现代智能技术中的重要方面,研究从观测数据(样本)出发寻找规律,利用这些规律对未来数据或无法观测的数据进行预测。迄今为止,关于机器学习还没有一种被共同接受的理论框架,关于其实现方法大致可以分为三种[3]:第一种是经典的(参数)统计估计方法。包括模式识别、神经网络等在内,现有机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的,在这种方法中,参数的相关形式是已知的,训练样本用来估计参数的值。这种方法有很大的局限性,首先,它需要已知样本分布形式,这需要花费很大代价,还有,传统统计学研究的是样本数目趋于无穷大时的渐近理论,现有学习方法也多是基于此假设。但在实际问题中,样本数往往是有限的,因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。第二种方法是经验非线性方法,如人工神经网络(ANN)。这种方法利用已知样本建立非线性模型,克服了传统参数估计方法的困难。但是,这种方法缺乏一种统一的数学理论。与传统统计学相比,统计学习理论(Statistical Learning Theory或SLT)是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系,在这种体系下的统计推理规则不仅考虑了对渐近性能的要求,而且追求在现有有限信息的条件下得到最优结果。V. Vapnik等人从六、七十年代开始致力于此方面研究[1],到九十年代中期,随着其理论的不断发展和成熟,也由于神经网络等学习方法在理论上缺乏实质性进展,统计学习理论开始受到越来越广泛的重视。统计学习理论的一个核心概念就是VC维(VC Dimension)概念,它是描述函数集或学习机器的复杂性或者说是学习能力(Capacity of the machine)的一个重要指标,在此概念基础上发展出了一系列关于统计学习的一致性(Consistency)、收敛速度、推广性能(Generalization Performance)等的重要结论。统计学习理论是建立在一套较坚实的理论基础之上的,为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中,有望帮助解决许多原来难以解决的问题(比如神经网络结构选择问题、局部极小点问题等);同时,这一理论基础上发展了一种新的通用学习方法──支持向量机(Support Vector Machine或SVM),已初步表现出很多优于已有方法的性能。一些学者认为,SLT和SVM正在成为继神经网络研究之后新的研究热点,并将推动机器学习理论和技术有重大的发展。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度,Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以期获得最好的推广能力(Generalizatin Ability)。支持向量机方法的几个主要优点有: 1. 它是专门针对有限样本情况的,其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值; 2. 算法最终将转化成为一个二次型寻优问题,从理论上说,得到的将是全局最优点,解决了在神经网络方法中无法避免的局部极值问题; 3. 算法将实际问题通过非线性变换转换到高维的特征空间(Feature Space),在高维空间中构造线性判别函数来实现原空间中的非线性判别函数,特殊性质能保证机器有较好的推广能力,同时它巧妙地解决了维数问题,其算法复杂度与样本维数无关;在SVM方法中,只要定义不同的内积函数,就可以实现多项式逼近、贝叶斯分类器、径向基函数(Radial Basic Function或RBF)方法、多层感知器网络等许多现有学习算法。统计学习理论从七十年代末诞生,到九十年代之前都处在初级研究和理论准备阶段,近几年才逐渐得到重视,其本身也趋向完善,并产生了支持向量机这一将这种理论付诸实现的有效的机器学习方法。目前,SVM算法在模式识别、回归估计、概率密度函数估计等方面都有应用。例如,在模式识别方面,对于手写数字识别、语音识别、人脸图像识别、文章分类等问题,SVM算法在精度上已经超过传统的学习算法或与之不相上下。目前,国际上对这一理论的讨论和进一步研究逐渐广泛,而我国国内尚未在此领域开展研究,因此我们需要及时学习掌握有关理论,开展有效的研究工作,使我们在这一有着重要意义的领域中能够尽快赶上国际先进水平。由于SLT理论和SVM方法尚处在发展阶段,很多方面尚不完善,比如:许多理论目前还只有理论上的意义,尚不能在实际算法中实现;而有关SVM算法某些理论解释也并非完美(J.C.Burges在[2]中就曾提到结构风险最小原理并不能严格证明SVM为什么有好的推广能力);此外,对于一个实际的学习机器的VC维的分析尚没有通用的方法;SVM方法中如何根据具体问题选择适当的内积函数也没有理论依据。因此,在这方面我们可做的事情是很多的。 2方法介绍 SVM是从线性可分情况下的最优分类面发展而来的,基本思想可用图1的两维情况说明。图中,实心点和空心点代表两类样本,H为分类线,H1、H2分别为过各类中离分类线最近的样本且平行于分类线的直线,它们之间的距离叫做分类间隔(margin)。所谓最优分类线就是要求分类线不但能将两类正确分开(训练错误率为0),而且使分类间隔最大。分类线方程为 ,我们可以对它进行归一化,使得对线性可分的样本集 , , , ,满足 (1) 此时分类间隔等于2/||w||,使间隔最大等价于使||w||2最小。满足条件(1)且使 最小的分类面就叫做最优分类面,H1、H2上的训练样本点就称作支持向量。利用Lagrange优化方法可以把上述最优分类面问题转化为其对偶问题[2],即:在约束条件 , (2a) 和 ai ³ 0 i=1,¼n (2b) 下对ai求解下列函数的最大值: (3) ai为原问题中与每个约束条件(1)对应的Lagrange乘子。这是一个不等式约束下二次函数寻优的问题,存在唯一解。容易证明,解中将只有一部分(通常是少部分)ai不为零,对应的样本就是支持向量。解上述问题后得到的最优分类函数是 , (4) 式中的求和实际上只对支持向量进行。b*是分类阈值,可以用任一个支持向量(满足(1)中的等号)求得,或通过两类中任意一对支持向量取中值求得。对非线性问题,可以通过非线性变换转化为某个高维空间中的线性问题,在变换空间求最优分类面。这种变换可能比较复杂,因此这种思路在一般情况下不易实现。但是注意到,在上面的对偶问题中,不论是寻优目标函数(3)还是分类函数(4)都只涉及训练样本之间的内积运算 。设有非线性映射Φ : Rd ® H将输入空间的样本映射到高维(可能是无穷维)的特征空间H中。当在特征空间H中构造最优超平面时,训练算法仅使用空间中的点积,即Φ(xi).Φ(xj),而没有单独的Φ(xi)出现。因此,如果能够找到一个函数K使得K( xi , xj )=Φ(xi).Φ(xj),这样,在高维空间实际上只需进行内积运算,而这种内积运算是可以用原空间中的函数实现的,我们甚至没有必要知道变换Φ的形式。根据泛函的有关理论,只要一种核函数K( xi,xj)满足Mercer条件,它就对应某一变换空间中的内积。因此,在最优分类面中采用适当的内积函数K( xi,xj)就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加,此时目标函数(3)变为: , (5) 而相应的分类函数也变为 , (6) 这就是支持向量机。这一特点提供了解决算法可能导致的“维数灾难”问题的方法:在构造判别函数时,不是对输入空间的样本作非线性变换,然后在特征空间中求解;而是先在输入空间比较向量(例如求点积或是某种距离),对结果再作非线性变换[9]。这样,大的工作量将在输入空间而不是在高维特征空间中完成。SVM分类函数形式上类似于一个神经网络,输出是s中间节点的线性组合,每个中间节点对应一个支持向量,如图2所示。函数K称为点积的卷积核函数,根据[2],它可以看作在样本之间定义的一种距离。 图2 支持向量机示意图 显然,上面的方法在保证训练样本全部被正确分类,即经验风险Remp为0的前提下,通过最大化分类间隔来获得最好的推广性能。如果希望在经验风险和推广性能之间求得某种均衡,可以通过引入正的松弛因子ξi来允许错分样本的存在。这时,约束(1)变为 (7) 而在目标——最小化 ——中加入惩罚项 ,这样,Wolf对偶问题可以写成: Maximize: (8) s.t. (9a) 0 £ ai £ C i=1,¼n (9b) 这就是SVM方法的最一般的表述。为了方便后面的陈述,这里我们对对偶问题的最优解做一些推导。定义 (10) (11) 对偶问题的Lagrange函数可以写成: (12) KKT条件为 (13a) (13b) mi (ai - C ) = 0 " i (13c) 由此,我们可以推导出如下关系式: l 若ai = 0 则 di ³ 0 mi = 0 Þ (Fi - bi )yi ³ 0 (14a) l 若0 < ai < C 则 di = 0 mi = 0 Þ (Fi - bi )yi = 0 (14b) l 若 ai = C 则 di = 0 mi ³ 0 Þ (Fi - bi )yi £ 0 (14c) 由于KKT条件是最优解应满足的充要条件[6],所以目前提出的一些算法几乎都是以是否违反KKT条件作为迭代策略的准则。
分享到:
评论

相关推荐

    基于统计学习理论的支持向量机算法研究.caj

    目前,统计学习理论和支持向量机作为小样本学习的最佳理论,开始受到越来越广泛的重视,正在成为人工智能和机器学习领域新的研究热点。本论文研究的主要内容包括以下几个方面:支持向量机算法、多输出支持向量回归、多类...

    支持向量机算法的研究及其应用

    研究了目前超球面支持向量机算法,它们的目标函数中缺少了使分类间隔尽量大这个条件,而这个条件是统计学习理论中结构风险最小化的体现,直接反映了算法的推广能力。因此,提出了一种新的超球面支持向量机算法,具有...

    支持向量机理论与算法研究综述_丁世飞.pdf

    统计学习理论(statistical learning theory,SLT)是一种小样本...该文系统介绍了支持向量机的理论基础,综述了传统支持向量机的主流训练算法以及一些新型的学习模型和算法,最后指出了支持向量机的研究方向与发展前景。

    支持向量机理论与算法研究综述

    统计学习理论(statistical learning theory,SLT)是一种小样本...该文系统介绍了支持向量机的理论基础,综述了传统支持向量机的主流训练算法以及一些新型的学习模型和算法,最后指出了支持向量机的研究方向与发展前景。

    基于统计学习理论的支持向量机的分类方法

    支持向量机是一种新型机器学习方法,由于其出色的学习...用于分类的支持向量机的统计学习理论基础,在此基础上提出了支持向量机的分类算法,讨论了支持向量机存在的问题, 对用于分类的支持向量机的应用前景进行了展望。

    基于分解技术的并行支持向量机算法

    基于分解技术的并行支持向量机算法,李明强,韩丛英,支持向量机是以统计学习理论为基础的新型的机器学习方法,近年来已经成为机器学习领域一个新的研究热点。由于传统的优化算法在处

    关于统计学习理论与支持向量机

    新的通用学习算法——支持向量机(SVM ) , 能够较好的解决小样本学习问题. 目前, SL T 和 SVM 已成为国际上机器学习领域新的研究热点. 本文是一篇综述, 旨在介绍SL T 和SVM 的 基本思想、特点和研究发展现状, 以引起...

    基于支持向量机的机器学习研究 Research of Machine-Learning Based Support Vector Machine

     本文对机器学习、支持向量机的研究现状及应用领域进行了综述,阐述了机器学习和支持向量机的基本概念、基本模型和支持向量机的训练算法。针对机器学习系统的具体结构,提出了机器学习系统的模块化设计,划分出了输入...

    论文研究-基于支持向量机的虹膜识别方法研究 .pdf

    基于支持向量机的虹膜识别方法研究,王勇,,为了提高虹膜识别的准确性和稳定性,本文研究了统计学习理论的支持向量机学习算法,在该研究的基础上,将二维分类问题扩展到虹膜特征

    支持向量机分类算法研究与应用 Research on Classification Algorithm of Support Vector Machine an

    基于统计学习理论的支持向量机算法具有理论完备、全局优化、适应性强、推广能力好等优点,是机器学习研究的新热点。它在最小化经验风险的同时,有效提高了算法的泛化能力,具有良好的应用价值和发展前景。本文首先系统...

    支持向量机应用于恶意代码检测

    持向量机是自上世纪90年代提出的一种基于统计学习理论的机器学习算法。与传统统计学研究样本产生的规律或样本数目趋于无穷大时的渐进性能不同,它更注重研究样本本身所提供的信息,所以特别适合于小样本问题。 本...

    论文研究-支持向量机训练算法的实验比较.pdf

    SVM是基于统计学习理论的结构风险最小化原则的,它将最大分界面分类器思想和基于核的方法结合在一起,表现出了很好的泛化能力。并对目前的三种主流算法SVMlight,Bsvm与SvmFu在人脸检测、MNIST和USPS手写数字识别等...

    论文研究-基于支持向量机的导航星选取算法研究.pdf

    而基于统计学习理论( SLT) 的支持向量机( SVM) 方法正好克服了这方面的不足。SLT 理论和SVM 方法为导航星选取过程的简化和结果的最优性的获得提供了新的途径。讨论了支持向量机在导航星选取优化中进行应用的分类算法...

    改进的模糊多类支持向量机算法在瓦斯预警中的应用

    支持向量机是在瓦斯预警中广泛使用的一种技术,以统计学习理论和支持向量机为基础,通过研究基于模糊支持向量机的多类分类方法,对原算法进行改进,采用模糊多类支持向量机,并构造模糊隶属函数,同时使用序列最小最优化...

    支持向量机回归算法与应用研究 Algorithm and Application Research of Support Vector Machine Reg

    统计学习理论(SLT)是一种专门研究小样本情况下机器学习规律的理论,它建立在一套较坚实的理论基础之上的,为解决有限样本学习问题提供了一个统一的框架也发展了一种新的通用学习方法一支持向量机(SVM),较好的解决小...

    支持向量机与神经网络的区别

    而支持向量机有严格的理论和数学基础,基于结构风险最小化原则, 泛化能力优于前者,算法具有全局最优性, 是针对小样本统计的理论。 目前来看,虽然二者均为机器学习领域非常流行的方法,但后者在很多方面的应用一般...

Global site tag (gtag.js) - Google Analytics