动机
交叉验证分数可以有两种不同用途:协助选择学习规则,或评估一个没有使用受评估观测来作决定的规则。同一个数字若兼任两者,就把选择步骤藏起来。候选搜索范围愈大,愈可能部分因为碰上有利的评估噪声而找到低分。
嵌套交叉验证在每次外层迭代中,把这两项工作分配给不同观测。内层折选配置,再以当次外层训练部分重新拟合整个所选流程。外层折的预测没有使用该折的观测来拟合或选择。不同外层迭代可以选到不同配置;这本来就是受评估程序的一部分。
稀疏学习笔记已描述这个安排,回归流程笔记则区分了训练、验证、重新拟合和独立最终测试。这里把嵌套算法写成有限、可执行的步骤,也确认它的真正目标。外层平均涉及几个以较小训练样本运作的学习程序;它不会自动成为置信区间,也不是以独立观测量得的、使用全部开发数据拟合之最终预测器的风险。
定义
定义 27.1.1
(有次序的配置清单与完整拟合操作)
设 ,其中 ,并固定非负预测损失 。预先指定有限的有序流程配置清单 。以 表示只用索引属于 的观测来拟合配置 所得的预测器。
拟合操作包括所有需要估计的变换:缺失值填补、中心化、尺度化、特征选择、降维、系数及任何学习所得的预测阈值。配置指定拟合方法;拟合状态则依赖输入的观测。所有同分情况均按 的先后次序处理。
固定多项式次数属于配置选择,拟合后的列平均及系数向量则属于状态。提早停止规则也是方法的一部分;若它使用额外验证分割,该分割必须留在当前拟合部分之内。随机拟合器需要已声明的种子,以及独立于该次拟合所排除观测的种子产生规则。每次要求的拟合都必须有定义;例如需要两个类别的流程,不能在只有一类的训练部分上默默照常执行。
定义 27.1.2
(外层分割、内层分割与观测权重)
把 分成非空外层折 ,各自补集 亦非空。对每个 ,再把它分成 ,其中 ,且每个内层训练补集 都非空。这些是内层验证折。记 及 。
内外层均按观测数加权:
这里 是下述算法所定义的、重新拟合后的所选流程。当折大小不同,这不是各折平均损失的不加权平均。每个观测在外层分数中都占 。其他科学目标可以适合其他合并规则,但必须说明。下述概率定理使用在看数据前固定的确定索引分割。若分割独立随机产生,则要按定理后的说明给定该分割。按标签分层、分组及依时间排列的抽样,各自需要交代所得分布,不能自动套用该定理。
定理与命题
定理 27.1.3
(信息边界清楚的有限嵌套算法)
对每个外层折 ,依次执行以下步骤。
- 对每个 及内层折 ,在 上全新拟合完整流程。在 上评分,计算 。
- 按已声明的同分规则,选择令 最小的 。
- 弃用那些内层拟合状态。重新拟合 ,包括重新估计全部已学习的变换。
- 在 上记录一次预测和损失。不可用这些外层分数改变该次迭代的选择。
按上述观测权重合并外层损失。若拟合及分割规则只用已述输入和允许的种子,则每个 都是 及这些种子的函数,不依赖 。
配置清单、损失、分割方法、同分规则、预处理次序和失败处理方式,都应在评估前锁定。若看过外层结果后再改这些选择,改动后的程序便没有经过未使用观测的评估。在几次嵌套实验中保留最好的外层分数,也是在更高一层重新引入选择。
定理 27.1.4
(独立同分布抽样下,外层平均的目标)
设 独立同分布,分布为 ;外层分割是看观测前已固定的确定分割,全部允许的拟合种子均独立于数据。对每个 ,以 收集其种子,定义新观测风险
假设所有显示的损失期望均有限,则
若全部外层训练大小均为 ,而每次迭代都应用相同的大小为 之选择及重新拟合规则,包括重标索引后相同的内层分割方法,以及相同种子分布,右侧就是该大小为 的程序在重复训练下之期望风险。若大小或内层方法不同,则是相应期望风险的加权混合。
若外层分割随机产生,须假设分割与全部拟合种子联合独立于数据。先给定已实现的索引集合,再套用定理。等式此时是给定该分割下的条件等式。若折大小是随机的,对分割再取期望时,其权重必须留在期望之内。
这个精确期望等式没有确认某个使用全部数据的最终预测器之条件风险,也没有给出该风险与较小样本目标之间的一般大小关系。复杂程序收到更多数据后也可能表现较差,配置赢家亦可能随训练大小改变。即使较大样本通常有帮助,从 修正到 仍需要额外证据或假设。
定理 27.1.5
(样本平均预测器的精确留一评分)
对实数响应 ,其中 ,设 。样本平均预测器的平方损失留一评分为
预先指定的常数预测器 则有评分 。两个公式均不需要随机抽样假设。
证明与关键思路
证明
(追查哪些观测可以进入每个拟合状态)
在外层迭代 内,每个内层拟合子集和验证子集都包含于 。因此,其拟合变换、预测器、分数和按同分规则选出的配置,都只依赖 及已声明的种子。全新重新拟合具有相同信息边界。把这些操作合成,不会引入 的观测。把 应用于外层输入,是计算已固定函数的值;这不容许利用该输入或其标签重新估计变换。
这个论证核实的是所述数据流,不保证内层选择器会选出统计上最优的配置。在内层分割前先用全部 拟合一个尺度化器,虽然仍未碰外层折,却已不是这里指定的内层仅训练数据程序。每次内层都重新拟合完整流程,才能维持两道边界。
证明
(每次只条件化一个外层迭代)
固定 ,给定 及 。此时 已固定。由于索引分割独立于各个独立同分布观测,剩余每个 的 仍有分布 ,且独立于已给定的对象。因此,每项条件期望损失都是 。把 项平均便得第一式。再用全期望公式,以及 ,由期望的线性得第二式。
证明完全没有用到不同 之间的独立性。它们的预测器以重叠数据训练;某个外层迭代受评估的观测,在其他迭代中正是训练观测。我们可以逐次给定各迭代所允许的信息来证明期望等式;若同时给定所有外层拟合预测器,一般会泄露正在受评估观测的信息。
证明
(留出残差是放大后的中心化残差)
略去响应 时,拟合平均为 。因此
逐项平方再平均,就得到公式。常数预测器不会因略去观测而改变,所以其分数就是经验平方损失。平均预测器的留一误差一般大于训练误差:平均中心化平方残差被乘上 。
证明透视
每次预测确实留出,不代表各折平均独立
信息边界证明涉及一个拟合函数及它本身排除的观测。期望证明逐折使用该边界,再把期望相加。两者都没有建立各折平均的独立性。因此,把它们的样本标准差除以 来求标准误,还需要超出“共有 折”以外的论据。
例题
例题 27.1.6
(六个观测、两个配置、三个外层拟合)
所有输入均为同一常数,按索引排列的确定响应为 。预先选定索引折 、、;这个例子并不是按看过的标签分组。采用平方损失、内层留一法和有序配置 :永远预测事先指定的常数一;:预测拟合样本平均。没有其他预处理。
对 ,外层训练响应是 ,平均 ,中心化平方和为一。因此 ,而 。选 ,在全部四个外层训练观测上重新拟合平均 ,再对两个零都预测该值。外层平均平方损失为 。
对 ,外层训练响应是 ,平均为一,中心化平方和为四。因此 ,。选 ;两个留出响应都是一,所以外层损失为零。对 ,对称性给出以下完整表格。
| 外层折 | 外层训练响应 | A 内层分数 | B 内层分数 | 所选配置 | 重新拟合预测 | 外层平均损失 |
|---|---|---|---|---|---|---|
| 1 | 1, 1, 2, 2 | 1/2 | 4/9 | B | 3/2 | 9/4 |
| 2 | 0, 0, 2, 2 | 1 | 16/9 | A | 1 | 0 |
| 3 | 0, 0, 1, 1 | 1/2 | 4/9 | B | 1/2 | 9/4 |
六个外层损失为 ,所以 。若改为平均三个胜出内层分数,则得 。这是用途不同的另一个数字,并非外层评估。
例题 27.1.7
(在全部开发观测上重新执行程序)
评估后,在全部六个开发观测上再次执行相同配置选择方法,内部仍使用留一法。其平均为一,中心化平方和为四,所以 ,而 。选 ,产生最终的常数一预测器。外层赢家 不是用来多数决选 ;已声明的最终选择步骤,是在全部开发数据上重新执行。
最终预测器的训练误差为 。这个训练数字和嵌套分数 ,都没有量度它的新观测风险。这六个确定观测不会建立来自某个指定总体的独立同分布抽样。计算展示的是算法及选择结果的改变,不是真实数据实验,也不提供总体表现保证。
以下完整程序只用标准库,并以有理数作精确运算。程序索引从零开始,打印出的折编号从一开始。每次内层拟合排除正在评分的响应,而在外层预测前,所选配置都会全新重新拟合。
from fractions import Fraction as F
y = tuple(map(F, (0, 0, 1, 1, 2, 2)))
CONFIGS = ("A", "B") # Fixed one, then fitted mean; this is the tie order.
OUTER = ((0, 1), (2, 3), (4, 5))
ALL = tuple(range(len(y)))
def fit(indices, config):
assert indices and config in CONFIGS
return F(1) if config == "A" else sum(y[i] for i in indices) / len(indices)
def inner_scores(indices):
assert len(indices) >= 2
scores = {}
for config in CONFIGS:
total = F(0)
for held in indices:
train = tuple(i for i in indices if i != held)
prediction = fit(train, config)
total += (prediction - y[held]) ** 2
scores[config] = total / len(indices)
return scores
def select_and_refit(indices):
scores = inner_scores(indices)
chosen = min(CONFIGS, key=lambda c: (scores[c], CONFIGS.index(c)))
return chosen, fit(indices, chosen), scores
losses = {}
for number, held in enumerate(OUTER, 1):
train = tuple(i for i in ALL if i not in held)
chosen, prediction, scores = select_and_refit(train)
for i in held:
assert i not in train and i not in losses
losses[i] = (prediction - y[i]) ** 2
outer_mean = sum(losses[i] for i in held) / len(held)
print(f"fold {number}: A={scores['A']} B={scores['B']} "
f"choose={chosen} predict={prediction} outer={outer_mean}")
assert set(losses) == set(ALL)
print("nested MSE:", sum(losses.values()) / len(y))
chosen, prediction, scores = select_and_refit(ALL)
print(f"full development: A={scores['A']} B={scores['B']} "
f"choose={chosen} predict={prediction}")
fold 1: A=1/2 B=4/9 choose=B predict=3/2 outer=9/4
fold 2: A=1 B=16/9 choose=A predict=1 outer=0
fold 3: A=1/2 B=4/9 choose=B predict=1/2 outer=9/4
nested MSE: 3/2
full development: A=2/3 B=24/25 choose=A predict=1
例题 27.1.8
(两点计算中完全相依的留出误差)
设 是独立的公平二元标签。一个以单一观测训练的学习器,对所有输入都预测该观测的标签,使用零一损失。在普通的两折留一评估中,两个损失都等于 。所以 、,且 。
两个已观察折损失的样本标准差永远是零:每组数据只会产生 或 。把零再除以 ,会把重复抽样变动全部藏起来。这是普通交叉验证的相依性例子,不是把只有一个观测的训练部分硬分出内层折的嵌套运算。相同逻辑问题仍可能出现在嵌套评估:留出本身不建立外层损失之间的独立性。
常见误解
反例模式
用合并外层分数选择,便把它们变成选择数据
考虑独立同分布的公平二元标签,以及两个预先指定的预测器:常数零和常数一,使用零一损失。对两个观测,各固定预测器的合并留一误差就是观察到的错误比例。选择这两个比例中较小的一个,再把它报作所选预测器的评估。
两个标签相同时,所报最小值为零;不同时为 。两种情况概率各为 ,所以报告值的期望是 。但不论选哪个常数,它对独立、公平的新标签的条件风险都恰为 。每个固定候选的留出预测本来都合规;用两个标签选赢家,却破坏了所声称的最终评估解读。这里期望上的乐观差额恰为 ,不表示每组数据都严格乐观。
修补信息边界的方法,是在每个外层训练部分内选配置,再用其排除观测评估完整选择器。若用外层比较作进一步选择,就需要另一份未碰过的评估数据,或明确不同的推论分析。
反例模式
合并拟合的目标编码表可以已经藏有留出答案
设输入是独立同分布的连续标识符,标签是独立的公平比特。标识符几乎必然互不相同。在分割前,建立把每个已观察标识符对应至其标签的查找表;用该表预测,未见过的标识符则预测零。若所谓交叉验证重用这份合并数据表,每个留出观测都得零损失,因为变换已经存储它的标签。
真正的新标识符几乎必然不在表中,所以所得预测器对新标签的条件错误率为 。若表只在允许的训练观测上拟合,排除的标识符亦不在表中,便不再取得自己的答案。变换可以在最终估计器拟合前已泄露标签;把某行排除于最后的系数拟合之外,不能抹去先前的使用。
常见错误
(重复分割不是新的数据集)
重复随机分割可以描述结果对分割方法的敏感度,但各次重复仍重用观测,没有创造独立新数据集。同样,所选配置之间的分歧描述了不稳定性,却没有建立某模型在科学上正确的概率。对分组受试者或未来时间预测,应按真正独立的抽样单位和目标设计分割;把相关记录随机散到各折,可能评估了另一个问题。
概念视角
报告分数可以描述的三种对象
最小内层分数是经选择的比较数字。在相关抽样假设下,合并外层分数评估已声明的选择及重新拟合规则,训练大小是各次外层训练大小。新的独立最终测试则在给定开发数据下评估已锁定的最终预测器。三者都可能有用,但把其中一个名称换成另一个,会在没有改算术的情况下改变主张。
快速检查
快速检查
(两个外层折大小为 和 ,平均损失为 和 。计算按观测加权的分数,以及各折平均的不加权平均。本笔记定义了哪一个?)
先数出每个折平均代表多少个观测。
解答 · 答案
已定义的分数是 ,不加权平均是 。差别来自不加权折平均会让较小折中的单个损失占较大权重。两种算术都可以定义,但本笔记指定每个受评估观测权重相同。
快速检查
(拟合样本的响应为 。以平方损失和内层留一法,在固定预测值一与样本均值之间选择,再给出所选配置重新拟合后的预测。)
先算中心化平方和,再套用精确公式。
解答 · 答案
拟合平均是一,中心化平方和为四。样本平均的留一分数为 ;固定一的分数为 。选固定一,按该配置重新拟合,得到预测一。全样本预测相同不代表内层分数相同:略去观测会改变拟合平均,却不会改变固定预测器。
快速检查
(九个观测的嵌套运算使用大小为 、、 的外层折。在独立同分布定理下,其期望是否等于以六个观测训练的程序之风险?说明实际的混合。)
每个外层训练大小都是九减去其留出大小。
解答 · 答案
以 表示指定大小为 的内层选择及重新拟合规则之期望新损失。同一大小的各次迭代,均使用重标索引后相同的内层分割方法和相同种子分布。真正的期望是 。只有在这些风险另有等式或特殊关系时,它才等于 。把训练大小取平均,并不是把风险等同起来的定理。
快速检查
(在公平标签的合并选择反例中,把两个观测改为三个。计算所报最小值的期望,与新标签风险比较,并解释为什么重新拟合所选常数不能修正该报告。)
一的个数服从参数为三和二分之一的二项分布。
解答 · 答案
设 是一的个数。当 或三,总概率为 ,所报最小值为零;当 或二,总概率为 ,最小值为 。故期望是 ,但所选常数的条件新标签风险仍为 。在这个三观测构造中,差额仍是 。常数重新拟合没有学习状态可改;更一般地说,重新拟合不能把已用于选择的观测变回未碰过的评估样本。