交叉验证（Cross Validation）

交叉验证的定义

交叉验证（Cross Validation），有的时候也称作循环估计（Rotation Estimation），是一种统计学上将数据样本切割成较小子集的实用方法，该理论是由Seymour Geisser提出的。

在模式识别（Pattern Recognition）和机器学习（Machine Learning）的相关研究中，经常会将整个数据集合分成两个部分，分别是训练集合和测试集合。假设 $X$ 是集合全体， $A\subseteq X$ 是全集 $X$ 的非空真子集，那么非空集合 $X\setminus A\neq \emptyset$ 则是集合 $A$ 在全集 $X$ 中的补集。于是可以先在 $A$ 上面做训练和分析，而集合 $X\setminus A$ 则用来做测试和验证。一开始的集合 $A$ 被称作训练集，而它的补集 $X\setminus A$ 被称作验证集或者测试集。这里有一个重要的观点就是：只有训练集才可以使用在模型的训练之中，而测试集必须在模型训练完成之后才被用来评估模型的误差。

HoldOut检验（Hold-Out Method）

这个方法是将原始的数据集合 $X$ 随机分成两个集合 $A$ 和 $X\setminus A$ ，其中 $A$ 作为训练集， $X\setminus A$ 作为测试集。先使用训练集训练模型，然后利用测试集验证模型的效果，记录最后的分类准确率作为Hold-Out下该模型的性能指标。比方说，处理时间序列模型是否准确的时候，把整个数据集合分成前后两部分，前部分占比70%，后部分占比30%。前部分来进行时间序列模型的训练，后部分用来测试改时间序列的准确性。其准确性可以用MAE，MAPE之类的统计指标来衡量。综上所述，该方法的好处就是处理起来简单，只需要把原始数据分成两个部分即可。但是从严格意义上来说，Hold-Out检验并不算是交叉检验（Cross Validation），因为该方法没有达到交叉检验的思想，而且最后验证准确性的高低和原始数组的分类有很大的关系，所以该方法得到的结果在某些场景中并不具备特别大的说服力。在Hold-Out检验不够有说服力的情形下，有人提出了交叉验证这一个重要思想。

交叉检验的常见形式

假设有一个未知模型有一个或者多个未知的参数，并且有一个训练集。操作的过程就是对该模型的参数进行调整，使得该模型能够最大的反映训练集的特征。如果模型因为训练集过小或者参数不合适而产生过度拟合的情况，测试集的测试效果就可以得到验证。交叉验证是一种能够预测模型拟合性能的有效方法。

彻底的交叉验证（Exhaustive Cross Validation）

彻底的交叉验证方法指的是遍历全集 $X$ 的所有非空真子集 $A$ 。换句话说也就是把 $A$ 当作训练集， $X\setminus A$ 是测试集。如果 $X$ 中有 $n$ 个元素，那么非空真子集 $A$ 的选择方法则是 $2^{n}-2$ ，这个方法的时间复杂度是指数级别的。

留P验证（Leave-p-out Cross Validation)

留 $p$ 验证（LpO CV）指的是使用全集 $X$ 中的 $p$ 个元素作为测试集，然后剩下的 $n-p$ 个元素作为训练集。根据数学上的定理可以得到， $p$ 个元素的选择方法有 $C_{n}^{p}=n!/(p!\cdot(n-p)!)$ 个，其中 $n!$ 表示 $n$ 的阶乘。在这个意义下，留 $p$ 验证的时间复杂度也是非常高的。当 $p=1$ 的时候，留1验证（Leave-one-out Cross Validation）的复杂度恰好是 $C_{n}^{1}=n$ 。

不彻底的交叉验证（Non-exhaustive Cross Validation）

不彻底的交叉验证不需要考虑全集 $X$ 的所有划分情况，这种方法是留 $p$ 验证的一个近似验证算法。

k-fold交叉验证（K-fold Cross Validation）

在k-fold交叉验证中，全集 $X$ 被随机的划分成 $k$ 个同等大小的集合 $A_{1},\cdot\cdot\cdot,A_{k}$ ，换句话说也就是 $X=A_{1}\cup\cdot\cdot\cdot\cup A_{k}$ ，并且 $|A_{1}|=\cdot\cdot\cdot=|A_{k}|$ 。这里的 $|A_{i}|$ 指的是集合 $A_{i}$ 的元素个数，也就是集合的势。这个时候需要遍历 $i$ 从 $1$ 到 $k$ ，把 $X\setminus A$ 当作训练集合， $A_{i}$ 当作测试集合。根据模型的测试统计，可以得到 $A_{i}$ 集合中测试错误的结果数量 $n_{i}$ 。如果全集 $X$ 的势是 $n$ 的话，可以得到该模型的错误率是 $E=\sum_{i=1}^{k}n_{i}/n$ 。为了提高模型的精确度，可以将k-fold交叉验证的上述步骤重复 $t$ 次，每一次都是随机划分全集 $X$ 。在 $t$ 次测试中，会得到 $t$ 个模型的错误率 $E_{1},\cdot\cdot\cdot, E_{t}$ 。定义 $e=\sum_{j=1}^{t}E_{j}/t$ , $V=\sum_{j=1}^{t}(E_{j}-e)^{2}/(t-1)$ ， $\sigma=\sqrt{V}$ 。这样该模型的错误率就是 $e$ ，其方差是 $\sigma$ 。

注释：

1. 一般来说，10-fold交叉验证的情况使用得最多。

2. 当 $k=2$ 的时候，也就是最简单的k-fold交叉验证，2-fold交叉验证。这个时候 $X=A_{1}\cup A_{2}$ ，首先 $A_{1}$ 当训练集并且 $A_{2}$ 当测试集，然后 $A_{2}$ 当训练集并且 $A_{1}$ 当测试集。2-fold交叉验证的好处就是训练集和测试集的势都非常大，每个数据要么在训练集中，要么在测试集中。

3. 当 $k=n$ 的时候，也就是n-fold交叉验证。这个时候就是上面所说的留一验证（Leave-one-out Cross Validation）。综上所述，交叉验证（Cross Validation）的好处是可以从有限的数据中获得尽可能多的有效信息，从而可以从多个角度去学习样本，避免陷入局部的极值。在这个过程中，无论是训练样本还是测试样本都得到了尽可能多的学习。