交叉验证（cross validation） 可能是最简单和使用最广泛的估计预测误差的方法。这个方法直接估计预期样本外误差 $\text{Err}=\operatorname{E}[L(Y,\hat{f}(X))]$，即为模型 $\hat{f}(X)$ 应用在 $X$ 与 $Y$ 联合分布下的独立测试样本上的平均泛化误差。如之前所述，我们希望交叉验证可以估计出固定训练集 $\mathcal{T}$ 时的条件期望误差。但如在第 7.12 节进行说明的，交叉验证通常只能较好地估计出期望预测误差。
7.10.1 K 折交叉验证
理想情况下，如果有足够多数据，可留出一个验证集用来评估预测模型的表现。由于数据量经常是稀缺的，这个做法通常不可行。为应对这个问题，K 折（K-fold）交叉验证使用可用数据的一部分来拟合模型，另一部分来测试模型。我们将数据大致分成大小基本相同的 K 个部分；例如，当 $K=5$ 时，如下图所示：
针对第 k 个部分（上图为第三个），用其他 $K-1$ 部分的数据来拟合模型，再用训练好的模型预测第 k 部分中的数据，据此计算预测误差。对每个 $k=1,2,\dots,K$ 进行这样的操作，然后将 K 个预测误差的估计结合在一起。
以下更详细地说明。令 $\kappa:\{1,\dots,N\}\rightarrow\{1,\dots,K\}$ 为索引函数，表明了第 i 个观测样本经过随机分组后进入的组别。记 $\hat{f}^{-k}(x)$ 为在排除掉第 k 部分数据后拟合的函数。那么预测误差的交叉验证估计为：
$$\operatorname{CV}(\hat{f}) = \frac{1}{N} \sum_{i=1}^N L(y_i, \hat{f}^{-\kappa(i)}(x_i)) \tag{7.48}$$K 的典型选择为 5 或 10（讨论见下）。$K=N$ 的情况被称为 留一法（leave-one-out，LOO） 交叉验证。此时 $\kappa(i)=i$，针对观测样本 $i$ 的拟合使用了排除了其自身之外的所有数据。
给定一个由调节参数 $\alpha$ 控制的模型集合 $f(x,\alpha)$，记 $\hat{f}^{-k}(x,\alpha)$ 为使用去除第 k 部分的数据以及参数 $\alpha$ 拟合的模型。则对这些模型可定义：
$$\operatorname{CV}(\hat{f}, \alpha) = \frac{1}{N} \sum_{i=1}^N L(y_i, \hat{f}^{-\kappa(i)}(x_i, \alpha)) \tag{7.49}$$函数 $\operatorname{CV}(\hat{f},\alpha)$ 提供了一个测试误差曲线的估计，我们可找出使其最小化的调节参数 $\hat{\alpha}$。而最终选中的模型即为 $f(x,\hat{\alpha})$，然后再用所有数据进行拟合。
一个值得关注的问题是 K 折交叉验证所估计的是什么。当 $K=5$ 或 $K=10$ 时，每一折中所用的训练集与原始训练集有很大不同，好像估计的是预期误差 $\text{Err}$。另一方面，当 $K=N$ 时，交叉验证又好像在估计条件误差 $\text{Err}_\mathcal{T}$。但根据第 7.12 节的讨论，交叉验证只能有效地估计平均误差 $\text{Err}$。
那么应该如何选择 K？当 $K=N$ 时，交叉验证的估计是真实（预期）预测误差的近似无偏的估计，但由于 $N$ 个“训练集”彼此之间过于相似，它可能有较大方差。同时也需要考虑进行 N 次模型训练的计算负担。在一些特定问题中，这种计算可以很快完成，见练习 7.3 和练习 5.13。
另一方面，假设 $K=5$，检查验证的方差较低。但偏差可能会导致一些问题，而这取决于学习方法的表现受训练样本大小的影响程度。图 7.8 是一个假定的某个任务的学习器的“学习曲线”，即 $1-\text{Err}$ 对训练集大小 $N$ 的曲线。随着样本量增加到 100，分类器的表现提升；而将样本量增加到 200 只会继续带来很弱的改进。若训练集中有 200 个观测点，那么五折交叉验证所估计的是在训练样本量为 160 的分类器的表现，从图 7.8 中可见其与全样本量 200 时的表现一样。因此交叉验证不会产生很大偏差。然而若训练集中有 50 个观测点，那么五折交叉验证所估计的是在训练样本量为 40 的分类器的表现，从图中可见这时会低估 $1-\text{Err}$。因此交叉验证对 $\text{Err}$ 的估计会存在向上的偏差。
综上所述，若学习曲线在给定的训练集大小处有较大的斜率，那么五折或十折交叉验证会过大估计真实的预测误差。这个偏差是否会影响实际应用，还要看具体应用目标是什么。另一方面，留一法交叉验证偏差低但可能方差高。一般来说，五折或十折是比较好的折中，见 Breiman and Spector (1992) 和 Kohavi (1995)。
使用图 7.3 中右下图场景中的单一训练集进行估计，图 7.9 展示了预测误差和十折交叉验证的曲线。这是一个二分类问题，使用的是由最优子集回归选择 $p$ 个特征的线性模型。从每部分中得到的各个误分类错误率可计算出标准误差，图中体现为点上方和下方的横线范围。两个曲线都在 $p=10$ 处达到最小值，但交叉验证曲线在 10 附近比较平缓。通常在交叉验证中应用“一个标准误差（one standard error）”规则，即选择误差高于最优模型一个标准误差水平之内最简约的模型。据此，这里会选择 $p=9$ 个自变量的模型，而真实的模型中 $p=10$。
广义交叉验证（generalized cross-validation，GCV） 给平方误差损失的线性拟合中的留一法交叉验证提供了一个方便的近似。如第 7.6 节中所定义，一个线性拟合方法可写为：
$$\hat{\mathbf{y}} = \mathbf{S} \mathbf{y} \tag{7.50}$$在很多线性拟合方法中：
$$\frac{1}{N} \sum_{i=1}^N [y_i-\hat{f}^{-i}(x_i)]^2 = \frac{1}{N}\sum_{i=1}^N \left[ \frac{y_i-\hat{f}(x_i)}{1-S_{ii}} \right]^2 \tag{7.51}$$其中 $S_{ii}$ 是 $\mathbf{S}$ 的第 i 个对角线元素（练习 7.3）。GCV 近似可写为：
$$\operatorname{GCV}(\hat{f}) = \frac{1}{N} \sum_{i=1}^N \left[ \frac{y_i - \hat{f}(x_i)}{1-\text{trace}(\mathbf{S})/N} \right]^2 \tag{7.52}$$如第 7.6 节中所定义，$\operatorname{trace}(\mathbf{S})$ 是有效参数数量。
在一些场景中，$\mathbf{S}$ 的迹（trace）要比单独的对角元素 $S_{ii}$ 更容易计算，GCV 在计算上更有优势。在平滑问题中，GCV 也可以减轻交叉验证平滑不足的趋势。通过近似关系 $1/(1-x)^2\sim1+2x$ 中可看出 GCV 与 AIC 的相似之处（练习 7.7）。
7.10.2 进行交叉验证的错误和正确方式
在应用中，例如对基因组或蛋白组的研究，可能存在大量的自变量。通常的分析策略可能如下：
- 筛选自变量：寻找与类别标签有较强的（单变量）相关性的“好”自变量。
- 用这个子集中的自变量，建立多元分类器。
- 使用交叉验证估计未知的调节参数，并估计最终模型的预测误差。
这是否是正确地应用交叉验证？考虑这样的场景，有 50 个均匀分布的二分类样本，有 $p=5000$ 个独立于分类标签的数值自变量（标准高斯分布）。则任意模型的真实（测试）误差率为 50%。根据上述的分析策略，在第（1）步中选择与分类标签最相关的 100 个自变量，然后在第（2）步中基于这 100 个自变量使用 1-近邻分类器。对这个场景进行 50 次模拟的结果，平均交叉验证误差率为 3%。这远低于 50% 的真实误差率。
发生了什么？问题在于自变量中存在不正常的有利条件，因为在第（1）步中是基于所有的样本进行的变量选择。如果分类器中的自变量是这样选出的，由于这些自变量已“见识”过所有的样本，所以在交叉验证中并没有真正地实现训练集与测试集的独立。
图 7.10（上图）演示了这个问题。基于 50 个样本先选出 100 个与分类标签最相关的自变量。然后类似五折交叉验证，随机选出 10 个样本，并在这 10 个样本上计算选好的 100 个自变量与分类标签的相关系数。结果的平均相关度为 0.28，而不是真实模型的 0 左右。
在这个例子中，下面是正确的交叉验证操作：
- 将样本随机分成 K 个交叉验证组。
- 对每个 $k=1,2,\dots,K$
- 使用排除第 k 组后的样本，寻找与类别标签有较强的（单变量）相关性的“好”自变量。
- 使用排除第 k 组后的样本，用这个子集中的自变量，建立多元分类器。
- 使用训练好的分类器预测第 k 组中样本的分类标签。
将所有 K 折的步骤（2.2）中的误差估计累积起来，就得到了预测误差的交叉验证估计。在流程中的第 k 折中，在第 k 组 10 个样本上计算步骤（2.1）中正确选出的 100 个自变量与分类标签的相关系数，结果的分布图展示在图 7.10 的下图。可见其平均值大约为 0，正如真实的模型。
一般来说，在多步骤的建模流程中，交叉验证必须要实施在建模的整体步骤上。尤其是必须要在进行任何选择或过滤步骤前，保留出独立的测试集。有一类操作是允许的：在保留测试集之前，可以进行初始的无监督筛选步骤。例如，在开始交叉验证之前，可以先选出在 50 个样本上的方差最大的 1000 个自变量。由于这种筛选没有涉及到分类标签，所以它没有给自变量带来不正常的有利条件。
尽管读者能清楚地看出问题所在，但笔者在顶级学术杂志发表的论文中曾多次看到这种错误。在基因组和其他领域中，自变量的数量常常非常大，急剧地加重了这种错误的潜在影响，对这个问题的更详细讨论，请见 Ambroise and McLachlan (2002)。
7.10.3 交叉验证真的有用吗？
我们再考察高维度分类问题中交叉验证的性质。考虑一个场景中有 $N=20$ 个二分类样本，每一类样本数相等，有 $p=500$ 个与类别标签独立的量化自变量。同上，任意分类器的真实误差率应是 50%。考虑一个简单的单变量分类器：最小化误分类误差的单次划分（“树桩（stump）”模型）。决策树桩是只有一次划分的决策树，第十章的提升方法中也会使用。一个简单的论述认为在这个场景中交叉验证可能会失效1。
通过对全样本的拟合会找到一个可很好划分样本的自变量。若进行五折交叉验证，这个自变量应该对任意的 4/5 和 1/5 部分数据也能很好地划分。因此其交叉验证误差会比较小（远小于 50%）。因此交叉验证不会给出误差的准确估计。
图 7.11 对这个情景进行了模拟来探讨这个论述是否正确。一次模拟中有 500 个自变量和 20 个样本，两个类型各占一半，自变量都服从标准高斯（正态）分布。左上图展示了 500 个树桩训练样本拟合中的训练误差个数。其中用颜色标记出了误差最少的六个自变量。右上图中，用样本随机的 4/5 部分（16 个样本）拟合树桩，用剩下的 1/5 部分（4 个样本）计算测试误差，图中的点为测试误差2。其中有颜色的点分别对应着左上图中同样颜色点的自变量。可见蓝色点代表的自变量产生的树桩（左上图中的最佳点）在四个测试样本上有两个误分类误差（50%），并没有好于随机分类。
为什么与论述的结论不同？在之前的论述中没有注意到在交叉验证中模型必须要在每一折过程中对样本完全重新训练。在这个例子中，这意味着最佳的自变量和对应的划分点需要由这 4/5 部分数据来决定。从右上图可看出这种变量选择的效果。由于类别标签与自变量独立，树桩在 4/5 部分训练数据上的表现不能体现出其在剩下的 1/5 部分数据上的表现。左下图展示了划分点选择的影响。图中为第 436 个自变量的数据，也就是左上图中蓝色的点。用颜色标记的点为 1/5 部分测试数据，而剩余的点为 4/5 部分训练数据。图中标记出了基于全部训练集和 4/5 的训练集产生的自变量最优划分点。基于全部训练集的划分，在 1/5 的测试集上没有误差。但在交叉验证中需要根据 4/5 的训练集来确定划分，这会在 4 个样本上带来 2 个误差。
右下图为对 50 组模拟数据进行五折交叉验证的结果。正如我们所期望，平均交叉验证误差大约为 50%，即这个分类器的真实期望预测误差。因此交叉验证的结果与所期待的一致。另一方面，误差估计中有较大的波动，因此提供交叉验证估计值的估计标准误差非常重要。练习 7.10 从另一种形式讨论了这个问题。
本节练习
练习 7.3
令 $\hat{\mathbf{f}}=\mathbf{S}\mathbf{y}$ 为 $\mathbf{y}$ 的一个线性平滑器。
- 若 $S_{ii}$ 为 $\mathbf{S}$ 的第 i 个对角元素，证明从最小二乘投影和三次平滑样条中得出的 $\mathbf{S}$，它的交叉验证残差可写为： $$y_i - \hat{f}^{-i}(x_i) = \frac{y_i - \hat{f}(x_i)}{1 - S_{ii}} \tag{7.64}$$
- 通过这个结论，证明 $|y_i-\hat{f}^{-i}(x_i)| \geq |y_i-\hat{f}(x_i)|$。
- 找出使结论 7.64 成立的任意平滑器 $\mathbf{S}$ 的一般性约束条件。
练习 7.7
利用近似关系 $1/(1−x)^2\approx1+2x$，说明 $C_p$/AIC（7.26）和 GCV（7.52）之间的关联关系，其主要的不同是用于估计噪声方差 $\sigma_\varepsilon^2$ 的模型。
练习 7.10
在第 7.10.3 节的例子中，假设所有的 $p$ 个自变量都是二元的，因此不再需要估计分割点。自变量和之前一样独立于类别标签。那么如果 $p$ 非常大，我们很可能会找到一个可以完美地将所有训练集分隔开的自变量，因而它也会完美地将验证集分隔开。因此这个自变量的交叉验证误差为零。这是否意味着在这个情景中交叉验证没有给出对测试误差的一个良好的估计？（由 Li Ma 提供的问题。）