模型评估与选择

经验误差与过拟合

通常我们把分类错误的样本数占样本总数的比例称为错误率（error rate），即若 $m$ 个样本中有 $a$ 个样本分类错误，则错误率 $E = \dfrac{a}{m}$。相应地 $1 - \dfrac{a}{m}$ 称为精度（accuracy）。

更一般地，我们把学习器的实际预测输出与样本的真实输出之间的差异称为误差（error），学习器在训练集上的误差称为训练误差（training error）或经验误差（empirical error），在新样本上的误差称为泛化误差（generalization error）。

显然我们希望得到泛化误差小的学习器，但是我们无法直接得到泛化误差，实际能做的努力是努力使经验误差最小化。然而经验误差很小、在训练集上表现很好的学习器，在多数情况下泛化能力都并不好。

我们实际希望的，是在新样本上能表现得很好的学习器。为了达到这个目的，应该从训练样本中尽可能学出适用于所有潜在样本的「普遍规律」，这样才能在遇到新样本时做出正确的判别。然而当学习器把训练样本学得「太好了」时，很可能将训练样本自身一些特点当作了所有潜在样本都会具有的一般性质，这就会导致泛化性能下降，这种现象称为过拟合（overfitting）。

与之相对的是欠拟合（underfitting），即模型在训练集上的表现就很差，这种情况下模型的泛化能力也会很差。

有多种因素可能导致过拟合，其中最常见的情况是由于学习能力过于强大，以至于把训练样本所包含的不太一般的特性都学到了；而欠拟合则通常是由于学习能力低下而造成的。

欠拟合比较容易克服，例如在决策树学习中扩展分支、在神经网络学习中增加训练轮数等。而过拟合则很麻烦，实际上过拟合是机器学习面临的关键障碍，是无法彻底避免的，我们所能做的只是缓解，或者说减小其风险。

评估方法

通常，我们可通过实验测试来对学习器的泛化误差进行评估并进而做出选择。为此需使用一个测试集（testing set）来测试学习器对新样本的判别能力，然后以测试集上的「测试误差」（testing error）作为泛化误差的近似。

通常我们假设测试样本也是从样本真实分布中独立同分布采样而得。但需注意的是，测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现、未在训练过程中使用过。

我们只有一个包含 $m$ 个样例的数据集 $D = \left\lbrace (\bm{x}_1, y_1),\, (\bm{x}_2, y_2),\, \cdots,\, (\bm{x}_m, y_m) \right\rbrace$，既要训练，又要测试，就需要对 $D$ 进行适当的处理，从中产生训练集 $S$ 和测试集 $T$。下面是几种常见的做法。

留出法

留出法（hold-out）直接将数据集 $D$ 划分为两个互斥的集合，其中一个集合作为训练集 $S$，另一个作为测试集 $T$。即 $D = S \cup T,\, S \cap T = \empty$。在 $S$ 上训练出模型后，用 $T$ 来评估其测试误差，作为对泛化误差的估计。

训练/测试集的划分要尽可能保持数据分布的一致性，例如在分类问题中，每个类别的样本在训练集和测试集中的比例应该大致相同。从采样（sampling）的角度看待数据集的划分过程，保留类别比例的采样法时通常称为分层采样（stratified sampling）。

即使给定训练/测试集的样本比例，仍然存在多种划分方式对初始数据集 $D$ 进行分割。单次使用留出法得到的估计结果往往不够稳定可靠，通常要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。

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

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

交叉验证法

交叉验证法（cross validation）先将数据集 $D$ 划分为 $k$ 个大小相似的互斥子集，即 $D = D_1 \cup D_2 \cup \cdots \cup D_k, D_i \cap D_j = \empty$。每个子集 $D_i$ 都尽可能保持数据分布的一致性，即采用分层采样。然后每次用 $k - 1$ 个子集的并集作为训练集，余下的那个子集作为测试集，这样就可以得到 $k$ 组训练/测试集，从而可进行 $k$ 次训练和测试，最终返回的是这 $k$ 个测试结果的均值。

显然，交叉验证法评估结果的稳定性和保真性在很大程度上取决于 $k$ 的取值，因此通常将交叉验证法称为 $k$ 折交叉验证（$k$-fold cross validation）。通常 $k = 10$，此时成为 10 折交叉验证。

与留出法类似，划分为 $k$ 个子集同样存在多种划分方式。为减小因样本划分不同而引入的差别，$k$ 折交叉验证通常要随机使用不同的划分 $p$ 次，最终评估结果是这 $p$ 次 $k$ 折交叉验证结果的均值。常使用的有「10 次 10 折交叉验证」，这与「100 次留出法」都是进行了 100 次训练/测试。

令 $k$ 为数据集 $D$ 中包含的样本数量，就得到了交叉验证发的一个特例——留一法（leave-one-out, LOO）。显然留一法不受随机样本划分方式的影响。但留一法的重要缺陷就是，当数据集比较大时，训练大量模型的计算开销可能是难以忍受的。

自助法

我们希望评估的是用 $D$ 训练出的模型，但在前两个方法中，都保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比 $D$ 小，这必然会引入一些因训练样本规模不同而导致的估计偏差。

自助法（bootstrapping）是一种通过自助采样技术来评估学习器泛化误差的方法。给定包含 $m$ 个样本的数据集 $D$，我们对它进行 $m$ 次有放回的随机采样，得到了 $m$ 个样本的自助采样集 $D'$。显然，由于是有放回采样，$D'$ 中有的样本可能重复出现，而有的样本则根本不出现。

可以进行一个简单的估计，样本在 $m$ 次采样中始终不被采到的概率是 $\left(1 - \dfrac{1}{m}\right)^m$，取极限得到 $\lim\limits_{m \to \infty} \left(1 - \dfrac{1}{m}\right)^m = \dfrac{1}{\e} \approx 0.368$，即约有 $36.8\%$ 的样本不会出现在自助采样集中。

于是我们可将 $D'$ 用作训练集，$D\backslash D'$ 用作测试集。这样实际评估的模型与期望评估的模型都使用 $m$ 个训练样本，而我们仍有数据总量约 $\dfrac{1}{3}$ 的、没在训练集中出现的样本用于测试。这样的测试结果，亦称为包外估计（out-of-bag estimate）。

自助法在数据集较小、难以有效划分训练/测试集时很有用。但由于自助法产生的数据集改变了初始数据集的分布，这会引出估计偏差，因此在数据集足够大时，留出法和交叉验证法更常用。

调参与最终模型

大多数学习算法都有些参数（parameter）需要设定，参数配置不同，学得模型的性能往往有显著差别。因此，在进行模型评估与选择时，除了要对适用学习算法进行选择，还需对算法参数进行设定，这就是通常所说的参数调节或简称调参（parameter tuning）。

调参似乎与算法选择并没什么本质区别：对每种参数配置训练出模型，然后把对应最好的模型的参数作为结果。但实际上，调参与算法选择是有区别的。

学习算法的很多参数都是在实数范围内取值，因此对每种参数的配置都训练出模型是不可行的。现实中常用的做法是对每个参数选定一个范围和变化步长，例如在 $[0, 0.2]$ 范围内以 $0.05$ 为步长，则实际需要评估的候选参数只要 $5$ 个，最终是从这 $5$ 个候选值中产生选定值。这是在计算开销与性能估计之间进行折中的结果。

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

通常将学得模型在实际使用中遇到的数据称为测试数据，为了加以区分，模型评估与选择中用于评估测试的数据集常称为验证集（validation set）。

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

性能度量

对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量 （performance measure）。

在预测任务中，给定样例集 $D = \left\lbrace (\bm{x}_1, y_1), (\bm{x}_2, y_2), \ldots, (\bm{x}_m, y_m) \right\rbrace$，其中 $y_i$ 是示例 $\bm{x}_i$ 的真实标记。要评估学习器 $f$ 的性能，就是要把学习器预测结果 $f(\bm{x})$ 与真实标记 $y$ 进行比较。

回归任务最常用的性能度量是均方误差（mean squared error）：

$$\boxed{E(f; D) = \dfrac{1}{m} \sum_{i=1}^{m} \left(f(\bm{x}_i) - y_i\right)^2}$$

更一般的，对于数据分布 $\mathcal{D}$ 和概率密度函数 $p$，均方误差可描述为

$$E(f; \mathcal{D}) = \int_{\bm{x} \sim \mathcal{D}} \left(f(\bm{x}) - y\right)^2 p(\bm{x}) \d \bm{x}$$

错误率与精度

错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本数占样本总数的比例。

对样例集 $D$，分类错误率定义为

$$\boxed{E(f; D) = \dfrac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f(\bm{x}_i) \ne y_i\right)}$$

精度则定义为

$$\boxed{ \begin{aligned} \operatorname{acc}(f; D) &= \dfrac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f(\bm{x}_i) = y_i\right) \\ &= 1 - E(f; D) \end{aligned}}$$

更一般的，对于数据分布 $\mathcal{D}$ 和概率密度函数 $p$，错误率和精度可描述为

$$\begin{aligned} E(f; \mathcal{D}) &= \int_{\bm{x} \sim \mathcal{D}} \mathbb{I}\left(f(\bm{x}) \ne y\right) p(\bm{x}) \d \bm{x} \\ \operatorname{acc}(f; \mathcal{D}) &= 1 - E(f; \mathcal{D}) \end{aligned}$$

查准率、查全率与 $F_1$

以西瓜问题为例，错误率衡量的是「有多少比例的瓜被判别错误」。但如果我们关心的是「挑出的西瓜中有多少比例是好瓜」或「所有好瓜中有多少比例被挑了出来」，就需要其他的性能度量。

类似的需求在信息检索、Web 搜索等应用中经常出现。例如在信息检索中，我们经常会关心「检索出的信息中有多少比例是用户感兴趣的」「用户感兴趣的信息中有多少被检索出来了」。查准率（precision, 准确率）与查全率（recall, 召回率）是更为适用于此类需求的性能度量。

对于二分类问题，可将样例根据其真实类别与学习器预测类别的组合划分为真正例（true positive）、假正例（false positive）、真反例（true negative）、假反例 false negative）四种情形。分别令为 $TP, FP, TN, FN$，分类结果的混淆矩阵（confusion matrix）如下：

真实情况	预测正例	预测反例
正例	$TP$（真正例）	$FN$（假反例）
反例	$FP$（假正例）	$TN$（真反例）

则查准率 $P$ 与查全率 $R$ 分别定义为：

$$\left\lbrace\begin{aligned} P &= \dfrac{TP}{TP + FP} \\ R &= \dfrac{TP}{TP + FN} \end{aligned}\right.$$

查准率和查全率是一对矛盾的度量。一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低。

例如，若希望将好瓜尽可能多地选出来，则可通过增加选瓜的数量来实现，如果将所有西瓜都选上，那么所有的好瓜也必然都被选上了，但这样查准率就会较低；若希望选出的瓜中好瓜比例尽可能高，则可只挑选最有把握的瓜，但这样就难免会漏掉不少好瓜，使得查全率较低。

通常只有在一些简单任务中，才可能使查全率和查准率都很高。

在很多情形下，我们可根据学习器的预测结果对样例进行排序，排在前面的是学习器认为「最可能」是正例的样本，排在最后的则是学习器认为「最不可能」是正例的样本。按此顺序逐个把样本作为正例进行预测，则每次可以计算出当前的查全率、查准率。以查准率为纵轴、查全率为横轴作图，就得到了「查准率-查全率曲线」，简称 P-R 曲线，显示该曲线的图称为 P-R 图。

在上图中，显然有学习器 A 的性能优于学习器 C（因为 C 被 A 完全「包住」）。但是对于 A 与 B 则难以进行断言，一般只能在具体的查准率或查全率条件下进行比较。

但很多情况下仍然希望将二者分个胜负，一个合理的判据就是比较其 P-R 曲线下面积的大小。但这个不太容易估算。

平衡点（break-even point, BEP）是 P-R 曲线上查准率等于查全率的点，是一个综合考虑查准率和查全率的性能度量。基于 BEP 比较，可认为 A 优于 B。

BEP 仍然过于简化了，更常用的是 $F_1$ 度量。

$F_1$ 是基于查准率与查全率的调和平均（harmonic mean）定义的：

$$\dfrac{1}{F_1} = \dfrac{1}{2} \left( \dfrac{1}{P} + \dfrac{1}{R} \right)$$

即

$$\begin{aligned} F_1 &= \dfrac{2 \times P \times R}{P + R} \\ &= \dfrac{2 \times TP}{\text{样例总数} + TP - TN} \end{aligned}$$

$F_{\beta}$ 是加权调和平均：

$$F_{\beta} = \dfrac{1}{1 + \beta^2} \left( \dfrac{1}{P} + \dfrac{\beta^2}{R} \right)$$

即

$$F_{\beta} = \dfrac{(1 + \beta^2) \times P \times R}{(\beta^2 \times P) + R}$$

其中 $\beta > 0$ 度量了查全率对查准率的相对重要性。当 $\beta = 1$ 时，$F_{\beta}$ 退化为标准 $F_1$；$\beta > 1$ 时查全率有更大影响；$\beta < 1$ 时查准率有更大影响。

与算术平均 $\dfrac{P + R}{2}$ 与几何平均 $\sqrt{P \times R}$ 相比，调和平均更重视较小值。

很多时候我们有多个二分类混淆矩阵，例如进行多次训练/测试，每次都能得到一个混淆矩阵，抑或是在多个数据集上进行训练/测试，希望估计算法的全局性能等。总之我们希望在 $n$ 个二分类混淆矩阵上综合考察查准率和查全率。

一种直接的做法是先在各混淆矩阵上分别计算出查准率和查全率，记为 $(P_1, R_1),\, (P_2, R_2),\, \cdots,\, (P_n, R_n)$，再计算平均值，就得到了宏查全率（macro-$P$）、宏查准率（macro-$R$）和相应的宏 $F_1$（macro-$F_1$）：

$$\left\lbrace\begin{aligned} \text{macro-}P &= \dfrac{1}{n} \sum_{i=1}^{n} P_i \\ \text{macro-}R &= \dfrac{1}{n} \sum_{i=1}^{n} R_i \\ \text{macro-}F_1 &= \dfrac{2 \times \text{macro-}P \times \text{macro-}R}{\text{macro-}P + \text{macro-}R} \end{aligned}\right.$$

另一种做法是先将各混淆矩阵的对应元素进行平均，得到 $TP, FP, TN, FN$ 的平均值，记为 $\overline{TP}, \overline{FP}, \overline{TN}, \overline{FN}$，再计算查准率和查全率，就得到了微查全率（micro-$P$）、微查准率（micro-$R$）和相应的微 $F_1$（micro-$F_1$）：

$$\left\lbrace\begin{aligned} \text{micro-}P &= \dfrac{\overline{TP}}{\overline{TP} + \overline{FP}} \\ \text{micro-}R &= \dfrac{\overline{TP}}{\overline{TP} + \overline{FN}} \\ \text{micro-}F_1 &= \dfrac{2 \times \text{micro-}P \times \text{micro-}R}{\text{micro-}P + \text{micro-}R} \end{aligned}\right.$$

ROC 与 AUC

很多学习器是为测试样本产生一个实值或概率预测，然后将这个预测值与一个分类阈值（threshold）进行比较，若大于阈值则分为正类，否则反类。这样分类过程就相当于在这个排序中以某个「截断点」（cut point）将样本分为两部分，前一部分判作正例，后一部分判作反例。

在不同的应用任务中，我们可根据任务需求来采用不同的截断点，例如若我们更重视「查准率」，则可选择排序中靠前的位置进行截断；若更重视「查全率」，则可选择靠后的位置进行截断。

因此排序本身的质量好坏，体现了综合考虑学习器在不同任务下的「期望泛化性能」的好坏，或者说，「一般情况下 」泛化性能的好坏。ROC 曲线则是从这个角度出发来研究学习器泛化性能的有力工具。

ROC 全称是受试者工作特征（receiver operating characteristic）曲线。与 P-R 曲线类似，我们根据学习器的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测，每次计算出两个重要量的值，分别以它们为横纵坐标作图，就得到了 ROC 曲线。

ROC 曲线的横轴是假正例率（false positive rate, FPR），纵轴是真正例率（true positive rate, TPR），分别定义为

$$\left\lbrace\begin{aligned} \text{FPR} &= \dfrac{FP}{FP + TN} \\ \text{TPR} &= \dfrac{TP}{TP + FN} \end{aligned}\right.$$

剩下内容似乎重要性不足？后面再补吧。

哼哧哼哧开补了。补完记得删。

进行学习器的比较时，与 P-R 图类似，若一个学习器的 ROC 曲线被另一个学习器的曲线完全包住，可断言后者的性能优于前者。

若两个学习器的 ROC 曲线发生交叉，难以一般性断言两者孰优孰劣，若一定要进行比较，一个合理的判据是比较 ROC 曲线下的面积，即AUC（Area Under ROC Curve）。

假定 ROC 曲线是由坐标为 $\left\lbrace (x_1, y_1), (x_2, y_2), \cdots, (x_m, y_m) \right\rbrace$ 的点按序连接而成（$x_1 = 0, x_m = 1$），AUC 可估算为

$$\text{AUC} = \dfrac{1}{2} \sum_{i=1}^{m-1} (x_{i+1} - x_i) \cdot (y_i + y_{i+1})$$

形式化地看，AUC 考虑的是样本预测的排序质量，与排序误差有紧密联系。

给定 $m^{+}$ 个正例和 $m^{-}$ 个反例，令 $D^{+}$ 和 $D^-$ 分别表示正、反例集合，则排序损失（loss）定义为

$$\ell_{\text{rank}} = \dfrac{1}{m^{+}m^{-}} \sum_{\bm{x}^{+} \in D^{+}} \sum_{\bm{x}^{-} \in D^{-}} \left( \mathbb{I}\left(f(\bm{x}^{+}) < f(\bm{x}^{-})\right) + \dfrac{1}{2} \mathbb{I}\left(f(\bm{x}^{+}) = f(\bm{x}^{-})\right) \right)$$

上式的含义是：考虑每一对正、反例，若正例的预测值小于反例，则记一个「罚分」；若相等，则记半个「罚分」。显然 $\ell_{\text{rank}}$ 对应的是 ROC 曲线之上的面积：若一个正例在 ROC 曲线上对应标记点的坐标为 $(x, y)$，则 $x$ 恰是排序在其之前的反例所占的比例，即假正例率，因此有

$$\text{AUC} = 1 - \ell_{\text{rank}}$$

代价敏感错误率与代价曲线

在很多应用中，不同的错误分类所造成的损失是不同的。例如在医学诊断中，将一个健康人诊断为患病（假正例）与将一个患病的人诊断为健康（假反例）所造成的后果是不同的。为权衡不同类型错误所造成的不同损失，可为错误赋予非均等代价（unequal cost）。

以二分类任务为例，可根据任务的领域知识设定一个代价矩阵（cost matrix），如下表所示，其中 $\text{cost}_{ij}$ 表示将第 $i$ 类样本预测为第 $j$ 类样本的代价。一般来说，$\text{cost}_{ii} = 0$，即正确分类的代价为零。

真实类别	预测类别（第 $0$ 类）	预测类别（第 $1$ 类）
第 $0$ 类	$0$	$\text{cost}_{01}$
第 $1$ 类	$\text{cost}_{10}$	$0$

若将第 $0$ 类判别为第 $1$ 类所造成的损失更大，则 $\text{cost}_{01} > \text{cost}_{10}$。损失程度相差越大，$\text{cost}_{01}$ 与 $\text{cost}_{10}$ 的差别越大。

前面介绍的一些性能度量大都隐式地假设了均等代价。例如上面对「错误率」的定义 $E(f; D) = \dfrac{1}{m} \displaystyle \sum_{i=1}^{m} \left(f(\bm{x}_i) - y_i\right)^2$，直接计算了错误次数，并没有考虑不同错误会造成不同后果。

在非均等代价下，我们所希望的不再是最小化错误次数，而是希望最小化总体代价（total cost）。

若将上表中第 $0$ 类作为正类、第 $1$ 类作为反类，令 $D^{+}, D^{-}$ 分别代表样例集 $D$ 的正例子集和反例子集，则代价敏感（cost-sensitive）错误率定义为

$$E(f; D; \text{cost}) = \dfrac{1}{m} \left( \sum_{\bm{x}_i \in D^{+}} \mathbb{I}\left(f(\bm{x}_i) \ne y_i\right) \times \text{cost}_{01} + \sum_{\bm{x}_i \in D^{-}} \mathbb{I}\left(f(\bm{x}_i) \ne y_i\right) \times \text{cost}_{10} \right)$$

类似地可以给出基于分布定义的「代价敏感错误率」，以及其他一些性能度量如「精度的代价敏感版本」。

若令 $\text{cost}_{ij}$ 中的 $i, j$ 取值不限于 $0, 1$，则可定义出多分类任务的代价敏感性能度量。

在非均等代价下，ROC 曲线不能直接反映出学习器的期望总体代价，而代价曲线（cost curve）则可达到该目的。

代价曲线图的横轴是取值为 $[0, 1]$ 的正例概率代价

$$P(+)\text{cost} = \dfrac{p \times \text{cost}_{01}}{p \times \text{cost}_{01} + (1 - p) \times \text{cost}_{10}}$$

其中 $p$ 是样例为正例的概率；纵轴是取值为 $[0, 1]$ 的归一化代价^[1]

$$\text{cost}_{\text{norm}} = \dfrac{\text{FNR} \times p \times \text{cost}_{01} + \text{FPR} \times (1 - p) \times \text{cost}_{10}}{p \times \text{cost}_{01} + (1 - p) \times \text{cost}_{10}}$$

其中 $\text{FPR}$ 是上面定义的「假正例率」；$\text{FNR}$ 是「假反例率」，定义为 $1 - \text{TPR}$。

ROC 曲线上每一点对应了代价平面上的一条线段，设 ROC 曲线上点的坐标为 $(\text{TPR}, \text{FPR})$，则可相应计算出 $\text{FNR}$，然后在代价平面上绘制一条从 $(0, \text{FPR})$ 到 $(1, \text{FNR})$ 的线段，线段下的面积即表示了该条件下的期望总体代价。

如此将 ROC 曲线上的每个点转化为代价平面上的一条线段，然后取所有线段的下界，圈成的面积即为在所有条件下学习器的期望总体代价，如下图所示：

比较检验

偏差与方差

---

1. 规范化（normalization）是将不同变化范围的值映射到相同的固定范围中，常见的是 $[0, 1]$，此时亦称为归一化。 ↩︎