（应用数学专业论文）基于分组聚类的svm训练算法.pdf

摘要 摘要 多数基于数据的机器学习问题的传统研究方法只有在样本数无穷大时才能在 理论上对其一致性、无偏性等有所保证。但是，在实际应用中，样本的数量往往 是有限的，尤其当问题处在高维空间时尤其如此。因此，理论上优秀的传统统计 学习方法在实际应用中的表现却可能不尽人意，这也正是类似于神经网络等机器 学习方法遇到诸如过学习与欠学习、局部极小陷阱等问题的根本原因。 v a p n i k 等人提出的统计学习理论与传统统计学相比，着重研究在小样本情况 下的统计规律及学习方法的性质，是一种小样本统计理论。1 9 9 2 年至1 9 9 5 年期 间，v a p n i k 等人在这个理论框架下发展出了一种新的模式识别方法和通用的学习 算法一支撑矢量机( s u p p o r t v e c t o rm a c h i n e s ，简称s v m ) 。s v m 在解决小样本、 非线性及高维模式识别问题中表现出许多特有的优势，并能够推广到函数拟合等 其它机器学习问题中。因此s v m 被众多学者认为是继模式识别和神经网络研究 之后机器学习领域的新的研究热点，并将推动机器学习理论和技术有重大的发展。 由于s v m 对模式识别问题的求解过程相当于解一个线性约束的二次规划问 题，求解的变量个数与训练样本数相等，且需要计算和存储的核函数矩阵的大小 与训练样本数的平方相关，因此，随着样本数目的增多，经典的求解二次规划问 题的算法根本不适用。所以，对s v m 训练算法的研究是国际上s v m 研究中的一 个热点。 以前，人们的研究注意力主要放在算法的训练过程中，尽管已经提出了许多 优秀的算法，我们认为仍然有很大的改进余地。在算法开始时，如果我们能够在 保持原数据特征的同时有效地减少训练样本个数，那么算法的训练速度将会加快。 考虑到对噪声样本敏感是s v m 的固有特性，为了加快算法的训练速度，同 时不降低学习机的推广能力，本文提出了一种基于分组聚类的训练算法。其主要 想法是：首先把原训练样本随机分成多个互不相交的子集；然后在每个子集中进 行k 一均值聚类，得到多个类中心：最后把得到的类中心作为新的训练样本进行 s v m i j t i 练。由于这些类中心很好地表示了原训练样本的特征，可以说该方法不会 降低学习机的推广能力。从理论上，我们分析了算法的复杂度，保证了所提山的 算法比不聚类的算法快。在多个公开的标准测试数据集上的计算结果表明：所提 算法在保持推广能力的同时比不聚类的s v m 训练算法快至少一倍以上。 关键词统计学习理论；支撑矢量机：s m o 算法；分组聚类；k 一均值聚类 牮薅理工夫学理学骚士学懂论文 a b s t r a c t c u r r e n t l y m o s tm e t h o d sb a s e do nt r a d i t i o n a ls t a t i s t i c a l t h e o r y i nm a c h i n e l e a r n i n gs o m e t i m e sd on o th a v eg o o db e h a v i o ri np r a c t i c a la p p l i c a t i o n s ，b e c a u s et h e i r t h e o r ya b o u tc o n s i s t e n c ya n da p p r o x i m a t i o ni s b a s e do ni n f i n i t e s a m p l e s ，w h i c h i s r a r e l ys a t i s f i e di np r a c t i c e ，e s p e c i a l l yw h e nt h es a m p l e sh a v em a n ya t t r i b u t e s 。t h i si s t h eb a s i cr e a s o nw h yag o o dl e a r n i n gm e t h o ds u c ha sn e u r a ln e t w o r ke n c o u n t e r s p r o b l e m sl i k el o c a lm i n i m u m o ro v e r f i t t i n g c o m p a r e dw i t h t h et r a d i t i o n a l l e a r n i n gm e t h o 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 l t ) p r o p o s e db yv a p n i kp l a c e se m p h a s i so ns m a l ls a m p l es t a t i s t i c s ，a n df r o mt h i s f r a m e w o r kan e w t y p e o fu n i v e r s a l l e a r n i n ga l g o r i t h m c a l l e d s u p p o r t v e c t o r m a c h i n e s ( s v m ) i sc o n s t r u c t e d s v mi sd e r i v e df r o mt h ei d e ao fg e n e r a l i z e do p t i m a l h y p e r p l a n ew i t hm a x i m u mm a r g i nb e t w e e nt h et w oc l a s s e sa n dt h i si d e ai m p l e m e n t s t 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 ( s r m ) p r i n c i p l ei ns l t m a x i m i z i n gt h em a r g i n p l a y sa ni m p o r t a n tr o l ei nt h ec a p a c i t yc o n t r o ls ot h a tt h es v mw i l ln o to n l yh a v e s m a l le m p i r i c a lr i s k s ，b u ta l s oh a v eg o o dg e n e r a l i z a t i o np e r f o r m a n c e s l ta n ds v m h a v ea t t r a c t e dm o r ea n dm o r er e s e a r c h e r si nr e c e n ty e a r s ，a n dt h e yh a v eb e e n a p p l i e d s u c c e s s f u l l yt o aw i d ev a r i e t yo fd o m a i n ss u c ha st h ep a t t e r nr e c o g n i t i o n ，f u n c t i o n a p p r o x i m a t i o n ，r e g r e s s i o ne s t i m a t i o n ，c o m p u t e rv i s i o n ，d a t am i n i n ga n dm a n yo t h e r s 。 s o l v i n gt h ep r i m eo p t i m i z a t i o np r o b l e mo ft h eo p t i m a lh y p e r p l a n ev i ai t sd u a l f o r mi sa ni m p o r t a n ti d e ai ns v m ，w h i c hi s a c t u a l l yaq u a d r a t i cp r o g r a m m i n g ( q p ) a l t h o u g h i ta v o i d st h ew e l l k n o w n ”d i s a s t e ro f d i m e n s i o n a l i t y “i nl a r g e s c a l e p r o b l e m s ，i tm a ya c t u a l l yr a i s ean e wp r o b l e m ：i np r a c t i c ei t i si n t r a c t a b l et ot h e c o n v e n t i o n a lo p t i m i z a t i o n t e c h n i q u e sw h e nt h en u m b e ro fs a m p l e se x c e e d saf e w t h o u s a n d s t h e r e f o r et h e s t u d yo fs v mt r a i n i n ga l g o r i t h m s i sah o tt o p i ci nt h e r e s e a r c hw o r l d m a n ye x c e l l e n ta p p r o a c h e sh a v eb e e np r o p o s e di nt h ep a s tf e wy e a r s ，a n dt h e d e c o m p o s i t i o na l g o r i t h m sp l a ya ni m p o r t a n tr o l ei ni m p r o v i n gt h es p e e do ft h es v m ， w et h i n kt h a ti fo n ec a nf u r t h e rr e d u c et h en u m b e ro ft h e s u p p o r t v e c t o r sw h i l e k e e p i n g t h ec h a r a c t e ro ft h e o r i g i n a l d a t a d u r i n gt r a i n i n g ，t h es p e e d c a nb e a c c e l e r a t e df u r t h e r i ti sw e l lk n o w nt h a ts v m i ss e n s i t i v et on o i s e so ro u t l i n e r s 。i no r d e rt os p e e d u pt h et r a i n i n gt i m ew h i l en o tt od e g r a d et h eg e n e r a l i z a t i o np e r f o r m a n c eo fs v m 。w e p r o p o s ean e ws v mt r a i n i n ga l g o r i t h mo nt h eb a s i so fs e ts e g m e n t a t i o na n dk ，m e a n s l l a b s t r a c t c l u s t e r i n g i nt h e o r y w eg i v et h e c o m p l e x i t ya n a l y s i s o ft h e p r o p o s e da l g o r i t h m ， w h i c hs h o w so u ra l g o r i t h mi sf a s t e rt h a ns t a n d a r ds v mt r a i n i n ga l g o r i t h m sw i t h o u t c l u s t e r i n g s o m ee x p e r i m e n t so nd i f f e r e n td a t as e t sa r ei m p l e m e n t e dt oi l l u s t r a t et h a t t h e a l g o r i t h mi s e f f e c t i v en o t o n l y f o rt h e l a r g e l i n e a rp r o b l e m sb u ta l s of o rt h e n o n l i n e a ro n e s k e y w o r d s ： s t a t i s t i c a l l e a r n i n gt h e o r y ；s u p p o r t v e c t o r m a c h i n e s ；s m o ；s e t s e g m e n t a t i o n ；k m e a n sc l u s t e r i n g i i i 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 宫 作者签名：棘六稚i 乇 曰期：2 0 0 3 年5 月2 0 臼 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权华南理工大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密毗 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 夫赢日期：2 0 0 3 年5 月2 。日 埠吼。多年g 月驴日僻掰 第一章绪论 1 1 研究背景 第一章绪论 基于数据的机器学习是现代智能技术中的重要方面。主要研究从观测数据( 样 本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。模式 识别、函数拟合以及概率密度估计等问题都属于该类问题。现有方法的重要理论 基础之一是传统的统计学，其研究的基础是样本数目趋于无穷大时的渐近理论。 统计学中关于估计的一致性、无偏性、方差的界以及关于分类的错误率等的诸多 结论，都依赖于这种渐近特性，所提出的各种方法只有在样本数无穷大时其性能 才有理沦上的保汪。但是这个前提条件在实际应用中却往往得不到满足，样本数 往往是有限的，尤其当问题处在高维空间时尤其如此，因此理论上很优秀的学习 方法在实际中表现却可能不尽人意。这实际上是包括神经网络等在内的现有机器 学习理论和方法中的一个根本问题。 统计学习理论问题( 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 ) 是a t & t 实验 室的v l a d i m i r v a p n i k 等人提出的一种小样本统计理论，与传统统计学相比，着重 研究在小样本的情况下的统计规律及学习方法性质。v a p n i k 等人早在2 0 世纪6 0 年代就开始研究有限样本下的机器学习问题【2 l 。由于当时这些研究尚不十分完善， 且内容比较艰涩，而在解决模式识别问题时人们往往趋于保守，从而直至9 0 年代 以前并没有提出将理论付诸实现的较好的方法。加之当时正处于其它学习方法飞 速发展的时期，因此这些研究一直没有得到充分的重视。直到九十年代中期，有 限样本情况下的机器学习理论逐渐成熟起来，形成了一个较完善的统计学习理论 体系。而同时，神经网络等较新兴的机器学习方法的研究则遇到些重要的困难， 譬如如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题等等。在 这种情况下，试图从更本质上研究机器学习的统计学习理论逐步得到重视。 s l t 为机器学习问题建立了一个良好的理论框架，也发展了一种新的通用的 学习算法支撑矢量机( s u p p o r tv e c t o rm a c h i n e s ，简称s v m ) 。1 9 9 2 年一1 9 9 5 年， v a p n i k 等人在统计学习理论的基础上发展出了一种新的模式识别方法s v m ，在 解决小样本、非线性及高维模式识别问题中表现山许多特有的优势，并能够推广 到函数拟合等其它机器学习问题中。虽然统计学习理论和支撑矢量机方法中尚有 华南理工人学理学硕上学位论文 很多问题需要进一步的研究，但很多学者认为，他们正在成为继模式识别和神经 网络研究之后机器学习领域的新的研究热点并将推动机器学习理论和技术有重大 的发展。 1 2 研究现状 统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。它 从理论上较系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险 与期望风险的关系，以及利用这些理论找到新的学习原则和方法等问题。其主要 内容包括四个方面1 3 l ： 1 经验风险最小化原则下统计学习一致性的条件； 2 在这些条件下关于统计学习方法推广性的界的结论； 3 在这些界的基础上建立的小样本归纳推理原则； 4 实现这些新的原则的实际方法( 算法) 。 前三部分的核心内容是统计学习理论的理论部分，而要使理论在实际中发挥 作用，还要求它能够实现，也就是统计学习理论的第四部分的内容，即实现其理 论思想的方法，也就是支撑矢量机方法。这是统计学习理论中最年轻的部分，其 主要内容是在1 9 9 2 年一1 9 9 5 年间才基本完成，目前仍处于不断发展阶段。可以 说，统计学习理论之所以从2 0 世纪9 0 年代以来受到越来越多的重视，很大程度 上就是因为它发展出了支撑矢量机这一通用学习方法。 但是统计学习理论和支撑矢量机方法尚处在发展阶段，很多方面尚不完善， 比如：许多理论目前还只有理论上的意义，尚不能在实际算法中实现；有关s v m 算法某些理论解释也并非完美，譬如文献 4 】中就曾提到结构风险最小原理并不能 严格证明s v m 为什么会有好的推广能力；此外，统计学习理论提出的结构风险 最小化准则并没有给出选择函数子集结构的标准，核一i i , 概念v c 维也没有切实可 行的计算理论和方法，以及在s v m 方法中如何根据具体问题选择适当的内积函 数也没有理论依据。这些都是理论方面需要进一步研究的问题。另一方面研究的 重点为支撑矢量机为代表的新的学习算法，研究如何让这些理论和方法在实际应 用中发挥作用。 支撑矢量机在模式识别( 包括手写体字符识别【5 1 、人脸检测刚、三维物体识 别【7 】等) 以及函数拟合( 主要实验尚属于原理性研究阶段，包括函数逼近 8 1 、时 第一章绪论 间序列预测9 i 等) 、数据挖掘和知识发现1 0 1 等方面均有很好的应用。 在模式识别方面最突出的应用研究是贝尔实验室对美国邮政手写字库进行的 实验l ”。这是一个可识别性较差的数据库，人工识别的错误率是2 5 ，用决策树 方法识别错误率是1 6 2 ，两层神经网络中错误率是5 9 ，专门针对该问题设计 的五层神经网络错误率是5 i ( 其中利用了大量的先验知识) ，而用s v m 方法 ( 采用三种核函数) 得到的错误率平均为4 1 ，且直接采用了1 6 1 6 的字符点 阵作为s v m 的输入，并没有进行专门的特征提取。实验方面说明了s v m 方法 较传统方法有明显的优势，另一方面也得到了不同核函数的s v m 方法可以得到 性能相似的结果( 而不像神经网络那样依赖于模型的选择) 。 而用支撑矢量机的方法进行函数拟合已经在系列建模问题得到了应用。例 如，文献 9 】中在数据集s a n t af et i m es e r i e sc o m p e t i t i o n 上应用支撑欠量同归， 比原先已知的最好结果提高了2 9 。 由于支撑矢量机坚实的理论基础和它在很多领域表现出的良好的推广性能， 目前，国际上止在广泛开展对支撑矢量机方法的研究。许多关于s v m 方法的研 究，包括算法本身的改进和算法的实际应用，都陆续提了出来，以下是其中主要 的研究热点。 1 改进训练算法 由于s v m 对偶问题的求解过程相当于解一个线性约束的二次规划问题( q p ) ， 需要计算和存储核函数矩阵，其大小与训练样本数的平方相关，因此，随着样本 数目的增多，所需要的内存也就增大，例如，如果我们有2 0 0 0 0 个样本，核函数 矩阵的每个元素用4 个字节来存储，则存放核函数矩阵就需要1 6 g 空间；其次， s v m 在二次型寻优过程中要进行大量的矩阵运算，多数情况下。寻优算法是占用 锋法时间的主要部分。目前s v m 的训练算法中的一大类是分解算法。分解算法 的思路是把要求解的问题分成许多子问题，然后通过反复求解子问题来求得最终 的解，实现的方法有块处理算法i i 、固定工作集算法幢1 以及序列最小优化( s m o ) 算法( ”1 等。其他的算法还有n p a 最近点算法“j 、卫向量的几何训练法5 1 等。 2 提高测试速度 s v m 的分类函数的计算量和支撑矢量的数目成正比。对于大训练集合，其支 撑欠量的数目会达到几千个，这就使s v m 对实验样本的测试判别速度变慢，因 此，提高s v m 的测试速度是另一个研究热点。对此，o s u n a 等人【1 6 1 提出3 种方 案，其中第1 个方案已经被b u r g e s 论证并实现m 1 ，其基本思想是：在s v m 的高 华南理j 二人学理学硕士学位论文 维特征空间中，运用比原来少得多的精简集合( r e d u c e ds e t ，r s ) 来拟合原来所有 支撑欠量s v 所构成的分界超平面，可以在损失极少信息的基础上，大大提高测 试速度。 3 核函数的构造、改进以及相应参数的调整 s v m 的核函数有多项式函数、径向基函数等。尽管一些实验结果表明核函数 的具体形式对分类效果的影响不大，但是核函数的形式及其参数的确决定了分类 器的类型和复杂程度，它显然应该作为控制分类器性能的手段。最常用的模型参 数选择方法是最小化“留一法”( l o o ) 的错误率。由于用l o o 来估计错误率 从而凋整参数需要大量的样本进行训练，因此有人提出用估计错误率上限的方法 来调整s v m 的参数。文献 1 8 】中提出了几种估计错误率上限的方法，其中有逐个 确认估计、留一法上限估计、用支撑矢量数与i ) l i 练样本数的比值估计上限、 j a a k k o l a h a u s s l e r 上限、o p p e r - w i n t h e r 上限、r a d i u s m a r g i n 上限、s p a n 上限等。 同时，还实现了根据错误率上限的估计来调整s v m 参数的算法，其具体思路是： 初始化s v m 的核函数参数，然后利用求得的结果估计错误率上限，再利用对错 误率上限的梯度下降法调整核函数参数，反复执行上述步骤，直到得到最小的错 误率上限。c h a p e l l e 等人1 9 1 使用基于矩阵的二次规划方法实现了利用l o o 上限 来调整s v m 参数的方法。应当指出的是，即使对于只有几千个样本的中型问题， 也很难在内存中容下整个核函数矩阵，并进行相应的矩阵操作，这种方法有时也 会带来问题，因此，寻找合适的迭代策略仍是进一步的研究问题。 4 利用s v m 解决多分类的问题 由于支撑矢量机是针对二分类模式识别问题提出的，因此，存在一个如何将 其推广到多分类问题上，特别是对极大类别分类的问题上。目前有以下几种方案： ( 1 ) 一对多( o n ec l a s sv e r s u sa 1 1o t h e r s ，o v o ) 其基本想法是把某一种类别的样本当作一个类别，剩余其他类别的样本当作 另一个类别，这样就变成了个二分类问题。这种分类方案的缺点是i ) i i 练样本数 目大，训练困难。 ( 2 ) 一对一( o n ec l a s sv e r s u sa n o t h e rc l a s s ，o v a ) 【 0 i 其做法是在多类别中，任意抽取两类进行两两配对，转化成两类问题进行训 练学习。识别时，对所构成的多个s v m 进行综合判断，一股可采用投票方式来 完成多类识别。这种分类方案存在一个明显的缺点，就是子分类器过多，测试时 需要对每两类都进行比较，导致测试速度慢。 4 第一章绪论 ( 3 ) s v m 决策树( d e c i s i o nt r e em e t h o d ) 1 2 j l 它通常和二叉决策树结合起来，构成多类别的识别器这种方法的缺点是如 果在某个节点上发生了分类错误，将会把错误延续下去，该节点后续下一级节点 上的分类就失去了意义。 另外，s v m 的研究点还有如何把s v m 中的核函数内积的思想应用到其他方 面。s c h 6 1 k o p f 等学者首先把核函数的概念引入到p c a ( p r i n c i p a lc o m p o n e n t a n a l y s i s ，主成份分析) 中2 封，用核函数实现非线性主成份分析，它是传统主成份 分析方法的推广。 1 3 本文的研究与组织 由于s v m 对模式识别问题的求解过程相当于解一个线性约束的二次规划问 题，求解的变量个数与训练样本数相等，且需要计算和存储的核函数矩阵的大小 与训练样本数的平方相关，因此，随着样本数目的增多，经典的求解二次规划问 题的算法根本不适用。所以，对s v m 训练算法的研究是国际上s v m 研究中的 个热点。 以前，人们的研究注意力主要放在算法的训练过程中，尽管已经提出了许多 优秀的算法，我们认为仍然有很大的改进余地。在算法开始时，如果我们能够有 效地减少训练样本，同时又不改变原数据的特征，那么，算法的训练速度肯定会 加快。 考虑到对噪声样本敏感是s v m 的固有特性，文献 2 3 1 中提出了c e n t e r s v m 算法。首先计算每类训练样本的中一d ( c e n t e r ) ，调整原s v m 模型，使二二次规划变 成在一定约束条件下求使两个类中心的距离最大的最优解。优点是减少了训练数 据中野值对分类结果的影响，缺点是没有减少原问题的求解复杂度还增加了一个 l a g r a n g e 乘子。 受这一算法的启发，为了加快算法的训练速度，同时不降低学习机的推广能 力，我们提出了一种基于分组聚类的训练算法。其主要想法是：首先把原训练样 本随机分成多个互不相交的子集：然后在每个子集中采用k 一均值算法进行聚类分 析，得到多个类中心；最后把得到的类中心作为新的训练样本进行训练。由于这 些类中心很好地表示了原训练样本的特征，所以该方法不会降低学习机的推广能 力。从理论上，我们分析了算法的复杂度，保证了所提出的算法比不聚类的s v m 算法快。在多个公开的标准测试数据集上的计算结果表明：所提出的算法在保持 华南理工夫学理学硕士学位论文 推广能力的同时比不聚类的s v m 训练算法快至少一倍以上。 本文的组织如下。第一二章首先介绍统计学习理论的核心理论：基于学习过程 收敛速度的非渐近理论条件下的推广性的界，以及与此相关的核心概念v c 维； 然后详述了支撑矢最机从线性完全可分到非线性不可分的三种数学模型的建立过 程。第三章在综述s v m 的现有各种i ) lj 练算法的基础上，着重介绍分解算法中的 s m o 算法，分析原始s m o 的求解原理和步骤以及算法的改进，并给山其改进算 法的收敛性证明。第四章详细介绍我们提出的基于分组聚类的训练算法，我们采 用k 一均值聚类方法，在多个公开测试数据集上与标准s v m 训练的计算结果进行 比较：结果表明我们提出的新训练算法在保持精确度的同时使速度提高了一倍以 。 第二章统计学习理论及支撑矢昔机 第二章统计学习理论及支撑矢量机 2 1 符号和定义 ( 1 ) 本文讨论的是模式识别中有监督学习的两类分类问题： 设有，个训练样本 ( x 。，y 。) ，( z ：，y ：) ，( _ ，y m ，其中鼍尺4 别标号，d 是样本的维数。 ( 2 ) 沃夫对偶问题( w o l f ed u a l ) 1 2 4 1 ： 假设x e r ”，f ，g c 1 ，若原优化问题为： m a x f ( x ) s t g ( x 1 0 则其对偶问题为： y f + l ，一1 ) 是类 r m n ，( y ) 一g ( y ) s t f ( y ) 一9 7 ( y ) = o “0 ( 3 ) k k t ( k a r u s h k u h n t u c k e r ) 条件( 一般称为k u h n t u c k e rc o n d i t i o n s 恩一塔克条件) 2 5 1 ： 设x + 是非线性规划 f 2 一l a ) ( 2 1 b ) ( 2 2 a ) r 2 2 b ) ( 2 2 c ) 也即库 minf舢(x),x，r，stg0 ：1 ，z ( 2 _ 3 ) 【( 工) ，= ，z 。 的局部极小点，( 上) ，g ，( x ) ( j = l ，f ) 在x + 处有一阶连续偏导数，且与x + 处所有起 作用的约束梯度线性无关，则存在数“，“，使得 j 掣卜“，掣涵4 ， 1 “，g f ( 妒) = o ，且h 0 ，j = t ，l ( 4 ) 核和m e r c e r 条件： 根据h i l b e r t - s c h m i d t 定理，只要k ( x ，y ) 是一个对称正定函数，且满足以下的 m e r c e r 条件，则k ( x ，y ) 代表特征空间中两个向量，y 的内积。其中，y 7 分别是输 华南理工大学理学硕士学位论文 入空间中的上，y 在高维特征空间中的某个非线性映射的像，函数k ( x ，y ) 称为核。 m e r c e r 条件：对于任意非零且满足f g2 ( t ) d t 0 成立。 2 2 机器学习问题的表示 机器学习的目的是根据给定的训练样本对某系统输入输出之间依赖关系进行 估计，使它能够对未知输出做出尽可能准确的预测。机器学习一般地可以表示为 ”1 ：假定变量y 与x 存在一定的未知依赖关系，即遵循某一未知的联合概率f ( x ，y ) ， ( x 和y 之间的确定性关系可以看作是其特例) 。机器学习问题就是根据，个独立 同分布观测样本 ( x 。，y 1 ) ，( x 2 ，y 2 ) ，( _ ，y 1 ) ，其中x f r 4 ，y f + l ，一l l ，d 是样本 的维数，在一组函数 f ( x ，d ) 中求个最优的函数f ( x ，瓯) 对依赖关系进行估计， 使期望风险最小，即 m i n 足( 口) = j l ( y ，( 五口) ) 口妒( 五_ ) ，) ( 2 5 ) 其中，预测函数集( f ( x ，口) 可以表示为任何函数集合，口为函数的，义参数， l ( y ，f ( x ，口) ) 为用f ( x ，口) 对y 进行预测所造成的损失，不同类型的学习问题有不同 形式的损失函数。预测函数也叫学习函数、学习模型或学习机器。 有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计。在我 们讨论的模式识别问题中，预测函数称为指示函数，损失函数可以定义为 坳讹= 怯器署巍蕃 陋s ， 统计模式识别的传统方法都是在样本数目足够多的前提下进行研究的，所提 出的各种方法只有在样本数趋于无穷大时其性能才有理论上的保证。而在实际的 应用中，样本数目通常是有限的，于是，人们采用了所谓的经验风险最小化 ( 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 ) 准则，即用样本定义经验风险 第二章统计学习理论及支撑矢量机 1 l r 。( 口) = l ( y ，( x i a ) ) ( 2 7 ) i = l 机器学习就是要设计学习算法，使如。 ) 最小化，作为对式( 2 - 5 ) 的估计。 多年来，人们将大部分注意力集中到如何更好地最小化经验风险上，但是，从期 望风险最小化到经验风险最小化并没有可靠的理论依据”1 。首先k 。 ) 和r ( a ) 都 是口的函数，概率论中的大数定理只说明了在一定条件下，当样本数趋于无穷大 时，r 。 ) 将在概率意义上趋近于r ) ，并没有保证使r 。 ) 最小的口+ 与使r ) 最小的口+ 是同一个点，更不能保证如。噼+ ) 能够趋近于r ( a + ) ；其次，即使有办法 使这些条件在样本数无穷大时得到保证，也无法认定在这些前提下得到的经验风 险最小化方法在样本数有限时仍能得到好的结果。e r m 准则不成功的一个例子就 是神经网络的过学习问题。设想一个简单的例子，假设有一组实数样本数据f x ，y ， y 取值在 0 ，1 之间，那么无论样本是什么模型产生的，只要用函数f ( x ，口) = s i n ( o x ) 去拟合它们( a 是待定参数) ，总能够找到一个口使训练误差为零，但显然得到 的最优函数并不能上e 确代表真实的模型。究其原因是试图用一个十分复杂的模型 去拟合有限的样本，导致丧失了推广能力。在神经网络中，若对有限的样本来说 网络学习能力过强，足以记住每个样本，此时经验风险很快就可以收敛到很小甚 至零，但却根本无法保证它对未来样本能给出好的预测。学习机器的复杂性与推 广性之间的这种矛盾同样可以在其他学习方法中看到。由此可看出，有限样本情 况下，经验风险最小并不一定意味着期望风险最小，而且学习机器的复杂性不但 应与所研究的系统有关，而且要与有限数目的样本相适应。 v a p n i k 等人甲在2 0 世纪6 0 年代就开始研究有限样本情况下的机器学习问 题，但直到9 0 年代以前，也没有提出能够将其理论付诸实现的较好办法，直到 9 0 年代中期，有限样本情况下的机器学习理论研究才逐渐成熟起来，形成了一个 较完善的理论体系一一统计学习理论。它能将很多现有方法纳入其中，可望解决 许多原来难以解决的问题，如学习能力和推广。能力的统一。1 9 9 2 年1 9 9 5 年， v a p n i k 等人又在统计学习理论的基础上，发展出了一种新的通用的学习方法一一 支撑矢量机，其在解决小样本、非线性及高维模式识别问题中表现出许多特有的 优势，并且能够推j “到函数逼近和概率密度估计等其它机器学习问题中。 9 华南理工大学理学硕士学位论文 2 3 统计学习理论的核心内容 统计学习理论研究的是下面四个问题【2 l ： i 一个基于e r m 原则的学习过程一致充分必要条件是什么? 2 这个学习过程收敛的速度有多快? 3 如何控制这个学习过程的收敛速度或者推广能力? 4 怎样构造能够控制推广能力的算法? 这四个问题分别对应学习过程一致性理论、学习过程收敛速度的非渐近理论、 控制学习过程推广能力的理论以及构造学习算法的理论。其中最有指导性的理论 结果是基于学习过程收敛速度的非渐近理论的条件下的推广性的界，与此相关的 一个核心概念是v c 维。 2 3 1 v c 维和推广性的界 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了系列有 关函数集学习性能的指标，其中最重要的是v a p n i k 和c h e r v o n e n k i s 提出的v c 维 ( v c 就是取v a p n i k 和c h e r v o n e n k i s 名字的首字母而成) 。v c 维是统计学习理 论中的一个核心概念，它是目前为止对函数集学习性能最好的描述指标。一个函 数集的v c 维可以理解为由其分类函数能正确给出以所有可能二值标识的最大训 练样本数，也就是说，如果存在h 个样本的样本集能够被函数集打散，而不存在 有h + 1 个样本的样本集能够被函数集打散，则函数集的v c 维就是h 。如果对于 任意的样本数，总能找到一个样本集能够被这个函数集打散，则函数集的v c 维 就是无穷大。应当指出，这里是存在h 个样本的样本集能够被函数集打敞，不是 指任意h 个样本的样本集能够被函数集打散。函数集的v c 维( 而不是其自由参 数个数) 影响了学习机器的推广性能。这给我们克服所谓的“维数灾难”创造了 一个很好的机会：以一个包含很多参数但却有较小的v c 维的函数集为基础实现 较好的推广性。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂。遗憾的是目 前尚没有通用的关于任何函数集的v c 维计算理论和方法，只对一些特殊的函数 集知道其v c 维。比如在1 1 维实数空间中线性分类器和线性实函数的v c 维是n + i ， 而前文所提到的f ( x ，o r ) = s i n ( c ) 的v c 维是无穷大。对于些较复杂的学习机器 ( 如神经网络等) ，其v c 维除了与函数集( 例如神经网络的函数结构) 有关外， 1 0 第耄鲮毒专学习理论及支撑矢量t 还受学习算法等的影响，其确定就更加困难了。对于给定的学习函数集，如何( 用 建论或者实验静诗箨方法) 计算其v c 维仍是当薪统计学习瑾论中有特疆究舔阉 题i 。 统计学习理论系统地骚突了各耪类型丞数袋豹经验风验窝实际鼹险之趣敬关 系，即推广性的界。关于两类分类问题有如下结论：对指示函数集中的所有函数 ( 包括使经验风险最小化的函数) ，经验风险拧 ) 和实际风险r ) 之间至少以 穰率l 一野满足下列关系： l 霞( 群) sl 。( 掰) + 垂( 等)( 2 8 ) 艇中，h 是函数集的v c 维，是样本数。o o 3 7 时这个界肯定是松驰的， l 当v c 维无穷大时这个界就不再成立了。比如最近邻法，它的v c 维是无穷大的， 但是它在很多情况下有较好的推广性，说明统计学习理论中关于推广性的界的理 论并不能解决祝器学习中静所有闻题，穰多瑟瑟仍待进一步的深入研究。焉且这 种界只在对同一类学习函数谶行比较时有用，可以指导我们从函数集中选择最优 华南理工人学理学硕上学位论文 的函数，在不同函数集之间比较却不一定成立。v a p n i k 在 2 】中也指出，寻找更女了 的反映学习机器能力的参数和更紧的界将是统计学习理论今后的研究方向之一。 2 3 2s r m 准则 从( 2 - 8 ) 式我们可以看出，经验风险最小化原则在样本有限时，不尽合理， 一般需要同时最小化经验风险和置信界限。其实在传统方法中，选择模型和算法 l 的过程就是调整置信范围的过程，如果模型比较适合现有的训练样本( 兰值适当) ， z 则可以取得比较好的效果。但是因为缺乏理论指导，这种选择只能依赖于先验知 识和经验，造成了如神经网络等方法对使用者技巧的过分依赖。 统计学习理论提出了一种新的策略，即把函数集构造为一个函数子集序列， l 使各个子集按照v c 维的大小( 亦即中( 芸) 的大小) 排列；在每个子集中寻找最小 f 经验风险，在子集间折衷考虑经验风险和置信界限，取得实际风险的最小。如图 2 一l 所示，这种思想称为结构风险最小化( 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 ) ，即s r m 准则。统计学习理论还给出了合理的函数子集结构应满足的条 件及在s r m 准则下实际风险收敛的性质。 风险 一三_ 甬数集了集：s 1 匕s 2 c 二j s ， v c 维 h l 托：h 图2 1s r m 准则示意图 f i g u r e2 一is r m p r i n c i p l es k e t c hm a p 1 2 第一章统计学习理论及支撑欠量机 结构风险最小化原则( s r m ) 首先定义了一种函数集的嵌套结构： s l c s 2c cs 。c 这些函数集的v c 维从小到大排列，这样函数集的v c 维就成为了可控参数。对 一个给定的训练集，s r m 原则选择适当的子集s 。使得风险上界( 2 - 8 ) 式最小。 s r m 原则定义了在对给定数据的遁近精度和逼近函数的复杂性之间的一种 折衷。s r m 的一股原则可以用不同的方法实现。在实际的算法中，神经网络是通 过选择一个适当构造的机器来保持固定的置信范围并最小化经验风险；支撑矢量 机是保持经验风险固定并最小化置信范围。实现s r m 原则可以有两种思路，一是 在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的 子集。显然这种方法比较费时，当子集数目很大甚至是无穷时不可行。因此有第 一二种思路，即设计函数集的某种结构使在每个子集中都能取得最小的经验风险 ( 如使训练误差为0 ) ，然后只需选择适当的子集使置信范围最小，则这个子集 中使经验风险最小的函数就是最优函数。实际上，支撑矢量机方法就是第二种思 想的具体实现。应当指出，s r m 准则并没有指出如何选择函数子集结构，而且由 于尚没有一般地关于v c 维计算的理论和方法，构造函数子集的一般方法也是一 个需要进一步研究的问题。 2 4 支撑矢量机简介 2 4 1 简述 支撑矢量机方法是建立在统计学习理论的v c 维理论和结构风险最小化s r m 原则基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精 度，a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷， 以期获得最好的推广能力( g e n e r a l i z a t i o na b i l i