7-计算学习理论.pptVIP

第七章 计算机学习理论 7.1 简介 在研究机器学习的过程中,学习器应遵循什么样的规则? 是否能够独立于学习算法确定学习问题中固有的难度? 能否知道为保证成功的学习有多少训练样例是必要的和充足的? 如果学习器被允许想施教者提出查询,而不是观察训练集的随机样本,会对所需样例数目有怎样的影响? 能否刻画出学习器在学习目标函数前回有多少次出错? 能否刻画出一类学习问题中固有的计算复杂度? 在这里我们着重讨论只给定目标函数的训练样例和候选假设空间的条件下,对该未知的目标函数的归纳学习问题. 主要要解决的问题如:需要多少训练样例才足以成功的学习到目标函数以及学习器在达到目标前会出多少次错. 后面将对以上的问题提出定量的上下界,这基于学习问题的如下属性: 学习器所考虑的假设空间的大小和复杂度 目标概念须近似到怎样的精度 学习器输出成功的假设的可能性 训练样例提供给学习器的方式 我们学习本章的目标的就是为了回答以下的问题: 样本复杂度:学习器要收敛到成功假设(以较高的概率),需要多少的训练样例? 计算复杂度:学习器要收敛到成功假设(以较高的概率)需要多大计算量? 出错界限:在成功收敛到一个假设前,学习器对训练样例的错误分类有多少次? 注意:为解决这些问题需要许多特殊的条件设定. 如:有许多方法来指定对于学习器什么是”成功的”. 一种可能判断的方法是:学习器是否输出等于目标函数的假设.另一种方法是:只要求输出的假设与目标函数在多数的时间内意见是一致,或是学习器通常会输出这样的假设. 如:学习器是如何获得训练样例的? 可以指定训练样例由一个施教者给出,或由学习器自己实验得到,或按照某过程随机的生成而不受学习器的控制. 对于以上问题的回答以来我们所考虑的特定框架或学习模型 7.2 可能学习近似正确假设 这节我们学习一种特殊的框架---可能学习近似正确(probably approximately correct,PAC)学习模型. 首先我们指定PAC学习模型适用的问题,然后分析在此模型下学习不同类别的目标函数需要多少训练样例和多大计算量. 前提:这里的讨论将限制在学习布尔值的概念,且训练 数据是无噪声. 7.2.1 问题框架 另X代表所有实例的集合,目标函数在其上定义.每个实例由属性来描述. 另C代表学习器要代表的目标概念集合.C中的每个目标概念c对应于X的某个子集或一个等效的布尔函数c:X?{0, 1} 实例按照某概率分布D从X中随机的产生.一般D,可为任何分布,而且它对学习器是未知的.对于D,所要求是它的稳定性,既该分布不会随时间的变化. 训练样例的生成按照分布D随机抽取实例x,然后x及其目标值c(x)被提供给学习器. 学习器L在学习目标概念时考虑可能的假设集合H.(H可为所有属性的合取表示的假使的集合.) 在观察了一系列目标概念c的训练样例后,L必须从H中输出某假设h,他是对c的估计.我们通过h在从X中抽取的新实例上性能来评估L是否成功.抽取过程按照分布D,即与产生训练样例相同的概率分布. 在此框架下,我们感兴趣的是刻画不同的学习器L的性能,这些学习器使用不同的假设空间H,并学习不同类别的C中的目标概念.由于我们要求L足够一般,以至可以学到任何目标概念而不管训练样例的分布如何,所以我们经常会对C中所有可能的目标概念和所有可能的实例分布进行最差的分析. 7.2.2 假设的错误率 定义:假设h的关于目标概念c和分布D的真实错误率为h误分类根据D随机抽取的实例的概率. 图7-1显示了该错误率的定义.概念c和h被表示为X中标为正例的实例集合.h关于c的错误率为随机选取的实例落入和不一致的区间(即它们的集合差)的概率. 注意:错误率定义在整个的分布上,而不只是训练样例上,因为它是实际应用此假设h到后续实例上时会遇到真实的错误率. 注意:此错误率紧密的依赖于未知的概率分布D, 例如:如果D是一个均匀的概率分布,它对X中的每个实例都赋予相同的概率.那么假设的错误率为h和c不一致的空间在全部实例空间中的比例.然而,如果D恰好把h和c不一致的区间中的实例赋予了很高的概率,相同的h和c将造成更高的错误率.极端的情况下,若D对满足h(x)=c(x)的所有的实例赋予零概率,图中的错误率将为1,而不论在多少实例上分类一致. 最后,注意h关于c的错误率不能直接有学习器观察到.L只能观察到在训练样例上h的性能,它也只能在此基础上选择其假设输出.用术语训练错误率来指代训练样例中被误分类的样例所占的比例,以区分真实错误率.这里关于学习复杂度的分析多数围绕着这样的问题:”的观察到的训练错误率对真实错误率产生不正确估计的可能性有多大?”. PAC可学习性 我们的目标是刻画出这样的目标概念