（应用数学专业论文）基于随机集样本的统计学习理论基础.pdf

摘要 摘要 基于随机样本的统计学习理论被认为是目前关于小样本统计学习的最佳理论，并己 成为继神经网络之后机器学习领域新的研究热点。但是，该理论难以处理现实世界中客 观存在的基于随机集样本的小样本统计学习问题。本文讨论了基于随机集样本的统计学 习理论，首先讨论了随机集的定义及其分布函数等性质，并给出了基于m 维随机变量的 大数定律等一些重要的不等式；然后给出了经验风险最小化原则( e r m ) 的严格一致性 的定义，并证明了基于随机集样本的关键定理；最后讨论了基于随机集样本的一致收敛 速率的界和v c 维理论，为系统建立基于随机集样本的统计学习理论奠定了理论基础。 关键词随机集关键定理一致收敛速率的界v c 维 a b s t r a c t a b s t r a c t 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 ) b a s e do nr a n d o ms a m p l e si sc o n s i d e r e da tp r e s e n ta s o n eo ft h ef u n d a m e n t a lt h e o r i e sa b o u ts m a l ls a m p l e ss t a t i s t i c a ll e a r n i n g i th a sb e c o m ea n o v e la n di m p o r t a n tf i e l do fm a c h i n el e a r n i n ga l o n gw i t ho t h e rc o n c e p t sa n da r c h i t e c t u r e s s u c ha sn e u r a ln e t w o r k s h o w e v e r , t h et h e o r yh a r d l yh a n d l e ss t a t i s t i c a ll e a r n i n gp r o b l e m sf o r s a m p l e st h a ti n v o l v er a n d o ms e ts a m p l e s i nt h i ss t u d y , w ed i s c u s ss l tb a s e do nr a n d o ms e t s a m p l e s f i r s t l y , w ed i s c u s st h ed e f i n i t i o n so fr a n d o ms e t sa n dt h ed i s t r i b u t i o nf u n c t i o no f r a n d o ms e t sw h i l es o m ep r o p e r t i e sa r eg i v e n ，a n di n t r o d u c eac e r t a i nl a wo fl a r g en u m b e r sf o r md i m e n s i o nr a n d o ms a m p l e sw h i l es o m ei m p o r t a n ti n e q u a l i t i e sa r eg i v e n s e c o n d l y , w e p r e s e n tan o t i o no ft h es t r i c tc o n s i s t e n c yo ft h ep r i n c i p l eo fe 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 ) o nr a n d o ms e ts a m p l e s ，a n da f t e r w a r d sf o r m u l a t ea n dp r o v et h ek e yt h e o r e m f i n a l l y , w e d i s c u s st h eb o u n d so nt h er a t eo fu n i f o r mc o n v e r g e n c eo fs t a t i s t i c a ll e a m i n gt h e o r yb a s e d o nr a n d o ms e ts a m p l e sa n dv cd i m e n s i o nt h e o r y , w h i c hb e c o m ec o m e r s t o n e so ft h e t h e o r e t i c a lf u n d a m e n t a l so f t h es l tf o rr a n d o ms e ts a m p l e s k e y w o r d s r a n d o ms e t s k e yt h e o r e m b o u n d so nt h er a t eo fu n i f o r mc o n v e r g e n c ev c d i m e n s i o n 河北大学 学位论文独创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书所 使用过的材科。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了致谢。 作者签名： 盈：兰缓 日期：卫乒年上丘日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 l 、保密口，在年月日解密后适用本授权声明。 2 、不保密日 ( 请在以上相应方格内打“4 ”) 保护知识产权声明 本人为申请河北大学学位所提交的题目为( 基于随机集样本的统计学习理论基础) 的学位论文，是我个人在导师( 哈明虎，田大增) 指导并与导师合作下取得的研究成果， 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费资助下 完成的本人完全了解并严格遵守中华人民共和国为保护知识产权所制定的各项法律、 行政法规以及河北大学的相关规定 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大学的书 面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内容如果违反 本声明，本人愿意承担相应法律责任 声明人： ：群：丛王珞 日期： 年月丘同 作者签名：豳! 丝 日期：上竺互年厶月j 厶日 导师签名：幽丝垒燮 日期：立竺五年二月碰同 第l 章绪论 第1 章绪论 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 ) 是v v a p n i k 等人【1 3 】从2 0 世纪 6 0 年代就开始研究的有限样本下的统计理论，在6 0 - - 7 0 年代奠定了其思想和框架的基础， 在此期间还定义了能反映函数集学习能力的v c 维；到9 0 年代发展成为比较完善的理论， 并受到了广泛的重视【卜5 1 。它为研究有限样本情况下机器学习的理论和方法提供了理论 框架，其核心思想是通过对学习机器容量的控制来实现对学习机器推广能力的控制。在 短短4 0 多年的时间里，国内外出现了大量此方面的论文。目前，统计学习理论已经成为 国际上机器学习领域新的研究热点。 在1 9 8 9 年，v a p n i k & c h e r v o n e n k i s 提出了学习理论的关键定理，把学习的一致性问题 转化为一致收敛性的问题。统计学习理论的关键定理十分重要，因为它指出了经验风险 最小化原则一致性的充分必要条件是取决于函数集中“最坏”的函数，同时，关键定理 也为后面的理论与应用奠定了基础。 统计学习理论一致收敛速率的界是统计学习理论的重要组成部分，这些界确定了采 用经验风险最小化( e r m ) 原则的学习机器的推广能力，所以统计学习理论一致收敛速 率的界是分析学习机器性能和发展新的学习算法的重要基础。通过对界的讨论，可以得 到经验风险最小化原则中经验风险与实际风险之间的关系，进而可以研究学习机器的推 广性能。 在对经验风险最小化原则的研究中发现，当样本有限时，不仅要最小化经验风险， 还要最小化与学习机器函数集的v c 维和训练样本数订有关的置信范围。基于此， v v a p n i k 提出了结构风险最小化原贝i j ( 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 u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是统计学 - j 理论的v c 维理论和结构 风险最小化原则的具体实现。它是一种新的通用机器学习方法，在生物信息技术、图象 图形处理与经济预测等领域中均取得了成功的应用1 6 - 9 1 。因此，较之以往的机器学习方 法，s l t 与s v m 在理论研究和应用过程中都表现出很大的优势。国内外已有众多学者开 始密切关注和研究这一学术领域，目前s l t 与s v m 已成为学术界公认的机器学习领域一 河北大学理学硕士学位论文 个新的研究热点。 1 2 基于随机集样本的统计学习理论的提出及意义 尽管统计学习理论是学术界公认的较好的处理小样本的学习理论，但它仍有一些不 完善之处，如：统计学习理论是基于随机样本( 随机变量) 的，它难以处理基于随机集 样本的学习问题。随机集是由d gk e n d a l l 1 0 】在1 9 7 3 年用集值集函数的关联函数引出了 可测闭集值映射( 也称随机集) ，是对随机变量的一个重要推广，并且已经成功的运用到 了数理经济【1 1 1 、随机优化理论f 1 2 】等学科中。因此把基于随机样本的统计学习理论推广为 基于随机集样本的统计学习理论具有重要的理论意义和广阔的应用前景【协15 1 。国内外学 者刚刚开始此领域的研究，并得到了一些有意义的工作。如：哈明虎，陈继强和郑莉芳 1 6 , 1 7 首次讨论了基于随机集样本的关键定理；哈明虎、陈继强【1 8 1 讨论了基于集值概率和 随机集的统计学习理论，提出了集值概率空间中基于随机集样本的关键定理，学习过程 收敛速率的界和结构风险最小化。 1 3 本文的主要内容 本文结合随机集和统计学习理论的知识，给出了基于随机集样本的统计学习理论的 关键定理、学习过程一致收敛速率的界和v c 维。主要内容如下： 第2 章是随机集的基本知识，讨论了随机集的一些性质，给出了基于所维随机变量 的大数定律等一些重要的不等式。 第3 章提出了基于随机集的一致收敛性概念，证明了基于随机集样本的关键定理。 第4 章给出并证明了学习过程一致收敛速率的界，v c 维和推广性的界。 第2 章预备知识 第2 章预备知识 这一章主要给出了随机集的基本知识，讨论了随机集的一些性质，给出了基于m 维 随机变量的大数定律等若干重要不等式。 2 1 随机集的基本概念 首先我们给出随机集的定义并进一步讨论它的一些性质。 本文假定冗”为肌维欧氏空间，昂( r ”) 表示爱”中全体非空子集，q 为非空集合，4 为q 的子集组成的仃代数，则( q 4 ) 为一可测空间。 定义2 1 1 1 9 1 设z 和j ，是两个非空集合，我们称映射j f ：x 斗死( ，) 是从x 到l ，的集 值映射。 定义2 2 f 2 0 1 若( q 么) 是可测空间，( ) 是从q 到尺”的集值映射，厂为尺”中所有 闭集组成的集类，我们称，( ) 为可测空间( q 么) 上的集值随机变量( 或可测集值映射) 当且仅当 ：( ) r 、f o a 其中f 7 - 。为了简便起见我们记为，。 定义2 3 1 2 0 1 若( q ，4 ) 是可测空间，扣) 是从q 到尺”的集值映射，厂是r ”中所有 闭集组成的集类，映射，：q 一五是闭集值映射若二是r ”中所有非空闭集组成的集类： 闭集值映射，是可测的若 ：，( ) n f o a 其中f 厂。可测的闭集值映射也称为随机集。 显然，若，是从( q 4 ，p ) 到r ”的随机集( 或闭随机集) ，则它也是从( q 4 ，p ) 到r ” 的集值随机变量。 2 2 随机集的性质和重要不等式 为了讨论基于随机集的统计学习理论的相关内容，下面我们给出随机集一些的性质 和若干重要的不等式。 定义2 4 1 2 0 】若( q ，a ，p ) 为概率空间，是从q 到r ”的随机集，肜是r ”中所有的紧 1 - 7 3 l 大学理学硕十学位论文 集组成的集类，乃( k ) 是，关于p 的分布函数当且仅当 乃( k ) = p ( ：，( ) r 、k o ) ，v k c 若，。( 玎1 ) 是从q 到r m 的随机集序列，( k ) 是丘关于p 的分布函数当且仅当 t f f n ( k ) = p ( c o ：，。( c o ) nk o ) ，v k 6 若，。( 玎1 ) 是从q 到尺m 的随机集序列，。研1 ) 是关于p 同分布的当且仅当 p ( ：，( c o ) nk a ) = p ( ：，。( c o ) nk o ) 其寺弋k 瓦，l ，n no 若，。( ，7 1 ) 是从q 到尺m 的随机集序列，称，。( ，1 ) 关于p 是相互独立的当且仅当 p ( - f 。( 国) r 、k g ，。( & ) ) 厂、k 0 ) - 乃。( k i ) 乃( 吒) 其中k l ，k2 ，k n 配。 定义2 5 t 2 0 l 若m ，鸩，帆是r 朋的子集，定义其乘法如下 m m ：鸠= 五x ：矗；m ( 1 ，刀) ) 其中而邑矗分别是相应元素的乘积。 引理2 1 若x 是f ( e ) 中的随机集，t 为从c ( z ) 到拓扑空间，的b o r e l 可测函 数，则r ( x ) 为f 中的随机集。 定义2 6 1 如果仃= ( 仃，口2 1 ，仃m ) ，仃( j ) ：q 寸足，仃关于j l l 是可积的当且仅当 仃( f s 朋) 关于是可积的，这时有 p 础= i - 0 1 d j ，o ) d a ，础l 厂、 q q qq 设厶( q ，r ”) 为q 到火m 关于u 可积函数的总体，f 是q 到r m 的集值映射。记 ( ) = 盯厶( q ，r ”) ；仃( ) 厂( ) ( 口，已) ) 。 设是( 9 4 ) 到足m 的集值映射，称 眇y e r ；y = 弘艇毗，) 为厂关于的积分。若p ，称厂关于p 是可积的。若厂是q 到r 。的随机集，称 4 第2 章预备知识 肛p 为随机集积分。 q 定义2 7 【2 0 1 设( q ，a ，尸) 是概率测度空间，是q 到度量空间足”的集值映射。 仃：q r ”是，的可测选择，若仃( ) ，( ) ，( q ) ，且4 是可测的。 定理2 1 【2 0 】设，是q 到r m 的闭集值映射。，是随机集当且仅当存在j f 的可测选择族 c v ；n21 ，使对任意& ) q ，有，( 国) = d ( ) ；，2l 。 定理2 2 我们令随机集：( ) = c ， 仃。( ) ；一1 ) ，( ) 为二( ) 的一个可测选择，则 q ( ：( ) ，仅) = c z 仃，( ，a ) ；玎1 ) ，仃。( ，a ) 为q ( ：( ) ，q ) 的一个可测选择。 证明由引理2 1 和定理2 1 即可得证。 定理2 3 【2 0 1 ( 基于m 维随机变量的大数定律) 设m 维随机变量x 。，x ：，e 相互独 立，并且与x 同一分布，则 夏= 丢喜z 寺肛( ：) 河北大学理学硕士学位论文 第3 章基于随机集样本的学习理论的关键定理 本苹我们首先给出基于随机集样本统计学习理论的若干基本概念，然后在此基础上 讨论学习理论的关键定理。 3 1 经验风险最小化原则 定义3 1 1 1 6 】( 基于随机集样本的经验风险最小化原则) 我们用最小化经验风险泛函 r e m p ( a ：寻圭q ( z ，a ) ，a a 来代替最小化期望风险泛函 尺( a ) = j 9 ( z ，a 炒( z ) ，a 人 其中期望风险泛函基于数据 z t ，z 2 ，z | 以及分布函数f ( ：) 而得到的，并且是显式的形式，因此它容易最小化。 设期望风险泛函在q ( z ，a 。) 上取得最小值，经验风险泛函在9 ( ：，a ，) 上取得最小值。 我们将考虑用9 ( ：，a ，) 来近似代替q ( z ，口。) ，这种处理最小化期望风险泛函问题的方式 称为经验风险最小化原则，简称为e r i v i 原则。 定义3 2m 维随机向量爿= ( q ，a m ) ，下文中我们定义i 彳l - - i ( q ，) l = ( ，i 1 ) ， = ( q ，s 。) ，s 石即( 毛 o ，2 o ，靠 0 ) 。 定义3 3q ( z ，a ) 是随机集，仃( 2 ，口) 是随机集q ( z ，a ) 的任一可测选择，我们定义 s 砌u p q ( 础) = m 2 ( 磐仃( 扣：) ，s 砌u p a口( z ：，a ) j ，a e 口e口 廷f q ( 乙a ) = n = ( i n f o ( ：，a ) ，。i n 。f 仃( 乏，a ) ) 。 定义3 4 ，维随机向量a = ( 口1 ，) ，b = ( 6 l ，屯) ，我们定义彳 b 营口1 6 l ， k ， 彳u b = ( a iu 6 i ，a mu k ) 。 定义3 5 设仃( z ，口) 是随机集9 ( z ，a ) 的任一可测选择。册维随机变量序列 考7 = s a 印e alip ( 厶a ) 护( z ) 一7 1 善仃( 乙，口) l ，= t ，2 ， 第3 章基丁随机集样本的统计学习理论的关键定理 对于任伺正的s ，卜夕u 收敛住 p 矧川嘶) 一辛c 叫， 0 一。 成立，我们称上述关系式为在给定随机集类上均值到期望的致( 双边) 收敛性。 定义3 6 设仃( z ，a ) 是9 ( z ，口) 任一可测选择。令 + = 嚣。 若m 维随机向量序列 乒s a u e p af ，a ) 卵 喜吨) h 2 ， 对于任何正的g ，下列收敛性 p k a e a f ，p 仁口) 嘶) 喜吨卜) 与。 成立，我们称上述关系式为在给定随机集类上均值到期望的一致单边收敛性。 定义3 7 我们称e r m 原则是平凡一致的若对于随机集类9 ( z ，口) ，口人和分布函 数f ( z ) ，下列收敛性成立 蝶( a ) 寺瓣r ( a ) 即对于随机集类q ( 三，a ) ，a 人的任一可测选择口( ：，a ) ，下列收敛性成立 p i 赠p ( z ，a ) 印( 三) 一蝶詈喜j ( ，口) l ) 与。 定义3 8 我们称e r m 原则是严格( 非平凡) 一致的若对于随机集类 q ( ：( ) ，a ) ，口人和概率分布函数，( 三) ，q ( ：，a ) ，a 人的任意非空子集 人( c ) = a ：p ( z ，a p f ( z ) c ，口人) ，c r ”， 下列收敛性成立 。( 口) i n ( ( t f r ( a ) 即对于随机集类q ( ：，a ) ，a 人的任一可测选择巧( z ，a ) ，下歹u 收敛性成立 7 河北大学理学硕+ 学位论文 p | 蝶p ( 乙口) 卯( z ) 一蝶；妻盯( z ，a ) j 。 g ) 与。 c 3 m 定理3 1 若e r m 原则是严格一致的，则下式成立 r ( a ，) 1 扣骤灭( 口) i a y _ 明要i y _ 明r ( a ，) 吉一孵r ( 口) 成立，即我们要i y 明对于随机集类 q ( 二，a ) ，a 人的任一可测选择仃( ：，a ) ，下列收敛性成立 p ( 乙q ) 护( z ) 1 搽p ( 鹚矽( z ) ( 3 2 ) 令蝶p ( z ，a ) a r ( z ) = p ( z ，口。炒( z ) = 丁= ( ，。，2 ，o ) ，对于任意s 石，考虑随机 集类q ( z ，a ) ，口人的子集人( 丁+ ) = 人( f i + s l ，岛+ 2 ，0 + g ，) ，令我们选取s ，使得子 集人( 丁+ ) 非空，所以蝶p ( 乙及) 抒( z ) r + s 7 + 导，即 舰p 喜比川犰和 又因为e r m 原则是严格一致的，所以式( 3 1 ) 成立，则 p 獬喜咖m 心 一。 即 骢p ；喜仃( 互，a ，) 芝丁+ 兰) = 。 所以 骢p 口，人( 丁+ ) = o ，则a ，a ( 丁+ s ) 是不成立的，所以口，萑人( 丁+ s ) ，则不等 式丁p ( z ，a ，) d f ( z ) 丁+ 成立。这一不等式说明式( 3 2 ) 成立。 因此我们已经证明了严格一致性包含收敛性，但反之则不成立。 有了匕述定义我们便n - i 以给出基于随机集样本的学习理论的关键定理。 3 2 关键定理 下面，我们给出基于随机集样本的学习理论的关键定理。 定理3 2 设9 ( ：，口) ，a 人为随机集类，o ( z ，口) 为9 ( z ，口) 的任一可测选择，菩存在 8 第3 章基丁二随机集样本的统计学习理论的关键定理 所维实数e 和f ，使得对于随机集类g 【z ，a j ，a 人中所有的随机集，及某个给定的分 布函数f ( 二) ，不等式 e p ( ：，a p f ( z ) f ，ae a 成立，则e r m 原则严格一致性的充分必要条件是均值到数学期望的一致单边收敛性成 立，即 p 慨，p 似a ) 嘶) 一i n f “，7 1 善i 雌，仅) | 。 0 与。 一, u p f f o 础) 水一7 1 善1 吨川) 0 与。 成立。 证明必要性：若e r m 原则是严格一致的，则对于任意非空集合 人( c ) = 仅：卜( ：a 妒( ：) c ，a 人 ，c 为渐维实数，收敛性 p 慨，pb 口) 删矿蕊i 1 善i 比州卜) 与。 3 ， 成立。考虑有限个朋维数列口l ，它满足b + 。一q l 。 ) 假设彳出现，则有口人，使得p ( ：，口) 扭( ：) 一 妻叮( 互，口) s 成立。我们从a 中找 到一个七， 使得口人( q ) = a ：p ( 工，a 炒( z ) q ，a 人 ， 那么不等式 p ( z ，a ) 卵( z ) 一q 手喜d ( 互，a ) i n 。f 嘞彦喜仃( ，a ) 即事件疋出现，因此丁也出现。所以有：p ( a ) 0 一。 5 ， 定理第一部分得证。 充分性：现在假设一致单边收敛性( 3 5 ) 发生。下面我们证明在这种情况下严格一致 收敛性发生，即：对任意s 石，收敛性 咄i n 冰f ，p k a ) 嘶) 一献i n f 7 1 荟1 叱川卜) 与。 成立。我们令 4 = 1 蕊p k a ) 嘶) 一刚i n f 手喜仃( 叫。 0 4 = z ：蕊，口) 卵刚i n f 手喜吨川) 4 = k i 刮n f u 胁a ) 织一蕊，蒜吨州) 则4 = 4 u 4 。 我们要确定事件的概率的界：p ( 4 ) - p ( 4 ) + p ( a 2 ) 假设事件4 出现，为了确定p ( 4 ) 的界，我们取盯( z ，a ) ，使得： p ( 即) 卵( ：) 州i n f p ( 础) 积( z ) + 兰 p ( z ，口) 卵( z ) + 兰 蕊，p ( z ，a ) 卵( 三) + s 蕊专喜仃( ，a ) 封与。 6 ， 根据定理2 3 ，右端概率趋于零。 另一方面，如果事件4 发生，则存在仃( z ，口”) ，使得： 藩口( 邵“) 。酷；喜比川+ g j ；喜口( ，口“) + 三 。i 州n f ，彦喜盯( ，引+ e ， 、i， v 心 口 t 、l 、 ，d 闽七 1一， flj，硝 、l ， l一， 一| ， 打 、l-， r 五 一 矽 ，il ，、 似 七 如p 0 s ) = p ( 卜( 归( z ) ，p ( ”渺) 一噍口( 扣一，謦( 和。) ) “，) = p 舵( 碱) 嘶) 一7 1 善ia ( 扣。) ) s n ( p ( 柚归一辛( 和。) ) 岛) 血n p n ( 。) 嘶) 一( 为口。) ) ，) 其中川2 肌 我们利用c h e m o f f 不等式： 1 2 第4 章学习过程一致收敛速率的界 p 弘( 矗) 嘶) 一辛( 哆吒) ) 巳) s ) 0 喜p ( p b a 归一夸( 训。) ) s 卜e x p h ， 下面我们讨论学习过程一致收敛速率的界以及界与集合容量之间的关系。 定理4 2 设q ( ：，吒) k = 1 ，2 ，是指示随机集类，盯( ：，a 州) ) 是q ( ：，a 州j ) 的任一 可测选择，则不等式 p(z，a。，)df(z)一：委口(，a。，)(1nn-lnq)：，乎 依至少1 一r l 的概率成立。 证明根据定理4 1 ，我们引进正数叩，0 ，时，q = o 。对于上述函数，很容易验证 t = o 关系式 m ( 1 ，z ，研) = c , o = 1 ，( 刀，朋) = 2 k m ，如果， i 意味着序列中有一个元素z 。使得对于某一随机集9 ( z ，) ，我们有( 三，口。) = 1 ， 仃，( z ，q ) 表示随机集q ( 三，a ，) 的可测选择仃( z ，) 的第p 个分量，p = l ，m 。而对于 另一随机集q ( z ，口：) ，我们有( z ，a ：) - o ，所以有 ( z ) - - 2 ”。 2 对于，玎一1 ，因为前提条件为假，所以引理的论断为真。实际上，在这种情况 下，前提条件是 ( g i ) 2 2 ，刁) 2 k 研，这是不可能成立的，因为 ( 三。，2 2 ，刁) 2 h ”。 3 最后假定对于疗n o 和所有的，引理成立。考虑i = n o + 1 的情况，我们将证明 这种情况下，对于所有，引理同样成立。 我们固定竹= + 1 ，并进行关于，的归纳推理。正如前面已经指出，对于， ( + l ，l o + 1 ，肌) 如果我们找到长度为+ 1 的一个子序列，比如：毛，2 2 ，气+ l ，使得 ( 毛，z 2 ， + 。) = 2 ”咖脚 则引理将得到证明。 考虑子序列毛，z ：，气，有两种情形： 情形1 ： ( 毛，：，气) ( + l ，厶，聊) ，很显然。 一一一一 叁尘曼耋型丝丝丝塑型坠一 情形2 ：n a ( 毛，z 2 ，气) ( 代+ 1 ，f o ，南) ，我们将序列毛，毛，气的子序列分成两 种类型。我们将子序列z p 气，0 指定为第一种类型，如果在随机集类q ( z ，a ) ，a 人 中，存在一个随机集9 ( z ，口) ，满足条件 仃，( 气“，口。) = 1 ，p = l ，- 。，疗 仃，( 气，a ) = ( 铂，a ) ，k = 1 2 一， ( 一，a ) ( 气a ) ，如果z ，芒 气，k = l ，2 ，厂 又存在另一个随机集9 ( ：，a “) ，满足条件 ( 气+ l ，a “) = o ，p = l ，历 c r p ( 气，a ”) ( 气巾a ”) ，k = l 一2 一， ( 二，口“) = a p ( 气a ”) ，如果刁正 o ，k = 1 ，2 ，n 我们把子序列气，乙，二。定义为第二种类型，如果在随机集类9 ( ：，a ) ，a 人中，或 者存在一个随机集q ( ：，口) ，满足条件 o r ( o 一) = 1 ，p = l ，m 万，( 气a ) = ( 气小a 。) ，七= 1 2 “，r 仃，( 彳，及) ( 气小a 。) ，如果乃萑 气，k = l ，2 ，厂 或者存在另一个随机集q ( 二a “) ，满足条件 c 7 p ( 讪，a ”- o ，p = l ，m o p ( 气，a ”) ( 讪，a ”) ，k = l 2 一，r o p ( ? ，a ”) = 仃p ( 气+ ，q ”) ，如果乃叠 气，k = 1 ，2 ，- ( 不同时满足) 。 用k 表示第一类子序列的数目，用k ：表示第二类子序列的数目，则 n ( z iz ：，气) ；k + 心 1 7 河北大学理学硕士学位论文 因此 n “2 i ，z ，z 一。i = 2 k i + k z ( z 1 ，z ：，气，气+ ，) = ( 毛，乞，气) + k ( 4 5 ) 用q ( z ，a ) ，a 人表示随机集类q ( z ，口) ，a 人的子集，它在毛，乞，刁，气+ t 上诱导 出第一类子序列。如果 墨= z i ，乞，气) 中( ，f 0 ，肌) 则根据归纳假设，存在一个子序列气，气，互。，使得 n a ( 邻气，z k ) = 2 m 然而，这种情况下，对于序列毛，气，气，气+ i ，有 n a ( 气，气，气，气+ 。) = 2 + 1 p 掰 因为这一子序列属于第一类子序列。 然而，j z l 3 果k l = r ( 互，乞，气) ( ，乇，朋) ，则根据式( 4 5 ) 和( 4 6 ) 得 n ( 毛，z ：，气，气+ 。) ( 玎。+ l ，乇，聊) + 。( ，乇，坍) 利用函数( ”，) 的性质( 4 4 ) ，上式意味着有 ( 毛，乞，气+ 。) ( + 1 ，乇+ 1 ，肌) 这与引理条件矛盾，引理得证。 由引理4 1 我们推断出下列引理成立。 ( 4 6 ) 引理4 2 如果对于某个刀，有s u pn ( z 1 , 乞，乙+ 。) 2 肿1 “，则对于所有， 刀， - i ：2 而+ i 不等式 s u pn ( 而，乞，刁) ( 刀+ l ，m ) ：l ，：2 ：f 成立。 引理4 3 对于随机集类q ( 2 ，仅) ，位人的生长函数或者满足等式 或者满足下面不等式 g 1 ) = ( i x m ) i n 2 1 8 弗4 早：了二卅 过忾一取叶足玖述罕h 0 罗r f = ( ，r e ) m 2 若，s 办 g 7 1 m - n ( 砉q ) 聊h ( 鲁) 6 = ，疗厅( ，+ - n 丢) 若， 办 这里办为随机集类9 ( z ，a ) ，0 t 人的v c 维，肼为随机集可测选择的维数。 定理4 4 3 1 设指示函数集q ( z ，口) ，口人包含无穷多个元素，则下列不等式成立： 。抽a e a 妒一7 1 黔i ) 卜p ( 华一( g 一册 定理4 5 对于指示随机集类q ( z ，口) ，a 人，及某个给定的分布函数f ( ：) ，设盯( z ，a ) 是q ( ：a ) 任一可测选择，下列不等式成立 幅俐一7 1 渺i 巾 0 = p m 嘶) 一7 1 善i 如仅) 印，m 卵一7 i 善i 。( 曩a ) s 。) ) r n j n p 冀p ( p ( 乃，a ) 扭( 二) 一手喜d ( ) ，一，= 2 ，坍 由定乳4 确p 卜s u p ”ih 口) 啡) 一渤誓小，卜p ( 掣t 册 舭 s u p f a e a 、, 州告咖卜p ( 华t 册卜 p c z ，a ，d f c ：，一7 1 善i ac，a， 1 9 l + ：， ， 1 + 一 ， 河北大学理学硕士学位论文 证明肌删俐唧 ( 华t 珊卜从 而解得： j2 因此，对于集类q ( ：，口) 中的任意元素，不等式： p ( 础) 卵( z ) 喜仃( ) l j - ， 1 + 了， l l 上一 ， ( 4 7 ) 依至少l r 7 的概率成立。 定理4 7 若q ( ：，口) 是随机集类，仃( 二，a ) 是q ( z ，o t ) 的任一可测选择，则不等式： p ( 硼，) 卵( z ) 一p ( 删。) 打( z ) 1 + 一+ ， 依至少1 - 2 7 7 的概率成立。 证明利用c h e m o f f 不等式： p 犯喜心a ) 一，a ) 嘶) ) 小唧h ， 引进o ( 印 ) ) = p ( p ( 五以) 卵( z ) 一7 1 善i 仃( 才以) ) s 。n n ( p ( 孙) 卵( z ) 一7 1 善i 仃( 彳以) ) ) 一肛( 孙口。) 嘶) 一謦( 巧q ) ) s 小其中川，2 儿 我们利用h o e f f d i n g 不等式： p ，叫酢一1 驰i 以) ) ，卜 - 啬 y 口j 北灭字理7 删1 ：了= 似比义 曼! 鼍喜詈! 皇皇墨詈! 鼍皇鼍i 鼍皇曼詈! 詈皇皇鼍鼍曼薯皇! 罡! ! 曼! 鲁詈詈鼍鼍曼皇皇! ! ! ! 曼詈喜量詈! 鼍! ! ! 皇詈詈寡曼! 皇曼! ! 曼曼皇皇 p 雌七小地叫刊 一卜唧 一器 成立，则下列不等式成立 p f 。娑( p ( z ，a 渺( z ) 一辛( z ，叫 s ) 喜p ( p ( z ，口。) 卵( i ) 一7 1 善i 仃( 互，a 。) ) ) m 以俐一7 1 黔i 训) s 岛j j ，则 ， 一 z 、，j一) 1一，一月 一 一一 s 一日 盟 、i - ，一，一 2 一i 、一 声，一? 删一 华 o，一f， l一，一一 一 一一一b 而 一 奶一 壁， 一 小 朋 衅 h 脚 吐 r 0驴州 口 吖 j o 0 d，d闻 ，d一一 一飞 垆 以 一 纠 哪 电 弘 h l 厂 叩卧 一 ， 蔫、姗咕 ，以 葛 2 2 、，一) 1一，一月 一 一一 s 日 盟 、- ，一 ，_ 2 一，一 声，一? a 期一 半 、1iib卜lij 哥虿 l r p 一 狮 幽， 5 河北大学理学硕士学位论文 定理4 1 3 设9 ( z ，a ) 是随机集类，仃( z ，口) 是9 ( z ，a ) 的一个可测选择，其中 a o i ( z ，a ) b ，则不等式 胁a ) 卵( z ) 一番1i ( ) ( ) 厕 依至少1 一r l 的概率成立，其中 ( ，) = 础( 2 z ) 山翌4 1 碟( 2 7 ) - l nr 4 l 。l ，z z。z 证明根据定理4 1 2 ，我们引进0 叩1 ，令4 e x p 而解得： ，= ( b - a ) 1 + 一 ， = r 7 ，从 因此，对于集类9 ( z ，口) 中的任意元素，不等式： 胁妒一辛( 枷) 小x p 一舀) 引进0 7 1 ， 从而解得： ，z 一，- 、，一hl， 1一，一4 一 一一 g 一石 哑删 、，一 t ，_ 2 一 ，l一 声，一， a 婴 半 南 第4 章学习过程一致收敛速率