计算学习理论

机器学习与数据挖掘第7章计算学习理论1概述•本章从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力•这个理论要回答的问题是：–在什么样的条件下成功的学习是可能的？–在什么条件下某个特定的学习算法可保证成功运行？•这里考虑两种框架：–可能近似正确（PAC）•确定了若干假设类别，判断它们能否从多项式数量的训练样例中学习得到•定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学习所需的训练样例数目–出错界限框架•考查了一个学习器在确定正确假设前可能产生的训练错误数量2简介（1）•机器学习理论的一些问题：–是否可能独立于学习算法确定学习问题中固有的难度？–能否知道为保证成功的学习有多少训练样例是必要的或充足的？–如果学习器被允许向施教者提出查询，而不是观察训练集的随机样本，会对所需样例数目有怎样的影响？–能否刻画出学习器在学到目标函数前会有多少次出错？–能否刻画出一类学习问题中固有的计算复杂度？3何为PAC?•PAC（ProbablyApproximatelyCorrect,概率近似正确),该模型可解决信息分类的问题，比如判断一份邮件是不是SPAM。为解决信息分类问题，学习算法会根据过去的经验设计一个概率假设，并将此假设作为判断依据。然而，这种根据过去经验的泛华可能并不适用于将来，比如过渡泛华。PAC模型可最大限度地降低泛化带来的错误，这就是它为什么被称为“概率近似正确”的原因。4简介（2）•对所有这些问题的一般回答还未知，但不完整的学习计算理论已经开始出现•本章阐述了该理论中的一些关键结论，并提供了在特定问题下一些问题的答案•主要讨论在只给定目标函数的训练样例和候选假设空间的条件下，对该未知目标函数的归纳学习问题•主要要解决的问题是：需要多少训练样例才足以成功地学习到目标函数以及学习器在达到目标前会出多少次错5简介（3）•如果明确了学习问题的如下属性，那么有可能给出前面问题的定量的上下界–学习器所考虑的假设空间的大小和复杂度–目标概念须近似到怎样的精度–学习器输出成功的假设的可能性–训练样例提供给学习器的方式•本章不会着重于单独的学习算法，而是在较宽广的学习算法类别中考虑问题：–样本复杂度：学习器要收敛到成功假设，需要多少训练样例？–计算复杂度：学习器要收敛到成功假设，需要多大的计算量？–出错界限：在成功收敛到一个假设前，学习器对训练样例的错误分类有多少次？6简介（4）•为了解决这些问题需要许多特殊的条件设定，比如–“成功”的学习器的设定•学习器是否输出等于目标概念的假设•只要求输出的假设与目标概念在多数时间内意见一致•学习器通常输出这样的假设–学习器如何获得训练样例•由一个施教者给出•由学习器自己实验获得•按照某过程随机生成7简介（5）•7.2节介绍可能近似正确（PAC）学习框架•7.3节在PAC框架下，分析几种学习算法的样本复杂度和计算复杂度•7.4节介绍了假设空间复杂度的一个重要度量标准，称为VC维，并且将PAC分析扩展到假设空间无限的情况•7.5节介绍出错界限模型，并提供了前面章节中几个学习算法出错数量的界限，最后介绍了加权多数算法8可能学习近似正确假设•可能近似正确学习模型（PAC）–指定PAC学习模型适用的问题–在此模型下，学习不同类别的目标函数需要多少训练样例和多大的计算量•本章的讨论将限制在学习布尔值概念，且训练数据是无噪声的（许多结论可扩展到更一般的情形）9问题框架•X表示所有实例的集合，C代表学习器要学习的目标概念集合，C中每个目标概念c对应于X的某个子集或一个等效的布尔函数c:X{0,1}•假定实例按照某概率分布D从X中随机产生•学习器L在学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后，L必须从H中输出某假设h，它是对c的估计•我们通过h在从X中抽取的新实例上的性能来评估L是否成功。新实例与训练数据具有相同的概率分布•我们要求L足够一般，以至可以从C中学到任何目标概念而不管训练样例的分布如何，因此，我们会对C中所有可能的目标概念和所有可能的实例分布D进行最差情况的分析10•1、可用数据样本上该假设的错误率称为样本错误率。•2、分布为D的整个实例集合上该假设的错误率称为真是错误率。11假设的错误率•为了描述学习器输出的假设h对真实目标概念的逼近程度，首先要定义假设h对应于目标概念c和实例分布D的真实错误率•h的真实错误率是应用h到将来按分布D抽取的实例时的期望的错误率12•定义：假设h的关于目标概念c和分布D的真实错误率为h误分类根据D随机抽取的实例的概率13)()(Pr)(xhxcherrorDxD图7-1此错误率紧密依赖于未知的概率分布D，图7-1：h关于c的错误率是随机选取的实例落入h和c不一致的区间的概率14假设的错误率（2）•真实错误率紧密地依赖于未知的概率分布D–如果D是一个均匀的概率分布，那么图7-1中假设的错误率为h和c不一致的空间在全部实例空间中的比例–如果D恰好把h和c不一致区间中的实例赋予了很高的概率，相同的h和c将造成更高的错误率•h关于c的错误率不能直接由学习器观察到，L只能观察到在训练样例上h的性能•训练错误率：指代训练样例中被h误分类的样例所占的比例•问题：h的观察到的训练错误率对真实错误率产生不正确估计的可能性多大？15PAC可学习性（1）•我们的目标是刻画出这样的目标概念，它们能够从合理数量的随机抽取训练样例中通过合理的计算量可靠地学习•对可学习性的表述–一种可能的选择：为了学习到使errorD(h)=0的假设h，所需的训练样例数•这样的选择不可行：首先要求对X中每个可能的实例都提供训练样例；其次要求训练样例无误导性–可能近似学习：首先只要求学习器输出错误率限定在某常数范围内的假设，其次要求对所有的随机抽取样例序列的失败的概率限定在某常数范围内•只要求学习器可能学习到一个近似正确的假设16PAC可学习性（2）17PAC可学习性（3）•在实践中，通常更关心所需的训练样例数，–如果L对每个训练样例需要某最小处理时间，那么为了使c是L可PAC学习的，L必须从多项式数量的训练样例中进行学习–实际上，为了显示某目标概念类别C是可PAC学习的，一个典型的途径是证明C中每个目标概念可以从多项式数量的训练样例中学习到，且处理每个样例的时间也是多项式级•PAC可学习性的一个隐含的条件：对C中每个目标概念c，假设空间H都包含一个以任意小误差接近c的假设18•上面定义要求学习器L满足两个条件–L必须以任意高的概率（1-）输出一个错误率任意低（）的假设–学习过程必须是高效的，其时间最多以多项式方式增长•上面定义的说明–1/和1/表示了对输出假设要求的强度，n和size(c)表示了实例空间X和概念类别C中固有的复杂度–n为X中实例的长度，size(c)为概念c的编码长度19VC维与模型复杂度、样本复杂度•我们引入了VC维的概念，用它来描述假设集合的表达能力。我们将从VC维的物理意义出发，进一步学习如何根据VC维传达的信息来选择模型和假设集合。•现在，我们用VC维这个工具来描述。20VC维与模型复杂度、样本复杂度•VC维的物理意义•如果我们将假设集合的数量|H|比作假设集合的自由度，那么VC维就是假设集合在做二元分类的有效的自由度，即这个假设空间能够产生多少Dichotomies的能力（VC维说的是，到什么时候，假设集合还能shatter，还能产生最多的Dichotomies）。21VC维与模型复杂度、样本复杂度•VC维、真实错误率、训练错误率•在上一节中，我们讨论要做到好的预测要满足两个条件，第一是训练误差要接近真实误差，即Ein(g)约等于Eout(g)；第二是训练误差要尽量接近0，即Ein(g)约等于0。22vc维与模型复杂度、样本复杂度•如果VC维很小，那么发生预测偏差很大的坏事情的可能性也就很小，那这有利于Ein(g)接近Eout(g)；但是，这是我们的假设空间的表达能力受到了限制，这样Ein(g)可能就没有办法做到很小。23有限假设空间的样本复杂度•PAC可学习性很大程度上由所需的训练样例数确定•随着问题规模的增长所带来的所需训练样例的增长称为该学习问题的样本复杂度•我们把样本复杂度的讨论限定于一致学习器（输出完美拟合训练数据的学习器）•能够独立于特定算法，推导出任意一致学习器所需训练样例数的界限•变型空间：能正确分类训练样例D的所有假设的集合。24•如果VC维很大，那么假设空间的表达能力很强，我们很有可能选到一个Ein(g)很小的假设，但是Ein(g)和Eout(g)之差很大的坏事情发生的情况发生的可能性就变得很大，这样Ein(g)和Eout(g)根本不接近，我们就无法确定选择的假设在测试数据的时候表现的很好。25有限假设空间的样本复杂度（1）26))}()(()(,(|{,xcxhDxcxHhVSDH变型空间：能正确分类训练样例D的所有假设的集合有限假设空间的样本复杂度（2）•变型空间的重要意义是：每个一致学习器都输出一个属于变型空间的假设•因此界定任意一个一致学习器所需的样例数量，只需要界定为保证变型中没有不可接受假设所需的样例数量27•定义：考虑一假设空间H，目标概念c，实例分布D以及c的一组训练样例S。当VSH,D中每个假设h关于c和D错误率小于时，变型空间被称为c和D是-详尽的。28)()(,herrorVShDDH有限假设空间的样本复杂度（3）•-详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于•从学习器的角度看，所能知道的只是这些假设能同等地拟合训练数据，它们都有零训练错误率•只有知道目标概念的观察者才能确定变型空间是否为-详尽的29有限假设空间的样本复杂度（4）•但是，即使不知道确切的目标概念或训练样例抽取的分布，一种概率方法可在给定数目的训练样例之后界定变型空间为-详尽的•定理7.1（变型空间的-详尽化）–若假设空间H有限，且D为目标概念c的一系列m=1个独立随机抽取的样例，那么对于任意0==1，变型空间VSH,D不是-详尽的概率小于或等于：meH||30•证明：–令h1,...,hk为H中关于c的真实错误率大于的所有假设。当且仅当k个假设中至少有一个恰好与所有m个独立随机抽取样例一致时，不能使变型空间-详尽化。–任一假设真实错误率大于，且与一个随机抽取样例一致的可能性最多为1-，因此，该假设与m个独立抽取样例一致的概率最多为(1-)m–由于已知有k个假设错误率大于，那么至少有一个与所有m个训练样例都不一致的概率最多为（当，则）3110e1mmmeHHk||)1(||)1(有限假设空间的样本复杂度（5）•定理7.1基于训练样例的数目m、允许的错误率和H的大小，给出了变型空间不是-详尽的概率的上界•即它对于使用假设空间H的任意学习器界定了m个训练样例未能将所有“坏”的假设（错误率大于的假设）剔除出去的概率32•利用上面的结论来确定为了减少此“未剔除”概率到一希望程度所需的训练样例数–由–解出m，得到––（7-2）式33meH||)/1ln(||ln1Hm有限假设空间的样本复杂度（6）•式子7.2提供了训练样例数目的一般边界，该数目的样例足以在所期望的值和程度下，使任何一致学习器成功地学习到H中的任意目标概念•训练样例的数目m足以保证任意一致假设是可能（可能性为1-）近似（错误率为）正确的•m随着1/线性增长，随着1/和假设空间的规模对数增长34有限假设空间的样本复杂度•上面的界限可能是过高的估计，主要来源于|H|项，它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和•在7.4节讨论一个更紧凑的边界以及能够覆盖无限大的假设空间的边界35不可知学习和不一致假设（1）•如果学习器不假定目标概念可在H中表示，而只简单地寻找具有最小训练错误率的假设，这样的学习器称为不可知学习器•式7.2基于的假定是学习器输出一零错误率假设，在更一般的