概述 本章从理论上刻画了若干类型的机器学习问题中的困 难和若干类型的机器学习算法的能力 这个理论要回答的问题是: 在什么样的条件下成功的学习是可能的? 在什么条件下某个特定的学习算法可保证成功运行? 这里考虑两种框架: 可能近似正确(PAC) ·确定了若干假设类别,判断它们能否从多项式数量的训练样例中 学习得到 定义了一个对假设空间复杂度的自然度量,由它可以界定归纳学 习所需的训练样例数目 出错界限框架 ·考査了一个学习器在确定正确假设前可能产生的训练错误数量 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏 22003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 2 概述 • 本章从理论上刻画了若干类型的机器学习问题中的困 难和若干类型的机器学习算法的能力 • 这个理论要回答的问题是： – 在什么样的条件下成功的学习是可能的？ – 在什么条件下某个特定的学习算法可保证成功运行？ • 这里考虑两种框架： – 可能近似正确（PAC） • 确定了若干假设类别，判断它们能否从多项式数量的训练样例中 学习得到 • 定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学 习所需的训练样例数目 – 出错界限框架 • 考查了一个学习器在确定正确假设前可能产生的训练错误数量