如果一个函数类能匹配许多任意标签模式,它既可能拟合信号,也可能拟合噪声。Rademacher 复杂度在观察到的输入上提出一个定量问题:类中的函数能与独立随机符号有多强的相关性?与简单计算假设个数不同,其值可以依赖样本所在的位置。
固定样本上的随机符号
设 从固定分布 独立同分布抽取,;设 是抽样前固定的非空可测函数类,成员为 。记 、。假设下文用到的上确界均可测,包括涉及独立幽灵样本和符号的上确界;有限或可数类满足要求,下文的连续紧致参数例子也满足要求。
下文对数均为自然对数。
定义 2.5.1
(经验与期望 Rademacher 复杂度)
给定样本 ,令 是独立均匀的 符号,并独立于样本。定义
所有样本点必须使用同一个 。符号是分析工具,不是提供给训练算法的标签。对符号取期望在上确界之外:每个符号向量可以选择不同的上确界函数。对任一固定成员,其带符号和的期望为零,因此 。
例题 2.5.2
(两个常值函数)
设 由恒零和恒一函数组成。当 时,上确界为 。其期望为 :只有两个符号均为正的情形有贡献。这是类在样本上的复杂度,不是训练误差,也不是误分类的概率。
从对称化得到一致界
定理 2.5.3
(经验 Rademacher 泛化界)
对 ,以样本为随机性、概率至少为 ,对所有 同时有
对固定的损失函数类,这用经验损失控制总体损失;复杂度必须针对该损失函数类计算,不能自动以底层预测器类的复杂度代替。即使函数是在看到样本后从类中选出的,结论仍成立,因为该事件对所有成员同时成立。
证明
(幽灵样本、对称化与有界差)
令 ,引入与样本独立、同分布的幽灵样本 。由于 ,将期望移到上确界之外得到
每对 可交换。根据随机符号独立交换每对中的元素,不改变联合分布,因此
不等式把差的上确界拆成两个上确界;符号向量与其相反数同分布。这就是对称化步骤。
我们使用有界差不等式:若改变第 个独立输入使函数变化至多 ,则它超过均值 的概率至多为 ;低于均值的同等偏差也有此界。例如,可对逐次条件期望构成的鞅差应用 Hoeffding 引理得到此结论。由于所有函数值都在 ,改变一个样本点使 或 的变化均至多为 。令 , 的上偏差和 的下偏差各以至多 的概率失败。在两者共同成立的事件上,
对每个成员都有 ,故定理成立。
证明透视
幽灵样本和符号为何出现
幽灵样本只用于证明。逐对交换把两个经验均值的差变成带符号的差。拆分所得上确界后得到两份复杂度。完成这个期望论证后,才用有界差把未知的期望复杂度换成经验版本。
这个不等式是单侧的。它不保证每个样本的右侧都很小:经验复杂度本身可以很大,且仍有概率至多 的例外事件。如果看过同一份样本后才构造 ,就不能不加额外论证地应用这个固定类定理。
有限类与范数有界的无限类
引理 2.5.4
(有限类的复杂度很小)
对于大小为 的固定有限类,每个样本都满足
证明
(矩母函数论证)
当 时,令 。对任意 ,Jensen 不等式及非负数的 给出
这里 ,因为 且 。取 使右侧最小。当 时带符号和的均值为零,所以同一个界成立。该界可能大于由值域直接得到的平凡界,也不一定紧。
无限类不能直接使用基数界。但令定义域与分布支撑在球 上,并考虑 ,其中 、,并令 。这些函数的值在 。对任何样本,
常数项的带符号期望为零; 在欧氏(Euclidean)球上的上确界为 。Jensen 不等式及交叉项抵消给出中间的界。该类虽然无限,其复杂度仍受范数约束控制。维数仍可能通过 、 和数据的尺度间接影响结果。
例题 2.5.5
(有限类,以及界何时没有意义)
取 、,并设所选函数的经验均值为 。当 时,有限类界给出 ,置信项为 。因此定理右侧至多为 ,超过平凡值 :在这个样本量下它什么也没有说明。当 时,相应的量为 和 ,所以右侧至多为 。在退化情形 时,界为 ,与单个函数的 Rademacher 复杂度为零这一事实一致。
例题 2.5.6
(范数有界的线性类在两种样本量下的情形)
取 、,故 ,函数 取值于 。复杂度界为 ,在 时为 ,在 时为 。取 ,定理中复杂度的贡献 分别至多为 和 ,而置信项分别为 和 。在 时,起主导作用的是置信项,而不是这个无限类的复杂度。这个类含有无限多个函数,贡献却比上面八个函数的有限界更小。
反例模式
依样本选出的类可能使定理失效
设定义域有 个等概率点,每个点的“标签”就是某个函数在该点的值。观察 后,选择只含函数 的单元素类,其中 在观察到的点取零,在其他点取一。其经验复杂度为零,因为类中只有一个函数,且 ,但 。当 、 时,定理所示右侧约为 ,所以若在此应用,便会对每个样本失败。函数类是根据样本选出的,因此固定类定理不适用。遗漏的复杂度在于对许多可能函数进行适应性选择。
常见错误
(把上确界放到对符号的期望之外)
对每个固定的 ,带符号的和均值为零,所以对任何类都有 。复杂度是 ,其中上确界可以随符号调整。对 的两个常值函数,正确值为 ,而不是 。交换这两个运算,会使每个类看起来都没有拟合噪声的能力。
常见错误
(用预测器的复杂度代替损失类的复杂度)
定理控制的是取值于 的损失函数类 。对标签 和 0-1 损失,。常数 的贡献均值为零,而 仍是均匀符号,所以损失类的复杂度恰好是同一批输入上预测器类复杂度的一半。直接代入 的复杂度会使复杂度项加倍;必须指明正确的类。
练习与解答
快速检查
(对只含恒等于 的函数的类,计算任意 下的经验 Rademacher 复杂度。)
上确界遍历多少个函数?
解答 · 答案
为零:带符号和的均值为零。
快速检查
(当 、 时,写出有限类上界。)
代入 。
解答 · 答案
。
快速检查
(若 、、,给出上述线性类的复杂度界。)
用 。
解答 · 答案
至多为 。
快速检查
(为什么定理允许依据数据选择 ,却不允许未计入代价地依据数据选择整个类?)
抽样之前固定的是哪个对象?
解答 · 答案
一个同时成立的事件覆盖了抽样前固定的类中的每个成员;看到样本之后才改变类本身,则超出了该事件的量词范围。