（应用数学专业论文）原始空间中支持向量机若干问题的研究.pdf

摘要支持向量机成为一种主要的机器学习技术已经有十多年了，然而它的大部分学习算法都是在对偶空间针对其对偶问题提出的。近年来的研究表明，直接在原始空间对支持向量机的原始问题进行求解也是训练支持向量机的一种有效途径。随着人们在原始空间对支持向量机研究的深入，实际应用中碰到的各种问题也开始在原始空间进行求解，如半监督学习问题等。但总体来说，支持向量机在原始空间中的研究还不是很多，也不够完善。因此，本文重点研究了原始空间中支持向量机分类算法的以下四个问题。1 针对光滑支持向量机中现有的光滑函数逼近精度不高的问题，将正号函数变形并展开为无穷多项式级数，由此得到了一族多项式光滑函数，并证明了这类光滑函数的优良性能，它既能满足任意阶光滑的要求，也能达到任意给定的逼近精度。最后将得到的多项式光滑函数用于求解广义支持向量机。2 半监督支持向量机利用大量的未标记样本和少量的标记样本共同学习以改进其泛化性能，最后得到一个非凸优化问题，对其优化采取两种策略：组合优化和连续优化。组合优化的具体方法是给出了一个自训练半监督支持向量机分类算法，它的子程序是用前面得到的多项式光滑函数在原始空间求解标准支持向量机。接下来用连续优化的方式给出了一个多项式光滑的半监督支持向量机分类算法，给出的多项式函数有严格的理论基础，并且在样本的高密度区逼近精度高，而当逼近精度低时，则出现在样本的低密度区。3 直接方法是一类常用的无约束优化技术，简便实用，它和之前用于支持向量机的循环算法不同，不是一次更新w 的所有分量，而是每次通过解一个单变量的子问题来更新w 的一个分量。本文分别用h o o k ea i l dj e e v e s 模式搜索法、r o s e n b r o c k 转轴法和p o w e l l 方向加速法求解线性支持向量机，并分析了算法的复杂性。4 支持向量机采用的线性h i n g e 损失函数对噪声样本产生的损失没有限制，这是支持向量机对噪声敏感的根本原因。由于特殊的损失函数能有效抑制噪声产生的损失，本文据此给出了一个全新的双曲正切损失函数，并在此基础上给出了相应的健壮支持向量机。实验表明上述方法和结果在支持向量机算法中均具有较好的学习性能。关键词：统计学习理论支持向量机分类光滑函数半监督学习直接方法h o o k e 锄dj e e v e s 算法r o s e n b r o c k 算法p o w e n 算法a b s t r a c ts u p p o i r tv e c t o rm a c h i n e( s v m )h a sb e e nad o m i n a n tm a c h i n el e 锄i n gt e c h n i q u ef o rm o r et h a nad e c a d e ，h o w e v e r ，m o s to fi t sa l g o r i t h m sw e r ep r o p o s e di na l l u s i o nt oi t sd u a lp r o b l e mi nt h ed u a ls p a c e r e s e a r c hi n d i c a t e st h a ts o l v i n gt h ep r i m a lp r o b l e mi sa l s oa ne f f e c t i v ea p p r o a c hf o rt r a i n i n gs v mi nr e c e n ty e a r s a sp e o p l em a k e 觚i n t e n s i v es t u d yo fs v mi nt h ep r i m a ls p a c e ，v a r i o u sp r o b l e m sm e t e di na p p l i c a t i o nw e r es o l v e di nt h ep r i m a ls p a c e ，s u c ha st h ep r o b l e mo fs e m i s u p e r v i s e dl e 锄i n g b u ta saw h o l e ，t h er e s e 2 u r c ho ns v mi sn o tf a m i l i a ra i l dp e r f e c ti nt h ep r i m a ls p a c e t h e r e f o r e ，t h i sd i s s e r t a t i o nm a i n l yf o c u s e so nt h es t u d yo ft h ef o l l o w i n gf 0 1 1 rp r o b l e m so fs v mc l a s s i f i c a t i o na l g o r i t h mi nt h ep r i m a ls p a c e t 0d e a l 晰t ht h ep r o b l e mo fp o o ra p p r o x i m a t i o np e 怕m 肌c eo fs m o o t h i n gf u n c t i o n sa v a i l a b l eo fs m o o t h i n gs u p p o r tv e c t o rm a c h i n e s ，p l u sf u n c t i o nw a st r a n s f o m e di n t o觚e q u i v a l e n ti n f i n i t es e r i e s t h u saf 锄i l yo fp o l y n o m i a ls m o o t h i n gf u n c t i o n sw e r ed e r i v e d t h ep r o p e r t i e so ft h e mw e r ed i s c u s s e d i ti ss h o 、nt h a tt h ea p p r o x i m a t i o na c c u r a c y觚ds m o o t l l i n gr a n k o fp o l y n o m i a l如n c t i o n sc 趾b e 嬲h i g ha sr e q u i r e d f i n a l l y ，t h ep o l y n o m i a ls m o o t h i n gf u n c t i o n sw e r eu s e dt os o l v et h eg e n e r a l i z e ds u p p o nv e c t o rm a c h i n e s e m i - s u p e r v i s e ds v mm a k e su s eo ft h el a r g ec o l l e c t i o no f 吼l a b e l e dd a t aj o i n t l yw i t haf e wl a b e l e de x 锄p l e sf o ri m p r o v i n gg e n e r a l i z a t i o np e r f o m a n c e f i n a l l y ，an o n c o n v e xo p t i m i z a t i o np r o b l e mw a so b t a i n e d w ea d o p t e dt w os t r a t e g i e sf o rm i n i m i z i n ga b o v eo p t i m i z a t i o np r o b l e m ：c o m b i n a t o r i a lo p t i m i z a t i o na n dc o n t i n u o u so p t i m i z a t i o n t h ew a yo fc o m b i n a t o r i a lo p t i m i z a t i o ni sp r e s e n t i n gas e l f t r a i n i n gs e m i s u p e r v i s e ds v mc l a s s i f i c a t i o na l g o r i t h m ，w h o s es u b p r o g r 锄u s et h ea b o v eo b t a i n e dp o l y n o m i a ls m o o t h i n gf u n c t i o n st os o l v et h es t a i l d a r ds v mi nt h ep r i m a l a r e rt h a t ，ap o l y n o m i a ls m o o t hs e m i s u p e r v i s e ds u p p o r tv e c t o rm a c h i n e sc l a s s i f i c a t i o na l g o r i t h mw 嬲p r e s e n t e di nt h ew a yo fc o n t i n u o u so p t i m i z a t i o n t h ei n t r o d u c e dp o l y n o m i a lm n c t i o n sh a v eag o o dc o m m 锄do ft h e o r ya n di l a v eh i g ha p p r o x i m a t i o na c c u r a c yi nh i 曲d e n s i t yr e g i o n so fs a m p l e sa n dp o o ra p p r o x i m a t i o np e r f o r m 锄c ea p p e a ri nl o wd e n s i t yr e g i o n so fs 锄p l e s d i r e c ts e a r c hm e t h o di sac o m m o nu n c o n s t r a i n e do p t i m i z a t i o nt e c h n i q u e ，i ti sd i 彘r e n t 行o mt h ec y c l i ca l g o r i t l n su s e di ns v mf o r m e r w h i c hu p d a t ea l lc o m p o n e n t so fwa tat i m e h o w e v e r d i r e c ts e a r c hm e t h o du p d a t e so n ec o m p o n e n to fwa tat i m eb ys o l v i n gao n e - v a r ia _ b l es u b p r o b l e m o na c c o u n to fvt h es i m p l e n e s s 觚dp r a c t i c a b i l i t yo fd i r e c ts e a r c hm e t h o d ，t l l r e ea l g o r i t h m so ft h em e t h o dw e r eu s e dt 0s o l v el i n e a rs v m t h et h r e ea l g o r i t t l i l l sa r eh o o k ea n dje e v e sp a t t e ms e a r c ha l g o r i t h m 、r o s e n b r o c kc o o r d i n a t e t u m i n gm e t h o da n dp o w e l l sd i r e c t i o na c c e l e r a t i o nm e t h o d t h ed e t a i l e ds o l v i n ga l g o r i t h mw a sg i v e na n dt h ec o m p l e x i t yo ft h ea l g o r i t h mw a sa n a l v z e d t h ee s s e n t i a lr e a s o no ft h es e n s i t i v i t yo fs v mt on o i s ei st h a tt h ea d o p t e dl i n e a rl o s sm n c t i o nh a sn ol i m i t so nt h ep e n a l t y1 0 s so fn o i s es 锄p l e s a c c o r d i n gt ot h ef a c tt h a ts p e c i a l l o s s 如n c t i o ni sa b l et oc o n t r 0 1 t h el o s sv a l u ec a u s e db vn o l s es 锄p l e s ，an o v e lh y p e r b o l i ct a n g e n tl o s sf u n c t i o nw a sc o n s t r u c t e d ，a n db a s e do nt h en e wl o s sf u n c t i o n ，t h ec o r r e s p o n d i n gr o b u s ts v m h y p e r b o l i ct a n g e n ts v mw a sp r o p o s e d e x p e r l m e n t sw e r ep e r f o m e dt ov e r i 匆t h ea b o v ef o u rp r o b l e m si ns v mc l a s s i f i c a t i o na l g o r i t h m ，e x p e r i m e n t a lr e s u l t ss h o wt h e yc a no b t a i ns a t i s f a c t o r yl e a m i n gp e r f o r m a n c e k e y w o r d s ：s t a t i s t i c a l1 e a m i n gt h e o 哆s u p p o r cv e c t o rm a c h i n ec l a s s i f i c a t i o ns m o o t h i n gf u n c t i o ns e m i s u p e n ，i s e dl e a m i n gd i r e c ts e a r c hm e t h o dh o o k ea n dj e e v e sa l g o r i t h mr o s e n b r o c ka l g o r i t h mp o w e l la l g o r i t h m独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担二切的法律责任。本人签名：日期j o 。，o关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本人签名：鱼11 堕盘导师签名：日期如仉- 口日觏砂o ；第一章绪论本章首先介绍了支持向量机的研究背景，接着分六类介绍了支持向量机分类算法的研究现状，这六类算法是分解算法、增量学习算法、多类别分类算法、支持向量机改进算法、支持向量机变形算法和原始空间中的求解算法。最后，介绍了本文的主要内容及结构安排。1 1 研究背景基于数据的机器学习【l 】是现代智能技术的重要内容，也是极为活跃的一个研究方向。主要研究如何从观测数据( 样本) 中发现规律，利用获得的规律对未来数据或者无法观测的数据进行预测。传统的基于数据的机器学习方法包括经典的( 参数) 统计方法与经验非线性方法【2 】。参数统计方法基于传统统计学，存在很大的局限性。在这些方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这些方法需要事先知道样本的分布形式，这需要花费很大的代价，而且传统统计学研究的是样本数目趋于无穷大时的渐进理论，现有学习方法也多是基于此假设。但在实际问题中，样本数目往往是有限的，因此一些理论上很优秀的学习方法实际表现却可能不尽人意。经验非线性方法，如人工神经网络，利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是这种方法经验性成分特别大，缺乏一种统一的数学理论。支持向量机( s u p p o r tv c c t o rm a c h i n e ，s v m ) 3 ，4 5 6 】是在统计学习理论( s t a t i s t i c a ll e a m i n gt h e o s l t ) 【3 ，7 ，8 】基础上发展起来的一种新型的机器学习方法。统计学习理论是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下，统计推理规则不仅考虑了对渐进性能的要求，而且追求在现有有限信息的条件下得到最优结果。支持向量机是统计学习理论中最实用的部分，也正是由于它的产生才使统计学习理论有了新的动力。虽然其核心内容早在1 9 9 2 年到1 9 9 5 年就已提出【3 4 】，但目前仍处在不断丰富发展阶段。与其它机器学习算法仅仅考虑到经验风险最小化( e m p i r i c a l 砒s km i n i m i z a t i o n ，e r m ) 的原则不同，支持向量机采用统计学习理论中的结构风险最小化( s t r u c t u r a lr i s km i n i m i z a t i o n ，s i 之m ) 原则来训练学习机，同时用v c 维理论来度量结构风险。支持向量机的最终求解可以转2西安电子科技大学博士学位论文：原始空间中支持向量机若干问题的研究化为一个具有线性约束的凸二次规划问题，因此能够保证获得全局最优解。通过引入核函数，可以很容易地将线性支持向量机推广到非线性支持向量机，使数据在高维空间中依然可以用线性判别函数分类。核函数的引入，使支持向量机巧妙地解决了“维数灾难”，使高维样本几乎不增加任何额外的计算量。支持向量机具有直观的几何解释、简洁的数学形式和人为设定参数少等优点，因而便于理解和使用。建立在严格理论基础之上的支持向量机较好地解决了传统机器学习方法中的模型选择和过学习问题，非线性与维数灾难问题，局部极小值等问题。与传统的人工神经网络相比，支持向量机不仅具有坚实的理论基础，而且结构简单，各种技术性能尤其是泛化性能( g e n e r a l i z a t i o np e r f o m a n c e ) 明显提高【3 ，7 9 】，因此被广泛应用于模式分类、函数估计及回归分析等领域，并已成功解决文本分类10 1 、人脸检测【1 1 1 、目标识别【1 2 1 、手写数字识别吲、语音识别t 1 3 】、性别分类【1 4 】、遥感图象分析【1 5 】等诸多实际问题。1 2 支持向量机分类算法研究现状支持向量机提出以后，由于在许多应用领域表现出较好的推广能力，因此得到了广泛的研究。其中在算法方面，研究者针对s v m 本身的特点，尝试通过不同的途径来求解，提出了多种学习算法，主要有分解算法、增量学习算法、多类别分类算法、支持向量机改进算法、支持向量机变形算法和原始空间中的求解算法等。1 2 1分解算法由于s v m 的训练最终归结为解一个凸二次规划问题，当问题的规模较小时，一些经典的优化算法如牛顿法、拟牛顿法、共轭梯度法都能够很好的解决。但是当问题规模很大时，由于这些算法在每一步迭代中都需要计算核函数的矩阵，而核函数的矩阵占有的内存随样本数的增加而呈平方增长，如计算4 0 0 0 个样本的核函数矩阵就需要1 2 8 m 内存，这就使得算法还需要很大的内存。另外，支持向量机在二次寻优过程中要进行大量的矩阵计算，很多时候寻优算法是占用算法时间的主要部分，所以当训练样本增加时，这些经典算法还需要很长的训练时间。为了解决这些问题，人们提出了很多算法，其中大部分算法是将大规模的原问题分解成若干个规模较小的子问题，按照某种迭代策略，反复求解子问题，得到原问题的近似解，并能逐渐收敛到原问题的最优解。这就是分解第一章绪论3算法的一般做法。根据从训练集中选择工作样本集做法的不同，分别演化出不同的分解算法如b o s e r 等【1 6 】提出的c h u n k i n g 算法，o s u n a 【1 。7 j 提出的w b r k i n gs e t 算法，p 1 a t t 【1 8 】提出的序贯最小优化( s m o ) 算法等等。c h u n k i n g 算法基于这样一个事实：去掉l a g r a i l g e 乘子为零的样本即非支持向量不会影响问题的解。同时由于非支持向量占样本的大部分，去掉它可以节省大量的计算和内存。具体的做法是，在算法的每一步都解决一个二次规划问题，其工作样本为上一步所剩的具有非零l a g r a n g e 乘子的样本以及m 个不满足k u h n t u c k e r 条件的最差样本。如果在某一步中，不满足k u h l l t u c k e r 条件的样本不足m 个，则这些样本全部加入到新的二次规划问题中。在算法进行到最后一步时，所有非零l a g r a n g e 乘子都被找到，从而解决了初始的大规模二次规划问题。c h u n l 【i n g 算法将矩阵规模从训练样本数的平方减少到具有非零l a g r 强g e 乘子的样本数的平方。w 0 r k i n gs e t 算法的基本思想是首先建立一个工作集，保持其大小不变，在解决每个二次规划子问题时，先从工作集中移走一个样本，并加入一个不满足k u h n t u c k e r 条件的样本，再进行优化。由于每一步进行二次规划问题的最优化只能使一个样本符合k u h n t u c k e r 条件，所以该算法的效率较低。s m o 算法是分解算法的极端情形，它的工作集大小是2 ，也就是每个子问题只对两个变量进行优化。因为有等式约束，所以这是最小的工作集。其工作集的选择不是采用传统的最陡下降法，而是采用启发式策略。s m o 算法的优点在于，优化问题只有两个l a g r a n g e 乘子，它用解析的方法即可解出，从而完全避免了复杂的数值解法。另外，它根本不需要巨大的矩阵存储。这样，即使是很大的支持向量机学习问题，也可在p c 机上实现。1 2 2 增量学习算法增量学习方法是对不断更新的数据进行学习的一种方法。它是在保留以前学习结果的基础上，仅对新增加的数据进行再学习，从而形成一个连续的学习过程。这种方法更适合于像s v m 这样的分类算法。这是因为s v m 的泛化性能不是依赖于全部的训练数据而是其中一个称为支持向量的子集。由于支持向量的个数明显小于训练样本的个数，所以s v m 可以成为增量学习的有效工具。当数据连续成批地出现时，可以把之前批次的数据压缩成支持向量，然后对新来的数据，s v m 在新数据和之前学习得到的支持向量上训练，这称为支持向量机的增量学习【l 皿3 4 】。由于标准的s v m 学习算法并不直接支持增量式学习，所以研究有效的s v m 增量学习方法具有重要的理论意义和实用价值。4西安电子科技大学博士学位论文：原始空间中支持向量机若干问题的研究文献 3 2 】首先提出了s v m 的增量学习，它只关注了每批数据中直接成为支持向量的数据。后面出现的s v m 增量学习方法有很多都是对这种方法的改进【2 卜2 6 1 ，它们在文献【3 2 】的基础上，检查是否有新增训练样本违背k k t 条件。因为如果有，则在违反k k t 条件的样本中，肯定存在部分或全部新支持向量，同时原分类支持向量机中非支持向量有可能转化为支持向量1 27 。，据此，找出支持向量集。文献 2 8 3 1 】分别提出了寻找支持向量候选集的新方法。支持向量机增量学习背后的原理是：s v m 结果得到的决策函数仅仅依赖于它的支持向量，也就是只在支持向量上训练s v m 和在全部数据上训练可以得到相同的决策函数。正因为如此，如果增量学习最后的训练集中包含了非增量训练中所有的支持向量的话，可以期望增量学习的结果和非增量学习相同。文献【3 2 】中给出了评价支持向量机增量学习算法的3 个准则：稳定性：在增量学习的每一步，在测试集上的预测精度不应该剧烈地改变。改进性：随着训练过程中学习算法使用越来越多的训练样本，在预测精度上应该有改进。可恢复性：学习算法应该能够从它的错误中恢复。也就是说，即使在某一步性能下滑了，算法应该能够恢复并改进到或优于原来的最好性能。1 2 3多类别分类算法支持向量机是从二分类问题提出的，而实际中的很多问题都是多分类问题，因此，怎么样把二分类问题推广到多分类问题是很值得研究的。目前已提出的多种方法，可以归结为如下几种方案：1 一对一( o n e v e r s u s o n e ) ”3 6 】，这种方法的做法是在多类中任意取出两类进行训练，这样对一个七类分类问题，就转化成尼( 七一1 ) 2 个二类问题。识别时，对所构成的七( 七一1 ) 2 个s v m 进行综合评判。这种分类方案的缺点是，由于要构造的子分类器过多，所以计算量非常庞大。同时测试时，需要对每两类都进行比较，导致测试速度很慢。另外这种方法常存在着不可分的区域。2 一对多( o n e v e r s u s r e s t ) 了7 1 ，这种方法的基本思想是在多类中把其中某一类当作一个类别，剩余的所有类别的样本当作另一类，这样就变成了一个两分类问题。这种分类方案的缺点是训练样本很多，训练很困难。同时容易产生属于多类别的样本和没有被分类的样本。3 直接考虑多类问题【3 8 ，3 9 1 ，这类方法借鉴二类分类问题的思想，构造一个学习模型，在优化问题中统一处理全部训练样本。具体地说，对k 类问题，需要构造k 个判决函数，其中第i 个把第i 类与其它类数据区分开来。与一对第一章绪论5多方法不同的是，这k 个判决函数统一于一个模型，通过学习同时得到。4 支持向量机决策树砌，这种方法通常和二叉树结合起来，构成多类别的识别器。它的缺点是如果在某个分类节点上发生了分类错误，那么错误将会被延续下去，因此这个节点后续所有节点上的分类也就失去了可信度。1 2 4 支持向量机改进算法支持向量机提出后，随着分类算法的发展也出现了大量的改进算法，它们大致可以分为以下两类：1 几何方法。s v m 具有清晰的几何含义，训练s v m 等价于求解特征空间中两类训练样本形成的两个凸包或者简化凸包之间的距离，几何方法就是利用这种几何解释，将s v m 训练问题转化为经典的几何问题。比如b e 皿e t te ta 1 【4 1 】把s v m 问题转化为求两个凸多面体之间的最近点问题。在此基础上。k e e r t h ie ta 1 【4 2 】将两个传统的n e a r e s tp o i n t 算法n p a 加以组合改进，提出了一个快速的最近点算法。另外l g 等【4 3 】利用几何方法来选取潜在的支持向量，该方法利用训练集中的集合信息，提出了g u a u r dv e c t o r 的概念，g u a u r dv e c t o r即是通过该向量能使输入空间线性可分的向量，所有的支持向量都是g u a r dv e c t o r ，但反之不成立。直观地讲g u a r dv e c t o r 就是支持向量的候选对象，所有g u a r d v e c t o r 构成的集合是支持向量集的超集，但一般比训练集小的多。当训练集合较大时，首先找出样本集的g u a r dv e c t o r ，再以g u a r dv e c t o r 构成传统的二次规划问题求出支持向量，g u a r dv e c t o r 的求解是通过判断其对偶空间中的线性规划问题的可行性而不是求其解，从而使问题大大简化，最后再在g u a r dv e c t o r 的基础上构建s v m 。2 与其他学习方法结合。比如l u 等【4 4 】将s v m 与主动学习方法结合，提出了交互式s v m 算法。z h a l l g 等【4 5 】将s v m 与小波学习方法相结合，提出了小波支持向量机。s u y k e n s 与v n d e w a l l e 等【4 6 】将s v m 与递归神经网络相结合，开发出一种所谓的递归s v m 。1 2 5 支持向量机变形算法尽管研究者采用了很多方法【4 7 5 2 1 来减少标准s v m 对应的二次规划问题在求解过程中的计算复杂性，但效果都不是太理想。于是一些学者提出通过增加函数项、变量或者系数使公式变形，以简化所求的优化问题，于是出现了很多变形s v m 。简要介绍下面四个：6西安电子科技大学博士学位论文：原始空间中支持向量机若干问题的研究1 最小二乘支持向量机。1 9 9 9 年，s u y k e r s 等【5 3 】人提出了最小二乘s v m ( l e a s ts q u a r es v m ，l s s v m ) ，l s s v m 用等式约束替换不等式约束，并且采用二次损失函数，从而把s v m 学习问题转化为一个线性方程组问题，用最小二乘法即可求解。用等式约束代替原来的不等式约束后，改变了问题的性质，即标准s v m 中的稀疏性消失了。大量的实验结果表明，l s s v m 的泛化能力与标准s v m 是可比的。2 线性规划支持向量机【5 4 1 。在标准s v m 中，将间隔的度量由2 范数换成1 范数，就得到了线性规划s v m ，由于解线性规划比二次规划容易的多，因此线性规划s v m f 艮实用。线性规划s v m 的另一个好处是降维，因为最小化1 范数将导致间隔的稀疏化，将不重要的特征丢弃，起到特征选择的效果。虽然标准s v m 也有类似的效果，但比较起来，线性规划s v m 会迫使更多属性的权值趋于零。3 最接近支持向量机( p r o x i m a ls v m ，p s v m ) 5 5 】。p s v m 是在采用二次损失的s v m 优化模型的基础上，做了一个非常简单又非常基本的改变即用等式约束代替不等式约束。p s v m 的几何解释是，寻找两个平行的超平面，每类样本围着相应的超平面聚集，并且两个超平面离的尽可能的远。判断规则是，待分类样本对应着离它最近的那个超平面。这与标准s v m 的解释完全不同，但也体现了边缘最大化的思想，这是s v m 的本质特征。p s v m 的优势在训练速度方面，当输入空间维数不大时，即使训练数据达几百万，训练速度也很快，并且准确率与标准s v m 相当。但是当把p s v m 推广到非线性情形时，由于这时方程组系数矩阵的阶等于样本总数，所以只能处理中等规模大小的问题。4 g e p s v m 【5 6 】。在p s v m 的基础上，丢弃最近超平面平行的条件，要求两个超平面离一类样本尽可能的近，同时离另一类样本尽可能的远，这样就得到两个不平行的超平面。实验结果证明，这种分类机最善于分类交叉平面分类的情形。对一般的数据集分类，速度没有p s v m 快。1 2 6 原始空间中的求解算法支持向量机中的大多数学习算法都是针对其对偶优化问题进行求解的【5 7 。6 4 1 ，近年来，一些学者的研究f 6 5 。6 7 1 指出，直接对s v m 的原始优化问题进行求解也是训练支持向量机的一种有效途径，特别是需要快速地求解s v m 的近似最优解时，直接对原始优化问题进行求解更具优势，因为：( a ) 根据对偶理论，对偶问题和原始问题的目标函数值只有当取最优解时才相等；( b ) 支持向量机的最大间隔决策超平面是通过原始优化问题确定的。因此，针对原始优化第章绪论7问题研究支持向量机的学习算法是非常有意义的。为此，我们进行如下的定义，以便区分这两类算法。定义1 2 1 ( 原始空间) 称针对支持向量机的原始优化问题进行求解的学习算法为“原始型算法”，而算法相应的求解空间称为“原始空间”。定义1 2 2 ( 对偶空间) 称针对支持向量机的对偶优化问题进行求解的学习算法为“对偶型算法”，而算法相应的求解空间称为“对偶空间”。在原始空间求解支持向量机，最主要的思路是把约束优化问题转化为无约束优化问题，比如文献【6 5 】【6 7 7 l 】等。近几年，随着人们在原始空间对支持向量机研究的深入，实际应用中碰到的各种问题也开始在原始空间进行求解，如半监督学习问题，噪声问题等。但总体来说，在原始空间求解支持向量机的研究还不是很多，也不完善。因此，深入研究支持向量机在原始空间的各种学习算法是必要的，也是有积极意义的。以上简单介绍了支持向量机算法的研究现状，为了叙述的方便，我们把论文中所要涉及内容的研究现状放在了相关的章节中。1 3 研究内容与结构安排支持向量机在原始空间中的研究远没有在对偶空间中的研究那么深入和广泛，这为我们在原始空间研究支持向量机提供了广阔的空间。本文针对以下几个方面对原始空间中的支持向量分类机进行了研究和探讨：1 光滑函数在光滑s v m 中起着非常重要的作用，利用函数的级数展开法得到一类多项式光滑函数。从理论上证明了这类函数的性能，它既能满足任意阶光滑的要求，也能达到任意给定的逼近精度。并将得到的多项式光滑函数用于求解广义支持向量机。2 给出了一个自训练半监督支持向量机算法；并提出了解决半监督型学习问题的多项式光滑的半监督支持向量分类机，给出的多项式函数有严格的理论基础，并且满足在样本的高密度区逼近精度高，逼近精度低时出现在样本的低密度区。3 由于原始空间中的支持向量机模型可以转化为一个无约束优化问题，因此引入非线性规划中的三个直接方法一h o o k e 髓dj e e v e s 算法、r o s e n b r o c k算法和p o w e u 算法对其进行求解，为支持向量机提供了一种新型的求解算法。4 利用特殊的损失函数能有效抑制噪声对泛化性能的影响，给出了一个新的损失函数，并在此基础上给出了相应的健壮支持向量机。8西安电子科技大学博士学位论文：原始空间中支持向量机若干问题的研究全文共分六章，具体安排如下：第一章是绪论，概述了论文的研究背景，支持向量机分类算法的研究现状，并指出本文将要研究的内容和所做的主要工作。第二章概述了支持向量机的主要理论基础，简述了机器学习、统计学习理论以及优化理论中的一些基本概念和定理，然后在此基础上简要介绍了支持向量机和核函数理论，并给出了支持向量分类机的数学模型。第三章研究了光滑支持向量机中的多项式光滑函数。先分析了光滑支持向量机中使用的指数函数，虽然它可以任意阶光滑，但是它的逼近精度却不高。当要求达到的逼近精度很小时，此指数光滑函数不能满足要求。为此我们在本章给出了一类既能满足任意阶光滑，也能达到任意给定的逼近精度的多项式光滑函数。数值实验说明随着多项式光滑函数阶数的提高，逼近精度提高，其相应支持向量机模型的分类性能也相应提高。最后将多项式光滑函数应用于求解广义支持向量机，实验结果说明求解算法是有效的。第四章研究了原始空间中的半监督支持向量机。首先给出了一个自训练半监督支持向量机算法。因为它是一个循环算法，并把标准支持向量机作为一个子程序，为了提高算法的效率，将第三章中得到的多项式光滑函数用于求解标准支持向量机。实验结果显示，给出的算法效率高，分类器性能稳定，因此给出的算法有效。另一方面，由于原始空间中的半监督支持向量分类机的优化问题是非凸非光滑的，为了处理它，引入一族多项式光滑函数来逼近非凸的目标函数，并给出了它的逼近误差。数值实验结果显示，我们给出的分类器不仅能保证标号数据很少时的分类精度，而且不因标号数据的增多而明显提高分类性能。第五章研究了线性支持向量机的直接方法。首先介绍了最简单的并行下降方法应用于线性支持向量机的情况，指出其存在的缺点。然后将直接法中的h 0 0 k ea n dj e e v e s 算法、r o s e n b r o c k 算法和p o w e u 算法分别用于求解线性支持向量机，分析了算法的性能。实验表明，前两个算法都改进了并行下降法最终收敛慢的问题，且在分类中以更快的速度获得了更高的测试精度。p o w e l l算法的测试精度也优于并行下降算法。由于它和并行下降算法的终止条件不同，所以不能直接比较它们的收敛速度，但收敛速度的实验显示，开始时算法收敛的非常快，虽然最终的收敛速度有所缓慢，但都非常快的收敛到了最小值。第六章研究了原始空间中的健壮支持向量分类机。首先分析了噪声样本对支持向量机泛化能力的影响，然后分别介绍了健壮支持向量机在对偶空间和在原始空间中的研究现状，指出现有的原始空间中存在的损失函数的缺点，最后给出一个新的损失函数，基于此新损失函数给出相应的健壮支持向量分类机。实验结果表明给出的损失函数和健壮支持向量分类机都是有效的。第二章支持向量机理论基础本章首先介绍了机器学习的相关知识及其存在的不足，从而引出统计学习理论的基本思想。然后介绍了在支持向量机中经常用到的优化理论中的k k t条件和w o l f 对偶理论，以及一些基本概念。在此基础之上，概要介绍了支持向量机和核函数理论，并给出了支持向量机分类的数学模型。2 1机器学习机器学习( m a c h i n el e a m i n g ) 是人工智能的核心，是使计算机具有智能的根本途径。至今，还没有统一的“机器学习”的定义，而且也很难给出一个公认的和准确的定义。尽管如此，为了便于进行讨论，有必要对机器学习给出定义，即使这种定义是不完全的和不充分的。顾名思义，机器学习是研究如何使用机器来模拟人类学习活动的一门学科。稍为严格的提法是：机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。2 1 1 学习问题的表示机器学习的目的是根据给定的训练样本对某系统输入输出之间的依赖关系进行估计，使它能够对未知输入做出尽可能准确的预测【l 3 1 。学习问题一般表示为：对，个服从联合概率分布f ( x ，少) 的独立同分布的观测样本( 而，弗) ，( 屯，北) ，( 而，m ) ，学习问题就是从给定的函数集 厂( x ，口) 中选择一个最优函数 ( x ，口) ) ，使得期望风险r ( 口) = 弘( j ，( x ，a ) ) 订( x ，y )( 2 1 1 )最小。其中，厂( x ，口) 为预测函数，a 为函数的广义参数， 厂( x ，a ) ) 可以表示91 0西安电子科技大学博士学位论文：原始空间中支持向量机若干问题的研究任何函数集! 三( y ，厂( x ，口) ) 度量了由于使用厂( x ，a ) 对y 进行预测而造成的损失。通过选择不同形式的损失函数可以构成不同类型的学习机器。学习问题的形式化表示涉及面很广，最基本的机器学习问题有三类：模式识别( 分类) 、函数逼近( 回归估计) 和概率密度估计。本论文主要研究模式识别问题，对后两类机器学习问题不作详细讨论。对于模式识别问题，输出y 只取两种值，可分别表示为y = o ，1 ) 或 一1 ，1 ，并令厂( x ，口) 为指示函数( 指示函数既只有o 或1 两种取值的函数) ，损失函数可以定义为：m “础) ) - 蒜篇?( 2 m )对于这个损失函数，( 2 1 1 ) 式的期望风险确定了训练器和指示函数厂( x ，a ) 所给出的答案不同的概率，我们把指示函数给出的答案与训练器输出不同的情况即y 厂( x ，a ) 的情况称为分类错误。因此，对于模式识别问题来说，学习问题就是根据给定的观测样本，在概率分布f ( x ，y ) 未知的情况下，寻找使得分类错误概率最小的预测函数厂( x ，a 1 。2 1 2 经验风险最小化在上述学习问题表述中，学习的目标在于使得期望风险最小化。但是，由于概率密度f ( x ，y ) 未知，公式( 2 1 1 ) 表示的期望风险无法计算。因此，传统学习方法采用了经验风险最小化原则( e m p i r i c a lr i s km i n i m i z a t i o n ，e m r ) ，即用观测样本的损失定义的经验风险，( a ) = 三( m ，厂( 墨，a ) )( 2 1 3 )j = l作为对期望风险的估计。经典的模式识别分类器绝大多数都是基于经验风险最小化原则的，比如在回归估计问题中的最小二乘方法、概率密度估计中的最大似然方法等都是e m r 原则的具体实现。事实上，用e m r 原则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法。首先，( a ) 和r ( a ) 都是a 的函数，概率论中的大数定理只说明了( 在一定条件下) 当样本趋于无穷多时，( a ) 将在概率意义上趋近于r ) ，并没有保证( 口) 和只( a ) 在同一个点上取得最小值；第二章支持向量机理论基础其次，没有理论保证在样本无穷多条件下得到的学习机器，在样本数有限的情况下仍能得到好的结果。2 1 3 学习机器的泛化能力e m r 原则希望通过最小化训练误差来实现最小化测试误差的目的，因此在早期的机器学习研究中，人们总是把注意力集中在如何使如。( a ) 更小，但很快发现一味追求训练误差小并不总能达到好的预测效果。人们把学习机器根据已有数据( 训练数据) 建立的模型对新数据( 测试数据) 做出正确反应的能力称为泛化能力( g e n e r a l i z a t i o np e r f 0 肌锄c e ) ，泛化能力也被称为推广能力。在某些情况下，当训练误差过小反而会导致泛化能力的下降，比如当学习机器“记住”所有训练样本，则训练误差为零，但是实际上这种学