2.4 比较检验

有了实验评估方法和性能度量，看起来就能对学习器的性能进行评估比较了：先使用某种实验评估方法测得学习器的某个性能度量结果，然后对这些结果进行比较。但怎么来做这个“比较”呢？是直接取得性能度量的值然后“比大小”吗？实际上，机器学习中性能比较这件事要比大家想象的复杂得多。这里面涉及几个重要因素：首先，我们希望比较的是泛化性能，然而通过实验评估方法我们获得的是测试集上的性能，两者的对比结果可能未必相同；第二，测试集上的性能与测试集本身的选择有很大关系，且不论使用不同大小的测试集会得到不同的结果，即便用相同大小的测试集，若包含的测试样例不同，测试结果也会有不同；第三，很多机器学习算法本身有一定的随机性，即便用相同的参数设置在同一个测试集上多次运行，其结果也会有不同。那么，有没有适当的方法对学习器的性能进行比较呢？

更多关于假设检验的介绍可参见[Wellek，2010]。

统计假设检验（hypothesis test）为我们进行学习器性能比较提供了重要依据。基于假设检验结果我们可推断出，若在测试集上观察到学习器A比B好，则A的泛化性能是否在统计意义上优于B，以及这个结论的把握有多大。下面我们先介绍两种最基本的假设检验，然后介绍几种常用的机器学习性能比较方法。为便于讨论，本节默认以错误率为性能度量，用表示。

2.4.1 假设检验

假设检验中的“假设”是对学习器泛化错误率分布的某种判断或猜想，例如“=0”。现实任务中我们并不知道学习器的泛化错误率，只能获知其测试错误率泛化错误率与测试错误率未必相同，但直观上，二者接近的可能性应比较大，相差很远的可能性比较小。因此，可根据测试错误率估推出泛化错误率的分布。

泛化错误率为的学习器在一个样本上犯错的概率是；测试错误率意味着在m个测试样本中恰有×m个被误分类。假定测试样本是从样本总体分布中独立采样而得，那么泛化错误率为的学习器将其中m′个样本误分类、其余样本全都分类正确的概率是；由此可估算出其恰将×m个样本误分类的概率如下式所示，这也表达了在包含m个样本的测试集上，泛化错误率为的学习器被测得测试错误率为的概率：

给定测试错误率，则解∂P（；）/∂=0可知，P（；）在=时最大，|-|增大时P（；）减小。这符合二项（binomial）分布，如图2.6所示，若=0.3，则10个样本中测得3个被误分类的概率最大。

α的常用取值有0.05、0.1，图2.6中α较大是为了绘图方便。

我们可使用“二项检验”（binomial test）来对“≤0.3”（即“泛化错误率是否不大于0.3”）这样的假设进行检验。更一般的，考虑假设“≤0”，则在1-α的概率内所能观测到的最大错误率如下式计算。这里1-α反映了结论的“置信度”（confidence），直观地来看，相应于图2.6中非阴影部分的范围。

s.t.是“subject to”的简写，使左边式子在右边条件满足时成立。

二项检验的临界值在R语言中可通过qbinom（1-α，m，0）计算，在Matlab中是icdf（′Binomial′，1-α，m，0）。

此时若测试错误率小于临界值，则根据二项检验可得出结论：在α的显著度下，假设“≤0”不能被拒绝，即能以1-α的置信度认为，学习器的泛化错误率不大于0；否则该假设可被拒绝，即在α的显著度下可认为学习器的泛化错误率大于0。

R语言是面向统计计算的开源脚本语言，参见www.r-project.org。

在很多时候我们并非仅做一次留出法估计，而是通过多次重复留出法或是交叉验证法等进行多次训练/测试，这样会得到多个测试错误率，此时可使用“t检验”（t-test）。假定我们得到了k个测试错误率，1，2，...，k，则平均测试错误率μ和方差σ2为

考虑到这k个测试错误率可看作泛化错误率0的独立采样，则变量

服从自由度为k−1的t分布，如图2.7所示。

临界值tα/2在R语言中可通过qt（1−α/2，k−1）计算，在Matlab中是icdf（′T′，1−α/2，k−1）。

对假设“μ=0”和显著度α，我们可计算出当测试错误率均值为0时，在1-α概率内能观测到的最大错误率，即临界值。这里考虑双边（two-tailed）假设，如图2.7所示，两边阴影部分各有α/2的面积；假定阴影部分范围分别为[−∞，t−α/2]和[tα/2，∞]。若平均错误率μ与0之差|μ−0|位于临界值范围[t−α/2，tα/2]内，则不能拒绝假设“μ=0”，即可认为泛化错误率为0，置信度为1−α；否则可拒绝该假设，即在该显著度下可认为泛化错误率与0有显著不同。α常用取值有0.05和0.1.表2.3给出了一些常用临界值。

上面介绍的两种方法都是对关于单个学习器泛化性能的假设进行检验，而在现实任务中，更多时候我们需对不同学习器的性能进行比较，下面将介绍适用于此类情况的假设检验方法。

2.4.2 交叉验证t检验

对两个学习器A和B，若我们使用k折交叉验证法得到的测试错误率分别为和其中和是在相同的第i折训练/测试集上得到的结果，则可用k折交叉验证“成对t检验”（paired-tests）来进行比较检验。这里的基本思想是若两个学习器的性能相同，则它们使用相同的训练/测试集得到的测试错误率应相同，即=。

具体来说，对k折交叉验证产生的k对测试错误率：先对每对结果求差，∆i=−；若两个学习器性能相同，则差值均值应为零。因此，可根据差值∆1，∆2，...，∆k来对“学习器A与B性能相同”这个假设做t检验，计算出差值的均值μ和方差σ2，在显著度α下，若变量

小于临界值tα/2，k-1，则假设不能被拒绝，即认为两个学习器的性能没有显著差别；否则可认为两个学习器的性能有显著差别，且平均错误率较小的那个学习器性能较优。这里tα/2，k-1是自由度为k-1的t分布上尾部累积分布为α/2的临界值。

欲进行有效的假设检验，一个重要前提是测试错误率均为泛化错误率的独立采样。然而，通常情况下由于样本有限，在使用交叉验证等实验估计方法时，不同轮次的训练集会有一定程度的重叠，这就使得测试错误率实际上并不独立，会导致过高估计假设成立的概率。为缓解这一问题，可采用“5×2交叉验证”法[Dietterich，1998]。

5×2交叉验证是做5次2折交叉验证，在每次2折交叉验证之前随机将数据打乱，使得5次交叉验证中的数据划分不重复。对两个学习器A和B，第i次2折交叉验证将产生两对测试错误率，我们对它们分别求差，得到第1折上的差值和第2折上的差值。为缓解测试错误率的非独立性，我们仅计算第1次2折交叉验证的两个结果的平均值，但对每次2折实验的结果都计算出其方差。变量

服从自由度为5的t分布，其双边检验的临界值tα/2，5当α=0.05时为2.5706，α=0.1时为2.0150。

2.4.3 McNemar检验

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

e01=e10通常很小，需考虑连续性校正，因此分子中有-1项。

若我们做的假设是两学习器性能相同，则应有e01=e10，那么变量|e01-e10|应当服从正态分布。McNemar检验考虑变量

中文称为“卡方分布”。

临界值在R语言中可通过qchisq（1-α，k-1）计算，在Matlab中是icdf（′Chisquare′，1-α，k-1）。这里的k=2是进行比较的算法个数。

服从自由度为1的2分布，即标准正态分布变量的平方。给定显著度α，当以上变量值小于临界值时，不能拒绝假设，即认为两学习器的性能没有显著差别；否则拒绝假设，即认为两者性能有显著差别，且平均错误率较小的那个学习器性能较优。自由度为1的2检验的临界值当α=0.05时为3.8415，α=0.1时为2.7055。

2.4.4 Friedman检验与Nemenyi后续检验

交叉验证t检验和McNemar检验都是在一个数据集上比较两个算法的性能，而在很多时候，我们会在一组数据集上对多个算法进行比较。当有多个算法参与比较时，一种做法是在每个数据集上分别列出两两比较的结果，而在两两比较时可使用前述方法；另一种方法更为直接，即使用基于算法排序的Friedman检验。

假定我们用D1、D2、D3和D4四个数据集对算法A、B、C进行比较。首先，使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果，然后在每个数据集上根据测试性能由好到坏排序，并赋予序值1，2，...；若算法的测试性能相同，则平分序值。例如，在D1和D3上，A最好、B其次、C最差，而在D2上，A最好、B与C性能相同，……，则可列出表2.5，其中最后一行通过对每一列的序值求平均，得到平均序值。

然后，使用Friedman检验来判断这些算法是否性能都相同。若相同，则它们的平均序值应当相同。假定我们在N个数据集上比较k个算法，令ri表示第i个算法的平均序值，为简化讨论，暂不考虑平分序值的情况，则ri的均值和方差分别为（k+1）/2和（k2-1）/12。变量

原始检验要求k较大（例如＞30），若k较小则倾向于认为无显著区别。

在k和N都较大时，服从自由度为k-1的2分布。

然而，上述这样的“原始Friedman检验”过于保守，现在通常使用变量

其中2由式（2.34）得到。F服从自由度为k-1和（k-1）（N-1）的F分布，表2.6给出了一些常用临界值。

F检验的临界值在R语言中可通过qf（1−α，k-1，（k-1）（N-1））计算，在Matlab中是icdf（′F′，1-α，k-1，（k-1）*（N-1））。

若“所有算法的性能相同”这个假设被拒绝，则说明算法的性能显著不同。这时需进行“后续检验”（post-hoc test）来进一步区分各算法。常用的有Nemenyi后续检验。

Nemenyi检验计算出平均序值差别的临界值域

qα是Tukey分布的临界值，在R语言中可通过qtukey（1-α，k，Inf）/sqrt（2）计算。

表2.7给出了α=0.05和0.1时常用的qα值。若两个算法的平均序值之差超出了临界值域CD，则以相应的置信度拒绝“两个算法性能相同”这一假设。

以表2.5中的数据为例，先根据式（2.34）和（2.35）计算出F=24.429，由表2.6可知，它大于α=0.05时的F检验临界值5.143，因此拒绝“所有算法性能相同”这个假设。然后使用Nemenyi后续检验，在表2.7中找到k=3时q0.05=2.344，根据式（2.36）计算出临界值域CD=1.657，由表2.5中的平均序值可知，算法A与B的差距，以及算法B与C的差距均未超过临界值域，而算法A与C的差距超过临界值域，因此检验结果认为算法A与C的性能显著不同，而算法A与B、以及算法B与C的性能没有显著差别。

上述检验比较可以直观地用Friedman检验图显示。例如根据表2.5的序值结果可绘制出图2.8，图中纵轴显示各个算法，横轴是平均序值。对每个算法，用一个圆点显示其平均序值，以圆点为中心的横线段表示临界值域的大小。然后就可从图中观察，若两个算法的横线段有交叠，则说明这两个算法没有显著差别，否则即说明有显著差别。从图2.8中可容易地看出，算法A与B没有显著差别，因为它们的横线段有交叠区域，而算法A显著优于算法C，因为它们的横线段没有交叠区域。