（控制理论与控制工程专业论文）提高支持向量机的学习效率和分类速度的研究和应用.pdf

j 女一。 q 提高支持向量机的学习效率和分类速度的研究和应用 摘要 基于统计学习理论和结构风险最小化原理的支持向量机 ( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是一种非常有力的机器学习 新方法，较好的解决了困扰很多学习方法的小样本、非线性、过学习、 维数灾难、局部极小等问题，具有很好的泛化能力。由于这些良好的 性能，支持向量机和统计学习理论开始受到越来越广泛的重视并得到 了广泛的应用。但是当训练样本的数目很大时，支持向量机的训练需 要的时间和计算机内存急剧增加，这阻碍了支持向量机在解决大样本 问题上的应用。因此为支持向量机解决大样本问题设计快速高效的训 练算法得到了研究人员的极大重视。另外对于大样本问题，支持向量 机往往具有数目众多的支持向量，由于非线性支持向量机的决策函数 的复杂度由支持向量的个数来决定，大量的支持向量导致了高度复杂 的决策函数和较低的分类效率。因此提高解决大样本问题的支持向量 机分类速度也是十分有意义的研究。 本文从支持向量机的理论、方法和应用相结合的角度出发。在提 高支持向量机训练效率，简化支持向量机的决策函数以提高分类速度 以及应用支持向量机改进其他学习方法的性能方面进行了系统的研 究。本文的主要工作和贡献包括以下内容： 1 根据支持向量的特殊性质，提出了候选支持向量的概念，并 设计了从训练集合中选择候选支持向量的方法，在此基础上提出了利 用候选支持向量代替整个训练集合学习支持向量机的方法。实验证明 本方法能够快速学习支持向量机，而且测试精度和利用全部训练集合 得到的支持向量机相当。在本文的方法中，候选支持向量选择算法直 接影响到训练得到的s v m 的性能，约简的支持向量机( r e d u c e ds v m ， 简称r s v m ) 能够快速得到决策函数，而且精度也是令人满意的，因 此它提供了一种有效的候选支持向量选择算法。本文进而提出利用 r s v m 选择候选支持向量，再利用候选支持向量训练标准支持向量机。 实验证明这种方法是十分有效的。 2 对于非线性支持向量机，支持向量的个数和决策函数的复杂 度直接关联。为了简化支持向量机的决策函数，提高分类速度，必须 减少支持向量的个数。本文提出了利用迭代学习和构造替代向量集 合两种方法来简化支持向量机的决策函数，从而提高解决大样本问题 的支持向量机的分类速度。实验证明这两种方法都能够获得支持向量 数目减少的支持向量机，而且简化的s v m 的精度和原始s v m 相当。 3 对于最小二乘支持向量机，由于优化目标函数要使训练误差平 方最小化，导致了稀疏性的丢失，使得所有偏离决策边界的训练样本 都将成为支持向量。所以在解决大样本问题时，会导致决策函数非常 复杂和较慢的分类速度，因此研究获得稀疏最小二乘支持向量机的方 法是很有意义的研究。本文分析了现有获得稀疏最小二乘支持向量机 方法的不足，提出了一种改进的稀疏最小二乘支持向量分类器。实验 证明本方法比现有的方法具有更高的精度，。而且决策函数更简单。 4 在解决大样本问题方面，经典近邻规则需要有效的典型样本选 择算法来支撑。本文从支持向量机的训练得到启发，应用本文的s v m 快速学习算法和分类算法，提出了两种近邻规则选择典型样本的方 法，提高了近邻规则的效率。 一? y l 令 v 关键词：统计学习理论，支持向量机，最小二乘支持向量机，简化支 持向量机，近邻规则，典型样本选择算法 s t u d ya n da p p l i c a t l 0 n0 fr a p i d l e a r n i n ga n dc l a ss i f i c a t i o no f s v m a b s t r a c t t h es u p p o r tv e c t o rm a c h i n e s ( s v m ) t h a ta r ei n d u c e df r o ms t a s t i t i c a l l e a m i n gt h e o 巧a n ds t r u c t u r er i s km i n i m i z a t i o np r i n c i p l ea r eap o w e r 如1 k i n do fm a c h i n el e a m i n gm e t h o d s t h e yh a v eo v e r c o m e dt h eo v e r f i t t i n g ， d i m e n s i o nd i s a s t e r sa n dl o c a lm i n i m ap r o b l e m sw h i c ha r ed i m c u l tt o d e a li no t h e rm a c h i n e1 e a n r i n gm e t h o d s t h es v ma l s oc a ng e n e r a l i z e 一一粕 v w e l lf o ral a r g ev a r i e t yo fp r o b l e m s s ot h es v mh a sb e e nan e wr e s e a r c h h o t s p o ta n db e e nu s e dt os o l v ea ni n c r e a s i n g l ym a n yp r a c t i c a lp r o b l e m s b u tw h e nt h es i z eo ft r a i n i n gs e ti sv e r yl a r g e ，s l o wt r a i n i n gs p e e da n d 1 a 唱es t o r a g er e q u i r e m e n to c c u rt os v ml e a m i n g t h e r e f o r e ，e f j f e c t i v e t r a i n i n gm e t h o d so fs v m sw i t hl a r g et r a i n i n g s e ta r ep a i dm u c hm o r e a t t e n t i o nb yr e s e a r c h e r s i ng e n e r a l ，t h es v m sw i t hn o n l i n e a rk e m e l f u n c t i o n sh a v eh u g es u p p o i r tv e c t o rs e t sw h e nt h et r a i n i n gs e ti sl a r g e ， w h i c hm a k e st h ed e c i s i o nm n c t i o n sc o m p l e xa n dt h et e s i n gs p e e d sv e 巧 s l o w s os p e e d i n gt h ec l a s s i f i c a t i o no fs v m sw i t hl a r g et r a i n i n gs e tb y r e d u c i n gt h es u p p o r tv e c t o rs e t si sav e 巧i m p o r t a n tr e s e a r c ht o p i c j t h i sw o r kh a sf o c u s e do nt h et h e o r y ，m e t h o da n da p p l i c a t i o n so f s v m ，a n ds y s t e m a t i c a l l ys t u d i e dt h em o r ee f f e c t i v et r a i n i n gm e t h o d so f s v m ；m o r es i m p l i f i e ds v mw i t hg o o da c c u r a c ys oa st oi m p r o v et h e 4 产 i v t e s t i n gs p e e d ，a n dt h ea p p l i c a t i o n so fs v m t oi m p r o v eo t h e rm a c h i n e 1 e 锄i n gm e t h o d sf o rs u c hp r o b l e m sw i t hl a 唱et r a i n i n gs e t t h em a i n c o n t r i b u t i o n so ft h i sw o r ka r ea sf o l l o w s ： 1 t h ec o n c e p to fs u p p o r tv e c t o rc a n d i d a t e s ( s v c s ) a n dam e t h o dt o s e l e c ts v c s 仔o mt h et r a i n i n gs e ta r ep r o p o s e d i ti sa l s op r o p o s e dt ot r a i n s v mw i t hs v c si n s t e a do ft h ew h 0 1 et r a i n i n gs e t c o m p u t a t i o n a lr e s u l t s i n d i c a t et h a tt h ep r o p o s e dm e t h o dc a nl e a ms v mw i t h1 e s st i m ea n dt h e a c c u r a c yi se q u a l t ot h a to fs v mw i t hm 1 1t r a i n i n gs e t t h ep e r f o m l a n c e o fp r o p o s e dm e t h o di sd e p e n d e n to fm e t h o dt os e l e c ts v c s f o rt h e r e d u c e ds u p p o r tv e c t o rm a c h i n e ( r s v m ) c a no b t a i nt h ed e c i s i o n 如n c t i o n q u i c k l yw i t hs a t i s f a c t o i ya c c u r a c y ，s oi t i sp r o p o s e dt h a to n ec a nu s e r s v mt os e l e c ts v c sa n dt r a i ns t a n d a r ds v mw i t ht h es e l e c t e ds v c s c o m p u t a t i o n a lr e s u l t ss u p p o r ti t se f f e c t i v e n e s s 2 f o rn o n l i n es u p p o nv e c t o rm a c h i n e s ，t h ec o m p l e x i t yo fd e c i s i o n 如n c t i o n si sd e t e m i n e db yt h en u m b e ro fs u p p o i r cv e c t o r s i no r d e rt o i m p r o v et h et e s t i n gs p e e do fs v mw i t hl 粥et r a i n i n gs e t ，t h es v m s h o u l db es i n l p l i f i e db yr e d u c i n gt h es u p p o r tv e c t o rs e t t w om e t h o d st o s i m p l i 矽s v ma r ep r o p o s e d ，a n do n ei st oo b t a i ns i m p l i f i e ds v mw i t h l e s ss u p p o r r tv e c t o r sb yi t e r a t i v e1 e a m i n g ，t h eo t h e ri st os i m p l i 矽t h e d e c i s i o n 向n c t i o n b yc o n s t m c t i n gas m a ua p p r o x i m a t i n gv e c t o r s e t c o m p u t a t i o n a lr e s u l t si n d i c a t et h a t ，b yb o t hm e t h o d s ，o n ec a no b t a i n s i m p l i f i e ds v m sw i t hm u c hl e s ss u p p o r tv e c t o r sa n dt h es i h l p l i f i e ds v m h a v ee q u i v a l e n ta c c u r a c yt oo r i 百n a lg i v e ns v m 3 t h el e a s t s q u a r e s s u p p o r tv e c t o rm a c h i n e s ( l s s v m s ) l o s tt h e s p a r s e n e s s b e c a u s et h e s q u a r e s o fe r r o r sa r em i n i m i z e di nt h e o p t i m i z a t i o nt a r g e tf u n c t i o n s oa l lt h en a i n i n ge x a m p l e so f ft h ec l a s s b o u n d a 巧 w i l lb es u p p o r tv e c t o r sa n di ti s u r g e n t t oo b t a i n s p a r s e 5 l s s v m sw i t hl a r g et r a i n i n gs e t s b a s e do ne x t e n s i v ea n a l y s i so f e x i s t i n gm e t h o d s ，a ni m p r o v e ds p a r s el s s v mc l a s s i f i e ri sp r o p o s e d ，t h e c o m p u t a t i o n a lr e s u l t si n d i c a t ei ti sm o r ee f i f e c t i v et h a np r e v i o u ss t u d i e s 4 t h ec l a s s i c a ln e a r e s tn e i g h b o rr u l e s ( n nm l e s ) n e e dm o r ee f f e c t i v e p r o t o t y p es e l e c t i o nm e t h o d sa ss u p p o i r t si no r d e rt os o l v es u c hp r o b l e m s w i t hl a r g et r a i n i n gs e t t h ea b o v er e s e a r c hr e s u l t so ns v m sa r ea p p l i e d t od e s i g n i n gt w op r o t o t y p es e l e c t i o nm e t h o d sf o rn nm l e ss oa st o i m p r o v e t h ec l a s s i f i c a t i o ne 衔c i e n c yo fn nm l e s k e yw o r d s ：s t a t i s t i c a l1 e a m i n g ，s u p p o r tv e c t o rm a c h i n e s ，l e a s t s q u a r e ss u p p o r tm a c h i n e s ， s i m p l i 矗e ds u p p o r tv e c t o rm a c h i n e s ，n e a r e s t n e i g h b o rm l e s ，p r o t o t y p es e l e c t i o na l g o r i t h m s 6 v 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：季3 之 日期：沙饵r 月尸 ，l 伊? v 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 | 不保密日。 ( 请在以上方框内打“”) 学位论文作者虢辔缓 指导教师 日期：沙年月罗日 日期：年月日 _ r 童 v 第l 章绪论 人类智慧的一个重要标志就是学习能力，表现为根据过去的数据和以往的 知识，通过归纳学习，得到对客观世界的认识和规律。这些知识可以帮助人类 认识现有的世界，同时帮助人类对未知的现象做出正确的预测和判断。利用获 得的规律对未知的现象做出正确的预测和判断，这种能力称为推广能力或者泛 化能力。 在人工智能的研究中，人们试图通过计算机来模拟人类的这种学习能力， 从而赋予计算机一定的“智慧”，具有某种知识，这被称为基于数据的机器学 习川。基于数据的机器学习的任务就是设计某种方法和模型，通过已知的数据， 找到数据内在的相互依赖关系，从而对未知数据进行预测和判断。其最终目的 是使机器具有良好的泛化能力。 基于传统统计学的机器学习方法，以样本无穷为假设来推导算法和建模。 然而在现实中，能够得到的样本数目是有限的，此时传统的机器学习方法得到 的结果有时差强人意。这是因为在有限样本的情况下，往往是多个解都满足给 定的条件，具体哪一个解被训练算法选中输出与具体算法有关。所以在有限样 本的情况下，很难得到反应真实样本分布的解。如何在有限样本的情况下得到 泛化能力最好的分类器是机器学习需要解决的一个棘手的问题。v a p n i k 等人开 始建立的一个新的统计学习理论体系为解决这个问题提供了有力的武器。这一 理论体系称为统计学习理论( s t a t i s t i c a ll e a m i n gt h e o r y ) 【2 圳。 统计学习理论系统 的研究了机器学习的问题，尤其是在小样本情况下的统计学习问题。并在此理 论的框架体系下，产生了种新的非常有力的通用学习方法：支持向量机 ( s u p p o r tv e c o t rm a c h i n e s ，简称s v m ) 。由于支持向量机具有优良的性能，近年 得到了研究者的极大重视，在理论和应用领域都取得了极大的进展。 1 1 机器学习以及机器学习问题的表达 学习是系统获取知识，使其本身能力增强或者改进的自我完善过程，使得 其在下次执行同样的任务或者类似任务时，能做得更好，效率更高，适应性更 强。机器学习则是指用机器来模拟人类的学习活动，使机器能够自动获取新的 上海交通大学博士学位论文 知识的和技能，不断完善其性能，并识别现有的知识。机器学习是人工智能研 究的一个重要研究领域，也是人工智能研究的核心课题之一。机器学习的目的 是根据给定样本对系统输入输出之间依赖关系进行估计，使得她能够对未知输 出做出尽可能准确的预测。输入输出之间的依赖关系称为学习函数、学习模型 或者学习机器。对于给定的独立同分布样本 z i ，z 2 ，z 学习问题一般可以表示如下：设有定义在空间z 上的概率测度f ( z ) 和函数 的集合q ( z ，口) ，臼r 。学习的目的就是最小化风险泛函： r ( 口) = i q ( z ，口) d f ( z ) ，臼尺( 1 1 ) 其中q ( z ，口) 是损失函数。所以学习问题就是在已知数据的基础上最小化风 险泛函月( 口) 。 学习问题的形式化表达很多，最基本的三类机器学习问题分别是模式识别 ( 分类问题) ，函数逼近( 回归估计) 和概率密度函数估计4 1 。 1 模式识别 对模式识别问题，考虑一个两类问题，令( 戈，臼) ，d 人为判别函数集合， 损失函数为： 坳胞砌= 侣多i 麓等 2 ， 对于这个损失函数，风险泛函r ( d ) 确定了训练机器和判别函数输出不同的 概率。把这种训练机器输出和判别函数输出不同的情况称为分类错误。所以对 于分类问题，学习问题就是在概率测度f ( z ，y ) 未知，给定数据的情况下，寻找 使得分类错误的概率最小的函数。 2 回归估计 假设训练机器的输出为实数值j ，厂( x ，口) ，以人为实函数集合，其中包含 了回归函数。令损失函数为：三( j ，( x ，口) ) = ( 少一( x ，口) ) 2 。回归函数就是在损失 函数下使得风险泛函r ( 以) = i ( j ，厂( x ，口) ) 卵( x ，y ) 最小的函数。所以对回归估计 问题，学习问题就是在概率密度f ( x ，j ，) 未知，给定数据的情况下，寻找使得r ) 、 l l ：- _ i v ， r _ | - 第l 章绪论 最小的函数。 3 概率密度估计 概率密度估计问题研究从概率密度函数集p ( x ，口) ，口人中估计概率密度函 数的问题。令损失函数为：( p ( x ，臼) ) = 一l o g p ( x ，口) ，所要求的概率密度函数就 是在损失函数下使得r ( 口) 最小化。所以概率密度估计问题就是，在相应的概率 密度瞰) ，给定数据的情况下，寻找使得月 ) 最小的概率密度函数。 1 2 经验风险最小化原则 在用数据进行期望风险的随机逼近时，经常用到经验风险最小化原则，它 是目前的一些学习方法( 如神经网络、最小二乘) 中最常用的学习原则。以回 归估计为例： 假设样本 ( x ，m ) ，( _ ，乃) r 胛r ( 1 3 ) 是从未知概率分布p ( x ，j ，) 的独立采样，回归估计问题的风险泛函为： r ( 日) = 三( y ，厂( x ，口) d 尸( x ，y ) ( 1 4 ) 其中厂( x ，口) 是用来最小化风险泛函的目标函数，( y ，( x ，口) ) 是损失函数， 它是对应于输入x 的y 与目标函数( x ，口) 之间的偏差。当概率分布尸( x ，少) 未知 的时候，很难直接评价或者最小化r ( 臼) 。只能通过经验风险函数r ( 口) 来逼近 r ( a ) 的最小化。对于给定的经验数据x 和y ，r ( a ) 可以用经验数据的和 u 妒导喜m 卅) ( 15 ) 来取代在概率密度函数尸( x ，y ) 上的积分r ( 口) 。r ( 口) 常被称为经验风险泛 函。 在实际的学习算法中常常用最小化经验风险泛函来取代实际的期望风险泛 函，这就是最小经验风险原则e r m ( e m p i r i c a l 鼬s km i n i m i z a t i o n ) 。最小化经 验风险原则应用很广，一些经典的方法，如回归问题中的最小二乘法、极大似 然法都是最小经验风险原则在特殊损失函数下的应用，传统的神经网络学习方 上海交通大学博士学位论文 法也应用了最小经验风险原则。 在神经网络学习研究中，研究者发现一味追求训练误差小并不是总能达到 好的预测效果。在某些情况下，当训练误差过小反而使得泛化能力下降。这就 是几乎所有的神经网络研究者都曾遇到的过学习问题。之所以出现过学习现象， 一是因为学习样本不充分，二是因为学习机器设计不合理。这两个问题相互关 联。在神经网络学习中，对于有限的样本，如果网络学习能力过强，足以记住 每一个训练样本，此时经验风险很快就可以收敛到很小甚至为0 ，但无法保证它 对新样本能够很好的预测。这些问题使研究人员认识到： 1 经验风险最小化并不一定意味着期望风险最小。 2 学习机器的复杂性不但与所研究的系统有关，而且要和有限样本相适应。 这就是有限样本下学习机器的复杂性和泛化能力之间的矛盾。有限样本情 况下学习精度和泛化能力之间的矛盾几乎不可调和，采用复杂的学习机器容易 使得学习误差更小，但往往导致泛化能力的下降。统计学习理论的发展为此问 题的解决提供了坚实的理论基础和有效方法。 1 3 统计学习理论 统计学习理论被认为是目前针对有限样本统计估计和预测学习的最佳理 论。它从理论上系统的研究了经验风险最小化原则成立的条件、有限样本下经 验风险与期望风险的关系以及如何利用这些理论找到新的学习原则和方法的问 题。统计学习理论的主要内容包括：基于e r m 原则的学习过程具有一致性的充 分必要条件；学习过程收敛速度的非渐进理论，即研究学习过程收敛的速度问 题；控制学习过程的推广能力理论，即研究如何控制学习过程的推广能力；构 造学习算法的理论，即研究如何构造能够控制推广能力的学习机器。 关于学习一致性的结论是统计学习理论的基础，也是它与传统渐进统计学 的基本联系所在。所谓学习过程一致性，就是指当训练样本数目趋于无穷大时， 经验风险的最优值能够收敛到真实风险的最优值。只有满足这一条件，才能保 证在经验风险最小原则下得到最优方法当样本趋于无穷大时趋近于期望风险最 小的最优结果。 定义1 ：设q ( z ，a ) 是对给定的独立同分布观测蜀，乞，z ，使经验风险泛函 - 、 p 、 j 。 第l 章绪论 = q ( 刁，口) 最小化的函数。如果下面两个序列以概率p 收敛于同一个极 - l 限，即 r ( q ) 与i n f 尺( 口) ，尺。驴( q ) = 兰哼i n f r ( 口) 口e 口 则e r m 原则，对函数集q ( z ，口) ，口人和概率分布函数心) 是一致的【4 】o 也就是说，一个e r m 方法，如果它提供一个函数序列q ( z ，口a ，= l ，2 ， 对这个序列来说期望风险和经验风险都收敛到最小可能的风险值，则这个e r m 方法是一致的。为了保证一致性是所研究的学习方法的性质，而不是由于函数 集中的个别函数导致的。因此提出了非平凡一致性的概念，即定义中的式子对 预测函数集的所有子集都成立。只有非平凡一致性才是实际上有意义的，因此 这里说的一致性就是指非平凡一致性。 定理 1 【4 】： 设函数集 q ( z ，口) ，口八 ，满足条件 彳f q ( z ，口) 卵( z ) b ，彳r ( 以) b ，那么e i 州原则一致性的充分必要条件是： 经验风险r 。( 口) 在如下意义上一致收敛于实际风险尺( 口) ： 1 i m p s u p ( r ) 一心妒( 日) ) 占) = 0 ，v s 0 ，其中p 表示概率，r ( 臼) 和r 。p ( 口) 分别是真实风险和经验风险泛函。 因为这一理论在统计学习理论中的重要性，被叫做学习理论的关键定理。 它把学习一致性的问题转化为上式的一致收敛问题。由于在学习过程中，经验 风险和期望风险都是预测函数的泛函。机器学习的目的不是用经验风险去逼近 期望风险，而是通过使经验风险最小化的函数来逼近能使期望风险最小化的函 数。因此其一致性条件比传统统计学中的一致条件更严格。从学习理论关键定 理看到，统计学习理论中基于经验风险最小化原则的学习过程一致性的条件是 取决于预测函数中最差的函数的，因此是最坏情况分析。 在统计学习理论中，收敛速度的定义为，如果对应任意的7 f 0 ，都成立 p r ( 口) 一r ( 口o ) s ) p 。r 。 ( 1 6 ) 则称渐进收敛的速度是快的5 1 。为了研究函数集在经验风险最小化原则的学 习一致性问题和一致性收敛的速度，统计学习理论提出了学习理论的三个里程 上海交通大学博士学位论文 碑的定理。他们在不同程度上回答了学习理论中的最基本的问题，即在什么条 件下，一个遵循经验风险最小化原则的学习机器或算法，当样本数目趋向无穷 大时收敛于期望风险最小的最优解，而且收敛速度是快的。 设有一个指示函数集厂( x ，口) ，和一组，个训练样本集合 z ，= z j = ( x ，y ，) ，f = 1 ，2 ，f ) ，贝0 有 定理2 【4 1 ：函数集学习过程双边一致收敛的充分必要条件是l i m 旦旦：o ， ，_ o f 其中日( 7 ) 是指示函数集在样本数，上的v c 熵。 定理3 【4 】：函数集学习过程收敛速度快的充分条件是l i m 皇警盟：o ， ，_ 。 f 玩。( ，) 为退火的熵。 定理4 【4 】：函数集学习过程一致收敛的充分必要条件是对任意样本分布，都 有；i m 鱼婴：o ，这时学习过程收敛速度一定是快的。其中g ( f ) 为函数集的生长 ，- + 0 。 z 函数。 学习算法推广能力的分析是学习机器性能和开发新的学习算法的重要基 础。它是建立在v c 维基础上的。 定义2 【6 】：设f 为一个从以维向量x 到( 0 ，1 ) 的函数族，则，的v c 维为 子集e 的最大元素数，其中_ e 满足：对于任意s e ，总存在函数厂f ，使得 当x s 时，厂( x ) = l ；当x 仨s 但x e 时，厂( x ) = 0 。 v c 维是统计学习理论中的一个核心概念，它是目前为止对函数学习性能的 最好的描述指标。v c 维可作为函数族f 复杂度的度量。它是一个自然数，表示 无论以何种组合方式出现均可被函数族f 正确划分为两类的向量个数的最大值。 由于基于统计的学习机可以由一族函数 ( x ，口) ，口人) 表征。因此， 厂( x ，口) ，口人) 的v c 维也表征了该学习机器的v c 维。它表征了学习机的最大 学习能力，是学习机容量的一种度量。 统计学习理论关于函数集的推广能力的界有如下的结论【4 】： 定理5 ：对于指示函数集( x ，日) ，如果损失函数q ( z ，口) = 三( y ，厂( x ，口) ) 的取 值为0 或1 ，对所有函数，则经验风险和实际风险之间至少以概率1 7 7 满足如下 第l 章绪论 关系： 脚) 啪) + 卢巫乒巫 7 ， 其中，是样本数，办是学习机器的v c 维 以上定理告诉我们，经验风险最小化原则下的学习机器的实际风险是由两 部分组成的，其中一部分为训练样本的经验风险，第二部分称作置信区间。从 界的表达式可以看出，置信区间不仅受到置信水平1 7 7 的影响，而且更是函数 集v c 维和训练样本数目的函数，且随着它的增加而单调减少。定理给出的是关 于经验风险和真实风险之间差距的上界，它们反映了根据经验风险最小化原则 得到的学习机器的推广能力，被称为推广能力的界。 对于数目为，的样本，如果比值，办小于2 0 ，则这样的样本集为小样本【7 1 。 进一步分析发现，当z 办较小时，置信区间较大，用经验风险金丝真实风险是有 较大的误差，用经验风险最小化得到的最优解可能具有较差的推广能力；如果 样本数目较多，当，办较大，则置信区间就会小，经验风险最小化的最优解就接 近实际的最优解。 另一方面，对于一个特定的问题，当样本数目，是固定时，学习机器的v c 维越高，也即复杂性越高，置信区间就越大，导致真实风险与经验风险之间可 能的差就越大。因此，在设计学习机器时，不但要使经验风险最小化，还要使 v c 尽量小。从而缩小置信区间，使期望风险最小。这就是一般情况下选用过于 复杂的分类器和神经网络往往得不到好的效果的原因。 所以，要使训练好的学习机器具有较好的泛化能力，需要在v c 维与训练 集规模之间取得某种较好的折衷。由于神经网络的v c 维取决于网络结构中可调 参数的数目，而后者又是由网络拓扑结构确定的，所以网络的v c 与网络拓扑结 构之间有必然的联系。在给定训练集合的情况下，如果能求出合适的v c 数，则 可以帮助确定的网络结构。 1 4 结构风险最小化原则 e 蹦原则是从样本无穷大假设下出发的，这一原则还可以通过考虑推广能 力界的不等式来证明。当，办较大时，第二项就变得很小，于是实际风险就接近 上海交通大学博士学位论文 经验风险的分值，较小的经验风险值能够保证期望风险值也较小。然而如果z 办 较小，那么一个小的r 。( 口) 并不能保证小的实际风险值。在这种情况下，要最 小化实际风险尺( 口) ，应当对第一项和第二项同时最小化。因此在传统的机器学 习方法中，普遍采用的经验风险最小化的原则在样本数目有限时是不合理的， 因为需要同时最小化经验风险和置信区间。事实上，传统的方法中，选择学习 模型和算法的过程就是优化置信范围的过程。例如在神经网络中，需要根据问 题和样本的具体情况来选择网络结构，然后进行经验风险最小化。这种做法实 际就是首先确定( ，办) ，然后利用经验风险最小化来求最小风险。这种选择往 往是依赖经验，过分依赖于使用者的技巧。 统计学习理论利用推广能力界的理论寻找解决策略。这就是定义函数 q ( z ，以) ，d 人的集合s 具有一定的结构。这一结构由一系列嵌套的函数子集 瓯= q ( z ，口) ，以八。) 组成的。它们满足scs ：c cs ，其中结构中的元素满 足下面两个性质【4 j 。 1 每个函数集& 的v c 维是有限的，因此矗。 2 结构的任何元素瓯包含一个完全有界函数的集合 o q ( z ，以) 峨，口a k 。 这样在同一个子集中置信区间就相同，在每一个子集中寻找最小经验风险。 选择最小化经验风险与置信区间之和最小的子集，就可以达到期望风险的最小。 这个子集中使经验风险最小的函数就是所要求的最优函数。这种思想称作结构 风险最小化( s t m c t l l r e 础s km i n i m i z a t i o n ，简称s r m 原则) 。对于一个给定的 观测集z 。，z ：，z ，s r m 原则在保持风险最小化的子集& 中选择使经验风险最小 化的函数q ( z ，研) 。s r m 原则定义了在对给定数据逼近精度和逼近函数的复杂性 之间的一种折衷。图1 1 为风险界示意图，随着子集序号的增加，经验风险的最 小值减小，但决定置信范围的项却增加。s r m 原则通过选择子集& 将两者都考 虑在内，最小化经验风险得到了最好的界。在函数逼近精度和逼近函数的复杂 性之间取得了一种最佳的折衷。这时模型具有最好的推广能力。 结构风险最小化提供了一种不同于经验风险