动机
分类器可以完全拟合训练样本,却在未见过的数据上频繁出错。分析差距之前,我们必须说明样本如何产生、错误如何衡量,以及保证中的概率针对什么随机性。PAC 学习要求算法以高概率输出近似正确的假设,并不保证每一个可能样本都会成功。
本节讨论可实现的二分类模型:标签由假设类中的目标函数产生,样本独立地来自一个固定但未知的分布。样本数量足够并不自动意味着能高效找到所需假设;统计与计算是两个不同问题。
定义
定义 1.1.1
(风险与 PAC 保证)
令 为可测实例空间, 为可测函数组成的假设类, 为概率分布,目标为 ,且 。独立同分布样本 的经验误差和总体风险为
可实现 PAC 学习要求:对每个 、 和 ,输出的 以至少 的概率满足 。概率针对训练样本和算法内部随机性。高效 PAC 学习还要求运行时间在相关参数中有适当的多项式界。
经验误差为零的假设称为与样本一致。一致只约束观察到的点;概率为零的点即使标签不同,也不增加总体风险。
定义 1.1.2
(打散与 VC 维数)
若有限集合 的每一种二元标记都能由某个 实现,则称 打散 。VC 维数是被打散的有限集合的最大大小;若能打散任意大的有限集合,则维数为无穷。存在一个大小为 的被打散集合就足够,并不要求所有大小为 的集合都被打散。
概念视角组合
打散即标记模式的计数
对有限集合 ,令 为 在 上能实现的标记模式的集合。则 被打散当且仅当 ,即 。多个假设可以产生同一个模式,所以 。因此有限类只能打散满足 的集合,由此得 。这是把同一概念看作模式的计数,而不是逐个标记地检查。
定理/命题
定理 1.1.3
(有限类的一致学习界)
设 有限,算法总返回 中与可实现的独立同分布样本一致的假设。如果
则输出的风险至多为 的概率至少是 。
定理 1.1.4
(可数类的奥卡姆界)
对可数假设类赋予正权重 ,满足 ,且权重在观察样本前固定。以至少 的概率,每个与样本一致的假设同时满足
可以给描述较短的假设较大权重;在一致的条件下,这给出较小的风险上界。
证明思路
证明
(坏假设必须避开所有样本错误)
固定一个 的假设。每个样本落入其错误区域的概率大于 ;独立性给出它仍然一致的概率至多为 。对所有假设使用并集界,存在坏的一致假设的概率至多为 。因此在剩余事件上,算法即使看过样本才选择假设,其一致输出仍有风险至多 。可实现性确保至少存在一致的目标假设。
对于加权结论,令 。当 时, 一致但风险大于 的概率至多为 ;当 时结论自动成立。对所有假设求和,失败概率至多为 。不同假设的失败事件不必相互独立。
证明透视
为什么界适用于依赖数据的选择
先固定一个坏假设:独立性控制它避开所有样本错误的概率。然后在学习器选出输出之前,对所有假设取并集界。在所得成功事件上,每个一致候选都准确,所以保证也适用于观察样本后选出的输出。
以下独立的四点例子使证明更具体。输入从 {a,b,c,d} 独立均匀抽取,目标为 0000,固定假设类为 {0000,0001,0011}。抽取两次、,并选取一致假设中序号最大者时,十六个有序样本中有四个会选出坏假设。改变选取规则,可比较特定学习器失败的事件与“存在任何坏的一致假设”的事件。样本量界是分布无关的充分条件;这个精确计数只适用于所述均匀分布。
例题
例题 1.1.5
(有限假设类)
若 、、,定理给出的充分样本数为
这是对所有符合模型的分布有效的充分界,并非每个具体问题所需的精确阈值。计数证明也没有给出寻找一致假设的算法运行时间。
例题 1.1.6
(实数轴上的阈值)
令 ,其中 。任意一个点可以被标为零或一,所以能被打散。对于 ,标记 无法由阈值实现,因此 VC 维数为一。这个类是无穷的,不能直接把无穷代入有限类的样本界。
例题 1.1.7
(实数轴上的区间)
取所有有界闭区间的示性函数,并加入空集对应的假设。两个不同点的四种标记都可实现:选取只含其中一点、包含两点的区间,或选空集。三个有序点的标记 不可能由区间实现,所以 VC 维数是二。即使不加入空假设,也可选取与有限集合不相交的有界区间来实现全零标记。
下面的互动图列出固定样本在阈值类与区间类下的每一种标记,并为每种标记给出可拟合的假设或有序反例,让两个 VC 维数可逐一模式核对。
常见错误
常见错误
(只检验一个集合,而不是所有集合)
要证明 ,只需给出一个大小为 的被打散集合。要证明 ,则必须排除所有大小为 的集合;找到一个没有被打散的集合并不能说明任何问题。例如令 , 由在 处取值为零的四个函数组成。集合 没有被打散,因为没有假设在 处给出标签 ;但 被打散,所以 。
常见错误
(训练误差、总体误差和概率)
经验误差为零不代表总体误差为零。 控制抽到使保证失败的训练样本的概率; 控制成功事件上的总体误差。二者均不是某一次固定测试预测出错的概率。
反例模式
权重之和超过一
假设有人对每个假设取 来使用奥卡姆(Occam)界。取 、 为均匀分布、目标 ,以及 ,其中 是单点 的示性函数。则每个 都有 ,而权重之和为 。取 ,所声称的界是 ;当 时等于 。但七次抽样至多包含七个不同的点,所以必有某个点 未被抽到;此时 与样本一致,而它的风险是 。所声称的事件“每个一致假设的风险都至多为 ”因此概率为 ,而不是至少 。换用合法的权重 ,界为 ,与实际情形相符。条件 正是对假设取并集界所需要的。
无分布假设的保证仍有模型条件:样本必须独立地来自同一个固定分布,且标签由 中的目标产生。不能不加修改地把结论用于相依样本、分布变化或任意标签噪声。
总结
一致性与有限假设类通过并集界给出样本保证;加权计数将论证推广到可数类。VC 维数衡量类能实现的标记模式,对无穷类也有意义。统计可学习性与计算效率应分别分析。
练习
快速检查
(若 、、,求有限类定理给出的充分整数样本数。)
计算 并向上取整。
解答 · 答案
,向上取整得到充分样本数 。
快速检查
(若有限定义域有 个点, 包含定义域上的所有二元函数,求 VC 维数并解释。)
整个定义域是否被打散?有没有更大的子集?
解答 · 答案
整个定义域被打散,因为全部 种标记均在类中。定义域没有更大的子集,因此维数恰为 。
快速检查
(某一致假设的权重为 ,样本量为 ,。写出它的加权风险上界。)
此时 。
解答 · 答案
在同时成立的高概率事件上,。该事件对每个一致假设成立,包括看过样本后选择的假设。
快速检查
(利用模式计数的描述,说明只有五个假设的类不能打散任何三点集合。)
比较 与 。
解答 · 答案
对任何三点集合 ,限制 中每个假设至多给出一个模式,所以 。八种标记不可能全部出现,因此 不被打散。