一、经验误差与过拟合

1. 错误率与精度

• 错误率(error rate)：分类错误的样本数占样本总数的比例，即如果在$mm$个样本中有$aa$个样本分类错误，则错误率为$E=\frac{a}{m}E\; =\; \backslash frac\; \{a\}\{m\}$
• 精度(accuracy)：$1-\frac{a}{m}1-\backslash frac\; \{a\}\{m\}$，即精度=1-错误率

2. 误差(error)

定义：学习器的实际预测输出与样本的真实输出之间的差异

• 训练误差(training error)或经验误差(empirical error)：学习器在训练集上的误差
• 泛化误差(generalization error)：在新样本上的误差

3. 过拟合与欠拟合

• 过拟合(overfitting)：当学习器把训练样本学得“太好”了的时候，很可能已经把训练样本自身的一些特点当作所有潜在样本都会具有的一般性质，这样会导致泛化性能下降。
  PS：很多因素可能导致过拟合，最常见的情况是由于学习能力过于强大，过拟合是无法彻底避免的，只能缓解或者说减少其风险
• 欠拟合(underfitting)：对训练样本的一般性质尚未学好，由学习能力低下造成的

二、评估方法

通常，可通过实验测试来对学习器的泛化误差进行评估并进而做出选择。为此，需使用一个测试集来测试学习器对新样本的判别能力，然后以测试集上的“测试误差”作为泛化误差的近似。通常，假设测试样本也是从样本真实分布中独立同分布采样而得。需注意的是，测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现、未在训练过程中使用过。

只有一个包含$mm$个样例的数据集$D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_m,y_m)\}D=\backslash \{(x\_1,y\_1),(x\_2,y\_2),\backslash ldots,(x\_m,y\_m)\backslash \}$，既要训练，又要测试，就需要对$DD$进行适当的处理，从中产生出训练集$SS$和训练集$TT$.以下为几种常见的做法.

2.1 留出法(hold-out)

直接将数据集$DD$划分为两个互斥的集合，其中一个集合作为训练集$SS$，另一个作为测试集$TT$，即$D=S\cup T,S\cap T=\mathrm{\varnothing }D\; =\; S\; \backslash cup\; T,\; S\; \backslash cap\; T\; =\; \backslash varnothing$. 在$SS$上训练出模型后，用$TT$来评估其测试误差，作为对泛化误差的估计。

注意：
① 训练/测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。例如在分类任务中至少要保持样本的类别比例相似.如果从采样(sampling)的角度来看待数据集的划分过程，则保留类别比例的采样方式通常称为“分层采样”(stratified sampling)
② 即便在给定训练/测试集的样本比例后，仍存在多种划分方式对初始数据集$DD$进行分割。这些不同的划分将导致不同的训练/测试集，相应的，模型评估的结果也会有差别。因此，单次使用留出法得到的估计结果往往不够稳定可靠，在使用留出法时，一般要采用若干次随机划分、重复实验评估后取平均值作为留出法的评估结果。

缺点：
我们希望评估的是用$DD$训练出的模型的性能，但留出法需划分训练/测试集，会导致一个窘境：令训练集$SS$包含绝大多数样本，则训练出的模型可能更接近于用$DD$训练出的模型，但由于$TT$比较小，评估结果可能不够稳定准确；若令测试集$TT$多包含一些样本，则训练集$SS$与$DD$差别更大了，被评估的模型与用$DD$训练出的模型相比可能有较大差别，从而降低了评估结果的保真性(fidelity).

这个问题没有完美的解决方案，常见做法是将大约$\frac{2}{3}\backslash frac\; \{2\}\{3\}$ ~ $\frac{4}{5}\backslash frac\; \{4\}\{5\}$的样本用于训练，剩下样本用于测试

2.2 交叉验证法(cross validation)

先将数据集$DD$划分为$kk$个大小相似的互斥子集，即$D=D_1\cup D_2\cup \dots \cup D_k,D_i\cap D_j=\mathrm{\varnothing }(i\mathrm{\ne }j)D\; =\; D\_1\; \backslash cup\; D\_2\; \backslash cup\; \backslash ldots\; \backslash cup\; D\_k,\; D\_i\; \backslash cap\; D\_j\; =\; \backslash varnothing(i\; \backslash neq\; j)$. 每个子集$D_{i}D\_i$都尽可能保持数据分布的一致性，即从$DD$中通过分层采样得到。然后，每次用$k-1k-1$个子集的并集作为训练集，余下的那个子集作为测试集；这样就可获得$kk$组训练/测试集，从而可进行$kk$次训练和测试，最终返回的是这$kk$个测试结果的均值。

• 显然，交叉验证法评估结果的稳定性和保真性在很大程度上取决于$kk$的取值，为强调这点，通常把交叉验证法称为“$kk$折交叉验证($kk$-fold cross validation)”
• $kk$最常用的取值为10；其他常用的取值有5，20等

与留出法相似，将数据集$DD$划分为$kk$个子集同样存在多种划分方式。为减少因样本划分不同而引入的差别，$kk$折交叉验证通常要随机使用不同的划分重复$pp$次，最终的评估结果是这$pp$次$kk$折交叉验证结果的均值，例如常见的有“10次10折交叉验证”。

留一法(Leave-One-Out，简称LOO)：

交叉验证的一个特例。假定数据集$DD$中包含$mm$个样本，令$k=mk=m$.

• 留一法不受随机样本划分方式的影响，因为$mm$个样本只有唯一的方式划分为$mm$个子集--每个子集包含一个样本
• 留一法使用的训练集与初始数据集相比只少了一个样本，这就使得在绝大多数情况下，留一法中被实际评估的模型与期望评估的$DD$训练出的模型很相似。

优缺点：

• 优点：留一法的评估结果往往被认为比较准确
• 缺点：
  • 在数据集比较大时，训练$mm$个模型的计算开销可能是难以忍受的
  • 留一法的估计结果也未必永远比其他评估方法准确，"没有免费的午餐"定理对实验评估方法同样适用

2.3 自助法(bootstrapping)

我们希望评估的是用$DD$训练出的模型，但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比$DD$小，这必然会引入一些因训练样本规模不同而导致的估计误差。而留一法虽受训练样本规模变化的影响较小，但计算复杂度太高了。"自助法"是一个较好的解决方案。

定义：

• 以自助采样法(也称可重复采样或有放回采样)为基础
• 给定包含$mm$个样本的数据集$DD$，对它进行采样产生数据集$D^{\mathrm{\prime }}D\text{'}$：每次随机从$DD$中挑选一个样本，将其拷贝放入$D^{\mathrm{\prime }}D\text{'}$，然后再将该样本放回初始数据集$DD$中，使得该样本在下次采样时仍有可能被采到；这个过程重复执行$mm$次后，就得到了包含$mm$个样本的数据集$D^{\mathrm{\prime }}D\text{'}$，这就是自助采样的结果。
• 显然，$DD$中有一部分样本会在$D^{\mathrm{\prime }}D\text{'}$中多次出现，而另一部分样本不出现。样本在$mm$次采样中始终不被采到的概率是$(1-\frac{1}{m}{)}^m(1-\backslash frac\; \{1\}\{m\})^m$，取极限得到${}_{m\to \mathrm{\infty }}(1-\frac{1}{m}{)}^m=\frac{1}{e}\approx 0.368\backslash lim\_\{m\; \backslash to\; \backslash infty\}\; (1-\backslash frac\{1\}\{m\})^m\; =\; \backslash frac\{1\}\{e\}\backslash approx0.368$.即通过自助采样，初始数据集$DD$中约有$36.8\mathrm{\%}36.8\backslash \%$的样本未出现在采样数据集$D^{\mathrm{\prime }}D\text{'}$中，于是将$D^{\mathrm{\prime }}D\text{'}$用作训练集，$D\mathrm{\backslash }{D}^{\mathrm{\prime }}D\backslash backslash\; D\text{'}$用作测试集

包外估计(out-of-bag estimate)

实际评估的模型与期望评估的模型都使用$mm$个训练样本，而仍有数据总量约$\frac{1}{3}\backslash frac\; \{1\}\{3\}$的、没在训练集中出现的样本用于测试，这样的测试结果被称为"包外估计"

优缺点：

• 优点：
  • 在数据集较小、难以有效划分训练/测试集时很有用
  • 自助法能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大的好处
• 缺点：
  • 自助法产生的数据集改变了初始数据集的分布，会引入估计偏差，因此在初始数据量足够时，留出法和交叉验证法更常用一些

2.4 调参与最终模型

参数调节(简称调参(parameter tuning))

大多数学习算法都有些参数需要设定，参数配置不同，学得模型的性能往往有显著差别。因此，在进行模型评估与选择，还需对算法参数进行设定。

• 调参和算法的选择类似：对每种参数配置都训练出模型，然后把对应最好的模型的参数作为结果
• 注意：学习算法的很多参数是在实数范围内取值，因此，对每种参数配置都训练出模型是不可行的。现实中常用做法，是对每个参数选定一个范围和变化步长。显然，这样选定的参数值往往不是"最佳"值，但这是在计算开销和性能估计之间进行折中的结果，通过这个折中，学习过程才变得可行。事实上，即便在进行这样的折中之后，调参依然很困难。很多强大的学习算法有不少参数需设定，这将导致极大的调参工程量，以至于在不少应用任务中，参数调得好不好往往对最终模型性能有关键性影响

最终模型

给定包含$mm$个样本的数据集$DD$，在模型评估与选择过程中由于需要留出一部分数据进行评估测试，事实上只用了一部分数据训练模型。因此，在模型选择完成后，学习算法和参数配置已选定，此时应该用数据集$DD$重新训练模型。这个模型在训练过程中使用了所有$mm$个样本，这才是最终提交给用户的模型

• 注意：通常把学得模型在实际使用中遇到的数据称为测试集，为了加以区分，模型评估与选择中用于评估测试的数据集常称为"验证集"(validation set)

在研究对比不同算法的泛化性能时，用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集和验证集，基于验证集上的性能来进行模型选择和调参