机器学习 第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） • 如果明确了学习问题的如下属性，那么有可能给出前 面问题的定量的上下界 – 学习器所考虑的假设空间的大小和复杂度 – 目标概念须近似到怎样的精度 – 学习器输出成功的假设的可能性 – 训练样例提供给学习器的方式 • 本章不会着重于单独的学习算法，而是在较宽广的学 习算法类别中考虑问题： – 样本复杂度：学习器要收敛到成功假设，需要多少训练样例？ – 计算复杂度：学习器要收敛到成功假设，需要多大的计算量？ – 出错界限：在成功收敛到一个假设前，学习器对训练样例的 错误分类有多少次？