（计算机软件与理论专业论文）基于核函数的机器学习方法研究.pdf

摘要 近年来，v a p n i k 等人基于统计学习理论提出的支持向量机方法是机器学 习非常活跃的研究领域，并正迅速成为数据分析的有力工具之一尽管有坚 实的理论基础，支持向量机方法在具体实现上仍存在许多有待进一步研究和 探讨的问题 在以往的工作中，大部分的研究和应用都是基于l 1 一软间隔支持向量机 方法的本文首先较为系统地讨论了l 2 一软间隔支持向量机方法，探讨了它 与l l 一软间隔支持向量机方法相区别的一些性质，如支持向量分布和几何特 性等 在实现算法上，本文针对l 2 一软问隔支持向量机方法提出了一种基于积 极集法的快速支持向量机训练算法，该算法采用了分解迭代的策略，使用积 极集方法来求解二次规划子问题，有效地简化了支持向量机的实现步骤在 多个标准数据集上的数值实验表明，该算法对正则参数g 的变化不敏感，且 在正则参数取值较大c 1 0 时，新算法所需的训练时间比经典的s v m l i 口h t 算 法要少的多，而得到的预测准确率可以与基于l 1 一软间隔支持向量枧的算法 相比拟此外，本文从几何直观角度研究了l 2 一软间隔支持向量机方法，改 进了k e e r t h i 等人提出的最小模算法使得该算法在所需计算量上可以与近来 k e e r t h i 等人提出的最近点对算法( 即n p a 算法) 相比拟，但在编码实现上要 简单得多 本文进一步研究了大间隔分类方法将l 2 一软间隔方法与k e r n e l a d a t r o n 算法相结合，改进了k e r n e l o a d a t r o n 算法，使其不再受样本在特征空间中是线 性可分的假设的约束，从而在特征空间中仍然得到统计力学对其收敛速度的 理论保证同时改进了m i n o v e r 方法，给出了一种加快k e r n e l a d a t r o n 算法收 敛速度的新方法 最后，本文研究了一种基于加权p a r z e n 窗的数据聚类方法该方法放宽 了p a r z e n 窗的权系数限制，采用加权p a r z e n 窗获得对数据分布状态的良好描 述，并根据数据的分布状态得到不同模式类的分界面，将聚类过程转变为求 解加权p a r z e n 窗权值的线性规划阉题 主题词支持向量机l 2 一软间隔积极集法最近点加权p a r z e n 窗 a b s t r a c t i nr e c e n ty e a r s ，an e wm a c h i n e - l e a r n i n ga l g o r i t h m ，w h i c hi s b a s e do nv a p n i k s s t a t i s t i c a ll e a r n i n gt h e o r y , n a m e ds u p p o r tv e c t o rm a c h i n e s ( s v m s ) h a sa t t r a c t e d al o to ff o r e i g na n dd o m e s t i cr e s e a r c h e r sf o ri t sf i r m l yt h e o r e t i c a lb a s i sa n de x c e l l e n t g e n e r a l i z a t i o np e r f o r m a n c e i tr a p i d l yb e c o m e so n eo ft h ep o w e r f u lt o o l s f o rd a t a a n a l y s i s h o w e v e r t h e r ea r em a n yp r o b l e m st ob es o l v e db e f o r ei tb e c o m e sap r a t i c a l m e t h o d a l m o s ta l lo ft h ep r e v i o u ss t u d i e sa n da p p l i c a t i o n sa r eb a s e do i ll 1s o f tm a r g i n s u p p o r tv e c t o rm a c h i n e s ( l 1 一s v m s ) i nt h i st h e s i s ，w ef i r s t l ya n a l y z et h ed i f f e r e n t p r o p e r t i e so f l 2s o f tm a r g i ns u p p o r t v e c t o rm a c h i n e s ( l 2 - s v m s ) f m m l 1 一s v m s ，s u c h a st h ed i s t r i b u t i o n so fs u p p o r tv e c t o r sa n dg e o m e t r yp r o p e r t y f o l l o w i n gt h ea b o v ed i s c u s s i o n ，an e wa l g o r i t h mf o rl 2 一s v m sb a s e do na c t i v e s e tm e t h o di sp r o p o s e d t h i sn e wa l g o r i t h mr e a c h e st h eo p t i m a ls o l u t i o nb ys o l v i n g af i n i t en u m b e ro fl i n e a re q u a t i o n s ，a n dr e q u i r e sn os p e c i a lq u a d r a t i cp r o g r a m m i n g k n o w l e d g e f o rl a r g el e a r n i n gt a s k sw i t hm a n ys a m p l e s tad e c o m p o s i t i o nm e t h o d ，d u e t oj o a c h i m s ，h s ua n dl i n ，i su s e dt oa v o i de n o r m o u sm a t r i xs t o r a g ea n de x p e n s i v e m a t r i xo p e r a t i o n s n u m e r i c a le x p e r i m e n t so ns e v e r a ls t a n d a r dc l a s s i f i c a t i o np r o b l e m s s h o wt h a to u ra l g o r i t h mi sc o m p a r a b l eo rf a s t e rt h a ns v m i 幻 ta n dw ea l s os t u d yl 2 一 s v m sf r o mt h ev i e w p o i n to fg e o m e t r y , a n di m p r o v et h em i n i m a ln o r m a la l g o r i t h m ( m n a ) w h i c h i sp r e s e n t e db yk e e r t h ia n dh i sc o l l e a g u e s n u m e r i c a le x p e r i m e n t ss h o w t h a tt h ei m p r o v e da l g o r i t h mi sc o m p a r a b l ew i t hn e a r e s tp o i n t sa l g o r i t h ma n df a s t e r t h a nm n a i nt h es t u d yo fl a r g em a r g i nm e t h o d s ，w er e p l a c eh a r dm a r g i nm e t h o dw i t h l 2s o f tm a r g i nm e t h o di nt h ek e r n e la d a t r o na l g o r i t h m t h i sa p p r o a c ha v o i d st h e a s s u m p t i o nt h a ta l ls a m p l e si nt h ef e a t u r es p a c es h o u l db es e p a r a b l e ，a n dk e e p st h e t h e o r e t i c a lg u a r a n t e e ss t u d i e di nt h es t a t i s t i c a lm e c h a n i c sl i t e r a t u r e w ea l s op o i n t o u tt h ed i s a d v a n t a g e so ft h em i n o v e rm e t h o d ，a n di m p r o v ei tt om a k ek e r n e la d a t r o n a l g o r i t h mf a s t e r f i n a l l y ，w es t u d yan e wc l u s t e r i n ga l g o r i t h mb a s e do nw e i g h t e dp a r z e nw i n d o w t h i s a l g o r i t h mf i n d so u tt h eb o u n d a r i e s f o rd i f f e r e n tc l u s t e r sb yu s i n gw e i g h t e dp a r z e n w i n d o wt od e s c r i b et h ed a t ad i s t r i b u t i o ns t a t u s t h u st h ec l u s t e r i n gp r o c e s si sc o n - v e r t e dt ot h ep r o b l e mo fs o l v i n gal i n e a rp r o g r a m m i n gp r o b l e mf o rd e t e r m i n i n gt h e c o e f f i c i e n t s v a l u e so fw e i g h t e dp a r z e nw i n d o w e x p e r i m e n t ss h o wt h a tt h ec l u s t e r ；x 2 0 0 2 盏 中田科学技术大学博士学位论文 x b o u n d a r i e sf o u n do u tb yp r e s e n t e da l g o r i t h ma r es i m i l a rt ot h a tb ys u p p o r tv e c t o r c l u s t e r i n ga l g o r i t h m ，w h i c hi sp r o p o s e db ya s ab e n h u re t c ，a n dl e s st i m ei sn e e d e d i nt h ef o r m e r k e y w o r d ss u p p o r tv e c t o rm a c h i n e s ，l 2s o f tm a r g i n ，a c t i v es e tm e t h o d ，c l o s e s t p o i n t ，w e i g h t e dp a r z e nw i n d o w 致谢 首先要感谢两位导师王晓蒲教授和陈国良教授两位老师严谨的学术精 神和一丝不苟的治学态度使我折服在我完成论文工作的期间，老师们不仅 认真仔细地指导我的论文，而且对我严格要求，鼓励我多思考，并且给我提供 了良好的科研条件他们的谆谆教导使我获益匪浅 同时，我还要衷心地感谢霍剑青教授尽管在繁忙的行政工作压力下，霍 老师还要兼顾我和实验室其他学生的学习和生活她的敬业精神值得我好好 学习 感谢实验室的杨旭、董敏、宛田宾、杨宏彬、郭玉刚等诸位师兄弟姐妹们， 多年来他们一直给我提供了不少帮助，并在精神上给予了我很多支持 感谢同学兼室友王宝善和现在正在国外读书的刘伟等同学。他们不辞辛 苦，多次为我查询和提供了很多有用的学术资料感谢那些曾经帮助过我和与 我交流过的朋友们 感谢那些在网络上与我讨论过学术问题的朋友们，尽管我们互不知名， 但与他们的讨论使我对所作的研究有了更为深刻的理解 最后，向敬爱的父母和姐姐们致以最衷心的感谢他们不遗余力地给了 我精神和物质上的全力支持，使我能够完成学业 插图目录 21 结构风险最小化示意图 9 2 2 线性可分情形下，分类间隔和最优分类面示意图1 2 2 3 核函数将输入空间中的非线性分类面转化为特征空间中的线性分 类面1 3 31 线性可分情形下支持向量分布比较( 图中实线为分类面，虚线为 边界面，支持向量以小圆圈标注) ：( a ) l 1 一s v m ；( b ) l 2 一s v m 2 0 3 2 空间x 中l 2 一s v m 等价于两类样本点构成的凸包间的最近点对 问题 2 l 约束条件下l a g r a n g e 变量的取值范围( 左图中8 = 一1 ，右图中 s = + 1 1 2 5 n p a 算法中，u ，口，= 等相互关系的几何示意图3 0 w i s c o n s i nb r e a s tc a n c e rd a t a s e t ：c p u 计算时间比较3 7 s a t i m a g ed a t a s e t ：c p u 计算时间比较3 7 a d u l t 一1d a t a s e t ：c p u 计算时间比较3 8 a d u l t 4d a t a s e t ：c p u 计算时间比较3 8 n p a 算法中优化对象选择方法几何示意图4 3 c p a 算法中优化对象选择方法几何示意图4 4 a d u l t - 1 数据集：不同算法核函数计算次数随分类间隔的变化4 7 a d u l t - 2 数据集：不同算法核函数计算次数随分类间隔的变化4 7 w e b - 1 数据集：不同算法核函数计算次数随分类间隔的变化4 8 w e b 4 数据集：不同算法核函数计算次数随分类间隔的变化4 8 5 1 参数g 对算法收敛速度的影响：上、中、下三行分别为k a 、 i b k a 以及l 2 一b k a 三种算法的计算结果左列为目标函数的收 敛趋势图示，右列为分类间隔的收敛趋势图示 5 2 m i n o v e r 方法对算法收敛速度的影响：上、中、下三行分别为k a 、 i b k a 以及l 2 一b k a 三种算法的计算结果左列为目标函数的收 敛趋势图示，右列为分类间隔的收敛趋势图示 ， 2 3 4 5 6 7 8 9 加 n 挖 4 4 4 4 4 4 4 4 4 4 4 4 中嗣科学技术太学博士学健论文 v j 5 3 m a x i n c 方法对算法收敛速度的影响：上、中、下三行分别为k a 、 t b k a 以及l 2 一b k a 三种算法的计算结果友列为目标函数的收 敛趋努霞示，右翊为分类闻黼的狡敛趋势圈永。 6 1 加权p a r z e n 窗方法描述数据分布状态 6 2 加权p a r z e n 窗聚类算法( # 2 一u 3 0 ) 6 , 3 加权p a r z e n 窗聚类算法( 口2 = v t o ) 6 , 4 震持向萤聚类算法的聚类结果 6 , 5 加权p a r z e n 窗聚类算法的聚类结架 6 6 模糊c 均值聚类算法的聚类结果 嚣 略n n n 表格目录 3 1 不同支持向量机方法中目标函数的凸性 4 1 测试数据集及其属性 4 2 a s m 算法在不同参数g 下的1 0 - f o l dc r o s s - v a l i d a t i o n 识别率( ) 4 3l i b s v m 在不同参数g 下的1 0 - f o l dc r o s s v a l i d a t i o n 识别率( ) 44 测试数据集及其属性 5 1 k a 、i b k a 和l 2 一b k a 三种算法目标函数值和支持向量数目的 比较 。、。 5 2 测试数据集及其属性 5 3 k a 算法在不同参数a 下的1 0 - f o l dc r o s s - v a l i d a t i o n 识别率( ) 5 4 i b k a 算法在不同参数g 下的l o - f o l dc r o s s v a l i d a t i o n 识别率( ) 5 5 l 2 一b k a 算法在不同参数g 下的l o - f o l dc r o s s 。v a l i d a t i o n 识别率( ) 5 6 不同参数下的l o - f o l dc r 0 8 8 v a l i d a t i o n 识别率比较 61 聚类算法支持向量数目和c p u 时间的比较 2 2 3 6 3 9 3 9 4 6 。号髓乱铊 铀 第一章引言 s t a t i s t i c a ll e a r n i n gt h e o r yn o wp l a y snm o r ea c t i v er o l e ：啦e rt h eg e n e r a la n a l y s i s o fl e a r n i n gp r o c e s s e s t h er e s e a r c hi n 矾ea r e ao fs y n t h e s i so fo p t i m a la l g o r i t h m sw a s s t a r t e dt h e s es t u d i e s ，h o w e v e r , d on o tb e l o n gt oh i s t o r yy e t t h e ya r eas u b j e c to f t o d a y 0r e s e a r c ha c t i v i t i e s v l a d i m i rv a p n i k 1 1研究的背景和意义 机器学习是人工智能领域的一个新的分支学科，是进行复杂数据分析和 构建智能系统的一个十分重要的研究课题它研究对特定问题域进行知识获 取的智能过程和方法，探索人类的认识规律，以模拟人类的学习行为，并借助 于计算机科学和技术建立各种模型，赋予机器( 即计算机系统) 学习和预测的 能力在过去的二十年里，这一学科取得了长足发展，涌现出许多新的学习理 论和方法 1 ，1 2 ，1 3 ，1 4 】其中以统计学习理论为基础的支持向量机方法在模式 识别等领域引起了相当广泛的注意和研究 统计学习理论是v a p n i k 等人提出的一种研究有限样本情形下统计规律及 学习方法性质的理论 1 0 】它为有限榉本的机器学习问题建立了一个良好的理 论框架，较好地解决了小样本、非线性、高维数和局部极小点等实际问题，其 核心思想就是学习机器要与有限的训练样本相适应尽管v a p n i k 等人从六、 七十年代就已经开始致力于统计学习理论的研究工作，但是直到1 9 9 5 年他和 他的合作者明确提出一种新的通用学习方法一支持向量机【3 ，7 】后，该理论 才受到广泛的重视在随后的几年中，统计学习理论在模式识别 4 】、回归函 数估计 2 4 】、密度估计【2 5 】等领域得到了大力的推广和研究，并被成功地应用 于手写字体识别【3 ，2 6 ，2 7 】、人脸检测【2 8 ，2 9 ，3 0 ，4 5 】、文本分类【3 1 ，3 2 ，4 4 】、 特征提取【3 3 ，3 4 】等模式识别问题 在模式识别领域，支持向量机方法目前仍处于研究阶段，并没有成为实用 的方法这是因为它在具体实现上仍然存在许多有待进一步研究和探讨的问 题f 4 ，4 0 ，4 1 。主要有： 模型选择所谓模型选择，即通过有效的方法确定数学模型的参数( 包括核函 数参数和正则参数) ，使学习机器具有最佳的推广能力【3 5 】 简化方法虽然支持向量机方法可以获得良好的推广能力，但在决策速度方面 不及神经网络等其它学习方法简化支持向量机的目的就是加快做出决策、 1 ， 2 0 0 2 年中国科学技术大学博士学位论文 2 的进程4 2 ，4 3 1 多类问题在模式识别问题上，支持向量机方法是基于两类分类问题得到的 尽管在多类问题上出现了很多解决方法【3 6 】，但从计算时间上看这些方法 并不理想 实现算法支持向量机将模式识别等问题归结为一个二次规划问题，这类问题 的求解算法多趋于复杂当问题规模较大时，通常需要耗费相当可观的计 算时间和存储空间 实际上，其中模型选择和多类问题的解决是以快速的实现算法为基础的 因为，目前对学习机器推广能力的有效估计通常是通过1 0 0 错误率( l e a v eo n e o u te r r o r ) 1 l 】或其估值定量描述的 3 5 】，对每一组参数值至少需要执行一次训 练过程来获得l o o 错误率；而多类问题通常被分解为两类问题进行求解，训练 过程所消耗的计算时间和存储空间仍然依赖于现有的实现算法如果将多类 问题转化为单一的规划问题来求解，通常比分解为两类问题的做法需要更多 的计算时间【3 6 因此，寻找快速而有效的实现算法对支持向量机方法的实用 化将是非常有意义的 此外，支持向量机方法在解决有监督学习问题上有出色的表现，如何将它 的思想用于解决无监督学习问题是一个新的挑战 1 2 研究现状分析 统计学习理论的基础理论部分已经较为完善，目前的研究多偏向于它的 实现方法等近几年来，对支持向量机方法及其思想的研究规模达到了空前 的盛大仅从下面的数据就可以看到这一点：将“s u p p o r tv e c t o rm a c h i n e s ”输 入目前因特网上最为强大的搜索引擎g o o g l e ，可以得到2 2 ，0 0 0 多条记录! 这 个数目是惊人的然而遗憾的是如果输入的是“支持向量机”，仅能得到1 1 0 多条记录这表明国内在这一方面的研究和推广应用工作才刚刚起步，还远 没有形成规模 自从支持向量机方法提出以来，大部分的研究和应用工作都是基于l 1 一软 间隔支持向量机方法的l 2 一软间辅支持向量机方法最早出现在文献 7 j 的末 尾此后，只出现了一些利用l 2 一软间隔方法几何特性的训练算法。如k e e r t h i 等人提出的最近点对算法【5 6 】本文的研究工作主要是基于l 2 一软间隔支持向 量机的 对于模式分类问题，支持向量机使用核函数方法巧妙地将观测样本从输 入空间映射到高维的特征空间，并通过在特征空间中使分类超平面具有最大 2 0 0 2 年串羞科举技术戈群博士攀位_ 奇支 3 闻瓣寒获褥学葛撬耩鼗努懿灌广瞧镪瓣。遗榉瓣处理避翟产垒的4 裁作用” 是我嬲不褥不整对一个褥簧兹黄量大静葵爨翡= 次蔑粼阍联。对予规模较大 的模式分类问题，设计算法鹱要赋冁和躲决如下鲍闻慰；1 ) 大规摸的矩阵避 算和存谙；2 ) 算法的收敛速度；3 ) 求解算法实现的笈杂程度。目前些快速 趣速代棼法8 经蒎雳予臻辩囊持秘警梳伉仡简题，如p l a t t 摄出的s m o 4 6 】、 j o a c h i m s 撼畿秘s v m z l g h 2 l 霉、m a a g a s a r i a n 撼凄鹩s o r1 4 8 】等葬法s m o 簿法 搜嚣癸线戆懿存搭空溺，毽劈法在每个建健步孛寝撬键疆令辩蒙，敬s m o 舞法 对学习问题的规模较势敏感f 7 2 l ；s v m t 坪觚舞法是一秘典毅的分髂遗代算法， 骄霈的存储空间与优化予问题的规模有燕尽管数缎实验袭明谯较大规模盼 学露阕题上s v m t i s r h 算法较s m o 算法消耗的c p u 遂算时间较少【4 7 】，但由予 采瓣了羧越算法j | 毫采辩凌识予麓惩，嚣藏在舆侮实蕊上较为笈杂；s o r 算法 酌赛壤较上逡薄释筹法寒说都要麓擎，稳数穰实验表骥该算法酌稽对予蓊两 者来淡要慢的多f 5 7 l ，鼗掺，k e e r t h i 等人f 嗣爨霞滤的张铃教授 5 8 l 扶凡筒 角度研究了支持向量机方法。并提出了基予几何穷法的训练算法，这些葵法 翡实现通常院较麓黼寻我易子实现和快速的求解算法仍然最支持向擞机研 究鳃一个藏要穷嚣泻 程缀多棱筑努溪麓嚣上，变撩鹈薰祝鹃连琶表蕊令入繇象深刻值怒，复 杂懿镶练遘程势谈方法在安嚣阏糕孛懿瘦爱建筑了“蘩袅”，髓囊持海蘩梳在 机器学习领域磐没有纛裁褥裂广泛戆皮爆。毽茈，人辅试鬻等求一种楚擎酌 解决方案，使其能同时遵循支持向慧帆的某些贩则( 妇最太化分类阅疆) ，以 获褥理沦上静僳诞这种傲法尊致后来发展出类寻求支持向慧机近似解的 葵法，郄大阍瑙分类方法l a r g em a r g i nc l a s s i f i c a t i o n ) 遽骜方法犬致可分为两 类：一类将感黧器耪孩涵数方法楗缝合，热 7 s ，7 7 ，8 鼙；另一癸粥慕于农筏增 量学习，热f 7 崴8 7 1 宅躲在训练避程申遭遨最太耀疆，以获褥学习壤器好静 搬广能力。此外，述有些其它的实现方法，如s c h a p i r e 等人基于b o o s t i n g 方 法酌大闯隔分爨方法f 8 0 j 其中，p r i e b 等人提出的k e m e l - a d a t r o n 算法f 7 5 l 是 这些方法串酶一个共登代袭 在簇式谖瓣镁城，统诗学舄理论酌结论都怒钟对予有藏营学习的情形 锺懿，程经有一些磷突将绞诗学霉褒论瓣v c 缝簿襁念戮入无麓督学习 9 萄， 僵这些鼹突对实黪应耀还没寿指导链的意义。壤戴，蹬理了一婆褥蠢鼗瞽学 习搬无艇督学习相缝合的方法f 3 7 ，3 8 ，3 9 】。核函数的薅线性映射是主要被借鉴 到无湓蟹擎习的支持向蕾机思想，如s c h s l k o p f 簿人提出的用于非线性生元分 析豹k p c a 9 6 ，以及一些蕊于核趱散的聚类方法f 9 7 ，9 8 1 掰前，将统计学习 2 0 0 2 年中国科学技术大学博士学位论文 4 理论的思想推广到无监督学习的研究正处于起步阶段 1 3 本文研究的内容与方法 统计学习理论及其方法仍有许多有待改进和进一步研究的问题本文主 要从事了以下几个方面的研究： l 2 一软间隔支持向量机及其性质的探讨l 1 一软间隔支持向量机方法的研 究已经比较深入本文在给出l 2 一软间隔支持向量机方法数学描述的基础 上，探讨了它与l 1 一软间隔支持向量机方法之间的关系，并从支持向量分 布、几何特性等角度较为系统地讨论了它的一些基本性质 基于l 2 - 软间隔支持向量机方法的快速训练算法研究目前，一些主要的 训练算法，如s m o 、s v m “g h 等，都是针对l 卜软间隔支持向量机方法的 在仔细研究l 2 一软间隔支持向量机方法后后，注意到它可以归结为一个具 有简单界约束且目标函数h e s s i a n 矩阵正定的二次规划问题这类问题存在 一些实现非常简单的算法，如本文中采用的积极集法 6 l 】，可以避免采用 复杂的优化问题求解算法遗憾的是，积极集法要求进行矩阵求逆运算， 对于较大规模的学习问题显然是不实用的因此，本文借鉴了s v m 恸等 算法的分解策略，结合积极集法，提出了一种新的快速训练算法此外， l 2 一软间隔支持向量机简单而直观的几何特性引起了我们极大的兴趣在 重新实现了k e e r t h i 等人的n p a 算法后，我们发现n p a 算法在优化对象选 择上存在着不足，没有充分利用优化对象提供的信息在此基础上，本文 研究了改进的最近点算法 基于l 2 一软间隔方法的k e r n e l a d a t r o n 算法研究f r i e b 等人提出的k e r n e l a d a t r o n 算法是以硬间隔支持向量机方法为基础的，它假设样本在特征空 间中是线性可分的，这种情况下统计力学对其收敛速度有理论保证实际 上，可以通过l 2 一软间隔方法将样本映射到一个高维空间，在该空间中 样本是线性可分的这样可以统一处理线性可分和线性不可分的情形因 此，本文将l 2 软间隔方法引入了k e r n e l - a d a t r o n 算法 基于加权p a r z e n 窗的聚类方法研究加权p a r z e n 窗被广泛地应用于非参 数的密度估计等问题，能较好地描述数据分布状态但是，概率密度估计 本身是一个不适定问题【3 】3 ，导致基于密度估计的聚类算法容易受到外来 噪声和样本数目的影响为避免这些负面效应。放弃对概率密度的估计， 放宽权值的限制，采用加权p a r z e n 窗获得对数据分布状态的良好描述，从 而求出不同模式类的分界面，将聚类过程转变为求解加权p a r z e n 窗权值的 2 0 0 2 年中国科学技米大学博士学位论文 5 线性规划问题 1 4 本文的组织结构 本文第二章简要介绍了统计学习理论及基于结构最小化原则下的支持向 量机方法；第三章研究了l 2 一软间隔支持向量机及其基本性质；第四章研究了 基于l 2 一软间隔支持向量机的快速训练算法；第五章探讨了基于l 软间隔 方法的k e r n e l - a d a t r o n 算法；第六章研究了基于加权p a r z e n 窗的轮廓聚类方 法第七章对全文的工作作出了总结 第二章统计学习理论及其方法 统计学习理论以统计学为基础研究了有限样本情况下学习机器推广能力 的问题，为解决基于数据的机器学习问题提供了有力的理论基础本章引入了 机器学习问题和统计学习理论中一些基本的术语和概念，并在统计学习理论 关于学习机器推广能力界的结论的基础上，简要介绍了结构风险最小化原则 下的支持向量机方法此外，对核函数及其一些性质进行了讨论 2 1 学习问题及其表示 广义上讲，机器学习问题( 简称学习问题) 研究的是如何从先验的不完整 信息中构建模型来尽可能精确地描述某种未知的依赖关系，使之能较好地对 未知数据进行预测或对其性质进行判断【3 ，9 ，1 0 ，1 1 】“从统计学角度来看， 学习问题可以形式化地表述为：已知变量y 与输入向量z r n 之间存在未知 依赖关系，即服从某种未知但确定的联合概率分布f ( 。，”) ，如何依据f 个独 立同分布( i i d ) 观测样本屹 ( l ，y 1 ) ，( 霉2 ，2 ) ，( 。f ，们) ) 从给定的函数集 ，( z ，a ) ，a a ) 中选取使预测期望风险泛函叼 r ( a ) = 珊，( ) ) d f ( 刚) ( 2 1 1 ) ( 2 1 2 ) 最小化的最优函数f ( x ，a + ) 来作为对未知依赖关系的近似? 其中， ，( 。，a ) ， q a ) 称为决策( 或指示) 函数集，a a 为广义参数；最优函数f ( x ，a + ) 称 为学习机器、学习函数或学习模型；l ( g ，( 2 ，a ) ) 称为损失函数，即当使 用，( 。，a ) 对y 进行预测时造成的损失 学习问题的核心是如何构造学习机器并使其具有良好的推广能力根据 上面对学习问题的数学描述，为构造学习机器必须确定以下四个方面的内容 9 】9 ： 1 1 直到目前为止机器学习问题并没有一个统一的定义这里对机器学习问题的描述是在统计学习理 论的框架下给出的 1 2 在本文中观测样本将视情形而被冠以样本、向量、输入向量、模式、模式向量等不同名称在使 用时不再具体说明 乜在一些英文文献中期整风险( e x p e c t e dr i s k ) 有时被直接称作( 实际) 风险( r i s k ) 6 2 0 0 2 年中国科学技术大学博圭学位论文 7 问题域由f 个观测样本( 2 1 1 ) 和特定的损失函数l ( y ，( 2 ，a ) ) 组成v a p n i k 研究了三类主要的学习问题：模式识别、回归函数估计和密度估计【3 1 3 对 于模式识别问题，y l 给出了样本z f 的类别信息考虑下面的损失函数 工( 可，( 。，a ) ) = o ， i f 掣= ，( 茁，a ) 【1 ，o t h e r w i s e 对于这个损失函数，期望风险泛函( 2 1 2 ) 给出了错误分类的概率本文将 主要讨论模式识别问题 归纳原则在给定有限样本( 训练集) 的前提下，用于构造特征空间中决策规则的 原则依据，如由统计学发展而来的经验风险最小化原则( e m p i r i c a l r i s k m i n i m i z a t i o np r i n c i p l e ) 统计学习理论则依据结构风险最小化原则( s t r u c t u r a l r i s km i n i m i z a t i o np r i n c i p l e ) 提出了支持向量机学习方法 决策函数集为构造学习机器，必须事先选择好一个指示函数集 ，( $ ，a ) ， a a ) 在支持向量机方法中。采用了如下线性表示的决策函数集 l、 f ( x ) = s g n l ：a i k ( x ，) + bl 百 其中， h = 1 ，2 ，f ) 为空间孵中的已知向量b 为偏置项，是一个标 量a 为参数空间r l 中的待求矢量函数k ( x ，z ) 称为核函数，要求符合 m e r c e r 条件【3 】3 核函数可以有多种选择，如线性函数、多项式函数、s p i i n e 函数以及径向基函数等【1 6 】当采用非线性函数时，核函数实现了从样本 输入空间到特征空间的非线性映射 算法实现上述内容的具体过程 上述四个方面的内容确定了构造学习机器的全部信息当给定问题域和 决策函数集后，不同的学习过程在构造学习机器时采用不同的归纳原则 2 2 统计学习理论 统计学习理论( 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 ) 是为解决有限样本情 形下的机器学习问题而提出的它主要研究了以下四个方面的内容【3 】：1 ) 学 习过程的一致性；2 ) 学习过程收敛速度的非渐进理论；3 ) 控制学习过程的推 广能力的理论；4 ) 构造学习算法其中，有关学习机器推广能力界的结论为 解决学习问题奠定了坚实理论基础并具有实际的指导意义 2 0 0 2 年中国科学技术大学博士学位论文 8 2 2 1 经验风险最小化原则 为使期望风险最小化，需要最小化泛函( 2 1 2 ) 然而，实际上除了给定的 f 个样本( 2 1 1 ) ，对联合概率分布函数f ( ，g ) 一无所知因此，只能根据已知 的f 个样本的分布状态对函数f ( x ，9 ) 进行估计 经典统计学理论指出，可以使用下面的经验风险泛函( e m p i r i c a l r i s kf u n c t i o n a l ) 作为对期望风险的一个好的估计： 1 三 r e m p ( c r ) = l ( 聃，( n ) ) ( 2 2 1 ) 用使经验风险( 2 2 1 ) 最小化的函数l ( g ，( 2 ，a ) ) 来逼近使风险( 2 1 2 ) 最 小化的函数l ( y ，( x ，a + ) ) 这一原则称为经验风险最小化( e m p i r i c a l r i s km i n i m i z a t i o n j 归纳原则( 简称e r m 原则) 然而，经典统计学以大样本为前提使用e r m 原则替代期望风险最小化 并没有充分的理论依据，只是一种想当然的做法实际上，当1 较小时函数 l ( y ，( z ，) ) 通常不能很好地逼近函数l ( y ，f ( x ，n ) ) ，即经验风险最小并不意 味着期望风险最小 2 2 2 学习机器的推广能力和v c 维 学习问题的关键是如何从可能的决策函数集中选择一个具有“最好”推广 能力的函数，使预测风险泛函( 2 1 2 ) 最小化统计学习理论通过v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o 州来描述函数集的学习能力两类模式识别问题中v c 维的直观定义是 3 ，1 0 ：对于一个指示函数集，如果k 个样本能够被函数集内 的函数按照所有可能的2 种形式分开，则称函数集能够把这k 个样本打散 函数集的v c 维就是它能打散的最大样本数目h 若函数集可以打散任意数目 的样本，则称该函数集的v c 维是无穷大v c 维反映了函数集内在的性质， 定量地刻划了学习机器的复杂程度目前，尚没有通用的关于任意函数集v c 维计算的理论，只知道一些特殊函数的v c 维如舻中，超平面函数集的v c 维为n + l ；p 阶多项式核函数的v ( 3 维为r 弋_ 1 ) + 1 ；径向基核函数的v c 维 为无穷大【3 ，4 】 v a p n i k 等人在v c 维概念的基础上研究了学习机器推广能力的界，证明出 下面关于预测风险的界以1 一q 的概率成立 3 】3 脚) r b “卅坐蠼匕幽 ( 2 2 2 ) 2 0 0 2 年中国科学技术大学博士学位论文 9 上式表明，学习机器的推广能力受到两方面的约束：经验风险和置信范 ( c o n f i d e n c ei n t e r v a l ，式( 2 2 2 ) 中右边第二项) 对于确定的问题域，置信范 围仅与v c 维有关，它控制了学习机器的复杂程度单纯地应用经验风险最小 化原则，很可能导致学习机器过于复杂而产生过学习( o v e r f i t t i n g ) 现象 2 2 3 结构风险最小化原则 统计学习理论关于学习机器推广能力的界的理论指出必须同时最小化经 验风险和置信范围构造如下的嵌套函数子集结构 s 1c 岛c c 岛 ( 2 2 3 ) 使各子集的v c 维满足 h i h 2 h n( 2 2 4 ) 以及同伦结构q 的要求如图2 1 所示： 闲绪“ ； i；e m p i d c a “ 图2 1 ：结构风险最小化示意图 q 也称为容许结构即结构中的任何元索或者包含一个完全有界函数的集合 0 茎q ( z ，n ) b i ，n a 或者包含对一定的p ，7 k ) 对满足下列不等式的函数集合 蕊娣j 燃t z ) 鲰蹦a e “ v p j u o 2 0 0 2 年中墨科学技术大学博士学位论文 1 0 如果在每个函数子集中使经验风险最小，然后选择合适的函数使其所属函 数子集的置信范围与该函数的经验风险同时最小化，即使期望风险的界( 2 2 2 ) 最小化这一过程被称为结构最小化归纳原则( 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 原则) ，它定义了对给定数据逼近的精度和逼近函数的复杂性之间 的一种折衷 正如在下文中将要看到的，结构风险最小化原则与正则网络1 5 1 的思想 非常类似在一定条件下，它们是等价的【1 5 ，1 6 】它们都没有直接最小化损 失函数，而是同时最小化损失函数和一个正则化泛函这使得遵循结构风险 最小化原则的支持向量机方法能够较好地解决密度估计等不适定问题“ 2 3 支持向量机 支持向量机是在统计学习理论框架和结构风险最小化原则下提出的一种 通用的机器学习方法对于模式识别问题，最大化分类间隔和使用核函数将观 测样本从输入空间映射到高维的特征空间是该方法的两个最为重要的思想， 这些思想对今天的机器学习领域产生了巨大的影响 2 3 1 支持向量机的提出 统计学习理论的研究结果表明，期望风险的界是由与样本有关的经验风 险和代表机器学习能力的置信范围两部分组成的【3 v a p n i k 等人提出结构风 险最小化归纳原则以最小化期望风险的界，获得学习机器良好的推广能力 支持向