（应用数学专业论文）基于e范数的学习推广能力与计算复杂性.pdf

中文摘要 摘要 我们已经知道基于v c ( v a p n i k - c h e r v o n e n k i s ) 维及其推广f s ( f a t - s h a t t e r i n g ) 维 的统计学习理论以及在此理论基础上构造的通用学习机器一一支持向量 机( s v m s ) 的有关技术由于其强大的功能和优良的特性近几年来s v m s 技术已 经广泛应用于文本分类，图像识别，生物信息学等领域尽管如此，基于v c 维的学 习理论仍然存在不足主要表现为有关推广能力的界可能太大甚至不切实际；在 算法的某些实现中表现为收敛速度慢。所需训练样本大。错误率高等缺陷因此， 寻找能够更为精确地描述推广性能和算法复杂性的参数就显得很有意义 近几年来。人们在这一方面的探索取得了一定的成果其中基于b a n a c h 空间 局部理论的p 一范数为研究学习问题的的推广性能提供了一个表现良好的参数 已经证明如果b a n a c h 空间的对偶单位球的经验p 一范数是有界的，那么它的对称 凸包具有一个有着较小直径的七阶余维的部分而且决定该部分的泛函可以经验 的算出依据经验数据寻求所期望的依赖关系的学习问题可以归结为解一个线 性方程组的问题本文在此基础上利用b a n a c h 空间的几何结构进一步研究了学习 问题的推广性能。给出了统计量复杂性( s t a t i s t i c c o m p l e x i t y ) 的概念及其界的估计 本文的主要内容安捧如下： 第一章：引言主要介绍学习问题的背景和研究方法以及本文的主要结果 第二章：介绍基于v c 维及其推广f s 维的统计学习理论主要包括学习问题 收敛性的定性分析和定量分析以及s v m s 的思想和方法 第三章：介绍b a n a c h 空间和f 一范数的有关理论回顾了b a n a c h 空间，f 一范数。 覆盖数及其与f 一范数的关系，v c 维与一范数的关系等后面将要用到的基本概念 和重要结论 第四章：基于前面凡章所提得到的已有结果我们首先给出了基于经 验f 一范数的样本误差的界然后依据b a n a c h 空间中称为g a u s s 型的几何特 性。我们又得到了基于g a u s s 型的样本误差的界及样本复杂性估计最后 在p o j o r f f l l t o m c z a kj a e g e r m a n n 的一个重要结论的基础上我们总结了基于e 一范 数求解学习问题的方法 第五章：这一章主要研究了基于f 一范数求解学习问题的算法复杂性我们 把为了达到一定的精度所需构造的经验泛函的最小个数定义为假设空间的统计 量复杂性利用一范数估计了f s 维具有多项式增长级的函数集的统计量复杂性 湖北大学硕士学位论文 据此可以找到一个基数性为统计量复杂性的线性经验泛函集。利用该线性经验泛 函集可以构造以所需的任意精度逼近未知函数的学习算法同时给出了随机生 成这些经验泛函的方法 第六章：总结与评述以h i l b e r t 空间为例对本文所涉及的学习算法作出总 结，并且提出了有待进一步解决的问题 关键词：推广能力：g l i v e n k o c a n t e l l i 类：l - 范数：v c 维；统计量复杂性 - 英文摘要 a b s t r a c t w eh a v ek n o w nt h es t a t i s t i c a ll e a r n i n gt h e o r yb a s e do nt h ev c ( v a p n i k - 嘶o n e n k i s ) d i m e n s i o na n di t sg e n e r i cv e r s i o nf s ( f a t - s h a t t e r i n g ) d i m e n s i o na l o n g w i t ht h et e c h n o l o g yo fs u p p o r tv e c t o rm a c h i n e s ( s v m s ) 一一t h eg e n e r a ll e a r n i n gm a - c h i n e sb a s e do nt h i st h e o r y t h et e c h n o l o g yo fs v m sh a sb e e nw i d e l yu s e di nt e x t c l a s s i f i c a t i o n ，i m a g er e c o g n i t i o n , b i o l o g i c a lm e s s a g ee t c i nd a ep a s tf e wy e a r sf o ri t s w o n d e r f u lp e r f o r m a n c e h o w e v e r t h el e a r n i n gt h e o r yb a s e do nt h ev cd i m e n s i o nh a s s o m ed e f e c t ss u c ha st h eb o u n d so f g e n e r a l i z a t i o na b i l i t yo f t h el e a r n i n gm a c h i n e sm a y b et o ol a r g eo ri n s i g n i f i c a n t , t h er a t eo fc o n v e r g e n c em a yb es l o w l yi ni m p l e m e n t a t i o n o f s o m e a l g o r i t h m s 。t h e n e e d e d t r a i n i n gs a m p l e t o o m a c ha n ds o o n s o ，i t i s i n t e r e s t i n g t os e e ko t h e rp a r a m e t e rw h i c hw i l lb em 眦p r e c i s e l yi nd e s c r i p t i o nt h eg e n e r a l i z a t i o n p e r f o r m a n c ea n dt h ea l g o r i t h m sc o m p l e x i t y br e c e n ty e a r s s u b s t a n t i a lp r o g r e s sh a sb e e ng a i n e di nt h i sd i r e c t i o n ha l lt h e r e s u l t s ，t h ee - n o r mw h i c hi saf u n d a m e n t a lt o o li nt h el o c a lt h e o r yo fb a n a c hs p a c e s p r o v i d e sap a r a m e t e rw h i c hh a sg o o dp 口f o m a n c ei nt h es t u d yo fl e a r n i n gp r o b l e m i t h a sb e e np r o v e dt h a ti ft h ee m p i r i c a le - n o r mo fau n i tb a l lo ft h ed u a l i t yo fab a n a c h s p a c ei sb o u n d e dt h e ni t ss y m m e t r i c c o n v e xh u l lh a sas e c t i o no f c o d i m e n s i o n 七w h i c h h a sa s m a l l d i a m e t e r m o r e o v e r , t h ef u n c t i o n a l sw h i c hd e t e r m i n et h i ss e c t i o nm a yb e c a l c u l a t e de m p i r i c a l l y t h u s ，t h el e a r n i n gp r o b l e mo fc h o o s i n gt h ed e s i r e dd e p e n d e n c e o nt h eb a s i so fe m p i r i c a ld a t am a yb er e d u c e dt ot h ep r o b l e mo fs o l v eo fas y s t e mo f l i n e a re q u a t i o n s i nt h i sp a p e r , w es t u d yt 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 ft h el e a r n i n g p r o b l e m b a s e d o n t h e s e r e s u l t s a t t h es a m e t i m e ，t h e c o n c e p t o f s t a t i s t i c c o m p l e x i t y i s g i v e na n dt h ee s t i m a t e so ni t su p p e rb o u n di sp r o v i d e d t h em a i nc o n t e n ta i ea r r a n g e d a sf o l l o w i n g ： i i lt h ef i r s tp a r tw ei n t r o d u c et h er e s e a r c ho b j e c t sa n dm e t h o d so f l e a r n i n gp r o b l e m a l o n gw i t ht h em a i nr e s u l t so ft h i sp a p e r i np a r tt w o t h es t a t i s t i cl e a r n i n gt h e o r yb a s e do nt h ev cd i m e n s i o ni si n t r o d u c e d i n c l u d et h eq u a l i t a t i v ea n dq u a n t i t a t i v ea n a l y s i sa b o u tt h ep r o p e r t yo fc o n v e r g e n c eo f t h el e a r n i n gp r o b l e ma sw e l la st h ei d e ao fs v m s i nt h e i i r dp a r t t h et h e o r ya b o u tb a n a c hs p a c ea n de - n o r mi si n t r o d u c e d w e r e c a l lc o n c e p t sa n dr e s u l t sa b o u tb a n a c hs p a c e s ，e - n o r m 。c o v e r i n gn u m b e ra n dt h e r e l a t i o n sb e t w e e nt h e ma n dv cd i m e n s i o nw h i c hw i l lb eu s e di nt h es e q u e l i l lt h ep a r tf o u r , t h eb o u n do fs a m p l ee r r o l d e s c r i b e db ye m p i r i c a le - n u r mi sg i v e n m 湖北大学硕士学位论文 u s i n gt h er e s u l t si n t r o d u c e da b o v e a f t e rt h a t 。w ee s t i m a t et h eu p p e rb o u n do fs a m p l e e r r o ra sw e l la st h es a m p l ec o m p l e x i t yu s i n gt h eg e o m e t r i cp r o p e r t yo fb a n a c hs p a c e c a l l e dg a u s s i a nt y p e a tl a s t ，w ec o n c l u d ea l e a r n i n gp r o g r a mb a s e do nt h et h e o r y a b o u tg - n o r mu s i n ga ni m p o r t a n tr e s u l tb e l o n gt op o j o ra n dt o m c z a k j s e g e r m a n n i nt h ep a r tf i v e , w es t u d yt h ec o m p u l a t i o n a lc o m p l e x i t yo ft h el e a r n i n gp r o b l e m b a s e do nt h ee - n o r m w ed e f i n et h es t a t i s t i cc o m p l e x i t yo fh y p o t h e s i ss p a c e sa st h e m i n i m u m n u m b e r o f t h e e m p i r i c a l f u n c t i o n a i sn e e d e d t o e l l , s a g e t h e g i v e n a c c u r a c y w e e s t i m a t et h es t a t i s t i cc o m p l e x i t yo ff u n c t i o nc l a s s e sw i t hap o l y n o m i a lr a t eo ft h ef s d i m e n s i o na n ds h o wt h a to n e c a nf i n das e to fl i n e a re m p i r i c a lf u n c t i o n a l so fs i z ei n t h es t a t i s t i cc o m p l e x i t yt h a ta r es u f f i c i e n tf o rc o n s t r u c tal e a r n i n ga l g o r i t h mw h i c hc a l l a p p r o x i m a t et i mu n k n o w nf u n c t i o n a tt h es a i f l et i m e ，t h er a n d o mp r o c e d u r et os e l e c t t h e s ef u n c t i o n a l si sg i v e n a tl a s t ，t h er e m a r k sa n dc o n c l u s i o n sa r eg i v e n a sa ne x a m p l e ，w ep r e s e n ta c o m p l e t el e a r n i n gs c h e m ei nah i l b e r ts p a c eu s i n gt h et h e o r yi nt h i sa r t i c l e b yt h e w a y , t h eo p e np r o b l e m sb cp r o p o s e d k e yw o r d s ： g e n e r a l i z a t i o np e r f o r m a n c e ；g l i v e n k o c a n t e l l ic l a s s ；l - n o r m ；v c d i m e n s i o n ；s t a t i s t i cc o m p l e x i t y 一一 湖北大学学位论文原创- i 生声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 论文作者签名： 禽舐冱 签名日期：山矽年月日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务：学 校可以允许采用影印、缩印、数字化或其它复制手段保存学位论文：在不以赢 利为目的的前提下，学校可以公开学位论文的部分或全部内容。( 保密论文在 解密后遵守此规定) 论文作者签名：省俺钞父蕴 签名日期小妒年朗移日 导师签名：龆，宅 签名日期：叩年珀7 日 第一章引言 第一章引言 一般来说学习问题是人工智能和生物智能中最核心的问题理解学习问题的 本质在诸如经济决策，各类工程学，计算机科学特别是在研究人类的思维过程等 很多学科中都具有十分重要的意义从数学的角度来说学习问题是指依据经验数 据选取所期望的依赖关系的统计推理闯题其中推广性能是学习理论中最基本的 问题，而学习算法的复杂性在理论的实现中是一个不可忽视的因素 1 1 传统的统计推理方法 从g a u s s 和l a p l a c e 所作的开创性的工作以来，统计推理的基础已有两百多年 的历史2 0 世纪以来得到迅猛发展统计推理的问题可以描述为：给定一个来自 某一函数依赖关系的经验数据集推断这一函数依赖关系 2 0 世纪2 0 年代f i s h e r 提出了参数统计学统一框架下的统计推理的主要模 型他把从给定数据集估计函数的不同问题( 判别分析，回归估计和密度估 计) 表达为参数化模型的参数估计问题，并提出了估计所有模型的未知参数的方 法。即最大似然法 1 1 1 统计推理的参数体系 参数推理的主要思想是在2 0 世纪3 0 年代发展起来的，1 9 3 0 年至1 9 6 0 年这3 0 年 问是参数推理的黄金时期经典参数体系的哲学思想基于以下三点； 第一，为了从数据中找到一种函数依赖关系，统计学家可以定义一个与参数 成线性关系的函数集，它包含了对所求函数的最佳逼近描述函数集的自由参数 的个数较少这一思想得到了w e i e r s t r a s s 定理的支持根据w e i e r s t r a s s 定理任何 连续函数都可以在有限区问上以任意精度用多项式来逼近由此而得到的启发 是，如果多项是能够很好的逼近所求函数，那么就可以定义与参数成线性关系且 只含有少量自由变数的一个函数集( 不一定是多项式，比如三角函数) ，该函数 集提供所求函数的一个好的逼近 第二，大多数实际问题的随机分量所隐含的统计规律是正态律这一思想得 到了中心极限定理的支持中心极限定理指出：在很宽泛的条件下，大量随机变 量之和可以用正态律来逼近而实际问题的随机性是大量随机分量相互作用的结 果，则问题的随机因素可以用正态律来描述 湖北大学硕士学位论文 第三，最大似然方法是估计参数的有效工具这一点得到了关于方法的条件 最优性定理的支持人们期望最大似然方法成为估计模型参数的有效工具，既使 对小样本也不例外 1 1 2 参数体系的缺点 2 0 世纪6 0 年代，随着计算机科学的迅猛发展，研究人员试图利用计算机解决 高维问题。或得到更精确的逼近这些尝试立刻在经典参数体系所立足的三个思 想上暴露出这一体系的缺点 首先大规模多变量问题的分析导致了“维数灾难”增大所考虑因子的数 量需要成指数的增加计算资源例如。根据w e i e r s t r a s s 定理，任何定义在n 维单位 立方体上的连续函数都可以用任意精度用多项式来逼近然而，如果欲求的函数 只有8 阶的导数，则利用含项的多项式只能保证精度o ( n 一n ) 如果未知函数不 是很光滑( o o s 比较小) ，则为了获得较高的精度，随着变量数目n 的增加需要成指 数的增加多项式的项数因此，在含有几十个甚至几百个变量的实际多维问蹶 中定义一个相当小的函数集，且函数集中包含对欲求函数的较好逼近是不切实 际的 其次，通过分析实际数据，t u k e y 说明了实际问题的统计成分并不能仅用经典 的统计分布函数来描述实际分布经常是存在差别的为了构造有效的算法，必须 考虑这种差别 另外，j a m e s 和s t e i n 证明，既使对于最简单的密度估计问题比如，估计具有单 位协方差矩阵的n 2 维的正态律的均值问题，最大似然方法也不是最好的i2 | 他 们提出了一个估计子，对于这一特定问题。该估计子都比似然估计子好 因此，经典体系所立足的三个基本思想被证明对于许多问题是不适合的人 们试图通过推广三个基本假设来挽救经典体系。例如h u b e r p 提出了参数统计 学的鲁棒方法吼n e d l e r j 和w e d e m b u r nr 提出了广义线性模型：b m i m a nl ， h u b e rp 和f r i e d m a nj 用正则化经验风险最小化方法取代最大似然方法h 尽管 取得了一些成果经典参数体系的局限性仍然存在在这种背景下一种通用的非 参数推理方法一一学习方法得到了迅速的发展并取得了丰硕的成果本文主要考 察统计推理的学习方法 2 第一章引言 1 2 学习问题的数学模型 本文所涉及的学习问题是指依据经验数据选择所期望的依赖关系的问题而 学习过程则是一个从给定的函数集中选择一个适当函数的过程 1 2 1 学习问题的一般表达 学习问题的一般模型可以用三个部分来表示：( 样本) 数据产生器( & 哪恤 g ) ，训练器( s u p e r v i s o r , s ) 与学习机器( l e a r n i n gm a c h i n e l m ) 产生器是决定硼练器和学习机器运作环境的源头本文中，我们考虑最简单 的情形：产生器g 依据某一未知( 但固定) 的概率分布p ( z ) 生成独立同分布的向 量卫zci f 在本文中假定疋为则上的紧域或流形训练器将这些向量作为输 入，并返回输出值y ycr ，这里v i i 练器根据条件分布函数p ( 引z ) 输出! ，的值我 们不知道训练器将向量z 的值转化为y 值的规则但是这个规则确实存在而且不发 生改变 学习机器观察n 个数据( 训练集) ( 。l ，y 1 ) ，( z 。，) ( 1 2 1 ) 该训练集包含了输入向量z 和训练器的响应值y 它是依据一个定义在z y 联合 概率分布函数弘( 。，彩= p ( ) p 例z ) 随机独立抽取的根据假设p ( z ，蓼) 是未知的但 是确定不变的在这个过程中学习机器构造一个规则。这个规则根据产生嚣产生 的具体向量值乩来预测训练器的响应值执学习的目的就是要对任何输入构造一 个与训练器响应适当的逼近 每当选择一个具有想要的性质的函数的问题出现时，我们应该考虑的一个模 型为：在所有可能的函数中要寻找一个以最好的可能方式满足给定的性质评判 标准的函数为了选择所能得到的对训练器响应晟好的逼近就要度量在给定输 a x 下训练器响应y 与学习机器给出的响应_ h ( z ) 之间的损失或差异f ( ”， 扛) ) 对于可溯空间( n ，e ) 上的任意概率测度肌用e 。表示关于p 的数学期望考虑 损失的数学期望值 洳，扎) = 蜘，联瑚审， 1 2 2 ) 3 - 湖北大学硕士学位论文 它就是风险泛函，也称为期望风险学习的目标就是：在联合概率分布函数“= p ( z ，! ，) 未知，所有可用信息都包含在训练集( 1 2 1 ) 式中的情形下在某一给定的 函数集h 上寻找函数( z ) ，使它在函数集7 - 1 上最小化风险泛函e 。f ( ，h ( z ) ) 其 中何称为假设空间，称为目标函数 若记，( z ，9 ) = f ( 9 ， ( z ) ) 。则在函数集州中寻找最小化q ( 玑j l ( z ) ) 的函数h 就 相应于在函数集，中寻找最小化e 。，的函数，o ，其中 ，= m ，) k ) 一z ( ，l ( z ) ，f ) ：h e - ) 称为损失函数集 因此，学习问题可以简单表述如下：设弘为定义在可测空间q 上的概率测度1 。 考虑函数集合，= f c x ，y ) lc = ，) 一f ( h ( z ) ，”) ：h 丸) 学习的目标是最小化风 险泛函 w = 厂m 朋毗，芦 其中概率测度p 未知。但给定了一组依据概率测度肛选取的独立同分布( i i d ) 的样 本( 1 2 1 ) 式 为了叙述方便本文在很多地方忽略其中蕴含的y 值函数类爿而只考虑定义 在可测空间q 上的一致有界的实值函数类，且径称，为假设空间不难证明在适 当的条件下这样的函数类总是对应着一个损失函数类吲5 为了避免对可测性问 题的分析，我们假定p 为q 上的b o r e l 测度，且对任意的u q ，p ( u = 0 这样。学 习问题就可以进一步简单表示为：已知一组( i i d ) 经验数据 i t ) 1 ，“n 在损失函数类，上最小化泛函 w = 似) 咖， 这里的n 中的点由点对( z ，掣) 构成而p 为联合概率测度p ( 。，v ) 4 ( 1 2 3 ) ( 1 2 4 ) 第一章引言 基于经验数据( 1 2 3 ) 最小化风险泛函( 1 2 4 ) 的问题是非常一般的特别是它 包括模式识别，回归估计等基本统计学问题 1 2 2 模式识别问题 模式识别问题是2 0 世纪5 睥代末正式提出来的本质上它可以描述如下： 训练器观察到所出现的事件并确定每个事件属于七类中的那一类；需要构造一个 学习机器该机器在观察了训练器的分类后能够以与训练器相同的方式近似地完 成分类工作 这种描述可以形式化地表示为：在一个由未知但确定的概率分布p ( 茁) 所 刻画的环境中事件随机独立地出现：训练器利用条件概率分布p ( 掣i o ) 。其 中! ， o ，l ，七一1 ( ! ，= p 指训练器将事件z 指派到p 类) 1 完成分类 本文考虑最简单的情形即二分类问题。其损失函数为 ，c 而们= - “订c 妒c z ，”，= 乏萋：i ： c - z s ， 其中7 ，咒为某- o ，1 ) 函数类 若记p = p ( ”i z ) p ( 为联合概率分布( 由上述可知其存在，未知) ，则损失函 数集为 芦= ，( 。，耖) l ( z ，掣) - _ + 1 f v 训 ( ( z ) ，) ：咒 模式识别问题就是要在 o ，1 函数类f 上最小化风险泛函 ( ，) = 1 ( ( z ) ，g ) d p ， ( 1 2 6 ) 其中概率分布p 未知，但给出独立同分布的样本点对( z 1 ，9 1 ) ，( ，9 。) 很显然，对于损失函数( 1 2 5 ) 泛函( 1 2 6 ) 确定了任何决策规则妒的分类错误 概率这样，最小化( 1 2 6 ) 就是最小化分类错误概率 由于模式识别问题处理最简单的损失函数所以它构成了最简单的学习问 题模式识别问题中的损失函数描述一个指示函数集。目标函数也属于一个指示 函数集 这是晟一般的情况，它包含了训练器用函数= ，( z ) 来分类事件，的情形 5 一 湖北大学硕士学位论文 1 - 2 3 回归估计问题 同样。设爿是欧氏空间r d 上的一个紧域或流形，空间y = r p ( z ) 为定义在z 上的一个概率分布对每一个z ，在y 上定义一个条件分布p ( z l ) 使y 的值的选取 是依据这一分布来实现的( 包含函数y = ，( z ) 的情形) 在这种情况下，存在一个联 合分布p ( z ，”) 。依据这一分布独立地随机生成经验数据点对( z 1 ，y 1 ) ，( $ 。，) 学习问题要求在未知概率侧度的情况下依据经验数据估计随机依赖关系，这 意味着要估计分布函数p ( l 。) 这是一个很难的问题因为它是不适定的1 6 ，7 一 然而。我们需要的经常不是关于函数联，k ) 的知识，而是确定它的一个特性就够 了，例如条件数学期望函数 巾) = _ 厂”咖( 咖) ( 1 2 7 ) 这一函数称为回归在函数集h 上估计这一函数的问题称为回归估计问题，其 中h 就是假设空间为此引入以下损失函数集 ，= ，( 训) 忙p ) 一b h ( z ) ) 2 ： h ) 相应的风险泛函为 e p ( ，) =- h ( z ) ) 2 d p ( z ，可) ，厂 ( 1 2 8 ) 该泛函给出了用危( z ) 代替所产生的损失的均值对于风险泛函( 1 2 8 ) ，有如下命 题： 命题1 1 对任意的，y 有 吼( ，) = j 厂( 吣) - r ( 瑚2 州z ) + 町2 ， ( 1 2 9 ) 其中砰= f ( y r ( z ) ) 2 d # c x ，) = ( r ) 证明由于 仆m ) - r ( z ) ) ( 巾) 一9 ) 舡( 咖) 】舡( 。) = 。 第一章引言 故有 吼( ，) = ( m ) 一巾) + 巾) 一9 ) 2 舡( 训) = ( m ) - r ( z ) ) 2 咖( z ) + ( 巾) 一”) 2 咖( 训) + 2 ( 坼) - r ( z ) ) 厂( 巾) 一) 中( 咖) 】舡( z ) = ( m ) r ( z ) ) 2 中( 卫) + 砰 显然，( 1 2 9 ) 的右边第一项给出了在度量空间l 2 ( p ( 。) ) 中用函数 ( 。) 代替回 归函数r ( o ) 所产生的误差的平方，而第二项与7 l ( z ) 无关因此命题1 1 表明。在所有 的函数h ：爿一y 中，回归函数具有最小可能的风险换言之。用回归函数代替未 知函数所产生的损失在度量空间l 2 ( 茁) ) 中是最小的e 。( r ) 给出了风险的一个 下界，它只与分布卢( z ，”) 有关因此，回归估计问题学习的目标就是在某一给定 的假设空间死中寻找回归函数r ( o ) 的一个好的逼近。而这可以逶过最小化风险泛 函耽( ，) 来实现 不难看出回归估计学习问题与模式识别学习问题的主要差别在于他们所采 用的损失函数不同，前者的假设空间为任意的实函数集而后者为指示函数集 1 3 基于经验数据最小化风险泛函的归纳原则 如前所述学习问题可以归结为：在未知概率测度“但已知一组( i i d ) 的经 验数据 ( x l ，9 1 ) ，一，( 铷，骱) 的情况下。在损失函数集芦中最小化风险泛函 ( 1 - 3 1 ) ( ，) = f f ( z ，9 ) 咖，户 ( 1 3 2 ) 遗憾的是由于定义风险的概率测度p 未知，直接最小化风险泛函吼( ，) 是不 可能的为此在空间q 中引入经验测度的概念对任意的u q 和定义在n 上的函 数集蛋用丸表示定义在g 上赋值泛函，即对任意的函数9 9 ，有屯( 9 ) = 9 p ) 我 7 湖北大学硕士学位论文 们用加表示支撑于n 中n 个点上的经验测度即有，p 。= ：l 钆 用弘。表示支撑于样本( 1 3 1 ) 上的经验测度对任意的，y ，考虑它的经验均 值 驯，) _ ：喜m 谳，只 ( 1 3 - 3 ) 称之为经验风险泛函这一泛函是以显式的形式定义的，因而易于被最小化 设，0 为芦上最小化风险泛函( 1 3 2 ) 的函数，而 为在，上最小化经验风险泛 函( 1 3 3 ) 的函数( 需要说明的是矗，厶的存在性的一个充分条件是函数集，是紧集 且( ，) 及e 。( ，) 在尸上连续，本文假定它们都是存在的i 9 o j ) 我们将函数厶作 为，0 的一个近似解风险最小化问题的这一原则称为经验风险最小化( e m p i r i c a l r i s km i n i m i z a t i o n ) ( 归纳) 原则，简称e r m 原则 对于模式识别问题，风险泛函为 e 。( ，) = l ( ，t ，( ( 。) ，) 6 啦， ( 1 3 4 ) 其中，= ，( z ，口) i ( z ，) 一1 v 辨( 扛) ，f ) ：竹) 咒为 o ，1 ) 函数类对应的经 验风险泛函为 ( ，) _ 去喜圯捌( 酬栅，f ( 1 3 5 ) 最小化经验泛函产生一个函数，该函数在训练数据上具有最小错分数 对于回归估计问题风险泛函为 ( 月= 厂( y 一) ) 2 审， 3 6 ) 其中，= ，( z ，y ) i ( z ，) 一国一危扛) ) 2 ：h 爿) ，咒为某一实值函数类对应的经 验风险泛函为 瓯。( ，) = 云1 n ( 坎一h ( 翰) ) 2 ，z ( 1 3 7 ) 8 第一章引言 在统计学中，最小化该泛函的方法称为最小二乘法 下面考虑厶的风险值e 。( ) ，由于 觋( 厶) = 陬( 厶) 一( 而) 】+ e ，( ，o ) ， ( 1 3 8 ) 记吼，( ，) = 瓯( ，) 一耳( ，o ) ，称之为，在，中的风险则e ，( 厶) 就可以分解为两部 分之和： 耳( 厶) = e p ，( 厶) + 屹( 兀) ( l 3 9 ) ( 1 3 9 ) 式的第二部分依赖于假设空间，而与样本无关，在很多文献中称之为。逼 近误差”【9 1 ”相应的，称第一部分为。样本误差”因此估计e 。( 厶) 的问题就分 解成分别估计逼近误差和样本误差的问题 本文将考虑样本误差 1 4 学习理论的基本问题 一致性与推广能力是学习理论要研究的两个最基本的问题一致性揭示学习 过程的可能性而推广能力表征了学习机器的有效性 1 4 1 学习过程的一致性与g l i v e n k o c a n t e l l i 类 经验风险最小化理论的的基本问题是描述经验风险最小化原则一致性的条 件下面是一致性的经典定义 定义1 1 对于函数集，和概率分布地如果下面两个序列依概率收敛于同一极 限： 觋( 厶) 毒僻i n f 吼( ，) ( 矗) 去落( ，) ( 1 4 1 ) 则称经验风险最小化原则的学习过程是一致的 抉句话说，如果经验风险最小化方法能够提供一个函数序列厶，厶只使得 期望风险和经验风险以概率都收敛于( 对于给定的函数集) 最小可能风险值则 - 9 湖北大学硕士学位论文 经验风险最小化方法是一致的( 1 4 1 ) 式的第一式表明，对于给定的函数集，所得 的风险值序列收敛于最小可能的风险：第二式表明。经验风险序列的极限估计出 风险的最小可能值 对于上面给出的一致性的经典定义如果函数集，中包含一个劣化函数，则 会出现平凡一致性的情况【1 2 1 因此，为了得到这样的一致性条件：它们仅仅依赖 于函数集的一般特性而不依赖于函数集中的特定函数，又有以下改进的非平凡一 致性的定义 定义1 2 对于函数集尸和概率分布“，如果对于这一函数集的任何非空子 集疋= ，：r ( f ) c ，f 研，c ( 一o 。，+ o 。) 使得收敛性 i 。n f 。e 一, 。( ，) 芒，c i n f 吼( ，) ( 1 - 4 2 ) 成立。则称经验风险最小化方法的学习过程是严格( 非平凡) 一致的 根据定义1 2 如果对于给定的函数集f 和所有的函数子集五，经验风险最小 化方法具有收敛性( 1 4 2 ) ，则这一学习过程是严格一致的，其中函数子集五是从 给定函数集中排出风险值小于c 的函数之后剩余的函数所构成的集合这样就排 除了平凡一致性的情况 确保一致性成立的一个充分条件是函数集，满足一致大数定理1 1 3 ，14 1 满足 一致大数定理的函数类称为g l i v e n k o c a n t e l l i 类我们用p r 表示无穷乘积测度p 。， 则g l i v e n k o - c a n t e l l i 类定义如下 定义1 3 设( q ，) 为一可测空间，为定义在q 上的函数类，a 为一测度族如 果对任意的e 0 。 。l i m 。p s u a p p r s u ps ，u 。，p i 耳f e 一f l e ) = 。 ( 1 4 3 ) 成立，则称函数类，为关于测度族a f l 向o l i v e n k o c a n t e l l i 类其中p 。为支撑于样本 的前m 个坐标的经验测度如果a 由( n ，) 上全体的概率测度组成，则称，为一 致g l i v e n k o c a n t e l l i 类 在本文中。g l i v e n k o c a n t e l l i 类简称为g c 类 1 0 第一章引言 1 4 2 学习机器的推广能力 一个好的学习机器要求在能较好的解释已知实例的同时还能对未来的现象 作出比较可靠的预测和判断，我们把这种能力称为学习机器的推广能力( 亦称推 广性) 推广性问题是学习的核心问题。同时也是关于自然科学和哲学的核心问 题现代对这一问题的研究始于2 0 t ! 纪前期k o l m o g o r o va n 在1 9 3 3 年提出了 概率论和统计学的公理体系，在这一体系下有两种不同的推理的数学模型：演绎 模型( 概率的理论) 和归纳模型( 统计的理论) 从那时起人们才把统计学看成是一 种推理的数学模型，其主要问题是给定观测( 数据 寻求推广( 感兴趣的函数) 。2 0 世 纪7 0 年代人们发现：对于归纳推理来说，有且仅有两种因素影响学习机器的推广 性他们分别是： 经验风险，它说明了被选中的函数在多大程度上刻画了观测 假设空间的容量( 或称复杂性) 它描述了从中选择解函数的函数集的多样 性如果函数集足够“大”。那么我们选中的函数可以充分好地适应观测样本( 即 经验风险可以充分小) 但是它对新样本预测的真实风险可能很大，我们把函数集 这种适应不同数据的能力称为它的容量 学习过程的一致性只是提供了学习的可能性，而没有提供任何关于学习效率 ( 最小化经验风险的函数厶到目标函数的收敛速率) 的任何信息有可能构造这 样的例子此时学习过程是一致的。但具有任意缓慢的收敛速率表现为学习效率 低。推广能力差 基本问题是：对于任何概率测度而言，存在着快的( 一般指具有指数界) 一 致收敛性渐进速率的条件是什么? 回答这个问题意味着描述一组条件。在这组条 件下，存在两个正常数g 和c ，使得对于充分大的n n ( e ，) 不等式 m , t e - p ap r 。 s u r e ：pi l e p ，一e m ，i e ) 0 ，0 0 。存在正常数