1.1　过拟合和欠拟合的背后

一个典型的机器学习任务所使用的数据集，一般是从隐含未知的分布上独立采样得来，最终我们在数据上学习到的模型要去预测这个隐含未知的分布。我们将模型在数据集上的误差叫作经验误差（empirical error），将模型在隐含未知分布上的误差叫作泛化误差（generalization error），为了在有限的数据中可以讨论这两种误差（因为我们无法得到这个分布下的所有数据），我们将得到的数据进行分集，训练集用来得到经验误差（或者是训练误差），测试集用来得到泛化误差（或者是测试误差）。(1)

基于此，我们发展出一系列进行分集的方法，需要保证两个子集的分布的一致性，否则会导致测试误差和经验误差丧失可比性。标准的交叉验证会将数据集分为k个大小基本一致的子集，然后依次用k-1个子集做训练，剩下的做测试，最后的性能为k次训练和测试的均值，当然还有更多的分集方法，各有优劣，需要视具体情况而定。

好的学习算法应该满足两个条件：

（1）它可以将训练误差降得足够低，表明它真的学习到了某种从特征X到目标值y的函数关系。

（2）它可以将训练误差与测试误差的间隔降得足够低，表明它学习到的函数是好的，在未见过的数据上的表现依然很好。

第一个条件如果不满足，那么就代表着欠拟合，第一个条件满足而第二个条件不满足，就代表着过拟合。根据Hoeffding不等式（1.1），当我们固定好小的ε，表示这样的间隔是可以接受的，那么可以看到随着数据量的增大，泛化误差与经验误差的小间隔的概率就越大。

定义1.1（Hoeffding不等式）　假设有m个独立有界的随机变量，E_test，E_train分别代表着泛化误差和经验误差，对于任意的ε>0，就有：

泛化误差与经验误差的小间隔的概率越大，代表泛化误差与经验误差越接近，这一结论概率上是近似正确的。