误差与过拟合

误差

假设m个样本中有a个样本分类错误

  • 错误率(error rate):分类错误的样本数占样本总数的比例,E=a/m
  • 精度(accuracy):分类正确的样本数占样本总数的比例,1-a/m
  • 精度=1-错误率
  • 误差(error):学习器的实际预测输出与样本的真实输出之间的差异
  • 学习器在训练集上的误差称为训练误差(training error)/经验误差(empirical error)
  • 学习器在新样本上的误差称为泛化误差(generalization error)
  • 机器学习的目标是得到泛化误差小的学习器,但是实际能做的是努力使经验误差最小化

过拟合与欠拟合

当学习器把训练样本学得太好的时候,很可能已经把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质,这样就会导致泛化性能下降。这种现象在机器学习中称为过拟合(overfitting)。与过拟合相对的是欠拟合(underfitting),这是指对训练样本的一般性质尚未学好。

  • 过拟合是机器学习中的关键障碍

评估方法

通常,通过实验测试来对学习器的泛化误差进行评估。为此,需使用一个测试集(testing set)来测试学习器对新样本的判别能力,然后以测试集上的测试误差(testing error)作为泛化误差的近似。

  • 通常我们假设测试样本也是从样本真实分布中独立同分布采样而得
  • 测试集应该尽可能与训练集互斥
  • 验证集(validation set)指用于评估模型的不包含在训练样本与测试样本的其他真实数据

评估方法即通过适当的处理,从包含m个样例的数据集D中产生出训练集S和测试集T

留出法(hold-out)

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

  • 划分过程中需要采取均匀的分层取样(stratified sampling)
  • 一般单次留出法往往不可靠,需要反复多次进行留出法产生不同的训练集与测试集,对评估结果取均值
  • 常见的分法是训练集占总数据集的2/3~4/5

交叉验证法(cross validation)

交叉验证法(cross validation)先将数据集D划分为k个大小相似的互斥子集,即 D=D1 U D2 U … U Dn,Di ∩ Dj = (i≠j)。每个子集都尽可能保持数据分布的一致性,即通过分层采样得到。每次用 k-1 个子集的并集作为训练集,余下的那个子集作为测试集。这样就可获得 k 组训练测试集,从而可进行 k 次训练和测试,最终返回的是这 k 个测试结果的均值。

  • 通常把交叉验证法称为k**折交叉验证**(k-fold cross validation)。k最常用的取值是10,此时称为10折交叉验证
  • k折交叉验证通常也要随机使用不同的划分重复p次,最终会得到p×k次结果并取均值

留一法(Leave-One-Out,LOO)

假定数据集D中包含m个样本,当k=m,则得到了交叉验证法的一个特例:留一法(Leave-One-Out,LOO)

  • 在绝大多数情况下,留一法中被实际评估的模型与期望评估的用D训练出的模型很相似。因此,留一法的评估结果往往被认为比较准确
  • 缺点:在数据集比较大时运算量无法接受

自助法(bootstrapping)

自助法(bootstrapping)直接以自助采样法(bootstrap sampling)为基础。

给定包含m个样本的数据集D,我们对它进行采样产生数据集D’。每次随机从D中挑选一个样本,将其拷贝放入D′,然后再将该样本放回初始数据集D中,使得该样本在下次采样时仍有可能被到。这个过程重复执行m次后,我们就得到了包含m个样本的数据集D’,即自助采样的结果。

D中有一部分样本会在D’中多次出现,而另一部分样本不出现。可以做一个简单的估计,样本在m次采样中始终不被采到的概率是(1-1/m)^m,取极限得到

即通过自助采样,初始数据集D中约有36.8%的样本未出现在采样数据集D中。于是可将D’用作训练集,D\D’用作测试集。这样,实际评估的模型与期望评估的模型都使用m个训练样本,而我们仍有数据总量约1/3的、没在训练集中出现的样本用于测试这样的测试结果,亦称包外估计(out-of-bag-estimate)

  • 自助法在数据集较小、难以有效划分训练/测试集时很有用
  • 在初始数据量足够时,留出法和交叉验证法更常用一些

调参(parameter tuning)

  • 在进行模型评估与选择时,除了要对适用学习算法进行选择,还需对算法参数进行设定,这就是通常所说的参数调节/调参(parameter tuning)
  • 实际操作中一般会对每个参数选定一个范围或者步长
  • 在研究对比不同算法的泛化性能时,用测试集上的判别效果来估计模型在实际使用时的泛化能力,而把训练数据另外划分为训练集和验证集,基于验证集上的性能来进行模型选择和调参

性能度量

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

给定样例集 D={(x1,y1), (x2,y2), …, (xm,ym)},其中的 yi 是 xi 的真实标记,评估学习器 f 的性能,即比较 f(xi) 与 yi

均方误差

均方误差(mean squared error):回归任务最常用

对于数据分布D和概率密度函数p(·),均方误差为:

错误率与精度

错误率与精度适用于分类任务

  • 错误率(error rate)
    对于数据分布D和概率密度函数p(·),误差为:
  • 精度(accuracy)
    对于数据分布D和概率密度函数p(·),精度为:

查准率、查全率与F1

查准率(precision)又称精确度,二分类(0,1分类)中,代表预测为1的所有结果中,预测正确的比例。

查全率(recall)又称召回率,二分类(0,1分类)中,代表真实情况为1的所有样本中,预测结果同样为1的比例

对于二分类问题,可以将真实情况与预测情况组合为如下四种:真正例(true positive)、假正例(false positive)、真反例(true negative)、假反例(false negative)四种情形,令TP、FP、TN、FN分别表示其对应的样例数,则显然有TP+FP+TN+FN=样例总数。分类结果的混淆矩阵(confusion matrix)如下

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

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

PR曲线与PR图

在很多情形下,可根据学习器的预测结果对样例进行排序,排在前面的是学习器认为最可能是正例的样本,排在最后的则是学习器认为最不可能是正例的样本。(或者理解为,对分类结果是否更加被认为是正例给定一个概率,0-1,按照该概率从高到低排序,确定一个阈值(threshold)来控制正例与反例的划分)。按此顺序逐个把样本作为正例进行预测,则每次可以计算出当前的查全率、查准率。以查准率为纵轴、查全率为横轴作图,就得到了査准率-查全率曲线,简称PR曲线,该曲线的图称为PR图

  • 如果有曲线完全包住了另一条曲线,如A包住了C,则A比C优秀
  • 如果两条曲线有交叉,如A和B
    • 比较各自曲线下的包裹面积,面积大的优于面积小的
    • 使用平衡点比较:平衡点(Break-Event Point,BEP)为查准率=查全率时对应的取值,该值大的优于小的。如A优于B

由于平衡的BEP过于简化,更常用Fβ度量

  • F1度量:
    其实F1是基于查准率与查全率的调和平均(harmonic mean)定义的:
  • Fβ度量:当对查准率和查全率的重视程度不同时可以调节β的值体现这一差异:
    其实Fβ是基于查准率与查全率的加权调和平均(harmonic mean)定义的:

与算术平均和几何平均相比,调和平均更重视较小值

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

多个二分类混淆矩阵下的查准率、查全率与F1

当对一个二分类问题多次重复训练得到多个二分类混淆矩阵,或者当对多分类任务下,两两类别组合都对应一个二分零混淆矩阵等情况时,需要在n个二分类混淆矩阵上计算查准率、查全率与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))曲线,和PR曲线意义相似,横纵坐标表示不同,ROC横轴为假正例率(False Positive Rate,FPR),纵轴是真正例率(True Positive Rate,TPR)

  • ROC图中,对角线对应于随机猜想模型,而点(0,1)对应将所有正例排在所有反例之前的理想模型
  • 现实任务中,根据学习器预测结果对样例进行排序,先把分类阈值设为最大,即把所有样例均预测为反例,此时真正例率和假正例率均为0,在坐标(0,0)处标记一个点;然后,将分类阈值依次设为每个样例的预测值,分别计算真正例率和假正例率,然后画点
  • 若一条ROC曲线能够完全包裹另一条ROC曲线,则前者优于后者
  • AUC(Area Under ROC Curve)即ROC曲线下包裹的面积,面积大的一般为优

图b中有限样例绘制的ROC曲线计算AUC即:

给定m+个正例,m-个反例时,排序损失(rank loss)定义为:

即考虑每一对正、反例,若正例的预测值小于反例,则记一个罚分,若相等,则记0.5个罚分。lrank对应的是ROC曲线之上的面积,因此有:

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

非均等代价(unequal cost),权衡不同类型错误所造成的不同损失

代价矩阵(cost matrix)比较所有分类的两两比较中,相对的损失大小,costij表示i对j类造成的损失大小。一般costii=0,costij>costji表示i对j损失更大

非均等代价下希望得到最小化的总体代价(total cost),例如m个样例的D集中,D+和D-分别表示正例集和反例集,则代价敏感(cost-sensitive)错误率为:

代价曲线(cost curve)可以反应学习器的期望总体代价。

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

纵轴是取值为[0,1]的归一化代价,其中FPR为假正例率,FNR=1-TPR是假反利率

代价曲线的绘制:ROC曲线上每一点对应了代价平面上的一条线段,设ROC曲线上点的坐标为(TPR,FPR),则可相应计算出FNR,然后在代价平面上绘制条从(0,FPR)到(1,FNR)的线段,线段下的面积即表示了该条件下的期望总体代价;将ROC曲线上的每个点转化为代价平面上的一条线段,然后取所有线段的下界,围成的面积即为在所有条件下学习器的期望总体代价

比较检验

比较检验即确定多个学习器之间的关系,孰强孰弱。

假设检验

统计假设检(hypothesis test)为进行学习器性能比较提供了重要依据。基于假设检验结果可推断出,若在测试集上观察到学习器A比B好,则A的泛化性能是否在统计意义上优于B,以及这个结论的把握有多大。如果二者接近的可能性比较大,则可以根据测试错误率推出泛化错误率(即检验“测试错误率和泛化错误率相等”此假设在多大的置信区域内是成立的)

常用的假设检验方法

  • 二项检验(binomial test):对于验证假设“泛化错误率<=给定错误率(一般是测试错误率)”此假设能否被拒绝
  • t检验(t-test):对于多次留出法得到的测试错误率做估计
  • 交叉验证t检验
    • 对于k折交叉验证法得到的测试错误率使用成对t检验(paired t-tests)
    • 由于进行有效的假设检验的重要前提是测试错误率均为泛化错误率的独立采样。然而,通常情况下由于样本有限,在使用交叉验证等实验估计方法时不同轮次的训练集会有一定程度的重叠。为缓解这一问题,可采用 5×2交叉验证

McNemar 检验

McNemar检验用于对二分类问题,使用留出法估计学习器的测试错误率的情况。

二分类问题下的留出法可获得两学习器分类结果的差别,即两者都正确、都错误、一个正确另一个错误的样本数,得到一个列联表(contingency table)

若假设“两个学习器的性能相同”,则应有 e01=e10,从而 |e01-e10| 应服从正态分布,且均值为1,方差为 e10+e01。从而变量

服从自由度为1的卡方分布,即标准正态分布变量的平方,给定显著度α可以做假设检验

Friedman 检验 与 Nemenyi 后续检验

交叉验证t检验和McNemar检验都是在一个数据集上比较两个算法的性能。当在一组数据集上对多个算法进行比较时,一种做法是在每个数据集上分别列出两两比较的结果,在两两比较时可使用以上方法;另一种方法是使用基于算法排序的 Friedman 检验。

Friedman 检验可以判断“所有算法的性能相同”此假设是否可以被拒绝,如果不可以,则需要进行后续检验(post-hoc test)进一步区分算法,常用Nemenyi后续检验。

Friedman检验图可以直观地展示检验结果,其纵轴是各个算法,横轴为平均序值。对每个算法,用一个圆点显示其平均序值,以圆点为中心的横线段表示临界值域的大小。若两个算法的横线段有交叠,则说明这两个算法没有显著差别,否则即说明有显著差别。

偏差与方差

偏差-方差分解(bias-variance decomposition)试图对学习算法的期望泛化错误率进行拆解,是解释学习算法泛化性能的重要工具。

对测试样本x,令yD为x在数据集中的标记,y为x的真是标记,f(x;D)为训练集D上学得模型f在x上的预测输出,在回归任务中

学习算法的期望预测为:

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

噪声为:

期望输出与真实标记的差别称为偏差(bias):

在假定噪声期望为零的情况下,有:

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

推导过程:

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

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

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

全文参考:周志华 著 《机器学习》