支持向量机回归与ν-支持向量机分类解的关系

支持向量机回归与ν-支持向量机分类解的关系 支持向量机回归与ν-支持向量机分类解的 关系 第26卷第1期 2OO4年3月 湖北大学(自然科学版) J0uITlalofHttbeiUniversity(NaturalSci— enceE — dition) V01.26?.1 Mar.,2OO4 文章编号:1000—2375(2004)01—0012一o4 支持向量机回归与一支持向量机分类解的关系 邹斌,李落清 (湖北大学 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 与计算机科学学院,湖北武汉430062) 摘要:讨论了支持向量机回归与v一支持向量机分类解的关系,证明了对给定的v一支持向量机分类问 题的解,通过选择适当参数,存在,个支持向量机回归问题的解与它等价. 关键词:支持向量机;分类;回归;关系 中图分类号:TP18文献标志码:A 1引言 1962年,F.Rosenblattn提出了第一个机器学习的模型,称为感知器,这标志着人们对学习过程进行 数学研究的真正开始.感知器模型在被用来解决模式识别问题时,在最简单的情况下,感知器利用了最 简单的神经元的自适应特性,每个神经元都是一个McCulloch—Pitts模型,它有n个输入:(,,…, ")?X[_R"和一个输出Y?{一1,1},输入和输出之间具有函数依赖关系:Y=sgn{(??)+b},其 中(??) 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示两个向量的内积,b是一个域值,sgn(.)是符号函数,即如果u>0,则有sgn(u)=1,如 果u?0,贝0有sgn(u):一1. 支持向量机(SupportVectorMachine)简称SVM,是由V.N.Vapnik和C.CortesL2.在1995年提出来的, 是近年来机器学习研究的一项重大成果.根据Vapnik和A.J.Chervonenkis的统计学习理论,如果数据服 从某个(固定但未知的)分布,要使机器的实际输出与理想输出之间的偏差尽可能小,则机器应遵循结构 SRM),而不仅是经验风险最小化原则(ERM).通俗地说,风险最小化原则(就是应当使错误概率的上界 最小化.支持向量机正是这一理论的具体实现.支持向量机的实现思想是通过事先选择的非线性映射将 输入向量映射到一个高维的特征空间z,再在这个空间中构造最优的分类超平面用以解决模式识别. 支持向量机不仅能用于解决分类问题,而且可用于解回归,密度估计,算子方程等问题,并都有了较为理 想的实验效果.通过对支持向量机的进一步研究,B.Schalkop(等提出了v一支持向量机;J.A.K. SuykensL5提出了最小平方支持向量机(LS—SVM).M.PontilL6等通过对支持向量分类和支持向量回归的 研究,讨论了支持向量机分类与支持向量机回归解的关系.本文讨论v一支持向量机分类与支持向量回 归解的关系,并证明对给定的支持向量机分类问题(以下简称v—SVMC)的解,通过选择适当参数,一 定存在一个支持向量机回归问题(以下简称svMR)的解与它等价. 1.1支持向量机(SVM)对给定的训练数据集{(,Y),i:1,2,…,2,Y?{一1,1},?R},假设 存在一个超平面60?+b=0,它能够把数据集分成两类:1类(Y=1)与一1类(Y=一1).这就意味 ILI 着在超平面上的点满足叫?+b=0,其中60是超平面的模,是超平面与原点的垂直距离, lI60ll ll叫ll是欧基米德范数,叫?是?与的内积.定义间隔是可分的超平面到最近的1类中的点与最近的 一 1类中的点的距离之和.对线性可分情况,支持向量机就是寻找最大间隔的可分超平面,它可以公式化 为所有训练数据点满足线性约束条件:Y(60?+b)一1?0,i:1,2,…,2,从这个约束条件我们可以 收稿日期:20O3—02—17 基金项目:湖北省自然科学基金(99j169)资助课题 作者简介:邹斌(1971一),男,讲师 第1期邹斌等:支持向量机回归与一塞向量墨l3 计算出其间隔为.于是在上述约束条件下寻找带有最大间隔的可分超平面(最优可分超平面)问 lluVll 题等价求解下面问题. 问题1rain1llll.约束条件为:Yi(?+b)?1,i=1,2,…,z. 在软间隔(非线性可分)情况l3下,求解推广的最优可分超平面问题等价于求解下面问题. 1l 问题2哑专llll+c?毫.约束条件为:(oo?+6)?1一毫,i:1,2,…,z,毫?0,C>0. 其中c为正则化参数,在高维情况下,支持向量机就把输入空间z映射到一个更高维的希尔伯特空间 上,再在这个空间中构造最优的线性分类器.为此,我们可选择一个映射函数:R一日,使()(Y) = k(x,Y),而k是某个已知的并且容易去估价的函数,这个映射存在的充分条件是k满足Mercer定 理[引. 1.2支持向量机回归(S眦)与v一支持向量机分类(v—SVMC)SVMR是为估计带参数的函数 )=?+b,对给定的z对,依未知概率密度而随机独立产生的训练数据集{(,Y),i:1,2,…, Z,Yi?R,?R},最小化下面问题. . 问题3win. 1l1l1+c?(毫+).约束条件为:一(?+6)?e+毫,i=1,2,…,z, ??b?}i?}【一i1 (.+b)一yi?e+,i=1,2,…,z,毫?0,?0.其中e是回归问题的精度,它是事先给定的. v—SVMC是SVMC的推广,所谓v—SVMC,它是对给定的c对随机独立同分布训练数据集{(Xi, Yi),i=1,2,…,z,Y?{一1,1},?R},寻找决策函数)=sgn(?+b),,?R,b?R, 因此必须最小化下面问题. 1 问题4吉l1l1一+c毫.约束条件为:Y.(oo.X,i+6)?10一毫,=1,2,…,z,毫? 0,10?0.特别地,在v—SVMC问题中当参数:0时,』0可取值』0:1[引,此时v—SVMC问题就是SVMC 问题,并且在v—SVMC问题中,v不仅是间隔误差部分的一个上界,而且是支持向量部分的一个下 界】. 2SVlVlR与y—SVlVlC解的关系 为方便起见,这里仅考虑线性可分情况,对线性不可分情况,可采用引入非线性的Mereer核(, )可类似进行讨论.一般,回归问题是考虑Y.取实数情况,在此仅讨论Y取二值,即 Y.:1或:一1, 并且精度e满足0<e<1的情况,因此以下都是对数据集{(毛,Yi),i:1,2,…,z,? {一1,1},? R}讨论,我们的主要结论叙述为如下定理. 定理1设带有正则化参数C且P?1的v—SVMC问题(问题4)的解为(?,b,p),于 是存在一个 常数0,当0?(0,1),使对任意的,?(0,1),存在带有正则化参数为(1一e)C的SVMR 问题(问题3) 的解为(1一e)(,b). 定理1的证明首先作替换: f毫当Yi=1,『当Y.:1, 当儿:一1,'7lI毫当:一1. 上面问题3变形为下面表达式: .1 rain . 1IJ+c?(+)(1) 约束条件为:(?+6)?1一,一,i:1,2,…,l Y.((o?+6)?1+e+77,i:1,2,…,f ?0,7?0 (2) (3) (4) 14湖北大学(自然科学版)第26卷 因为0<,<1所以1一,?0且1一,>0,再令: cu,:: ,: 卫 1-e: 上面表达式(1)及约束条件(2—4)变为下面表达式(6)及约束条件(79). 约束条件为: 1,ll+砉(+,6,..二一,一' Yi(?+b)?1一,i=1,2,…,Z ),i(cu+6)?+,:1,2,…,f (5) (6) (7) (8) ?0,?0(9) 表达式(6)(在约束条件(7—9)下)的求解是凸 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 问题.为求其解,必须寻找拉格朗 日函数,(,, 6,, ,)的鞍点. ,(cu,6,,)=cu,ll+(+)一(),(cu+6)一l+)一 ?i=I a (+(cu))一塞一卢(10) 对函数,(,b,,)分别关于cU,b,,求偏导并令它们为0,再代人函数,(,,6,,,)就 得到它的对偶表达式(11)及约束条件(12,13)~tlJT. rain .吉?(a)(a.一a)),+?a一?a(11)ai,ai—J,口,一i=I一西函 约束条件为: 由于0<,<1,当,一1一时,有 ,f ?a:?aiyi,i:12..,2(12)i=Ii=I a,a?0(13) 1+, r一+?' 因而表达式(6)中第二个约束条件(8)当=0时也会自动满足,故约束条件(8)可消去.同理表达式 (11)中项}薹a也可消去,从而得到(14)式及约束条件(15)和(16)如下. minI塞珊1a 约束条件为:?aiY:0,:1,2,…,l (14) (15) 由此可发现表达式(14)及约束条件(15,16)正好对应着修正后的,SVIVIC问题(表达式(17)及约束条 件(18,19)的对偶表达式: 翼1IIcUII一+?毫(17) 约束条件为:((U?+6)?+l0,,: t= , l YiXi1i12,…,l(18) ,?0,l0?I(19) 因为v—sVMc问题(表达式(17)及约束条件(18,19)的解为(,b,p).而回归问题(表达式(6)及约束条 件(7,9)的解为(cU,6)且cU,=T_,6:.『_.所以定理得证. 3讨论 在v—SVMC问题中,当v=0,l0=1时,v—SVMC问题就是SVMC问题,由此可得出下面推论. 第1期邹斌等:支持向量机回归与一支持向量机分类解的关系 推论1设对带有正则化参数为c的SVMC问题的解(?,b),于是存在一个常数口,当口?(0,1), 使得对任意的,?(口,1)存在带有正则化参数为(1一,)C的SVMR问题的解为(1 一,)(?,b). 此推论正是M.Pontil等在文献[6]中所讨论的结论. 参考文献: l1jRosenblatt.F.Principlesofneurodymmies:perceptronandtheoryofbrainmechanisms[M].WashingtonDC:Ba,1962. [2]VapnikVN.Tnenatureofstatisticallearningtheory[M].Heidelberg,Ge瑚aIIy:Sp面 gerVerlag,1995. [3JVapnikVN.Statisticallearningtheory[M].NewYork:JWiley,1998. [4]Sch~lko#B,SmolaA,WiliamonR,eta1.Newsupportvectoralgorithms[J].NeuralComputafion,2000,12(15):12071245. [5]SuykensJAK,VandewaUeJ.Leastsquaressupportvectormachineclassifiers[J].NeuralPr0cessiIlgLetteIs,1999,9(3):293 300. [6JPontilM,RilkinR,EvgeniouT.Fromregressiontoclassificationinsupportvectormaehines[A].Es^NN1999.PrDoeedin,Eu— ropeanSymposiumonArtificalNetworks[C].Bm(Belgium):D— FactoPublic:1999.2123:225230. 17jBurgesCJc_Atutorialonsupportvectorlnachinesforpatternrecognition[J].KataMiningandedgesc0very,1998,2(2): 121—167. 18jBurgesCJC,CrispKJ.UniquenessoftheSVMsolution[J].N】PS,2OOO,12:223229. TherelationofsolutionbetweensupportvectormachineI'eand supportvectormachineclassification ZOUBin,LII~o-qing (SchoolofMathematicsandComputerScience,HubeiUniversity,Wuhan430062,Cllim) Abstract:Therelationofsolutionbetweensupportvectormachineregressionandsuppovect0rITlaIchinecks si— ficafionisdescribedinthispaper.Showthatforagivenv—SVMCsolutionthere麟istsaSVMR9olution,whichis equivalentforacertainchoiceoftheparameters. Keywords:supportvectormachine;classification;i'e~ssion;I?lati0n (责任编辑肖铿)