4.4 Friedman检验与Nemenyi后续检验

交叉验证t检验和McNemar检验都是在一个数据集上比较两个算法的性能，而很多时候，会在一组数据集上对多个算法进行比较。当有多个算法参与比较时，一种做法是在每个数据集上分别列出两两比较的结果，而在两两比较时可使用前述方法；另一种使用基于算法排序的Friedman检验。

• 假定用$D_1\mathrm{、}{D}_2\mathrm{、}{D}_3\mathrm{和}{D}_{4}D\_1、D\_2、D\_3和D\_4$四个数据集对算法A、B、C进行比较。首先，使用里留出法或交叉验证法得到每个算法在每个数据集上的测试结果，然后在每个数据集上根据测试性能由好到坏排序，并赋予序值1，2，……；若算法的测试性能相同，则平分序值。
• 例如，在$D_1\mathrm{、}{D}_{3}D\_1、D\_3$和$D_{4}D\_4$上，A最好、B次之、C最差，而在$D_{2}D\_2$上，A最好、B与C性能相同，可列出下表，其中最后一行通过对每一列的序值求平均，得到平均序值。

算法比较序值

• 然后，使用Friedman检验来判断这些算法是否性能都相同。若相同，则它们的平均序值应当相同。假定在N个数据集上比较k个算法，令$r_{i}r\_i$表示第$ii$个算法的平均序值，为简化讨论，暂不考虑平分序值的情况，则$r_{i}r\_i$的均值和方差分别为$\frac{k+1}{2}\backslash frac\; \{k+1\}\{2\}$和$\frac{k^2-1}{12N}\backslash frac\; \{k^2-1\}\{12N\}$.变量${\tau }_{{\chi }^2}=\frac{k-1}{k}\cdot \frac{12N}{k^2-1}{\sum }_{i=1}^k(r_i-\frac{k+1}{2}{)}^2=\frac{12N}{k(k+1)}({\sum }_{i=1}^k{r}_i^2-\frac{k(k+1{)}^2}{4})\backslash tau\_\{\backslash chi^2\}=\; \backslash frac\; \{k-1\}\{k\}\backslash cdot\; \backslash frac\{12N\}\{k^2-1\}\backslash sum\_\{i=1\}^k(r\_i-\backslash frac\{k+1\}\{2\})^2=\backslash frac\; \{12N\}\{k(k+1)\}(\backslash sum\_\{i=1\}^k\; r\_i^2-\backslash frac\{k(k+1)^2\}\{4\})$在k和N都较大时，服从自由度为k-1的${\chi }^2\backslash chi^2$分布

• 然而，上述这样的“原始Friedman检验”过于保守，现在通常使用变量${\tau }_F=\frac{(N-1){\tau }_{{\chi }^2}}{N(k-1)-{\tau }_{{\chi }^2}}\backslash tau\_F=\backslash frac\{(N-1)\backslash tau\_\{\backslash chi^2\}\}\{N(k-1)-\backslash tau\_\{\backslash chi^2\}\}$,其中${\tau }_{{\chi }^2}\backslash tau\_\{\backslash chi^2\}$由上式得到。${\tau }_F\backslash tau\_F$服从自由度为k-1和(k-1)(N-1)的F分布。

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

• Nemenyi检验计算出平均序值差别的临界值域$CD=q_{\alpha }\sqrt{\frac{k(k+1)}{6N}}CD\; =\; q\_\backslash alpha\backslash sqrt\{\backslash frac\; \{k(k+1)\}\{6N\}\}$.若两个算法的平均序值之差超出了临界值域CD，则以相应的置信度拒绝“两个算法性能相同”这一假设

五、偏差与方差

"偏差-方差分解"(bias-variance decomposition)是解释学习算法泛化性能的一种重要工具

• 偏差-方差分解试图对学习算法的期望泛化错误率进行拆解。算法在不同训练集上学得的结果很可能不同，即便这些训练集是来自同一个分布。对测试样本$xx$,令$y_{D}y\_D$为$xx$在数据集中的标记，$yy$为$xx$的真实标记，$f(x;D)f(x;D)$为训练集D上学得模型$ff$在$xx$上的预测输出。以回归任务为例，学习算法的期望预测为: $\bar{f}(x)={\mathbb{E}}_D[f(x;D)]\backslash bar\; f(x)=\backslash mathbb\; E\_D[f(x;D)]$
  使用样本数相同的不同训练集产生的方差为：$var(x)={\mathbb{E}}_D[(f(x;D)-\bar{f}(x){)}^2]var(x)=\backslash mathbb\; E\_D[(f(x;D)-\backslash bar\; f(x))^2]$
  噪声为：${\epsilon }^2={\mathbb{E}}_D[(y_D-y{)}^2]\backslash varepsilon^2=\backslash mathbb\; E\_D[(y\_D-y)^2]$
  期望输出与真实标记的差别称为偏差(bias)，即$bia{s}^2(x)=(\bar{f}(x)-y{)}^{2}bias^2(x)=(\backslash bar\; f(x)-y)^2$
  为便于讨论，假定噪声期望为零，即${\mathbb{E}}_D[y_D-y]=0\backslash mathbb\; E\_D[y\_D-y]=0$，通过简单的多项式展开合并，可对算法的期望泛化误差进行分解。最终可得 $E(f;D)=bia{s}^2(x)+var(x)+{\epsilon }^{2}E(f;D)=bias^2(x)+var(x)+\backslash varepsilon^2$，即泛化误差可分解为偏差、方差与噪声之和。

• 偏差：度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力

• 方差：度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响

• 噪声：表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度

• 偏差-方差分解：泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。给定学习任务，为了取得好的泛化性能，则需使偏差较小，即能够充分拟合数据，并且使方差较小，即使得数据扰动产生的影响小。

• 一般来说，偏差与方差是有冲突的，这称为偏差-方差窘境(bias-variance dilemma)。给定学习任务，假定能够控制学习算法的训练程度，则在训练不足时，学习器的拟合能力不够强，训练数据的扰动不足以使学习器产生显著变化，此时偏差主导了泛化错误率；随着训练程度的加深，学习器的拟合能力逐渐增强，训练数据发生的扰动渐渐能被学习器学到，方差逐渐主导了泛化错误率；在训练程度充足后，学习器的拟合能力已非常强，训练数据发生的轻微扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合。