在机器学习里，通常来说我们不能将全部用于数据训练模型，否则我们将没有数据集对该模型进行验证，从而评估我们的模型的预测效果，也就无法从某些候选模型中选择最适合某个学习问题的模型。以多元回归模型为例：$h_\theta(x)=g(\theta_0+\theta_1x+\theta_2x^2+…++\theta_kx^k)$。应该如何确定k的大小，使得该模型对解决相应的分类问题最为有效？如何在偏倚（bias）和方差（variance）之间寻求最佳的平衡点？更进一步，我们同样需要知道如何在加权回归模型中选择适当的波长参数$\Gamma$，或者在基于范式$l_1$的SVM模型中选择适当的参数C？
我们假设模型集合为有限集$\mathcal M=\{M_1,…,M_d\}$我们的目的就是从这d个模型中，选择最有效的模型。
假设样本集为S，根据经验风险最小化原则（ERM），可能会使用这样的算法：
- 在S上训练每个模型$M_i$，得到相应的假设函数$h_i$；
- 选择训练误差最小的假设函数，即为我们需要的函数。
然而，这样的算法实际上并不有效。以多元回归模型为例，指数越高，对样本集S的拟合就越准确，这样虽然保证了较低的训练误差，但是这种方法会使泛化误差变得很大，因此，这并不是一个好的方法。
为了解决这一问题，有如下常用的方法。
下面介绍的各种交叉验证的方法，可用于模型的选择，但也可以针对单个算法和模型进行评价。
简单交叉验证
第一种是最简单的，也是很容易就想到的。我们可以把整个数据集分成两部分，一部分用于训练$S_{train}$，一部分用于验证$S_{cv}$，这里称作$S_{cv}$简单交叉验证集。这也就是我们经常提到的训练集（training set）和验证集（Validation set）。
例如，如上图所示，我们可以将蓝色部分的数据作为训练集（包含7、22、13等数据），将右侧的数据作为测试集（包含91等），这样通过在蓝色的训练集上训练模型，在测试集上观察不同模型不同参数对应的MSE的大小，就可以合适选择模型和参数了。详细步骤如下：
- 在$S_{train}$上训练每个模型$M_i$，得到相应的假设函数$h_i$；
- 将每个假设函数$h_i$通过交叉验证集$S_{cv}$进行验证，选择使得训练误差$\hat{\varepsilon}_{S_{cv}}(h_i)$最小的$h_i$；
- 通过简单交叉验证，可以得到每个假设函数$h_i$的真实的泛化误差，从而可以选择泛化误差最小的那个假设函数。
通常，预留1/4-1/3的样本作为交叉验证集，而剩下的作为训练集使用。
步骤3也可以替换成这样的操作：选择相应的模型$M_i$，使得训练误差$\hat{\varepsilon}_{S_{cv}}(h_i)$最小，然后在用对整个样本集S进行训练得到新的$h_i$。使用这样的方法原因是有的学习算法对于初试的条件非常敏感，因此，他也许在上表现良好，但是在整个样本集中却存在很大的误差，因此需要再次带入整个样本集进行验证。
不过，这个简单的方法存在两个弊端。
弊端1
最终模型与参数的选取将极大程度依赖于你对训练集和测试集的划分方法。什么意思呢？我们再看一张图：
右边是十种不同的训练集和测试集划分方法得到的test MSE，可以看到，在不同的划分方法下，test MSE的变动是很大的，而且对应的最优degree也不一样。所以如果我们的训练集和测试集的划分方法不够好，很有可能无法选择到最好的模型与参数。
弊端２
该方法只用了部分数据进行模型的训练
我们都知道，当用于模型训练的数据量越大时，训练出来的模型通常效果会越好。所以训练集和测试集的划分意味着我们无法充分利用我们手头已有的数据，所以得到的模型效果也会受到一定的影响。
基于这样的背景，有人就提出了Cross-Validation方法，也就是交叉验证。
Cross-Validation
LOOCV（Leave-one-out cross-validation）
首先，我们先介绍LOOCV方法，即（Leave-one-out cross-validation）。像Test set approach一样，LOOCV方法也包含将数据集分为训练集和测试集这一步骤。但是不同的是，我们现在只用一个数据作为测试集，其他的数据都作为训练集，并将此步骤重复N次（N为数据集的数据数量）。
如上图所示，假设我们现在有n个数据组成的数据集，那么LOOCV的方法就是每次取出一个数据作为测试集的唯一元素，而其他n-1个数据都作为训练集用于训练模型和调参。结果就是我们最终训练了n个模型，每次都能得到一个MSE。而计算最终test MSE则就是将这n个MSE取平均。
$y_i$比起test set approach，LOOCV有很多优点。首先它不受测试集合训练集划分方法的影响，因为每一个数据都单独的做过测试集。同时，其用了n-1个数据训练模型，也几乎用到了所有的数据，保证了模型的bias更小。不过LOOCV的缺点也很明显，那就是计算量过于大，是test set approach耗时的n-1倍。
为了解决计算成本太大的弊端，又有人提供了下面的式子，使得LOOCV计算成本和只训练一个模型一样快。
其中$\hat{y_i}$表示第$i$个拟合值，而$h_i$则表示leverage。关于$h_i$的计算方法详见线性回归的部分（以后会涉及）。
K-fold Cross Validation
另外一种折中的办法叫做K折交叉验证，和LOOCV的不同在于，我们每次的测试集将不再只包含一个数据，而是多个，具体数目将根据K的选取决定。比如，如果K=5，那么我们就为五折交叉验证。k-折交叉验证将样本集随机划分为k份，k-1份作为训练集，1份作为验证集，依次轮换训练集和验证集k次，验证误差最小的模型为所求模型。具体方法如下：
- 随机将样本集S划分成k个不相交的子集，每个子集中样本数量为m/k个，这些子集分别记作$S_1,…,S_k$；
- 对于每个模型$M_i$，进行如下操作：
for j=1 to k
将$S_1\cup…\cup S_{j-1}\cup S_{j+1}\cup…\cup S_k$作为训练集，训练模型$M_i$，得到相应的假设函数$h_{ij}$。
再将$S_j$作为验证集，计算泛化误差$\hat{\varepsilon}_{S_{j}}(h_{ij})$； - 计算每个模型的平均泛化误差，选择泛化误差最小的模型$M_i$。
整体公式可以表示为：
K-折交叉验证方法，每次留作验证的为总样本量的1/k(通常取k=10)，因此每次用于训练的样本量相应增加了，然而K-折交叉验证对于每个模型都需要运行k次，他的计算成本还是较高的。
不难理解，其实LOOCV是一种特殊的K-fold Cross Validation（K=N）。再来看一组图：
每一幅图种蓝色表示的真实的test MSE，而黑色虚线和橙线则分贝表示的是LOOCV方法和10-fold CV方法得到的test MSE。我们可以看到事实上LOOCV和10-fold CV对test MSE的估计是很相似的，但是相比LOOCV，10-fold CV的计算成本却小了很多，耗时更少。
Bias-Variance Trade-Off for k-Fold Cross-Validation
最后，我们要说说K的选取。事实上，和开头给出的文章里的部分内容一样，K的选取是一个Bias和Variance的trade-off。
K越大，每次投入的训练集的数据越多，模型的Bias越小。但是K越大，又意味着每一次选取的训练集之前的相关性越大（考虑最极端的例子，当k=N，也就是在LOOCV里，每次都训练数据几乎是一样的）。而这种大相关性会导致最终的test error具有更大的Variance。
一般来说，根据经验我们一般选择k=5或10。
Cross-Validation on Classification Problems
上面我们讲的都是回归问题，所以用MSE来衡量test error。如果是分类问题，那么我们可以用以下式子来衡量Cross-Validation的test error：
其中Erri表示的是第i个模型在第i组测试集上的分类错误的个数。
图片来源：《An Introduction to Statistical Learning with Applications in R》
深度学习框架中验证集作用
对于一个模型来说，其参数可以分为普通参数和超参数。在不引入强化学习的前提下，那么普通参数就是可以被梯度下降所更新的，也就是训练集所更新的参数。另外，还有超参数的概念，比如网络层数、网络节点数、迭代次数、学习率等等，这些参数不在梯度下降的更新范围内。尽管现在已经有一些算法可以用来搜索模型的超参数，但多数情况下我们还是自己人工根据验证集来调。
那也就是说，从狭义来讲，验证集没有参与梯度下降的过程，也就是说是没有经过训练的；但从广义上来看，验证集却参与了一个“人工调参”的过程，我们根据验证集的结果调节了迭代数、调节了学习率等等，使得结果在验证集上最优。因此，我们也可以认为，验证集也参与了训练。
总结
小结：交叉验证是一种模型选择或者参数选择方法，其将样本的一部分用于训练，另一部分用于验证。因此不仅考虑了训练误差，同时也考虑了泛化误差。从这里可以看出机器学习、数据挖掘与传统统计学的一个重要差别：传统统计学更注重理论，追求理论的完整性和模型的精确性，在对样本建立某个特定模型后，用理论去对模型进行各种验证；而机器学习/数据挖掘则注重经验，如交叉验证，就是通过不同模型在同一样本上的误差表现好坏，来选择适合这一样本的模型，而不去纠结理论上是否严谨。
参考
【机器学习】Cross-Validation（交叉验证）详解
斯坦福大学机器学习——交叉验证
深度学习-超参数和交叉验证
tensorflow：训练集、测试集、验证集
