当前位置：首页 > news >正文

统计学习方法概论（综合数据挖掘概论）

news 来源：原创 2024/4/29 16:10:05

1.1 统计学习

统计学习是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。

1.2 监督学习

统计学习由监督学习、非监督学习、半监督学习和强化学习等组成。本文只讨论监督学习。

关键词汇：

1、输入空间 input space（样本空间 sample space、属性空间 attribute space、特征空间 feature space）：
输入的所有可能取值的集合。有时假设输入空间与特征空间为不同的空间，将实例从输入空间映射到特征空间。

2、输出空间 output space（标记空间 label space）：
输出的所有可能取值的集合

3、实例 instance（示例 instance、特征向量 feature vector）：
一条记录或一行具体的输入

4、样本 sample（样例 example）：
输入与输出对或拥有了标记信息的示例

5、特征值 feature value（属性值 attribute value）：
特征上的取值

不同的预测任务：

回归：输出为连续变量的预测问题
分类：输出为有限个离散变量的预测问题
标记：输入变量与输出变量均为变量序列的预测问题

联合概率分布：

监督学习假设输入与输出的随机变量$X$和$Y$遵循联合概率分布$P(X,Y)$，$P(X,Y)$表示分布函数，或分布密度函数。注意，在学习过程中，假定这一联合概率分布存在，但对学习系统来说，联合概率分布的具体定义是未知的。训练数据与测试数据被看作是依联合概率分布$P(X,Y)$独立同分布产生的。统计学习假设数据存在一定的统计规律，$X$和$Y$具有联合概率分布的假设就是监督学习关于数据的基本假设。

假设空间：

监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。换句话说，学习的目的就在于找到最好的这样的模型。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间（hypothesis space）。
监督学习的模型可以是概率模型或非概率模型，由条件概率分布$P(Y|X)$或决策函数$Y=f(X)$表示，随具体学习方法而定。对具体的输入进行相应的输出预测时，写作$P(y|x)$和$y=f(x)$
需注意的是，现实问题中我们常面临很大的假设空间，但学习过程是基于有限样本训练集进行的，因此，可能有多个假设与训练集一致，即存在着一个与训练集一致的“假设集合”，我们称之为“版本空间”（version space）。
我们可以通过归纳偏好选择版本空间中的一个假设作为模型。归纳偏好可看作学习算法自身一个可能很庞大的假设空间中队假设进行选择的启发式或“价值观”。那么，有没有一般性的原则来引导算法确立“正确的”偏好呢？“奥卡姆剃刀”（Occam's razor）是一种常用的、自然科学研究中最基本的原则，即“若有多个假设与观察一致，则选最简单的那个”。

1.3 统计学习三要素

统计学习方法都是有模型、策略和算法构成的，即统计学习方法由三要素构成，可以简单地表示为

方法 = 模型 + 策略 + 算法

1.3.1 模型

统计学习首要考虑的问题是学习什么样的模型。在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。例如，假设决策函数是输入变量的线性函数，那么模型的假设空间就是所有这些线性函数构成的函数集合。假设空间中的模型一般有无穷多个。

$F=\{f | Y=f(X)\}$或$F=\{P | P(Y|X)\}$

1.3.2 策略

有了模型的假设空间，统计学习接着需要考虑的是按照什么样的准则学习或选择最优的模型。统计学习的目标在于从假设空间中选取最优模型。
首先引入损失函数与风险函数的概念。损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。

1、损失函数和风险函数

用一个损失函数（loss function）或代价函数（cost function）来度量预测错误的程度。损失函数是$f(X)$和Y的非负实数值函数，记作$L(Y,f(X))$。
统计学习常用的损失函数有以下几种：
（1）0-1损失函数（0-1 loss function）

$L(Y,f(X))=\left\{
\begin{aligned}
1, &&Y\neq f(X) \\
0, &&Y=f(X)
\end{aligned}
\right.$

（2）平方损失函数（quadratic loss function）

$L(Y,f(X))=(Y-f(X))^{2}$

（3）绝对损失函数（absolute loss function）

$L(Y,f(X))=|Y-f(X))|$

（4）对数损失函数（log loss function）或对数似然损失函数（log-likelihood loss function）

$L(Y,P(Y|X))=-\log P(Y|X)$

损失函数值越小，模型就越好。由于模型的输入、输出$(X,Y)$是随机标量，遵循联合分布$P(X,Y)$，所以损失函数的期望是

$R_{exp}(f)=E_{p}[L(Y,F(x))]=\int_{\chi\times\gamma}L(y,f(x))P(x,y)dxdy$

这是理论上模型$f(X)$关于联合分布$P(X,Y)$的平均意义下的损失，称为风险函数（risk function）或期望损失（expected loss）
学习的目标就是选择期望风险最小的模型。由于联合分布$P(X,Y)$是未知的，$R_{exp}(f)$不能直接计算。这样一来，一方面根据期望风险最小学习模型要用到联合分布，另一方面联合分布又是未知的，所以监督学习就成为一个病态问题。

2、经验风险最小化与结构风险最小化

在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数式就可以确定：

$R_{emp}(f)=\frac{1}{N}\sum_{i=1}^{N}L(y_{i},f(x_{i}))$

根据大数定律，当样本容量N趋于无穷时，经验风险$R_{emp}(f)$趋于期望风险$R_{exp}(f)$。经验风险最小化（ERM）的策略认为，经验风险最小的模型就是最优的模型。根据这一策略，按照经验封校最小化求最优模型就是求解最优化问题：

$\min_{f\in F} \frac{1}{N}\sum_{i=1}^{N}L(y_{i},f(x_{i}))$

其中，$F$是假设空间。
当样本容量足够大时，经验风险最小化能保证有很好的学习效果，在现实被广泛采用。比如，极大似然估计就是经验风险最小化的一个例子。
但是，当样本容量很小时，经验风险最小化学习的效果就未必很好，会产生“过拟合”现象。

结构风险最小化（SRM）是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化。结构风险在经验风险上加上表示模型复杂度的正则化项或罚项。在假设空间、损失函数以及训练数据集确定的情况下，结构风险的定义是：

$R_{SRM}(f)=\frac{1}{N}\sum_{i=1}^{N}L(y_{i},f(x_{i}))+\lambda J(f)$

其中$J(f)$为模型的复杂度，是定义在假设空间$F$上的泛函。模型$f$越复杂，复杂度$J(f)$就越大；反制，模型$f$越简单，复杂度$J(f)$就越小。也就是说，复杂度表示了对复杂模型的惩罚。$\lambda\geq 0$是系数，用以权衡经验风险和模型复杂度。结构风险小需要经验风险与模型复杂度同时小。结构风险小的模型往往对训练数据以及未知的测试数据都有较好的预测。
结构风险最小化的策略认为结构风险最小的模型是最优的模型。所以求最优模型，就是求解最优化的问题：

$\min_{f\in F} \frac{1}{N}\sum_{i=1}^{N}L(y_{i},f(x_{i}))+\lambda J(f)$

这样，监督学习问题就变成了经验风险或结构风险函数的最优化为题。这时经验或结构风险函数是最优化的目标函数。

1.3.3 算法

算法是指学习模型的具体计算方法。统计学习基于训练数据集，根据学习策略，从假设空间中选择最优模型，最优需要考虑用什么样的计算方法求解最优模型。

1.4 数据集

如何从数据集$D$产生训练集$S$和测试集$T$

1、留出法

“留出法”（hold-out）直接将数据集$D$划分为两个互斥的集合，其中一个集合作为训练集$S$，另一个作为测试集$T$，即$D=S\bigcup T$，$S\bigcap T=\varnothing$。在$S$上训练处模型后，用$T$来评估测试误差，作为对泛化误差的估计。

需要注意的问题：
1、训练集和测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。如果从采样的角度来看待数据集的划分过程，则保留类别比例的采样方式通常称为“分层采样”。
2、给定训练集和测试集的样本比例后，仍存在多种划分方式对初始数据集$D$进行分割。一般要采用若干次随机划分、重复进行试验评估后取平均值作为留出法的评估结果。

2、交叉验证法

“交叉验证法”（cross validation）先将数据集$D$划分为$k$个大小相似的互斥子集，即$D=D_{1}\bigcup D_{2}\bigcup\ldots\bigcup D_{k}$，$D_{i}\bigcap D_{j}=\varnothing (i\neq j)$。每个子集$D_{i}$都尽可能保持数据分布的一致性，即从$D$中通过分层采样得到。然后，每次用$k-1$个子集的并集作为训练集，余下的那个子集作为测试集；这样就可获得$k$组训练/测试集，从而可进行$k$次训练和测试，最终返回的是这$k$个测试结果的均值。显然，交叉验证法评估结果的稳定性和保真性在很大程度上取决于$k$的取值，为强调这一点，通常把交叉验证法称为“k折交叉验证”（k-fold cross validation）。$k$最常用的取值是10，其他常用的取值有5、20等。

与留出法相似，将数据集$D$划分为$k$个子集同样存在多种划分方式。为减小因样本划分不同而引入的差别，$k$折交叉验证通常要随机使用不同的划分重复$p$次，最终的评估结果是这$p$次$k$折交叉验证结果的均值，例如常见的有“10次10折交叉验证”。

3、留一法

留一法（Leave-One-Out）是交叉验证法的特殊情况。当$k=m$时（$m$为样本总数），就得到了留一法。留一法虽然结果更加准确，但计算开销却非常大。

4、自助法

自助法（bootstrapping）直接以自助采样法（bootstrap sampling）为基础。给定包含$m$个样本的数据集$D$，我们对它进行采样产生数据集$D^{'}$：每次随机从$D$中挑选一个样本，将其拷贝放入$D^{'}$，然后再将该样本放回初始数据集$D$中，使得该样本在下次采样时仍有可能被采集到；这个过程重复$m$次后，我们就得到了包含$m$个样本的数据集$D^{'}$，这就是自助采样的结果。显然，$D$中有一部分样本会在$D^{'}$中多次出现，而另一部分样本不出现。可以做一个简单的估计，样本在$m$次采样中始终不被采到的概率是$(1-\frac{1}{m})^{m}$，取极限得到

$$\lim_{m\rightarrow\infty}(1-\frac{1}{m})^{m} \longrightarrow \frac{1}{e} \approx 0.368$$

自助法在数据集较小、难以有效划分训练集和测试集时很有用；此外，自助法能从初始数据集中产生多个不同的训练集，这对集成学习等方法由很大的好处。然而，自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差。因此，在初始数据量足够时，留出法和交叉验证法更常用一些。

1.5 模型评估与模型选择

1.5.1 训练误差与测试误差

统计学习的目的是使学到的模型不仅对已知数据而且对未知数据都能有很好的预测能力。不同的学习方法会给出不同的模型。当损失函数给定时，基于损失函数的模型的训练误差和测试误差就自然成为学习方法评估的标准。

假设学习到的模型是$Y=f(X)$,训练误差是模型$Y=f(X)$关于训练数据集的平均损失：

$e_{train}=\frac{1}{N}\sum_{i=1}^{N}L(y_{i},f(x_{i}))$，其中$N$是训练样本容量

测试误差是模型$Y=f(X)$关于测试数据集的平均损失：

$e_{test}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}L(y_{i},f(x_{i}))$，其中$N^{'}$是测试样本容量

例如，当损失函数是0-1损失时，测试误差就变成了常见的测试数据集上的误差率（error rate）：

$e_{test}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}I(y_{i}\neq f(x_{i}))$

这里$I$是指示函数（indicator function），即$y\neq f(x_{i})$时为1，否则为0。

相应的常见的测试数据集上的准确率（accuracy）为

$r_{test}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}I(y_{i}= f(x_{i}))$

（注：虽然测试误差和训练误差的公式与经验风险一样，但两者概念不同，使用的场合也不同。在学习最优模型时，采用的策略可以是经验风险最小化或者结构风险最小化。但在评估模型时，计算测试误差和训练误差只能用经验风险的公式。）

1.5.2 过拟合与模型选择

1.5.3 查准率、查全率与F1

1、查准率、查全率

错误率和精度虽常用，但并不能满足所有的任务需求（模型评估）。

类似的需求在信息检索、Web搜索等应用中经常出现，例如在信息检索中，我们经常会关系“检索出的信息中有多少比例是用户感兴趣的”，“用户感兴趣的信息中有多少被检索出来了”。“查准率” （precision）与“查全率”（recall）是更为适用于此类需求的性能度量。

查准率 precision（精确率、精度）： $P=\large{\frac{TP}{TP+FP}}$

查全率 recall（召回率）：$R=\large{\frac{TP}{TP+FN}}$

查准率和查全率是一对矛盾的度量。一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低。

2、P-R曲线和F1

在很多情形下，我们可根据学习器的预测结果对样例进行排序，排在前面的是学习器认为“最可能”是正例的样本，排在最后的则是学习器认为“最不可能”是正例的样本。按此信息逐个把样本作为正例进行预测，则每次可以计算出当前的查全率、查准率。以查准率为纵轴、查全率为横轴作图，就得到了查准率-查全率曲线，简称“P-R曲线”，显示该曲线的图称为“R-P图”。

若一个学习器的P-R曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者，例如图中学习器A的性能优于学习器C；如果两个学习器的P-R曲线发生了交叉，例如图中的A与B，则难以一般性地断言两者孰优孰劣，只能在具体的查准率或查全率条件下进行比较。然而，在很多情形下，人们往往仍希望把学习器A与B比出个高低，这时一个比较合理的判据是比较P-R曲线下面积的大小，它在一定程度上表征了学习器在查准率和查全率上取得相对“双高”的比例。但这个值不太容易估算。因此，人们设计了一些综合考虑查准率、查全率的性能度量。

“平衡点”（BEP）就是这样一个度量它是“查准率=查全率”时的取值，例如图中学习器C的BEP是0.64，而基于BEP的比较，可认为学习器A优于B。

但BEP还是过于简化了些，更常用的是F1度量：

$F1=\large{\frac{2\times P\times R}{P+R}}=\large{\frac{2\times TP}{样例总数+TP-TN}}$

3、不平衡类问题 $F_{\beta}$

在一些应用中，对查准率和查全率的重视程度有所不同。例如在商品推荐系统中，为了尽可能少打扰用户，更希望推荐内容确是用户感兴趣的，此时查准率更重要；而在逃犯信息检索系统中，更希望尽可能少漏掉逃犯，此时查全率更重要。$F1$度量的一般形式——$F_{\beta}$，能让我们表达出对查准率/查全率的不同偏好，它定义为

$$F_{\beta}=\large{\frac{(1+\beta^{2})\times P\times R}{(\beta^{2}\times P)+R}}$$

其中$\beta>0$度量了查全率对查准率的相对重要性。$\beta=1$时退化为标准的$F1$；$\beta>1$时查全率有更大影响；$\beta<1$时查准率有更大影响。

很多时候我们有多个二分类混淆矩阵，例如进行多次训练/测试，每次得到一个混淆矩阵；或是在多个数据集上进行训练/测试，希望估计算法的“全局”性能；甚或是执行多分类任务……总之，我们希望在n个二分类混淆矩阵上综合考察查准率和查全率。

一种直接的做法是先在各混淆矩阵上分别计算出查准率和查全率，再计算平均值，这样就得到“宏查准率”和“宏查全率”，再以此计算相应的“宏F1”

另一种就是先将各混淆矩阵的对应元素进行平均，得到$TP$、$FP$、$TN$、$FN$的平均值，分别记为$\overline{TP}$、$\overline{FP}$、$\overline{TN}$、$\overline{FN}$，再基于这些平均值计算出“微查准率”和“微查全率”，再以此计算相应的“微F1”。

1.5.4 ROC与AOC

很多学习器是为测试样本产生一个实值或概率预测，然后将这个预测值与个分类阈值（threshold）进行比较，若大于阈值则分为正类，否则为反类。例如，神经网络在一般情形下是对每个测试样本预测出一个[ 0.0，1.0 ]之间的实值，然后将这个值与0.5进行比较，大于0.5则判为正例，否则为反例。这个实值或概率预测结果的好坏，直接决定了学习器的泛化能力。实际上，根据这个实值或概率预测结果，我们可将测试样本进行排序，“最可能”是正例的排在最前面，“最不可能”是正例的排在最后面。这样，分类过程就相当于在这个排序中以某个“截断点”（cut point）将样本分为两部分，前一部分判作正例，后一部分则判作反例。

在不同的应用任务中，我们可根据任务需求来采用不同的截断点。例如若我们更重视“查准率” ，则可选择排序中靠前的位置进行截断；若更重视“查全率”，则可选择靠后的位置进行截断。因此，排序本身的质量好坏，体现了综合考虑学习器在不同任务下的“期望泛化性能”的好坏，或者说，“一般情况下”泛化性能的好坏。ROC曲线则是从这个角度出发来研究学习器泛化性能的有力工具。（画法与P-R曲线相似）

ROC曲线的纵轴是“真正例率”（TPR），横轴是“假正例率”（FPR），两者分别定义为：

$TPR=\large{\frac{TP}{TP+FN}}$ 和 $FPR=\large{\frac{FP}{TN+FP}}$

进行学习器的比较时，与P-R图相似，若一个学习器的ROC曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者；若两个学习器的ROC曲线发生交叉，则难以一般性断言两者孰优孰劣。此时如果一定要进行比较，则较为合理的判据是比较ROC曲线下的面积，即AUC。

$$AUC=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_{i})(y_{i}+y_{i+1})$$

形式化地看，AUC考虑的是样本预测的排序质量，因此它与排序误差有紧密联系。给定$m^{+}$个正例和$m^{-}$个反例，令$D^{+}$和$D^{-}$分别表示正、反例集合，则排序“损失”定义为：

$$l_{rank}=\large{\frac{1}{m^{+}m^{-}}\sum_{x^{+}\in D^{+}}\sum_{x^{-}\in D^{-}}}\Big(I(f(x^{+})<f(x^{-}))+\frac{1}{2}I(f(x^{+})=f(x^{-}))\Big)$$

即考虑每一对正、反例，若正例的预测值小于反例，则记一个“罚分”，若相等，则记0.5个“罚分”。容易看出，$l_{rank}$对应的是ROC曲线之上的面积：若一个正例在ROC曲线上对应标记的坐标为$(x,y)$，则$x$恰是排序在其之前的反例所占的比例，即假正例率。因此有：

$$AUC=1-l_{rank}$$

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

在现实任务中常会遇到这样的情况：不同类型的错误所造成的后果不同。例如在医疗诊断中，错误地把患者诊断为健康人与错误地把健康人诊断为患者，看起来都是犯了“一次错误”，但后者的影响是增加了进一步检查的麻烦，前者的后果却可能是丧失了拯救生命的最佳时机。为权衡不同类型错误所造成的不同损失，可为错误赋予“非均等代价”（unequal cost）。

以二分类任务为例，我们可根据任务的领域知识设定一个“代价矩阵”（cost matrix），如下表所示，其中$cost_{ij}$表示将第$i$类样本预测为第$j$类样本的代价。一般来说，$cost_{ii}=0$；若将第0类判别为第1类所造成的损失更大，则$cost_{01}>cost_{10}$；损失程度相差越大，$cost_{01}$与$cost_{10}$值的差别越大。

回顾前面介绍的一些性能度量可看出，它们大都隐式地假设了均等代价，例如错误率是直接计算“错误次数”，并没有考虑不同错误会造成的不同的后果。在非均等代价下，我们所希望的不再是简单地最小化错误次数，而是希望最小化“总体代价”（total cost）。“代价敏感”错误率为

$$E(f;D;cost)=\frac{1}{m}\Big(\sum_{x_{i}\in D^{+}}I(f(x_{i})\neq y_{i})\times cost_{01} + \sum_{x_{i}\in D^{-}}I(f(x_{i})\neq y_{i})\times cost_{10} \Big)$$

类似的，可给出基于分布定义的代价敏感错误率，以及其他一些性能度量如精度的代价敏感版本。若令$cost_{ij}$中的$i$、$j$取值不限于0、1，则可定义出多分类任务的代价敏感性能度量。

在非均等代价下，ROC曲线不能直接反映出学习器的期望总体代价，而“代价曲线”（cost curve）则可达到该目的。代价曲线图的横轴是取值为[0,1]的正例概率代价

$$P(+)cost=\large{\frac{p\times cost_{01}}{p\times cost_{01}+(1-p)\times cost_{10}}}$$

其中$p$是样例为正例的概率。纵轴是取值为[0,1]的归一化代价

$$cost_{norm}=\large{\frac{FNR\times p\times cost_{01}+FPR\times (1-p)\times cost_{10}}{p\times cost_{01}+(1-p)\times cost_{10}}}$$

其中FPR是假正例率，FNR=1-TPR是假反例率。代价曲线的绘制很简单：ROC曲线上每一点对应了代价平面上的一条线段，设ROC曲线上点的坐标为（FPR，TPR），则可相应计算出FNR，然后在代价平面上绘制一条从（0，FPR）到（1，FNR）的线段，线段下的面积即表示了该条件下的期望总体代价；如此将ROC曲线上的每个点转行为代价平面上的一条线段，然后取所有线段的下界，围成的面积即为在所有条件下学习器的期望总体代价，如图所示。

1.5.4 比较检验

有了实验评估方法和性能度量，看起来就能对学习器的性能进行评估比较了：先使用某种实验评估方法测得学习器的某个性能度量结果，然后对这些结果进行比较。但怎么来做这个“比较”呢？是直接取得性能度量的值然后“比大小”吗？实际上，机器学习中性能比较这件事要比大家想象的复杂得多。这里面涉及几个重要因素：
1、我们希望比较的是泛化性能，然而通过实验评估方法我们获得的是测试集上的性能，两者的对比结果可能未必相同；
2、测试集上的性能与测试集本身的选择有很大关系，且不论使用不同大小的测试集会得到不同的结果，即便用相同大小的测试集，若包含的测试样例不同，测试结果也会有不同；
3、很多机器学习算法本身有一定的随机性，即便用相同的参数设置在同一个测试集上多次运行，其结果也会有不同。

简而言之，试验评估方法主要侧重于测试集上的性能，为了真正比较学习器的泛化性能，我们可以采用“统计假设检验”（hypothesis test）方法。基于假设检验结果我们可推断出，若在测试集上观察到学习器A比B好，则A的泛化性能是否在统计意义上优于B，以及这个结论的把握有多大。

1、二项检验

泛化错误率为$e$的学习器在一个样本上犯错的概率是$e$；测试错误率$\hat{e}$意味着在$m$个测试样本中恰有$\hat{e}\times m$个被误分类。由此可估算出其恰将$\hat{e}\times m$个样本误分类的概率如下式所示，这也表达了在包含$m$个样本的测试集上，泛化错误率为$e$的学习器被测得测试错误率为$\hat{e}$的概率：

$$P(\hat{e};e)=\large{{m\choose \hat{e}\times m}e^{\hat{e}\times m}(1-e)^{m-\hat{e}\times m}}$$

给定测试错误率，则解得$P(\hat{e};e)$在$e=\hat{e}$时最大，$|e-\hat{e}|$增大时$P(\hat{e};e)$减小。这符合二项分布，如下图所示，若$e=0.3$，则10个样本中测得3个被误分类的概率最大。

我们可使用“二项检验”（binomial test）来对“$e\leq 0.3$”（即“泛化错误率是否不大于0.3”）这样的假设进行检验。更一般的，考虑假设“e\leq e_{0}”，则在$1-\alpha$的概率内所能观测到的最大错误率如下式计算。这里$1-\alpha$反映了结论的“置信度”（confidence），直观地来看，相应于上图非阴影部分的范围。

$$\bar{e}=\max e\quad s.t.\quad \large{\sum^{m}_{i=e_{0}\times m+1}}{m\choose i}e^{i}(1-e)^{m-i}$$

此时若测试错误率$\hat{e}$小于临界值$\bar{e}$，则根据二项检验可得出结论：在$\alpha$的显著度下，假设“$e\leq e_{0}$”不能被拒绝，即能以$1-\alpha$的置信度任务，学习器的泛化错误率不大于$e_{0}$；否则该假设可被拒绝，即在$\alpha$的显著度下可任务学习器的泛化错误率大于$e_{0}$。

2、t检验

在很多时候我们并非仅做一次留出法估计，而是通过多次重复留出法或是交叉验证法等进行多次训练/测试，这样会得到多个测试错误率，此时可使用“t检验”（t-test）。假定我们得到了$k$个测试错误率，$\hat{e}_{1}$，$\hat{e}_{2}$，……，$\hat{e}_{k}$，则平均测试错误率$\mu$和方差$\sigma^{2}$为

$$\large{\mu=\frac{1}{k}\sum_{i=1}^{k}\hat{e}_{i}}$$

$$\large{\sigma^{2}=\frac{1}{k-1}\sum^{k}_{i=1}(\hat{e}_{i}-\mu)^{2}}$$

考虑到这$k$个测试错误率可看作泛化错误率$e_{0}$的独立采样，则

$$\large{\tau_{t}=\frac{\sqrt{k}(\mu-e_{0})}{\sigma}}$$

服从自由度为$k-1$的$t$分布，如图所示。

对假设“$\mu=e_{0}$”和显著度$\alpha$，我们可计算出当测试错误率均值为$e_{0}$时，在$1-\alpha$概率内能观测到的最大错误率，即临界值。若平均错误率$\mu$与$e_{0}$之差$\mu-e_{0}$位于临界值范围$[t_{-\alpha/2},t_{\alpha/2}]$内，则不能拒绝假设“$u=e_{0}$”，即可任务泛化错误率为$e_{0}$，置信度为$1-\alpha$；否则可拒绝该假设。$\alpha$常用取值有0.05和0.1。下表给出了一些常用临界值。

“二项检验”和“t检验”都是对关于单个学习器泛化性能的假设进行检验，而在现实任务中，更多时候我们需对不同学习器的性能进行比较，下面将介绍适用于此类情况的假设检验方法。

3、交叉验证t检验

对两个学习器A和B，我们可用k折交叉验证“成对t检验”来进行比较检验。这里的基本思想是若两个学习器的性能相同，则它们使用相同的训练/测试集得到的测试错误率应相同，即$e^{A}_{i}=e^{B}_{i}$。

具体来说，对k折交叉验证产生的k对测试错误率：先对每对结果求差，$\Delta_{i}=e^{A}_{i}-e^{B}_{i}$；若两个学习器性能相同，则差值均值因为零。因此，可根据差值$\Delta_{1}$，$\Delta_{1}$，……，$\Delta_{k}$来对“学习器A与B性能相同”这个假设做t检验，计算出差值的均值$\mu$和方差$\sigma^{2}$，在显著度$\alpha$下，若变量

$$\large{\tau_{t}=|\frac{\sqrt{k}\mu}{\sigma}|}$$

小于临界值$t_{\alpha/2,k-1}$，则假设不能被拒绝，即认为两个学习器的性能没有显著差别；否则可认为两个学习器的性能有显著差别，且平均错误率较小的那个学习器性能较优。（这里可参考t检验）

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

5×2交叉验证是做5次2折交叉验证，在每次2折交叉验证之前随机将数据打乱，使得5次交叉验证中的数据划分不重复。对两个学习器A和B，第$i$次2折交叉验证将产生两队测试错误率，我们对它们分别求差，得到第1折上的差值$\Delta_{i}^{1}$和第2折上的差值$\Delta_{i}^{2}$.为缓解测试错误率的非独立性，我们仅计算第1次2折交叉验证的两个结果的平均值$\mu=0.5(\Delta_{1}^{1}+\Delta_{1}^{2})$，但对每次2折实验的结果都计算出其方差$\sigma^{2}_{i}=(\Delta^{1}_{i}-\frac{\Delta^{1}_{i}+\Delta^{2}_{i}}{2})^{2}+(\Delta^{2}_{i}-\frac{\Delta^{1}_{i}+\Delta^{2}_{i}}{2})^{2}$。变量

$$\large{\tau_{t}=\frac{\mu}{\sqrt{0.2\sum_{i=1}^{5}\sigma^{2}_{i}}}}$$

服从自由度为5的t分布，其双边检验的临界值$t_{\alpha/2,5}$当$\alpha=0.05$时为2.5706，$\alpha=0.1$时为2.0150。

4、McNemar检验

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

若我们做的假设是两学习器性能相同，则应用$e_{01}=e_{10}$，那么变量$|e_{01}-e_{10}|$应当服从正态分布。McNemar检验考虑变量

$$\large{\tau_{\chi^{2}}=\frac{(|e_{01}-e_{10}|-1)^{2}}{e_{01}+e_{10}}}$$

服从自由度为1的$\chi^{2}$分布，即标准正态分布变量的平方。给定显著度$\alpha$，当以上变量值小于临界值$\chi^{2}_{\alpha}$时，不能拒绝原假设，即认为两学习器的性能没有显著差别；否则拒绝假设，即认为两者性能有显著差别，且平均错误率较小的那个学习器性能较优。自由度为1的$\chi^{2}$检验的临界值当$\alpha=0.05$时为$3.8415$，$\alpha=0.1$时为$2.7055$。

4、Feiedman检验与Nemenyi后续检验

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

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

然后，使用Friedman检验来判断这些算法是否性能都相同。若相同，则它们的平均序值应当相同。假定我们在N个数据集上比较k个算法，令$r_{i}$表示第$i$个算法的平均序值。为简化讨论，暂不考虑平分序值的情况，则$r_{i}$的均值和方差分别为$(k+1)/2$和$(k^{2}-1)/12$。变量

$$\tau_{\chi^{2}} = \frac{k-1}{k}*\frac{12N}{k^{2}-1}\sum^{k}_{i=1}(r_{i}-\frac{k+1}{2})^{2}$$

$$= \frac{12N}{k(k+1)}(\sum_{i=1}^{k}r^{2}_{i}\frac{k(k+1)^{2}}{4})$$

在$k$和$N$都较大时，服从自由度为$k-1$的$\chi^{2}$分布。

然而，上述这样的“原始Friedman检验”过于保守，现在通常使用变量

$$\tau_{F}=\frac{(N-1)\tau_{\chi^{2}}}{N(k-1)-\tau_{\chi^{2}}}$$

其中$\tau_{\chi^{2}}$由上式得到。$\tau_{F}$服从自由度为$k-1$和$(k-1)(N-1)$的$F$分布，下表给出了一些常用临界值。