（基础数学专业论文）学习理论中的误差分析.pdf

中文摘要 捅要 学习问题就是利用经验数据从给定函数集寻找待求的函数依赖关系的问 题其核心问题之一就是分析处理学习问题的各种方法( 或算法) 的推广性能处 理学习问题常用方法之一就是基于所选函数的品质可以用风险泛函来评价这一 思路在这种情况下，从给定函数集i i i 选取函数就足基于经验数据最小化风险 泛函的问题而经验风险最小化归纳原则( 简称e r m 原则) 是用于解决基于经验 数据最小化风险泛函问题的主要归纳原则之一；虽然e r m 原则是学习理论中常 用的归纳原则，但是当函数集的容量很大时，e r m 原则问题的解通常是不适定 的于是，t i k h o n o v 等引入了正则化方法；又由于经验数据是独立的条件是非常强 的故本文基于独立和相依两利- 不同的数据，针对上述两利一不同方法( e r m 原则 和t i k h o n o v 正则化方法) 的学习机器的推广性能进行了研究，重点分析了混合相 依数据下e r m 原则和t i k h o n o v 正则化方法的学习机器的样本误差 由于在学习机器推广性能的研究中，函数集的容量是描述学习机器推广性能 界的一个重要因素而当一个函数集的容量是无限时，我们是不能用基于函数集 容量的界来分析学习机器的推广性能的因此，我们又对独立于函数集容量的算 法稳定的方法进行了研究本论义的主要上作及创新之处： ( 1 ) 通过对独立( 同分布) 数据下e r m 原则学习机器推广性能已有结论的研究， 我们引入了算法稳定的思想来对目标函数集进行“消噪”，得到了目标函数集的 一个子集再针对这个子集，我们得到了独立数据下e r m 原则学习机器推j “性能 的界 ( 2 ) 由于经验数据是独立的条件，无论从理论上，还是实际应用中都是非常强 的我们把独立数据下e r m 原则学习机器推广性能的结论推广到相依数据情况 下，研究了混合相依数据下e r m 原则学习机器的推广性能，得到了q 混合和混 合两种不同数据下e r m 原则学习机器推广性能的界 ( 3 ) 我们研究了混合相依数据下t i k h o n o v 正则化方法学习机器的推广性能， 分别得到了q 混合和p 一混合两种不同数据下t i k h o n o v 正则化方法的学习机器的 推广性能的界 ( 4 ) 在独立于函数集奔量的理论框架下，我们应用算法稳定的方法研究了分 类学习算法的推广性能，得到了逐点假设稳定条件下基于留一经验误差估计的推 广误差的界和留一稳定条件下基于留一经验误差估计的相对误差的界 湖北大学博士学位论文 关键词：学习理论；推广性能；混合序列；经验风险；期望风险；e r m 原则； t i l d l o n o v 正则化方法：算法稳定 i i 英文摘要 a bs t r a c t l e a r n i n gp r o b l e mi st h ep 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 ef r o mag i v e n f u n c t i o ns e to nt h eb a s i so fe m p i r i c a ld a t a t h es t u d yo ft h eg e n e r a l i z a t i o na b i l i t yo f v a r i o u sa p p r o a c h e st ot h el e a r n i n gp r o b l e mi so n eo ft h em a i ns u b j e c t so fl e a r n i n gp r o b - l e m t h ec o m m o n a p p r o a c ht ot h el e a r n i n gp r o b l e mi sb a s e do nt h ei d e at h a tt h eq u a l i t y o ft h ec h o s e nf u n c t i o nc a nb ee v a l u a t e db yar i s kf u n c t i o n a l i nt h i sc a s et h ec h o i c eo f t h ea p p r o x i m a t i n gf u n c t i o nf r o mag i v e ns e to ff u n c t i o n si sap r o b l e mo fm i n i m i z i n gt h e r i s kf u n c t i o n a lo nt h eb a s i so fe m p i r i c a ld a t a t h ee m p i r i c a lr i s km i n i m i z a t i o np r i n c i - p i e ( e r m ) i so n eo fa p p r o a c h e st os o l v et h ep r o b l e mo fm i n i m i z i n gt h er i s kf u n c t i o n a l o nt h eb a s i so f e m p i r i c a ld a t a a l t h o u g ht h ee m p i r i c a lr i s km i n i m i z a t i o np r i n c i p l ei sa c o m m o nm e t h o di nl e a r n i n gt h e o r y , t h es o l u t i o no ft h ep r o b l e mo ft h ee m p i r i c a lr i s k m i n i m i z a t i o np r i n c i p l ei su s u a li l l p o s e d t h e nt h er e g u l a r i z a t i o nm e t h o di si n t r o d u c e d b yt i k h o n o v s i n c et h ec o n d i t i o nt h a tt h ee m p i r i c a ld a t ai si i d i ss t r o n g ，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 na b i l i t yo ft h ee m p i r i c a lr i s km i n i m i z a t i o np r i n c i p l ea n dt h e t i k h o n o vr e g u l a r i z a t i o nm e t h o do nt h eb a s i so ft w ok i n d so fe m p i r i c a ld a t a h o w e v e r , w h e nt h ec a p a c i t i e so ff u n c t i o ns e ti si n f i n i t e ，w ec a nn o tu s et h eb o u n d so nt h eg e n e r - a l i z a t i o np e r f o r m a n c et oa n a l y s et h eg e n e r a l i z a t i o na b i l i t yo fl e a r n i n gm a c h i n e s ow e a l s oc o n s i d e rt h ea p p r o a c ho fa l g o r i t h ms t a b i l i t y t h em a i nc o n t e n t sa n dc o n t r i b u t i o n s o ft h i sd i s s e r t a t i o na l ea sf o l l o w s ： ( 1 ) t os 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 ee m p i r i c a lr i s km i n i m i z a t i o n p r i n c i p l eu n d e rt h ec o n d i t i o no fi i d e m p i r i c a ld a t a ，w eu s et h ei d e ao fa l g o r i t h m s t a b i l i t yt oe l i m i n a t et h en o i s eo ft h eo b j e c t i v ef u n c t i o ns e t t h e nw eo b t a i nas u b s e to f t h eo b j e c t i v ef u n c t i o ns e ta n de s t a b l i s ht h eb o u n d so nt h eg e n e r a l i z a t i o np e r f o r m a n c e o fl e a r n i n gm a c h i n eu n d e rt h ec o n d i t i o no fi i d e m p i r i c a ld a t af o rt h i ss u b s e t ( 2 ) s i n c et h ec o n d i t i o no fi i d i ss t r o n gf r o mb o t ht h e o r ya n da p p l i c a t i o n ，w e e x t e n dt h er e s u l t so ft h eg e n e r a l i z a t i o na b i l i t yo fl e a r n i gm a c h i n eu n d e rt h ec o n d i t i o n o fi i d e m p i r i c a ld a t at ot h ec a s eo fd e p e n d e n te m p i r i c a ld a t a 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 ee m p i r i c a lr i s km i n i m i z a t i o np r i n c i p l eu n d e rt h ec o n d i t i o no f t h em i x i n gd e p e n d e n te m p i r i c a ld a t aa n do b t a i nt h eb o u n d so nt 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 ee m p i r i c a lr i s km i n i m i z a t i o np r i n c i p l eu n d e rt h ec o n d i t i o no fo l m i x i n g ， 8 一m i x i n gr e s p e c t i v e l y ( 3 ) w ea l s os 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 et i k h o n o vr e g u l a l i z a t i o n m e t h o du n d e rt h ec o n d i t i o no ft h em i x i n gd e p e n d e n te m p i r i c a ld a t a w ee s t a b l i s ht h e 湖北大学博士学位论文 b o u n d so nt 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 et i k h o n o vr e g u l a r i z a t i o nm e t h o du n d e r t h ec o n d i t i o no f o m i x i n g ，p m i x i n gr e s p e c t i v e l y ( 4 ) 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 fc l a s s i f i c a t i o nl e a r n i n ga l g o r i t h m b yu s i n gt h em e t h o do fa l g o r i t h ms t a b i l i t y , w h i c hi si n d e p e n d e n tt ot h et h e o r yo ft h e c a p a c i t i e so ff u n c t i o ns e t w ee s t a b l i s ht h eb o u n do nt h eg e n e r a l i z a t i o ne r r o rb a s e do n l e a v e 。o n e 。o u te m p i r i c a le s t i m a t o ru n d e rt h ec o n d i t i o no fp o i n t w i s eh y p o t h e s i ss t a b i l i t y a n dt 1 1 eb o u n d so nt l l er e l a t i v ee r r o rb a s e do nl e a v e o n e o u te m p i r i c a le s t i m a t o ru n d e r t h ec o n d i t i o no fl e a v e - o n e o u ts t a b i l i t y k e yw o r d s ：l e a r n i n gt h e o r y ；g e n e r a l i z a t i o np e r f o r m a n c e ；m i x i n gs e q u e n c e ；e m p i r i c a lr i s k ；e x p e c t e dr i s k ；t h ee m p i r i c a lr i s km i n i m i z a t i o np r i n c i p l e ；t h et i k h o n o v r e g u l a r i z a t i o nm e t h o d ；a l g o r i t h ms t a b i l i t y 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 论文作者签名：却到 签名口期：弘日年月，d 日 f 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学 校可以允许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢 利为目的的前提下，学校可以公开学位论文的部分或全部内容。( 保密论文在 解密后遵守此规定) 论文作者签名： 却斌 签名日期：弘刁年f l f oh 导师签名： 柱惑 签名日期：彳降易月，2 日 第一章绪论 第一章绪论 1 1 学习问题研究的四个阶段 人是如何学习的? 为什么人具有学习能力? 学习的本质是什么? 这些问题 是哲学家、心理学家、语言学家、计算机专家、数学家等讨论了多年的问题通 过对学习过程的研究，人们发现，人的智慧中一个很重要的方而就是从实例学习 的能力即通过对已知事实的分析后总结规律，预测不能直接观测的事实在这种 学习中，重要的是要能够举一反三，即利用学习得到的规律，不但可以较好的解释 已知的实例，而且能够对未来的或无法观测的现象做出正确的预测和判断我们 把这种能力叫做推广能力( 或泛化能力、推广性能) 在人们对机器智能的研究中，希望能够用机器( 主要是计算机) 来模拟人的这 利- 学习能力，这就是所谓的基丁数据( 或样本) 的机器学习问题机器学习的目的 是，在机器通过对( 经验) 数据的学习后，设计某种( 某些) 方法( 或算法) ，使之能够通 过对已知数据的学习，找到数据内在的相互依赖关系，对数据间的函数依赖关系 进行逼近，从而对未知数据进行预测或对其性质进行判断同样，这里我们最关心 的仍然是推广能力问题 基于数据的机器学习问题( 以下简称学习问题) 是智能技术中十分重要的一 个方面它主要研究如何从一些观测数据出发得出尚刁i 能通过原理分析得到的规 律，利用这些规律去分析客观对象，对未来的或无法观测的数据进行预测显示世 界中大量存在的、尚不能准确认识的、但却可以进行预测的现象基于数据的机 器学习问题从现代科学、技术到社会、经济等各领域中都有着十分重要的应用 学习问题的研究历史可以分为四个阶段，它们分别以下面四个重要事件为标 志： ( 1 ) 第一个学习机器模型的创立； ( 2 ) 学习理论基础的创立； ( 3 ) 神经网络的创立； ( 4 ) 神经网络替代方法的创立 在不同的历史阶段有不同的研究主题和重点，所有这些研究共同勾画出了人 们对机器学习进行探索的一幅复杂的和充满矛盾的图i | i i 湖北大学博士学位论文 第一个学习机器模型的创立 1 9 6 2 年，r o s e n b l a r 提出了第一个学习机器的模型，称为感知器，这标志着人 们对学习过程进行数学研究的真正开始f l j i 从概念上讲，感知器的思想并不是新 的但是，r o s e n b l a t t 做了一件不寻常的事，就是把这个模型表现为一个计算机程 序，并通过简单的试验说明这个模型能够被推广。感知器模型在被用来解决模式 识别问题时，在最简单情况下，就是用给定的例子来构造一个把两类数据分开的 规则 1 9 6 4 年，n o v i k o f f 证明了感知器能够将训练样本集分开的定理，这一定理的证 明又标志着人们对学刊过程进行理论研究的开始【2 】2 定理指出。如果 ( 1 ) 训练向量z 的模以某个常数r 为界( i z i 兄) ； ( 2 ) 训练数据能够以间隔p 被分开：s u p , m i n 玑( z l u ) p ； ( 3 ) 对感知器进行足够多次训练过程，则在最多n i 譬1 次修正以后可以构 造出将这些训练数据分开的超平面这一定理在创建学习理论中起了- 分重要的 作用它在一定意义上将学习机器具有推广性能的原因与最小训练样本集上错误 数的原则联系起来 关于感知器的实验广为流传后，人们很快又提出了一些其它类型的学习机 器，如：w i d r o w 构造的m a d a l i n e 自适应学习机器，s t e i n b u c h 提出的学习矩阵等与 感知器不同的是，这些学习机器从一开始就是被作为解决实际问题的丁具来研究 的，而没有被看作是学习问题的一般模型 学习理论基础的创立 存2 0 世纪6 0 年代至7 0 年代，数学的各个不同的分支产生了一些开创性的新理 论：一是统计学习理论的基本思想已经得到了很大的发展对于指示函数集，已 经提出t v c 熵和v c 维的概割3 - 5 】，它是统计学习理论中的核心概念利用这个概 念，发现了泛函卒问的大数定律，从而研究了它与学习过程的联系，得到了关于 一致收敛速率的非渐进界的主要结论这些结论使得新的归纳原则( 结构风险最 小化原则，s 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 e ，简称s r m ) 成为可能，从而完成了 模式识别的学习理论；二是t i k h o n o v1 6 1 ，i v a n o v r l 和p h i l l i p si s 发现了解决不适定 问题的正则化方法：三是p a r z e n1 9 1 ，r o s e n b l a t t 1 0 】和c h e n b o v1 1 1 】发现的非参数统计 学；四是s o l o m o n o f f l l 2 1 ，k o l m o g o r o v 1 3 j 和c h a i t i n 1 4 】分别提出了算法复杂度的思 想这些发现开创了研究推理问题的信息论方法，成为人们对学习过程的研究取 得新进展的重要基础 2 第一章绪论 神经网络的创立 在19 8 6 年，几个学者( l e c u n 【1 5 】；r u m e l h a r t ，h i n t o n 和w i l l i a m s 1 6 1 ) 独立地提 出了同时构造感知器所有神经元的向量系数的方法，就是用所谓的向后传播的方 法这一方法的思想是很简单的，它不是用m c c u l l o c h p i t t s 的神经元模型。而是采 用了一种稍加修改的模型，在其中把原来的不连续函数s 9 n x ) 一6 ) 替换为连 续的所谓s i g m o i d 函数： 矽= s ( u x ) 一6 ) ， 这里，s ( u ) 是一个满足性质 s ( 一) = 一i ，s ( + o o ) = 1 的单调函数这样，神经元合成的就是一个连续函数神经元，它对于任意固定的向 量x ，都存在对所有神经元的所有系数的梯度在1 9 8 6 年找到了计算这个梯度的方 法利用计算出的梯度，人们可以应用任何基于梯度的方法构造对预期函数的逼 近 向后传播的方法的发现可以看作是感知器的第二次诞生，具有多个可调节神 经元的感知器，与只有单个可调节神经元、但具有同样多的自由参数的感知器相 比，是否具有更好的推广性能，人们对于这一点实际上并不能断定，但是尽管如 此，由于实验规模的原因，科学界还是对这种新方法表现出很大的热情 神经网络替代方法的创立 在神经网络的思想产生后的近1 0 年里，神经网络的研究没有从本质卜推进对 学习过程本质的认识【蚓神经网络的研究也遇到一些重要的困难比如。如何确 定网络结构的问题、过学习与欠学习问题、局部极小点问题等等在这种情况 下，人们更多的注意力放在了对神经网络替代方法的研究上比如，人们用了很大 的精力进行了对径向基函数模型的研究，神经网络又被重新叫做多层感知器从 本质上研究机器学习问题的统计学习理论又开始吸引更多学者的注意和重视而 传统的统计学所研究的主要是渐近理论，即当样本趋于无穷多时的统计性质而 在现实的学习问题中，我们所面对的样本通常是有限的因此，统计学在解决学习 问题中起着基础性的作用，即仍以样本数日无穷多为假设来推导各种算法，希望 这样得到的算法在样本较少时也能有较好的( 至少是可接受的) 表现 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 是v a p n i k 等人早在2 0 世纪6 0 年代就 3 湖北大学博士学位论文 开始研究的有限样本下的学习问题，而直至, j 9 0 年代中期才形成的学习领域中一个 较为完善的理论体系【3 , 5 , 1 8 统计学习理论可以说是目前针对小样本统计估计和 预测学习的最佳理论它从理论上较系统地研究了经验风险最小化归纳原则成立 的条件，有限样本下经验风险，与期望风险的关系及如何利用这些理论找到新的学 习原则和方法等问题1 9 9 2 年一1 9 9 5 年，在统计学习理论的基础上发展出了一种 新的模式识别方法一支持向量机( s u p p o av e c t o rm a c h i n e ，简称s v m ) 在解决小样 本、非线性及高维模式识别问题中表现山许多特有的优势，并能够推广应用到函 数拟合等其它机器学习问题中【3 5 】虽然统计学习理论和支持向量机方法中尚有 很多问题需要进一步研究，但是很多学者认为。它们正在成为机器学习领域新的 研究热点，并将推动机器学y - - j 坪论和技术有重大的发展【1 9 - 2 1 】 机器学习的理论研究，是目前同际上人工智能、计算机科学、数学等学科中 最热门的研究领域之一许多学者，如m i t 大学的人工智能学者p o g g i o ，s t a n f o r d 大 学的统计学家h a s t i e ，t i b s h i r a n i ，俄罗斯学者、支持向量机的发明者v a p n i k ，数 学f i e l d s 奖的获得者s m a l e 等，纷纷开展学习理论的研究，在本世纪初掀起了机器 学习理论研究的新高潮1 2 2 】2 2 由于这一理论的高度复杂性和极强的应用前景，正吸 引越来越多的学者从事这一领域的研究虽然这一领域的研究在理论卜和应用上 都取得了很大进展，但是，学习理论仍是极具活力的研究领域，尚有许多有待进一 步研究的理论与应用问题特别是，越来越多的人们认识到研究机器学习数学基 础的重要性与必要性学习理论的数学基础已成为机器学习研究领域的重要研究 课题 1 2 学习问题的表示 学习问题可以看作是利用有限数量的( 经验) 数据来寻找待求的函数依赖关 系的问题 1 2 - 1 学习问题的一般模型 我们片】三个部分来描述从数据学习的一般模型( 图1 1 ) ： ( 1 ) 产生器( g e n e r a t o r , g ) ，它确定了训练器和学习机器工作的环境最简单的 环境是：产生器依据某一未知( 但固定) 的概率分布函数f ( x ) 独立同分布地产生向 量x r n ( 2 ) 训练器( s u p e r v i s o r , s ) ，训练器对每个输入向量x 返同一个输出值y ，产生输 4 第一章绪论 图1 1从实例学习的模型 出的根据是同样固定但未知的条件分布函数f ( y l x ) 这是一般的情况。其中包括 训练器采用某一函数y = 厂( x ) 的情况 ( 3 ) 学习机器( l e a r n i n gm a c h i n e ，l m ) ，学习机器能实现一定的函数集f ( x ，口) ， 0 a ，其中a 是参数集合这里，参数0 a 并不一定必须是向量，它们可以是任 意的抽象参数，因此，我们交际上考虑的是任意的函数集 从数据学习的一般模型可知，在学习过程中。学习机器观察数据对( 训练样 本) ( x ，可) 在训练之后，学习机器必须对任意的输入i 给出输出可学习的目标是 能够给出输出可，使之接近训练器的响应y 因此，学习问题就是从给定的函数 集f ( x ，p ) ，0 人中选择出能最好地逼近训练器响应的函数这种选择是基于训练 样本集的，训练样本集是由根据联合分布f ( x ，y ) = f ( x ) f ( yj x ) 抽取出的m 个独 立同分布( i i d ) 的观测 ( i l ，! ，1 ) ，( x 2 ，仇) ，( x m ，) ( 1 2 1 ) 所组成 1 2 2 风险最小化问题及损失函数 为了选择所能得到的对训练器响应最好的逼近，就要度量在给定输入x 下i j i i 练器响应可与学习机器给出的响应，( x ，p ) 之间的损失或差异c ( y ，f ( x ，口) ) 考虑损 失的数学期望值 兄( 厂( x ，口) ) = c ( y ，( x ，秽) ) d f ( x ，y ) ( 1 2 2 ) 它就是真实误差、风险泛函或期望风险学习的目标就是，在联合概率分布函 5 湖北大学博士学位论文 数f ( x ，y ) 未知，所有可用的信息都包含在训练样本集( 1 2 1 ) 式的情况下，寻找函 数f ( x ，日) ，使它最小化风险泛函r ( ，( x ，p ) ) 在这里，不同的研究对象对应着不同的损失函数 2 3 , 2 4 ，常见的损失函数如下： 一范数软间隔s v m 的损失函数：c ( 可，( x ，伊) ) = ( 1 一y f ( x ，p ) ) + g 范数软问隔s v m 的损失函数( 1 e 卜_ o ( 1 3 11 ) 9 湖北大学博士学位论文 和 p r ( f o m ) 一哪；n f r c f o ) i j o ， ( 1 3 1 2 ) 则e 蹦原则是一致的( 1 3 1 1 ) 式保证了所达到的风险收敛于最好的可能值，而 式( 1 3 1 2 ) 保证了可以在经验风险的取值基础上估计最小可能的风险这里，我 们日的是给出e r m 原则一致性的条件，使它们依赖于函数集的一般性质，而不 依赖于函数集l f l 特定的函数则我们必须刨出平凡一致性的情况( 对于平凡一致 性的例子可参见文献1 3 ，5 1 ) 于是，有下面的对于模式识别和回归函数估计问题 的e r m 原则( 严格) 一致性的定义 定义1 1 对于函数集e ( z ，f o ) ，口a 和概率分布函数f ( z ) ，如果对于这一函数 集的任何非空子集a ( c ) ，c ( 二o o ，o o ) a ( c ) = p ：( z ，知) d f ( z ) c ) 使得对v e 0 ，当m o o ， 尸他如忍唧( 办) 一刚i n ( c ) fr ( f o ) l ) 一o ( 1 3 1 3 ) 成立，则我们称e r m 原则是( 严格) 一致的 我们注意到，如果满足( 1 3 1 1 ) 式和( 1 3 1 2 ) 式的两个条件，则e l 蝴原则是一致 的在定义1 1 下，v a p n i k 经证明，我们只需要利用( 1 3 1 1 ) 式和( 1 3 1 2 ) 式中的一 个条件，另一个条件会自动满足即定义1 1 是e r m 原则严格( 非平凡) 一致的定义 1 3 2 经验过程 e r m 原则一致性分析在本质上是与两种经验过程的收敛性分析相联系的 设分布函数f ( z ) 定义在卒问z 上，e ( z ，f o ) ，p a 为一个可测函数集，又设 为一个独立同分布的样本序列 z l ，z 2 ，z m ， 1 0 一 第一章绪论 考虑随机变量序列 卜s u p l 心川d f 一去姜啦州仇乩2 ， m 3 m ， 式( 1 3 1 4 ) 是依赖于分布函数f ( z ) 和函数集( 名，i o ) ，0 a 的随机变量序列，我们称 它为双边经验过程 下面我们描述一组条件，使得在这组条件下，上述经验过程依概率收敛于零 即对于垤 0 ，当m 叫。o 时 p ( s xl 如川蜊一熹喜啦川l e ) 一。 3 m ， 我们称上述关系式为在给定的函数集上均值到数学期望的一致收敛性，简称为一 致收敛性 与经验过程p 一起，我们考虑由随机变量序列给出的单边经验过程 其中 时 弘( 溜驰删删一去喜酝删) + ，m _ 1 ，2 ，( 1 3 舶) c 乱，+ = 苫： ：三： 于是，与一致收敛性相对应的还有一致单边收敛性即对于垤 0 ，当m p k ( 粤c z , o ) d f ( z ) - 鬲1 ；m 啦删) e 一。 3 朋， 我们称上述关系式为在给定的函数集上均值到数学期望的一致单边收敛性，简称 为一致单边收敛性 湖北大学博士学位论文 1 3 3 学习理论的关键定理 如果函数集e ( z ，s o ) ，0 人中只包含一个元素，由大数定律，随机变量序 列f m ( ( 1 3 1 4 ) 式) 总是依概率收敛到零对于函数集e ( z ，f o ) ，0 人中包含有限 个( 女f l n 个) 元素的情况也是很容易的，我们可以把大数定律推广到维向量空 间中而得到解决而当函数集e ( z ，s o ) ，0 人中包含无限多个元素时，与有限个 元素情况不同，随机变量序列m 就不一定收敛到零，这时的问题就是：在函数 集e ( z ，f o ) ，护a 和分布函数f ( 2 ) 的什么特性下，随机变量序列m 依概率收敛到 零，这种情况下，我们称为大数定律在函数卒问中成立，或在给定的函数集卜存在 均值到期望的一致( 双边) 收敛性 v a p n i k 已经证明了学习理论的关键定理( 或等价性的定理) 即证明了一致单 边收敛性不仅是e r m 原则，致性的充分条什，而且是它的必要条件 等价- 眭定理设存在常数a 和a ，使得对于函数集z ( z ，s o ) ，0 a 中的所有函数 和给定的分布函数f ( z ) ，有下面不等式成立： n 粤( z ，如) d f ( z ) a ，p a 则下面两种表达方式是等价的： ( 1 ) 对于给定的分布函数f ( z ) ，e r m 原则在函数集e ( z ，s o ) ，0 a 上是严格一 致的 ( 2 ) 对于给定的分布函数f ( z ) ，在函数集e ( z ，后) ，0 a 上出现均值到数学期 望的一致单边收敛性 这一定理的表述是针对某固定分布函数f ( 名) 而言的然而，学习理论的丰 要兴趣是找到一组条件，使得e r m 原则对于分布函数集合中任何分布函数都是 一致的于是又有下面的等价性定理的推论 等价性定理的推论假设存在常数a 和a ，使得对于函数集e ( z ，s o ) ，0 a 中的 所有函数和集合p 中的分布函数f ( z ) ，有下面不等式成立： ， o ( z ，f o ) d f ( z ) a ，0 a ，r ( z ) p ， 则下面两种表达方式是等价的： 1 2 第一章绪论 ( 1 ) 对于集合p 中的分布函数，e r m 原则在函数集粤( z ，知) ，口a 上是严格一 致的 ( 2 ) 对于集合p 中任何分布函数，在函数集粤( z ，s o ) ，伊人上出现均值到数学期 望的一致单边收敛性 于是，学习理论的关键定理将e r m 原则一致性问题转化为均值一致单边收 敛于数学期望的存在性问题从概念上讲，这个定理足十分重要的，因为它指出 了e r m 原则一致性的条件是必要的( 和充分的) 取决于函数集中“最坏”的函数 的也就是说，根据这一定理，对e r m 原则的任何分析都必须是“最坏情况的分 析” 由上面的讨论可知，学习理论的关键定理定性地描述了e r m 原则除此之外， 我们还应定量地对e r m 原则进行描述对于模式识别问题( 回归函数估计问题也 是类似) ，即描述最小化经验风险的函数的测试错误概率的界为此，我们要估计 出两个因子：一个是在给定数据上最小化经验风险的函数的错误概率：另一个是 该错误概率与给定函数集上最小可能值之间的接近程度这些研究所得到的结论 刻画了采用e r m 原则的学习机器的推广能力 1 3 4 学习理论的四个部分 学习理论需要研究的是下面四个问题： ( 1 ) 一个基于e r m 原则的学习过程具有一致性的条件是什么7 ( 2 ) 这个学习过程收敛的速度有多快? ( 3 ) 如何控制这个学习过程的收敛速度( 或推广能力) ? ( 4 ) 怎样构造能够控制推广能力的算法? 对于这四个问题的回答构成了学习理论的四个部分： ( 1 ) 学习过程一致性的理论这一部分学习理论的目的是给出学习过程概念 模型的完整描述，即找出学习过程一致性的充要条件 ( 2 ) 学习过程收敛速度的非渐近理论这一部分学习理论致力于得到描述学 习机器推广性能的非渐近界 ( 3 ) 控制学习过程的推广能力的理论推广能力的界将被用于发展新的归纳 原则，该原则对于给定的有限观测数据能得到学习问题的最佳解 ( 4 ) 构造学习算法的理论 1 3 湖北大学博士学位论文 在这四个部分中，学习过程一致性的理论和学习过程收敛速度的非渐近理论 是基础在本文中，我们的工作主要是在这两部分展开的，这将在后面的章节中进 行 1 4 正则化方法 在学习理论中，另一个讨论较多的算法( 或原则、方法) 是正则化方法这是 因为当给定的目标函数集的容量很人时，e r m 原则( 1 3 9 ) 式的解通常是不适定 的【捌于是t i k h o n o v 等人提出了解决不适定问题的方法：一种方法是i v a n o v 提出 的拟解的方法f 7 】；另一种是t i k h o n o v 提出的正则化方法1 6 1 这两种方法都对函数集 的容量进行了控制，即这两种方法都执行了结构风险最小化原则 1 4 1 不适定问题 在2 0 世纪3 0 年代，当f i s h e r 提出他的理论体系时，不适定问题的概念还没有 发展起来，这是现代应用分析理论r f l 最重要的概念之一这一概念主要足在2 0 世 纪6 0 年代发展起来的不适定问题理论中的主要发现是这样一个事实，即存在很 广泛的一类问题，它们的形式化的解存在，但却不能用有限的资源( 计算资源和信 息资源) 得到如事件模型的辨识问题属于不适定问题这是在快速计算机诞生 的2 0 世纪6 0 年代被发现的，人们发现，f i s h e r 的应用统计学对于解决高维问题来 说不是一个合适的工具，因为它存在“维数灾难”问题 不适定问题的数学语言表述为：对于算子方程 a f ( t ) = f ( z ) ， ( 1 4 1 8 ) 如果方程右端f ( z ) f ( z ，叩) 发生微小变化，只会引起解的微小变化，即，如果对 任意e ，存在6 ( ) ，使得只要刁i 等式 p 励( f ( z ，叩) ，f ( z ，0 2 ) ) 6 ( ) 成立，不等式 f ( t f ( t ，玑) ) e- ( ，7 7 1 ) ， ，玑) ) e 一定成立，我们称算子方程( 1 4 1 8 ) 式的解是稳定的其中e 1 和易表示距离分别定 1 4 第一章绪论 义在度量空间e 1 和岛中，算子方程( 1 4 1 8 ) 式将空间e 1 中的函数映射到空间岛中 的函数 如果方程( 1 4 1 8 ) 式的解是： ( 1 ) 存在的 ( 2 ) 唯一的 ( 3 ) 稳定的 我们称解算子方程( 1 4 1 8 ) 式的问题在h a d a m a r d 意义下是适定的1 3 1 】如果方 程的解至少不满足上面提到的3 个条件之一，则解算子方程的问题就是不适定的 在学习理论中，我们通常考虑算子方程的解存在、唯，但不稳定的这类不适定 问题 1 4 2 解不适定问题的方法 在1 9 6 3 年，t i k h o n o v 等就提出了解决不适定问题的方法一正则化方法【3 2 一矧 假设要解m 到的连续一对一映射算子a 定义的算子方程 a f = f ( 1 4 1 9 ) 并假设方程( 1 4 1 9 ) 式的解存在 考察下半连续的泛函w ( ，) ，我们称它为正则项，它具有下j 9 i j 3 条性质： ( 1 ) 算子方程的解属于泛函( ，) 的定义域d ( ) ( 2 ) 在定义域上，泛函w ( ，) 取非负实数值 ( 3 ) 所有集合 m c = 厂：( ，) c ) ，c 0 都是紧的 正则化的思想是将最小化某一泛函的一个元素作为方程( 1 4 1 9 ) 式的解，该 泛函不是泛函p = p 2 ( a f ，f ) ，而是一个改进的泛函 r ( ，f ) = p 2 2 ( a f ，f ) + 7 w ( ，) ，d ( ) ， ( 1 4 2 0 ) 其中正则化参数，y 0 t i k h o n o v 已经证明了最小化泛函( 1 4 2 0 ) 式的问题 1 5 湖北大学博士学位论文 是稳定的，即对于相邻函数f 和r ( 其中他( e r ) 6 ) ，对应存在着最小化泛 函q ( ，j f l ) 和r ( ，乃) 的相邻元素，一r 和眉特别地，在h i l b e r t 空间中，对于线性算 子a ，我们可以选择泛函w ( 厂) 等于i l f l l 2 最常见的两种正则化方法是t i k h o n o v 正则化方法和i v a n o v 正则化方法 假设q ：，一r + 是定义在函数集合尸= 如，0 人) 上的一个惩罚泛函，于 是。l v a n o v 正则化方法的定义为 厶，e2a r g r a 口a i n 尼m p ( 厶) 8 t f l ( f e ) c ，( 1 4 2 1 ) 其中c 是一个大丁零的常数 t i k h o n o v 正则化方法的定义为 知，a = 盯g 惑 冗。m p ( 如) + a q ( 如) ) ， ( 1 4 2 2 ) 其中a 是一个大于零的常数 ( 1 4 ，2 1 ) 式和( 1 4 2 2 ) 式中的函数q ( 办) 被