动机
一个假设类即使包含无穷多个规则,在任一有限样本上的表现也可能只有有限种。实数轴上的阈值便是例子:切分点可以有无穷多个位置,但对 个有序输入只会产生 种标签模式。泛化证明可以统计这些模式,而不必逐一统计所有假设。困难在于,统计模式所用的样本本身是随机的,而且学习器是在看到标签之后才选择假设。
增长函数衡量给定大小的样本上最多可能出现多少种模式;VC 维数衡量多大的集合能够实现所有模式。Sauer–Shelah 定理把有限 VC 维数转化为多项式增长界。随后需要另一个概率论证,才能从计数得到同时成立的误差保证。单靠计数或训练拟合都不能保证总体表现:数据还必须满足所述抽样假设。
定义
定义 2.1.1
(迹、增长函数与打散)
设 为非空可测空间, 是由可测函数 组成的非空类。对有限集合 ,其迹为
若 ,称 被打散。VC 维数 是被打散的有限集合的最大大小;若不存在有限上界,则维数为无穷。定义增长函数
输入元组可以重复点;重复不会增加模式数。大小为 的集合被打散,当且仅当全部 种模式都能实现。有限 VC 维数为 意味着存在被打散的 点集合,但没有被打散的 点集合。被打散集合的每个子集也被打散:将子集上的任意标签扩展到较大集合即可。 时,非空 打散空集。
迹取决于输入,而不是观测标签。两个假设即使在其他地方不同,只要在这些输入上相同,就只贡献一个模式。反过来,无穷假设类不一定有无穷 VC 维数。即使 有限,定义仍允许样本点重复,这符合有放回抽样。
定义 2.1.2
(总体误差与经验误差)
令 为有标签对 的任意分布,其中 。对 定义
其中 独立地从 抽取。分布可以有标签噪声,不必由 中某个目标实现。一致收敛在同一个高概率事件上同时控制每个 的 ,因此也涵盖观察样本后选择的假设。
以下概率证明假设 可数,使相关上确界及所选的见证假设可测,无需引入额外的经验过程工具。组合定理本身不需要可数性。很多不可数类在适当可测性条件下也有相应概率结论;这些条件并非自动成立,此处不作证明。
定理/命题
定理 2.1.3
(Sauer–Shelah 增长界)
若 的 VC 维数为有限的 ,则对每个整数 ,
其中 时取 。特别地,固定 时,模式数至多按 的 次多项式增长,而不是按 增长。
定理 2.1.4
(通过幽灵样本得到一致误差界)
设 如上可数且其成员可测, 包含 个从任意 独立同分布抽取的有标签样本。若 且 ,则
右边可能大于一,此时不等式虽成立却没有实际信息。结合 Sauer–Shelah 定理可得可数有限 VC 类的无分布假设界;无需假设标签没有噪声。
对置信参数 及 VC 维数 ,定义
这里对数为自然对数。由于 ,定理适用:以至少 的概率,所有 同时满足 。这是一个明确的误差证书,不声称其常数或特殊模型下的速率总是最优。
即使不用更精细的二项式估计,增长界也能显示收敛速度。把一个 点集合中至多含 个元素的子集按递增次序列出,并用零补成长度 。这是到 的单射,因此 。由此
固定 和 时,右边趋于零。这里关于 的对数因子属于这个特定的界,不能证明更强的定理也必须含有它。若半径大于一,结论仍成立,但不会改善误差不超过一的平凡界。
证明思路
证明
(组合递推式)
固定 个互异点,把一个迹看成这些点的子集。从每个迹中删去最后一个点。令 为删点后得到的子集族,令 为同时有“包含最后一点”和“不包含最后一点”两种原始延伸的子集族。 中每个成员有一种或两种原始延伸,所以
的 VC 维数至多为 ,因为它打散的任何子集原本也被 打散。若 非空,其 VC 维数至多为 :若 打散剩余点中的 个点,那么这 点的每种标签都由 中某个迹实现。该迹对被删点有两种延伸,因而 会打散这 点及被删点,与 的定义矛盾。
归纳命题适用于 点集合上的任意有限子集族,只要求 VC 维数至多为 ,不局限于原类的迹。空族的大小为零,显然满足此界。对 同时归纳: 时,若有两个不同迹,它们必在某点不同,从而打散该单点,故至多有一个迹; 时初等界 恰为完整二项式和。其余情况下,归纳假设及 Pascal 恒等式给出
重复样本点只会减少不同模式的数量,因此同一界适用于 中的元组。
证明
(从第二个样本到一致界)
令 是同样大小、独立的“幽灵”样本。对固定的 ,幽灵经验误差的期望为 ,方差至多为 。Chebyshev 不等式给出
若 上存在坏假设满足 ,按固定的 枚举选出第一个。给定 后,独立幽灵样本以至少二分之一的概率使该假设的经验误差与真实误差相差至多 。三角不等式随即给出 。所以
为估计右边,将 和 的第 个样本配对,独立地以二分之一概率交换每对中的两个成员。交换性保证总体联合分布不变。给定交换前的 个有标签样本,最多出现 种预测模式。合并样本的标签也已固定,因此每个预测模式确定一个误差差值向量。对于固定模式,两个经验误差之差是独立、均值为零且位于 的带符号项的平均。Hoeffding 不等式说明其绝对值超过 的概率至多为 。对所有模式使用并集界,再对配对数据取平均,就得到定理和前面的系数四。
计数是在给定合并输入之后进行的,但早于选择违反界的模式。正因如此,对有限个样本模式取并集界可以控制从可数、甚至无穷类中依赖数据作出的选择。幽灵样本仅是证明工具;学习器不需要实际获取其标签。
证明透视
两个不同的归约
Sauer–Shelah 定理是确定性的:它控制固定输入上的标签模式数量。对称化是概率性的:独立幽灵数据和随机成对交换将真实误差转化成有限多个随机经验比较。增长函数只在计数步骤进入论证。分清两步可以避免错误地认为 VC 维数小就能保证某个具体训练样本一定有代表性。
一致假设的快速率界
双侧偏差界在 的尺度上控制经验误差与总体风险的差。对在样本上完全不犯错的假设,下述上界的指数因子是 ,但还乘以增长函数。有限 VC 维使该因子至多多项式增长,从而最终得到更快的速率。证明使用幽灵样本与独立交换。
本节取 ,即上面定义 时所用的带标签分布。记 为经验误差;对 、 和 使用相同记号。
定理 2.1.5
(一致假设的快速率界)
设 是非空可数的可测分类器类, 是带标签样例上的任意分布, 且 。若 ,则
定理并不假设可实现性;它对每个 都估计一个事件的概率。可实现性只在之后起作用:若固定的 满足 ,它几乎必然与样本一致,因此一致假设几乎必然存在。
证明
(幽灵样本、交换与 Chernoff 界)
已知不等式(乘法型 Chernoff). 设 是独立 Bernoulli 变量之和,,且 。则 。
幽灵样本。 取与 独立的 。记定理中的事件为 ;记 为“存在 使 且 ”。
枚举 。在 上,令 为第一个满足 且 的 。由于 可数,这个首个见证是 的可测函数。
给定 ,计数 是 个独立 Bernoulli 变量之和。这里 ,所以 。令 ,则 且 。由 Chernoff 不等式,
最后一步用到 。因此在 上 。这个事件包含于 。对 取平均得 ,即损失一个因子 。
交换。 写 、。取相互独立的均匀比特 ,并令它们与 独立。当 时交换 与 ,得到 。由于 独立同分布, 与 同分布。因此 等于 上同一事件的概率。
现在以交换前汇总的数据 为条件。每个 给出误差向量 : 当且仅当 在 上出错, 当且仅当 在 上出错。该向量由 在这 个点上的标签决定,所以至多出现 种;重复的点只会减少种数。
固定一个向量。
- 若某个 有 ,则无论 取何值,总有一个错误落入 ,故 不可能成立。
- 否则,设恰有一个错误的配对数为 。幽灵一侧至多有 个错误,所以事件要求 。事件还要求这 对都把出错的成员送到 ,其概率为 。
对所有向量作并集界,条件概率至多为 。再对汇总数据取平均, 满足同样的界。由于 ,结合幽灵样本一步的结论即完成证明。
说明
为何需要幽灵样本. 在 上表现相同的假设可以有不同的风险,因为 依赖整个 。所以只在 上计数行为模式不足以得到这里的统一风险界,而直接对无限的 使用无权并集界可能没有信息。幽灵样本把 换成 。这个量只依赖 个点,正是 所计数的对象。
界可能大于 1. 当 较小时,该界没有信息量。
样本量. 设 且 。Sauer–Shelah 引理给出 。在同时满足 的前提下,只需 。这是隐式的充分样本量不等式:增长项关于 为对数,而指数因子依赖 。若 且 非空,则 ;此时使用原界,要求 且 。在可实现情形下,一致输出就以至少 的概率满足 。这些是充分界,不是匹配的下界,也不是高效算法。
例题 2.1.6
(快速率界下的阈值类)
在 上取 ,其中 ,此类可数。在 个不同点上,阈值标签由排序后位于 及其右侧的点数决定。有理数稠密,所以 种情形都能出现,于是 。
取 ,。此时 ,界为
这是充分而非最优的结论;小得多的 也可以。
快速检查
(对同一类与 ,证明 使界小于 。)
先检查 的条件,再计算 。
解答 · 答案
条件成立:。又 ,,故界为 。因此在可实现情形下,一致输出的风险以至少 的概率不超过 。
例题
例题 2.1.7
(阈值:无穷规则与线性增长的模式)
令 ,定义域为 。任意单点都能标为零或一;但若 ,标签 不可能出现,所以 。对 个互异有序输入,可以在每个相邻间隙以及两个端点外侧选择有理切分点,因此 。本例中 Sauer–Shelah 界精确达到。此类虽无限,却满足可数性限制。实数参数阈值有相同的有限迹,但可数类的概率定理不能自动推广到该类:需要额外的可测性或单独的逼近论证,尤其当输入分布有原子时。
例题 2.1.8
(数值证书及其代价)
对上述阈值,。当 、 时,明确的一致误差半径为
因此定理保证以至少 的概率,所有阈值的误差偏差均小于约 。这个界为通用结论,可能较保守;它同时涉及每个阈值,不是对某个拟合模型实际误差的估计。
例题 2.1.9
(经验风险最小化如何利用这一事件)
固定非空可数 的枚举,令 为该枚举中第一个经验误差最小者。最小值确实存在,因为经验误差属于有限集合 ;这一平局处理规则也保证选择可测。在每个偏差都不超过 的事件上,对每个 ,
取下确界得 。最小真实风险不一定被某个假设达到。保证中包含类的逼近误差 ,不假设类中存在完美分类器。
反例模式
训练准确不代表泛化准确
取 ,两点等概率,且标签在 为 、在 为 。恒等于一的假设有真实误差 。若 个输入恰好全部为 ,这一事件的概率为 ,则它的经验误差为零。高概率定理可以控制不具代表性的样本出现的频率,却不会说这种样本不可能出现。
常见错误
常见错误
(将 VC 维数与假设个数混淆)
VC 维数为一并不意味着类中只有一个规则;它意味着至少一个点能被打散,但没有一对点能被打散。增长函数统计有限样本上可区分的标签模式;若不同假设在该样本上相同,只算一种模式。
常见错误
(拟合后套用固定假设的界)
对预先选定的一个 成立的集中不等式,不能直接用于观察同一样本后选出的假设。一致定理构造一个同时控制所有假设的事件,此时才可以代入拟合出的假设。使用概率结论前,须检查独立同分布及可测性条件。
总结
打散衡量哪些标签模式可以实现;Sauer–Shelah 递推控制最大模式数。幽灵样本、随机交换和集中不等式将计数转化为同时成立的偏差保证。即使标签含噪声,经验风险最小化也可以用这一事件将拟合风险与类中可达到的最佳风险比较。
练习
快速检查
(定义域有 个互异点, 包含所有二元函数。求 ,以及 时的 。)
数一数 个互异点上的模式。
解答 · 答案
整个定义域被打散,且不存在更大的子集,因此 。当 ,选取 个互异点,全部 种模式都出现;模式数也不可能更多,故 。
快速检查
(对 上的 ,求 并与 比较。)
数一数六个有序输入的切分位置。
解答 · 答案
六个互异有序输入的每个切分位置对应一种模式;重复输入不会产生额外切分,所以 ,远小于 。界 在此达到。
快速检查
(假设一致收敛事件的半径为 ,某经验风险最小化解的经验误差为 。给出其真实误差上界,并另外给出相对于 的界。)
一个界直接用该事件,另一个界与每个 比较。
解答 · 答案
一致事件给出 ;经验最小化论证给出 。这是两个不同结论,均未确定未知的最佳风险。
快速检查
(非空定义域上的假设类只包含两个常值分类器。求其 VC 维数及 时的增长函数,并验证 Sauer–Shelah 不等式。)
哪些由互异点组成的集合能被打散?
解答 · 答案
一个点可以标为零或一,所以维数至少为一。常值分类器不能给两个互异点不同标签;若定义域只有一个点,也没有更大子集,故维数仍为一。每个 均只有全零和全一两种迹,因此 。