2.1 误差

训练误差(training error) / 经验误差(empirical error)：学习器在训练集上的误差

泛化误差(generalization error)：学习器在新样本上的误差

过拟合(overfitting)：把训练样本自身的一些特点当做一般性质 -> 只能缓解

欠拟合(underfitting)：对训练样本的一般性质尚未学好 -> 可以解决

测试集(testing set)：尽可能与训练集互斥，将模型在测试集上的测试误差(testing error)作为泛化误差的近似

2.2 取样方法

  1. 留出法(hold-out)：直接将数据集D划分为两个互斥的训练集S和测试集T
    • 划分要尽可能保持数据分布的一致性，即保证S,T中样本类别的比例差别不大
    • 单次使用留出法的估计不稳定可靠：若干次随机划分后取平均值
    • T太大降低评估结果的保真性，T太小降低评估结果的准确性：选择65%~80%的样本用于训练，剩余用于测试
       
  2. k折交叉验证法(k-fold cross validation)
    1. 先将数据集D划分为k个大小相似的互斥子集，每个子集尽量保持数据分布的一致性
    2. 然后第k次测试用第k个子集作为测试集，余下子集的并集作为训练集，这样可以得到k个测试结果
    3. 取平均得到最终结果

       
  3. 自助法(bootstrapping)：假设数据集大小为m，进行m次有放回采样，最终得到一个大小为m的数据集D’作为训练集，然后将D\D’作为测试集
    • 当m充分大的时候，单个样本在m次采样中始终不被采到的概率约等于36.8%
    • 适用于数据集较小或难以有效划分数据集的情况
    • 训练集规模和数据集规模相同，减少规模不同造成的影响，进行高效地估计

2.3 评估方法

2.3.1 错误率和精度

  1. 均方误差(Mean Squared Error,MSE)：度量误差的大小

离散：E(f;D)=1m∑i=1m(f(xi)−yi)2连续：E(f;D)=∫x∼D(f(x)−y)2p(x)dx离散：E(f;D) = \frac{1}{m} \sum_{i=1}^m {(f(x_i)-y_i)^2}\\ 连续：E(f;D) = \int_{x{\sim}D} {(f(x)-y)^2p(x)dx}

  1. 错误率(error rate)：错误分类的比例

离散：E(f;D)=1m∑i=1mI(f(xi)≠yi)连续：E(f;D)=∫x∼DI(f(xi)≠yi)p(x)dx离散：E(f;D) = \frac{1}{m} \sum_{i=1}^{m} I(f(x_i) \neq y_i)\\ 连续：E(f;D) = \int_{x{\sim}D} \mathbb{I}(f(x_i) \neq y_i)p(x)dx

  1. 精度(accuracy)：正确分类的比例

离散：acc(f;D)=1m∑i=1mI(f(xi)=yi)=1−E(f;D)连续：acc(f;D)=∫x∼DI(f(xi)=yi)p(x)dx=1−E(f;D)离散：acc(f;D) = \frac{1}{m} \sum_{i=1}^{m} I(f(x_i) = y_i) = 1 - E(f;D)\\ 连续：acc(f;D) = \int_{x{\sim}D} \mathbb{I}(f(x_i) = y_i)p(x)dx = 1 - E(f;D)

2.3.2 查准率，查全率和F1

  1. 分类结果的混淆矩阵
  2. 查准率/精确度(precision)：在所有预测为正类的样本中，实际为正类的比例，适用于误判代价高的情况

Precision=TPTP+FPPrecision=\frac{TP}{TP+FP}

  1. 查全率/召回率(recall)：在所有实际为正类的样本中，被模型正确预测为正类的比例，适用于漏判代价高的情况

Recall=TPTP+FNRecall=\frac{TP}{TP+FN}

> 查准率和查全率是一对矛盾的度量。例如，有一摊西瓜：
> 希望将尽可能多的好瓜挑出来，则挑选的次数会变多，挑选到的坏瓜也会变多，导致查准率下降；
> 希望挑选到的瓜中好瓜尽可能多，则只挑选有把握的瓜，难免会遗漏很多看似不好的好瓜，导致查全率下降
  1. P-R曲线：设置不同的阈值来界定预测值，从而得到不同的查准率和查全率，以查准率作为纵轴，查全率作为横轴
    • 外包：若一个学习器的P-R曲线包住另一个学习器的P-R曲线，则可断言前者的性能优于后者
    • 相交：若两个学习器的P-R曲线有交点，则可以根据曲线包围的面积来比较性能
    • 平衡点(Break-Even Point,BEP)：查准率=查全率时的取值，平衡点越大性能越好
  2. F1度量：基于查准率和查全率的调和平均

F1=2×P×RP+R=2×TP样例总数+TP−TNF1 = \frac{2 \times P \times R}{P + R} = \frac{2 \times TP}{样例总数 + TP - TN}

  1. F~β~度量：表达了对查准率和查全率不同的偏好，β>1时侧重于查全率，β<1时侧重于查准率，β=1时退化为F1

Fβ=(1+β2)×P×R(β2×P)+RF_{\beta} = \frac{(1+\beta^2)\times P \times R}{(\beta^2 \times P)+R}

  1. 宏：先在各个混淆矩阵上分别计算得到P和R，然后加起来再计算平均值

macro-P=1n∑i=1nPi macro-R=1n∑i=1nRi macro-F1=2×macro-P×macro-Rmacro-P+macro-Rmacro\text{-}P = \frac{1}{n}\sum_{i=1}^n{P_i}\\ \,\\ macro\text{-}R = \frac{1}{n}\sum_{i=1}^n{R_i}\\ \,\\ macro\text{-}F1 = \frac{2 \times macro\text{-}P \times macro\text{-}R}{macro\text{-}P + macro\text{-}R}

  1. 微：先将各个混淆矩阵对应元素加起来得到平均值，然后再计算P和R

micro-P=TP‾TP‾+FP‾ micro-R=TP‾TP‾+FN‾ micro-F1=2×micro-P×micro-Rmicro-P+micro-Rmicro\text{-}P = \frac{\overline{TP}}{\overline{TP}+\overline{FP}}\\ \,\\ micro\text{-}R = \frac{\overline{TP}}{\overline{TP}+\overline{FN}}\\ \,\\ micro\text{-}F1 = \frac{2 \times micro\text{-}P \times micro\text{-}R}{micro\text{-}P + micro\text{-}R}

2.3.3 ROC和AUC

类别预测为正预测为负
真实为正真正例TP假反例FN
真实为负假正例FP真反例NP
  1. 真正例率：在所有实际为正类的样本中，被模型正确预测为正类的比例

TPR=TPTP+FNTPR=\frac{TP}{TP+FN}

  1. 假正例率：在所有实际为负类的样本中，被模型正确预测为正类的比例

FPR=FPTN+FPFPR=\frac{FP}{TN+FP}

  1. “受试者工作特征”曲线(Receiver Opearating Characteristic,ROC)：TPR越大，FPR越小，模型分类效果越好
    1. 根据学习器的预测结果对样例进行排序，假设实际上有m^+^个正例和m^-^个负例
    2. 先把分类阈值设为最大，此时全部样例均预测为负类，可以标记点(0,0)
    3. 然后将分类阈值依次设为每个样例的预测值，每次得到FPR和TPR分别作为横轴和纵轴，令前一个标记点的坐标为(x,y)：
      1. 若当前标记点是真正例，则坐标为(x,y+1m+\frac{1}{m^+})
      2. 若当前标记点是假正例，则坐标为(x+1m−\frac{1}{m^-},y)

ROC适用于评估分类器的整体性能，不受类别分布改变的影响
PR完全聚焦于正例，与类别分布相关

  1. ROC曲线下面积(Area Under ROC Curve,AUC)：判断模型分类性能的优劣
    • AUC=1：完美分类器，存在至少一个阈值能得出完美预测
    • 0.5<AUC<1：可以妥善设定阈值，具有预测价值
    • AUC=0.5：相当于随机猜测，没有任何预测价值
    • AUC<0.5：比随机预测还要差劲，但是可以尝试取预测的相反结果

AUC=12∑i=1m−1(xi+1−xi)(yi+yi+1)AUC=\frac{1}{2}\sum_{i=1}^{m-1}{(x_{i+1}-x_i)(y_i+y_{i+1})}


5. 排序损失：理想情况下，真正为正类而被预测为正类的概率值应该最大，排序应该靠前，因此ROC应该先竖直上升到(0,1)，再水平向右到(1,1)，面积为1。然而实际应用中，一些负类的概率值会比正类还大，造成ROC中途水平向右产生波折，导致面积小于1

lrank=∑x+∈D+1m+∑x−∈D−1m−( I(f(x+)<f(x−))+12I(f(x+)=f(x−)) )=1−AUCl_{rank} = \sum_{x^+ \in D^+}\frac{1}{m^+}\sum_{x^- \in D^-}\frac{1}{m^-}\Big(\,\mathbb{I}(f(x^+)<f(x^-))+\frac{1}{2}\mathbb{I}(f(x^+)=f(x^-))\,\Big) = 1-AUC

  • 求和每一次右移产生的损失矩形的面积
  • 特殊情况：负类和正类的预测概率值一样，此时ROC曲线既会竖直向上也会水平向右，产生一个斜线，面积是矩形的一半即三角形

2.3.4 代价

非均等代价(unequal cost)：将正类识别为负类和将负类识别为正类，具有不同的代价

代价矩阵：这里0是正类，1是负类，cost~ij~表示把i识别为j的代价值

代价敏感错误率(cost-sensitive)：针对不同类别分类错误带来不同后果的情况下的评估指标（假设有m个数据）

E(f;D;cost)=1m(∑xi∈D+I(f(xi)≠yi)×cost01+∑xi∈D−I(f(xi)≠yi)×cost10)E(f;D;cost)=\frac{1}{m}\Big(\sum_{x_i \in D^+}\mathbb{I}(f(x_i) \neq y_i) \times cost_{01} + \sum_{x_i \in D^-}\mathbb{I}(f(x_i) \neq y_i) \times cost_{10}\Big)

代价曲线(cost curve)：取ROC曲线上每一点得到(0,FPR)到(1,FNR)的一条线段，线段下的面积表示了该条件下的期望总体代价，取所有线段的下界为围城的图形面积就是学习器的期望总体代价

横轴：正例概率代价P(+)cost=p×cost01p×cost01+(1−p)×cost10 纵轴：归一化代价costnorm=FNR×p×cost01+FPR×(1−p)×cost10p×cost01+(1−p)×cost10横轴：正例概率代价P(+)cost = \frac{p \times cost_{01}}{p \times cost_{01} + (1-p) \times cost_{10}}\\ \,\\ 纵轴：归一化代价cost_{norm} = \frac{FNR \times p \times cost_{01} + FPR \times (1-p) \times cost_{10}}{p \times cost_{01} + (1-p) \times cost_{10}}

2.4 比较检验

2.4.1 假设检验

单次留出法：泛化错误率ϵ\epsilon等于测试错误率ϵ^\hat{\epsilon}的概率符合二项分布，当且仅当ϵ^=ϵ\hat{\epsilon}=\epsilon时P(ϵ^;ϵ)P(\hat{\epsilon};\epsilon)最大（m是样本总数）

P(ϵ^;ϵ)=(mϵ^×m)ϵϵ^×m(1−ϵ)m−ϵ^×mP(\hat{\epsilon};\epsilon)={m \choose \hat{\epsilon} \times m}\epsilon^{\hat{\epsilon} \times m}(1-\epsilon)^{m-\hat{\epsilon} \times m}

置信度(confidence)：假设“ϵ≤ϵ0\epsilon\leq\epsilon_0”。当且仅当ϵ≤ϵˉ{\epsilon}\leq\bar\epsilon，能以1−α1-\alpha的置信度认为泛化错误率不大于ϵ0\epsilon_0；否则拒绝该假设，即在αα的显著度下可认为学习器的泛化错误率大于ϵ0\epsilon_0

ϵˉ=min ϵs.t.∑i=ϵ0×m+1m(mi)ϵi(1−ϵ)m−i<α\bar\epsilon = min\,\epsilon\quad s.t.\quad \sum_{i=\epsilon_0 \times m + 1}^m{m \choose i}{\epsilon^i(1-\epsilon)^{m-i} < \alpha}

多次重复留出法：测试k次，得到k个测试错误率ϵ^1,ϵ^2,...,ϵ^k\hat\epsilon_1,\hat\epsilon_2,...,\hat\epsilon_k

μ=1k∑i=1k(ϵ^i) σ=1k−1∑i=1k(ϵ^i−μ)2 \mu = \frac{1}{k}\sum_{i=1}^k(\hat\epsilon_i)\\ \,\\ \sigma = \frac{1}{k-1}\sum_{i=1}^k(\hat\epsilon_i-\mu)^2\\ \,\\

置信度：τt\tau_t服从自由度为k-1的t分布，对假设“μ=ϵ\mu=\epsilon”。当且仅当τt\tau_t位于临界值范围[t−α/2,tα/2][t_{-\alpha/2},t_{\alpha/2}]之内，能以1−α1-\alpha的置信度认为泛化错误率等于μ\mu；否则拒绝该假设，即在αα的显著度下认为学习器的泛化错误率不等于μ\mu

τt=k(μ−ϵ)σ\tau_t = \frac{\sqrt{k}(\mu-\epsilon)}{\sigma}

2.4.2 交叉验证t检验

成对t检验：判断两个学习期的性能是否相同
1. 对两个学习器A和B，将样本分成k折，得到测试错误率分别为ϵ1A,ϵ2A,...,ϵkA\epsilon_1^A,\epsilon_2^A,...,\epsilon_k^A和ϵ1B,ϵ2B,...,ϵkB\epsilon_1^B,\epsilon_2^B,...,\epsilon_k^B
2. 相减得到差值Δ1,Δ2,...,Δk\Delta_1,\Delta_2,...,\Delta_k
3. 计算均值μ\mu和方差σ\sigma

置信度：对假设“A性能与B性能没有差异”。若τt<ta/2,k−1\tau_t<t_{a/2,k-1}，则可以以1−α1-\alpha的置信度认为两个学习器的性能没有显著差异；否则在αα的显著度下认为两个学习器性能具有显著差异

τt=∣kμσ∣\tau_t = |\frac{\sqrt{k}\mu}{\sigma}|

5×2交叉检验：做5次2折交叉验证，每次2折之前随机将数据打乱，使得5次交叉验证中的数据划分不重复，其中仅计算第1次的平均值，但对每次都计算出方差

μ=12(Δ11+Δ12) σi2=(Δi1−Δi1+Δi22)2+(Δi2−Δi1+Δi22)2\mu = \frac{1}{2}(\Delta_1^1+\Delta_1^2)\\ \,\\ \sigma_i^2 = (\Delta_i^1-\frac{\Delta_i^1+\Delta_i^2}{2})^2+ (\Delta_i^2-\frac{\Delta_i^1+\Delta_i^2}{2})^2

置信度：同上，服从自由度为5的t分布

τt=μ 15∑i=15σi2  a=0.05,ta/2,5=2.5706a=0.1,ta/2,5=2.0150\tau_t = \frac{\mu}{\sqrt{\,{\frac{1}{5}\sum_{i=1}^5}\sigma_i^2}\,}\\ \,\\ a=0.05,t_{a/2,5}=2.5706\\ a=0.1,t_{a/2,5}=2.0150

2.4.3 McNemar检验

列联表(contingency table)：获得两学习器分类结果的差别，若两学习器性能相同，则应该有e01=e10e_{01}=e_{10}，那么变量∣e01−e10∣|e_{01}-e_{10}|就应该服从正态分布

置信度：变量τχ\tau_\chi服从自由度为1的χ2\chi^2分布。假设“两学习器性能相同”。若τχ<χα2\tau_\chi<\chi_\alpha^2，则可以以1−α1-\alpha的置信度认为两个学习器的性能没有显著差异；否则在αα的显著度下认为两个学习器性能具有显著差异

τχ=(∣e01−e10∣−1)2e01+e10 a=0.05,ta/2,5=3.8415a=0.1,ta/2,5=2.7055\tau_\chi=\frac{(|e_{01}-e_{10}|-1)^2}{e_{01}+e_{10}}\\ \,\\ a=0.05,t_{a/2,5}=3.8415\\ a=0.1,t_{a/2,5}=2.7055

2.4.4 Friedman检验与Nemenyi后续检验

算法比较序值表：在每个数据集上根据测试性能将算法由好到坏排序，并赋予序值1,2,3,…若性能相同则平分序值

Friedman检验：假设在N个数据集上比较k个算法，令rir_i表示第i个算法的平均序值，则rir_i的均值和方差分别为(k+1)/2(k+1)/2和(k2−1)/12N(k^2-1)/12N

  • 变量τχ2\tau_{\chi^2}：服从自由度为k-1的χ2\chi^2分布

τχ2=12Nk(k+1)(∑i=1kri2−k(k+1)24)\tau_{\chi^2} = \frac{12N}{k(k+1)}\Big(\sum_{i=1}^k{r_i^2}-\frac{k(k+1)^2}{4}\Big)

  • 变量τF2\tau_{F^2}：服从自由度为k-1和(k-1)(N-1)的FF分布

τF=(N−1)τχ2N(k−1)−τχ2\tau_F = \frac{(N-1)\tau_{\chi^2}}{N(k-1)-\tau_{\chi^2}}

Nemenyi后续检验(post-hoc)：如果假设“所有算法的性能相同”被拒绝，说明算法的性能显著不同，需要进行后续检验来进一步区分各个算法，可以计算出平均序值差别的临界值域(critical domain)

CD=qαk(k+1)6NCD=q_\alpha\sqrt{\frac{k(k+1)}{6N}}

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令y是真实标记，y_D是数据集中标记，x是测试样本\\ f(x;D)是在数据集D上学到的模型在x上的输出，\bar{f}(x)是模型的期望预测输出\\ \,\\ \begin{cases} 偏差bias^2(x) = \big(\bar{f}(x)-y\big)^2\\ \,\\ 方差var(x) = E_D[\big(f(x;D)-\bar{f}(x)\big)^2]\\ \,\\ 噪声\epsilon^2 = E_D[(y_D-y)^2]\\ \,\\ 期望泛化误差E(f;D) = bias^2(x) + var(x) + \epsilon^2 \end{cases}

偏差-方差窘境(bias-variance dilemma)

时期主导表现
初期偏差训练不足，拟合能力很弱，欠拟合
中期偏差和方差相当训练加深，拟合能力增加，存在极值点
末期方差训练充足，拟合能力饱和，过拟合