机器学习的数学基础：假设检验

假设检验

默认以错误率为性能度量，错误率由下式给出：

$$E(f,\mathcal{D})={\int }_{\mathbf{x}\sim \mathcal{D}}\mathbb{II}(f(\mathbf{x})\ne y)p(\mathbf{x})\text{d}\mathbf{x}$$

假设检验中的"假设"是对学习泛化错误率分布的某种判断或者猜想，例如:

$$\epsilon ={\epsilon }_0$$

其中，我们${\epsilon }_0$为测试错误率是已知的。

对单个学习器泛化能力的假设检验

对于一个样本上的留出法得到的错误率${\epsilon }_0$,这意味着$m$个测试样本中，恰好有$m\times {\epsilon }_0$个错误分类。假设测试样本是从总体中独立同分布采样获得，那么泛化错误率为$\epsilon$的学习器，将其中$m\times {\epsilon }_0$个分类错误，其余分类正确的概率为:

单次留出法
$$P(\epsilon ;{\epsilon }_0)=\left(\genfrac{}{}{0ex}{}{m}{m\times {\epsilon }_0}\right){\epsilon }^{{\epsilon }_0\times m}(1-\epsilon {)}^{m-{\epsilon }_0\times m}$$

所以由极值条件得到：

$$\frac{\partial P}{\partial \epsilon }=0$$

然后选取一个显著性水平$\alpha$，对于$\epsilon \sim B(m,{\epsilon }_0)$,我们假设$\epsilon \le {\epsilon }^{\prime }$,满足：

$$
\overline{\varepsilon}=\min \varepsilon

\mathbf{s.t.}:
\sum_{i=\varepsilon^{\prime}\times m+1}^{{m}\binom{m}{i}\varepsilon}{i}(1-\varepsilon)^{m-i}
$$

若此时$\epsilon \le \overline{\epsilon }$则有$1-\alpha$的概率认为，学习器的泛化错误率不大于${\epsilon }^{\prime }$。

多次留出法或交叉验证法

类似的，假定我们得到了$k$个测试错误率，${\hat{\epsilon }}_1$,${\hat{\epsilon }}_2$,$\cdots$,${\hat{\epsilon }}_k$,则平均测试错误率$\mu$和方差${\sigma }^2$分别为：

$$\mu =\frac{1}{k}\sum _{i=1}^k{\hat{\epsilon }}_i$$

$${\sigma }^2=\frac{1}{k-1}\sum _{i=1}^k({\hat{\epsilon }}_i-\mu {)}^2$$
其中有假设：
每个测试错误率 ${\hat{\epsilon }}_1,{\hat{\epsilon }}_2,\dots ,{\hat{\epsilon }}_k$ 必须是独立同分布（independent and identically distributed, i.i.d.）的随机变量。且样本量足够大或者它们服从正态分布。

则：

$${\tau }_t=\frac{(\mu -{\epsilon }_0)}{\frac{\sigma }{\sqrt{k}}}\sim t(k-1)$$

对两个学习器泛化能力的假设检验

对于两个学习器$A$和$B$，使用$k$折交叉验证法得到：${\epsilon }_1^A$,${\epsilon }_2^A$,$\dots$${\epsilon }_k^A$和${\epsilon }_1^B$,${\epsilon }_2^B$,$\dots$${\epsilon }_k^B$

我们是对

$${\epsilon }_i^A={\epsilon }_i^B$$

进行假设，取独立变量：

$${\Delta }_i={\epsilon }_i^A-{\epsilon }_i^B$$

对样本均值进行标准化得到：

$${\tau }_t=\frac{\mu }{\frac{\sigma }{\sqrt{k}}}\sim t(k-1)$$

5×2交叉验证

其统计量为：
$${\tau }_t=\frac{\mu }{\sqrt{0.2\sum _{i=1}^5}{\sigma }_i^2}\sim t(4)$$

McNemar检验

对于二分类问题，我们通过列联表，基于两学习器的性能相同的假设，构造统计量：

	方法B 阳性	方法B 阴性
方法A 阳性	$a$	$b$
方法A 阴性	$c$	$d$

$${\tau }_{{\chi }^2}=\frac{(|b-c|-1{)}^2}{b+c}\sim {\chi }^2(1)$$

对多于两个学习器泛化能力的假设检验

对多个算法，要进行Friedman检验和Nemenyi检验。