模型评估与选择

西瓜书第2章学习笔记，别问为什么没有第1章，问就是懒。。。看的我数学恐惧症都要犯了，但还是能感受到数学的魅力；西瓜书本章从学习器的性能评估方法、性能度量、比较检验等方面描述了如何评估和选择学习算法

经验误差与过拟合

基本概念

设有m各样本中有a个样本分类错误，则

错误率(error rate)：

精度(accuracy)：

误差：

• 训练误差(training error)：也叫经验误差(empirical error)，是学习器在训练集上的误差
• 测试误差(testing error)：学习器在测试集上的误差，通常作为泛化误差的近似
• 泛化误差(generalization error)：学习器在新样本上的误差

评估方法

留出法

将数据集D划分为两个互斥的集合，其中一个作为训练集S，另一个作为测试集T，即： 通常我们希望训练集S和测试集T的划分尽可能保持数据分布的一致性，故可以采用分层采样(stratified sampling)；

即使采用了分层采样，也需要注意一个问题，即将样本排序后，每一层级可以将前一部分样本放入训练集，也可以将后一部分样本放入训练集，故单次留出法得到的估计结果不够稳定

在使用留出法时，一般采用若干次随即划分、重复进行实验评估后取平均值作为留出法的评估结果，常见做法是将大约2/3 ~ 4/5的样本用于训练，剩余样本用于测试

交叉验证法

将数据集D划分为k个大小相似的互斥子集，即： 每个子集都尽可能保持数据分布的一致性，即从D中通过分层采样得到

每次用k-1个子集的并集作为训练集，剩下的那个子集作为测试集，这样可以获得k组训练/测试集，可进行k次训练和测试，最终返回k个测试结果的均值

通常把交叉验证法称为k折交叉验证(k-fold cross validation)，k最常用的取值为10，其他还有5、20等

为了减小因样本划分不同而引入的差别，k折交叉验证通常要随机使用不同的划分重复p次，最终的评估结果是这p次k折交叉验证结果的均值，常见的有10次10折交叉验证

设数据集D中包含m个样本，若令k=m，则得到了交叉验证法的一个特例：留一法(Leave-One-Out, LOO)

显然留一法不受随机样本划分方式的影响，因为m个样本只有唯一的方式划分为m个子集；留一法使用的训练集与初始数据集相比只少了一个样本，这使得大多数情况下，留一法中被实际评估的模型与期望评估的用D训练出来的模型很相似，故留一法的评估结果往往被认为比较准确；但当数据集较大时，训练m个模型的计算开销会大到难以忍受，而这还没有考虑调参问题

自助法

自助法(bootstrapping)以自助采样法(bootstrap sampling)为基础，即给定包含m个样本的数据集D，对他采样产生数据集

采样方式：

• 每次随机从D中挑选一个样本，将其拷贝放入，然后再将该样本放回初始数据集D中，使得该样本在下次采样时仍可能被采到
• 这个过程重复执行m次，即可得到包含m个样本的数据集，这就是自助采样的结果

通过自助采样，D在有一部分样本会在中出现多次，而一部分样本不出现，而样本在m次采样中始终不被采到的概率是 取极限可得 没有出现在训练集中的样本用于测试，这样的测试结果称为包外估计(out-of-bag estimate)

自助法在数据集较小、难以有效划分训练/测试集时很有用

在初始数据量足够时，留出法和交叉验证法更常用一些

性能度量

性能度量(performance measure)：衡量模型泛化能力的评价标准

在预测任务中，给定样例集，其中是示例的真实标记，学习器的预测结果为

回归任务最常用的性能度量是均方误差(mean squared error)，即： 更一般的，对于数据分布和概率密度函数，均方误差可描述为：

错误率与精度

适用于二分类任务、多分类任务

对样例集D，分类错误率定义为： 精度定义为： 更一般的，对于数据分布和概率密度函数，错误率描述为： 精度定义为：

查准率、查全率与F1

查准率(precision)通俗来讲，以西瓜为例，即挑出来的瓜中有多少是好瓜

查全率(recall)通俗来讲，同样以西瓜为例，即所有好瓜中有多少被挑了出来

对于二分类问题，根据样例的真实类别与学习器的预测类别可组合划分为真正例(true positive)、假正例(false positive)、真反例(true negative)、假反例(false negative)四种，分别用TP、FP、TN、FN表示，则 则可以得到分类结果的混淆矩阵(confusion matrix)

查准率定义为： 查全率定义为： 以查准率P为纵轴，查全率R为横轴作图，即可得到P-R曲线，显示该曲线的图称为P-R图

当一个学习器的P-R曲线被另一个学习器的曲线完全包住，则认为后者性能优于前者，即图中的A、C曲线中，A的性能优于C；

若两个学习器的P-R曲线有交叉，则取平衡点(Break-Event Point, BEP)的值，认为BEP较大的性能较好，即图中的A、B曲线，A的性能优于B

平衡点是查准率=查全率时的取值

由于BEP过于简化，故更常用F1度量： F1度量的一般形式可以表达对查准率/查全率的不同偏好： 在该式中，度量了查全率对查准率的相对重要性

多混淆矩阵

对于训练/测试过程中得到多个二分类混淆矩阵的情况，可以使用以下几个性能度量方式

先在各混淆矩阵上分别计算出查准率和查全率，记作，再计算平均值，可以得到：

宏查准率(macro-P) 宏查全率(macro-R) 宏F1(macro-F1) 或先将各混淆矩阵的对应元素进行平均，得到TP、FP、TN、FN的平均值，记作，可以进一步得到

微查准率(micro-P) 微查全率(micro-R) 微F1(micro-F1)

ROC与AUC

很多学习器是为测试样本产生一个实值或概率预测，然后将这个预测值与一个分类阈值(threshold)比较，大于阈值则为正类，否则为反类；根据这个实值或预测概率排序，“最可能”的正例排在前面，“最不可能”的正例排在后面；分类过程就相当于在这个排序中以某个截断点(cut point)将样本分为前一部分的正例和后一部分的反例

• 若更重视查准率，则可以选择排序中靠前的位置进行截断
• 若更重视查全率，则可以选择排序中靠后的位置进行截断

故排序本身的质量好坏，体现了综合考虑学习器在不同任务下的期望泛化性能的好坏，或者说一般情况下泛化性能的好坏

ROC全程受试者工作特征(Receiver Operating Characteristic)曲线，先引入两个重要的值：

真正例率(True Positive Rate, TPR) 假正例率(False Positive Rate, FPR) 以真正例率为纵轴，以假正例率为横轴作图，即可得到ROC曲线，显示ROC曲线的图称为ROC图

现实任务中仅能获取有限个(真正例率，假正例率)坐标对，无法产生光滑的ROC曲线，故只能画出近似ROC曲线

近似ROC曲线的绘制过程：

• 给定个正例和个反例，根据学习器预测结果对样例进行排序
• 将分类阈值设为最大，即将所有样例均预测为反例，此时TPR和FPR均为0，即坐标
• 然后将分类阈值依次设为每个样例的预测值，即依次将每个样例划分为正例，设前一个点坐标为，则
  • 当前若为真正例，则点坐标为
  • 当前若为假正例，则点坐标为
• 最后用线段连接相邻点即可

与P-R图类似，若一个学习器的ROC曲线被另一个学习器的曲线完全包住，则后者的性能优于前者；若两个学习器的ROC曲线发生交叉，则要引入接下来的概念，即AUC(Area Under ROC Curve)，也就是ROC曲线下的面积

设ROC曲线是由坐标按序连接形成，则AUC可估算为： 即上图中标有AUC的阴影部分面积

AUC考虑的是样本预测的排序质量，故它和排序误差由紧密联系；给定个正例和个反例，令和分别表示正、反例集合，则排序损失(loss)定义为： 通俗来讲，即考虑每一对正、反例，若正例的预测值小于反例，则记一个“罚分”，若相等则记0.5个“罚分”

若一个正例在ROC曲线上对应点坐标为，则恰好是排序在其之前的反例所占的比例，即假正例率，故有：

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

以二分类任务为例，可根据任务设定一个代价矩阵(cost matrix)

其中表示第i类样本预测为第j类样本的代价；

• 一般来说，；
• 若将第0类判别为第1类所造成的损失更大，则；损失程度相差越大，与值的差别越大

之前所提到的性能度量都默认了均等代价，在非均等代价下，我们希望的是最小化总体代价(total cost)，而不是简单的最小化错误次数

将上表中的第0类作为正类、第1类作为反类，令与分别代表样例集D的正例子集和反例子集，则代价敏感(cost-sensitive)错误率为： 类似的，可以给出基于分布定义的代价敏感错误率，以及其他一些性能度量的代价敏感版本，若令中的i、j取值不限于0、1，则可以定义出多分类任务的代价敏感性能度量

在非均等代价下，ROC曲线不能直接反应学习器的期望总体代价，而代价曲线(cost curve)则可以达到目的

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

纵轴是取值为[0,1]的归一化代价 其中FPR是式(23)中定义的假正例率，是假反例率

代价曲线的绘制过程：

• 设ROC曲线上点坐标为，则可以计算出
• 然后在代价平面上绘制一条从到的线段，线段下的面积即表示了该条件下的期望总体代价
• 重复上述过程，将ROC曲线上的每个点转化为代价平面上的一条线段，然后取所有线段的下界，围成的面积即为在所有条件下学习器的期望总体代价

比较检验

对学习器进行性能比较的重要依据是统计假设检验(hypothesis test)，基于假设检验结果可以推断出，若测试集上观察到学习器A比B好，则A的泛化性能是否在统计意义上优于B，以及这个结果的把握有多大

假设检验

假设检验中的“假设”是对学习器泛化错误率分布的某种判断或猜想，我们只能得知其测试错误率，泛化错误率与测试错误率未必相同，但直观上二者接近的可能性较大，故可以根据测试错误率估推出泛化错误率的分布

二项检验

泛化错误率为的学习器在一个样本上犯错的概率是；测试错误率意味着在m个测试样本中恰有个被误分类

假设测试样本是从样本总体分布中独立采样而得，则泛化错误率为的学习器将其中个样本误分类、其余样本均分类正确的概率是；由此可估算出其将个样本误分类的概率为： 上式还表达了在包含m个样本的测试集上，泛化错误率为的学习器被测得测试错误率为的概率

给定测试错误率，则解可知，在时最大，增大时减小，这符合二项(binomial)分布

上图以为例，我们可以使用二项检验(binomial test)对(即泛化错误率不大于0.3)这样的假设进行检验

更一般的，考虑假设，则在的概率内所能观测到的最大错误率为： 这里的反映了结论的置信度(confidence)，相应于上图中的非阴影部分

此时若测试错误率小于临界值，则根据二项检验可得出结论：

• 在的显著度下，假设不能被拒绝，即能以的置信度认为，学习器的泛化错误率不大于
• 否则该假设可被拒绝，即在的显著度下，可认为学习器的泛化错误率大于

t检验

通常我们会进行多次训练/测试，会得到多个测试错误率，此时可以使用t检验(t-test)；假设我们得到了k个测试错误率，则平均测试错误率和方差为： 考虑到这k个测试错误率可看作泛化错误率的独立采样，则变量 服从自由度为k-1的t分布，下图以k=10为例

对假设和显著度，可以计算出当测试错误率均值为时，在概率内能观测到的最大错误率，即临界值

这里考虑双边(two-tailed)假设，如上图所示，两边阴影部分各有的面积；假设阴影部分范围分别为和：

• 若平均错误率与之差位于临界值范围内，则不能拒绝假设，即可认为泛化错误率为，置信度为
• 否则可拒绝该假设，即在该显著度下可认为泛化错误率与有显著不同

常用取值有0.05和0.1，下面给出一些常用临界值

以上两种方法都是针对单个学习器泛化性能的假设进行检验，下面介绍适用于对不同学习器的性能比较的假设检验方法

交叉验证t检验

对两个学习器A、B，若使用k折交叉验证法得到的测试错误率分别为和，其中和是在相同的第折训练/测试集上得到的结果，则可用k折交叉验证成对t检验(paired t-tests)来进行比较检验

若两个学习器的性能相同，则它们使用相同的训练/测试集得到的测试错误率应相同，即

对k折交叉验证产生的k对测试错误率，先对每对结果求差，，根据差值对“学习器A与B性能相同”这个假设做t检验，计算出差值的均值与方差，在显著度下，有变量：

• 若变量小于临界值，则假设不能被拒绝，即认为两个学习器的性能没有显著差别
• 否则可认为两个学习器的性能有显著差别，且平均错误率较小的那个学习器性能较优

这里的是自由度为k-1的t分布上尾部累积分布为的临界值

有效的假设检验是建立在测试错误率均为泛化错误率的独立采样之上的，然而通常样本有限，在使用交叉验证等实验估计方法时，不同轮次的训练集会有一定程度的重叠，这使得测试错误率实际上并不独立，会导致过高估计假设成立的概率

可采用5×2交叉验证法解决上述问题，即做5次2折交叉验证，在每次2折交叉验证之前随机将数据打乱，使得5次交叉验证中的数据划分不重复

对两个学习器A、B，第i次2折交叉验证将产生两对测试错误率，对它们分别求差，分别得到第1、2折上的差值；为了缓解测试错误率的非独立性，仅计算第1次2折交叉验证的两个结果的平均值，但对每次2折实验的结果都计算出其方差，变量 服从自由度为5的t分布，其双边检验的临界值当时为2.5706，时为2.0150

McNemar检验

对二分类任务，使用留出法不仅可估计出学习器A、B的测试错误率，还可获得两学习器分类结果的差异，即两者都正确、都错误、一个正确一个错误的样本数，如下列联表(contingency table)所示

若做假设“两学习器性能相同”，则应有，那么变量应当服从正态分布，且均值为1，方差为，故变量 服从自由度为1的分布(卡方分布)，即标准正态分布变量的平方，给定显著度

• 当变量小于临界值时，不能拒绝该假设，即认为两学习器的性能没有显著差别
• 否则拒绝假设，即认为两者性能有显著差别，且平均错误率较小的学习器性能较优

自由度为1的检验的临界值当时为3.8415，时为2.7055

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

Friedman检验与Nemenyi后续检验

当有多个算法参与比较时，一种做法是在每个数据集上分别列出两两比较的结果，在两两比较时可以采用前面的两种方法；另一种方法比较直接，即使用基于算法排序的Friedman检验

假设用四个数据集对算法A、B、C进行比较；首先用留出法或交叉验证法得到每个算法在每个数据集上的测试结果，然后再每个数据集上根据测试性能由好到坏排序，并赋予序值1，2，……；若算法的测试性能相同则平分序值；再求出同一个算法在不同数据集下的平均序值；以下列算法比较序值表为例

平分序值指的是，如在上表的数据集中，算法A的性能最好，算法B、C的性能相同

使用Friedman检验判断这些算法的性能是否相同；若相同，则它们的平均序值应当相同

假设在N个数据集上比较k个算法，令表示第i个算法的平均序值，以下讨论暂不考虑平分序值的情况，则服从正态分布，其均值和方差分别为和，则变量： 在k和N都较大时，服从自由度为k-1的分布

但上述的原始Friedman检验过于保守，现在通常使用变量： 其中由式(37)定义，服从自由度为和的F分布，下面给出一些常用的临界值

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

Nemenyi检验计算出平均序值差别的临界值域： 这里给出一些和时常用的值

若两个算法的平均序值之差超出了临界值域，则以相应的置信度拒绝“两个算法性能相同”这一假设

上述检验比较可以直观地用Friedman检验图显示；可以根据算法比较序值表绘制出Friedman检验图

上图中纵轴显示各个算法，横轴是平均序值；对每个算法，用一个圆点显示其平均序值，以圆点为中心的横线段表示临界值域的大小；若两个算法的横线段有交叠，则两个算法没有显著差别，否则说明它们有显著差别

偏差与方差

偏差-方差分解(bias-variance decomposition)是解释学习算法泛化性能的一种重要工具，即解释了为什么学习算法有这样的泛化性能

偏差-方差分解试图对学习算法的期望泛化错误率进行拆解；算法在不同训练集上学得的结果很可能不同，即便这些训练集来自同一个分布

对测试样本，令为在数据集中的标记，为的真实标记，为训练集上学得模型在上的预测输出；以回归任务为例，学习算法的期望预测为： 使用样本数相同的不同训练集产生的方差为： 噪声为： 期望输出与真实标记的差别称为偏差(bias)，即： 为便于讨论，假设噪声期望为零，即，通过多项式展开合并，可对算法的期望泛化误差进行分解(具体推导过程参考西瓜书45页)，最后可得： 也就是说，泛化误差可以分解为偏差、方差与噪声之和

偏差、方差、噪声的含义

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

偏差-方差分解说明，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的

对于给定的学习任务，为了取得更好的泛化性能，应

• 使偏差较小，即能够充分拟合数据
• 使方差较小，即使数据扰动产生的影响小

一般来说，偏差与方差是有冲突的，称为偏差-方差窘境(bias-variance dilemma)

上图体现了，给定学习任务，控制学习算法的训练程度

• 训练不足时，学习器拟合能力不够强，训练数据的扰动不足以使学习器产生显著变化，此时偏差主导泛化错误率
• 随着训练程度加深，学习器拟合能力逐渐增强，训练数据发生的扰动渐渐能被学习器学到，方差逐渐主导了泛化错误率
• 在训练充足后，学习器的拟合能力已经非常强了，训练数据发生轻微的扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合