西瓜书学习笔记(3)
主要内容：比较检验、偏差与方差
比较检验
在比较学习器泛化性能的过程中， 统计假设检验（hypothesis test） 为学习器性能比较提供了重要依据，即若A在某测试集上的性能优于B，那A学习器比B好的把握有多大。为方便论述，本篇中都是以 “错误率”$\epsilon$ 作为性能度量的标准。
假设检验
首先引入两个概念：
- 第一个叫做 泛化错误率$\epsilon$ ，是指学习器在一般情况下，对一个样本分类出错的概率，实际情况下我们是无法得知它的准确值的；
- 第二个叫做 测试错误率$\epsilon’$ ，即学习器在测试一个m大小的样本集时恰好有$\epsilon’$m个样本被分错类了，我们一般情况下只能获得这个值；
两者区别就是：
- 泛化错误率是一个理论上的值，无法获得
- 而测试错误率是一个我们可以测量得到的值。
统计假设检验的方法就是用$\epsilon’$估计$\epsilon$的值。
一个泛化错误率为$\epsilon$的学习器来测试一个大小为m的测试样例集，只可能有分对和分错两种情况，其中$\epsilon$m个分错，其余的分对，因此这就是一个典型的二项分布，那么我们可以得出测试的错误率分布函数：
$$
P(\epsilon’;\epsilon) =
\left(
\begin{array}{c}
m\
\epsilon’×m
\end{array}
\right)
\epsilon^{\epsilon’×m}
(1-\epsilon)^{m-\epsilon’×m}
$$
给定测试错误率，则解$\partial P(\epsilon’;\epsilon)/\partial\epsilon=0$可知，$P ( \epsilon’;\epsilon ) $在$\epsilon=\epsilon’$时最大，$|\epsilon-\epsilon’|$增大时$P ( \epsilon’;\epsilon ) $减小。
这符合二项分布。
二项假设检验
使用二项检验的方法(Binomial Test)，现假设 $H_{0}:\epsilon\le\epsilon_{0},H_{1}:\epsilon>\epsilon_{0}$ ，即右边检验，因此我们需要讨论单边检验的拒绝域形式，当 $H_{1}$ 为正时，测试错误率往往偏大，所以拒绝域形式为 $\hat{\epsilon}\ge k$ ，k为某一正数。
$$
P_{\epsilon\in H_{0}}{\hat{\epsilon}\ge k}=
\sum_{i=\lceil{mk}\rceil}^{m}
\left(
\begin{array}{c}
m\
i
\end{array}
\right)
\epsilon^{i}(1-\epsilon)^{m-i}\le
\sum_{i=\lceil{mk}\rceil}^{m}
\left(
\begin{array}{c}
m\
i
\end{array}
\right)
\epsilon_{0}^{i}(1-\epsilon_{0})^{m-i}\le \partial
$$
一般来说，$\alpha$ 通常取值为 0.01,0.05或0.1，通过该该等式可以求出满足条件的k值，即临界点，进一步求出该假设检验的拒绝域，当测试错误率大于该临界点时，假设被拒绝。
- 在假设检验中，我们称$\alpha$为显著性水平，也称之为显著值(signaficance)。
- 称$(1-\alpha)$为置信度。
t检验
在很多时候，我们会进行多次重复训练，会得到多个测试错误率，假设有k个。这时我们可以使用”t检验”，实际上k个测试错误率可以看为泛化错误率的k次独立采样，因此可以算出这k的样本的均值$\bar{X}$与方差$S^{2}$ 。
$$
\bar{X}=
\frac{1}{k}
\sum^{k}_{i=1}
\hat{\varepsilon} _{i}
$$
$$
S^{2}=
\frac{1}{k-1}
\sum^{k}_{i=1}
(\hat{ \varepsilon } _{i} - \bar{X})^{2}
$$
根据中心极限定理的经典推论，可以得知：$\frac{(\bar{X}-\varepsilon)}{S/\sqrt{n}}\sim t(n-1)$，当n足够大时，t分布近似于N(0,1)分布，一般情况下在n>45时，就可以使用标准正态分布的上分为点的$\alpha$值，有了这个分布之后，我们就可以类似二项检验进行t假设检验。t分布的示意图以及常用双边临界值表如下所示：
交叉t检验
对两个学习机A和B使用k折交叉验证法得到错误率分别为 $ \epsilon^{A}_1,\epsilon^{A} _{2},\dots,\epsilon^{A} _{k}$ 和 $\epsilon^{B}_1,\epsilon^{B} _{2},\dots,\epsilon^{B} _{k} $ 。
这里的基本思想是：若两个学习器A和B的性能相同，则它们使用相同的训练/测试集得到的测试错误率应相同，即 $ \epsilon ^{A} _{i} = \epsilon ^{B} _{i} $ 。我们对每一组数据求误差， $ \triangle _{i} = \epsilon ^{A} _{i} - \epsilon ^{B} _{i} $ ，则可以得到k个差值。用这k个差值来对”学习机A和学习机B性能相同”这一假设做t检验。
$$
\frac{ \left| \bar{ \triangle } - ( \epsilon _{ A } - \epsilon _{ B } ) \right| } { S / \sqrt{ k } } \sim t(k-1)
$$
计算出差值的均值 $ \bar{\triangle} $ 和方差 $ S^{2} $ ，在显著度 $ \alpha $ 下，若变量
$$
\tau _{t} = \left| \frac{ \sqrt{k} \bar{ \triangle } }{ S } \right|
$$
小于临界值 $ t _{\alpha / 2 , k-1} $ 则假设不能拒绝，即认为两个学习器没有显著差别；否则可认为两个学习器的性能有显著差别，且平均错误率较小的那个学习器性能更优。
在”交叉t检验”的基思想中，我们的前提是测试诓误率是泛化化误率的独立采样，但是在k折交叉检验中,选择的训练/测试难免会产生重，因此好的解决办法是便用5次2折交叉验证，使用第一次的两对差值计均值，便用全部的差值对（即10对〕计笪方差，可以有效地免这个问题。
McNumber检验
McNemar 检验用于检查两组之间的计数是否一致。它通常用于测试治疗组和对照组之间的计数是否相等。通常形式为列联表：
其中，$e_{00}$ 和 $e_{11}$ 表示两个学习器的结果都正确或都错误，$e_{01}$ 和 $e_{10}$ 表示两个学习器一方正确而另一方错误。
当我们假设两个学习器的性能都相同时，理想情况下应满足 $e_{01} = e_{10}$ , 且 $\left| e_{01} - e_{10} \right|$ 服从正态分布，且均值为1，方差为 $e_{01}+e_{10}$ 。因此变量
$$
\tau_{x^{2}} = \frac{(\left| e_{01} - e_{10} \right| - 1)^{2}}{e_{01}+e_{10}}
$$
服从自由度为1的 $x^{2}$ 分布，即卡方分布。
Friedman检验
当有多个算法参与多组数据集的比较时，可以较为直接的，使用基于算法排序的Friedman检验。基本思想是在同一组数据集上，根据测试结果（例：测试错误率）对学习器的性能进行排序，赋予序值1,2,3…，相同则平分序值，如下图所示
然后，使用Friedman检验来判断这些算法是否性能相同。若相同，则它们的平均序值应相同，且第i个算法的平均序值 $r_{i}$ 服从正态分布 $N((k+1)/2, (k^{2}-1)/12)$ 。变量
$$
\begin{align}
\tau_{x^{2}} &=
\frac{k-1}{k} ·
\frac{12N}{k^{2}-1}
\sum_{i=1}^{k}(r_{i} - \frac{k+1}{2} )^{2} \\
&= \frac{12N}{k(k+1)}\big( \sum_{i=1}^{k}r_{i}^{2} - \frac{k(k+1)^{2}}{4} \big)
\end{align}
$$
其中N为数据集数量，k为算法数量。当k和N都比较大时，服从自由度为k-1的 $x^{2}$ 分布。而这是较为原始的Friedman检验，过于保守，现在通常使用变量
$$
\tau_{F} = \frac{(N-1)\tau_{x^{2}}}{N(k-1)-\tau_{x^{2}}}
$$
$\tau_{F}$ 服从自由度为k-1和(k-1)(N-1)的F分布。F检验常用的临界值如下：
Nemenyi后续检验
当“所有算法的性能相同”这个假设被拒绝，则说明算法的性能显著不同，可以通过后续检验来进一步区分各算法，常用的有Nemenyi后续检验。
Nemenyi检验的基本思想是计算出平均序值差别的临界值域
$$
CD = q_{ \alpha } \sqrt{ \frac{ k(k+1) }{ 6N } }
$$
下表是常用的 $q_{\alpha}$ 值，若两个算法的平均序值差超出了临界值域CD，则相应的置信度 $1-\alpha$ 拒绝“两个算法性能相同”的假设。
偏差与方差
偏差-方差分解(Bias-Variance Decomposition)是解释学习器泛化性能的重要工具。在学习算法中，偏差指的是预测的期望值与真实值的偏差，方差则是每一次预测值与预测值得期望之间的差均方。实际上，偏差体现了学习器预测的准确度，而方差体现了学习器预测的稳定性。
通过对泛化误差的进行分解，可以得到：
$$
E(f;D) = \text{bias}^{2}(x) + var(x) + \epsilon^{2}
$$
其中 $\text{bias}^{2}(x)$ 为偏差， $var(x)$ 为方差， $\epsilon$ 为噪声（我们默认噪声为0）。可以看出：
- 期望泛化误差=方差+偏差
- 偏差刻画学习器的拟合能力
- 方差体现学习器的稳定性
一般来说，方差和偏差具有矛盾性，这就是常说的偏差-方差窘境（bias-variance dilamma），随着训练程度的提升，期望预测值与真实值之间的差异越来越小，即偏差越来越小，但是另一方面，随着训练程度加大，学习算法对数据集的波动越来越敏感，方差值越来越大。
换句话说：在欠拟合时，偏差主导泛化误差，而训练到一定程度后，偏差越来越小，方差主导了泛化误差。因此训练也不要贪杯，适度辄止。
