Note of Machine Learning 2

第2章　模型评估与选择

2.1　经验误差与过拟合

错误率(error rate) and 精度(accuracy)：分类错误的样本数占样本总数的比例称为“错误率”，如果在m个样本中有a个样本分类错误，则错误率E=a/m；相应的1-a/m称为“精度”。

误差(error)：学习器的实际预测输出与样本的真实输出之间的差异。

训练误差(training error) or 经验误差(empirical error)：学习器在训练集上的误差。

泛化误差(generalization error)：学习器在新样本上的误差。

过拟合(overfitting) and 欠拟合(underfitting)：学习器把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，导致泛化性能下降的现象称为“过拟合”，相对的，“欠拟合”指对训练样本的一般性质尚未学好。

欠拟合比较容易克服，过拟合是机器学习面临的关键障碍。过拟合是无法彻底避免的，只能减小其风险。可以这样理解：机器学习面临的问题通常是NP难甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获最优解，这就意味着我们构造性地证明了“P=NP”；因此，只要相信”P$\neq​$NP“，过拟合就不可避免。

模型选择(model selection)：现实任务中，往往有多种学习算法可供选择，对同一个学习算法，使用不同的参数配置时，也会产生不同的模型。选用哪一个学习算法、使用哪一种参数配置的问题，称为”模型选择“问题。

2.2　评估方法

通常，我们可通过实验测试来对学习器的泛化误差进行评估并进而做出选择。为此，需使用一个“测试集”(testing set)来测试学习器对新样本的判别能力，然后以测试集上的“测试误差”(testing error)作为泛化误差的近似。

测试集应尽可能与训练集互斥。有一个包含m个样例的数据集D = {(x₁,y₁),(x₂,y₂),…,(x_m,y_m)}，通过对D进行适当的处理，从中产生训练集S和测试集T。下面介绍几种常见做法。

2.2.1　留出法

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

需注意的是，训练/测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。

另一个需注意的问题是，即便在给定训练/测试集的样本比例后，仍存在多种划分方式对初始数据集D进行分割。因此，单次留出法得到的估计结果往往不够稳定可靠，在使用留出法时，一般要采用若干次随机划分，重复进行实验评估后取平均值作为留出法的评估结果。

留出法会导致一个窘境：若令训练集S包含绝大多数样本，则训练出的模型可能更接近于用D训练出的模型，但由于T比较小，评估结果可能不够稳定准确；若令测试集T多包含一些样本，则训练集S与D差别更大了，被评估的模型与用D训练出的模型相比可能有较大差别，从而降低了评估结果的保真性(fidelity)。这个问题没有完美的解决方案。

2.2.2　交叉验证法

交叉验证法(cross validation)：先将数据集D划分为k个大小相似的互斥子集，即D = D₁ $\cup$ D₂ $\cup$ … $\cup$ D_k，D_i $\cap$ D_j = $\varnothing$ (i$\neq$j)。每个子集D_i都尽可能保持数据分布的一致性，即从D中通过分层采样得到。然后，每次用k - 1个子集的并集作为训练集，余下的那个子集作为测试集；这样就可获得k组训练/测试集，从而可进行k次训练和测试，最终返回的是这k个测试结果的均值。

显然，交叉验证法评估结果的稳定性和保真性在很大程度上取决于k的取值，为强调这一点，通常把交叉验证法称为“k折交叉验证”(k-fold cross validation)。

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

假定数据集D中包含m个样本，若令k = m，则得到了交叉验证法的一个特例：留一法(Leave-One-Out，简称LOO)。留一法结果比较准确，但数据集比较大时，计算开销难以忍受。

2.2.3　自助法

自助法(bootstrapping)：给定包含m个样本的数据集D，对它进行采样产生数据集D’：每次随机从D中挑选一个样本，将其拷贝放入D‘，然后再将该样本放回初始数据集D中；这个过程重复执行m次，得到包含m个样本的数据集D’。样本在m次采样中始终不被采到的概率是

$$lim_{m\rightarrow\infty}(1-\frac{1}{m})^m=\frac{1}{e}\approx0.368　　　　　(2.1)$$

即通过自助采样，初始数据集D中约有36.8%的样本未出现在采样数据集D’中。将D’用作训练集，D\D’用作测试集；这样的测试结果，亦称“包外估计”(out-of-bagestimate)。

自助法在数据集较小、难以有效划分训练/测试集时很有用，但会引入估计偏差。初始数据量足够时，留出法和交叉验证法更常用一些。

2.2.4　调参与最终模型

大多数学习算法都有些参数(parameter)需要设定，在进行模型评估与选择时，除了要对适用学习算法进行选择，还需对算法参数进行设定，这就是“调参”(parameter tuning)。

通常把学得模型在实际使用中遇到的数据称为测试数据，模型评估与选择中用于评估测试的数据集常称为“验证集”(validation set)。

2.3　性能度量

对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量(performance measure)。

在预测任务中，给定样例集D = {(x₁,y₁),(x₂,y₂),…,(x_m,y_m)}，其中y_i是示例x_i的真实标记。要评估学习器f的性能，就要把学习器预测结果f(x)与真实标记y进行比较。

回归任务最常用的性能度量是“均方误差”(mean squared error)

$$E(f;D)=\frac{1}{m}\sum_{i=1}^{m}(f(x_i)-y_i)^2.　　　　　(2.2)$$

更一般的，对于数据分布$\mathcal{D}$和概率密度函数p($\cdot$)，均方误差可描述为

$$E(f;\mathcal{D})=\int_{x\sim\mathcal{D}}(f(x)-y)^2p(x)dx.　　　　　(2.3)$$

下面介绍分类任务中常用的性能度量。

2.3.1　错误率与精度

错误率是分类错误的样本占样本总数的比例，精度则是分类正确的样本数占样本总数的比例。对样例集D，分类错误率定义为

$$E(f;D)=\frac{1}{m}\sum_{i=1}^{m}\mathbb{I}(f(x_i\neq y_i)).　　　　　(2.4)$$

精度则定义为

$$\begin{aligned} acc(f;D)&=\frac{1}{m}\sum_{i=1}^m\mathbb{I}(f(x_i)=y_i)　　　　　(2.5)\\ &=1-E(f;D). \end{aligned}$$

更一般的，对于数据分布$\mathcal{D}$和概率密度函数p($\cdot$)，错误率与精度可分别描述为

$$E(f;\mathcal{D})=\int_{x\sim\mathcal{D}}\mathbb{I}(f(x)\neq y)p(x)dx,　　　　　(2.6)$$ $$\begin{aligned} acc(f;\mathcal{D})&=\int_{x\sim\mathcal{D}}\mathbb{I}(f(x)=y)p(x)dx,　　　　　(2.7)\\ &=1-E(f;\mathcal{D}) \end{aligned}$$

2.3.2　查准率、查全率与F1

错误率与精度不能满足所有任务需求，因此引入“查准率”(precision)与“查全率”(recall)。

对于二分类问题，可将样例根据其真实类别与学习器预测类别的组合划分为真正例(true positive)、假正例(false positive)、真反例(true negative)、假反例(false negative)，令TP、FP、TN、FN分别表示其对应的样例数，则显然后TP+FP+TN+FN=样例总数。分类结果的“混淆矩阵”(confusion matrix)如下

查准率P与查全率R分别定义为

$$P=\frac{TP}{TP+FP},　　　　　(2.8)\\ R=\frac{TP}{TP+FN}.　　　　　(2.9)$$

查准率和查全率是一对矛盾的度量。根据学习器的预测结果对样例进行排序，逐个把样本作为正例进行预测，则每次可以计算出当前的查全率、查准率。以查准率为纵轴，查全率为横轴作图，就得到了“P-R曲线“。

”平衡点“(Break-Even Point，简称BEP)是”查准率=查全率“时的取值，用于度量学习器的优劣。

F1度量：

$$F1=\frac{2\times P\times R}{P+R}=\frac{2\times TP}{样例总数+TP-TN}.　　　　　(2.10)$$

F1度量的一般形式——F_$\beta$，能表达出对查准率、查全率的不同偏好：

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

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

有多个混淆矩阵时，一种做法是在各混淆矩阵上分别计算出查准率和查全率，再计算平均值，得到”宏查准率“(macro-P)、”宏查全率“(macro-R)，”宏F1”(macro-F1)：

$$macroP=\frac{1}{n}\sum_{i=1}^nP_i,　　　　　(2.12)\\ macroR=\frac{1}{n}\sum_{i=1}^nR_i,　　　　　(2.13)\\ macroF1=\frac{2\times macroP\times macroR}{macroP+macroR}.　　　　　(2.14)$$

还可先将各混淆矩阵的对应元素进行平均，再基于这些平均值计算出“微查准率”(micro-P)、“微查全率”(micro-R)和“微F1”(micro-F1)。

$$microP=\frac{\overline{TP}}{\overline{TP}+\overline{FP}},　　　　　(2.15)\\ microR=\frac{\overline{TP}}{\overline{TP}+\overline{FN}},　　　　　(2.16)\\ microF1=\frac{2\times microP\times microR}{microP+microR}.　　　　　(2.17)$$

2.3.3　ROC与AUC

ROC全称“受试者工作特征”(Receiver Operating Characteristic)曲线。以“真正利率”(True Positive Rata，简称TPR)为纵轴，“假正例率”(False Positive Rate，简称FPR)为横轴，两者分别定义为：

$$TPR=\frac{TP}{TP+FN},　　　　　(2.18)\\ FPR=\frac{FP}{TN+FP}.　　　　　(2.19)$$

现实任务中测试样例有限，无法产生光滑ROC曲线，只能绘制出近似ROC曲线。

AUC(Area Under ROC Curve)，即ROC曲线下的面积，用于比较学习器的优劣，可估算为：

$$AUC=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_i)\cdot(y_i+y_{i+1}).　　　　　(2.20)$$

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

$$\mathscr{L}_{rank}=\frac{1}{m^+m^-}\sum_{x^+\in D^+}\sum_{x^-\in D^-}(\mathbb{I}(f(x^+)<f(x^-))+\frac{1}{2}\mathbb{I}(f(x^+)=f(x^-))),　　　　　(2.21)$$

容易看出$\mathscr{L_{rank}}$对应的是ROC曲线之上的面积，有

$$AUC=1-\mathscr{L}_{rank}.　　　　　(2.22)$$

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

不同类型的错误造成的后果不同。根据任务的领域知识设定一个“代价矩阵”(cost matrix)，其中cost_ij表示将第i类样本预测为第j类样本的代价。

非均等代价下，希望最小化“总体代价”(total cost)。若将上表中第0类中作为正类，第1类作为反类，另D⁺与D^-分别代表样例集D的正例子集和反例子集，则“代价敏感”(cost-sensitive)错误率为：

$$E(f;D;cost)=\frac{1}{m}(\sum_{x_i\in D^+}\mathbb{I}(f(x_i)\neq y_i)\times cost_{01}+\sum_{x_i\in D^-}\mathbb{I}(f(x_i)\neq y_i)\times cost_{10}).　　　　　(2.23)$$

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

$$P(+)cost=\frac{p\times cost_{01}}{p\times cost_{01}+(1-p)\times cost_{10}},　　　　　（2.24）$$

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

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

其中FPR是假正例率，FNR = 1 - TPR是假反例率。

代价曲线的绘制：ROC上每一点对应了代价平面上的一条线段，根据ROC的FPR计算出FNR，在代价平面上作从(0,FPR)到(1,FNR)的线段，线段下的面积表示了该条件下的期望总体代价；取所有线段的下界，就是在所有条件下学习器的期望总体代价。

2.4　比较检验

统计假设检验(hypothesis test)为学习器性能比较提供了重要依据。

下面介绍两种最基本的假设检验及几种常用的机器学习性能比较方法。默认错误率为性能度量，用$\epsilon$表示。

2.4.1　假设检验

可根据测试错误率估推出泛化错误率的分布。

泛化错误率为$\epsilon​$的学习器在一个样本上犯错的概率是$\epsilon​$；测试错误率$\widehat{\epsilon}​$意味着在m个测试样本中恰有$\widehat{\epsilon}\times m​$个被误分类。假定测试样本是从样本总体分布中独立采样而得，那么泛化错误率为$\epsilon​$的学习器将其中m’个样本误分类、其余样本全都分类正确的概率是$\left(\begin{array}{cc}m\m’\end{array}\right)\epsilon^{m’}(1-\epsilon)^{m-m’}​$；由此可估算出其恰将$\widehat{\epsilon}\times m​$个样本误分类的概率如下式所示，这也表达了在包含m个样本的测试集上，泛化错误率为$\epsilon​$的学习器被测得测试错误率为$\widehat{\epsilon}​$的概率：

$$P(\widehat{\epsilon};\epsilon)=\left(\begin{array}{cc}m\\\widehat{\epsilon}\times m\end{array}\right)\epsilon^{\widehat{\epsilon}\times m}(1-\epsilon)^{m-\widehat{\epsilon}\times m}.　　　　　(2.26)$$

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

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

$$\overline{\epsilon}=max\epsilon　s.t.　\sum_{i=\epsilon_0\times m+1}^m\left(\begin{array}{cc}m\\i\end{array}\right)\epsilon^i(1-\epsilon)^{m-i}<\alpha.　　　　　(2.27)$$

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

有多个测试错误率时使用“t检验”(t-test)。假定有k个测试错误率，则平均测试错误率$\mu$和方差$\sigma^2$为

$$\mu=\frac{1}{k}\sum_{i=1}^k\widehat{\epsilon_i},　　　　　(2.28)\\ \sigma^2=\frac{1}{k-1}\sum_{i=1}^k(\widehat{\epsilon_i}-\mu)^2.　　　　　(2.29)$$

考虑到这k个测试错误率可看作泛化错误率$\epsilon_0$的独立采样，则变量

$$\tau_t=\frac{\sqrt{k}(\mu-\epsilon_0)}{\sigma}　　　　　(2.30)$$

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

2.4.2　交叉验证t检验

对不同学习器的性能进行比较，可用k折交叉验证“成对t检验”(paired t-tests)来进行比较检验。这里的基本思想是若两个学习器的性能相同，则它们使用相同的训练/测试集得到的测试错误率应相同。

对k折交叉验证产生的k对测试错误率，先对每对结果求差，若两学习器性能相同，则差值均值应为零。因此可根据差值来对“两学习器性能相同”这个假设做t检验，计算出差值的均值$\mu$和方差$\sigma^2$，在显著度$\alpha$下，若变量

$$\tau_t=|\frac{\sqrt k\mu}{\sigma}|　　　　　(2.31)$$

小于临界值$t_{\alpha/2,k-1}$，则不能拒绝假设，否则可认为两个学习器性能有显著差别，平均错误率较小的那个学习器性能较好。

由于样本有限，不同轮次的训练集重叠会导致测试错误率并不独立，可采用”$5\times2$交叉验证“法。做5次2折交叉验证，第i次2折交叉验证产生两对测试错误率分别求差，计算第1次2折交叉验证的两个结果的平均值$\mu=0.5(\Delta_1^1+\Delta_1^2)$，但对每次2折实验的结果都计算方差$\sigma_i^2=(\Delta_i^1-\frac{\Delta_i^1+\Delta_i^2}{2})^2+(\Delta_i^2-\frac{\Delta_i^1+\Delta_i^2}{2})^2.$变量

$$\tau_t=\frac{\mu}{\sqrt{0.2\sum_{i=1}^5\sigma_i^2}}　　　　　(2.32)$$

服从自由度为5的t分布。

2.4.3　McNemar检验

对于二分类问题，使用留出法可获得两学习器分类结果的差别。如”列联表“(contingency table)所示。

若假设两学习器性能相同，则应有$e{01}=e{10}$，那么变量$|e{01}=e{10}|$应服从正态分布。McNemar检验考虑变量

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

服从自由度为1的$\chi^2$分布。给定显著度$\alpha$，当变量值小于临界值$\chi_\alpha^2$时不能拒绝假设，即认为两学习器性能无显著差别。

2.4.4　Friedman检验与Nemenyi后续检验

在一组数据集上对多个算法进行比较，使用基于算法排序的Friedman检验。假定用四个数据集对算法A、B、C进行比较，根据测试性能由好到坏排序，赋予序值1，2…；若算法测试性能相同，则平分序值。得到算法比较序值表。

然后用Friedman检验来判断这些算法是否性能都相同。假定在N个数据集上比较k个算法，令ri表示第i个算法的平均序值，则ri的均值和方差分别为(k+1)/2和($k^2$-1/12)。变量

$$\begin{aligned} \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}^kr_i^2-\frac{k(k+1)^2}{4})　　　　　(2.34) \end{aligned}$$

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

”原始Friedman检验“过于保守，现在通常使用变量

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

$\tau_F$服从自由度为k - 1和(k - 1)(N - 1)的F分布。

若”所有算法性能相同“这个假设被拒绝，则需进行”后续检验“(post-hoc test)来进一步区分各算法。

Nemenyi检验计算出平均序值差别的临界值域

$$CD=q_\alpha\sqrt{\frac{k(k+1)}{6N}},　　　　　(2.36)$$

若两个算法的平均序值之差超出了临界值域CD，则以相应的置信度拒绝”两个算法性能相同“这一假设。

检验比较可直观地用Friedman检验图表示。图中纵轴显示各个算法，横轴是平均序值，圆点表示平均序值，横线段表示临界值与大小，若两个算法的横线段有交叠，则没有显著差别，否则反之。

2.5　偏差与方差

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

对测试样本x，令$y_D$为x在数据集中的标记，y为x的真实标记，f(x;D)为训练集D上学得模型f在x上的预测输出。以回归任务为例，学习算法的期望预测为

$$\overline f(x)=\mathbb{E}_D[f(;D)],　　　　　(2.37)$$

使用样本数相同的不同训练集产生的方差为

$$var(x)=\mathbb{E}_D[(f(x;D)-\overline f(x))^2],　　　　　(2.38)$$

噪声为

$$\epsilon^2=\mathbb{E}_D[(y_D-y)^2].　　　　　(2.39)$$

期望输出与真实标记的差别成为偏差(bias)，即

$$bias^2(x)=(\overline f(x)-y)^2.　　　　　(2.40)$$

为便于讨论，假定噪声期望为零，即$\mathbb{E}_D[y_D-y]=0$。通过简单的多项式展开合并，可对算法的期望泛化误差进行分解：

于是，

$$E(f;D)=bias^2(x)+var(x)+\epsilon^2,　　　　　(2.42)$$

泛化误差可分解为偏差、方差与噪声之和。

偏差(2.40)度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力；方差(2.38)度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响；噪声(2.39)表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。

一般来说偏差与方差是有冲突的，称为偏差-方差窘境(bias-variance dilemma)。如下图，给定学习任务，训练不足时，拟合能力不够强，此时偏差主导了泛化错误率；训练程度较深，拟合能力增强，方差主导了泛化错误率。