假设的错误率(2) 图7-1:h关于c的错误率是随机选取的实例落入h和c不一致的区间 的概率 真实错误率紧密地依赖于未知的概率分布D 如果D是一个均匀的概率分布,那么图7-1中假设的错误率为h和c不 致的空间在全部实例空间中的比例 如果D恰好把h和c不一致区间中的实例赋予了很高的概率,相同的h 和c将造成更高的错误率 h关于c的错误率不能直接由学习器观察到,L只能观察到在训练 样例上h的性能 训练错误率:指代训练样例中被h误分类的样例所占的比例 问题:h的观察到的训练错误率对真实错误率产生不正确估计的可 能性多大? 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 11 假设的错误率（2） • 图7-1：h关于c的错误率是随机选取的实例落入h和c不一致的区间 的概率 • 真实错误率紧密地依赖于未知的概率分布D – 如果D是一个均匀的概率分布，那么图7-1中假设的错误率为h和c不 一致的空间在全部实例空间中的比例 – 如果D恰好把h和c不一致区间中的实例赋予了很高的概率，相同的h 和c将造成更高的错误率 • h关于c的错误率不能直接由学习器观察到，L只能观察到在训练 样例上h的性能 • 训练错误率：指代训练样例中被h误分类的样例所占的比例 • 问题：h的观察到的训练错误率对真实错误率产生不正确估计的可 能性多大？
PAC可学习性 我们的目标是刻画出这样的目标概念,它们能 够从合理数量的随机抽取训练样例中通过合理 的计算量可靠地学习 对可学习性的表述 种可能的选择:为了学习到使ero(h)=0的假设h, 所需的训练样例数 这样的选择不可行:首先要求对X中每个可能的实例都提 供训练样例;其次要求训练样例无误导性 可能近似学习:首先只要求学习器输出错误率限定 在某常数ε范围内的假设,其次要求对所有的随机抽 取样例序列的失败的概率限定在某常数δ范围内 2003.12.18 只要求学哥能常到t的n设面晓鹏2
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 12 PAC可学习性 • 我们的目标是刻画出这样的目标概念，它们能 够从合理数量的随机抽取训练样例中通过合理 的计算量可靠地学习 • 对可学习性的表述 – 一种可能的选择：为了学习到使errorD(h)=0的假设h， 所需的训练样例数 • 这样的选择不可行：首先要求对X中每个可能的实例都提 供训练样例；其次要求训练样例无误导性 – 可能近似学习：首先只要求学习器输出错误率限定 在某常数范围内的假设，其次要求对所有的随机抽 取样例序列的失败的概率限定在某常数范围内 • 只要求学习器可能学习到一个近似正确的假设
PAC可学习性(2) PAC可学习性的定义 考虑定义在长度为n的实例集合X上的一概念类别C,学习器L 使用假设空间H。当对所有c∈C,X上的分布D,ε和δ满足0<E, 6<1/2,学习器L将以至少1-6输出一假设h∈H,使eror(h)≤ε, 这时称C是使用H的L可PAC学习的,所使用的时间为1/,1/6, n以及se(c)的多项式函数 上面定义要求学习器L满足两个条件 L必须以任意高的概率(1-8)输出一个错误率任意低(ε)的 假设 学习过程必须是高效的,其时间最多以多项式方式增长 上面定义的说明 l/E和116表示了对输出假设要求的强度,n和size(c)表示了实例 空间X和概念类别C中固有的复杂度 2001为X实例的小度理论kec概解钓编琢廉者:陶晓鹏13
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 13 PAC可学习性（2） • PAC可学习性的定义 – 考虑定义在长度为n的实例集合X上的一概念类别C，学习器L 使用假设空间H。当对所有cC，X上的分布D，和满足0<, <1/2，学习器L将以至少1-输出一假设hH，使errorD(h)， 这时称C是使用H的L可PAC学习的，所使用的时间为1/，1/， n以及size(c)的多项式函数 • 上面定义要求学习器L满足两个条件 – L必须以任意高的概率（1- ）输出一个错误率任意低（）的 假设 – 学习过程必须是高效的，其时间最多以多项式方式增长 • 上面定义的说明 – 1/和1/表示了对输出假设要求的强度，n和size(c)表示了实例 空间X和概念类别C中固有的复杂度 – n为X中实例的长度，size(c)为概念c的编码长度
PAC可学习性(3) 在实践中,通常更关心所需的训练样例数, 如果L对每个训练样例需要某最小处理时间,那么 为了使c是L可PAC学习的,L必须从多项式数量的 训练样例中进行学习 实际上,为了显示某目标概念类别C是可PAC学习 的,一个典型的途径是证明C中每个目标概念可以 从多项式数量的训练样例中学习到,且处理每个样 例的时间也是多项式级 PAC可学习性的一个隐含的条件:对C中每个 目标概念c,假设空间H都包含一个以任意小误 差接近c的假设 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 14 PAC可学习性（3） • 在实践中，通常更关心所需的训练样例数， – 如果L对每个训练样例需要某最小处理时间，那么 为了使c是L可PAC学习的，L必须从多项式数量的 训练样例中进行学习 – 实际上，为了显示某目标概念类别C是可PAC学习 的，一个典型的途径是证明C中每个目标概念可以 从多项式数量的训练样例中学习到，且处理每个样 例的时间也是多项式级 • PAC可学习性的一个隐含的条件：对C中每个 目标概念c，假设空间H都包含一个以任意小误 差接近c的假设
有限假设空间的样本复杂度 PAC可学习性很大程度上由所需的训练样例数 确定 随着问题规模的增长所带来的所需训练样例的 增长称为该学习问题的样本复杂度 我们把样本复杂度的讨论限定于一致学习器 (输出完美拟合训练数据的学习器) 能够独立于特定算法,推导出任意一致学习器 所需训练样例数的界限 变型空间:能正确分类训练样例D的所有假设 的集合 口。HSD={∈H(<x,c(x)>∈D(h(x)=c(x) 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏 15
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 15 有限假设空间的样本复杂度 • PAC可学习性很大程度上由所需的训练样例数 确定 • 随着问题规模的增长所带来的所需训练样例的 增长称为该学习问题的样本复杂度 • 我们把样本复杂度的讨论限定于一致学习器 （输出完美拟合训练数据的学习器） • 能够独立于特定算法，推导出任意一致学习器 所需训练样例数的界限 • 变型空间：能正确分类训练样例D的所有假设 的集合。 { | ( , ( ) ( ( ) ( ))} , VS h H x c x D h x c x H D = =