《计算学习理论未讲》PPT课件VIP

2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,1,机器学习,第7章计算学习理论,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,2,概述,本章从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力这个理论要回答的问题是：在什么样的条件下成功的学习是可能的？在什么条件下某个特定的学习算法可保证成功运行？这里考虑两种框架：可能近似正确（PAC）确定了若干假设类别，判断它们能否从多项式数量的训练样例中学习得到定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学习所需的训练样例数目出错界限框架考查了一个学习器在确定正确假设前可能产生的训练错误数量,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,3,简介,机器学习理论的一些问题：是否可能独立于学习算法确定学习问题中固有的难度？能否知道为保证成功的学习有多少训练样例是必要的或充足的？如果学习器被允许向施教者提出查询，而不是观察训练集的随机样本，会对所需样例数目有怎样的影响？能否刻画出学习器在学到目标函数前会有多少次出错？能否刻画出一类学习问题中固有的计算复杂度？,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,4,简介（2）,对所有这些问题的一般回答还未知，但不完整的学习计算理论已经开始出现本章阐述了该理论中的一些关键结论，并提供了在特定问题下一些问题的答案主要讨论在只给定目标函数的训练样例和候选假设空间的条件下，对该未知目标函数的归纳学习问题主要要解决的问题是：需要多少训练样例才足以成功地学习到目标函数以及学习器在达到目标前会出多少次错,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,5,简介（3）,如果明确了学习问题的如下属性，那么有可能给出前面问题的定量的上下界学习器所考虑的假设空间的大小和复杂度目标概念须近似到怎样的精度学习器输出成功的假设的可能性训练样例提供给学习器的方式本章不会着重于单独的学习算法，而是在较宽广的学习算法类别中考虑问题：样本复杂度：学习器要收敛到成功假设，需要多少训练样例？计算复杂度：学习器要收敛到成功假设，需要多大的计算量？出错界限：在成功收敛到一个假设前，学习器对训练样例的错误分类有多少次？,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,6,简介（4）,为了解决这些问题需要许多特殊的条件设定，比如“成功”的学习器的设定学习器是否输出等于目标概念的假设只要求输出的假设与目标概念在多数时间内意见一致学习器通常输出这样的假设学习器如何获得训练样例由一个施教者给出由学习器自己实验获得按照某过程随机生成,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,7,简介（5）,7.2节介绍可能近似正确（PAC）学习框架7.3节在PAC框架下，分析几种学习算法的样本复杂度和计算复杂度7.4节介绍了假设空间复杂度的一个重要度量标准，称为VC维，并且将PAC分析扩展到假设空间无限的情况7.5节介绍出错界限模型，并提供了前面章节中几个学习算法出错数量的界限，最后介绍了加权多数算法,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,8,可能学习近似正确假设,可能近似正确学习模型（PAC）指定PAC学习模型适用的问题在此模型下，学习不同类别的目标函数需要多少训练样例和多大的计算量本章的讨论将限制在学习布尔值概念，且训练数据是无噪声的（许多结论可扩展到更一般的情形）,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,9,问题框架,X表示所有实例的集合，C代表学习器要学习的目标概念集合，C中每个目标概念c对应于X的某个子集或一个等效的布尔函数c:X0,1假定实例按照某概率分布D从X中随机产生学习器L在学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后，L必须从H中输出某假设h，它是对c的估计我们通过h在从X中抽取的新实例上的性能来评估L是否成功。新实例与训练数据具有相同的概率分布我们要求L足够一般，以至可以从C中学到任何目标概念而不管训练样例的分布如何，因此，我们会对C中所有可能的目标概念和所有可能的实例分布D进行最差情况的分析,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,10,假设的错误率,为了描述学习器输出的假设h对真实目标概念的逼近程度，首先要定义假设h对应于目标概念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中假设的错误率为h和c不一致的空间在全部实例空间中的比例如果D恰好把h和c不一致区间中的实例赋予了很高的概率，相同的h和c将造成更高的错误率h关于c的错误率不能直接由学习器观察到，L只能观察到在训练样例上h的性能训练错误率：指代训练样例中被h误分类的样例所占的比例问题：h的观察到的训练错误率对真实错误率产生不正确估计的可能性多大？,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,12,PAC可学习性,我们的目标是刻画出这样的目标概念，它们能够从合理数量的随机抽取训练样例中通过合理的计算量可靠地学习对可学习性的表述一种可能的选择：为了学习到使errorD(h)=0的假设h，所需的训练样例数这样的选择不可行：首先要求对X中每个可能的实例都提供训练样例；其次要求训练样例无误导性可能近似学习：首先只要求学习器输出错误率限定在某常数范围内的假设，其次要求对所有的随机抽取样例序列的失败的概率限定在某常数范围内只要求学习器可能学习到一个近似正确的假设,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,13,PAC可学习性（2）,PAC可学习性的定义考虑定义在长度为n的实例集合X上的一概念类别C，学习器L使用假设空间H。当对所有cC，X上的分布D，和满足0,=1个独立随机抽取的样例，那么对于任意0=q1，那么预测c(x)=0如果q0=q1，那么对c(x)随机预测为0或1对每个预测算法ai如果ai(x)c(x)，那么wiwi,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个算法的权的和，W的初始值为n，对加权多数算法的每次出错，W被减小为最多，其原因是加权投票占少数的算法最少拥有整个权W的一半值，而这一部分将被乘以因子1/2。令M代表加权多数算法对训练序列D的总出错次数，那么最终的总权W最多为n(3/4)M由，得意义：加权多数算法的出错数量不会大于算法池中最佳算法出错数量，加上一个随着算法池大小对数增长的项，再乘以一常数因子,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,50,小结,可能近似正确模型（PAC）针对的算法从某概念类C中学习目标概念，使用按一个未知但固定的概念分布中随机抽取的训练样例，它要求学习器可能学习到一近似正确的假设，而计算量和训练样例数都只随着1/、1/、实例长度和目标概念长度的多项式级增长在PAC学习模型的框架下，任何使用有限假设空间H的一致学习器，将以1-的概率输出一个误差在内的假设，所需的训练样例数m满足,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,51,小结（2）,不可知学习考虑更一般的问题：学习器不假定目标概念所在的类别，学习器从训练数据中输出H中有最小误差率的假设。学习保证以概率1-从H中最可能的假设中输出错误率小于的假设，需要的随机抽取的训练样例数目m满足学习器考虑的假设空间的复杂度对所需样例的数目影响很大，而衡量假设空间复杂度的一个有用的度量是VC维。VC维是可被H打散的最大实例集的大小,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,52,小结（3）,在PAC模型下以VC(H)表示的足以导致成功学习的训练样例数目的上界和下界分别是：另一种学习模式称为出错界限模式，用于分析学习器在确切学习到目标概念之前会产生的误分类次数Halving算法在学习到H中的任意目标概念前会有至多log2|H|次出错对任意概念类C，最坏情况下最佳算法将有Opt(C)次出错，满足VC(C)=Opt(C)=log2|C|,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,53,小结（4）,加权多数算法结合了多个预测算法的加权投票来分类新的实例，它基于这些预测算法在样例序列中的出错来学习每个算法的权值。加权多数算法产生的错误界限可用算法池中最佳预测算法的出错数来计算,2003.12.18,机器学习-计算学习理论作者：Mitchell译者：曾华军等讲者：陶晓鹏,54,补充读物,计算学习理论中许多早期的工作针对