2.1 误差
训练误差(training error) / 经验误差(empirical error):学习器在训练集上的误差
泛化误差(generalization error):学习器在新样本上的误差
过拟合(overfitting):把训练样本自身的一些特点当做一般性质 -> 只能缓解
欠拟合(underfitting):对训练样本的一般性质尚未学好 -> 可以解决
测试集(testing set):尽可能与训练集互斥,将模型在测试集上的测试误差(testing error)作为泛化误差的近似
2.2 取样方法
- 留出法(hold-out):直接将数据集D划分为两个互斥的训练集S和测试集T
- 划分要尽可能保持数据分布的一致性,即保证S,T中样本类别的比例差别不大
- 单次使用留出法的估计不稳定可靠:若干次随机划分后取平均值
- T太大降低评估结果的保真性,T太小降低评估结果的准确性:选择65%~80%的样本用于训练,剩余用于测试
- k折交叉验证法(k-fold cross validation)
- 先将数据集D划分为k个大小相似的互斥子集,每个子集尽量保持数据分布的一致性
- 然后第k次测试用第k个子集作为测试集,余下子集的并集作为训练集,这样可以得到k个测试结果
- 取平均得到最终结果
- 自助法(bootstrapping):假设数据集大小为m,进行m次有放回采样,最终得到一个大小为m的数据集D’作为训练集,然后将D\D’作为测试集
- 当m充分大的时候,单个样本在m次采样中始终不被采到的概率约等于36.8%
- 适用于数据集较小或难以有效划分数据集的情况
- 训练集规模和数据集规模相同,减少规模不同造成的影响,进行高效地估计
2.3 评估方法
2.3.1 错误率和精度
- 均方误差(Mean Squared Error,MSE):度量误差的大小
离散:E(f;D)=m1i=1∑m(f(xi)−yi)2连续:E(f;D)=∫x∼D(f(x)−y)2p(x)dx
- 错误率(error rate):错误分类的比例
离散:E(f;D)=m1i=1∑mI(f(xi)=yi)连续:E(f;D)=∫x∼DI(f(xi)=yi)p(x)dx
- 精度(accuracy):正确分类的比例
离散:acc(f;D)=m1i=1∑mI(f(xi)=yi)=1−E(f;D)连续:acc(f;D)=∫x∼DI(f(xi)=yi)p(x)dx=1−E(f;D)
2.3.2 查准率,查全率和F1
- 分类结果的混淆矩阵
- 查准率/精确度(precision):在所有预测为正类的样本中,实际为正类的比例,适用于误判代价高的情况
Precision=TP+FPTP
- 查全率/召回率(recall):在所有实际为正类的样本中,被模型正确预测为正类的比例,适用于漏判代价高的情况
Recall=TP+FNTP
> 查准率和查全率是一对矛盾的度量。例如,有一摊西瓜:
> 希望将尽可能多的好瓜挑出来,则挑选的次数会变多,挑选到的坏瓜也会变多,导致查准率下降;
> 希望挑选到的瓜中好瓜尽可能多,则只挑选有把握的瓜,难免会遗漏很多看似不好的好瓜,导致查全率下降
- P-R曲线:设置不同的阈值来界定预测值,从而得到不同的查准率和查全率,以查准率作为纵轴,查全率作为横轴
- 外包:若一个学习器的P-R曲线包住另一个学习器的P-R曲线,则可断言前者的性能优于后者
- 相交:若两个学习器的P-R曲线有交点,则可以根据曲线包围的面积来比较性能
- 平衡点(Break-Even Point,BEP):查准率=查全率时的取值,平衡点越大性能越好
- F1度量:基于查准率和查全率的调和平均
F1=P+R2×P×R=样例总数+TP−TN2×TP
- F~β~度量:表达了对查准率和查全率不同的偏好,β>1时侧重于查全率,β<1时侧重于查准率,β=1时退化为F1
Fβ=(β2×P)+R(1+β2)×P×R
- 宏:先在各个混淆矩阵上分别计算得到P和R,然后加起来再计算平均值
macro-P=n1i=1∑nPimacro-R=n1i=1∑nRimacro-F1=macro-P+macro-R2×macro-P×macro-R
- 微:先将各个混淆矩阵对应元素加起来得到平均值,然后再计算P和R
micro-P=TP+FPTPmicro-R=TP+FNTPmicro-F1=micro-P+micro-R2×micro-P×micro-R
2.3.3 ROC和AUC
类别 | 预测为正 | 预测为负 |
---|
真实为正 | 真正例TP | 假反例FN |
真实为负 | 假正例FP | 真反例NP |
- 真正例率:在所有实际为正类的样本中,被模型正确预测为正类的比例
TPR=TP+FNTP
- 假正例率:在所有实际为负类的样本中,被模型正确预测为正类的比例
FPR=TN+FPFP
- “受试者工作特征”曲线(Receiver Opearating Characteristic,ROC):TPR越大,FPR越小,模型分类效果越好
- 根据学习器的预测结果对样例进行排序,假设实际上有m^+^个正例和m^-^个负例
- 先把分类阈值设为最大,此时全部样例均预测为负类,可以标记点(0,0)
- 然后将分类阈值依次设为每个样例的预测值,每次得到FPR和TPR分别作为横轴和纵轴,令前一个标记点的坐标为(x,y):
- 若当前标记点是真正例,则坐标为(x,y+m+1)
- 若当前标记点是假正例,则坐标为(x+m−1,y)
ROC适用于评估分类器的整体性能,不受类别分布改变的影响
PR完全聚焦于正例,与类别分布相关
- ROC曲线下面积(Area Under ROC Curve,AUC):判断模型分类性能的优劣
- AUC=1:完美分类器,存在至少一个阈值能得出完美预测
- 0.5<AUC<1:可以妥善设定阈值,具有预测价值
- AUC=0.5:相当于随机猜测,没有任何预测价值
- AUC<0.5:比随机预测还要差劲,但是可以尝试取预测的相反结果
AUC=21i=1∑m−1(xi+1−xi)(yi+yi+1)
5. 排序损失:理想情况下,真正为正类而被预测为正类的概率值应该最大,排序应该靠前,因此ROC应该先竖直上升到(0,1),再水平向右到(1,1),面积为1。然而实际应用中,一些负类的概率值会比正类还大,造成ROC中途水平向右产生波折,导致面积小于1
lrank=x+∈D+∑m+1x−∈D−∑m−1(I(f(x+)<f(x−))+21I(f(x+)=f(x−)))=1−AUC
- 求和每一次右移产生的损失矩形的面积
- 特殊情况:负类和正类的预测概率值一样,此时ROC曲线既会竖直向上也会水平向右,产生一个斜线,面积是矩形的一半即三角形
2.3.4 代价
非均等代价(unequal cost):将正类识别为负类和将负类识别为正类,具有不同的代价
代价矩阵:这里0是正类,1是负类,cost~ij~表示把i识别为j的代价值
代价敏感错误率(cost-sensitive):针对不同类别分类错误带来不同后果的情况下的评估指标(假设有m个数据)
E(f;D;cost)=m1(xi∈D+∑I(f(xi)=yi)×cost01+xi∈D−∑I(f(xi)=yi)×cost10)
代价曲线(cost curve):取ROC曲线上每一点得到(0,FPR)到(1,FNR)的一条线段,线段下的面积表示了该条件下的期望总体代价,取所有线段的下界为围城的图形面积就是学习器的期望总体代价
横轴:正例概率代价P(+)cost=p×cost01+(1−p)×cost10p×cost01纵轴:归一化代价costnorm=p×cost01+(1−p)×cost10FNR×p×cost01+FPR×(1−p)×cost10
2.4 比较检验
2.4.1 假设检验
单次留出法:泛化错误率ϵ等于测试错误率ϵ^的概率符合二项分布,当且仅当ϵ^=ϵ时P(ϵ^;ϵ)最大(m是样本总数)
P(ϵ^;ϵ)=(ϵ^×mm)ϵϵ^×m(1−ϵ)m−ϵ^×m
置信度(confidence):假设“ϵ≤ϵ0”。当且仅当ϵ≤ϵˉ,能以1−α的置信度认为泛化错误率不大于ϵ0;否则拒绝该假设,即在α的显著度下可认为学习器的泛化错误率大于ϵ0
ϵˉ=minϵs.t.i=ϵ0×m+1∑m(im)ϵi(1−ϵ)m−i<α
多次重复留出法:测试k次,得到k个测试错误率ϵ^1,ϵ^2,...,ϵ^k
μ=k1i=1∑k(ϵ^i)σ=k−11i=1∑k(ϵ^i−μ)2
置信度:τt服从自由度为k-1的t分布,对假设“μ=ϵ”。当且仅当τt位于临界值范围[t−α/2,tα/2]之内,能以1−α的置信度认为泛化错误率等于μ;否则拒绝该假设,即在α的显著度下认为学习器的泛化错误率不等于μ
τt=σk(μ−ϵ)
2.4.2 交叉验证t检验
成对t检验:判断两个学习期的性能是否相同
1. 对两个学习器A和B,将样本分成k折,得到测试错误率分别为ϵ1A,ϵ2A,...,ϵkA和ϵ1B,ϵ2B,...,ϵkB
2. 相减得到差值Δ1,Δ2,...,Δk
3. 计算均值μ和方差σ
置信度:对假设“A性能与B性能没有差异”。若τt<ta/2,k−1,则可以以1−α的置信度认为两个学习器的性能没有显著差异;否则在α的显著度下认为两个学习器性能具有显著差异
τt=∣σkμ∣
5×2交叉检验:做5次2折交叉验证,每次2折之前随机将数据打乱,使得5次交叉验证中的数据划分不重复,其中仅计算第1次的平均值,但对每次都计算出方差
μ=21(Δ11+Δ12)σi2=(Δi1−2Δi1+Δi2)2+(Δi2−2Δi1+Δi2)2
置信度:同上,服从自由度为5的t分布
τt=51∑i=15σi2μa=0.05,ta/2,5=2.5706a=0.1,ta/2,5=2.0150
2.4.3 McNemar检验
列联表(contingency table):获得两学习器分类结果的差别,若两学习器性能相同,则应该有e01=e10,那么变量∣e01−e10∣就应该服从正态分布
置信度:变量τχ服从自由度为1的χ2分布。假设“两学习器性能相同”。若τχ<χα2,则可以以1−α的置信度认为两个学习器的性能没有显著差异;否则在α的显著度下认为两个学习器性能具有显著差异
τχ=e01+e10(∣e01−e10∣−1)2a=0.05,ta/2,5=3.8415a=0.1,ta/2,5=2.7055
2.4.4 Friedman检验与Nemenyi后续检验
算法比较序值表:在每个数据集上根据测试性能将算法由好到坏排序,并赋予序值1,2,3,…若性能相同则平分序值
Friedman检验:假设在N个数据集上比较k个算法,令ri表示第i个算法的平均序值,则ri的均值和方差分别为(k+1)/2和(k2−1)/12N
- 变量τχ2:服从自由度为k-1的χ2分布
τχ2=k(k+1)12N(i=1∑kri2−4k(k+1)2)
- 变量τF2:服从自由度为k-1和(k-1)(N-1)的F分布
τF=N(k−1)−τχ2(N−1)τχ2
Nemenyi后续检验(post-hoc):如果假设“所有算法的性能相同”被拒绝,说明算法的性能显著不同,需要进行后续检验来进一步区分各个算法,可以计算出平均序值差别的临界值域(critical domain)
CD=qα6Nk(k+1)
Friedman检验图:纵轴显示各个算法,横轴是平均序值,圆点是算法对应平均序值,横线段时临界值域,若临界值域在竖直方向上有交叠,表示两个算法没有显著差别
2.5 泛化误差
泛化误差 = 偏差 + 方差 + 噪声
类别 | 度量 | 刻画 |
---|
偏差(bias) | 学习算法的期望预测与真实结果的偏离程度 | 学习算法本身的拟合能力 |
方差(variance) | 同样大小的训练集的变动所导致的学习性能变化程度 | 数据扰动造成的影响 |
噪声(noise) | 当前任务上任何学习算法所能达到的期望泛化误差的下界 | 刻画了学习问题本身的难度 |
令y是真实标记,yD是数据集中标记,x是测试样本f(x;D)是在数据集D上学到的模型在x上的输出,fˉ(x)是模型的期望预测输出⎩⎨⎧偏差bias2(x)=(fˉ(x)−y)2方差var(x)=ED[(f(x;D)−fˉ(x))2]噪声ϵ2=ED[(yD−y)2]期望泛化误差E(f;D)=bias2(x)+var(x)+ϵ2
偏差-方差窘境(bias-variance dilemma)
时期 | 主导 | 表现 |
---|
初期 | 偏差 | 训练不足,拟合能力很弱,欠拟合 |
中期 | 偏差和方差相当 | 训练加深,拟合能力增加,存在极值点 |
末期 | 方差 | 训练充足,拟合能力饱和,过拟合 |