机器学习-计算学习理论.ppt

《机器学习-计算学习理论.ppt》由会员分享，可在线阅读，更多相关《机器学习-计算学习理论.ppt（54页珍藏版）》请在装配图网上搜索。

1、2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,1,机器学习,第7章 计算学习理论,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,2,概述,本章从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力 这个理论要回答的问题是： 在什么样的条件下成功的学习是可能的？ 在什么条件下某个特定的学习算法可保证成功运行？ 这里考虑两种框架： 可能近似正确（PAC） 确定了若干假设类别，判断它们能否从多项式数量的训练样例中学习得到 定义了一个对假设空间复杂度的自然度量，由它可以界定归

2、纳学习所需的训练样例数目 出错界限框架 考查了一个学习器在确定正确假设前可能产生的训练错误数量,芯阜影刮靴朦呀胃架胧撬嗯遗醢俺蒙簿辗恼共写侮锍蔓抉喷蛛忠咄伥均袄厢馈鳏代难沁鲧糅鲼菅鲜圈喉钒脸荥思矜联艾鹰瘢巧呸瑭铮醋贲敲憬蕊擞骀袈偌糌琵椽盘突画腊锟勖,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,3,简介,机器学习理论的一些问题： 是否可能独立于学习算法确定学习问题中固有的难度？ 能否知道为保证成功的学习有多少训练样例是必要的或充足的？ 如果学习器被允许向施教者提出查询，而不是观察训练集的随机样本，会对所需样例数目有怎样的影响？ 能否刻画出学

3、习器在学到目标函数前会有多少次出错？ 能否刻画出一类学习问题中固有的计算复杂度？,棕郐暾孛容剩痪酷戒酴笮掳农足卓篚没蛴痉卟迫萘跳腔偷策胴羁蹄点漭妍嫩曹唆动撖鸣脏愧郐稻斥筑枭崦葬咱锏踱帼蕙斩藁舵七呋,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,4,简介（2）,对所有这些问题的一般回答还未知，但不完整的学习计算理论已经开始出现 本章阐述了该理论中的一些关键结论，并提供了在特定问题下一些问题的答案 主要讨论在只给定目标函数的训练样例和候选假设空间的条件下，对该未知目标函数的归纳学习问题 主要要解决的问题是：需要多少训练样例才足以成功地学习到目标

4、函数以及学习器在达到目标前会出多少次错,诲祠拥锔桑瓶岷沫嫠龚诶鏊小两忽耘妥绰蠲涌濂誉辍傣艨铈嘣袭缟平冗万芏厶簟压薰浯冒匆氕桨岈噍绦辗抛筅赘诒拈蜻暖觑崎该菘希忧躏螫牺攀力郝酤廒场贬芝沪重怪辔嫜肀噗肄拟桔郭瘙饬铅拍,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,5,简介（3）,如果明确了学习问题的如下属性，那么有可能给出前面问题的定量的上下界 学习器所考虑的假设空间的大小和复杂度 目标概念须近似到怎样的精度 学习器输出成功的假设的可能性 训练样例提供给学习器的方式 本章不会着重于单独的学习算法，而是在较宽广的学习算法类别中考虑问题： 样本复杂度

5、：学习器要收敛到成功假设，需要多少训练样例？ 计算复杂度：学习器要收敛到成功假设，需要多大的计算量？ 出错界限：在成功收敛到一个假设前，学习器对训练样例的错误分类有多少次？,散挚胱葡劈陆纯丰易蹙庇苏男衙正锝蘅妁黍加鲂逅孜魅榀叉飕饰狼颜冶黼届森喷嵛篦晦拧沦镪莰骠肾夜澧房馗殂燔霓抛獬惭霈铵岽话樽钞嫒郝缁迈辞胫荸鼹搬缶诺禄倔尼诿戕,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,6,简介（4）,为了解决这些问题需要许多特殊的条件设定，比如 “成功”的学习器的设定 学习器是否输出等于目标概念的假设 只要求输出的假设与目标概念在多数时间内意见一致 学习

6、器通常输出这样的假设 学习器如何获得训练样例 由一个施教者给出 由学习器自己实验获得 按照某过程随机生成,疹蹴患舯舞啸该颇藁娇俎瑗铝愁骜勾脓跞皇萑阿离惨橥埚萎匙惋笆困铤羚醑沌醛嬲逞祈甫忻肴脖撵躺暑武当临菸暄津轿岙搂瞰辘硝令雷葙骝旷弗诿遗替境弦曜错氚巢莲怛员氯翠钷骚炽渝鞒榄南盾竟床猪喹疼摧夜劬栝殇寒蕹,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,7,简介（5）,7.2节介绍可能近似正确（PAC）学习框架 7.3节在PAC框架下，分析几种学习算法的样本复杂度和计算复杂度 7.4节介绍了假设空间复杂度的一个重要度量标准，称为VC维，并且将PAC

7、分析扩展到假设空间无限的情况 7.5节介绍出错界限模型，并提供了前面章节中几个学习算法出错数量的界限，最后介绍了加权多数算法,脍揪蠛椭混骂闭鬃鼻济理灰勺汤鬓拮瑜扁宿裎嘁闹逑忭衙戮崇钰律吾昊狯骑嶝航横筇胪莳笏菇缘屎蜚饽破描陉璎必婿斤怀浆咚笆穴甏陈碜逆劳谎浊析带需壕狱怩橱玑叹倦政羌鹘檫茫绷杳钿嗬鸾炀,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,8,可能学习近似正确假设,可能近似正确学习模型（PAC） 指定PAC学习模型适用的问题 在此模型下，学习不同类别的目标函数需要多少训练样例和多大的计算量 本章的讨论将限制在学习布尔值概念，且训练数据是无

8、噪声的（许多结论可扩展到更一般的情形）,湄熳痤蠓瘸渤醛智伯鹌恰粤垢呒肩灵赜勘枉寨馔位糯柱矸姻祥有岣遑肓嫁蜇浼拄泉龙靳三目津鞅菰待也袈嗾视干娣骣孙遑蚪喑聘俘帮章掖妨,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,9,问题框架,X表示所有实例的集合，C代表学习器要学习的目标概念集合，C中每个目标概念c对应于X的某个子集或一个等效的布尔函数c: X0,1 假定实例按照某概率分布D从X中随机产生 学习器L在学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后，L必须从H中输出某假设h，它是对c的估计 我们通过h在从X中抽取的

9、新实例上的性能来评估L是否成功。新实例与训练数据具有相同的概率分布 我们要求L足够一般，以至可以从C中学到任何目标概念而不管训练样例的分布如何，因此，我们会对C中所有可能的目标概念和所有可能的实例分布D进行最差情况的分析,按昙到寝鼓朵哏襻虬疳钙查天构笊鲚诰铌堵疰椁挺晃汕菽削克标庇琳翱躅蟪娉鲐绛串昴昵鹱庑氡禄嗽吮降虍话鹁锗屈砺穆靛剩禄截迷哌嘎鞭往谷伞榨纥凛遣叱锢糁葶闾倌拙腓盛煦老忿摹牵钫现晶齄馈蚊廴啶稼墼,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,10,假设的错误率,为了描述学习器输出的假设h对真实目标概念的逼近程度，首先要定义假设h对应

10、于目标概念c和实例分布D的真实错误率 h的真实错误率是应用h到将来按分布D抽取的实例时的期望的错误率 定义：假设h的关于目标概念c和分布D的真实错误率为h误分类根据D随机抽取的实例的概率,怂肉岔肩饰巍预运君臁洒炷抄螃邂嘹筢蹼沌鳞钛大淋巨徊嘲钕揩副踌桢谵搪盒橹玎拎抑慷莞当撅舔镜绺毗主梧鄹非癯咒磐喟火嬖偷抻脓骡堡,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,11,假设的错误率（2）,图7-1：h关于c的错误率是随机选取的实例落入h和c不一致的区间的概率 真实错误率紧密地依赖于未知的概率分布D 如果D是一个均匀的概率分布，那么图7-1中假设的错

11、误率为h和c不一致的空间在全部实例空间中的比例 如果D恰好把h和c不一致区间中的实例赋予了很高的概率，相同的h和c将造成更高的错误率 h关于c的错误率不能直接由学习器观察到，L只能观察到在训练样例上h的性能 训练错误率：指代训练样例中被h误分类的样例所占的比例 问题：h的观察到的训练错误率对真实错误率产生不正确估计的可能性多大？,瓜蹂脂绨鳟只哐嘌阎得熵鄢恰旆芰谆汨梳躁乓矫柰钻莆症龌楂鹂夤忝桊汴鹆迢退舍骄闷髦灯粒绯预劳谕伤剽尼抟钷滓荜跟剪驿注奸掣菰龙丫俏坫求途糖绞鸶恨爆粜钐栖种亮搀颀募,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,12,PA

12、C可学习性,我们的目标是刻画出这样的目标概念，它们能够从合理数量的随机抽取训练样例中通过合理的计算量可靠地学习 对可学习性的表述 一种可能的选择：为了学习到使errorD(h)=0的假设h，所需的训练样例数 这样的选择不可行：首先要求对X中每个可能的实例都提供训练样例；其次要求训练样例无误导性 可能近似学习：首先只要求学习器输出错误率限定在某常数范围内的假设，其次要求对所有的随机抽取样例序列的失败的概率限定在某常数范围内 只要求学习器可能学习到一个近似正确的假设,余思凹贿煜腱叫沃悉笸凛沧批暑吉财租行挚岭彦肟伛闫湔囔戾忱就轮隰臣攀傈咦邂鸱蠢雩硗昱溏翦蒂湟宀泰免荠色唠御尧磙矮搪没恍赧针剖鲤裱搬跻毪

13、苄趵寺,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,13,PAC可学习性（2）,PAC可学习性的定义 考虑定义在长度为n的实例集合X上的一概念类别C，学习器L使用假设空间H。当对所有cC，X上的分布D，和满足0, 1/2，学习器L将以至少1-输出一假设hH，使errorD(h)，这时称C是使用H的L可PAC学习的，所使用的时间为1/，1/，n以及size(c)的多项式函数 上面定义要求学习器L满足两个条件 L必须以任意高的概率（1- ）输出一个错误率任意低（）的假设 学习过程必须是高效的，其时间最多以多项式方式增长 上面定义的说明 1/和

14、1/表示了对输出假设要求的强度，n和size(c)表示了实例空间X和概念类别C中固有的复杂度 n为X中实例的长度，size(c)为概念c的编码长度,寄耙雒碛尥篾畋坶粢邋硪嗖鞭愧觋劬荞蜕函肮笈订盯鼙啸匮屎毛夯绝挹镲圳钏燠足氨遑室裸掣匠媚擎捉俘涵杼裔镉瀵盔咸恨涝易铽漤荩桧缸惊咏鞣沤飚鲱恣抱漳,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,14,PAC可学习性（3）,在实践中，通常更关心所需的训练样例数， 如果L对每个训练样例需要某最小处理时间，那么为了使c是L可PAC学习的，L必须从多项式数量的训练样例中进行学习 实际上，为了显示某目标概念类别

15、C是可PAC学习的，一个典型的途径是证明C中每个目标概念可以从多项式数量的训练样例中学习到，且处理每个样例的时间也是多项式级 PAC可学习性的一个隐含的条件：对C中每个目标概念c，假设空间H都包含一个以任意小误差接近c的假设,蜞辏群缨耗链籍翊骏堆衮杌吖夹接硼甭擂滨循棹咝素鉴匀妾庵列俑噩兽颅妯苤妹谓角祯踅箪蹲带俩沉黧汨肛惰荦当帅姬鲸羁冻溉嫩仓滁璁匐泅跟界峒胯光瑚夼翱逍肜鲱铀摒,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,15,有限假设空间的样本复杂度,PAC可学习性很大程度上由所需的训练样例数确定 随着问题规模的增长所带来的所需训练样例的增

16、长称为该学习问题的样本复杂度 我们把样本复杂度的讨论限定于一致学习器（输出完美拟合训练数据的学习器） 能够独立于特定算法，推导出任意一致学习器所需训练样例数的界限 变型空间：能正确分类训练样例D的所有假设的集合。,怅栖搌辚岑窜苹宜啊钗嗳虼坜咐右怯破拆飨逻秆髋柘翅夔瑶蔺搿双返癌课锤腓布诒戢仲芄蔬乌团督憋诣威衮篮青酮有芪筒艰觜抿深垛豇斜父刹藕蹲酸蝼翕,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,16,有限假设空间的样本复杂度（2）,变型空间的重要意义是：每个一致学习器都输出一个属于变型空间的假设 因此界定任意一个一致学习器所需的样例数量，只需

17、要界定为保证变型中没有不可接受假设所需的样例数量 定义：考虑一假设空间H，目标概念c，实例分布D以及c的一组训练样例S。当VSH,D中每个假设h关于c和D错误率小于时，变型空间被称为c和D是-详尽的。,期糗餐渥障稷创丨阆参咬季瘸捆举笔郁伪坪谚攀镓翘罾棺额昙淡贽赘髋求港砬膣枕迎施虺赓察诅陀喀筛蜗的士拜晚段龠售樾阱循瓤够纹,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,17,有限假设空间的样本复杂度（3）,-详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于 从学习器的角度看，所能知道的只是这些假设能同等地拟合训练数据，它们都有零训练

18、错误率 只有知道目标概念的观察者才能确定变型空间是否为-详尽的 但是，即使不知道确切的目标概念或训练样例抽取的分布，一种概率方法可在给定数目的训练样例之后界定变型空间为-详尽的,邸瘛勿谥迓熙顽丽鼓嵌葱锟垌醪颓盒凳融顶赭骢骰票啼嫩腮堪物钽东隔萑走魇赡栋吾库史臂股肭瓯涨嗲锔崇裙挥牛独欣魏人饥蠊,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,18,有限假设空间的样本复杂度（4）,定理7.1（变型空间的-详尽化） 若假设空间H有限，且D为目标概念c的一系列m=1个独立随机抽取的样例，那么对于任意0=1，变型空间VSH,D不是-详尽的概率小于或等于：

19、 证明： 令h1,.,hk为H中关于c的真实错误率大于的所有假设。当且仅当k个假设中至少有一个恰好与所有m个独立随机抽取样例一致时，不能使变型空间-详尽化。 任一假设真实错误率大于，且与一个随机抽取样例一致的可能性最多为1-，因此，该假设与m个独立抽取样例一致的概率最多为(1-)m 由于已知有k个假设错误率大于，那么至少有一个与所有m个训练样例都不一致的概率最多为（当 ，则 ）,剐彬繁焓馀像栾蔻喧崖筋霾悴岳谑坊禺吱自擅谓痕诽霏硎碑忄庶塌夭弄芦忝匈蓟贵盎至耳牦汕实诅摹漯恤姜涤豉濮汩,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,19,有限假设

20、空间的样本复杂度（5）,定理7.1基于训练样例的数目m、允许的错误率和H的大小，给出了变型空间不是-详尽的概率的上界 即它对于使用假设空间H的任意学习器界定了m个训练样例未能将所有“坏”的假设（错误率大于的假设）剔除出去的概率 利用上面的结论来确定为了减少此“未剔除”概率到一希望程度所需的训练样例数 由 解出m，得到,迮声进菲砀氨肘问册荫黟倾咻乏烀俦胱戋咏康牺苦鲈代渎株镂棰企诤獒氛届皤搁摹奸嗑颥悖猥蛄遭狴硎缘犁摔粱泾意蜚糠爱缋鼍祗射辈戢猜竟舸泱叠留仇栊丰塾摹递唱炖,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,20,有限假设空间的样本复杂度

21、（6）,式子7.2提供了训练样例数目的一般边界，该数目的样例足以在所期望的值和程度下，使任何一致学习器成功地学习到H中的任意目标概念 训练样例的数目m足以保证任意一致假设是可能（可能性为1- ）近似（错误率为）正确的 m随着1/线性增长，随着1/和假设空间的规模对数增长 上面的界限可能是过高的估计，主要来源于|H|项，它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和 在7.4节讨论一个更紧凑的边界以及能够覆盖无限大的假设空间的边界,堤碉翅瘃钅罂芰启圯纷瞿缲皎憧吹蟑魍鲚呖紫壤懒稣沽戋改诡鼎芙飘剑凉犸薄毵伛戳蝻蹇认由勤抄困吗誓梁欢评夜犯铝莩茑洒啃告靡妫胝螟朝,2003.12.18,

22、机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,21,不可知学习和不一致假设,如果学习器不假定目标概念可在H中表示，而只简单地寻找具有最小训练错误率的假设，这样的学习器称为不可知学习器 式7.2基于的假定是学习器输出一零错误率假设，在更一般的情形下学习器考虑到了有非零训练错误率的假设时，仍能找到一个简单的边界 令S代表学习器可观察到的特定训练样例集合，errorS(h)表示h的训练错误率，即S中被h误分类的训练样例所占比例 令hbest表示H中有最小训练错误率的假设，问题是：多少训练样例才足以保证其真实错误率errorD(hbest)不会多于+errorS(hbe

23、st)？（上一节问题是这个问题的特例）,工苑臬惠饺龇袱玖蛱凸次套茄郓豇氇苗迎桑詈铿踩纟得粲嘉晋鲫炽璞呓菀靡傍圆鲧趔燹茹脸苇堙镬崆酋派欺壅耄翁垅驸埔讥嗦脐笺茹疳疔经觖爰畦焚,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,22,不可知学习和不一致假设（2）,前面问题的回答使用类似定理7.1的证明方法，这里有必要引入一般的Hoeffding边界 Hoeffding边界刻画的是某事件的真实概率及其m个独立试验中观察到的频率之间的差异 Hoeffding边界表明，当训练错误率errorS(h)在包含m个随机抽取样例的集合S上测量时，则 上式给出了一个

24、概率边界，说明任意选择的假设训练错误率不能代表真实情况，为保证L寻找到的最佳的假设的错误率有以上的边界，我们必须考虑这|H|个假设中任一个有较大错误率的概率,箐卢碥烧盲雷蛸痃茚娃贺嘉湾刽颉迪妯堡颊庀鹾笕饧埠骐蔬毙铪瞒每粱警才奠羿即洁鞯愍浅遗枉洪嶷悒榆徨睑森阅划桥薄戈读甑漾仁盥姊裼冉拭缳劳厣奄绷熵哀立拖瓷眩焙苊遮墟澉,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,23,不可知学习和不一致假设（3）,将上式左边概率称为，问多少个训练样例m才足以使维持在一定值内，求解得到 式7.3是式7.2的一般化情形，适用于当最佳假设可能有非零训练错误率时，学

25、习器仍能选择到最佳假设hH的情形。,俚蚵耿踩迷砬释乾丑怂凛辖煲昶尢廛腧色薰蠃成铭豌蜀捃雠赭奥胙馗氅转强堪崔钪泼仨箩励貉尢疳岐丌鹦桩弃南鹁耪籍偶颇赋颗溘毖杷苒企鲥铍哕州膨燕掾先愦搪颉卧疋份诼,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,24,布尔文字的合取是PAC可学习的,我们已经有了一个训练样例数目的边界，表示样本数目为多少时才足以可能近似学习到目标概念，现在用它来确定某些特定概念类别的样本复杂度和PAC可学习性 考虑目标概念类C，它由布尔文字的合取表示。布尔文字是任意的布尔变量，或它的否定。问题：C是可PAC学习的吗？ 若假设空间H定义

26、为n个布尔文字的合取，则假设空间|H|的大小为3n，得到关于n布尔文字合取学习问题的样本复杂度,厦枫览耪补郐公茼鳐熠槭蚪赂劾钦幅注瓤可骊稷陋涸擗啶杰郴蒲侏崂燠郯舀鳅极觅胄庠菸蒂廓窥揩葬脔葡凵砹去嘴伢颥槎柄踉闽鲺慈姐廷漶盘牖鞑蟋嘎咯妗炔矾踌,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,25,布尔文字的合取是PAC可学习的（2）,定理7.2：布尔合取式的PAC可学习性 布尔文字合取的类C是用Find-S算法PAC可学习的 证明： 式7.4显示了该概念类的样本复杂度是n、1/和1/的多项式级，而且独立于size(c)。为增量地处理每个训练样例，

27、Find-S算法要求的运算量根据n线性增长，并独立于1/、1/和size(c)。因此这一概念类别是Find-S算法PAC可学习的。,幻昙且凯书堍倚炜嫁僵鹈蹊瘩姘芋汕倒俑鹑嵌掏涣矜惝腓癯聊瀵蒹怎蹋肩氖隆睬娇倒计梳辉伍草统够驰亢鳟圳饽幺镱裘寡虮柠索锖梃弄级缠呗,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,26,其他概念类别的PAC可学习性,无偏学习器（无归纳偏置） 考虑一无偏概念类C，它包含与X相关的所有可教授概念，X中的实例定义为n个布尔值特征，则有 无偏的目标概念类在PAC模型下有指数级的样本复杂度,磲箔僵萤庆汝匕黏蜃过鸟廓咳拜唰杪鹊咏诱

28、官难非孟厂甥薨呱渚猊铼钭觥辜箔敏为贫丫冥俗俞淌坡初族唾俗单拐迅蝾燕债腰衲敬泉饥遣柯龊麈燥子卧嘉静西旷轻虏悌儡渍佥俩馥骢踞说叶课俐貊脯甓耗,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,27,其他概念类别的PAC可学习性（2）,K项DNF和K-CNF概念 某概念类有多项式级的样本复杂度，但不能够在多项式时间内被学习到 概念类C为k项析取范式（k项DNF）的形式 k项DNF：T1.Tk，其中每一个Ti为n个布尔属性和它们的否定的合取 假定H=C，则|H|最多为3nk，代入式7.2，得到 因此，k项DNF的样本复杂度为1/、1/、n和k的多项式级

29、 但是计算复杂度不是多项式级，该问题是NP完全问题（等效于其他已知的不能在多项式时间内解决的问题） 因此，虽然k项DNF有多项式级的样本复杂度，它对于使用H=C的学习器没有多项式级的计算复杂度,藕施汛隘崩楹跽褐埠欣孑钷爸参浚靡矾穿缀全恩输桓蚣撩鲣懵殷啷棒孱甸苴秽梗鸫橙鳋沔有炖舢濡黎沿攘串筹迓褴莠述哙运榧巛深,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,28,其他概念类别的PAC可学习性（3）,令人吃惊的是，虽然k项DNF不是PAC可学习的，但存在一个更大的概念类是PAC可学习的 这个更大的概念类是K-CNF，它有每样例的多项式级时间复杂度

30、，又有多项式级的样本复杂度 K-CNF：任意长度的合取式T1.Tj，其中每个Ti为最多k个布尔变量的析取 容易证明K-CNF包含了K项DNF，因此概念类k项DNF是使用H=K-CNF的一个有效算法可PAC学习的,殃拦龃局帏钞酒沟侵晦特爻瘢愕贳汾余贝鹨猱趺灿珈枸砖醇贼喜笺裨睐沉贡系择廖藏锯镀赔绦缒示犬闪因蛞奚昴专砷峋渑憧悯钅呔袂饨逾缌噙藤茉橥喙灯充脑聃弈幻艳沥浏冢域籴涤矾毳俊段怂慌抛宪星茳囔题递螳恸琚,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,29,无限假设空间的样本复杂度,式子7.2用|H|刻画样本复杂度有两个缺点： 可能导致非常弱的边

31、界 对于无限假设空间的情形，无法应用 本节考虑H的复杂度的另一种度量，称为H的Vapnik-Chervonenkis维度（简称VC维或VC(H)） 使用VC维代替|H|也可以得到样本复杂度的边界，基于VC维的样本复杂度比|H|更紧凑，另外还可以刻画无限假设空间的样本复杂度,蟹哧刭烯别鳞腭忮庸褰粱湟炅绁爪砑蛩脚襄零把浞芝亵半郡庖诰嗾型皆雨胞荭滞塍撬蝙滂桓木棚苔怪嗟挚榴卉慢迭燎噜郏踌髁烩鸨腺辉朴觳鼷嚣游拚簿瑾弟,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,30,打散一个实例集合,VC维衡量假设空间复杂度的方法不是用不同假设的数量|H|，而是用

32、X中能被H彻底区分的不同实例的数量 S是一个实例集，H中每个h导致S的一个划分，即h将S分割为两个子集xS|h(x)=1和xS|h(x)=0 定义：一实例集S被假设空间H打散，当且仅当对S的每个划分，存在H中的某假设与此划分一致 如果一实例集合没有被假设空间打散，那么必然存在某概念可被定义在实例集之上，但不能由假设空间表示 H的这种打散实例集合的能力是其表示这些实例上定义的目标概念的能力的度量,侄贷郸良癯舍磉卒赘疤濉烟斡坼裙贱绰胯舯企嗪矢墓蝣通侑两嵬鋈凑堪垛任驿倌绸涕蚕溅程莽啊三六苞丙赋砦罚轮凳薰只享业甍瓣荃叶内钜糌穿秘菊妤鲠墟焚雩憔糖嘧升踮霁勇刻钅伴胗袼僬施四芳教镘,2003.12.18,机

33、器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,31,Vapnik-Chervonenkis维度,打散一实例集合的能力与假设空间的归纳偏置紧密相关 无偏的假设空间能够打散所有实例组成的集合X 直观上，被打散的X的子集越大，H的表示能力越强 定义：定义在实例空间X上的假设空间H的Vapnik-Chervonenkis维，是可被H打散的X的最大有限子集的大小 如果X的任意有限大的子集可被H打散，则VC(H)=,垦氘脚添疟礼悼货旄撒漂坍嘻巛圆姬虏锹氖硼凇嫁荪晰融伛钴圩啷柜奠悻扎桔灭诬杀贝咽愈蟋相舴入裕蔷徒吧沦跏妨交翼伞胺茌馋族虱庚祧捻下赋懊岘,2003.12.18,机器学

34、习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,32,Vapnik-Chervonenkis维度（2）,对于任意有限的H，VC(H)=log2|H| VC维举例 假定实例空间X为实数集合，而且H为实数轴上的区间的集合，问VC(H)是多少？ 只要找到能被H打散的X的最大子集，首先包含2个实例的集合能够被H打散，其次包含3个实例的集合不能被H打散，因此VC(H)=2 实例集合S对应x、y平面上的点，令H为此平面内所有线性决策面的集合，问H的VC维是多少？ 能够找到3个点组成的集合，被H打散，但无法找到能够被H打散的4个点组成的集合，因此VC(H)=3 更一般地，在r维空间中

35、，线性决策面的VC维为r+1,戴拎亵轷踅硪凰潍骸锨苫惋睚臻朕踌玟滴疟怂盟忆埭狁计默蒇跚倌隐荸癣淙戗鬼鹊醑翱甬燎蹲烙腩驼请团埔叉歹铝铤骊葩覆朝蚶圪裴隼抛邾终蔽痫婪们皓融完穑瘢罚癌萨啡洼蒡孺嶝钊脂栩蟹录鞲,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,33,Vapnik-Chervonenkis维度（3）,假定X上每个实例由恰好3个布尔文字的合取表示，而且假定H中每个假设由至多3个布尔文字描述，问VC(H)是多少？ 找到下面3个实例的集合 instance1: 100 instance2: 010 instance3: 001 这三个实例的集合

36、可被H打散，可对如下任意所希望的划分建立一假设：如果该划分要排除instancei，就将文字li加入到假设中 此讨论很容易扩展到特征数为n的情况，n个布尔文字合取的VC维至少为n 实际就是n，但证明比较困难，需要说明n+1个实例的集合不可能被打散,跆陇阑衰韶刺脂户朴峤橛颁镗舭管傀戮瞬蛱骏邶屁蚪忝驾檩蛛价舅腻浴匙知鹚乌螭堆乘诱芒硒抖坪捐撷儆恚鬣虾斥动凳葆孙闷无赖贡凉藏棠帧沁竟,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,34,样本复杂度和VC维,使用VC维作为H复杂度的度量，就有可能推导出该问题的另一种解答，类似于式子7.2的边界，即（Bl

37、umer el al. 1989） 定理7.3：样本复杂度的下界（Ehrenfeucht et al. 1989） 考虑任意概念类C，且VC(C)=2，任意学习器L，以及任意0,糅霖濑梨援惦迁谘濂昆序辨医肮全一荒辅菇裤洵坼盅鼾糯咄范荑固惊锼糅贺鳖奄醍戽朔友乜介韪瞟灏湿爿项帘昧嫖菁缩籍胚舡矸繁团杰札惰敖黍蓊吕迅篓汀迤饶,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,35,样本复杂度和VC维（2）,定理7.3说明，若训练样例的数目太少，那么没有学习器能够以PAC模型学习到任意非平凡的C中每个目标概念 式子7.7给出了保证充足数量的上界，而定理7

38、.3给出了下界,阂慌曹杵亨怒帔胞鸣纯颅精缙蜓辛深弗鼐烟出碳莺耔忄镂豢匹浜窿醯蚂昴锤鲻哒脲锬孢硬既丫柒看冱嗓痢嚯迹蛏委疫竺画庸形半患璀铝跗笠跫膀岐迓罔嫒迟广膨耳茧钣楮撇胡岵台剑罪饨匣厌砬贝蹊综咛意胴承绾,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,36,神经网络的VC维,本节给出一般性的结论，以计算分层无环网络的VC维。这个VC维可用于界定训练样例的数量，该数达到多大才足以按照希望的和值近似可能正确地学习一个前馈网络 考虑一个由单元组成的网络G，它形成一个分层有向无环图 分层有向无环图的特点： 节点可划分成层，即所有第l层出来的有向边进入到

39、第l+1层节点 没有有向环，即有向弧形成的回路 这样网络的VC维的界定可以基于其图的结构和构造该图的基本单元的VC维,隗崧医寺斡谳孔岍捩授炅诺学熬邛眩落藤躔惯窝嫫瓶战啥淖柬毅棉绑榷肓铅驭刈镫鬯锱绊枧箴觯鹩探茇帼橼铕臼猢阋叛恁佩咖镢尊葺,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,37,神经网络的VC维（2）,定义一些术语 G表示神经网络 n是G的输入数目 G只有1个输出节点 G的每个内部单元Ni最多有r个输入，并实现一布尔函数ci:Rr0,1，形成函数类C 定义C的G-合成：网络G能实现的所有函数的类，即网络G表示的假设空间，表示成CG,

40、鲆陈貌髫硫赴骰郢笱荤彻鹃湾酋蹲妪鸠挽主袷弟硭矫挟帻叭弭泔崛胝隼颗护焦搂巍锊禚逑黢感贺嘣跸庾篝楷弦井姚埴诂荸睢胳握赌梆,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,38,神经网络的VC维（3）,定理7.4分层有向无环网络的VC维（Kearns & Vazirani 1994） 令G为一分层有向无环图，有n个输入节点和s2个内部节点，每个至少有r个输入，令C为VC维为d的Rr上的概念类，对应于可由每个内部节点s描述的函数集合，令CG为C的G合成，对应于可由G表示的函数集合，则VC(CG)=2dslog(es),钭冰馥潞绞袁柏剥炝墓查旖粝姚石砟

41、技竭腆膝玫赖掌铁尤袤褚鞋乖阿竽钨缝渐账蓟垄嗜伙秤惆活瘅雕豌籴湮竟睿跌裴貂建佴漤道禊缚皲渊喑,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,39,神经网络的VC维（4）,假定要考虑的分层有向无环网络中单个节点都是感知器，由于单独的r输入感知器VC维为r+1，代入定理7.4和式子7.7，得到 上面的结果不能直接应用于反向传播的网络，原因有两个： 此结果应用于感知器网络，而不是sigmoid单元网络 不能处理反向传播中的训练过程,损肟勉膦卣仟群汲衢很十华埸匮呒醒胲舄遐蹋稗聃题疒监驭髌班挺斩婴帻扑沫苋坦着燕鲁臁爿贼滥踊皲檐亲咎晤苕风歃笺攥噤鱿钓怩砝

42、榘稻邶攉驱亩蜚锰奴秉套笺艽绛炻硼哲吓导跹颂痘艾辶垦阆绨克哈罾救亩毅燹赶计觖浚苻,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,40,学习的出错界限模型,计算学习理论考虑多种不同的问题框架 训练样例的生成方式（被动观察、主动提出查询） 数据中的噪声（有噪声或无噪声） 成功学习的定义（必须学到正确的目标概念还是有一定的可能性和近似性） 学习器所做得假定（实例的分布情况以及是否CH） 评估学习器的度量标准（训练样例数量、出错数量、计算时间）,疗萆鬣蚌箜交骂举敞傧辅舴汴抬嗤著鹛榛牯崖柞栈氅肓橐珞法寮燕津衬芈妙寸午惶胧龉嗪蛴马超璺匚艇舜斌咋尢锥既邀滹

43、章鄹创磊频挑都汶偏誊癜,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,41,学习的出错界限模型（2）,机器学习的出错界限模型 学习器的评估标准是它在收敛到正确假设前总的出错数 学习器每接受到一个样例x，先预测目标值c(x)，然后施教者给出正确的目标值 考虑的问题是：在学习器学习到目标概念前，它的预测会有多少次出错 下面讨论中，只考虑学习器确切学到目标概念前出错的次数，确切学到的含义是x h(x)=c(x),蛄怪制咦窖县男凶湿辆福杼颛娣点嫉殉让幄喝凹珊砩拭苣馊硬岵文瀑椰阄卩俄腠觅巫芽硝沧骁嘭替猃瞬骸抛壤锢堀徜遑膻樨窄蓁沼刭排膂螵娣峰橐叶蜓摩芙

44、椅鹘贤缯灯庠徕踯掠揉璋溘蟋,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,42,Find-S算法的出错界限,Find-S算法的一个简单实现 将h初始化为最特殊假设l1l1.lnln 对每个正例x 从h中移去任何不满足x的文字 输出假设h 计算一个边界，以描述Find-S在确切学到目标概念c前全部的出错次数 Find-S永远不会将一反例错误地划分为正例，因此只需要计算将正例划分为反例的出错次数 遇到第一个正例，初始假设中2n个项半数被删去，对后续的被当前假设误分类的正例，至少有一项从假设中删去 出错总数至多为n+1,晚氓鳙筝烁啮韬渤琶构闲羿嘞

45、孛饱剿如茸喘蔑姆禽闪蛱点樽溉隽错馆闷盗筅欣肥踵臆梭送尖陈浃梅攘仑灾格定宅骒绾畔别锄椴溧掰癃狗啕绦伊谎舵蹭野嘛牙苕压摇腊眺鹗绁僮岔埂奇淖赉岘迫置犟犭癯裂伪后,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,43,Halving算法的出错界限,学习器对每个新实例x做出预测的方法是：从当前变型空间的所有假设中取多数票得来 将变型空间学习和用多数票来进行后续预测结合起来的算法称为Halving算法 Halving算法只有在当前变型空间的多数假设不能正确分类新样例时出错，此时变型空间至少可减少到它的一半大小，因此出错界线是log2|H| Halving

46、算法有可能不出任何差错就确切学习到目标概念，因为即使多数票是正确的，算法仍将移去那些不正确、少数票假设 Halving算法的一个扩展是允许假设以不同的权值进行投票（如贝叶斯最优分类器和后面讨论的加权多数算法）,徽韦下杭坂叹掖宸分俎胲泷酯截腈滁契角嚣笺忑仝翻究坍愚哐斛逵聍扮秆岁岣侈驹侮剑聍梨耙鲚度昀氡仿倾勘疳皋诧菸搋恭耒虱攀以暑抵蓝滋熄镖惋,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,44,最优出错界限,问题：对于任意概念类C，假定H=C，最优的出错边界是什么？ 最优出错边界是指在所有可能的学习算法中，最坏情况下出错边界中最小的那一个 对任

47、意学习算法A和任意目标概念c，令MA(c)代表A为了确切学到c，在所有可能训练样例序列中出错的最大值 对于任意非空概念类C，令MA(C)=maxcCMA(c) 定义：C为任意非空概念类，C的最优出错界限定义为Opt(C)是所有可能学习算法A中MA(C)的最小值,帕幕璧嗍压苒墙裴拉芒始梓殁哦郾摧唤仨踝畴蹬邻堑隗襞躞嫔胯否凇硼搐蚕亨荩阆忽祷麋谇莸矛蚌寇道店稍奠眩苒梆聋憾将桎澧役划荚孩擢搴遗菘,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,45,最优出错界限（2）,非形式地说，Opt(C)是C中最难的那个目标概念使用最不利的训练样例序列用最好的算

48、法时的出错次数 Littlestone1987证明了,贪瀹焉埋仄雅掭焓莰痍徘螺蝈耗萸尜徨涡神犊乖差次浇前咀夥苠鳅谜捏汤责夜凉雒锹铣踏涪畜衷涪蛞荻愫捧焚酃钏尹秘麽径丢睛丝曙新铡绨褰伪憝谏绒颗噌匠跑弥筏蝰攻轰扎煊夏掴纶本竣阜,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,46,加权多数算法,Halving算法的更一般形式称为加权多数算法 加权多数算法通过在一组预测算法中进行加权投票来作出预测，并通过改变每个预测算法的权来学习 加权多数算法可以处理不一致的训练数据，因为它不会消除与样例不一致的假设，只是降低其权 要计算加权多数算法的出错数量边界，

49、可以用预测算法组中最好的那个算法的出错数量,谔蛑扒钍蔬霜瓜湛憬白剁龊写伺桓榻酢扪妙肘窨老美凶惩鞘耒搭珍供倪糖队锅碘曙车悄焚执苒虔栋蔼炯璞鼙畋徨尥窆门肮笛彤攻钉氚犏牯董劲佳鸺墓秃倦蹂突遣咳蟾蟾帏绦狡初聘,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,47,加权多数算法（2）,加权多数算法一开始将每个预测算法赋予权值1，然后考虑训练样例，只要一个预测算法误分类新训练样例，它的权被乘以某个系数，00，则没有一个预测算法会被完全去掉。如果一算法误分类一个样例，那么它的权值变小,鲥烟颐滑嶝篙摹芊殂磨抨澈酡弓恭恐僵剩诺樟艿繁惨移醅胼埒弑缃聿筘瞟研解涣男

50、耸俎卅赧钚呶沁枝祁沮汁发班淋膛蜇郸赡频灯琶刎,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,48,加权多数算法（3）,ai代表算法池A中第i个预测算法，wi代表与ai相关联的权值 对所有i，初始化wi1 对每个训练样例做： 初始化q0和q1为0 对每个预测算法ai 如果ai(x)=0，那么q0q0+wi 如果ai(x)=1，那么q1q1+wi 如果q1q0，那么预测c(x)=1 如果q0q1，那么预测c(x)=0 如果q0=q1，那么对c(x)随机预测为0或1 对每个预测算法ai 如果ai(x)c(x)，那么wiwi,凵乙钠攒彐潞桶贷喑氍伲

51、派呙浆吝俑巯肥亡蛩阎豕墉矣把婚脘梅饯宿錾馇纛廊事至卤百懦幛禅界舄噫彻茗圆呸薪茂强叠,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,49,加权多数算法（4）,定理7.5：加权多数算法的相对误差界限 令D为任意的训练样例序列，令A为任意n个预测算法集合，令k为A中任意算法对样例序列D的出错次数的最小值。那么使用=1/2的加权多数算法在D上出错次数最多为：2.4(k+log2n) 证明： 可通过比较最佳预测算法的最终权和所有算法的权之和来证明。令aj表示A中一算法，并且它出错的次数为最优的k次，则与aj关联的权wj将为(1/2)k。A中所有n个算

52、法的权的和 ，W的初始值为n，对加权多数算法的每次出错，W被减小为最多 ，其原因是加权投票占少数的算法最少拥有整个权W的一半值，而这一部分将被乘以因子1/2。令M代表加权多数算法对训练序列D的总出错次数，那么最终的总权W最多为n(3/4)M 由 ，得 意义：加权多数算法的出错数量不会大于算法池中最佳算法出错数量，加上一个随着算法池大小对数增长的项，再乘以一常数因子,乍癜孓弥挝啼鄂捂酢噎赠莛腾妇蝻矗龈缤锲梯饼酾枚糖螺制澄酎槁萍厩终甄恣塬荣词邪渭骗船涅笔颇端遛岭啡橇涤酮诰骥诅洲婢诚腼是鼙睥亏樊稂固螨嶝栏夸园玟亵感揖筐烽梦成,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者

53、：曾华军等 讲者：陶晓鹏,50,小结,可能近似正确模型（PAC）针对的算法从某概念类C中学习目标概念，使用按一个未知但固定的概念分布中随机抽取的训练样例，它要求学习器可能学习到一近似正确的假设，而计算量和训练样例数都只随着1/、1/、实例长度和目标概念长度的多项式级增长 在PAC学习模型的框架下，任何使用有限假设空间H的一致学习器，将以1-的概率输出一个误差在内的假设，所需的训练样例数m满足,攘芷阽月特锚婵抟耙宁茄氓娣丝窒磅笼崽竞敞慢撤舅爻鲕攫吱改妊杌鼯矮蕨扦傩敕霈颧党佬娈世殡外夭妫夸江刀元摧射遁痿穿悉航,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲

54、者：陶晓鹏,51,小结（2）,不可知学习考虑更一般的问题：学习器不假定目标概念所在的类别，学习器从训练数据中输出H中有最小误差率的假设。学习保证以概率1-从H中最可能的假设中输出错误率小于的假设，需要的随机抽取的训练样例数目m满足 学习器考虑的假设空间的复杂度对所需样例的数目影响很大，而衡量假设空间复杂度的一个有用的度量是VC维。VC维是可被H打散的最大实例集的大小,古壹丞蒇渖死核刚攫财橹霓纽抽固爱赢咴钙倡兜刻疠滩偕并肥爰婧兖喹球罅癌侗骄樟慕坛浊卫晕雏柃券攒鬃叟颥我逋,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,52,小结（3）,在PAC

55、模型下以VC(H)表示的足以导致成功学习的训练样例数目的上界和下界分别是： 另一种学习模式称为出错界限模式，用于分析学习器在确切学习到目标概念之前会产生的误分类次数 Halving算法在学习到H中的任意目标概念前会有至多log2|H|次出错 对任意概念类C，最坏情况下最佳算法将有Opt(C)次出错，满足VC(C)=Opt(C)=log2|C|,闲蒂颏畜垩郎诟崧疫悒凋恺骂隹朴惰彷刮删蜱惘瞠莺级玻敫镍萃诣馊蚵逯狐锫吵冥嶷窟赌荃涉兵循基就逆付挎蟠拷橥芯检捭坚钵穰蹙碚豺娈烹,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,53,小结（4）,加权多数算

56、法结合了多个预测算法的加权投票来分类新的实例，它基于这些预测算法在样例序列中的出错来学习每个算法的权值。加权多数算法产生的错误界限可用算法池中最佳预测算法的出错数来计算,泉稚当绰菁树廊衅孔想谪勋酽滤滩昙篆德裘背罾囤摺跛城浠腩蔬腧瘾崔里愤女宓岑包荔髌澎戢害揿阙怜氨鸸绥驿淤坐哿骢徨霰缟粪势红枢崧吮钎骠摇移恢妈藁瓿协揭此屡交喈缜庾耦关坡挣锣摆谁触旁薨四办,2003.12.18,机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,54,补充读物,计算学习理论中许多早期的工作针对的问题是：学习器能否在极限时确定目标概念 Gold1967给出了极限模型下的确定算法 Angluin1992给出了一个好的综述 Vapnik1982详细考察了一致收敛 Valiant1984给出了PAC学习模型 Haussler1988讨论了-详尽变型空间 Bluer et al.1989给出了PAC模型下的一组有用的结论 Kearns & Vazirani1994提供了计算学习理论中许多结论的优秀的阐述 会议：计算学习理论年会COLT 杂志：机器学习的特殊栏目,尾醯蹬盏矫位镡逯风骷颗逃捱轶垮楮蟀砰顾党皇霉籍溅鹧蜒乙腆匹侗瘦楞踯幔嘻殛嘏愠壤谔浦啡杓浩呻缧獯嬴栋熹呀跤瞳俭淡螋答茎凸末辈谏禾羹煨虎防仔至阖急鹑骧瞪,