有限假设空间的样本复杂度(2) 变型空间的重要意义是:每个一致学习器都输 出一个属于变型空间的假设 因此界定任意一个一致学习器所需的样例数量 只需要界定为保证变型中没有不可接受假设所 需的样例数量 定义:考虑一假设空间H,目标概念c,实例分 布D以及c的一组训练样例S。当VSp中每个假 设h关于c和D错误率小于ε时,变型空间被称为 c和D是8-详尽的 h∈SHD)eror(h)<E 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏 16
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 16 有限假设空间的样本复杂度（2） • 变型空间的重要意义是：每个一致学习器都输 出一个属于变型空间的假设 • 因此界定任意一个一致学习器所需的样例数量， 只需要界定为保证变型中没有不可接受假设所 需的样例数量 • 定义：考虑一假设空间H，目标概念c，实例分 布D以及c的一组训练样例S。当VSH,D中每个假 设h关于c和D错误率小于时，变型空间被称为 c和D是-详尽的。 ( ) ( ) h VSH ,D errorD h
有限假设空间的样本复杂度(3) -详尽的变型空间表示与训练样例一致的所有 假设的真实错误率都小于 从学习器的角度看,所能知道的只是这些假设 能同等地拟合训练数据,它们都有零训练错误 率 只有知道目标概念的观察者才能确定变型空间 是否为8-详尽的 但是,即使不知道确切的目标概念或训练样例 抽取的分布,一种概率方法可在给定数目的训 练样例之后界定变型空间为8-详尽的 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏 17
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 17 有限假设空间的样本复杂度（3） • -详尽的变型空间表示与训练样例一致的所有 假设的真实错误率都小于 • 从学习器的角度看，所能知道的只是这些假设 能同等地拟合训练数据，它们都有零训练错误 率 • 只有知道目标概念的观察者才能确定变型空间 是否为-详尽的 • 但是，即使不知道确切的目标概念或训练样例 抽取的分布，一种概率方法可在给定数目的训 练样例之后界定变型空间为-详尽的
有限假设空间的样本复杂度(4) 定理7.1(变型空间的详尽化) 若假设空间H有限,且D为目标概念c的一系列m>=1个独立随 机抽取的样例,那么对于任意0=<<=1,变型空间VSHD不是ε 详尽的概率小于或等于:H|em 证明: 令h1h为H中关于c的真实错误率大于ε的所有假设。当且仅 当k个假设中至少有一个恰好与所有m个独立随机抽取样例 致时,不能使变型空间ε详尽化。 任一假设真实错误率大于ε,且与一个随机抽取样例一致的可 能性最多为1-ε,因此,该假设与m个独立抽取样例一致的概 率最多为(18)m 由于已知有k个假设错误率大于8,那么至少有一个与所有m个 训练样例都不一致的概率最多为(当≤1,则1-≤e) k(l-8) qHI(1-8)"Hle 2003.12.18 机器学习-计算学习理论作者: Mitchel译者:曾华军等讲者:陶晓鹏 18
2003.12.18 机器学习-计算学习理论作者：Mitchell 译者：曾华军等讲者：陶晓鹏 18 有限假设空间的样本复杂度（4） • 定理7.1（变型空间的-详尽化） – 若假设空间H有限，且D为目标概念c的一系列m>=1个独立随 机抽取的样例，那么对于任意0=<<=1，变型空间VSH,D不是- 详尽的概率小于或等于： • 证明： – 令h1 ,...,hk为H中关于c的真实错误率大于的所有假设。当且仅 当k个假设中至少有一个恰好与所有m个独立随机抽取样例一 致时，不能使变型空间-详尽化。 – 任一假设真实错误率大于，且与一个随机抽取样例一致的可 能性最多为1-，因此，该假设与m个独立抽取样例一致的概 率最多为(1-) m – 由于已知有k个假设错误率大于，那么至少有一个与所有m个 训练样例都不一致的概率最多为（当 ，则 ） m H e − | | m m m k H H e − (1− ) | |(1− ) | | 0 1 1− e