待领略了多种机器学习/深度学习模型后再回过头来看本章，会有新感悟。

1 误差与过拟合

通常将学习器对样本的实际预测结果与样本的真实值之间的差异称为误差（Error）。定义：

• 在训练集上的误差称为训练误差（Training Error）或经验误差（Empirical Error）
• 在测试集上的误差称为测试误差（Test Error）
• 学习器在所有新样本上的误差称为泛化误差（Generalization Error）

显然所有人都希望得到在新样本上表现得很好的学习器，即泛化误差小的学习器。因此应让学习器尽可能地从训练集中学出普适性的“一般特征”，这样在遇到新样本时才能做出正确的判别。然而，存在学习器把训练集学得“太好”的时候，即把一些训练样本的自身特点当做了普遍特征；同时也有学习能力不足的情况，即训练集的基本特征都没有学习出来。定义：

• 学习能力过强，以至于把训练样本所包含的不太一般的特性都学到了：过拟合（Overfitting）
• 学习能力太差，训练样本的一般性质尚未学好：欠拟合（Underfitting）

可以得知：在过拟合问题中，训练误差十分小，但测试误差教大；在欠拟合问题中，训练误差和测试误差都比较大。目前，欠拟合问题比较容易克服，例如通过增加迭代次数等，但过拟合问题还没有十分好的解决方案，是机器学习面临的关键障碍。

---

2 评估方法

在现实任务中往往有多种算法可供选择，那么应选择哪一个算法才是最适合的呢？如上所述，通常希望得到的是泛化误差小的学习器，理想的解决方案是对模型的泛化误差进行评估，然后选择泛化误差最小的学习器。但是，泛化误差指的是模型在所有新样本上的适用能力，无法直接获得。

因此，通常采用一个测试集来测试学习器对新样本的判别能力，然后以测试集上的测试误差作为泛化误差的近似。显然选取的测试集应尽可能与训练集互斥，以下通过一个考试例来解释：

【考试例】假设Hyplus出了10道习题供HyUser们练习，考试时Hyplus又用同样的这10道题作为试题，可能有的HyUser只会做这10道题却能得高分，很明显，这个考试成绩并不能有效地反映出真实水平。回到之前问题，希望得到泛化性能好的模型就好比希望HyUser们Hy课学得好并获得了对所学知识"举一反三"的能力；训练样本相当于给HyUser们练习的习题，测试过程则相当于考试。显然，若测试样本被用作训练了，则得到的将是过于"乐观"的估计结果。

---

3 数据集的划分方法

如前所述，通常用一个测试集的测试误差来作为泛化误差的近似，因此需要对初始数据集进行有效划分，划分出互斥的训练集和测试集。以下为几种常见的划分方法：

3.1 留出法

留出法（Hide-out）将数据集D划分为两个互斥的集合，一个作为训练集S，另一个作为测试集T，满足D=S\cap T且S\cap T=\empty，常见的划分为：约\dfrac23~\dfrac45的样本用作训练，剩下的用作测试。

需要注意的是：训练/测试集的划分要尽可能保持数据分布的一致性，以避免由于分布的差异引入额外的偏差，常见的做法是采取分层抽样（Stratifed Sampling）。同时，由于划分的随机性，单次的留出法结果往往不够稳定，一般要采用若干次随机划分，重复实验取平均值的做法。

3.2 交叉验证法

交叉验证法（Cross Validation）将数据集D划分为k个大小相同的互斥子集，满足D=D_1\cup D_2\cup \cdots \cup D_k,\ D_i\cap D_j=\empty\ (i≠j)，同样地尽可能保持数据分布的一致性，即采用分层抽样的方法获得这些子集。交叉验证法的思想为：每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集，这样就有k种训练集/测试集划分的情况，从而可进行k次训练和测试，最终返回k次测试结果的均值。故交叉验证法又称为k折交叉验证，其中k最常用的取值是10，下图给出了10折交叉验证的示意图。

与留出法类似，将数据集D划分为k个子集的过程具有随机性，因此k折交叉验证通常也要重复p次，称为p次k折交叉验证，常见的是10次10折交叉验证，即进行了100次训练/测试。特别地，当划分的k个子集的每个子集中只有一个样本时，称为留一法（Leave-One-Out，LOO），显然，留一法的评估结果比较准确，但对计算机的资源消耗也是巨大的。

3.3 自助法

通常希望评估的是用整个数据集D训练出的模型，但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比D小，这必然会引入一些因训练样本规模不同而导致的估计偏差，留一法受训练样本规模变化的影响较小，但计算复杂度又太高了。

自助法（Bootstrapping）正是解决了这样的问题，常用的自助采样（Bootstrap Sampling）的基本思想为：给定包含m个样本的数据集D，每次随机从D中挑选一个样本，将其拷贝放入D'，然后再将该样本放回初始数据集D中，使得该样本在下次采样时仍有可能被采到。重复执行m次，就可以得到了包含m个样本的数据集D'。可以得知在m次采样中，样本始终不被采到的概率取极限为：

\begin{aligned}
\lim\limits_{m\longmapsto \infty}\left (1-\frac1m \right )^m \longmapsto \frac {1}{\text{e}}\approx 0.368
\end{aligned}

这样，通过自助采样，初始样本集D中大约有36.8%的样本没有出现在D'中，于是可以将D'作为训练集，D-D'作为测试集。自助法在数据集较小，难以有效划分训练集/测试集时很有用，但由于自助法产生的数据集（随机抽样）改变了初始数据集的分布，因此引入了估计偏差。在初始数据集足够时，留出法和交叉验证法更加常用。

---

4 调参

大多数学习算法都有参数（Parameter）需要设定，参数配置不同，学得模型的性能往往有显著差别，这就是通常所说的参数调节（Parameter Tuning，调参）。

学习算法的很多参数都是在实数范围内取值，因此，对每种参数取值都训练出模型是不可行的。常见的做法为：对每个参数选定一个范围和步长λ，使得学习的过程变得可行。例如，假定算法有3个参数，每个参数仅考虑5个候选值，这样对每一组训练/测试集就有5\times5\times5= 125个模型需考察，由此可见：拿下一个参数（即经验值）对算法人员来说是相当来之不易的。

通常把学得模型在实际使用中遇到的数据称为测试数据，为了加以区分，模型评估与选择中用于评估测试的数据集常称为验证集（Validation Set）。例如，在研究对比不同算法的泛化性能时，用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集和验证集，基于验证集上的性能来进行模型选择和调参.

需要注意的是：当最后选定好模型和调参完成后，需要使用初始的数据集D重新训练模型，即让最初划分出来用于评估的测试集也被模型学习，增强模型的学习效果。用前述的考试例来比喻，就像每次考试完，要将考卷的题目消化掉（大多数题目都还是之前没有见过的）。

---

5 性能度量

相关阅读：时序预测评价指标简介

性能度量（Performance Measure）是衡量模型泛化能力的评价标准，在对比不同模型的能力时，使用不同的性能度量往往会导致不同的评判结果。本节除第1子节外，其他主要为分类模型的性能度量。

5.1 均方误差、错误率与精度

在回归任务中，即预测连续值时，最常用的性能度量是均方误差（Mean Squared Error），很多的经典算法都采用MSE作为评价函数，定义为

\begin{aligned}
E(f;D) &=\frac{1}{m}\sum\limits_{i=1}^m (f(\mathbf{x}_i)-y_i)^2
\end{aligned}

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

\begin{aligned}
E(f;\mathcal{D}) &=\int_{\mathbf{x}\sim \mathcal{D}} (f(\mathbf{x})-y)^2p(\mathbf{x})\text{d}\mathbf{x}
\end{aligned}

在分类任务中，即预测离散值的问题，最常用的是错误率（Error Rate）和精度（Accuracy）。错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本数占样本总数的比例，易知：错误率 + 精度 = 1。错误率和精度分别定义为

\begin{aligned}
E(f;D) &=\frac{1}{m}\sum\limits_{i=1}^m \mathbb{I} (f(\mathbf{x}_i)\ne y_i)
\end{aligned}

\begin{aligned}
\text{acc}(f;D) &=\frac{1}{m}\sum\limits_{i=1}^m  \mathbb{I}(f(\mathbf{x}_i)=y_i) \\
 &=1-E(f;D)
\end{aligned}

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

\begin{aligned}
E(f;\mathcal{D}) &=\int_{\mathbf{x}\sim \mathcal{D}} \mathbb{I} (f(\mathbf{x})\ne y)p(\mathbf{x})\text{d}\mathbf{x}
\end{aligned}

\begin{aligned}
\text{acc}(f;\mathcal{D}) &=\int_{\mathbf{x}\sim \mathcal{D}}  \mathbb{I}(f(\mathbf{x})=y)p(\mathbf{x})\text{d}\mathbf{x} \\
 &=1-E(f;\mathcal{D})
\end{aligned}

5.2 查准率、查全率、F1

错误率和精度虽然常用，但不能满足所有的需求，例如，在推荐系统中通常只关心推送给用户的内容用户是否感兴趣——查准率（Precision），或者说所有用户感兴趣的内容推送了多少——查全率（Recall）。因此，使用查准/查全率更适合描述这类问题。对于二分类问题，对于二分类问题，可将样例根据其真实类别与学习器预测类别的组合划分为真正例（True Positive）、假正例（False Positive）、真反例（True Negative）、假反例（False Negative）四种情形，令TP,FP,TN,FN分别表示其对应的样例数，样例总数为N，则显然有TP+FP+TN+FN=N。二元分类的混淆矩阵（Confusion Matrix）定义如下：

样本总数N		预测值
		Positive	Negative
真实值	Positive	真正例（True Positive）：实际为Positive、预测成Positive的样本数TP	假反例（False Negative）：实际为Positive、预测成Negative的样本数FN
	Negative	假正例（False Positive）：实际为Negative、预测成Positive的样本数FP	真反例（True Negative）：实际为Negative、预测成Negative的样本数TN

实际Positive样本数=TP+FN，实际Negative样本数=FP+TN

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

\begin{aligned}
P &=\frac{TP}{TP+FP}\\
R &=\frac{TP}{TP+FN}
\end{aligned}

正如天下没有免费的午餐，查准率和查全率是一对矛盾的度量。例如，若想让推送的内容尽可能用户全都感兴趣，那只能推送把握高的内容，这样就漏掉了一些用户感兴趣的内容，查全率就低了；若想让用户感兴趣的内容都被推送，那只有将所有内容都推送上，宁可多，不可漏，这样查准率就很低了。

P-R曲线正是描述查准/查全率变化的曲线，定义如下：根据学习器的预测结果（一般为一个实值或概率）对测试样本进行排序，将最可能是“正例”的样本排在前面，最不可能是“正例”的排在后面，按此顺序逐个把样本作为“正例”进行预测，每次计算出当前的P值和R值。一幅P-R图如下所示：

P-R曲线的评估方式：若一个学习器A的P-R曲线被另一个学习器B的P-R曲线完全包住，则称B的性能优于A；若A与B的曲线发生了交叉，则谁在曲线下的面积大，谁的性能更优。但一般来讲，曲线下的面积是很难进行估算的，故衍生出了平衡点（Break-Event Point，BEP）这一度量，即当P=R时的取值，平衡点的取值越高，性能更优。

查准率-查全率指标有时会出现矛盾的情况，此时就需要综合考虑它们，最常见的方法为F-Measure（又称F-Score），定义为查准率P与查全率R的加权调和平均（Weighted Harmonic Mean），即

\begin{aligned}
\frac{1}{F_\beta} &=\frac1{1+\beta^2}\left (\frac1P+\frac{\beta^2}{R}\right )\\
F_\beta &=\frac{(1+\beta^2)\times P \times R}{(\beta^2\times P)+R}
\end{aligned}

特别地，当\beta=1时，即为常见的F1度量，是P和R的调和平均（Harmonic Mean）。和算术平均\dfrac{P+R}{2}与几何平均\sqrt{P\times R}相比，调和平均更重视较小值。当F1较高时，模型的性能越好。定义式如下：

\begin{aligned}
\frac{1}{F_1} &=\frac1{2}\left (\frac1P+\frac{1}{R}\right )\\
F_1 &=\frac{2\times P \times R}{P+R}\\
 &=\frac{2\times TP}{N+TP-TN}
\end{aligned}

有时会有多个二分类混淆矩阵，例如多次训练或在多个数据集上训练，那么估算全局性能的方法就有两种，分为宏观和微观。一般情况下，宏观即为先分别算出每个混淆矩阵的查准率和查全率，记为(P_1,R_2),(P_2,R_2),\dots,(P_n,R_n)，再计算平均值，得到宏查准率\text{macro-}P、宏查全率\text{macro-}R以及相应的宏F1\text{macro-}F_1：

\begin{aligned}
\text{macro-}P &=\frac1n\sum\limits_{i=1}^n P_i\\
\text{macro-}R &=\frac1n\sum\limits_{i=1}^n R_i\\
\text{macro-}F_1 &=\frac{2\times \text{macro-}P \times \text{macro-}R}{\text{macro-}P+\text{macro-}R}
\end{aligned}

微观则是先计算出混淆矩阵的各项平均值\overline{TP},\overline{FP},\overline{TN},\overline{FN}，再基于这些平均值计算出微查准率\text{micro-}P、微查全率\text{micro-}R和微F1\text{micro-}F_1：

\begin{aligned}
\text{micro-}P &=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}\\
\text{micro-}R &=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}\\
\text{micro-}F_1 &=\frac{2\times \text{micro-}P \times \text{micro-}R}{\text{micro-}P+\text{micro-}R}
\end{aligned}

5.3 ROC与AUC

如前所述，学习器对测试样本的评估结果一般为一个实值或概率。设定一个分类阈值（Threshold），大于阈值为正例，小于阈值为负例，因此该实值的好坏直接决定了学习器的泛化性能，若将这些实值排序，则排序的好坏决定了学习器的性能高低。ROC（Receiver Operating Characteristic，“受试者工作特征”）曲线正是从这个角度出发来研究学习器的泛化性能。ROC曲线与P-R曲线十分类似，都是按照排序的顺序逐一按照正例预测，不同的是ROC曲线以真正例率（True Positive Rate，TPR）为横轴，以假正例率（False Positive Rate，FPR）为纵轴，更偏重研究基于测试样本评估值的排序好坏。真正例率\text{TPR}与假正例率\text{FPR}分别定义为

\begin{aligned}
\text{TPR} &=\frac{TP}{TP+FN}\\
\text{FPR} &=\frac{FP}{TN+FP}
\end{aligned}

一幅ROC图如下图中(a)所示，简单分析图像，可以得知：当FN=0时，TN也必为0，反之也成立。可以画一个队列，试着使用不同的截断点（即阈值）去分割队列，来分析曲线的形状，(0,0)表示将所有的样本预测为负例，(1,1)则表示将所有的样本预测为正例，(0,1)表示正例全部出现在负例之前的理想情况，(1,0)则表示负例全部出现在正例之前的最差情况。限于篇幅，此处不再论述。

现实中的任务通常都是有限个测试样本，因此只能绘制出近似ROC曲线。一般的绘制方法为，首先根据测试样本的评估值对测试样本排序，之后按照以下规则进行绘制（结果如上图中(b)所示）：给定m^+个正例和m^-个反例，根据学习器预测结果对样例进行排序，然后把分类阈值设为最大，即把所有样例均预测为反例，此时真正例率和假正例率均为0，在坐标(0,0)处标记一个点；然后，将分类阈值依次设为每个样例的预测值，即依次将每个样例划分为正例，设前一个标记点坐标为(x,y)，当前若为真正例，则对应标记点的坐标为(x,y+\dfrac{1}{m^+})；当前若为假正例，则对应标记点的坐标为(x+\dfrac{1}{m^-},y)，然后用线段连接相邻点即得。

同样地，进行模型的性能比较时，若一个学习器A的ROC曲线被另一个学习器B的ROC曲线完全包住，则称B的性能优于A；若A和B的曲线发生了交叉，则谁的曲线下的面积大，谁的性能更优。ROC曲线下的面积定义为AUC（Area Under ROC Curve），与P-R图不同，AUC是可估算的，即AOC曲线下每一个小矩形的面积之和。易知：AUC越大，证明排序的质量越好；\text{AUC}=1时，证明所有正例排在了负例的前面；\text{AUC}=0时，所有的负例排在了正例的前面。计算式如下：

\begin{aligned}
\text{AUC}=\frac{1}{2}\sum\limits_{i=1}^{m-1}(x_{i+1}-x_i)(y_i+y_{i+1})
\end{aligned}

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

上述方法中将学习器的犯错同等对待，但在现实生活中，将正例预测成假例与将假例预测成正例的代价常常是不一样的，例如将“无疾病”预测成“有疾病”只是增多了检查，但将“有疾病”预测成“无疾病”却是增加了生命危险。由此引入了代价矩阵（Cost Matrix），以二分类为例，其中cost_{ij}表示将第i类样本预测第j类样本的代价，一般情况下cost_{ii}=0，即：

		预测类别
		第0类	第1类
真实类别	第0类	\text{0}	cost_{01}
	第1类	cost_{10}	\text{0}

在非均等错误代价下，通常希望最小化总体代价（Total Cost）。将上表中的第0类作为正类、第1类作为正反类，令D^+,D^-分别代表样例集D的正例集和反例集，则代价敏感错误率（Cost-Sensitive Error Rate）为

\begin{aligned}
E(f;D;cost)=\frac1m\left (\sum\limits_{x_i\in D^+} \mathbb{I}(f(x_i)\ne y_i)\times cost_{01} + \sum\limits_{x_i\in D^-} \mathbb{I}(f(x_i)\ne y_i)\times cost_{10}\right )
\end{aligned}

同样地，对于ROC曲线，在非均等错误代价下演变成了代价曲线（Cost Curve），设p是样例为正例的概率，则横轴是取值为[0,1]的正例概率代价：

\begin{aligned}
P(+)cost=\frac{p\times cost_{01}}{p\times cost_{01}+(1-p)\times cost_{10}}
\end{aligned}

设\text{FPR}为上一节中定义的假正例率，\text{FNR}=1-\text{TPR}为假反例率，则纵轴是取值为[0,1]的归一化代价〔归一化（规范化，Normalization）将不同变化范围的值映射到相同的固定范围中，常为[0,1]〕：

\begin{aligned}
cost_{\text{norm}}=\frac{\text{FNR}\times p\times cost_{01}+\text{FPR}\times (1-p)\times cost_{10}}{p\times cost_{01} + (1-p)\times cost_{10}}
\end{aligned}

代价曲线的绘制方法：设ROC曲线上一点的坐标为(\text{TPR}, \text{FPR})，则可相应计算出\text{FNR}，然后在代价平面上绘制一条从(0, \text{FPR})到(1,\text{FNR})的线段，线段下的面积即表示了该条件下的期望总体代价；如此将ROC曲线上的每个点转化为代价平面上的一条线段，然后取所有线段的下界，围成的面积即为在所有条件下学习器的期望总体代价。结果如图所示：

---

6 比较检验

在比较学习器泛化性能的过程中，统计假设检验（Hypothesis Test）为学习器性能比较提供了重要依据，即若A在某测试集上的性能优于B，那A学习器比B好的把握有多大。 为方便论述，本篇中均以错误率作为性能度量的标准，用\varepsilon表示。

假设（Hypothesis）指的是对样本总体的分布或已知分布中某个参数值的一种猜想，例如假设总体服从泊松分布，或假设正态总体的期望\mu=\mu_0，或假设泛化错误率\varepsilon=\varepsilon_0。可以通过测试获得测试错误率\hat \varepsilon，但直观上测试错误率和泛化错误率相差不会太远，因此可以通过测试错误率来推测泛化错误率的分布，这就是一种假设检验。

6.1 二项检验

泛化错误率为\varepsilon的学习器在一个样本上犯错的概率是\varepsilon；测试错误率\hat \varepsilon意味着在m个测试样本上恰有\hat \varepsilon \times m（测试错误数）个被误分类。假定测试样本为从样本总体分布中独立采样而得，那么泛化错误率为\varepsilon的学习器将其中m'个样本误分类、其余样本全部分类正确的概率为\varepsilon^{m'}(1-\varepsilon)^{m-m'}；由此可估算出其恰将\hat \varepsilon \times m个样本误分类的概率如下式所示，这也表达了在包含m个样本的测试集上，泛化错误率为\varepsilon的学习器测得测试错误率为\hat \varepsilon的概率：

\begin{aligned}
P(\hat \varepsilon;\varepsilon)=\binom{m}{\hat \varepsilon \times m} \varepsilon^{\hat \varepsilon\times m}(1-\varepsilon)^{m-\hat \varepsilon \times m}
\end{aligned}

给定测试错误率\hat \varepsilon，则解\dfrac{\partial P(\hat \varepsilon;\varepsilon)}{\partial \varepsilon}=0可知，P(\hat \varepsilon;\varepsilon)在\varepsilon=\hat \varepsilon时最大，|\varepsilon-\hat \varepsilon|增大时P(\hat \varepsilon;\varepsilon)减小，这符合二项分布（Binomial Distribution）。故此处使用二项检验（Binomial Test）：现假设H_0:\varepsilon \le \varepsilon_0,\ H_1:\varepsilon \gt \varepsilon_0，进行右侧检验（单边检验的一种，核心特点是将拒绝域集中在分布的右侧），当H_1为真时，测试错误率\hat \varepsilon往往偏大，故拒绝域的形式为\hat \varepsilon \ge k，其中k为某一正常数，则

\begin{aligned}
P_{\varepsilon \in H_0}\{\hat \varepsilon \ge k\} &=\sum\limits_{i=\left \lceil mk \right \rceil}^{m}\binom{m}{i} \varepsilon^i(1-\varepsilon)^{m-i}\\
 &\le \sum\limits_{i=\left \lceil mk \right \rceil}^{m} \binom{m}{i} \varepsilon_0^i(1-\varepsilon_0)^{m-i}\\
  &\le \alpha
\end{aligned}

其中\alpha称为显著性水平，又称显著度（Significance），1-\alpha称为置信度（Confidence）。一般情况下，\alpha通常取值为0.01、0.05或0.1。通过取等号，可以求出满足条件的k值，即临界点，进一步求出该假设检验的拒绝域，当测试错误率大于该临界点时，假设被拒绝。

6.2 t检验

在很多时候会进行多次重复训练，会得到多个测试错误率。假设有k个测试错误率，则此时可以使用t检验（t-Test），实际上这些测试错误率可视作泛化错误率的k次独立采样，因此可以算出这k个样本的均值\mu（平均测试错误率）与方差\sigma^2：

\begin{aligned}
\mu &=\frac1k\sum\limits_{i=1}^k \hat \varepsilon_i\\
\sigma^2 &=\frac1{k-1}\sum\limits_{i=1}^k(\hat \varepsilon_i-\mu)^2
\end{aligned}

考虑到这k个测试错误率可视为泛化错误率\varepsilon_0的独立采样，根据中心极限定理的经典推论，可得

\begin{aligned}
\tau_{t}=\frac{\mu-\varepsilon_0}{S / \sqrt k}\sim t(k-1)
\end{aligned}

称\tau_{t}服从于自由度为k-1的t分布（t-Distribution）。当k足够大时，t分布近似于\mathcal{N}(0,1)分布。一般情况下，在k>45时，即可使用标准正态分布的上\alpha分位点作为\alpha值。有了这个分布之后，可以类似二项检验进行t假设检验。

t分布的示意图如下所示：

常用双边临界值表如下所示：

\alpha\k	2	5	10	20	30
0.05	12.706	2.776	2.262	2.093	2.045
0.10	6.314	2.132	1.833	1.729	1.699

6.3 交叉验证t检验

前两节介绍的两种方法都是对关于单个学习器泛化性能的假设进行检验，而在现实任务中，更多时候需对不同学习器的性能进行比较。对两个学习器A和B进行k折交叉验证，在相同的第i折训练/测试集上产生的测试错误率分别为\hat \varepsilon^A_1,\hat \varepsilon^A_2,\dots,\hat \varepsilon^A_k和\hat \varepsilon^B_1,\hat \varepsilon^B_2,\dots,\hat \varepsilon^B_k，若想比较A和B的泛化性能，则可使用k折交叉验证成对t检验（Paired t-Test），基本思想为：若两个学习器性能相同，则\hat \varepsilon^A_i=\hat \varepsilon^B_i；对每对结果求差\Delta_i=\hat \varepsilon^A_i-\hat \varepsilon^B_i，则\Delta_1,\Delta_2,\dots,\Delta_k可视为学习器A和B性能差值的独立采样，均值为\mu，方差为\sigma^2；根据这k个差值来对假设“学习器A和B泛化性能（泛化错误率分别为\varepsilon^A,\varepsilon^B）相同”做t检验，则有

\begin{aligned}
\tau_t=\frac{|\mu-(\varepsilon^A-\varepsilon^B)|}{\sigma/\sqrt{k}}\sim t(k-1)
\end{aligned}

现假设H_0:\varepsilon^A=\varepsilon^B,\ H_1:\varepsilon^A\ne\varepsilon^B，进行双边t检验（求拒绝域的方法类似于上一节），给定显著度\alpha，若\tau_t=\dfrac{|\mu|}{\sigma /\sqrt{k}}\le t_{\alpha/2,k-1}，则假设不能被拒绝，即认为两个学习器的性能没有显著差别；否则可认为两个学习器的性能有显著差别，且平均错误率较小的那个学习器性能较优。此处的临界值t_{\alpha/2,k-1}是自由度为k-1的t分布上尾累积分布为\dfrac{\alpha}{2}的临界值。

欲进行有效的假设检验，一个重要前提是测试错误率均为泛化错误率的独立采样。然而，通常情况下由于样本有限，在使用交叉验证等实验估计方法时，不同轮次的训练集会有一定程度的重叠，这就使得测试错误率实际上并不独立，会导致过高估计假设成立的概率。为缓解这一问题，可采用5×2交叉验证（Dietterich, 1998）：做5次2折交叉验证，在每次2折交叉验证之前随机将数据打乱，使得5次交叉验证中的数据划分不重复；对两个学习器A和B，第i次2折交叉验证将产生两对测试错误率，对它们分别求差，得到第1折和第2折上的差值\Delta_i^1,\Delta_i^2；为缓解测试错误率的非独立性，仅计算第1次2折交叉验证的两个结果的平均值\mu=\dfrac12(\Delta_1^1+\Delta_1^2)，但对每次2折实验的结果都计算出其方差\sigma_i^2=(\Delta_i^1-\dfrac{\Delta_i^1+\Delta_i^2}{2})^2+(\Delta_i^2-\dfrac{\Delta_i^1+\Delta_i^2}{2})^2，则有

\begin{aligned}
\tau_t=\frac{\mu}{\sqrt{0.2\sum\limits_{i=1}^5\sigma_i^2}}\sim t(5)
\end{aligned}

其双边检验的临界值t_{\alpha/2,5}当\alpha=0.05时为2.5706，\alpha=0.1时为2.0150。

6.4 McNemar检验

对二分类问题，使用留出法不仅可估计出学习器A和B的测试错误率，还可获得两学习器分类结果的差别，即两者都正确、都错误、一个正确另一个错误的样本数，如以下的列联表（Contingency Table）所示：

		算法A
		正确	错误
算法B	正确	e_{00}	e_{01}
	错误	e_{10}	e_{11}

MaNemar检验主要用于二分类问题，与成对t检验一样也是用于比较两个学习器的性能大小。主要思想为：若两学习器的性能相同，则“A预测正确、B预测错误”数应等于“B预测错误、A预测正确”数，即e_{01}=e_{10}，且|e_{01}-e_{10}|\sim \mathcal{N}(1，e_{01}+e_{10})，则有

\begin{aligned}
\tau_{\chi^2}=\frac{(|e_{01}-e_{10}|-1)^2}{e_{01}+e_{10}}\sim \chi^2(1)
\end{aligned}

称该随机变量\tau_{\chi^2}服从自由度为1（因为只有1个变量）的卡方分布（χ²分布，Chi-squared Distribution），其相当于标准正态分布\mathcal{N}(0,1)的随机变量的平方和。进行双边χ²检验的方法类似于前两节所述，此处略，给定显著度\alpha，当\tau_{\chi^2}≤\chi_\alpha^2时，不能拒绝假设，即认为两学习器的性能没有显著差别；否则拒绝假设，即认为两者性能有显著差别，且平均错误率较小的那个学习器性能较优。自由度为1的χ²检验的临界值\chi_\alpha^2当\alpha=0.05时为3.8415，\alpha=0.1时为2.7055。

6.5 Friedman检验与Nemenyi后续检验

上述三种检验都只能在一组数据集上进行，基于算法排序的Friedman检验则可在多组数据集进行多个学习器性能的比较，基本思想为：首先在同一组数据集上，根据使用留出法或交叉验证法得到的每个算法在每个数据集上的测试结果（例如测试错误率）对学习器的性能进行排序，赋予序值1,2,\dots,N，若算法的测试性能相同则平分序值。【例】用4个数据集D_1,D_2,D_3,D_4对算法A,B,C进行比较为例，可列出如下所示的表，其中最后一行通过对每一列的序值求平均，得到平均序值：

数据集	算法A	算法B	算法C
D_1	1	2	3
D_2	1	2.5	2.5
D_3	1	2	3
D_4	1	2	3
平均序值	1	2.125	2.875

然后，使用Friedman检验来判断这些算法的性能是否都相同。若学习器的性能相同，则其平均序值应相同。假定在N个数据集上比较k个算法，则第i个算法的平均序值r_i（为简化讨论，暂不考虑平分序值的情况）满足r_i\sim \mathcal{N}\left (\dfrac{k+1}{2},\dfrac{k^2-1}{12}\right )，变量

\begin{aligned}
\tau_{\chi^2} &=\frac{k-1}{k}\cdot \frac{12N}{k^2-1}\sum\limits_{i=1}^k\left (r_i-\frac{k+1}2\right )^2\\
 &=\frac{12N}{k(k+1)}\left (\sum\limits_{i=1}^kr_i^2-\frac{k(k+1)^2}{4}\right )
\end{aligned}

在k和N都较大时，有\tau_{\chi^2}\sim \chi^2(k-1)。然而这种“原始Friedman检验”过于保守，现在通常使用变量

\begin{aligned}
\tau_F=\frac{(N-1)\tau_{\chi^2}}{N(k-1)-\tau_{\chi^2}}\sim F(k-1,(k-1)(N-1))
\end{aligned}

称\tau_F服从自由度为k-1和(k-1)(N-1)的F分布（F-Distribution）。以下两表是F检验常用的临界值：

• \alpha = 0.05：

N\k	2	3	4	5	6	7	8	9	10
4	10.128	5.143	3.863	3.259	2.901	2.661	2.488	2.355	2.250
5	7.709	4.459	3.490	3.007	2.711	2.508	2.359	2.244	2.153
8	5.591	3.739	3.072	2.714	2.485	2.324	2.203	2.109	2.032
10	5.117	3.555	2.960	2.634	2.422	2.272	2.159	2.070	1.998
15	4.600	3.340	2.827	2.537	2.346	2.209	2.104	2.022	1.955
20	4.381	3.245	2.766	2.492	2.310	2.179	2.079	2.000	1.935

• \alpha = 0.1：

N\k	2	3	4	5	6	7	8	9	10
4	5.538	3.463	2.813	2.480	2.273	2.130	2.023	1.940	1.874
5	4.545	3.113	2.606	2.333	2.158	2.035	1.943	1.870	1.811
8	3.589	2.726	2.365	2.157	2.019	1.919	1.843	1.782	1.733
10	3.360	2.624	2.299	2.108	1.980	1.886	1.814	1.757	1.710
15	3.102	2.503	2.219	2.048	1.931	1.845	1.779	1.726	1.682
20	2.990	2.448	2.182	2.020	1.909	1.826	1.762	1.711	1.668

若前几节中的假设H_0（“所有算法的性能相同”）被拒绝，则说明算法的性能显著不同，此时需进行后续检验（Post-hoc Test）来进一步区分各算法，常用的有Nemenyi后续检验，该方法检验计算出平均序值差别的临界值域

\begin{aligned}
CD=q_\alpha \sqrt{\frac{k(k+1)}{6N}}
\end{aligned}

其中q_\alpha是Tukey分布的临界值。下表是常用的q_\alpha值，若两个算法的平均序值差超出了临界值域CD，则以相应的置信度1-α拒绝“两个算法性能相同”的假设：

\alpha\k	2	3	4	5	6	7	8	9	10
0.05	1.960	2.344	2.569	2.728	2.850	2.949	3.031	3.102	3.164
0.1	1.645	2.052	2.291	2.459	2.589	2.693	2.780	2.855	2.920

---

7 偏差-方差分解

偏差-方差分解（Bias-Variance Decomposition）是解释学习器泛化性能的重要工具，试图对学习算法的期望泛化错误率进行拆解。对于测试样本\mathbf{x}，令y_D为\mathbf{x}在数据集中的标记，y为\mathbf{x}的真实标记，f(\mathbf{x};D)为训练集D上学得模型f在\mathbf{x}上的预测输出。以回归任务为例，学习算法的期望预测为

\begin{aligned}
\bar f(\mathbf{x})=\mathbb{E}_D[f(\mathbf{x};D)]
\end{aligned}

使用样本数相同的不同训练集产生的方差为

\begin{aligned}
\text{Var}(\mathbf{x})=\mathbb{E}_D[(f(\mathbf{x};D)-\bar f(\mathbf{x}))^2]
\end{aligned}

噪声为

\begin{aligned}
\varepsilon^2=\mathbb{E}_D[(y_D-y)^2]
\end{aligned}

期望输出与真实标记的差别称为偏差（Bias），即

\begin{aligned}
\text{Bias}^2(\mathbf{x})=(\bar f(\mathbf{x})-y)^2
\end{aligned}

为便于讨论，假定噪声期望为零，即\mathbb{E}_D[y_D-y]=0，通过简单的多项式展开合并，可将算法的期望泛化误差E(f;D)进行分解，过程如下

\begin{aligned}
E(f;D) &= \mathbb{E}_D[(f(\mathbf{x};D)-y_D)^2]\\
 &= \mathbb{E}_D[(f(\mathbf{x};D)-\bar f(\mathbf{x}) + \bar f(\mathbf{x})- y_D)^2]\\
 &= \mathbb{E}_D[(f(\mathbf{x};D)-\bar f(\mathbf{x}))^2] + \mathbb{E}_D[(\bar f(\mathbf{x})-y_D)^2] + \mathbb{E}_D[2(f(\mathbf{x};D)-\bar f(\mathbf{x}))(\bar f(\mathbf{x}) - y_D)] \\
 &= \mathbb{E}_D[(f(\mathbf{x};D)-\bar f(\mathbf{x}))^2] + \mathbb{E}_D[(\bar f(\mathbf{x})-y_D)^2] \\
 &= \mathbb{E}_D[(f(\mathbf{x};D)-\bar f(\mathbf{x}))^2] + \mathbb{E}_D[(\bar f(\mathbf{x}) - y + y -y_D)^2]  \\
 &= \mathbb{E}_D[(f(\mathbf{x};D)-\bar f(\mathbf{x}))^2] + \mathbb{E}_D[(\bar f(\mathbf{x})-y)^2] + \mathbb{E}_D[(y-y_D)^2] + 2\mathbb{E}_D[(\bar f(\mathbf{x}) - y)(y-y_D)] \\
 &= \mathbb{E}_D[(f(\mathbf{x};D)-\bar f(\mathbf{x}))^2] + (\bar f(\mathbf{x}) - y)^2 + \mathbb{E}_D[(y_D-y)^2]\\
 &= \text{Var}(\mathbf{x})+\text{Bias}^2(\mathbf{x})+\varepsilon^2\\
\end{aligned}

可见，算法的期望泛化误差为方差、偏差与噪声之和，其中

• 方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响，体现学习器的稳定性
• 偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习器的拟合能力
• 噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。

偏差-方差分解说明，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。给定学习任务，为了取得好的泛化性能，则需使偏差较小，即能够充分拟合数据，并且使方差较小，即使得数据扰动产生的影响小。

一般情况下，方差和偏差具有矛盾性，这就是常说的偏差-方差窘境（Bias-Variance Dilamma）：随着训练程度的提升，期望预测值与真实值之间的差异越来越小，即偏差越来越小；但另一方面，随着训练程度加大，学习算法对数据集的波动越来越敏感，方差值越来越大。换句话说，在欠拟合时，偏差主导泛化误差；而训练到一定程度后，偏差越来越小，方差主导了泛化误差。如下图所示：

因此训练不要贪，适度辄止。