动机
样本平均即使无偏,波动仍可能太大,无法支持可靠决策。基本的方差界只回答关于这种波动的一个问题。如果每次观测都落在已知的有界区间内,就能利用这一更强的信息,得到随样本数指数下降的概率界。这在预测程序比较多个候选时尤其重要:逐个候选各有保证,不代表看过分数后挑出的赢家也自动受到同样保护。
假设用同一组训练数据建立六十四个候选预测函数,再用另一组验证数据比较它们的损失。在查看验证标签之前,以训练结果为条件,候选构成一份固定清单;验证结果则是随机的。我们需要一个足够强的结论,使它在选出表现最好的候选后仍然成立。有用的事件是:每个候选的验证分数都同时接近其总体风险。
“偏差”也有两个容易混淆的意思。它可以指函数族无法表示真实目标,也可以指训练所得预测函数的平均偏离真实目标。两者相关,但并不相同。本节会推导有限族的风险比较,以及偏差与方差分解,并逐一交代涉及的随机性和损失。下面没有任何定理声称:只因单个预测有界,任意的网络函数族就已在统计上受控。
定义
设 为相互独立的实值随机变量,有共同均值 ,且每个都几乎必然落在 内,其中 已知。这里同分布足够但不是必要条件。记 。集中不等式控制这个随机平均偏离其均值达到指定幅度的概率。
定义 10.1.1
(总体风险与验证风险)
对预测规则 ,定义总体风险及验证风险为
验证观测独立同分布,并独立于产生候选清单 的程序,其中 。每个候选的损失都落在 内,其中 是确定的上界。所有有限族的结论也可以改为以独立训练数据为条件来理解。它们不要求不同候选在同一观测上的损失相互独立。
定义 10.1.2
(近似经验最小化函数)
近似经验最小化函数 属于该清单,并满足 ,其中 。这个容许量衡量验证准则未完全优化的程度,不包括利用验证标签构造清单以外的新候选所造成的相依性。
定义 10.1.3
(训练平均预测函数)
在平方误差预测中,记 。设随机训练数据 独立于新的测试对 , 为拟合所得函数。其训练平均预测为 。假设下面所需的联合二阶矩有限;条件均值及函数均在输入概率为零的集合以外理解。
定理 / 命题
定理 10.1.4
(独立有界平均具有指数集中界)
在上述有界及独立假设下,对每个 ,
因此,当 时,以至少 的概率,固定清单的所有成员同时满足
在同一事件上,。若概率上界大于一,总可以改用一。
定理 10.1.5
(训练随机性分成平方偏差与方差)
设 ,且训练数据与测试数据独立。则
三项分别是条件噪声、训练平均预测函数的平方偏差,以及跨训练样本的变动。此恒等式不表示任何特定训练程序会使其中一项最小。
证明思路
证明
(指数矩与 Markov 不等式)
先证明推动第一个定理的指数矩事实。若 ,令 。有界性允许对每个实数 在期望内求导。二阶导数是 在指数倾斜概率律下的方差。在任何支撑于这个区间的概率律下,方差至多为 :由不等式 得到方差上界 ,其最大值正是所述数值。由于 ,把二阶导数的上界积分两次,得到
对正的 ,使用 Markov 不等式,并利用独立性把各观测的上界相乘,得到上尾概率界 。使它最小的值是 。对负方向的偏差作同样论证,再把两个概率相加,就证得双边不等式,不需要正态近似或估计的标准差。
证明透视
为什么一个方差界能控制所有指数矩
决定性的观察是:方差界 对 上的每个概率分布都成立,所以能同时用于每个指数倾斜后的分布;有界性只在这里使用。 的这个一致上界,连同 ,积分后给出对数矩的二次上界 。独立性只用来把 个矩界相乘。接着选取自由参数 使 Markov 界最小,从而得到指数中的因子 。仅有有限方差只在 处控制 ,不能沿整个倾斜控制它。
证明
(对固定清单使用并集界)
先对一个固定候选的验证损失应用该不等式,再对全部 个候选使用并集界。任何候选违反容许差距的概率至多为 。选取定理中的容许值,就使这个概率至多为 。一旦所有候选同时受控,所选指标可以依赖每一个验证结果:同一事件已经涵盖该指标。证明需要的是观测独立,而不是模型独立。
在这个事件上,把选定规则与清单中任一成员比较:由总体风险转到验证风险,付出 ;利用近似最小化,付出 ;再回到总体风险,又付出 。对比较对象取最小值,就得到风险不等式。相对于理想风险 ,差 是另一项逼近误差。因此表示能力、统计比较和不完美拟合各自贡献不同的量。
若候选因用较早的样本训练而是随机的,先以整个该样本为条件。对每份实现的候选清单,独立验证数据上的失败概率至多为同一选定水平。把这个条件概率对训练随机性取平均,界仍然成立。因此各候选共用一组训练数据在这里无害;但允许验证标签改变产生候选的程序,则是另一回事。独立样本提供了证明所需的分隔。
证明透视
独立性在哪里用到,在哪里没有用到
独立性只在指数矩一步用到一次:验证观测相互独立,总和的矩母函数才能分解为乘积。对候选函数则没有任何假设,它们在同一观测上的损失可以高度相关。并集界完全不需要独立性;它把 个失败事件当作互不相交,代价是因子 。
不明显之处在于量词的次序。对每个固定指标 成立的界,对看过分数后才选出的随机指标没有任何结论;而对所有 同时成立的事件,包含最终选出的任何指标。在看验证标签之前固定清单,正是使 成为固定数的假设;自适应搜索则须把 换成它可能产生的全部函数。风险不等式中的 记录了在总体风险与验证风险之间来回跨越两次。
证明
(先以训练样本为条件)
对第二个定理,先以 为条件,对新的测试对应用条件均值的风险恒等式。再写 。对训练数据取平均时,因 ,交叉项消失。平方可积性保证乘积及交换平均次序合法。这个证明也说明,为何依赖训练数据的测试响应不能简单地当作新的噪声。
这个分解比较随机训练预测函数的期望风险与其训练平均函数的风险:前者比后者多出积分后的训练方差。但这不意味着平均函数可以直接得到:要精确计算它,须对所有可能训练集的分布取平均。把多个拟合预测函数取平均有时能近似这个想法,但能消除多少变动取决于它们之间的相关性。恒等式本身并不假设实际得到的一批拟合预测函数相互独立。
例题详解
例题 10.1.6
(利用有界范围估计比例)
对独立的 Bernoulli 观测,区间长度为一。要使样本比例绝对误差至少 的概率不超过 ,只需要求 。向上取整得 738 个观测。先前只用方差的不等式给出保守的一致要求 2000。较强的结论使用了有界性,但它仍是充分条件,而非必要样本量。两项计算都不能在查看一个样本后证明其实际误差。
例题 10.1.7
(在六十四个独立训练的候选中选择)
设验证损失落在 ,,,。则 。精确的经验选择,其总体风险在概率至少 的事件上,至多为最佳候选风险加约 。若允许优化误差 ,该超额上界增至约 。
候选可共享训练观测、特征或架构。只要整份清单在接触独立验证标签之前已经固定,这并不影响上述条件论证。相反,看过这些标签后反复发明新的候选,会改变受控的清单。有效的分析必须把这个更大的选择程序纳入,或保留另一个独立样本。
例题 10.1.8
(有偏估计可能有较低预测风险)
设响应为成功概率 的 Bernoulli 变量,从 个独立训练响应拟合常数预测。考虑 ,其中 固定。它相对于 的平方偏差为 ,训练方差为 。新响应的风险再加上不可消除的噪声 。
当 、 时,样本平均的估计误差为 。取 ,平方偏差为 、方差为 ,合计 。因此新响应的预测风险分别为 及 。在这个分布下,有偏规则较好。然而当 时,样本平均完全准确,同一有偏规则的估计误差却是 。这只是一个比较,并非普遍支持收缩。
常见错误
有限方差不意味着有界范围,所以不能据此使用刚证明的指数界。罕见而极大的损失可以有有限方差,同时违反任何设想中较小的确定范围。证明在方差一步使用了有界性,方差假设不能取代它。
反例模式
有限方差不能给出有界区间的指数
断言:对方差为 的独立观测,把 换成 (具有相同方差的两点分布的宽度平方)后不等式仍成立。取 ,令 以各 的概率取 或 ,其余取 。则 、,而 。断言在 给出 ,约 ,远小于实际概率。若用正确区间 ,定理给出 ,虽平凡但正确。指数部分只含方差的界需要本节没有证明的额外假设。
常见错误
(只限制预测而不限制响应)
对平方损失,若响应及每个预测都限制在 内,就得到有效范围 。若响应仍然无界,只限制预测并不能限制平方损失。
常见错误
(只计算自适应搜索最后留下的模型)
有限清单与按验证标签拟合的函数类是不同的对象。只计算最后的少数模型,没有计入自适应搜索中考察过的每一种可能。同样,在这个论证中,训练分数不能代替独立的验证分数。证明的目标是:对一个独立于评估样本而固定的函数族,得到同时成立的事件。
函数类的有限网,或 Rademacher 复杂度,取代对固定清单的并集。
自然的下一个问题
对无限函数类,什么取代 M 的对数?
函数类的有限网,或 Rademacher 复杂度,取代对固定清单的并集。
并集界付出 的代价,对有无限多个成员的参数族毫无用处。若损失对有界集合中的参数 Lipschitz 连续,该集合的有限网便可充当清单,代价是一个离散化误差。另一种做法是通过函数类的 Rademacher 复杂度,估计整个类上最大偏差的期望。本章后续的笔记会发展这两条路线。
常见错误
(把逼近误差与平方偏差混为一谈)
偏差与方差的说法必须指明估计量及其随机性。逼近误差关乎函数族中可得的最佳函数;平方偏差关乎某个特定训练程序所产生的平均函数。即使函数族包含真实目标,该程序仍可能引入偏差。扩大函数族可能降低族内最佳误差,同时增加拟合规则的变动。
总结
已知有界性把平均误差的控制加强为指数概率不等式。有限并集界使保证在固定清单中选择后仍然成立。所得的风险比较分开族内最佳风险、估计容许量与拟合容许量。对平方损失,再对独立训练样本取平均,可进一步分开条件噪声、平方偏差与训练方差。每个结论都取决于其所述的数据切分及概率模型。
练习
快速检查
(十六个独立于验证而固定的候选,其损失都在 内。按定理, 须多大才能以至少 的概率保证所有风险差距同时不超过 ?给出精确的对数式及一个整数。)
解答 · 答案
解 得 。这约为 ,所以 1615 个观测足够。有界性及独立验证的假设是这个计算不可缺少的前提。
快速检查
(对 的 Bernoulli 训练数据,比较 与 的平方估计误差。这个逐点比较能否找出对每个 都最好的估计量?)
解答 · 答案
在 处两个规则都无偏。它们的估计误差分别为 及 ,所以较小的 在这个比较中较好。在 处,样本平均误差为零,而任何 都有正的平方偏差。因此在单一分布上的结论,不能给出对所有 Bernoulli 分布的一致占优。
快速检查
(设 ,且每个候选预测都在 内。求平方损失的有效上界 。若候选清单的最佳风险比理想风险高 ,一致差距容许量为 ,拟合容许量为 ,求所得的超额风险界。)
解答 · 答案
响应与预测之差的绝对值最大为五,所以 有效;损失非负。在同时成立的事件上,相对于理想风险的超额风险至多为 。比对称共同界捷径更精细的范围是合理的,因为它直接由所述响应及预测区间得出。
快速检查
(解释为何零训练误差不会触发有限清单定理。给出一个具体分布,以及一个训练误差为零、但总体平方风险为一的训练相依函数。)
解答 · 答案
令 在 上均匀分布,。对有限的已实现训练输入集,定义预测函数在这些点上为零、其他位置为一。它可测,训练损失为零,而总体风险为一,因为新的连续输入命中该有限集的概率为零。这个预测函数由被评估的观测构造,所有可能的这类函数所成的集合,也不是定理中那份独立固定的有限清单。