机器学习 第7章计算学习理论 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 1 机器学习 第7章 计算学习理论
概述 本章从理论上刻画了若干类型的机器学习问题中的困 难和若干类型的机器学习算法的能力 这个理论要回答的问题是: 在什么样的条件下成功的学习是可能的? 在什么条件下某个特定的学习算法可保证成功运行? 这里考虑两种框架: 可能近似正确(PAC) ·确定了若干假设类别,判断它们能否从多项式数量的训练样例中 学习得到 定义了一个对假设空间复杂度的自然度量,由它可以界定归纳学 习所需的训练样例数目 出错界限框架 ·考査了一个学习器在确定正确假设前可能产生的训练错误数量 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏 2
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 2 概述 • 本章从理论上刻画了若干类型的机器学习问题中的困 难和若干类型的机器学习算法的能力 • 这个理论要回答的问题是： – 在什么样的条件下成功的学习是可能的？ – 在什么条件下某个特定的学习算法可保证成功运行？ • 这里考虑两种框架： – 可能近似正确（PAC） • 确定了若干假设类别，判断它们能否从多项式数量的训练样例中 学习得到 • 定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学 习所需的训练样例数目 – 出错界限框架 • 考查了一个学习器在确定正确假设前可能产生的训练错误数量
简介 机器学习理论的一些问题: 是否可能独立于学习算法确定学习问题中固有的难 度? 能否知道为保证成功的学习有多少训练样例是必要 的或充足的? 如果学习器被允许向施教者提出查询,而不是观察 训练集的随机样本,会对所需样例数目有怎样的影 响? 能否刻画出学习器在学到目标函数前会有多少次出 错 能否刻画出一类学习问题中固有的计算复杂度? 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 3 简介 • 机器学习理论的一些问题： – 是否可能独立于学习算法确定学习问题中固有的难 度？ – 能否知道为保证成功的学习有多少训练样例是必要 的或充足的？ – 如果学习器被允许向施教者提出查询，而不是观察 训练集的随机样本，会对所需样例数目有怎样的影 响？ – 能否刻画出学习器在学到目标函数前会有多少次出 错？ – 能否刻画出一类学习问题中固有的计算复杂度？
简介(2) 对所有这些问题的一般回答还未知,但不完整 的学习计算理论已经开始出现 本章阐述了该理论中的一些关键结论,并提供 了在特定问题下一些问题的答案 ·主要讨论在只给定目标函数的训练样例和候选 假设空间的条件下,对该未知目标函数的归纳 学习问题 主要要解决的问题是:需要多少训练样例才足 以成功地学习到目标函数以及学习器在达到目 标前会出多少次错 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 4 简介（2） • 对所有这些问题的一般回答还未知，但不完整 的学习计算理论已经开始出现 • 本章阐述了该理论中的一些关键结论，并提供 了在特定问题下一些问题的答案 • 主要讨论在只给定目标函数的训练样例和候选 假设空间的条件下，对该未知目标函数的归纳 学习问题 • 主要要解决的问题是：需要多少训练样例才足 以成功地学习到目标函数以及学习器在达到目 标前会出多少次错
简介(3) 如果明确了学习问题的如下属性,那么有可能给出前 面问题的定量的上下界 学习器所考虑的假设空间的大小和复杂度 目标概念须近似到怎样的精度 学习器输出成功的假设的可能性 训练样例提供给学习器的方式 本章不会着重于单独的学习算法,而是在较宽广的学 习算法类别中考虑问题 样本复杂度:学习器要收敛到成功假设,需要多少训练样例? 计算复杂度:学习器要收敛到成功假设,需要多大的计算量? 出错界限:在成功收敛到一个假设前,学习器对训练样例的 错误分类有多少次? 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 5 简介（3） • 如果明确了学习问题的如下属性，那么有可能给出前 面问题的定量的上下界 – 学习器所考虑的假设空间的大小和复杂度 – 目标概念须近似到怎样的精度 – 学习器输出成功的假设的可能性 – 训练样例提供给学习器的方式 • 本章不会着重于单独的学习算法，而是在较宽广的学 习算法类别中考虑问题： – 样本复杂度：学习器要收敛到成功假设，需要多少训练样例？ – 计算复杂度：学习器要收敛到成功假设，需要多大的计算量？ – 出错界限：在成功收敛到一个假设前，学习器对训练样例的 错误分类有多少次？
简介(4) 为了解决这些问题需要许多特殊的条件设定 比如 “成功”的学习器的设定 ·学习器是否输出等于目标概念的假设 ·只要求输出的假设与目标概念在多数时间内意见一致 ·学习器通常输出这样的假设 学习器如何获得训练样例 由一个施教者给出 ·由学习器自己实验获得 ·按照某过程随机生成 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 6 简介（4） • 为了解决这些问题需要许多特殊的条件设定， 比如 – “成功”的学习器的设定 • 学习器是否输出等于目标概念的假设 • 只要求输出的假设与目标概念在多数时间内意见一致 • 学习器通常输出这样的假设 – 学习器如何获得训练样例 • 由一个施教者给出 • 由学习器自己实验获得 • 按照某过程随机生成
简介(5) 72节介绍可能近似正确(PAC)学习框架 73节在PAC框架下,分析几种学习算法的样本 复杂度和计算复杂度 ·74节介绍了假设空间复杂度的一个重要度量标 准,称为VC维,并且将PAC分析扩展到假设空 间无限的情况 75节介绍出错界限模型,并提供了前面章节中 几个学习算法出错数量的界限,最后介绍了加 权多数算法 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 7 简介（5） • 7.2节介绍可能近似正确（PAC）学习框架 • 7.3节在PAC框架下，分析几种学习算法的样本 复杂度和计算复杂度 • 7.4节介绍了假设空间复杂度的一个重要度量标 准，称为VC维，并且将PAC分析扩展到假设空 间无限的情况 • 7.5节介绍出错界限模型，并提供了前面章节中 几个学习算法出错数量的界限，最后介绍了加 权多数算法
可能学习近似正确假设 可能近似正确学习模型(PAC) 指定PAC学习模型适用的问题 在此模型下,学习不同类别的目标函数需要 多少训练样例和多大的计算量 本章的讨论将限制在学习布尔值概念, 且训练数据是无噪声的(许多结论可扩 展到更一般的情形) 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 8 可能学习近似正确假设 • 可能近似正确学习模型（PAC） – 指定PAC学习模型适用的问题 – 在此模型下，学习不同类别的目标函数需要 多少训练样例和多大的计算量 • 本章的讨论将限制在学习布尔值概念， 且训练数据是无噪声的（许多结论可扩 展到更一般的情形）
问题框架 Ⅹ表示所有实例的集合,C代表学习器要学习的目标概念集合,C 中每个目标概念c对应于X的某个子集或一个等效的布尔函数c X→>{0,1} ·假定实例按照某概率分布D从X中随机产生 学习器L在学习目标概念时考虑可能假设的集合H。在观察了一系 列关于目标概念c的训练样例后,L必须从H中输出某假设h,它是 对c的估计 我们通过h在从ⅹ中抽取的新实例上的性能来评估L是否成功。新 实例与训练数据具有相同的概率分布 我们要求L足够一般,以至可以从C中学到任何目标概念而不管训 练样例的分布如何,因此,我们会对C中所有可能的目标概念和 所有可能的实例分布D进行最差情况的分析 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 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进行最差情况的分析
假设的错误率 为了描述学习器输出的假设h对真实目标 概念的逼近程度,首先要定义偎设h对应 于目标概念c和实例分布D的真实错误率 h的真实错误率是应用h到将来按分布D抽 取的实例时的期望的错误率 定义:假设h的关于目标概念c和分布D的 真实错误率为h误分类根据D随机抽取的 实例的概率 errorD(h)= Pr[c(x)*h(x)I 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 10 假设的错误率 • 为了描述学习器输出的假设h对真实目标 概念的逼近程度，首先要定义假设h对应 于目标概念c和实例分布D的真实错误率 • h的真实错误率是应用h到将来按分布D抽 取的实例时的期望的错误率 • 定义：假设h的关于目标概念c和分布D的 真实错误率为h误分类根据D随机抽取的 实例的概率 error (h) Prc(x) h(x) x D D