资料来源参考：

清华大学出版社 周志华 《机器学习》 第一、二章

引子

在一个又一个算法模型的章节之后突然冒出来这么一个章节并非是没有原因的，从“资料参考来源”中我们也可以看出来，我似乎在越学越回去了，但事实上并非如此，而是我发现在进行机器学习的过程中开始逐渐的出现了一些与机器学习密切相关，但在学习开始时被我忽略的，而后又确证明是非常基础的先验知识。我在前面的章节中有多个地方出现了“之后我们再做详细讨论”就是这个缘故。但这并不意味着我对我直接跳过它们进行学习感到后悔，事实上，我觉得先学习一段时间的算法模型并实际尝试几个模型之后再取学习这部分内容会比上手直接学要有感触得多。至少于我而言，带着问题和疑惑去学，会比上来直接强行学某些知识效果要更好些。

因此，本章节将会着重于这部分基础内容。

不过在开始之前我还要说明一下关于两章之前有关AdaBoost和向前分步算法得关系的讨论，事实上我在参阅西瓜书集成学习后面的一部分扩展阅读内容之后发现，对于李教授在《统计学习方法》中讲述的关于AdaBoost由向前分步算法推导而来的结论，周教授是保留意见的。因为由“统计视角”出发的这个推论不能很好的解释AdaBoost为什么没有过拟合现象（严格表述是为什么AdaBoost在训练误差达到 0之后继续训练仍能提高泛化性能；若一直训练下去，过拟合最终仍会出现）。不过我们仍可以参考统计学派的这一视角，因为其本身还是很有意义的，只是它可能更像是阐释一个与AdaBoost相似的学习过程而非AdaBoost本身。

归纳偏好

本章的着重点在于如何选择模型和评估一个模型的性能。在前面我们一直都是在用模型的准确率作为评判模型好坏的标准，但事实上，判断该在什么场景使用怎样的模型，以及模型的表现如何，远不只有准确率这么简单。

让我们从一个有趣的定理开始讨论如何选择一个最适合的模型：

假设我们有两个算法，A和B，它们在某训练集上的表现如图：

若仅在训练集上，两个算法的表现一致，但我们知道若是在测试集上，曲线“平滑”的算法A一般情况下会比曲线“崎岖”的算法B表现的更好。

这样我们知道，哪怕是两个在训练集上看似“等效”的算法，未必就是效果也相同的算法。

而算法A的这种情况我们就称之为对这种类型假设的归纳偏好（inductive bias），简称偏好。偏好可以看作是学习算法在一个可能很庞大的假设空间（即包含了所有可能的假设（hypothesis）的空间）对假设进行选择的启发式或“价值观”，一般来说，我们用奥卡姆剃刀（Occam’s razor）准则作为引导算法确立其偏好的一般性原则，换句话说，就是若有多个假设与观察一致，则选择最简单的那个，在这个原则下，我们会普遍认为，越“平滑”的就是越“简单的”，也即越合适的模型，例如上图中的曲线A，它的方程式就要比曲线B的简单的多。

但是，奥卡姆剃刀准则却并非是唯一可行的，在某些情况下，甚至奥卡姆剃刀准则自身的诠释也会有争议。例如，我们发现了两个假设，一是“色泽= * ；根蒂=蜷缩；敲声=浊响”的瓜就是好瓜（ * 表示通配符，就是什么内容都适用）；二是“色泽= * ；根蒂=蜷缩；敲声=*”的瓜就是好瓜。那么仅对这两个假设，我们怎么知道哪一个假设才是更“简单”的那个呢？这个时候往往就需要借助其它的机制来帮我们判断那个假设更合适了。

而且事实上，算法的归纳偏好与问题本身的匹配程度往往决定了算法的性能好坏，换句话说，在具体的问题中，假设的成立与否会影响我们对对应模型的评价。

而且这并不是唯一的问题，尽管我们知道算法A在上图中的泛化性能要比算法B更强，但事实上，在某些情况下，算法B的性能，也即在测试集的效果反而会比算法A更强。这似乎有悖于我们的奥卡姆剃刀准则？但并非不可能，就像下图：

尽管是用了相同的训练样本，但（b）图中出现的测试样本集反而更加匹配算法B。

这个时候，我们就会感到疑惑了，那算法A与算法B，究竟哪一个算法会更好？

有趣的是，Wolpert and Macready[1995]告诉我们，算法A与算法B能够成功匹配测试集的期望，实际上是一样的，换言之，无论算法A有多“聪明”，算法B有多“笨拙”，哪怕算法B其实就是在随机猜测，二者的期望性能都是相同的，如果算法A在某个问题上表现的要比算法B要好，那么一定也有其他问题，算法B表现的要比算法A要好。

这个似乎有违我们直觉的定理，就是著名的没有免费的午餐定理（No Freee Lunch Theorem,NFL）

对这个定理，我们可以来做一个简单的证明（之所以是“简单”，是因为严格的NFL证明会比下面的复杂的多，但老样子，这不是我们目前要着重关注的内容）：

假设样本空间${\cal X}$和假设空间$H$都是离散的，令$P(h\mid X,\zeta_a)$代表算法$\zeta_a$基于训练数据$X$（注意不是${\cal X}$）产生假设$h$的概率，再令$f$代表我们希望学习的真实目标函数，$\zeta_a$的“训练集外误差”（换句话说，在测试机上的误差），即$\zeta_a$在训练集之外所有样本上的误差为：

其中$I()$为指示函数。

考虑二分类问题，且真实目标函数可以是任何函数${\cal X}\rightarrow\{0,1\}$，函数空间为$\{0,1\}^{\mid {\cal X}\mid}$。对所有可能的$f$按均匀分布对误差求和，有：

（可能会对$\sum_fI(h(x)≠f(x))\rightarrow \frac{1}{2}2^{\mid {\cal X}\mid}$这一步有疑惑。我们可以这样理解，因为$I$的值仅有0，1两种，又因为$f$均匀分布，所以$h(x)≠f(x)$的概率就是0.5，因此$2^{\mid {\cal X}\mid}$就是$I(h(x)≠f(x))$所有可能取值的个数，又因为其中一半是0，所以有$\sum_fI(h(x)≠f(x))= \frac{1}{2}2^{\mid {\cal X}\mid}$）

上式表明，总误差确实是与学习算法无关的，因而，对于任意两个学习算法$\zeta_a$和$\zeta_b$，我们都有：

由此得证NFL。但这下子我们反而会更加疑惑：既然所有算法都一样，那还有什么好选的？

然而，NFL定理又一个相当重要的前提就是真实目标函数$f$服从均匀分布，这意味着，所有的“问题”出现的机会是相同的，或者是说，所有的问题同等重要。这是一个很不符合现实的问题，因为我们只会关注自己正在解决的问题，换句话说，在我们关注的问题上能取得好效果的算法能不能在其他问题上效果也一样好，和我们没有关系。

因此，这一段讲了这么多，其实最终都只导向一个目的，那就是我们选择算法的标准：

没有最“好”的算法，只有最“合适”的算法。

评估方法

于是，我们的问题，如何选择“好”的模型就变成了如何选择最“合适”的模型。在解决这个问题之前，我们还需要解决另一个问题，那就是，怎么样评估一个模型是否“合适”？

我们曾经讨论过经验风险，欠拟合和过拟合的问题，那其实就与我们在这里要讨论的东西密切相关。另外，我们还曾介绍过评估模型精确度的一个“交叉验证法”，实际上，这就是评估模型的几种常见的做法之一。

假设我们有一个数据集D，下面我们来介绍一下另外的几种利用这个数据集评估模型的方法：

留出法

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

这是一个简单而且我们也用过不少次的方法。

需要注意的是，训练/测试集的划分要尽可能的保持数据分布的一致性，以免因数据划分过程引入额外的偏差而对最终结果产生影响。像是在分类任务中，就要注意保证样本的类别比例相似。若是从采样（sampling）的角度来看待数据的划分过程，则保留类别比例的采样方式通常称为分层采样（stratified samplinbg）。

举个例子，若对D进行分层采样，获得70%样本的训练集S和30%的测试集T，若D包含500个正例、500个反例，则分层采样得到的S应包含150个正例、150个反例。

如果S、T中样本类别差别比例很大，则误差估计也将由于训练/测试数据分布的差异而产生偏差。

另一个需要注意的问题是，即使是确定了训练/测试集的样本比例，仍然有多种对数据集D进行分割的划分方式。像上例，可以将D中的样本排序，然后把前350个正例放到训练集中，也可以将最后350个正例放到训练集中……这些不同的划分将导致不同的训练/测试集，相应的，模型评估的结果也会有差别。正因此，单次使用留出法的评估结果并不稳定可靠。一般来说，在使用留出法时，要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。例如进行100次随机划分，每次产生一个训练/测试集用于实验评估，100次后得到100个结果，然后返回这100个结果的平均（同时还可以得到估计结果的标准差）。

但由于留出法对数据集划分的操作，这导致：如果训练集S包含大多数样本，那么由于测试集T包含的样本不多，训练出的模型可能不够稳定准确；若令测试集T多包含一些样本，又会使得训练集S和数据集D的差别加大，被评估的模型与用D训练出的模型相比可能有较大差别，从而降低了评估结果的保真性（fidelity）（可以从偏差-方差角度来看，测试集小则评估结果方差较大；训练集小，则评估结果偏差较大）。这个问题并没有太好的解决方案，因此常见做法是将大约$\frac{2}{3}\sim \frac{4}{5}$的样本用于训练，剩余用于测试（一般而言，测试集最少应包含30个样例）。

自助法

自助法和留出法与我们之前在knn章节中讨论过的交叉验证法不同，后两者评估的模型所使用的训练集总是会比数据集D小，这就使得一些因训练样本规模不同而导致的估计偏差被引入。k折交叉验证法中的特例留一法尽管受到的训练集的规模变化影响较小，但又因为其计算复杂度过高，使得开销过大。

由此，自助法（bootstrapping）便是被提出的一个比较好的解决方案，它是以自助采样法（bootstrap sampling）为基础的方法，自助采样又称“可重复采样”，“有放回采样”。

假设有m个样本的数据集D，我们对它进行采样产生数据集D’：每次随机从D中挑选一个样本拷贝入D’，然后将样本放回。重复m次后，我们就得到一个规模与D相同，即包含m个样本的数据集D’了。

在集成学习的讨论中，我们曾提到过，D中有一部分样本会在D’中重复出现，一部分样本不出现，不出现的样本约占D的36.8%，我们现在可以来简单的计算一下，这个结果是如何出现的：

假设样本在m次采样中始终不被采到的概率为$(1-\frac{1}{m})^m$，取极限得到：

（这个证明很简答，高等数学中的常用极限）

这样子，我们就可以将D’用作训练集，D\D’用作测试集，使得司机评估的模型和期望评估的模型都使用了m个训练样本，而我们仍有约$\frac{1}{3}$的样本没有在训练集中出现并可用于测试。这样的测试结果，我们就称为包外估计（out-of-bag estimate）

自助法特别适用于数据集小、难以有效划分训练/测试集的状况；此外，由于其能从初始训练集中产生多个不同的训练集，这对集成学习等方法也有很大的好处（上一章的Bagging就是一种）。但有利必有弊，自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差，因此，若初始数据量足够，还是留出法和交叉验证法比较常用。

不过，即使是交叉验证的留一法，也未必永远比其它估计方法准确，根据情况采取评估方法——“没有免费的午餐定理”对于实验评估方法也同样适用。

调参与最终模型

我们在前面的算法学习中，往往会遇到有参数（parameter）需要设定（像是梯度上升的步长），参数配置的不同，往往也会影响到模型的性能。这中对算法参数的设定，就是我们通常所说的“参数调节”，简称调参（parameter tuning）。

而机器学习涉及的参数有两种：

1. 第一种是我们需要人为设置的参数，这种参数称为超参数，数目通常在10个以内
2. 另一类是模型参数，数目可能很多，在大型深度学习模型中甚至会有上百亿个参数。

两者调参的方式相似，一般都是在产生多个模型之后基于某种评估方法来进行选择；不同点在于，超参数通常是有人工设定多个参数候选值后产生模型，而后者这是通过学习来产生多个模型。

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

但需要注意的是，这些参数往往都是在实数范围内取值，换句话说，是连续的。因此，我们常用的做法是对每个参数设定一个范围和变化步长，例如[0，0.2]范围内以0.05为步长，这样子这个参数的候选值在实际评估中就仅有5个，最终结果将从这5个候选值中选定。我们知道，这种做法选出来的参数往往并不是最佳的，但这是在计算开销和性能估计之间进行折中的唯一方法，而且事实上，哪怕是用这种方法，调参也相当不容易。我们可以假设一下，如果一个算法有3个参数，每个参数5个候选值，那么排列组合一下，对于一组训练/测试集就有$5^3=125$个模型需要考察；在很多强大的学习算法中，有不少参数需要设定，这也就导致了极大的调参工程量，以至于在不少应用任务中，参数调的好与不好对最终模型的性能会有关键性的影响。

另外，若给定m个样本的数据集，我们在模型评估与选择中因为需要留出一部分数据进行评估测试，往往只会用到数据集的一部分来训练模型。因此，在确定好学习算法和参数配置后，我们还要用原有的数据集D重新训练一个模型，这个模型才是我们需要最终提交给用户的模型。

还有一点，就是我们实际上只会把模型在实际使用中遇到的数据称为测试集，而在模型评估与选择中，用于评估测试的数据集我们称为验证集（validation set）。

性能度量

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

性能度量反映任务需求，在对比不同模型的能力时，使用不同的性能度量往往会导致不同的评判结果，也即是说，模型的好坏其实也是相对的，什么样的模型是“合适”的，不仅和算法与数据有关，还和任务需求有关。

假设有数据集$D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$，其中$y_i$是示例$x_i$的真实标记（类别标签）。要评估学习器f的性能，我们就要将学习器预测结果与真实标记y进行比较。

均方误差（mean squared error）

我们先介绍回归任务常用的性能度量方式，均方误差，它的表达式我们已经相当熟悉了：

更一般的，对于数据分布D和概率密度函数$p(·)$，均方误差可描述为：

错误率与精度

接下来我们主要介绍分类任务的性能度量。

分类任务中最常用的两种性能度量就是错误率和精度，既适用于二分类，也适用于多分类。

对样本集D，错误率表示分类错误的样本数占样本总数的比例，定义为：

精度表示分类正确的样本占样本总数的比例，定义为：

更一般的，对于数据分布D和概率密度函数$p(·)$，错误率与精度可分别描述为：

查准率、查全率、F1

错误率和精度尽管常用，但并不代表它能满足所有的任务需求。假设瓜农拉来一车瓜（西瓜书的每个例子都离不开瓜，果真不是浪得虚名），我们用某训练好的模型对这些西瓜进行判别，错误率便衡量了有多少比例的瓜被判别错误。但是，若我们关心的是“挑出的西瓜中好瓜的比例是多少”，或说“挑出的瓜占所有好瓜的比例”，这个时候我们就需要一些其它的性能度量来帮助我们解决这些问题了。

仅看上面这个例子似乎不太能理解为什么会有这样的问题，但事实上，类似的需求往往会在信息检索，web搜索等应用中经常出现：例如，在信息检索中，我们会关注“检索出的信息中用户感兴趣的信息占的比例是多少”，“有多少用户感兴趣的信息被检索出来了”……这个时候，查准率（precision）（亦称准确率）和查全率（recall）（亦称召回率）就是更为适用于此类需求的性能度量。

对于二分类问题，我们可以将样本根据其真实类别与学习器预测出来的类别的组合划分为真实例（true positive,TP），假正例（false positive,FP），真反例（true negative,TN），假反例（false negative,FN），若令TP,FP,TN,FN分别表示其对应的样本数，那么就有$TP+FP+TN+FN=$样本总数。分类结果的混淆矩阵（confusion matrix）如图：

• TP：预测为正，实际为正的样本数量
• FN：预测为负，实际为正的样本数量
• FP：预测为正，实际为负的样本数量
• TN：预测为负，实际为负的样本数量

因此，很显然，预测正确的样本数量就是TP+TN，预测错的样本数量就是FN+FP，positive和negative表示其类别标签，true和false表示预测结果与真实情况是否相同。

由此，我们有查准率P的定义式：

查全率R的定义式：

查准率和查全率是一对矛盾的度量，换句话说，在一般情况下，查准率越高查全率就会偏低；查全率越高，查准率就会越低。

例如，我们若希望尽可能将好瓜都选出来，那么我们可以通过增加选中的瓜的数量来实现，若是将所有的瓜都选了，那必然也会选中所有的好瓜，但这样子查准率就会偏低；若希望选出的瓜中好瓜比例尽可能的高，那么就会只挑选有把握的瓜，但这样难免会漏掉不少好瓜，就使得查全率较低。一般只有在一些简单任务中，才能使查全率和查准率都高。

这个例子看起来有点奇怪，我们可以举一个分类垃圾邮件的例子，我们希望选中垃圾邮件准确率尽可能的高，但也绝不能把有用的邮件归为垃圾邮件，因为这样显然会惹恼用户，这个时候，就是“宁放过，不杀错”，宁可查漏几封垃圾邮件，也不能不小心过滤掉了对于用户有用的邮件，也即是让查准率高，同时查全率也就相对变低。

在很多情况下，我们可以根据学习器的预测结果来对样本进行排序，学习器将人为“最可能”是正例的样本排在前面，“最不可能”是正例的样本排在后面，按照这个顺序我们逐个将样本作为正例进行预测，就可以在每一次计算出当前的查全率与查准率。（就是每添加一个样本计算一次查全率和查准率）

（以信息检索为例，我们逐条向用户反馈其可能感兴趣的信息，就可以计算出查全率，查准率）

我们以查准率为纵轴、查全率为横轴在二维平面上作图，得到查准率-查全率曲线，简称P-R曲线（PR曲线），显示该曲线的图称为P-R图（PR图），下面就是三个学习器的PR曲线组成的PR图：

PR图直观地显示出学习器在样本总体上的查全率、查准率。在进行比较时，若一个学习器的PR曲线被另一个学习器的PR曲线完全“包住”，我们就可以断言后者的性能优于前者，像上图中学习器A的性能就优于学习器C；若是两个学习器的PR曲线发生交叉，像A和B，就比较难断言孰优孰劣，只能是在具体的查准率或查全率条件进行比较。

但也有很多时候我们仍希望A和B分个高低，这个时候我们会选择比较PR曲线下面积的大小，这是一个比较合理的判据，它在一定程度上表征了学习器在查准率和查全率取得相对“双高”的比例。但这个值又不是那么好算，因此，人们又设计了一些综合考虑查准率、查全率的性能度量：

平衡点（Break-Even Point,BEP）

平衡点就是那么一个综合考虑查准率和查全率的性能度量，它是“查准率=查全率”时的取值，如上图中C的BEP就是0.64，而基于BEP进行比较，我们可以认为学习器A要比B好。

F1

但BEP还是有些过于简单了，更常用的是F1度量：

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

F1度量的额一般形式——$F_\beta$，能让我们表达出对查准率/查全率的不同偏好，它定义为：

实际上就是加权调和平均：

（与算数平均$\frac{P+R}{2}$和几何平均$\sqrt{(P*R)}^2$相比，调和平均更重视较小值，换句话说，就是受较小值的影响比受较大值的影响要大，举个例子，就好像是两个电阻并联的等效电阻的值受到电阻值较小的电阻的影响更大）

其中 β > 0 度量了查全率对查准率的相对重要性。β =1 时退化为标准的 F1 ；β > 1 时查全率具有更大影响； β < 1 时查准率有更大影响。

多个二分类混淆矩阵的综合考查

很多时候我们往往有多个二分类混淆矩阵，例如在进行多次训练/测试的时候，每次训练/测试都会得到一个混淆矩阵；或是在多个数据集上进行训练/测试；又或是执行多分类任务，类别的每一个两两组合都可以衍生出一个混淆矩阵……这个时候，我们就希望在 n 个二分类混淆矩阵上综合考察准确率和查全率。

一种方法是直接在各混淆矩阵上分别计算出查准率和查全率，记为$(P_1,R_1),...,(P_n,R_n)$，在计算平均值，这样子得到的额就是宏查准率（macro-P）、宏查全率（macro-R），以及相应的宏F1（macro-F1）：

还有一种方法是将各混淆矩阵的对应元素进行平均，得到 TP,FP,TN,FN 的平均值，分别记为$\bar{TP},\bar{FP},\bar{TN},\bar{FN}$，再基于这些平均值计算出微查准率（micro-P），微查全率（micro-R），微F1（micro-F1）：

ROC与AUC

一般来说，我们在解决分类问题的时候用的学习器都是为测试样本产生一个实值或者概率预测，然后将这个预测值与预设的一个分类阈值（threshold）进行比较，若大于阈值则认为样本为正，反之为负。这样的学习器我们见过很多，逻辑回归（阈值0.5），感知机（阈值0）等等，这个预测值结果的好坏往往直接决定学习器的泛化能力。

但我们并不是只有这一种方法，实际上，我们还可以根据这个预测值，对测试样本进行排序，“最可能”为正例的样本排在最前面，“最不可能”为正例的样本排在最后面。然后，我们规定分类过程就是在这个序列中以某个截断点（cut point）为基准将样本集划分为两部分，排在前面的那一部分当作正例，排在后面的那一部分当作反例。

这样子，我们就可以根据不同的任务需求来采用不同的截断点，假设我们更重视查准率，那就可以让截断点靠近序列的前面；若是重视查全率，则可以让截断点排在序列的靠后方。因此，排序本身的质量好坏，就体现了综合考虑学习器在不同任务下期望泛化性能的好坏，或者说是“一般情况下”泛化性能的好坏。

ROC曲线就是从这个角度出发来研究学习器泛化性能的工具。

ROC全称受试者工作特征（Receiver Operating Characteristic）曲线，它的绘制过程与PR曲线类似，我们首先根据学习器的预测结果对样本进行排序，然后从前往后逐个将样本作为正例进行预测，每多预测一个样本，就对已预测的所有样本计算两个重要的值。这两个值就是它与PR曲线的区别，这两个值分别是真正例率（True Positive Rate ,TPR），作为ROC曲线的纵轴；假正例率（False Positive Rate,FPR），作为横轴，两者的定义分别为：

TPR即预测正确的正例占预测正确的正例和预测错误的反例中比例，FPR即预测错误的正例占预测正确的反例和预测错误的正例的比例。

显示ROC曲线的图为ROC图，下面这幅图中的（a）图就是一个示例：

对角线表示的是“随机猜测”模型，点（0，1）则对应于将所有正例排在所有反例之前的“理想模型”。

现实中通常利用有限个测试样本来绘制ROC图，此时就仅能获得有限个（真正例率，假正例率）坐标对，结果就像（b）图一样，而无法得到（a）图中那样的光滑曲线。（PR图其实也有一样的问题）

绘图过程如下：

假设我们有$m^+$个正例，$m^-$个反例：

1. 将分类阈值设为最大，即把所有样例均设为反例，此时真正例率和假正例率均为0，在坐标（0，0）处标记一个点
2. 将分类阈值一次设为每个样例的预测值，即截断点依次向后调，假设前一个标记点的坐标为（x,y），则后一个点若为真正例，坐标就是$(x,y+\frac{1}{m^+})$；若为假正例，则对应标记点坐标为$(x+\frac{1}{m^-},y)$
3. 用线段连接相邻点即可

与PR图相同，若一个学习器的ROC曲线被另一个学习器包住，我们就断言后者性能优于前者；若两者发生交叉，则判断ROC曲线下的面积AUC（Area Under ROC Curve）

假设ROC曲线的坐标集合为$\{(x_1,y_1),...,(x_m,y_m)\}$，其中$(x_1=0,x_m=1)$，这些点连成曲线，如图（b），则AUC可估算为：

（AUC的计算公式之所以这么写，而不是直接计算对应矩形的面积之和，是因为有时候当多个样本的预测值相等时，我们调整阈值就会使得标记点相对上一个标记点斜向平移，这个时候用求矩形面积之和的公式就不方便计算了，参考AUC计算方法总结 ）

AUC考虑样本预测的排序质量，因此它与排序误差有紧密联系。给定$m^+$个正例和$m^-$个反例，令$D^+$和$D^-$分别表示正、反例集合，则排序损失（loss）定义为：

即考虑每一对正、反例，若正例的预测值小于反例，则记一个“罚分”，若相等，则记0.5个“罚分”。 容易看出，$l_{rank}$对应的是ROC曲线上方的面积：若一个正例在ROC曲线上对应标记点的坐标为（x，y），则x恰是排序在这个样本之前的反例所占的比例，即假正例率。因此有：

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

在某些现实任务中，我们会发现，不同类型的错误造成的后果不同。例如在医疗诊断中，将一名癌症患者错误地诊断成健康人士，将一名健康人士错误地诊断为癌症患者，这两种情况要承担的后果是截然不同的：后者仅是增加了进一步检查的麻烦，而前者若上式最佳治疗时机，则要付出生命的代价。

为此，我们为错误赋予非均等代价（unequal cost）来权衡不同类型错误所造成的不同损失。

以二分类任务为例，我们可以为任务设置一个代价矩阵（cost matrix），如下表所示：

其中$cost_{ij}$表示第i类样本错误预测为第j类的代价。一般情况下$cost{ii}=0$这是因为预测正确了，就没有代价了。我们规定，若将第0类判别为第一类的所造成的损失更大，那么就有$cost_{01} > cost_{10}$，损失程度越大则两者相差越大。但这个“相差”不是表示两者之间的差值，表示的是比值，举个例子$cost_{01}:cost_{10}=5:1$的效果和$cost_{01}:cost_{10}=50:10$是相同的。

前面我们考虑的性能度量都是假设在均等代价的情况下，也即是说，以减小错误次数为主，但不考虑不同的错误类型造成的后果的严重程度。而在非均等代价下，我们希望最小化总体代价（total cost）。若设上表中第0类为正类，第1类为反类，令$D^+$和$D^-$分别代表样本集中的正类样本子集和反类样本子集，则代价敏感（cost-sensitive）错误率为：

由此我们可以推出其它性能度量的代价敏感版本，或者是基于分布定义的代价敏感错误率。若$cost_{ij}$中的值不局限于0，1，还可以定义出多分类任务的代价敏感性能度量。

在非均等代价下，我们用代价曲线（cost curve）代替ROC曲线表现学习器的期望总体代价。代价曲线图横轴是取值为[0,1]的正例概率代价：

其中p表示样例为正例的概率。

纵轴是取值为[0,1]的归一化代价：

归一化是规范化（normalization）的特例，规范化表示将不同变化范围的值映射到某相同、固定的范围当中，常见的固定范围是[0,1]，这个时候就是“归一化”。

FPR即之前定义的假正例率，FNR=1-TPR 是假反例率。

代价曲线的绘制方式：

1. ROC曲线上每一点对应代价平面上的一条线段，设ROC曲线上的坐标为（FPR，TPR），计算出相应的FNR
2. 在代价平面上绘制一条从（0，FPR）到（1，FNR）的线段，线段下的买诺记就表示了该条件下的期望总体代价
3. 将ROC曲线上的每个点转化为代价平面上的一条线段，然后取所有线段的下届，围成的面积即为在所有条件下学习器的期望总体代价

如下面的示例图：

比较检验

有了实验评估方法和性能度量之后，我们就可以对学习器的性能进行评估和比较了。但问题是，我们该如和进行这个“比较”呢？

事实上，机器学习中性能比较这件事情是相当复杂的，这里面涉及了几个问题：

1. 我们希望比较泛化性能，但通过实验评估方法我们获得的是不同学习器在测试集上的性能，两者的对比结果未必相同
2. 测试集上的性能和测试集本身也是有相当大的关系的，不仅不同大小的测试集会得到不同的结果，相同大小的测试集若包含的测试样本不同，结果也会不同
3. 有些机器学习算法本身就具有一定的随机性（像随机森林），即便是相同的参数设置在同一个测试集上多次运行，结果也未必相同

这个时候，我们就需要引入统计假设检验（hypothesis test），我们可以由假设检验的结果来推断，如果在测试集上观察到学习器A比B好，则A的性能在统计意义上优于B的可能性有多大。

下面我们将会了解两个最基本的假设检验，然后再介绍几种常用的机器学习性能比较方法。为便于讨论，我们默认错误率为性能度量，符号为$\epsilon$。

假设检验

二项检验

首先我们需要明确，在现实任务中，学习器的泛化错误率和测试错误率未必是相同的。因此，我们用“假设”来表示对学习器泛化错误率分布的某种判断或猜想，例如“$\epsilon=\epsilon_0$”。

但我们也知道，泛化错误率和测试错误率也未必相差的非常远。因此，我们可以根据测试错误率推出泛化错误率的分布：

泛化错误率为$\epsilon$的学习器在一个样本上犯错的概率为$\epsilon$；测试错误率$\hat{\epsilon}$表示在m个测试样本中有$\hat{\epsilon}*m$ 个样本被误分类。假设测试样本是从样本总体分布中独立采样而得，那么泛化错误率为$\epsilon$的学习器将其中 $m'$个样本误分类、其余全部样本分类正确的概率为

由此可以估算出该学习器将$\hat{\epsilon}*m$个样本误分类的概率为

这个式子还表示在m个样本的测试集上，泛化错误率为$\epsilon$的学习器被测得测试错误率为$\hat{\epsilon}$的概率。

给定$\hat{\epsilon}$，求$\frac{\delta P(\hat{\epsilon};\epsilon)}{\delta \epsilon}=0$可得，$P(\hat{\epsilon};\epsilon)$在$\epsilon=\hat{\epsilon}$时最大，$\mid \epsilon - \hat{\epsilon}\mid$增大时$P(\hat{\epsilon};\epsilon)$减小。这个结论符合二项分布，如下图所示，若$\epsilon=0.3$，则10个样本中测得3个被误分类的概率最大。

我们可以用二项检验（binomial test）来对$\epsilon ≤0.3$（表示“泛化错误率是否不大于0.3”）这样的假设进行检验。

更一般的，考虑假设$\epsilon ≤\epsilon_0$，则在$1-α$的概率内所能观测到的最大错误率如下：

1-α 反映了结论的置信度（confidence），它就相当于上图中的非阴影部分的范围。

此时若测试错误率$\hat{\epsilon}$小于临界值$\bar{\epsilon}$，则根据二项检验可得出结论：在α的显著度下，假设$\epsilon≤\epsilon_0$不能被拒绝（即为真？），那么就能以1-α的置信度认为，学习器的泛化错误率不大于$\epsilon_0$;否则认为该假设可被拒绝，即在α的显著度下可认为学习器的泛化错误率大于$\epsilon_0$。

t检验

我们在评估模型时，往往会用到多次留出法或是交叉验证法进行多次训练/测试，这样我们就会有多个测试错误率，此时我们就可以使用t检验（t-test）。假设我们得到k个测试错误率分别为$\hat{\epsilon_1},\hat{\epsilon_2}...\hat{\epsilon_k}$，则平均测试错误率 μ 和方差 $\sigma^2$为：

可以将这k个测试错误率看作泛化错误率$\epsilon_0$的独立采样，则变量

服从自由度为 k-1 的t分布，如图：

对于假设$μ=\epsilon_0$和显著度α，我们可以计算出当错误率均值为$\epsilon_0$时在 1-α 概率内能观测到的最大错误率，即临界值。这里我们考虑双边假设（two-tailed），如上图，两边阴影各有 $\frac{\alpha}{2}$的面积；假设阴影部分范围为$[-\infty,t_{-\frac{\alpha}{2}}]$和$[t_{\frac{\alpha}{2}},+\infty]$，若平均错误率μ 与 $\epsilon_0$之差$\mid μ-\epsilon_0\mid$位于临界值范围$[t_{-\frac{\alpha}{2}},t_{\frac{\alpha}{2}}]$之内，则不能拒绝假设$\\μ=\epsilon_0$，即认为泛化错误率为$\epsilon_0$，置信度为1-α（即认为假设可能成立，可能性为1-α）；否则拒绝该假设，即在该显著度α下认为泛化错误率与$\epsilon_0$有显著差异。

α常用取值有0.05和0.1，常用临界值有：

交叉验证t检验

上面两个检验分别是针对单个学习器单组训练/测试集和单个学习器多组训练/测试集的情况，下面我们来介绍多学习器假设检验的方法。

假设有两个学习器A和B，若使用k折交叉验证得到的测试错误率分别为$\epsilon_1^A,\epsilon_2^A,...,\epsilon^A_k$与$\epsilon^B_1,...,\epsilon^B_k$，其中$\epsilon^A_i$和$\epsilon^B_i$表示在相同的第i折训练/测试集上得到的结果。

对这种情况，我们可以用成对t检验（paired t-tests）来进行比较检验。该检验方式的基本思想就是，如果两个学习器的性能相同，那么它们使用相同的训练/测试集得到的测试错误率应该也相同，即$\epsilon^A_i=\epsilon^B_i$

检验具体步骤如下：

• 首先对每对k折交叉验证产生的错误率求差：$Δ_i=\epsilon^A_i=\epsilon^B_i$；若两学习器性能相同，差值均会为0，由此我们可根据差值Δ来对“学习器A和学习器B相同”这个假设作t检验
• 计算差值$Δ_1,...,Δ_k$的均值 μ 和方差 $σ^2$
• 在显著度α下，若变量

小于临界值$t_{\frac{\alpha}{2},k-1}$，则认为假设无法被拒绝；否则认为两个学习器的性能有显著差别，并认为平均错误率较小的学习器性能较优。（此处$t_{\frac{\alpha}{2},k-1}$是自由度为 k-1 的 t分布上尾部累积分布为 $\frac{\alpha}{2}$的临界值）

要进行有效地假设检验的一个重要前提是测试错误率均为泛化错误率的独立采样，但通常由于样本有限，使用交叉验证等方法时会使得不同轮次训练集有一定重叠，从而导致过高估计假设成立的概率。为解决这一问题，我们引入5x2交叉验证法：

5x2交叉验证实际上就是做5次2折交叉验证，并在每次2折交叉验证前随即将数据打乱，使5次交叉验证中的数据划分结果不重复。

对两个学习器A和B，每次2折交叉验证可产生两对测试错误率，我们对其分别求差，设第i次交叉验证中第1折错误率为$Δ^1_i$第2折错误率为$Δ^2_i$，，为了环节测试错误率的非独立性，我们仅计算第一次2折交叉验证的平均值$μ=0.5(Δ^1_1+Δ^2_1)$，但对每次2折实验结果都计算出方差$\sigma^2_i=(Δ^1_i-\frac{Δ^1_i+Δ^2_i}{2})^2+(Δ^2_i-\frac{Δ^1_i+Δ^2_i}{2})^2$，得到变量：

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

McNemar检验

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

如果A和B性能相同，就有$e_{01}=e_{10}$，由此，变量$\mid e_{01}-e_{10}\mid$服从正态分布，且均值为1，方差为$e_{01}+e_{10}$。

McNemar检验考虑变量

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

Friedman检验和Nemenyi后续检验

交叉验证t检验和McNemar检验都是在一个数据集上比较两个算法的性能。接下来，我们会介绍如何在一组数据集上对多个算法进行比较。

对于多个算法比较，一种做法是在每个数据集上分别列出两两比较的结果，这个比较繁琐，可以直接用前面说讨论过的方法；还有一种方法就比较直接，这种方法便是基于算法排序的Friedman检验。

Friedman检验

假设我们用$D_1\sim D_4$四个数据集对算法 A，B，C 进行比较，步骤如下：

1. 首先使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果
2. 根据测试结果，在每个数据集上对算法进行排序，并赋予序值（编上序号）1，2，…；若算法的测试性能相同，则平分序值。

例如，在$D_1和D_3$上，A最好，B其次，C最差，在$D_2$上，A最好，B、C相同……最终列出下表，其中最后一行是对每一列求平均，得到平均序值：

然后我们就可以使用Friedman检验来判断这些算法性能是否想通了。若相同，他阿门的平均序值也应当相同。

假设我们在N个数据集上比较k个算法，令$r_i$表示第i个算法的平均序值，为简化讨论，我们先不考虑平分序值的情况，则$r_i$的均值和方差分别为$\frac{k+1}{2}$（其实就是1+2+3+…+k再除k）和$\frac{(k^2-1)}{12}$，变量

关于这个部分，均值为所有算法的平均序值之和再平均，方差就是：

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

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

该式中的$\tau_{X^2}$由前面“原始Friedman检验”中的变量式子得到。$\tau_F$服从自由度为k-1和 $(k-1)(N-1)$ 的F分布，下表给出了一些常用临界值：

如果，“所有算法的性能相同”这个假设被拒绝，换句话说，通过Friedman检验我们得知算法之间的性能差异非常显著，那么我们就需要进行后续检验（post-hoc test）来进一步区分算法，常用的方法有Nemenyi后续检验。

Nemenyi后续检验

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

其中$q_\alpha$是Tukey分布的临界值，下表给出了一些α=0.05 和 0.1 时常用的$q_\alpha$值：

如果两个算法的平均序值之差超出临界值域CD，就可以以相应的置信度α拒绝“两个算法性能相同”这一假设。

我们可以以表2.5中的三个算法为例（就是在前面假设的3个算法4个数据集的那个表），先根据Friedman检验中$\tau_{X^2}$和$\tau_F$的表达式计算出$\tau_F=24.429$，再查阅表2.6给出的F检验常用临界值发现，它比α=0.05时的F检验临界值5.143大，由此说明“所有算法性能相同”这个假设成立的可能性很低（或说拒绝该假设）。然后我们使用Nemenyi后续检验，在上表中找到k=3 时对应的$q_{0.05}=2.344$，根据临界值域CD的表达式计算出 CD=1.657 ，由表2.5中的平均序值可知，算法A与算法B的差距，算法B与算法C的差距均没有超过临界值域，而算法A与C的差距超过了临界值域，由此认为A与C的性能显著不同，但A与B，B与C的性能没有显著差别。

我们还可以用Friedman检验图直观地将上述检验比较表示出来：

上图中纵轴显示各个算法，横轴是平均序值，对每个算法，用一个圆点显示其平均序值，以圆点为中心的横线段表示临界值域大小。

由此，当两个算法有交叠时（就像A和B或B和C），就说明这两个算法没有显著差别。

偏差和方差

我们在前面的章节中讨论时，用到过很多次偏差-方差分解（bias-variance decomposition），它是解释学习算法泛化性能的一种重要工具。

偏差-方差分解就是对学习算法的期望泛化错误率进行拆解。

我们知道，算法在不同的训练集上学得的结果很可能不同，即使这些训练集是来自同一个分布。

对测试样本 x ，令$y_D$为x在数据集中的类别标记，$y$为x的真实标记（这么做是因为有可能出现噪声使得$y_D≠y$），$f(x;D)$为训练集D上学得模型$f$在 x 上的预测输出。我们以回归任务为例，学习算法的期望预测为：

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

噪声为

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

为了便于讨论，我们假设噪声期望为0，即$E_D[y_D-y]=0$，通过简单的多项式展开合并，可以得到对算法的期望泛化误差进行分解：

上图中所说的式2.37指$\bar{f}(x)=E_D[f(x;D)]$，至于该tip指的“噪声不依赖于$f$”，个人理解为是指对应的那一项若留到最后需要与噪声的表达式并入同一项，但由于它本身预测值与期望预测值之差与噪声无关，所以其期望值为0 。另外，噪声期望为0不代表噪声为0

于是由上式有

即泛化误差可分解为偏差、方差、噪声之和。

• 偏差度量了学习期望预测与真实值之差的偏离程度，即表现了学习算法本身的拟合能力
• 方差度量了同样大小的额训练集的变动所导致的学习性能的变化程度，即刻画数据扰动对学习造成的影响
• 噪声则表达了在当前任务上人和学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度（换言之，表示了学习器可达到的最小泛化误差）

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

一般情况下，偏差和方差总是有冲突的，这称为偏差-方差窘境（bias-variance dilemma）。如下图：

假定我们有一个能控制训练程度的学习算法（像是决策树可以控制层数，集成学习控制基学习器个数），若训练不足，学习器的拟合能力不够，训练数据扰动不足以使学习器产生显著变化，偏差便会主导泛化错误率；随着训练程度加深，学习器拟合能力加强，训练数据的扰动逐渐被学习器学到，方差便逐渐开始主导泛化错误率；训练程度重组后，学习器的拟合能力非常强，训练数据的轻微扰动都会使学习器发生显著变化，若训练数据自身的、非全局的特性都被学习到了，就成了过拟合。