svm算法的泛化性能

svm算法的泛化性能

1svm的应用,源于数学人工智能是继专家系统以来的另一个重要研究领域，也是人工智能和神经计算的中心主题之一。对学习算法的创新可以极大地推动整个神经网络的发展。大多数机器学习算法的研究包括对数据的预测。目的是评估已知数据的相关性，并预测未来的情况。近年来，基于神经网络、灵活性统计和统计力学的学习算法取得了一些进展，两位科学家提出了一些新的概念和方法。从表面上看，这些概念和方法之间存在一些联系，但事实上，它们之间存在许多差异。人们需要一个完整的理论体系来预测学习算法。最近出现的VC理论(Vapnik-Chervonenkis)将学习问题的相关概念和原理进行了很好的结合,它比基于直觉和生物理论等经验性机器学习方法更有说服力,VC理论被认为是从有限数据中预测相关性的统一数学框架.尽管VC理论作为数学理论已出现了25年,但人们还没有充分体会和完全欣赏到它的理论和实际价值,近期的研究已经表明VC理论可以改善各种各样的神经网络学习算法.更为重要的是基于VC理论的创造性机器学习方法SVM(SupportVectorMachine)的出现.SVM是由Vapnik领导的AT&TBell实验室研究小组提出的一种新的非常有潜力的分类技术,它开辟了学习高维数据新的天地,这种新的学习算法可以替代多层感知机、RBF神经网络和多项式神经网络已有的学习算法,它也是一种可实现一些表示问题的建设性方法,在多层感知机、RBF神经网络和小波神经网络中有成功运用,同时SVM方法实际中有一些应用(如人面检测、KDD和信号处理)也说明了VC理论的理论和实用价值.1995年,文献和文献的出现是SVM诞生的标志,目前国外学者已取得了一些成果,作者的很多资料都从Internet网络获得,IEEETransactionsonNeuralNetworks也已经出版了关于VC维理论和SVM方面的专辑(见Vol.10(5),1999).但目前在国内,SVM的研究似乎尚未起步.我们曾对神经网络理论进行了较深入的研究,在本文中作者以和神经网络学习算法相比较的方式,介绍SVM理论及其研究进展,目的在于激发国内众多神经网络理论研究者的兴趣,抛砖引玉,以期促进和推动我国该方面的研究.2bp网络学习算法在过去的十年里,人工神经网络理论及其应用的研究是计算机与人工智能、认知科学、数学和物理学等相关专业的热点.由于神经网络具有很强自学习能力,即系统在学习过程中不断完善自己,具有创新特点,它不同于AI中的专家系统,后者只是专家经验的知识库,并不能创新和发展,因而吸引了众多的研究学者,学习算法的研究也成为神经网络研究中的关键问题.1958年,Rosenblatt提出了感知机(Peceptron)的概念,感知机在神经网络的研究中有着重要的地位和意义,它首先提出了自组织、自学习的思想,对能够解决的线性可分问题,有一个非常清楚的收敛算法,并从数学给出了严格的证明.以后的很多模型都是在这种指导思想下建立的,或是它的改进和推广.1986年,Rumelhart和McClelland领导的PDP研究小组在Werbos博士论文的基础上发展了误差反向传播网络学习算法,即BP算法.BP网络可以处理线性不可分问题,具有强大的运算能力,纠正了Minsky等人的片面观点,神经网络的研究也由复兴走向第二次高潮.尽管感知机对线性可分问题,有一个收敛的学习算法,但由于算法的初始值可任意选定,使得由此产生的分离超平面有无穷多种,往往造成了分类超平面严重偏向某一类,即导致了感知机泛化性能不高.另一方面,这种分类算法没能对在分类中起关键作用的训练元素进行刻划,当分类结束后添加新的训练样本时,先前已有的运算结果已无作用,网络须重新学习所有样本,可见这种算法没有真正起到“学习”作用.虽然BP网络通过增加隐层具有了非线性映射逼近能力,在神经网络的研究和应用中占着举足轻重的地位,也为神经网络的研究起过强烈的推动作用,但由于BP网络学习算法实际上是利用梯度下降法调节权值使目标函数达到极小,而目标函数仅为各给定输入和相应输出差的平方和,导致了BP网络过分强调克服学习错误而泛化性能不强.同时BP网络还具有一些其它难以克服的缺陷,如隐单元的个数难以确定,网络的最终权值受初始值影响大等.另外,对在联想记忆中起重要作用的Hopfield网络,它的能量函数也是各给定输入和期望输出差的平方和,因此学习算法与上述情形存在同样的问题.近年来,随着人工神经网络研究的深入,人们更加认识到它存在的严重不足,如尽管众多的研究者已经提出了大量的学习算法,但大都基于克服训练错误,从概率统计的角度说,神经网络的学习算法仅仅试图使经验风险最小化,并没有使期望风险最小化(见3、节4),与传统的最小二乘法相比,在原理上却缺乏实质性的突破,同时也缺乏理论依据.总之,神经网络的学习算法缺乏定量的分析与机理完备的理论结果.3神经网络的风险最小二乘两类模式的识别问题可描述如下:给定决策函数集这里∧为参数集,已知来自于一未知分布P(x,y)一组样本模式识别的目的是在决策函数集中寻求函数,最小化期望风险这里fλ:RN→{-1,1}称为假设函数,集合H={fλ(x):λ∈∧}称为假设空间.对神经网络来说,fλ可以解释为径向基函数或是有一些隐单元的多层感知机形成的非线性映射,在这种情形下,Λ就是网络的权值集合.由于分布P(x,y)未知,因此实际上R(λ)无法计算,因而也就无法最小化期望风险.但由于已知P(x,y)的一些样本点,且当样本点的个数l趋于无穷大时,经验风险趋于期望风险R(λ).很多函数逼近算法,如神经网络的学习算法和最小二乘法正是基于所谓风险最小化原理,即最小化经验风险试图使期望风险最小化.4基于稳定的二值分类函数早在1971年,Vapnik就指出经验风险的最小值未必收敛于期望风险的最小值,即经验风险最小化原理不成立,并且证明了经验风险的最小值收敛于期望风险的最小值当且仅当R(λ)依概率一致收敛于Remp(λ),当且仅当假设空间{fλ(x):λ∈∧}的VC维是有限的.下面首先介绍VC维(Vapnik-Chervonenkisdimension).近年来,数理统计、计算机科学和统计力学都试图对神经网络的信息处理能力进行深刻的分析,各自都取得了一定的进展,这些进展表面看来有很多联系,但实际上又不全相同,这就给问题的综合分析带来一定的困难.VC维被认为是数学和计算机科学中非常重要的定量化概念,它可用来刻画分类系统的性能.但不幸的是,对大部分情形,VC维的精确值无法计算,仅能获得VC维的界,即便如此,也只是对很简单的系统而言的.VC维dVC是通过生长函数Δ(p)来定义的.设X是一集合,C是将X进行二值分类的所有分类函数c:X→{-1,1}的集合.对N个输入和单输出的感知器来说,设X是所有输入向量ζ的集合,ζ∈RN或ζ∈{-1,1}N,分类的结果由二值输出σ=±1来确定,此时C就是所有可能权值和阈值构成的感知器分类映射的集合.对任意p个不同的输入{x1,x2,…,xp},其中xi为N维向量,i=1,2,…,p.定义Δ(p)为网络所有输出构成的p维向量(σ1,σ2,…,σp)集合中不同元素的个数,这里σi为对应于输入xi的输出.由于σ=±1,显然Δ(p)的最大值为2p.根据Sauer引理,对二值分类函数集合C,必存在自然数dVC(可以是无穷大),使得dVC称为二值分类函数集合C的VC维.VC维可以用来描述机器学习中的一些极端情形,而基于统计力学的学习方法仅仅考虑典型情形,但是即使对非常简单的单层感知器,典型情形和最差情形差异都非常巨大.得出基于经验风险最小化原理的学习算法缺乏理论依据只是解决了机器学习问题的一个方面.为了提出理论依据更可靠的学习算法,Vapnik和Chervonenkis深入研究R(λ)和Remp(λ)的关系,得出如下不等式以概率1-η成立:这里h是假设空间H的VC维.从(1)式可以看出,必须使经验风险、VC维和训练集元素个数的比率同时最小化,才能最小化期望风险.由于经验风险通常是VC维h的减函数,对给定元素数目的训练集,应存在最优的h值,使期望风险最小化.对多层感知器和RBF网络来说,计算VC维相当于确定它们隐层单元的数目,这是非常困难的,它本身也是神经网络亟待解决的难题.为了克服VC维难以计算这一缺陷,Vapnik在文献中提出了结构化风险最小化原理(StructureRiskMinimizationPrinciple),它基于(1)式,即为了最小化期望风险,必须同时最小化经验风险和VC维.5svm算法介绍我们知道,训练学习机器的一般方法都是调整参数,使某一定量指标最小化,关键是这个定量指标如何定义才能使学习算法性能优越.神经网络学习算法的指标一般都是仅仅依赖于先验知识,定量指标只定义在训练集上,如BP算法的定量指标就是其网络的目标函数,即学习错误,BP算法采用最速下降法极小化学习错误.但是低的学习错误并不能保证对处理未来数据低的期望错误,这种期望错误可以用来衡量泛化性能,因此寻求一种既有低的学习错误又有好的泛化性能的学习算法非常必要,SVM就是这样一种学习算法,它是结构化风险最小化原理的近似实现,因为它同时最小化经验风险和VC维的界.SVM最初用来解决模式识别问题,目的是发现泛化性能好的决策规则,SupportVectors实际上是训练集的子集,对SupportVectors的最优分类等价于对训练集的分类.下面通过一两类模式识别问题说明SVM算法的由来.设数据集合Class1和Class2是线性可分的,即存在(w,b),使分类的目的是寻求(w,b),最佳分离Classl和Class2,此时假设空间由所有的fω,b=Sign(ω·x+b)组成.为减少分类平面的重复,对(w,b)进行如下约束:满足(2)的超平面称为典型超平面,可以证明典型超平面集合的VC维是N+1,即所有自由参数的数目.如果x1,x2,…,xl位于N维单位球内,集合{fw,b=sign(w·x+b):||w‖≤A}的VC维h满足:当数据点x1,x2,…,xl位于半径为R的球内时,(3)式变为注意到点x到(w,b)确定的超平面的距离为根据约束条件(2)式可知,典型超平面到最近数据点的距离为,显然如果||w‖≤A,典型超平面到最近数据点的距离必然大于或等于,实际上此时典型超平面已将分类的对象由单纯的数据点变为数据点的球形邻域.对线性可分的情形(即经验风险为零),求最佳(w,b)归结为下列二次规划问题:根据(4)式,问题(6)的意思是指在经验风险为零的情形下,使VC维的界最小化,从而最小化VC维,这正是结构风险最小化原理.根据(5)式,最小化||w‖2等价于寻求一种特殊的超平面,它使数据集合Class1和Class2凸包之间沿垂直于自己方向的距离最大,故SVM有时也称为最大边缘(maximummargin)算法.图1明显说明了边缘大小和泛化性能之间的关系.下面利用经典优化中的对偶方法对优化问题(6)进行处理:定义问题(6)的Lagrange函数由于规划问题(6)是凸规划,根据鞍点定理,规划问题(6)的解由Lagrange函数的鞍点决定,令用上标*表示规划问题(6)的解,则将(9)和(10)代入(7)得规划问题(6)的对偶问题为这里y=(y1,y2,…,yl),D是对称的l×l矩阵,Dij=yiyjxi·xj.从互补性条件:容易知道当约束(6)有效时必有,对应的数据点xi我们称之为Supportvector.对任意Supportvector,根据(12)可得分类的决策函数则为值得提出的是,二次规划问题(6)是比较简单的,但通过上述的处理,可以给出SupportVector的定义;更为重要的是,这种方法可以进行推广,得到处理线性不可分情形的软边缘(softmargin)算法和处理非线性问题的核(kernel)方法.以上的分析实际上说明了SVM是一种基于规划的学习算法,为了定量化研究神经网络学习算法的性能,将其转化为约束的优化问题,这是一条非常值得探索的思路,已有学习者提出并加以研究.6其它学习算法目前,很多关于SVM和VC的理论和应用问题都亟待研究.一方面,这种基于统计学原理的理论思路对新的学习算法的提出很有启发,另一方面,由于SVM出现不久,其理论体系和算法实现尚有大量问题有待于发展和完善.在上述问题中,我们认为下面几个问题尤其值得研究.1.应用VC理论研究泛化性能更好的学习算法,如研究基于其它统计学原理或使期望风险近似最小化的其它学习算法.2.完善SVM方法.SupportVectors的确定可转化为约束的优化问题,但当训练集的规模很大时,传统的优化方法难以满足实时性要求,如何设计快速有效算法是SVM中的重要问题之一;另外,对非线性分类问题,SVM的核方法仍有一些理论缺陷.3.SVM的应用研究.由于SVM算法是对神经网络学习算法、最小二乘法的改良,应用SVM方法到实际问题中,如建模、参数辨识和自适应控制等问题,并将它与已有的处理结果进行比较也是非常有实际意义的.对形如(11)的含等式和盒式不等式约束的规划问题,文献提出了一种大范围收敛的连续神经网络模型进行求解,文献对的模型进行了简化和完善,使之具有了更好的功能(求解非线性规划问题)和性能(指数收敛性).我们认为这种基于动力系统的方法是解决优化问题的先进方法,一方面,这种模型可用电路实现,实时求解大规模的优化问题,另一方面,它的离散化可产生不同的数值算法,克服了普通数值算法须不断寻求