3.3 验证误差和交叉验证误差
欠拟合的问题容易解决，提高模型的复杂度即可；而过拟合却是一个难题，主要解决方法有正则化（Regulariation）和验证（Validation）。机器学习的主要任务就是最小化真实误差而不是训练误差，而且通常前者会比后者大，因为模型在未知的数据集上的表现不太可能会比在训练集中的表现好。因此，可以把真实误差分解成训练误差和一项Ω（在第6章被称为惩罚项），具体公式如下。
机器学习的真谛就是找到样本外误差的一个样本内估计（In-sample Estimate），但是使用正则化方法和验证方法做估计有所不同。
● 正则化方法通过间接估计惩罚项Ω再加上容易估计的训练误差，得到真实误差的估计值。
● 验证方法则直接估计真实误差，得到的估计值就叫作验证误差。
3.3.1 验证误差
验证集几乎和测试集一样，是从整个数据集中提取出来的一个子集。验证集和测试集的区别是：
● 验证集不是用来训练模型的，而是用来做模型选择的。
● 测试集既不是用来训练模型的，也不是用来做模型选择的。
测试集是最干净的，因此，首先将其从整个数据集中提取出来。比如随机选取20%的数据作为测试集，剩余的80%的数据作为训练集。而现在会随机从训练集中选取25%的数据作为验证集（占整个数据集的20%），剩余的75%的数据作为训练集（占整个数据集的60%），如下图所示。
训练集、验证集和测试集的划分
验证误差（Validation Error）是指模型在验证集上的误差，其计算公式如下：
h里面的参数是从训练集中拟合出来的，用在验证集的mval个样例上。
3.3.2 交叉验证误差
当数据不多时，像上面这样提取出测试集和验证集会导致没有足够多的数据用来训练模型。这时可以创建K折交叉验证集（K-Fold Cross Validation Set），即把整个数据集平均但随机分成K份，每份大概包含m/K个数据。当K=1时，得到了K折交叉验证法的一个特例：留一交叉验证法（Leave-One-Out Cross Validation，LOOCV），它不受随机样本划分方式的影响。下面用10个数据来描述这两种验证法。
续表
当数据集比较大时，LOOCV的计算成本较大。在实践中，通常选择K为5或10。
3.3.3 学习理论
一年后，斯蒂文的那个大客户又来了，他觉得模型将垃圾邮件分类的能力越来越差了。
大客户：上次你帮我开发的垃圾邮件分类模型现在的表现变差了。
斯蒂文：有可能，我准备多用几个模型，哪个在测试集上的误差最小就用哪个。
大客户：怎么能在整个学习过程中引进测试集？那测试集不就被污染了吗？我对你有一点失望。
斯蒂文：
斯蒂文感到沮丧，既然不能用测试集，那么就用一个类似测试集的数据集，即验证集。
斯蒂文：将整个数据集分成训练集Dtrain（mtrain个数据）、验证集Dval（mval个数据）和测试集Dtest（mtest个数据），用验证集来计算验证误差，不会碰到测试集。
大客户：怎么确保验证误差能很好地估计真实误差？
斯蒂文：先了解几个定义，如下图所示。
模型h和h-的区别
● 从验证集（Dval）中得到的模型为h-，用上标“-”表示有一些数据被拿走用于训练模型了。
● 原来在整个训练集（Dtv=Dtrain+Dval）上重新训练的模型被称为h。
● e（i）（h-）是模型h-测量第i个点上的误差函数。
因为数据是独立同分布的，再加上霍夫丁不等式（和测试集对应的不等式一样），可得到
可以看出，验证误差的均值是真实误差（即验证误差是真实误差的无偏估计），而两者的差距与验证集大小mval成反比。当验证集足够大时，验证误差能很好地反映真实误差。
大客户：h和h-为什么会不同？
斯蒂文：模型在不同数据集上训练肯定会不同，当然，数据集的差别越小，h和h-之差也越来越小。
大客户：明白了。最后用的模型是h，但你的结论都和h-相关，怎么和h产生联系？
斯蒂文：用以下不等关系，虽然没有严谨的数学证明，但是通常我们都认为数据越多，真实误差越小。
大客户：验证误差只不过像测试误差一样可以估计真实误差，但我还没看出它具有决定性作用。
斯蒂文：
机器学习模型太多了，因此，我们必须要有一个系统、科学的方法来选择模型，此时验证集就有用武之地了。
斯蒂文：验证集可以用来进行模型选择！假设有P个模型，用训练集来训练它们，得到H=
（上标 “-” 表示有一些数据被拿走用于训练模型了），用验证集来计算每个模型的验证误差，选一个最小的验证误差，其对应的模型就是最佳模型
。再在原来整个训练集（Dtv=Dtrain+Dval）中重新训练模型，得到的模型被称为g。整个流程如下图所示。
模型选择
通常模型个数P是有限的，而g-是从这P个模型中选出来的。类比上面关于单个模型h的不等关系，将霍夫丁不等式应用到g-上，可以得到（区别是O中的 “1” 变成了
）：
现在又遇到一个关于验证集mval大小的问题：
m val越大，g和g-的真实误差的差距越大，最终模型g的推广能力肯定不好，最好mval=1。
大客户：当验证集中只有一个数据时，你还好意思说验证误差的均值是真实误差（无偏估计）？
斯蒂文：
斯蒂文想：既然一个单点的验证误差不好，有没有办法找到很多这样的验证误差，然后加总再求平均值可能好一些。
斯蒂文：换一个思路，除了测试集，我们有mtv=mtrain+mval个数据，用交叉验证的思路，每次选一个数据当验证集，遍历除测试集外的所有数据，得到mtv个验证误差，然后加总求平均值。
计算留一交叉验证误差
从验证集（x（i），y（i））得到的模型为h-i，下标“-”表示除第i个数据都用来训练模型了，原来整个训练集（Dtv）上的重新训练的模型被称为h，如左图所示。计算平均的交叉误差
大客户：如果训练一个模型需要t秒，那么选择最佳模型需要mtvt秒，不是很高效，还有没有更高效的？
斯蒂文：还是根据交叉验证的思路，将数据大概平均分成K份，得到K个验证误差，然后加总求平均值，将K取5或10都是常见的做法。K折交叉误差为
，这样效率提高了mtv/K倍。
大客户：这个K折交叉验证听起来很合理，就按这个方法做吧。
斯蒂文：☺☺☺