02model_evaluation_and_model_selection.md

模型评估与选择

误差

在分类任务中，通常把错分的样本数占样本总数的比例称为错误率（error rate）。比如m个样本有a个预测错了，错误率就是a/m；与错误率相对的有精度（accuracy），或者说正确率，数值上等于1-错误率。

更一般地，通常会把模型输出和真实值之间的差异称为误差（error）。在训练集上的误差称为训练误差（training error）或者经验误差（empirical error）。而在新样本上的误差则称为泛化误差（generalization error）。我们希望模型的泛化误差尽可能小，但现实是，我们无法知道新样本是怎样的，所以只能尽可能地利用训练数据来最小化经验误差。

但是否经验误差小，泛化误差就一定小呢？这不是一定的，如果模型相比训练数据来说过于复杂，那就很有可能把训练数据本身的一些特点当作整个样本空间的特点，从而使得在训练数据上有很小的经验误差，但一旦面对新样本就会有很大误差，这种情况叫做过拟合（overfitting）。相对的是欠拟合（underfitting）。

欠拟合很容易避免，只要适当地增加模型复杂度（比方说增加神经网络的层数）就好。但过拟合是无法彻底避免的，只能缓解（减少模型复杂度/增加训练数据），这也是机器学习发展中的一个关键阻碍。

在现实任务中，要处理一个问题，我们往往有多种算法可以选择，即使是同一个算法也需要进行参数的选择，这就是机器学习中的**模型选择（model selection）**问题。既然泛化误差无法使用，而经验误差又存在着过拟合问题，不适合作为标准，那么我们应该如何进行模型选择呢？针对这个问题，后面的三个小节会给出回答。

这里先简单归纳一下，书中将模型选择问题拆解为（1）评估方法；（2）性能度量；（3）比较检验；三个子问题。可以这样理解：

• 评估方法：用什么数据做评估？如何获得这些数据？

• 性能度量：评估时如何衡量模型的好坏？有哪些评价标准？

• 比较检验：如何比较模型的性能？注意不是简单地比大小！在机器学习中性能比较是相当复杂的。

评估方法

前面已经提到了不能把经验误差用作模型评估，否则会存在过拟合的嫌疑。那么很自然地，我们就会想到是否有一种方法能近似泛化误差呢？答案是有的，就是使用**测试集（testing set）进行评估，利用测试误差（testing error）**来近似泛化误差。

测试集和训练集一样，从样本空间中独立同分布采样而得，并且应尽可能与训练集互斥，也即用于训练的样本不应再出现在测试集中，否则就会高估模型的性能。为什么呢？举个例子，老师布置了2道题做课后作业，如果考试还是出这2两题，只能证明大家记住了这2道题；只有出不一样的题，才能看出大家是否真的掌握了知识，具备了举一反三的能力。

注意！！测试数据更多地是指模型在实际使用中遇到的数据，为了和模型评估中使用的测试集进行区分，一般会把模型评估用的测试集叫做验证集（validation set）。举个例子，在Kaggle或者天池上参加比赛，我们一般会拿到一份带标记的原始数据集和一份不带标记的测试数据集。我们需要选用一种评估方法来把原始数据集划分成训练集和验证集，然后进行训练，并按照模型在验证集上的性能表现来进行选择。最后挑出最好的模型对测试集的样本进行预测，并提交预测结果。下文将介绍几种常用的评估方法。

留出法

直接将数据集划分为两个互斥集合，注意保持数据分布的一致性（比如比例相似）。保留类别比例的采样方式又叫分层采样（stratified sampling）。举个例子，原始数据集有100个样本，假设训练集占70个，验证集占30个。若训练集中正例反例各35个，也即比例为1:1，那么验证集中就应该正例反例个15个，同样保持1:1的比例。当然，这个比例最好还是遵循原始数据集中数据的分布规律。

单独一次留出法的结果往往不可靠，一般是进行多次随机划分，然后取各次评估的平均值作为评估结果。

留出法最大的缺点就是要进行划分，当训练集占的比例较大时，模型可以更准确地刻画原始数据集的特征，但是因为验证集较小，评估的结果往往不稳定也不准确；当训练集占的比例较小时，训练出的模型又不能充分学习到原始数据集的特征，评估结果可信度不高。这个问题没有完美的解决方案，一般取数据集2/3~4/5的样本作为训练集，余下的作为验证集。

交叉验证

又称为k折交叉验证（k-fold cross validation），将数据集划分为k个互斥子集。每次使用k-1个子集的并集作为训练集，余下的一个子集作为验证集，这就构成了k组训练/验证集，从而可以进行k次训练和验证。最终取k次验证的均值作为评估结果。 常用的k值包括5，10，20。

类似于留出法，因为存在多种划分k个子集的方式，为了减少因不同的样本划分而引入的差别，需要进行多次k折交叉验证。例如10次10折交叉验证，指的是进行了总计100次训练和100次评估。

特别地，令k=数据集样本数的交叉验证称为留一法（Leave-One-Out，简称LOO），即有多少样本就进行多少次训练/验证，并且每次只留下一个样本做验证。这样做的好处是不需要担心随即样本划分带来的误差，因为这样的划分是唯一的。一般来说，留一法的评估结果被认为是比较准确的。但是！当数据集较大时，使用留一法需要训练的模型太多了！这种计算开销是难以忍受的！

自助法

在留出法和交叉验证法中，我们都需要对数据集进行划分，从而使得训练所用的数据集比源数据集小，引入了一些因规模不同而造成的偏差，有没有办法避免规模不同造成的影响呢？

自助法（bootstrapping）正是我们需要的答案，以自助采样（bootstrap sampling）为基础，对包含m个样本的源数据集进行有放回的m次采样以获得同等规模的训练集。在这m次采样中都不被抽到的概率大约为0.368，也即源数据集中有大约1/3的样本是训练集中没有的。因此，我们可以采用这部分样本作为验证集，所得的结果称为包外估计（out-of-bag estimate）。

注意，自助法适用于数据集小，难以划分训练/验证集的情况。因为自助法能产生多个不同训练集，所以对集成学习也大有好处。但是！自助法改变了数据集的分布，也因此引入了一些额外的误差。因此，数据量足的时候还是留出法和交叉验证法用得多一些。

调参和最终模型

**调参（parameter tuning）**一般先选定一个范围和变化步长，比如(0,1]，步长0.2，这样就有五个参数候选值。然后进行评估，选出最好的一个。这样选出的未必是全局最优的参数，但为了在开销和性能之间折中，只能这么做，毕竟我们无法试尽参数的所有取值。而且多个参数组合的情况是指数上升的，比方说有3个参数，每个参数评估5种取值，就需要测试多达 $5^3$ 种情形。

特别注意，训练/验证这个过程是为了让我们确定学习算法和算法的参数，确定了这些之后，我们需要再利用整个源数据集进行训练，这次训练所得的模型才是最终模型，也即提交给用户，进行测试的模型。

性能度量

性能度量（performance measure）指的是用于衡量模型泛化能力的评价标准。使用不同的性能度量往往导致不同的评判结果。比方说搭建推荐系统，两个模型中一个精度高，一个覆盖度高，如果我们想让更多的商品得到推荐可以就会选后一个模型。所以说，模型的好坏是相对的，取决于我们采用什么性能度量，而采用什么性能度量则应取决于我们的任务需求。

这个小节主要介绍分类任务中常用的性能度量。

错误率和精度

在本章的开头已经提及到了，不再累述，这两个性能度量可写作更一般的形式，基于数据分布和概率密度函数进行定义。

查准率，查全率，F1

假设我们正常处理一个二分类问题，按照模型预测值和真实值可以把测试样本划分为四种情形：真正例（true positive），假正例（false positive），真反例（true negative），假反例（false negative）。可以把结果表示为下图这个矩阵——混淆矩阵(confusion matrix)。

真实情况	预测结果
	正例	反例
正例	TP（真正例）	FN（假反例）
反例	FP（假正例）	TN（真反例）

查准率，又称准确率（precision），用于衡量模型避免错误的能力，分母是模型预测的正例数目。

$$precision = \frac{TP}{TP+FP}$$

查全率，又称召回率（recall），用于衡量模型避免缺漏的能力，分母是测试样本真正包含的正例数目。

一般来说，这两者是矛盾的，提高其中一者则另一者必然会有所降低。

$$recall = \frac{TP}{TP+FN}$$

F1，是查准率和查全率的调和平均，用于综合考虑这两个性能度量。

$$\frac{1}{F1} = \frac{1}{2} \times (\frac{1}{precision} + \frac{1}{recall}) \Rightarrow F1 = \frac{2 \times precision \times recall}{presion + recall}$$

有时候我们对查准率，查全率的需求是不同的。比方说广告推荐，要尽量避免打扰用户，因此查准率更重要；而逃犯检索，因为漏检的危害很大，所以查全率更重要。这时就需要使用$F_\beta$了。

$F_\beta$，是查准率和查全率的加权调和平均，用于综合考虑这两个性能度量，并采用不同的权重。

$$\frac{1}{F_\beta} = \frac{1}{1+\beta^2} \times (\frac{1}{precision} + \frac{\beta^2}{recall}) \Rightarrow F_\beta = \frac{(1+\beta^2) \times precision \times recall}{(\beta^2 \times presion) + recall}$$

其中 $\beta>0$ 度量了查全率对查准率的相对重要性，等于1时$F_\beta$退化为F1，小于1时查准率更重要，大于1时查全率更重要。

书中还介绍了如何对多次训练/测试产生的多个混淆矩阵进行评估，包括宏方法（先分别计算性能度量，再计算均值）和微方法（先对混淆矩阵各元素计算均值，再基于均值计算性能度量）两种途径。

ROC与AUC

很多时候，使用模型对测试样本进行预测得到的是一个实值或者概率（比如神经网络），需要进一步设置阈值（threshold），然后把预测值和阈值进行比较才能获得最终预测的标记。

我们可以按照预测值对所有测试样本进行排序，最可能是正例的排前面，最不能是正例的排后面。这样分类时就像是在这个序列中以某个截断点（cut point）把样本分成两部分。我们需要根据任务需求来设置截断点。比如广告推荐更重视查准率，可能就会把截断点设置得更靠前。

因此！排序本身的质量很能体现出一个模型的泛化性能，ROC曲线就是一个用来衡量排序质量的工具。

ROC，全称受试者工作特征（Receiver Operating Characteristic）。怎样画ROC曲线呢？先定义两个重要的计算量：真正例率（True Positive Rate，简称TPR）和假正例率（False Positive Rate，简称FPR）。

$$TPR = \frac{TP}{TP+FN}$$

$$FPR = \frac{FP}{TP+FN}$$

TPR其实就等于召回率。在绘制ROC曲线时，纵轴为TPR，横轴为FPR。首先按预测值对样本进行排序，然后按序逐个把样本预测为正例，并计算此时的TPR和FPR，然后在图上画出该点，并与前一个点连线。如下图：

有两个值得注意的特例：

• 经过 (0,1) 点的曲线，这代表所有正例都在反例之前出现（否则会先出现假正例从而无法经过 (0,1) 点），这是一个理想模型，我们可以设置一个阈值，完美地分割开正例和反例。

• 对角线，这对应于随机猜测模型，可以理解为真正例和假正例轮换出现，即每预测对一次接下来就预测错一次，可以看作是随机猜测的结果。

若一个模型的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})$$

补充一点，ROC曲线上的面积等于排序损失（loss）。也即有：

$$AUC = 1 - \ell_{rank}$$

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

现实任务中，有时会遇到不同类型错误造成后果不同的状况。比如医生误诊，把患者诊断为健康人的影响远大于把健康人诊断为患者，因为可能因为这次误诊丧失了最佳治疗时机。为了权衡不同类型错误带来的不同损失，可以为这些错误类型赋以非均等代价（unequal cost）。

还是举二分类为类，可以根据任务的领域知识来设定一个代价矩阵（cost matrix）:

真实类别	预测类别
	第0类	第1类
第0类	0	$cost_{01}$
第1类	$cost_{10}$	0

预测值与真实值相等时，自然错误代价为0。但把第0类错预测为第1类和把第1类错预测为第0类这两种错误的代价是不同的。注意，重要的不是代价在数值上的大小，而是它们的比值。比方说 $\frac{cost_{01}}{cost_{10}} > 1$， 这就说明把第0类错预测为第1类的代价更高。

使用了非均等代价之后，我们在使用性能度量时自然也需要作出相应的改变，比方说**代价敏感（cost-sensitive）**版本的错误率：

$$E(f;D;cost) = \frac{1}{m}\lgroup\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}\rgroup$$

由于ROC曲线不能反应使用非均等代价之后的期望总体代价，所以改用**代价曲线（cost curve）**来取替。

代价曲线图的纵轴为归一化代价（将代价映射到 [0,1] 区间），横轴为正例概率代价。画法类似于ROC曲线，它是将ROC曲线的每一个点转为图中的一条线。依次计算出ROC曲线每个点对应的FPR和FNR，然后把点 (0,FPR) 和点 (0,FNR) 连线。最终所得的图中，所有线的下界所围成的面积就是该模型的期望总体代价。

比较检验

看起来似乎有了获取测试集$^{*}$的评估方法和用于比较模型的性能度量之后，就能够通过不同模型在测试集上的性能表现来判断优劣了。但是！事实上，在机器学习中，模型比较并不是这样简单的比大小，而是要考虑更多。

注：指验证集，但无论是书中还是论文中，都使用测试集较多，明白两者的区别就可以了。

在模型比较中，主要有以下三个重要考虑：

1. 测试集上的性能只是泛化性能的近似，未必相同；
2. 测试集的选择对测试性能有很大影响，即使规模一致，但测试样例不同，结果也不同；
3. 一些机器学习算法有随机性，即便算法参数相同，在同一测试集上跑多次，结果也可能不同；

那么应该如何有效地进行模型比较呢？答案是采用假设检验（hypothesis test）。基于假设检验的结果，我们可以推断出，若在测试集上观察到模型A优于B，则是否A的泛化性能在统计意义上也优于B，以及做这个结论的把握有多大。

本小节首先介绍最基本的二项检验和t检验，然后再深入介绍其他几种比较检验方法。默认以错误率作为性能度量。

几个基础概念：

• 置信度：表示有多大的把握认为假设是正确的。
• 显著度：也称“显著性水平”，表示假设出错的概率。显著度越大，假设被拒绝的可能性越大。
• 自由度：不被限制的样本数，也可以理解为能自由取值的样本数，记为 $v$ 或 $df$。

单个模型、单个数据集上的泛化性能检验

我们有多大把握相信对一个模型泛化性能的假设？

二项检验

在进行比较检验前，完成了一次模型预测，已知测试错误率为 $\hat{\epsilon}$。

一个泛化错误率为 $\epsilon$ 的模型在 $m$ 个样本上预测错 $m'$ 个样本的概率为：

$$ P(\hat{\epsilon};\epsilon) = \binom{m}{m'} \epsilon^{m'} (1-\epsilon)^{m - m'}$$

这个概率符合二项分布:

又因为已知测试错误率为 $\hat{\epsilon}$，也即知道了该模型在 $m$ 个样本上实际预测错 了$\hat{\epsilon} \times m$ 个样本。代入公式，对 $\epsilon$ 求偏导会发现，给定这些条件时，$\epsilon = \hat{\epsilon}$ 的概率是最大的。

使用二项检验（binomial test），假设泛化错误率 $\epsilon \leq \epsilon_0$，并且设定置信度为 $1-\alpha$。则可以这样定义错误率的阈值 $\overline{\epsilon}$：

$$\overline{\epsilon} = \max{\epsilon} \qquad s.t. \qquad \sum_{i=\epsilon_0 \times m+1}^m \binom{m}{i}\epsilon^i (1-\epsilon)^{m-i} < \alpha$$

其中 $s.t.$ 表示左式在右边条件满足时成立。右式计算的是发生不符合假设的事件的总概率，如果我们要有 $1-\alpha$ 的把握认为假设成立，那么发生不符合假设的事件的总概率就必须低过 $\alpha$。

在满足右式的所有 $\epsilon$ 中，选择最大的作为阈值 $\overline{\epsilon}$。如果在测试集中观测到的测试错误率 $\hat{\epsilon}$ 是小于阈值 $\overline{\epsilon}$的， 我们就能以$1-\alpha$ 的把握认为假设成立，即该模型的泛化误差 $\epsilon \leq \epsilon_0$。

t检验

二项检验只用于检验某一次测试的性能度量，但实际任务中我们会进行多次的训练/测试，得到多个测试错误率，比方说进行了k次测试，得到 $\hat{\epsilon}_1$,$\hat{\epsilon}_2$, ... ,$\hat{\epsilon}_k$。这次就会用到t检验(t-test)。

定义这 $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$$

注意！这里使用的是无偏估计的样本方差，分母是 $k-1$，因为当均值确定，并且已知 $k-1$ 个样本的值时，第 $k$ 个样本的值是可以算出来的，也可以说是受限的。

假设泛化错误率 $\epsilon = \epsilon_0$，并且设定显著度为 $\alpha$。计算统计量t：

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

该统计量服从自由度 $v = k-1$ 的t分布，如下图：

自由度越大，约接近于正态分布，自由度为无穷大时变为标准正态分布（$\mu=0$，$\sigma=1$）。

如果计算出的t统计量落在临界值范围 [$t_{-a/2}$,$t_{a/2}$] 之内（注：临界值由自由度 $k$ 和显著度 $\alpha$ 决定，通过查表得出），我们就能以$1-\alpha$ 的把握认为假设成立，即该模型的泛化误差 $\epsilon = \epsilon_0$。

两个模型/算法、单个数据集上的泛化性能检验

我们有多大把握相信两个模型的泛化性能无显著差别？

交叉验证t检验

对两个模型A和B，各使用k折交叉验证分别得到k个测试错误率，即$\hat{\epsilon}_1^A$,$\hat{\epsilon}_2^A$, ... ,$\hat{\epsilon}_k^A$ 和 $\hat{\epsilon}_1^B$,$\hat{\epsilon}_2^B$, ... ,$\hat{\epsilon}_k^B$。使用**k折交叉验证成对t检验（paired t-tests）**来进行比较检验。

对于这两组k个测试错误率，计算两组之间的每一对的差，即 $\triangle_i = \hat{\epsilon}_k^A - \hat{\epsilon}_k^B$，从而得到k个 $\triangle$。我们可以计算 $\triangle$ 的均值 $\mu$ 和方差 $\sigma^2$，定义统计量t：

$$t = \lvert \frac{\sqrt{k}\mu}{\sigma} \rvert$$

可以看到，和前面的t检验相比，这里的分子没有被减项，其实是省略了。因为我们假设两个模型的泛化错误率相同，实际上是假设 $\lvert \epsilon^A - \epsilon^B \rvert = 0$，这个 $0$ 被省略了。

类似地，这个统计量服从自由度 $v = k-1$ 的t分布。我们设定好显著度 $\alpha$，查表获取临界值范围，如果计算出的t统计量落在在范围内，就能以$1-\alpha$ 的把握认为假设成立，即两个模型的泛化性能无显著差别，否则认为平均测试错误率较低的模型更胜一筹。

McNemar检验

对于一个二分类问题，如果使用留出法，我们不仅可以获得两个算法A和B各自的测试错误率，或能够获得它们分类结果的差别（都预测正确、都预测错误、一个预测正确一个预测错误），构成一张列联表（contingency table）：

算法B	算法A
	分类正确	分类错误
分类正确	$e_{00}$	$e_{01}$
分类错误	$e_{10}$	$e_{11}$

假设两个算法的泛化性能无显著区别，则 $e_{01}$ 应该等于 $e_{10}$，变量 $\lvert e_{01}-e_{10} \rvert$ 应服从均值为 $1$，方差为 $e_{01} + e_{10}$ 的正态分布，可以计算统计量 $\chi^2$：

$$\chi^2 = \frac{(\lvert e_{01}-e_{10} \rvert -1)^2}{e_{01} + e_{10}}$$

该变量服从自由度为 $v=1$ 的 $\chi^2$ 分布（卡方分布），类似t检验，设定好显著度 $\alpha$，按照自由度和显著度查表获得临界值。若计算所得的统计量 $\chi^2$ 小于临界值，则能以$1-\alpha$ 的把握认为假设成立，即两个算法的泛化性能无显著差别，否则认为平均测试错误率较低的算法更胜一筹。

注：这里 $v$ 为1是因为只有2个算法

多个模型/算法、多个数据集上的泛化性能检验

我们有多大把握相信多个模型的泛化性能皆无显著差别？若有，接下来怎样做？

在一组数据集上进行多个算法的比较，情况就变得较复杂了，一种做法是使用前面的方法分开两两比较；另一种更直接的做法是使用基于算法排序的Friedman检验。

Friedman检验

假设有 $N=4$ 个数据集，$k=3$ 种算法，可以使用一种评估方法，获得各个算法在各个数据集上的测试结果，然后按照性能度量由好到坏进行排序，序值为1，2，3。若并列，则取序值的平均值。然后对各个算法在各数据集上的序值求平均得到平均序值，如：

数据集	算法A	算法B	算法C
D1	1	2	3
D2	1	2.5	2.5
D3	1	2	3
D4	1	2	3
平均序值	1	2.125	2.875

令 $r_i$ 表示第 $i$ 个算法的平均序值，则 $r_i$ 服从均值为 $\frac{k+1}{2}$，方差为 $\frac{(k^2)-1}{12}$ 的正态分布。可以计算统计量 $\chi^2$：

$$\chi^2 = \frac{12N}{k(k+1)}(\sum_{i=1}^k r_i^2 - \frac{k(k+1)^2}{4})$$

在 $k$ 和 $N$ 都较大时(通常要求 $k&gt;30$)，该变量服从自由度为 $v=k-1$ 的 $\chi^2$ 分布（卡方分布）。

以上这种检验方式也称为原始Friedman检验，被认为过于保守，现在通常用统计量 $F$ 代替：

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

该变量服从于自由度为 $v=k-1$ 或 $v=(k-1)(N-1)$ 的 $F$ 分布。

和前面的检验方式有所区别，F检验是根据设定的显著度 $\alpha$ 和算法个数 $k$ 以及 数据集个数$N$ 这三者来查表的，如果计算出的统计量 $F$ 小于查表所得的临界值，则假设成立，能以$1-\alpha$ 的把握认为认为这 $k$ 个算法的泛化性能无显著区别。

但如果这个假设被拒绝了呢？这时就需要进行后续检验（post-hoc test），常用的有 Nemenyi后续检验。

Nemenyi后续检验

定义平均序值差别的临界值域为：

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

其中 $q_\alpha$是由 显著度 $\alpha$ 和算法个数 $k$ 确定的，通过查表获取。若两个算法的平均序值之差不超过 $CD$，则能以$1-\alpha$ 的把握认为这两个算法的泛化性能无显著区别，否则认为平均序值较小的更胜一筹。

Nemenyi后续检验还可以通过Friedman检验图更直观地体现出来，横轴为性能度量，纵轴为算法，每个算法用一段水平线段表示，线段中心点为该算法的平均序值，线段长度为 $CD$。若两个算法的线段投影到x轴上有重叠部分，则可以认为这两个算法的泛化性能无显著区别。

偏差与方差

除了估计算法的泛化性能，我们往往还希望知道为什么有这样的性能？这时一个有用的工具就是偏差-方差分解（bias-variance decomposition）。

知乎上面有两个问题都有不错的答案，不妨先看看。[1] 机器学习中的Bias(偏差)，Error(误差)，和Variance(方差)有什么区别和联系？；[2] 偏差和方差有什么区别？。

对学习算法的期望繁华错误率进行拆解，最终会发现能拆解为三个项（需要推导）：

$$E(f;D) = \mathbb{E}_D[(f(x;D) - \overline{f}(x))^2] + (\overline{f}(x) - y)^2 + \mathbb{E}_D[(y_D - y)^2]$$

依次对应于方差（variance）、偏差（bias）、噪声（noise）：

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

这三者的含义是这样的：

• 方差：使用同规模的不同训练集进行训练时带来的性能变化，刻画数据扰动带来的影响；

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

• 噪声：当前任务上任何算法所能达到的期望泛化误差的下界（即不可能有算法取得更小的误差），刻画问题本身的难度；

也即是说，泛化性能是有学习算法的拟合能力，数据的充分性以及问题本身的难度共同决定的。给定一个任务，噪声是固定的，我们需要做得就是尽量降低偏差和方差。

但是这两者其实是有冲突的，这称为偏差-方差窘境（bias-variance dilemma）。给定一个任务，我们可以控制算法的训练程度（如决策树的层数）。在训练程度较低时，拟合能力较差，因此训练数据的扰动不会让性能有显著变化，此时偏差主导泛化错误率；在训练程度较高时，拟合能力很强，以至于训练数据自身的一些特性都会被拟合，从而产生过拟合问题，训练数据的轻微扰动都会令模型产生很大的变化，此时方差主导泛化错误率。

注意，将泛化性能完美地分解为方差、偏差、噪声这三项仅在基于均方误差的回归任务中得以推导出，分类任务由于损失函数的跳变性导致难以从理论上推导出分解形式，但已经有很多方法可以通过实验进行估计了。

习题

2.1

问：数据集包含1000个样本，其中500个正例，500个反例，将其划分为包含70%样本的训练集和30%样本的测试集用于留出法评估，试估算共有多少种划分方式。

按照题意，训练集包含700个样本，测试集包含300个样本。并且为了保证训练集和测试集的类别比例一致，使用分层采样，训练集包含正例反例各350个；测试集包含正例反例个150个。

有多少种划分方式是一个排列组合问题，等于从500个正例中挑选出300个的所有可能组合乘上从500个正例中挑选出300个的所有可能组合：

$$\binom{500}{350} \times \binom{500}{350} = \binom{500}{150} \times \binom{500}{150} $$

2.2

问：数据集包含100个样本，其中正反例各一半，假定学习算法所产生的模型是将新样本预测为训练样本数较多的类别（训练样本数相同时进行随机猜测），试给出用10折交叉验证法和留一法分别对错误率进行评估所得的结果。

（1）10折交叉验证法：通过分层采样获得10个互斥子集，每个子集包含10个样本，正反例各5个。每次取其中9个子集做训练，1个子集做测试。因为在训练集中两个类别数目相当（都为 $9*5=45$ 个），所以只能进行随机猜测，错误率为50%。

（2）留一法：每次取一个样本做测试，若取出的样本为正例，那么剩下的训练集中有50个反例，49个正例，因此预测结果为反例，反之亦然。故错误率为100%。

2.3

问：若学习器A的F1值比学习器B高，试析A的BEP值是否也比B高。

模型A的F1值高于模型B的F1值也即：

$$F1_A > F1_B \Leftrightarrow \frac{2 \times precision_A \times recall_A}{presion_A + recall_A} > \frac{2 \times precision_B \times recall_B}{presion_B + recall_B}$$

BEP是查准率precision与查全率recall相等时的取值，令式中的 $precision_A = recall_A = BEQ_A$，$precision_B = recall_B = BEQ_B$，因此有：

$$\frac{2 \times BEQ_A^2}{2 \times BEQ_A} > \frac{2 \times BEQ_B^2}{2 \times BEQ_B} \Rightarrow BEQ_A > BEQ_B$$

得证，若学习器A的F1值比学习器B高，则A的BEP值也比B高。

2.4

问：试述真正例率（TPR）、假正例率（FPR）与查准率（P）、查全率（R）之间的联系。

• 真正例率是真正例占真实正例的比例；

• 假正例率是假正例占真实反例的比例；

• 查准率是真正例占预测正例的比例；

• 查全率是真正例占真实正例的比例；

其中，真正例指模型预测为正例并且预测正确的样例，假正例指模型预测为正例并且预测错误的样例。前缀真实表明在数据集中的真实标记，前缀预测表明模型预测出的标记。

特别地，查全率与真正例率是相等的。

2.5

问：试证明 $AUC=1-\ell_{rank}$

先回顾一下AUC的计算方法：

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

计算方法类似于积分，把ROC曲线下的面积分解为m（样本个数）个小矩形，然后对这些小矩阵的面积求和。每个矩形的宽等于相邻的两个点横坐标的差值，每个矩形的高等于相邻两个点纵坐标之和的 $\frac{1}{2}$。上式把常数 $\frac{1}{2}$ 提到求和项外了。

再看看排序损失（指按算法预测值排序时带来的损失）：

$$\ell_{rank} = \frac{1}{m^+ \cdot m^-} \sum_{x^+ \in D^+}\sum_{x^- \in D^-} (\mathbb{I}(f(x^+) < f(x^-)) + \frac{1}{2}\mathbb{I}(f(x^+) = f(x^-)))$$

其中 $m^+$ 和 $m^-$ 分别表示测试集中的正例集和反例集。

这题目前还没有头绪，AUC曲线上的面积是：

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

怎么证明这个表达式和 $\ell_{rank}$ 相等呢？

2.6

问：试述错误率与ROC曲线之间的关系

错误率 $\epsilon$：

$$\epsilon = \frac{FP + FN}{m}$$

其中 $m$ 为样本总数， $FP$ 为假正例个数， $FN$ 为假反例个数。因为给定测试集，正例反例的数目是固定的。当我们以ROC曲线上的一个点作为阈值划分预测的正例和反例时，该点的真正例率（y轴）越高，那么假反例就会越少；该点的假正例率（x轴）越低，那么假正例就越少，从而使得错误率越低。归纳起来就是，在ROC曲线上距离左上角 (0,1) 点越近的点错误率越低。

2.7

问：试证明任意一条ROC曲线都有一条代价曲线与之对应，反之亦然。

回顾代价曲线的作法，求ROC曲线上每一点对应的FPR和FNR，在代价平面连接点 (0,FPR) 和点 (1，FNR)，代价曲线由所有连线的下界确定。由于ROC曲线是连续的，故必然有一条对应的代价曲线。 反过来，对代价曲线上的任何一点作切线，都可以得到对应的FPR与FNR，从而计算出ROC曲线上对应点的坐标。因此代价曲线也必然有一条对应的ROC曲线。

2.8

问：$Min-Max$ 规范化和 $z-score$ 规范化是两种常用的规范化方法。令 $x$ 和 $x'$ 分别表示变量在规范化前后的取值，相应的，令 $x_{min}$ 和 $x_{max}$ 表示规范化前的最小值和最大值， $x_{min}'$ 和 $x_{max}'$ 表示规范化后的最小值和最大值，$\bar{x}$ 和 $\sigma_x$ 分别表示规范化前的均值和标准差。试析二者的优缺点。

$Min-Max$ 规范化：

$$x' = x_{min}' + \frac{x-x_{min}}{x_{max}-x_{min}} \times (x_{max}' - x_{min}')$$

$z-score$ 规范化：

$$x' = \frac{x - \bar{x}}{\sigma_x}$$

$Min-Max$ 规范化比较简单，缺点在于当有新数据输入时，可能导致max和min的变化，需要重新定义。

$z-score$ 规范化能把数据的原分布转换为标准正态分布，即均值为0，标准差为1，对于某些任务可能会有帮助。比如分类时，规范化后取值靠近-1的认为是负类，取值靠近1的认为是正类。注意！它并非是把数据映射到 [-1,1] 区间，会有超出的部分（回想正态分布曲线两段的延伸段），实际处理时一般把超出部分都修改为-1和1以满足映射到区间内的要求。这种规范化的缺点就是改变了数据的分布，这可能会引入某种误差。

2.9

问：试述卡方检验过程。

根据概率论与数理统计中的内容（交大版本，P239）。卡方检验适用于方差的检验。步骤如下：

1）分均值已知与均值未知两种情况，求得卡方检验统计量；

2）根据备选假设以及α，求得所选假设对应的拒绝域（临界值区间）；

3）根据1）中求得的卡方统计量与2）中求得的拒绝域，判断假设成立与否；

2.10*

问：试述原始Friedman检验和F检验的区别。

暂时没有思路。