为什么要数模式,而不是参数?
参数网格通过比较附近的参数控制无限函数族,但需要度量和一致利普希茨(Lipschitz)条件。有时不同参数在所有观测点上给出的预测完全相同;反过来,一个描述看似简单的函数族也可能记住全部样本。我们需要衡量样本上的函数行为,而不是只数参数名称。
随机符号提供一种检验:为每个观测独立地赋予公平的正负号,问函数族能在多大程度上跟随这些人为噪声。丰富的函数族可以追随较多噪声,受限制的函数族则不行。这里直接衡量的是损失函数族;预测函数族的界不能不经论证就当作损失族的界。
设定与随机符号度量
设 独立同分布,公共分布为 ,。设 是非空、可数的可测函数族,每个函数取值于 。记
定义 10.3.1
(经验与期望拉德马赫复杂度)
令 为相互独立的公平正负号,且与样本独立。经验拉德马赫(Rademacher)复杂度是条件期望
上确界允许在看到随机符号后选择 ;否则每个固定函数的带符号和的期望均为零。可数性保证下文的上确界可测。即使函数族不含零函数,复杂度仍非负:上确界不小于任一固定函数的带符号和,而后者的期望为零。
定理 10.3.2
(单侧一致泛化界)
对 ,以下事件关于样本的概率至少为 :
因此,同一事件上,任何由数据决定的可测选择 的总体风险 至多是经验风险 加上右端。这里的复杂度还对样本取了期望,并非仅是观察到的经验复杂度。
证明:影子样本与集中不等式
证明
(先对称化,再用有界差分)
引入与原样本独立、同分布的影子样本 。对固定原样本,。把期望移到上确界之外只会增加表达式,因此
每一对 的两项可交换,而且各对独立。因此按独立公平符号交换各对两项,不改变联合分布。引入符号,再应用 ,得到
两个上确界可以选取不同函数,所以这里得到的是不等式。最后一步使用符号分布的对称性。
令 。更换一个观测使每个 的变化不超过 ,故 的变化也不超过 。有界差分不等式给出 。其证明也解释了条件:逐个揭示观测,形成 的 Doob 鞅;给定过去,每个鞅增量的条件均值为零,且位于长度不超过 的区间内。Hoeffding 引理将其条件指数矩控制在 。将各步相乘并用 Markov 不等式,得到 ;取最优 得所述尾界。取 并结合影子样本估计,即证定理。
证明透视
三个步骤,各自消除一个障碍
影子样本把未知的 换成独立副本的经验平均。这一步唯一的不等式,是把期望移到上确界之外。
接着可以插入随机符号而不改变任何东西,因为每对 可交换,而各对之间相互独立;独立同分布假设正是在这里用到。拆开上确界得到两个拉德马赫复杂度,系数二就来自这次拆分;它有所损失,因为两个上确界可以选取不同函数。
围绕其均值的集中只用到取值范围 ,通过大小为 的差分;有界性在这里进入。可数性只用于使上确界可测。界以期望复杂度 表述,因为对称化控制的是 ,而不是 本身。
这只是单侧界。对 也应用定理,再用并集界,可得双侧误差界,根号中的对数改为 。两族复杂度相同,因为额外常数项的带符号和期望为零,且符号反转不改变分布。若双侧一致误差为 ,而近似经验最小化满足 ,则 :先与任意 比较,再取下确界。
从样本模式得到界
引理 10.3.3
(模式计数界)
假设在固定样本上,取值向量 至多有 个不同值,则
证明
(对有限个模式取指数矩)
把这些向量记为 。对任意 ,由 Jensen 不等式、指数最大值界和 ,
当 时优化 并除以 ;当 时,带符号和的期望恰为零。如果同一个确定的 对每个样本有效,取样本期望后也得到 的上界。这个简便估计可能大于一,也不一定紧;当 相对 较小时才有用。
证明透视
为什么只有模式的数目重要
函数类只通过它的 个值向量出现,所以上确界变成有限多个和的最大值;正因如此,才可用软最大值上界 。接着 Jensen 不等式把对符号的期望移入对数之内。符号的独立性把每个指数矩分解为 ,而范围 把它界于 。选取 使两项平衡。若以 代替 ,就得到更精细的 。
例题 10.3.4
(阈值损失只有少量样本模式)
令 为实随机变量,,其中 取有理数。这是无限但可数的函数族。将任意 个观测排序,移动阈值只会按排序依次加入观测,因此最多出现 个不同取值向量;相同观测值可能使数量更少。于是
的概率至少为 。当 、 时,右端约为 。它是与分布无关的充分保证,不是观测误差,也不是最紧的阈值过程不等式。
例题 10.3.5
(两点上的两个函数:精确计算)
令 , 在样本上的取值向量为 与 。则 、,带符号的上确界是 。在四个等可能的符号对上,它分别为 ,平均为 。除以 得 。 的模式计数界给出 ,大三倍以上。这个界有效,但 很小时,对符号向量精确取平均可以紧得多。
例题 10.3.6
(边界情形:只有一个观测)
对阈值族及 ,把有理数 放在 之下或之上,每个观测都允许模式 与 。当 ,上确界为 ;当 ,上确界为 ,由模式 达到。因此对每个样本 ,而 。定理于是把 界定为 ,对每个 都大于 。取值于 的损失,其差距永远不超过 ,所以这个界正确却没有信息量;模式估计 也是如此。有用的保证需要 相对 很小。
一个会记住样本的函数族
取值有界与可数性本身并不能使复杂度变小。
反例模式
差距不会缩小的可数有界函数族
断言:对取值于 的可数函数族,一致差距随 增大而趋于零。令 为 上的均匀分布, 为有理端点开区间的有限并的指示函数族。它可数。对任意有限样本和任意 ,可用有限多个这样的区间覆盖样本点,并使总长度小于 。相应函数满足 、,故 。实际上,只要样本点互异,就可在标记为一的点附近选择足够小的区间,实现任意二元标记。因此,有界损失和可数性本身并不能保证有用的一致界:该族的复杂度不趋于零。函数族在抽样前固定的条件也很重要;若使用同一数据选择函数族,需要另作分析。
常见错误
常见错误
(先选函数,后看符号)
若把上确界换成一个固定的 , 的期望为零,每个函数族的复杂度都会变成零。定义允许 依赖符号向量;正因如此,它才度量函数族拟合噪声的能力。
常见错误
(用观测到的复杂度代替期望复杂度)
定理以 表述。把它换成在观测样本上计算的 ,需要对 再作集中论证,并会改变常数;本节没有证明这一步。对每个样本都成立的确定性模式计数可以避开这个问题,阈值例子正是如此。
常见错误
(把预测函数族的界转用于损失族)
计算是在损失函数本身进行的。预测函数族的复杂度界,不会自动成为复合后损失族的界;这种转移需要另外论证损失如何依赖预测。
练习
快速检查
(函数族只含 。计算其经验拉德马赫复杂度,并解释为什么结果不是一。)
解答 · 答案
它等于 。上确界只有一个候选函数,公平符号在期望中抵消;损失值一并不是带符号相关本身。
快速检查
(某二值函数族在任何大小为 的样本上最多产生 16 种模式。利用模式估计给出期望拉德马赫复杂度的数值上界。)
解答 · 答案
上界为 。由于对每个样本均成立,取期望后仍成立。
快速检查
(在上述阈值族中,观察样本后选择经验阈值。解释为何同时成立的定理适用,并指出仍须核对的一个条件。)
解答 · 答案
同一事件同时控制每个有理阈值,因此控制使用数据选择的阈值。选择必须可测且属于固定的可数函数族;不能据此擅自扩大成依赖同一数据的其他函数族。
快速检查
(对区间有限并的记忆函数族,计算互异的 个样本点上的经验复杂度。为什么它不趋于零?)
解答 · 答案
对每组符号,该族都能实现恰在正号点上为一的指示函数,因此最大的带符号和等于正号数量。经验复杂度为 ,对任意互异样本都与 无关。这个可数区间族足够丰富,可以记住随机符号。