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

摘要 统计学习理论为研究小样本情况下机器学习问题提供了有力的理论基础。它 使用结构风险最小化原则，综合了统计学习、机器学习和神经网络等方面技术， 在最小化经验风险的同时，有效地提高了算法泛化能力。支持向量机是在该理论 体系下产生的一种新的、非常有力的机器学习方法。它较好地解决了以往困扰很 多学习方法的小样本、非线性、过学习、高维数、局部极小点等实际问题，具有 良好的潜在应用价值和发展前景。目前，统计学习理论和支持向量机作为小样本 学习的最佳理论，受到越来越广泛的重视，成为人工智能和机器学习领域新的研 究热点。本文综述了支持向量机的研究现状，针对目前存在的几个问题：不平衡 调整问题、大样本减样和除噪问题、两种支持向量算法目1 s u p p o r tv e c t o rm a c h i n e s ( 或s v m ) 与s u p p o r tv e c t o rd o m a i nd e s c r i p t i o n ( 或s v d d ) 的结合问题、核心向 量的性能和应用问题以及s v d d 算法在不确定型决策中的应用等问题进行研究。本 文的主要工作如下： 1 研究了不平衡支持向量机的调整方法。不平衡数据集的学习问题被公认为机器 学习领域的难题之一，其困难主要来自于不平衡数据集本身的特点：例如，样本数 量少的类其样本不足，样本的分布并不能很好地反映整个类的实际分布。因此标 准支持向量机在应用于不平衡数据集时，往往把少数类的样本错分，尽管整体的 分类精度比较高，但数量少的类的分类精度非常低。本文针对支持向量机中两类 不平衡数据的分离超平面提出一种调整算法。该算法根据样本投影分布和样本容 量所提供的信息给出两类惩罚因子比例，从而得到一个新的分离超平面。实验结 果显示了该方法的良好性能。 2 研究了样本的减样和除噪问题。在使用支持向量机分类时，存在以下两个问题： 一是当两类训练样本中存在野点( 噪点) 时，分类的精度较低；二是对大规模样 本集，所占用的内存空间较大，训练时所需时间较长。针对以上问题，我们分别 基于欧氏距离和核距离，根据概率论的知识定位分析了野点( 噪点) 及多余样本点 的般比例情况，给出一种减样方法。实验结果表明该方法与标准s v m 相比， 能保持或提高分类精度；对于大样本来说不仅能保持精度不减，而且还能较大地 提高分类速度，具有较强的实用性。 3 将支持向量机与支持向量域描述结合起来，提出一种分类器。支持向量机在学 习阶段，所有样本参加训练，因此需要较大的内存空间和较长的训练时间；而支 持向量域分类器( s u p p o r tv e c t o rd o m a i nc l a s s i f i e r ，或s v d c ) ，只训练一类样本点， 因此，分类时训练时间较短，但精度较低。为了减少s v m 的训练时间，提高s v d c 的精度，我们建立一种新的分离超平面，即基于支持向量域的分离超平面。该算 法是从整体上考虑分类信息，实现了s v d d 和s v m 的结合。实验结果显示了该 方法的有效性。 4 提出了核心向量的重要概念，并把核心向量集应用于支持向量机的改进。为了 有效提取样本类信息，基于s v d d 算法依据参数选择，剔除支持向量，找核心向 量。为了研究核心向量的性能，分别使用线性以及径向基核函数对样本数据进行 描述，从理论上证明了核心向量在样本集中，在对应参数下具有最大密度值，因 而得出核心向量包含最大信息量的重要结论。因此，核心向量不仅可以作为样本 的期望点估计，而且可以提炼控制向量，改善s v m 的分类效果。 5 将支持向量域描述算法应用在不确定型群决策中。分别研究了模糊判断和区间 判断两种逆判问题。对于模糊判断的逆判问题，是以模糊互反判断为准，使用 s v d d 算法，寻找公共信息，根据信息的贡献量决定专家的评判权重。对于区间 判断的逆判问题，通过对区间判断矩阵的点向量分解，采用径向基核函数，使用 s v d d 算法提取群体的公共信息，同样根据信息贡献量决定专家的权重。该研究 充分利用了s v d d 的描绘功能，抓住主要信息，比较适合于不确定型的群决策问 题。它不仅开拓了s v d d 的研究领域，而且为不确定型群决策的研究提供了有效 的技术。 关键词：统计学习理论，支持向量机，支持向量域描述，核函数，不平衡，减样， 野点( 噪点) ，核心向量，模糊判断，群决策。 a b s t r a c t s t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) p r o v i d e sap o w e r f u lt h e o r e t i c a lb a s i sf o r m a c h i n el e a r n i n gi ns t u d y i n gs m a l ls a m p l e b yu s i n gt h es t r u c t u r a lr i s km i n i m i z a t i o n t oi n t e g r a t et e c h n i q u e so ft h es t a t i s t i c a ll e a r n i n g ，m a c h i n el e a r n i n ga n dn e u r a ln e t w o r k e t ca n de f f i c i e n t l yi m p r o v eg e n e r a l i z a t i o na b i l i t yo fa l g o r i t h mu n d e re m p i r i c a lr i s k m i n i m i z a t i o n s u p p o r tv e c t o rm a c h i n e ( o rs v m ) i san e wa n dv e r y p o w e r f u lm a c h i n e l e a r n i n gm e t h o dg e n e r a t e du n d e rs u c hat h e o r e t i c a ls y s t e m s v mi so fg o o dp o t e n t i a l a p p l i c a b i l i t ya n dd e v e l o p m e n tp r o s p e c t ，f o ri tc a ns o l v ew e l lm a n yp r a c t i c a lp r o b l e m s t h a tp u z z l em a n ye x i s t i n gl e a r n i n gm e t h o d s ，s u c ha ss m a l ls a m p l e ，n o n l i n e a r i t y ，o v e r l e a r n i n g ，h i 曲d i m e n s i o n a ln u m b e ra n dl o c a lm i n i m a lp o i n te t c c u r r e n t l y ，s l ta n d s v m ，a st h eb e s tt h e o r yf o rs m a l ls a m p l el e a r n i n g ，h a sr e c e i v i n gw i d ea t t e n t i o n ，a n d b e c o m i n gan e wr e s e a r c hh o t s p o ti nm a c h i n el e a r n i n ga n da r t i f i c i a li n t e l l i g e n c e i nt h i s p a p e r ，w ef i r s t l yi l l u s t r a t ee x i s t i n ga l g o r i t h ma n da p p l i c a t i o nr e s e a r c h e so ns v m s e c o n d l y ，w es t u d yi nd e t a i ls o m ee x i s t i n gp r o b l e m sc o n c e r n e dn o w ，s u c ha st h e u n b a l a n c e dp r o b l e m s ，d e s a m p l i n ga n dd e n o i s i n gp r o b l e m s ，c o m b i n a t i o np r o b l e m so f t w ok i n d so f s u p p o r t v e c t o r a l g o r i t h m ss v ma n ds u p p o r t v e c t o rd o m a i n d e s c r i p t i o n ( o rs v d d ) ，p e r f o r m a n c e sa n da p p l i c a t i o n so fc o r ev e c t o r sa n da p p l i c a t i o n p r o b l e mo fs v d da l g o r i t h mt ou n c e r t a i ng r o u pd e c i s i o ne t c t h em a i nw o r k si nt h i s p a p e ri n c l u d ec o n t e n t sa sf o l l o w s ： 1 s t u d yt h ea d j u s t m e n tm e t h o df o ru n b a l a n c e ds u p p o r tv e c t o rm a c h i n e s t h el e a r n i n g o fu n b a l a n c e dd a t as e ti sr e g a r d e da so n eo ft h eo p e nd i f f i c u l tp r o b l e m si nt h ea r e ao f m a c h i n el e a r n i n g ，w h e r et h e d i f f i c u l t yc o m e sm a i n l yf r o mt h e f e a t u r eo ft h e u n b a l a n c e dd a t ai t s e l f f o ri n s t a n c e ，t h ec l a s sw i t hf e ws a m p l e sl a c k ss a m p l e s ，w h i c h c a nn o tr e f l e c tw e l lt h ep r a c t i c a ld i s t r i b u t i o no fw h o l ec l a s s t h e r e f o r e ，t h es t a n d a r d s v mo f t e nm a k e sm i s t a k e sw h e ns e p a r a t i n gt h es a m p l e sf r o mt h ec l a s sw i t hf e w s a m p l e si na p p l i c a t i o nt ou n b a l a n c e dd a t as e t t h i sr e s u l t si nt h ef a c tt h a tt h ec l a s sw i t h f e ws a m p l e sh a sl o wp r e c i s i o nt h o u g ht h ew h o l ec l a s s i f i c a t i o np r e c i s i o ni sh i g h t h i s p a p e rp r o p o s e sa na d j u s t m e n ta l g o r i t h mf o rt h es e p a r a t i n gh y p e r p l a n eo ft w oc l a s s e so f u n b a l a n c e dd a t ai ns v m w eu s et h ei n f o r m a t i o np r o v i d e db ys a m p l ep r o je c t i o n d i s t r i b u t i o na n ds a m p l es i z et od e t e r m i n et h er a t i oo ft w oc l a s s e so f p e n a l t yf a c t o r sa n d t h e no b t a i nan e ws e p a r a t i n g h y p e r p l a n e e x p e r i m e n t r e s u l t ss h o wt h eg o o d p e r f o r m a n c e so ft h em e t h o d 2 s t u d yt h ed e s a m p l i n ga n dd e n o i s i n gp r o b l e m s t h e r ee x i s tt w op r o b l e m si nu s i n g s v mt op e r f o r mc l a s s i f i c a t i o n sa sf o l l o w s ：o n ei st h el o wc l a s s i f i c a t i o np r e c i s i o nd u e t ot h ee x i s t e n c eo fo u t l i e r s ( o rn o i s e s ) i ns a m p l es e t ；a n o t h e ri sl o n gt r a i n i n gt i m ef o ra l a r g es c a l es a m p l es e td u et or e q u i r i n gg r e a tm e m o r ys p a c e f o ra b o v ep r o b l e m s ， a c c o r d i n gt op r o b a b i l i t yt h e o r yw ea n a l y z ei nl o c a t i o ng e n e r a lp r o p o r t i o n so fo u t l i e r s ( o rn o i s e s ) a n ds u r p l u ss a m p l e s ，a n dp r o p o s ead e s a m p l i n gm e t h o db a s e do ne u c l i d d i s t a n c ea n dk e r n e ld i s t a n c e ，r e s p e c t i v e l y t h ee x p e r i m e n t ss h o wt h a tt h ep r o p o s e d m e t h o dc a nk e e po ri m p r o v ec l a s s i f i c a t i o np r e c i s i o nc o m p a r e dw i t hs v m g e n e r a l l y ； f o r l a r g es a m p l e ，t h e m e t h o dc a nn o t o n l yk e e pp r e c i s i o n ，b u ta l s oi m p r o v e c l a s s i f i c a t i o ns p e e dg r e a t l y , w h i c hi so fs t r o n gp r a c t i c a l i t y 3 ak i n do fc l a s s i f i e ri sp r e s e n t e db yc o m b i n i n gs v ma n ds v d d s i n c ea l lt h e s a m p l e sp a r t i c i p a t ei nt r a i n i n gf o ru s i n gs v m ，i tn e e d sg r e a tm e m o r ys p a c ea n dl o n g t r a i n i n gt i m e ；w h i l es v d c ( s u p p o r t v e c t o rd o m a i nc l a s s i f i e r ) i sl o wi nc l a s s i f i c a t i o n p r e c i s i o nt h o u g hi t n e e d sar e l a t i v e l yl i t t l et i m ei nc l a s s i f i c a t i o n t or e d u c et r a i n i n g t i m eo fs v ma n dt os p e e ds v d c ，w eb u i l dan e ws e p a r a t i n gh y p e r p l a n e ，n a m e l y s e p a r a t i n gh y p e r p l a n eb a s e d o ns v d d t h ea l g o r i t h mc o n s i d e r sc l a s s i f i c a t i o n i n f o r m a t i o na saw h o l e ，a n di m p l e m e n t st h ec o m b i n a t i o no fs v ma n ds v d d e x p e r i m e n t ss h o wt h ee f f i c i e n c yo ft h em e t h o d 4 p r o p o s et h ec o n c e p to fc o r ev e c t o r , a n da p p l yc o r ev e c t o rs e tt oi m p r o v es v m t o e x t r a c ts a m p l ei n f o r m a t i o ne f f i c i e n t l y , w ed e l e t ea l lt h es u p p o r tv e c t o r sa n df i n dc o r e v e c t o r sb yc h o o s i n gp a r a m e t e r sb a s e do ns v d d l i n e a rk e r n e la n dr a d i a lb a s i sk e r n e l f u n c t i o na r ea p p l i e dt od e s c r i b es a m p l ed a t ar e s p e c t i v e l yt os t u d yt h ep e r f o r m a n c eo f c o r ev e c t o r i ti sp r o v e dt h e o r e t i c a l l yt h a tac o r ev e c t o ri so fm a x i m a ld e n s i t yw i t h r e s p e c t t o c o r r e s p o n d i n gp a r a m e t e r s i n g i v e ns a m p l es e t ，h e n c ew eo b t a i nt h e i m p o r t a n tc o n c l u s i o nt h a ta c o r ev e c t o rc o n t a i n sm a x i m a li n f o r m a t i o ni nt h es a m p l es e t t h e r e f o r e ，a n yc o r ev e c t o rc a nb ee v a l u a t e dt h ee x p e c t a t i o np o i n to fas a m p l es e t ， f u r t h e rm o r e ，c o r ev e c t o rs e tc a nb et r a i n e dt of i n dc o n t r o lv e c t o rt oi m p r o v es v m 5 a p p l ys v d dt ou n c e r t a i ng r o u pd e c i s i o n r e s p e c t i v e l ys t u d yt h et w ok i n d so f i n v e r s ej u d g r n e n tp r o b l e m so ff u z z yj u d g m e n ta n di n t e r v a lj u d g m e n t f o rt h ef u z z y j u d g r n e n t ，w ec h o o s ef u z z yr e c i p r o c a lj u d g m e n ta st h es t a n d a r dt od e t e r m i n ee x p e r t w e i g h ta c c o r d i n gt ot h ei n f o r m a t i o n a lc o n t r i b u t i o nb yu s i n gs v d dt of i n dc o m m o n i n f o r m a t i o n f o rt h ei n t e r v a lju d g m e n t ，e x p e r tw e i g h t sa r ed e t e r m i n e di nt e r m so ft h e i n f o r m a t i o nc o n t r i b u t i o nb yu s i n gs v d dt oe x t r a c tg r o u pi n f o r m a t i o n ，i nw h i c h i n t e r v a lj u d g m e n tm a t r i c e sa r ed e c o m p o s e da sp o i n tv e c t o r s ，a n dr a d i a lb a s i sk e r n e l f u n c t i o ni sa p p l i e d t h i sr e s e a r c hm a k e sf u l lu s eo ft h ed e s c r i p t i o np e r f o r m a n c eo f s v d d ，h o l d sm a i ni n f o r m a t i o n ，w h i c hi sw e l ls u i t a b l ef o ru n c e r t a i ng r o u pd e c i s i o n p r o b l e m s t h i sm e t h o dn o to n l ye n l a r g e st h er e s e a r c ha r e ao fs v d d ，b u ta l s op r o v i d e s a ne f f i c i e n t l yt e c h n i q u ef o rs t u d y i n gu n c e r t a i nd e c i s i o n k e y w o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y ，s u p p o r tv e c t o rm a c h i n e s ( s v m ) ，s u p p o r t v e c t o rd o m a i nd e s c r i p t i o n ( s v d d ) ，k e r n e lf u n c t i o n ，u n b a l a n c e d ，d e - s a m p l i n g ， o u t l i e r s ( n o i s e s ) ，c o r ev e c t o r ，i n v e r s ej u d g m e n t ，g r o u pd e c i s i o n 西安电子科技大学 学位论文独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：纠互! 呈 i 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有 权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人 保证，毕业后结合学位论文研究课题再攥写的文章一律署名单位为西安电子 科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：幽丕! 乏本人签名：碰lz ：乞 导师签名：弛 日期翌矿：壁： 第一章绪论 第一章绪论 本章首先概述机器学习的发展历程、基本问题以及主要理论成果，对基于统 计学习理论的支持向量机方法的产生、主要研究内容以及国内外的研究现状进行 了阐述和分析。最后是本文的研究目的、意义以及全文的内容安排。 1 1 研究背景 人类可以通过归纳学习，获得对客观世界的认识和规律，进而利用这些规律 帮助人类认识现有的世界，同时帮助人类对未知的现象做出正确的预测和判断。 人们把从过去的数据和知识中学习并获取规律的能力称为“学习能力”。利用获得 的规律不仅可以解释己知现象，而且能够对未知现象做出正确的预测和判断，这 种能力称为“泛化能力”。基于数据的机器学习就是用机器来模拟人类学习活动， 使机器能够自动获取新的知识和技能，不断完善其性能，并识别现有的知识。机 器学习是现代人工智能技术的一个重要研究内容和方向，其主要研究是从观测数 据( 样本) 出发寻找规律，利用这些规律对未知数据或者无法观测的数据进行预测， 其最终目的是使得机器具有良好的泛化能力。1 4 t v a p n i k ( 1 9 9 5 ) 等人创立的统计学习 理论，为小样本的学习问题建立了坚实的理论基础，较好地解决了小样本、非线 性、高维数据和局部极值等实际问题。一种新的学习算法支持向量机是统计学 习理论的具体实现，尽管有许多良好性能，但仍处于发展研究阶段，还存在许多 问题有待进一步完善。 1 1 1 机器学习的发展历史 关于机器学习的研究，我们将它的研究和发展历程分成如下四个阶段【卜5 】 1 机器学习的产生 1 9 5 7 年r o s e n b l a t 提出第一个学习机器的模型，称为感知器【6 】。它在机器学习领 域中具有里程碑的意义，标志着人们对学习过程进行数学研究的真正开始。 r o s e n b l a t 将感知器的模型表示为一个计算程序，并通过实验说明了这个模型具有 一定的泛化能力。1 9 6 2 年，n o v i k o f 证明了感知器的第一个重要定理【7j 。该定理在 2 一 支持向量机中若干问题及应用研究 创建学习理论中起了十分重要的作用。 2 学习理论基础的创立 在感知器被提出来之后，人们很快提出了其他类型的学习机器，如自适应学 习机，隐马尔可夫模型等来解决实际问题。但这些机器只是解决实际问题的工具， 并非学习问题的一般模型。2 0 世纪6 0 7 0 年代期间，是统计学习理论获得大发展的 时期，产生了经验风险最小化原则的理论和算法复杂度的思想【8 ，9 】。 3 人工神经网络 1 9 8 6 年，l e c u n t l o 】、r u m e l h a r te ta l 1 1 1 独立地提出了构造感知器所有神经元的向 量系数的后向传播算法( b a c kp r o p a g a t i o n ，b p ) 。此方法采用连续的s i g m o i d 函数修 改了感知器的m c c u l l o c h p i t t s 神经元模型，使得对于任意固定的输入都存在对应于 所有神经元的所有系数的梯度。利用计算出的梯度，人们可以应用任何基于梯度 的方法来构造对预期函数的无限逼近。此后，感知器被改称为神经网络，并在手 写字体识别等问题中表现出较好的性能。然而，神经网络方法的本质是建立在样 本数无穷大的经典统计学理论基础上的，缺乏统一的数学理论基础。另外，神经 网络结构的选择和优化是基于启发式方法的，本身还存在一些固有的缺陷，例如， 欠学习、过学习、局部极值等。这些因素造成了对神经网络的研究无法从本质上 推进对学习过程本质的认识。 4 统计学习理论 v a p n i k 等人从六、七十年代开始致力于统计学习理论的研究。到九十年代中 期，随着其理论的不断发展和成熟，人们研究的重点转移到对神经网络的这种替 代方法的研究上。统计学习理论是一种专门研究小样本情况下机器学习规律的理 论。与传统的统计学相比，该理论针对小样本统计问题建立了一套新的理论体系， 在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有 限信息的条件下得到最优结果。现在，结构风险最小化原则成了人们研究的热点， 统计学习理论开始受到越来越广泛的重视。与神经网络相比，支持向量机方法具 有更坚实的数学理论基础，可以有效地解决有限样本条件下的高维数据模型构建 问题，并具有泛化能力强、收敛到全局最优、维数不敏感等优点。目前，统计学 习理论和支持向量机已经成为继衬i 经网络之后机器学习领域最热门的研究方向之 一，并有力地推动了机器学习理论的发展。 第一章绪论 1 1 2 机器学习问题的表述 学习问题的一般表示如下：对于服从联合概率分布f ( x ，y ) 的，个独立同分布 ( i i d ) 的观测样本( _ ，y 。) ，( 石：，y ：) ，( x 1 , y f ) ，学习问题就是从给定的函数集： f = f ( x ，口) ，口人) 中选择出一个最优函数f ( x ，口) ) ，使得期望风险 r ( a ) = s l ( y ，厂( x ，口) 矽( 工，少) ( 1 - 1 ) 最小。其中，f ( x ，口) 为预测函数，口为函数的广义参数，l ( y ，f ( x ，口) ) 是由于 f ( x ，口) 的预测误差而造成的损失。学习问题的形式化表示涉及面很广，最基本的 机器学习问题有三类：模式识别( 分类) 、函数逼近( 回归估计) 和概率密度估计【1 ，4 】。 不同类型的学 - j 问题具有不同形式的损失函数。其中，本论文将主要以模式分类 问题为研究对象，对后两类机器学 - j 问题不作详细的讨论。对于模式识别问题， 目标输出y 只取两种值，即y 一l ，+ 1 ) ，函数集f = f ( x ，口) ，口人) 是指示函数集， 并且，采用如下定义的“0 1 ”损失函数： 地m 川，= 0 舅嚣：三； m 2 ， 其中，y f ( x ，口) 的情况称为“分类错误”。因此，对于模式识别问题来说，学习 问题就是根据给定的观测样本，在概率分布f ( x ，y ) 未知的情况下，从函数集中寻 找使得分类错误概率最小的预测函数f ( x ，口+ ) 。 1 1 3 经验风险最小化 传统学习方法采用了经验风险最小化原则( e m p i r i c a lr i s km i n i m i z a t i o n ， e r m ) ，即采用观测样本的损失定义的经验风险 ( 咖詈妻m 删 ( 1 3 ) 作为对期望风险的估计。 概率论中的大数定律告诉我们在一定条件下，当样本数目趋于无穷大时， 4 一 支持向量机中若干问题及应用研究 g e m p ( a ) 在概率意义下趋近于期望风险。因此，一味地追求经验误差r e m p ( 口) 最小 化并不是总能获得非常好的预测效果。例如，在某些情况下，可以采用复杂的函 数( 或学习机器) 使得经验误差降低至0 ，但是，反而导致学习机器的泛化能力的下 降，原因是出现了“过学习”现象。因此经过长期的应用，对于有限样本情况下， 我们得出如下结果： ( 1 ) 经验风险最小并不一定意味着期望风险最小； ( 2 ) 学习机器的复杂性不但应该与所研究的系统有关，而且还要和有限数目的 样本相适应。 这就是有限样本下学习机器的复杂性和泛化能力之间的矛盾。因此，我们需 要一种新的学习原则来代替传统的经验风险最小化原则，它能够指导我们在有限 样本或小样本情况下获得具有优异泛化能力的学习机器。统计学习理论的发展为 此问题的解决提供了坚实的理论基础。 1 1 4 学习过程的一致性条件 随着对一般学习现象的研究，人们逐渐认清了机器学习的统计本质，开始采 用数学分析的手段，对一般学习过程进行形式化分析，摆脱了传统的基于渐近理 论统计学习方法的局限。学习过程的一致性结论是统计学习理论的基础，也是与 传统渐近统计学的基本联系所在。只有满足学习过程一致性条件，才能保证在学 习样本无穷大时，经验风险最小化原则下得到的最优学习机器的性能趋近于期望 风险最小时的最优结果。只有满足一致性条件，才能说明学习方法是有效的。 定义1 1 2 1 设 ( 五，y 。) ，( x ，y f ) ) 是按照概率分布f ( x ，y ) 得到的独立同分 布( i i d ) 的观测样本集合，f ( x ，口，) 是函数集o 中使得经验风险r e i n p ( 口，) 最小化的 预测函数。若对任意的占 0 ，有 ! i m p ( r ( 口，) 一i n f r ( o o ) s ) 2 0( 1 4 ) 卜 ，c v ! i m 尸 ( 尺。，p ( 口，) 一i n f r ( o r ) ) s ) 2 0 ( 1 - 5 ) 则称经验风险最小化原则对于函数集下和概率分布f ( x ，y ) 是一致的。换句话说， 如果经验风险最小化是一致的，那么它必须提供一个如下的函数序列 第一章绪论 f ( x ，口，) i ，= 1 , 2 ，) ，使得期望风险和经验风险收敛到一个可能的最小风险值。 定理1 1 i , 1 2 1 设存在常数a 和曰，使得对于函数集： f = f ( x ，a 川口人) 的所有函数和给定的概率分布f ( x ，y ) ，有下列不等式成 立： a 占) = 0 ( 1 7 ) 卜” 厂p 此定理是v a p n i k 和c h e r v o n e n k i s 于1 9 8 9 年提出的，在统计学习理论中具有非常 重要的地位，因此称为“学习理论的关键定理”。它把学习一致性的问题转化为公 式( 1 7 ) 定义的一致收敛问题，解释了经验风险最小化原则在什么条件下可以保证 是一致的。 1 1 5 统计学习理论中学习过程的推广能力 学习算法推广能力的分析是学习机器性能和发展新的学习算法的重要基础。 它是建立在v c 维基础上的。v c 维的定义如下： 1v c 维的概念 定义1 2 1 , 1 2 1 ( 指示函数集的v c 维) 对于一个指示函数集f ，如果存在h 个样本 能够被函数集里的函数按照所有可能的2 6 种组合分成两类，则称函数集f 能够把样 本数为h 的样本集打散。函数集f 的v c 维就是它能打散的最大样本数目h 。若对任 意数目的样本，函数集f 都有函数能将它们打散，则称函数集的v c 维是无穷大的。 一般而言，v c 维越大，则学习机器越复杂，学习容量越大。 2 推广能力的界 统计学习理论从v c 维的概念出发，研究了各种函数集情况下的经验风险和期 望风险之间的关系，即泛化能力的界。定理1 2 给出了任意函数集 6 一 支持向量机中若干问题及席用研究 f = f ( x ，o t ) i 口a ) 的构造性的且与分布f ( x ，y ) 无关的泛化能力界，可以用来估计 和控制学习机器的泛化能力。 定理1 2 1 ，1 2 1 ，设 ( 工。，y 。) ，( 石，y ，) ) 是依概率分布f ( 工，y ) z 。，i 。 一- - 同 分布的观测样本集合，任意函数集f = 厂( x ，口，) | o r ，人 v c 维是h ；则对f 中的任 意函数f ( x ，口，) ，下面的不等式至少依概率1 7 7 成立( 满足0 r l 1 ) r ( 口) 一g e m p ( 口) + 1 h ( 1 n ( 2 l h + i ) - l n ( q 4 ) ) - 0 - 8 ) 上述定理说明了学习机器的期望风险是由两部分组成的：第一部分是经验风 险；另一部分称为置信范围，是关于函数集f 的v c 维h 的增函数。显然，如果l h 较大，期望风险值由经验风险值决定，此时为了最小化期望风险，我们只需要最 小化经验风险：相反，如果l h 较小，经验风险最小并不能保证期望风险一定最小， 此时我们必须同时考虑不等式( 1 8 ) 右端的两项之和( 称为“结构风险”) 。 3 结构风险最小化原则 结构风险最小化( 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 r m ) 是针对小样本条件下的机 器学习问题而提出的一种归纳推理原则3 1 。定理1 2 表明，在小样本情况下控制学 习机器的泛化能力，必须同时使得不等式( 1 8 ) 的右端的结构风险( 两项之和) 最小 化。为了寻找使得结构风险达到最小的函数f ( x ，口) ，统计学习理论提出了一种新 的策略。它将函数集s = f ( x ，口) i 口人) 看成具有一定的结构，并由一系列嵌套的 函数子集s 。= f ( x ，口) l 口人。) 组成，它们满足 s lcs 2c cs 。c ，且s = u s 。 ( 1 - 9 ) 其中，函数子集s 。的v c 维h t 是有限的，且满足h ， h ： 0 的展开式( 即k ( x ，x ) 描述了某个 高维h i l b e r t 空间好中的内积) 。 的充分必要条件是： 露( 工，x7 ) = 岱。i ( x ) 。( x ) k = l ( 1 1 0 ) 量女( x ，x ) g g 蚴。( 1 - l 1 ) 对于所有的g l 2 ( z ) 成立，其中。( 曲表示对应于特征值口。的特征函数。 本文用到的m e r c e r 核函数包括： ( 1 ) 线性核：k ( x ，茗) = x 石 ( 2 ) 多项式核：k ( x ，x ) = ( o x ) + 1 ) d 核参数d 为多项式的阶数。 ( 3 ) 径向基核：k ( x ，x ) = e x p ( 一| | x x 1 1 2 ) 2 0 r 2 核参数仃r 。 定义1 4 f 1 , 1 2 令五，x ：，_ 是输入空间z 中的有限样本( zcr ”) ，且托，) ：z h r 是给定的醚锻钉核函数。我绷称第i 行第歹到元素为略一是茗；，一) 的；z 阶矩 阵，k 为克( ，) 关于x l ，彳2 ，x z 的核矩阵或g r a m 矩阵。 1 2 2 最优超平面 给定调练数据：( ，y ，) ，“，y ，) ，而r d ，y f + l ，一l ，定义一个超平面： w x + 6 = 0 f l 一1 2 ) 将给定的数据分开。由于给定数掘是可分的，所以这个向量集可以被个超平面 没有错误地分开。如果这个超平面使得分离超平面最近的向鏊与超平面的距离最 大。则这个超平面称为最优超平面。 如图1 2 ，h 是把两类没有错误分开的分类面，。、胃。分别为过各类样本中 离分类线最近的点且平行予分类面的平面，嚣；和胃：之闻的距离瑟毽做分类