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

为权衡不同类型错误所造成的不同损失，可为错误赋予"非均等代价"

• 以二分类任务为例，可根据任务的领域知识设定一个"代价矩阵"(cost matrix).如下表所示，其中，$cos{t}_{ij}cost\_\{ij\}$表示将第$ii$类样本预测为第$jj$类样本的代价。一般来说，$cos{t}_{ii}=0cost\_\{ii\}=0$;若将第0类判别为第一类所造成的损失更大，则$cos{t}_{01}>cos{t}_{10}cost\_\{01\}>cost\_\{10\}$;损失程度相差越大，$cos{t}_{01}cost\_\{01\}$与$cos{t}_{10}cost\_\{10\}$值的差别越大。一般情况下，重要的是代价比值而非绝对值

二分类代价矩阵

• 之前的一些度量性能那个可看出，大都隐式地假设了均等代价，并没有考虑不同错误会造成不同地后果。在非均等代价下，不再是简单地最小化错误次数，而是希望最小化"总体代价"(total cost).

1. 代价敏感(cost-sensitive)错误率

• 将表中的第0类作为正类，第1类作为反类，令$D^{+}D^+$与$D^{-}D^-$分别代表样例集$DD$的正例子集和反例子集，则"代价敏感"错误率为
  $E(f;D;cost)=\frac{1}{m}({\sum }_{x_i\in D^{+}}\mathbb{I}(f(x_i)\mathrm{\ne }{y}_i)\times cos{t}_{01}+{\sum }_{x_i\in D^{-}}\mathbb{I}(f(x_i)\mathrm{\ne }{y}_i)\times cos{t}_{10})E(f;D;cost)=\backslash frac\; \{1\}\{m\}(\backslash sum\_\{x\_i\backslash in\; D^+\}\backslash mathbb\{I\}(f(x\_i)\backslash neq\; y\_i)\backslash times\; cost\_\{01\}\; +\; \backslash sum\_\{x\_i\backslash in\; D^-\}\backslash mathbb\{I\}(f(x\_i)\backslash neq\; y\_i)\backslash times\; cost\_\{10\})$
• 类似的，可基于分布定义代价敏感错误率，给出其他一些性能度量的代价敏感版本
• 若令$cos{t}_{ij}cost\_\{ij\}$中的$i\mathrm{、}ji、j$取值不限于0、1，则可定义出多分类任务的代价敏感性能度量

2. 代价曲线(cost curve)

• 可以直接反映出学习器的期望总体代价
• 代价曲线图的横轴是取值为[0,1]的正例概率代价为：
  $P(+)cost=\frac{p\times cos{t}_{01}}{p\times cos{t}_{01}+(1-p)\times cos{t}_{10}}P(+)cost=\backslash frac\; \{p\backslash times\; cost\_\{01\}\}\{p\; \backslash times\; cost\_\{01\}\; +\; (1-p)\; \backslash times\; cost\_\{10\}\}$
  其中$pp$是样例为正例的概率；
  纵轴是取值为[0,1]的归一化代价
  $cos{t}_{norm}=\frac{FNR\times p\times cos{t}_{01}+FPR\times (1-p)\times cos{t}_{10}}{p\times cos{t}_{01}+(1-p)\times cos{t}_{10}}cost\_\{norm\}=\backslash frac\; \{FNR\; \backslash times\; p\; \backslash times\; cost\_\{01\}+FPR\; \backslash times\; (1-p)\; \backslash times\; cost\_\{10\}\}\{p\; \backslash times\; cost\_\{01\}+(1-p)\; \backslash times\; cost\_\{10\}\}$
  其中FPR为假正例率，FNR=1-TPR是假反例率

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

四、比较检验

• 希望比较的是泛化性能，然而通过实验评估方法获得的是测试集上的性能，两者的对比结果可能未必相同
• 测试集上的性能与测试集本身的选择有很大关系，且不论使用不同大小的测试集会得到不同的结果，即便使用相同大小的测试集，若包含的测试样例不同，测试结果也会有不同
• 很多机器学习算法本身有一定的随机性，即便使用相同的参数设置在同一个测试集上多次运行，其结果也会有不同

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

4.1 假设检验

假设检验中的"假设"是对学习器泛化错误率分布的某种判断或猜想，例如"$ϵ={ϵ}_0\backslash epsilon\; =\; \backslash epsilon\_0$".现实任务中并不知道学习器的泛化错误率，只能获知其测试错误率$\widehat{ϵ}\backslash hat\{\backslash epsilon\}$。泛化错误率与测试错误率未必相同，但直观上，二者接近的可能性应比较大，相差很远的可能性比较小，因此，可根据测试错误率估推出泛化错误率的分布

• 泛化错误率为$ϵ\backslash epsilon$的学习器在一个样本上犯错的概率是$ϵ\backslash epsilon$;测试错误率$\widehat{ϵ}\backslash hat\{\backslash epsilon\}$意味着在$mm$个测试样本中恰有$\widehat{ϵ}\times m\backslash hat\{\backslash epsilon\}\; \backslash times\; m$个被误分类。假定测试样本是从样本总体分布中独立采样而得，那么泛化错误率为$ϵ\backslash epsilon$的学习器将其中$m^{\mathrm{\prime }}m^\backslash prime$个样本误分类、其余样本全部分类正确的概率是：$C_m^{\widehat{ϵ}\times m}{ϵ}^{\widehat{ϵ}\times m}(1-ϵ{)}^{m-\widehat{ϵ}\times m}C^\{\backslash hat\{\backslash epsilon\}\; \backslash times\; m\}\_m\backslash epsilon^\{\backslash hat\{\backslash epsilon\}\; \backslash times\; m\}(1-\backslash epsilon)^\{m-\backslash hat\{\backslash epsilon\}\; \backslash times\; m\}$，给定测试错误率，则解$\mathrm{\partial }P(\widehat{ϵ};ϵ)\mathrm{/}\mathrm{\partial }ϵ=0\backslash partial\; P(\backslash hat\{\backslash epsilon\};\backslash epsilon)/\backslash partial\; \backslash epsilon\; =\; 0$可知，$P(\widehat{ϵ};ϵ)P(\backslash hat\{\backslash epsilon\};\backslash epsilon)$在$ϵ=\widehat{ϵ}\backslash epsilon=\backslash hat\{\backslash epsilon\}$时最大，$\mathrm{\mid }ϵ-\widehat{ϵ}\mathrm{\mid }|\backslash epsilon-\backslash hat\{\backslash epsilon\}|$增大时，$P(\widehat{ϵ};ϵ)P(\backslash hat\{\backslash epsilon\};\backslash epsilon)$减小，这符合二项(binomial)分布.

• 可使用"二项检验"(binomial test)对"$ϵ\le {ϵ}_0\backslash epsilon\; \backslash leq\; \backslash epsilon\_\{0\}$"的假设进行检验，则在$1-\alpha 1-\backslash alpha$的概率内所能观测到的最大错误率为：
  $\overline{ϵ}=maxϵ\backslash bar\{\backslash epsilon\}\; =\; max\; \backslash epsilon$  
  这里$1-\alpha 1-\backslash alpha$反映了结论的"置信度"。此时若测试错误率$\widehat{ϵ}\backslash hat\{\backslash epsilon\}$小于临界值$\overline{ϵ}\backslash bar\; \backslash epsilon$,则根据二项检验可得出结论：在$\alpha \backslash alpha$的显著度下，假设"$ϵ\le {ϵ}_0\backslash epsilon\; \backslash leq\; \backslash epsilon\_\{0\}$"不能被拒绝，即能以$1-\alpha 1-\backslash alpha$的置信度认为，学习器的泛化错误率不大于${ϵ}_0\backslash epsilon\_0$;否则该假设可被拒绝，即在$\alpha \backslash alpha$的显著度下可认为学习器的泛化错误大于${ϵ}_0\backslash epsilon\_0$。

• 由于很多时候并非仅做一次留出法估计，而是通过多次重复留出法或是交叉验证法等多次训练/测试，这样会得到多个测试错误率，此时可使用"$tt$检验"(t-test).假定得到了$kk$格测试错误率，${\widehat{ϵ}}_1,{\widehat{ϵ}}_2,\dots ,{\widehat{ϵ}}_k\backslash hat\; \backslash epsilon\_1,\backslash hat\; \backslash epsilon\_2,\backslash ldots,\backslash hat\; \backslash epsilon\_k$，则平均错误率$\mu \backslash mu$和方差${\sigma }^2\backslash sigma^2$为：
  $\mu =\frac{1}{k}{\sum }_{i=1}^k{\widehat{ϵ}}_i\backslash mu\; =\; \backslash frac\{1\}\{k\}\; \backslash sum\_\{i=1\}^k\; \backslash hat\; \backslash epsilon\_i$
  ${\sigma }^2=\frac{1}{k-1}{\sum }_{i=1}^k({\widehat{ϵ}}_i-\mu {)}^2\backslash sigma^2=\backslash frac\{1\}\{k-1\}\backslash sum\_\{i=1\}^k(\backslash hat\backslash epsilon\_i-\backslash mu)^2$
  考虑到这$kk$个测试错误率可看作泛化错误率${ϵ}_0\backslash epsilon\_0$的独立采样，则变量 ${\tau }_t=\frac{\sqrt{k}(\mu -{ϵ}_0)}{\sigma }\backslash tau\_t=\backslash frac\; \{\backslash sqrt\; k(\backslash mu-\backslash epsilon\_0)\}\{\backslash sigma\}$ 服从自由度为$k-1k-1$的$tt$分布。
  对假设"$\mu ={ϵ}_0\backslash mu\; =\; \backslash epsilon\_0$",计算出当测试错误率均值为${ϵ}_0\backslash epsilon\_0$时，在$1-\alpha 1-\backslash alpha$概率内能观测到的最大错误率，即临界值。这里考虑的是双边检验(two-tailed)假设，所以范围为$[-\mathrm{\infty },t_{-\frac{\alpha }{2}}][-\backslash infty,t\_\{-\backslash frac\; \{\backslash alpha\}\{2\}\}]$和$[t_{\frac{\alpha }{2}},\mathrm{\infty }][t\_\{\backslash frac\; \{\backslash alpha\}\{2\}\},\backslash infty]$.若平均错误率$\mu \backslash mu$与$ϵ\backslash epsilon$之差$\mathrm{\mid }\mu -{ϵ}_0\mathrm{\mid }|\backslash mu-\backslash epsilon\_0|$位于临界值范围$[t_{-\frac{\alpha }{2}},t_{\frac{\alpha }{2}}][t\_\{-\backslash frac\; \{\backslash alpha\}\{2\}\},t\_\{\backslash frac\; \{\backslash alpha\}\{2\}\}]$内，则不能拒绝假设"$\mu -{ϵ}_0\backslash mu-\backslash epsilon\_0$"，则可认为泛化错误率为${ϵ}_0\backslash epsilon\_0$，置信度为$1-\alpha 1-\backslash alpha$;否则可拒绝该假设，即在该显著度下可认为泛化错误率与${ϵ}_0\backslash epsilon\_0$有显著不同。

4.2 交叉验证t检验

• 对不同的学习器的性能进行比较
• 基本思想：若两个学习器的性能相同，则它们使用相同的训练/测试集得到的测试错误率应相同

• 对于两个学习器A和B，若使用k折交叉验证法得到的测试错误率分别为${ϵ}_1^A,{ϵ}_2^A,\dots ,{ϵ}_k^A\backslash epsilon\_1^A,\backslash epsilon\_2^A,\backslash ldots,\backslash epsilon\_k^A$和${ϵ}_1^B,{ϵ}_2^B,\dots ,{ϵ}_k^B\backslash epsilon\_1^B,\backslash epsilon\_2^B,\backslash ldots,\backslash epsilon\_k^B$，其中${ϵ}_i^A\backslash epsilon\_i^A$和${ϵ}_i^B\backslash epsilon\_i^B$是在相同的第$ii$折训练/测试集得到的结果，则可用$kk$折交叉验证"成对t检验"(paired t-test)来进行比较检验。

• 具体来说，对于$kk$折交叉验证产生的$kk$对测试错误率：先对每对结果求差，${\mathrm{\Delta }}_i={ϵ}_i^A-{ϵ}_i^B\backslash Delta\_i=\; \backslash epsilon\_i^A-\backslash epsilon\_i^B$;若两个学习器性能相同，则差值均值应为零。因此，可根据差值${\mathrm{\Delta }}_1,{\mathrm{\Delta }}_2,\dots ,{\mathrm{\Delta }}_k\backslash Delta\_1,\backslash Delta\_2,\backslash ldots,\backslash Delta\_k$来对"学习器A与学习器B性能相同"这个假设做$tt$检验，计算出差值的均值$\mu \backslash mu$和方差${\sigma }^2\backslash sigma^2$，在显著度$\alpha \backslash alpha$下，若变量${\tau }_t=\mathrm{\mid }\frac{\sqrt{k}\mu }{\sigma }\mathrm{\mid }\backslash tau\_t=|\backslash frac\; \{\backslash sqrt\; k\backslash mu\}\{\backslash sigma\}|$小于临界值$t_{\frac{\alpha }{2},k-1}t\_\{\backslash frac\; \{\backslash alpha\}\{2\},k-1\}$，则假设不能被拒绝，即认为两个学习器的性能没有显著差别；否则可认为两个学习器的性能有显著差别，且平均错误率较小的那个学习器性能较优。这里$t_{\frac{\alpha }{2},k-1}t\_\{\backslash frac\; \{\backslash alpha\}\{2\},k-1\}$是自由度为$k-1k-1$的$tt$分布上尾部累积分布为$\frac{\alpha }{2}\backslash frac\; \{\backslash alpha\}\{2\}$的临界值。

• 欲进行有效的假设检验，一个重要前提是测试错误率均为泛化错误率的独立采样。然而，通常情况下由于样本有限，在使用交叉验证等实验估计方法时，不同轮次的训练集会有一定程度的重叠，这就使得测试错误率实际上并不独立，会导致过高估计假设成立的概率。为缓解这一问题，可采用"5$\times \backslash times$2交叉验证"法

• 5$\times \backslash times$2交叉验证是做5次2折交叉验证，在每次2折交叉验证之前随机将数据打乱，使得5次交叉验证中的数据划分不重复。对两个学习器A和学习器B，第$ii$次2折交叉验证将产生两对测试错误率，对它们分别求差，得到第1折上的差值${\mathrm{\Delta }}_i^1\backslash Delta\_i^1$和第2折上的差值${\mathrm{\Delta }}_i^2\backslash Delta\_i^2$.为缓解测试错误率的非独立性，仅计算第1次2折交叉验证的两个结果的平均值$\mu =0.5({\mathrm{\Delta }}_1^1+{\mathrm{\Delta }}_1^2)\backslash mu=0.5(\backslash Delta\_1^1+\backslash Delta\_1^2)$，但对每次2折实验的结果都计算出其方差${\sigma }_i^2=({\mathrm{\Delta }}_i^1-\frac{{\mathrm{\Delta }}_i^1+{\mathrm{\Delta }}_i^2}{2}{)}^2+({\mathrm{\Delta }}_i^2-\frac{{\mathrm{\Delta }}_i^1+{\mathrm{\Delta }}_i^2}{2}{)}^2\backslash sigma\_i^2=(\backslash Delta\_i^1-\backslash frac\{\backslash Delta\_i^1+\backslash Delta\_i^2\}\{2\})^2+(\backslash Delta\_i^2-\backslash frac\{\backslash Delta\_i^1+\backslash Delta\_i^2\}\{2\})^2$.变量${\tau }_t=\frac{\mu }{\sqrt{0.2{\sum }_{i=1}^5{\sigma }_i^2}}\backslash tau\_t=\backslash frac\; \{\backslash mu\}\{\backslash sqrt\{0.2\backslash sum\_\{i=1\}^5\backslash sigma\_i^2\}\}$服从自由度为5的$tt$分布，其双边检验的临界值$t_{\frac{\alpha }{2},5}t\_\{\backslash frac\{\backslash alpha\}\{2\},5\}$当$\alpha \backslash alpha$=0.05为2.5706，当$\alpha \backslash alpha$=0.1为2.0150

4.3 McNemar检验(卡方检验)

• 对于二分类问题，使用留出法不仅可估计出学习器A和B的测试错误率，还可获得两学习器分类结果的差别，即两者都正确、都错误、一个正确另一个错误的样本数，如“列联表”所示：

两学习器分类差别列联表

• 若做的假设是两学习器性能相同，则应有$e_{01}=e_{10}e\_\{01\}=e\_\{10\}$，那么变量$\mathrm{\mid }{e}_{01}-e_{10}\mathrm{\mid }|e\_\{01\}-e\_\{10\}|$应当服从正态分布。McNemar检验考虑变量${\tau }_{{\chi }^2}=\frac{(\mathrm{\mid }{e}_{01}-e_{10}\mathrm{\mid }-1{)}^2}{e_{01}+e_{10}}\backslash tau\_\{\backslash chi^2\}=\backslash frac\{(|e\_\{01\}-e\_\{10\}|-1)^2\}\{e\_\{01\}+e\_\{10\}\}$服从自由度为1的${\chi }^2\backslash chi^2$分布，即标准正态分布变量的平方。给定显著度$\alpha \backslash alpha$，当以上变量值小于临界值${\chi }_{\alpha }^2\backslash chi\_\backslash alpha^2$时，不能拒绝假设，即认为两学习器的性能没有显著差别；否则拒绝假设，认为两者性能有显著差别，且平均错误率较小的那个学习器性能较优。自由度为1的${\chi }^2\backslash chi^2$检验的临界值当$\alpha =0.05\backslash alpha=0.05$时为3.8415，$\alpha =0.1\backslash alpha=0.1$时为2.7055