2 模型评估与选择

2.1 误差与过拟合

我们将学习器对样本的实际预测结果与样本的真实值之间的差异成为：误差（error）。定义：

• 在训练集上的误差称为训练误差（training error）或经验误差（empirical error）。
• 在测试集上的误差称为测试误差（test error）。
• 学习器在所有新样本上的误差称为泛化误差（generalization error）。

显然，我们希望得到的是在新样本上表现得很好的学习器，即泛化误差小的学习器。因此，我们应该让学习器尽可能地从训练集中学出普适性的“一般特征”，这样在遇到新样本时才能做出正确的判别。然而，当学习器把训练集学得“太好”的时候，即把一些训练样本的自身特点当做了普遍特征；同时也有学习能力不足的情况，即训练集的基本特征都没有学习出来。我们定义：

• 学习能力过强，以至于把训练样本所包含的不太一般的特性都学到了，称为：过拟合（overfitting）。
• 学习能太差，训练样本的一般性质尚未学好，称为：欠拟合（underfitting）。

可以得知：在过拟合问题中，训练误差十分小，但测试误差教大；在欠拟合问题中，训练误差和测试误差都比较大。目前，欠拟合问题比较容易克服，例如增加迭代次数等，但过拟合问题还没有十分好的解决方案，过拟合是机器学习面临的关键障碍。

可大致这样理解：机器学习面临的问题通常是NP-Hard甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获最优解，这就意味着我们构造性地证明了 “$P=NP$” ；因此，只要相信“$P\ne NP$” ，过拟合就不可避免。

我们需要进行模型选择：对候选模型的泛化误差就行评估，然后选择泛化误差最小的一个模型，以期达到最好的效果。然而，我们无法直接获得泛化误差，而训练误差又由于过拟合现象的存在而不适合作为标准。

---

2.2 评估方法

引入

1. 在现实任务中，我们往往有多种算法可供选择，那么我们应该选择哪一个算法才是最适合的呢？如上所述，我们希望得到的是泛化误差小的学习器，理想的解决方案是对模型的泛化误差进行评估，然后选择泛化误差最小的那个学习器。但是，泛化误差指的是模型在所有新样本上的适用能力，我们无法直接获得泛化误差。

2. 因此，通常我们采用一个“测试集”来测试学习器对新样本的判别能力，然后以“测试集”上的“测试误差”作为“泛化误差”的近似。显然：我们选取的测试集应尽可能与训练集互斥。

   假设老师出了10 道习题供同学们练习，考试时老师又用同样的这10道题作为试题，可能有的同学只会做这10 道题却能得高分，很明显：这个考试成绩并不能有效地反映出真实水平。回到我们的问题上来，我们希望得到泛化性能好的模型，好比希望同学们课程学得好并获得了对所学知识"举一反三"的能力；训练样本相当于给同学们练习的习题，测试过程则相当于考试。显然，若测试样本被用作训练了，则得到的将是过于"乐观"的估计结果。

训练集与测试集的划分方法

如上所述：我们希望用一个“测试集”的“测试误差”来作为“泛化误差”的近似，因此我们需要对初始数据集进行有效划分，划分出互斥的“训练集”和“测试集”。下面介绍几种常用的划分方法：

留出法(Hold-Out)

1. 将数据集D划分为两个互斥的集合，一个作为训练集S，一个作为测试集T，满足D=S∪T且S∩T=∅，常见的划分为：大约60%-80%的样本用作训练，剩下的用作测试。
2. 需要注意的是：训练/测试集的划分要尽可能保持数据分布的一致性，以避免由于分布的差异引入额外的偏差，常见的做法是采取分层抽样。同时，由于划分的随机性，单次的留出法结果往往不够稳定，一般要采用若干次随机划分，重复实验取平均值的做法。

交叉验证法(Cross Validation)

1. 将数据集D划分为k个大小相同的互斥子集，满足$D=\bigcup _{i=1}^k{D}_i$，$D_i\cap D_j=\mathrm{\varnothing }(i\ne j)$，同样地尽可能保持数据分布的一致性，即采用分层抽样的方法获得这些子集。交叉验证法的思想是：每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集，这样就有K种训练集/测试集划分的情况，从而可进行k次训练和测试，最终返回k次测试结果的均值。交叉验证法也称“k折交叉验证”，k最常用的取值是10，下图给出了10折交叉验证的示意图。

与留出法类似，将数据集D划分为K个子集的过程具有随机性，因此K折交叉验证通常也要重复p次，称为p次k折交叉验证，常见的是10次10折交叉验证，即进行了100次训练/测试。特殊地当划分的k个子集的每个子集中只有一个样本时，称为“留一法（Leave-One-Out）”，显然，留一法的评估结果比较准确，但对计算机的消耗也是巨大的。

自助法(Bootstrapping)

我们希望评估的是用整个D训练出的模型。但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比D小，这必然会引入一些因训练样本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小，但计算复杂度又太高了。“自助法”正是解决了这样的问题。

自助法的基本思想是：给定包含m个样本的数据集D，每次随机从D 中挑选一个样本，将其拷贝放入D'，然后再将该样本放回初始数据集D 中，使得该样本在下次采样时仍有可能被采到。重复执行m 次，就可以得到了包含m个样本的数据集D'。可以得知在m次采样中，样本始终不被采到的概率取极限为：

$$\underset{m\to \mathrm{\infty }}{lim}{(1-\frac{1}{m})}^m=\frac{1}{e}\approx 0.368$$

这样，通过自助采样，初始样本集D中大约有36.8%的样本没有出现在D'中，于是可以将D'作为训练集，D-D'作为测试集。自助法在数据集较小，难以有效划分训练集/测试集时很有用，但由于自助法产生的数据集（随机抽样）改变了初始数据集的分布，因此引入了估计偏差。在初始数据集足够时，留出法和交叉验证法更加常用。

调参与最终模型

大多数学习算法都有些参数(parameter) 需要设定，参数配置不同，学得模型的性能往往有显著差别，这就是通常所说的"参数调节"或简称"调参" (parameter tuning)。

学习算法的很多参数是在实数范围内取值，因此，对每种参数取值都训练出模型来是不可行的。常用的做法是：对每个参数选定一个范围和步长λ，这样使得学习的过程变得可行。例如：假定算法有3 个参数，每个参数仅考虑5 个候选值，这样对每一组训练/测试集就有555= 125 个模型需考察，由此可见：拿下一个参数（即经验值）对于算法人员来说是有多么的happy。

最后需要注意的是：当选定好模型和调参完成后，我们需要使用初始的数据集D重新训练模型，即让最初划分出来用于评估的测试集也被模型学习，增强模型的学习效果。

---

2.3 性能度量

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

2. 在预测任务中, 给定样例集$D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_m,y_m)\}$, 其中$y_i$ 是示例$x_i$的真实标记。要评估学习器 $f$ 的性能, 就要把学习器预测结果与真实标记$y$进行比较。

均方误差(Mean Squared Error)

回归任务最常用的性能度量。

$$E(f;D)=\frac{1}{m}\sum _{i=1}^m{(f\left(x_i\right)-y_i)}^2$$

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

$$E(f;D)={\int }_{x\sim D}(f(x)-y{)}^{2}p(x)\mathrm{d}x.$$

错误率和精度

错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本数占样本总数的比例。对于样本集D，分类错误率$E(f;D)$为

$$E(f;D)=\frac{1}{m}\sum _{i=1}^m\mathbb{I}(f\left(x_i\right)\ne y_i)$$

精度$acc(f,D)$为

$$acc(f;D)=\frac{1}{m}\sum _{i=1}^m\mathbb{I}(f\left(x_i\right)=y_i)$$$$acc(f;D)=1-E(f;D)$$

更一般地，对于数据分布$D$和概率密度函数$p(\cdot )$，错误率和精度与上述的情况类似。

查准率/准确率(Precision)、查全率/召回率(Recall)和$F_1$

对于二分类问题，我们的原始数据是被分为两类的（设他们分别是正、反类或0、1类），而在经过分类器分类之后，每一个数据样本都会被分类器认定为某一类（正（positive）或反（negative）），这也就是分类结果，最终判断其分类结果正确与否（true和false）。所以我们有一些符号设定：

1. 把原数据集中为正类，分类后仍为正类的样本集合记为TP（true positive）；

2. 把原数据集中为正类，但分类后为反类的样本集合记为FN（false negative）；

3. 把原数据集中为反类，但分类后为正类的样本集合记为FP（false positive）；

4. 把原数据集中为反类，分类后仍为反类的样本集合记为TN（true negative）；

   （T和F代表最终的分类结果是否正确；P和N代表分类的结果是正类或反类。）

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

查准率与查全率

查准率P与查全率R分别定义为$P={\displaystyle \frac{TP}{TP+FP}},R={\displaystyle \frac{TP}{TP+FN}}$。

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

PR图

• 以P为纵轴、R为横轴绘出图像，得到了查准率—查全率曲线，简称“P-R曲线”。

• P-R图直观地显示出学习器在样本总体上的查全率、查准率。在进行比较时，若一个学习器的P-R曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者。若出现交点则无法断言。

• 平衡点（BEP）是P=R时的取值，可以基于BEP进行比较。

F1值和F1度量

• $F_1$是基于查准率和查全率的调和平均来定义的：${\displaystyle \frac{2}{F_1}}={\displaystyle \frac{1}{P}}+{\displaystyle \frac{1}{R}}\Rightarrow F_1={\displaystyle \frac{2\times P\times R}{P+R}}$.

• $F_1$对查重率和查准率是同样重视的，$F_1$越大，我们认为性能越好。而在一些应用中，对查准率和查全率的重视程度有所不同。$F_1$度量的一般形式——$F_{\beta }$，能让我们表达出对查准率/查全率的不同偏好。

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

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

• “宏（微）查准率”、“宏（微）查全率”、“宏（微）$F_1$”

  我们希望在n 个二分类混淆矩阵上综合考察查准率和查全率时，直接的做法是先在各混淆矩阵上分别计算出查准率和查全率，并计算它们的平均值。这样可以得出“宏查准率”、“宏查全率”和“宏$F_1$”。

$$\begin{array}{rl}\text{macro-}P& =\frac{1}{n}\sum _{i=1}^n{P}_i\\ \text{macro-}R& =\frac{1}{n}\sum _{i=1}^n{R}_i\\ \text{macro-}{F}_1& =\frac{2\times \text{macro-}P\times \text{macro-}R}{\text{macro-}P+\text{macro-}R}\end{array}$$

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

$$\begin{array}{rl}\text{micro-}P& =\frac{\overline{TP}}{\overline{TP}+\overline{FP}}\\ \text{micro-}R& =\frac{\overline{TP}}{\overline{TP}+\overline{FN}}\\ \text{micro-}{F}_1& =\frac{2\times \text{micro-}P\times \text{micro-}R}{\text{micro-}P+\text{micro-}R}\end{array}$$

ROC与AUC

• 在不同的应用任务中，我们可根据任务需求来采用不同的截断点，例如若我们更重视“查准率”，则可选择排序中靠前的位置进行截断；若更重视“查全率”，则可选择靠后的位置进行截断.因此，排序本身的质量好坏，体现了综合考虑学习器在不同任务下的“期望泛化性能”的好坏，或者说，“一般情况下”泛化性能的好坏。
• ROC曲线：Receiver Operating Characteristic curve，描述了当阈值变化时真正例率和假正例率的变化情况。横轴为假正例率（FPR），纵轴为真正例率（TPR）。

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

1. ROC曲线越靠近左上角，分类器性能越好。
2. ROC曲线下的面积AUC（Area Under ROC Curve）是对ROC曲线的一个数值化的描述，AUC越大，分类器性能越好。
3. AUC的取值范围在0和1之间，AUC=0.5时，分类器性能等同于随机猜测。

• AUC：模型评估指标AUC(Area Under the Curve)，即ROC曲线下的面积。AUC值越大，说明模型的性能越好。AUC=1，是完美分类器，AUC=0.5是随机分类器。

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

1. 在现实任务中，不同的错误分类代价可能是不同的，例如在医学诊断中，将病人诊断为健康人的代价要远远小于将健康人诊断为病人。因此，我们需要对不同的错误分类赋予不同的代价，这就是代价敏感错误率。
2. 代价曲线：描述了不同代价下的分类器性能。横轴为错误分类的代价比例，纵轴为分类器的性能度量。
3. 代价曲线的绘制步骤：
   1. 选择不同的阈值，得到不同的混淆矩阵；
   2. 根据混淆矩阵计算出不同代价下的错误率；
   3. 绘制代价曲线。
   4. 代价曲线的绘制过程中，我们可以选择不同的代价比例，得到不同的代价曲线，从而选择最优的代价比例。

---

2.4 比较检验

一、为什么要引入比较检验

我们要比较两个学习器的学习性能，不仅仅需要求出两个关于性能度量的值，然后定量比较就完事儿的。因为，机器学习中，学习器性能的比较涉及到很多方面，而这些方面有时候又有矛盾关系。

我们需要考虑的评估学习性能的因素主要有以下几点：

• 泛化能力，即机器学习算法对新样本的适应能力。举个例子，我们高考的时候多半都会刷“五三”，刷了很多题，但是在高考的时候有些同学可以考的很好，但是有些就考的不行。原因在于高考的题目不可能是我们平时训练的原题，没有人做过，而不同的同学由于泛化能力不一样，因此举一反三的能力也就有了差距，最后导致大家的成绩天差地别。把高中生这种举一反三的能力放到机器学习上，就是学习器的泛化能力了。
• 测试集的选择，不同大小，不同样例的测试集导致的训练结果可能是不一样的。
• 算法的随机性，因为机器学习是有黑盒性质的，我们无法得知里面的具体运行过程，有可能相同的测试集、在同一个学习器上以相同的参数来运行，会出现不一样的结果；

因此，我们需要专门研究一下机器学习的比较检验问题。

二、几种比较检验方法

1、假设检验——二项检验

首先引入两个概念：

• 第一个叫做泛化错误率$e$，是指学习器在一般情况下，对一个样本分类出错的概率，实际情况下我们是无法得知它的准确值的；
• 第二个叫做测试错误率 $e^{\prime }$，即学习器在测试一个m大小的样本集时恰好有 $e^{\prime }m$个样本被分错类了，我们一般情况下只能获得这个值；

两者区别就是：泛化错误率是一个理论上的值，无法获得，而测试错误率是一个我们可以测量得到的值。统计假设检验的方法就是用 $e^{\prime }$估计$e$的值；

一个泛化错误率为 $e^{\prime }$的学习器来测试一个大小为m的测试样例集，只可能有分对和分错两种情况，其中 $e^{\prime }m$个分错，其余的分对，因此这就是一个典型的二项分布，那么我们可以得出测试的错误率分布函数：

$$P(e^{\prime };e)=(\genfrac{}{}{0ex}{}{m}{e^{\prime }\times m})e^{e^{\prime }\times m}(1-e{)}^{m-e^{\prime }m}$$

对$P(e^{\prime };e)$作关于$e$的一阶导，令${\displaystyle \frac{\delta P(e^{\prime };e)}{\delta e}}=0$，解得$e=e^{\prime }$时，$P(e^{\prime };e)$最大；$|e-e^{\prime }|$增大，$P(e^{\prime };e)$减小，就像二项分布一样；

之后便是检验的过程，由于西瓜书上讲的有点晦涩，所以我尽量用稍微简单点的方式描述一下二项假设检验。

前提条件：对于一个分布函数，我们已知这是一个二项分布了，但是这个二项分布的参数（二项分布就只有一个参数，就是正例概率p，在这个例子里面是泛化错误率）的取值是未知的。

假设方法

• 我们可以用假设的办法，人为的规定一个参数取值的“阈值范围”，在这个例子中，我们假设$e\le e_0$；

• 然后我们根据客观需要或者一些计算公式（这里不再赘述，具体问题具体分析），再人为设定一个用于检验的置信度$\alpha$，这个变量表示出现明显错误的标准，比如这个二项分布中大于6的概率为$\alpha$，我设定阈值为$\alpha$就说明我认为如果学习器分类错误个数大于6，那么就属于明显错误，这个假设是不成立的；

• 反之，$1-\alpha$则表示不会出现明显错误的标准，也就是可信任的标准；

我们现在就是要利用这个$1-\alpha$，来推出在这个置信度下，我们假设的$e_0$是不是合理的；

判断假设的合理性

判断合理性一共有两种方法，我主要介绍一下西瓜书上的那种；

大致的思路就是：利用我们设定好的$1-\alpha$的值作为约束，求得分布曲线不大于这个值的积分面积。在书中的例子中用的是条形1统计图，那就把每一条的横纵坐标相乘再做一个求和运算，求出不大于$1-\alpha$的最大值，最后求得这个时候的$e_i$。

公式如下：

$$\sum _{i=e_{0}m+1}^m(\genfrac{}{}{0ex}{}{m}{i})e^i(1-e{)}^{m-i}<1-\alpha$$

意思就是对这个条形统计图从最左边的一条开始累加“横坐标和纵坐标的面积”，然后一直加到刚好不大于$1-\alpha$为止。

我们取出此时的$i$，对应的横坐标即为可接受的阈值标准，再拿我们预先设定好的$e_0$跟它作比较，若$e_0$在小于这个阈值标准，则说明该假设可接受，是合理的假设；否则就是不合理的，需要重新假设。

其实说到头，这就是一个“自编自导”的过程，总结起来就是首先通过二项分布的特征，得到一个大致的阈值，然后在这个阈值中寻找更为精确的点。针对不同的学习器，我们可以使用这种方法，来人为设定参数，比较两个学习器的好坏。

2、假设检验——t检验

很多时候我们为了确保结果的普适性和精确度，我们会做很多次估计检测，假设我们得到了k个错误率$e{1}^{\prime },....,e{k}^{\prime }$，那么我们很容易得到平均错误率 μ 和方差${\sigma }^2$为：

$$\mu =\frac{1}{k}\sum _{i=1}^k{e}_i^{\prime }$$$${\sigma }^2=\frac{1}{k-1}\sum _{i=1}^k(e_i^{\prime }-\mu {)}^2.$$

由于每次估计检测都是独立的，所以这个概率分布函数可以写成：

$$T_t=\frac{\sqrt{k}(\mu -e_0)}{\sigma }$$

其中这个$e_0$是泛化错误率，这是一个满足正态分布的函数；

接下来我们还是跟二项检验一样，设定一个置信度$\alpha$，在正态分布曲线两边的${\displaystyle \frac{\alpha }{2}}$处各取一个明显错误区间，如图所示：

然后假设一个阈值区间 $\mu =e^{\prime }$，计算白色图像曲线下的定积分（条形统计图计算方法参照二项检验），将两个假设做一个对比，如果 $e^{\prime }$在置信度$\alpha$推出的区间内，则说明是可接受的。

双边t检验常用的临界值表：

这一部分的总体过程跟二项检验很相似，除了公式和分布曲线不一样，其余的步骤都是可以仿照二项检验的步骤的，这里就不再赘述。

3、交叉验证t检验

以上两个方法主要针对单个学习器性能的衡量，如果对于多学习器来说，则可以用k折交叉验证t检验来完成。

比如两个学习器A和B经过k次测试的错误率分别为 $\{e_1^A,...,e_k^A\}$，$\{e_1^B,...,e_k^B\}$，其中$e_i^A,e_i^B$是经过k折训练得到的第i折结果，对每一组训练测试结果求差值： $\mathrm{\Delta }i=e_i^A-e_i^B$ 假设每次测试都是相互独立的，所以我们可以把$\mathrm{\Delta }1...\mathrm{\Delta }k$视作k次性能差值的独立采样过程，计算出这组数据的均值 μ 和方差${\sigma }^2$，因此我们有可以接受的$\alpha$，使得$T_t=|{\displaystyle \frac{\sqrt{k}\mu }{\sigma }}|<t_{\alpha /2}$。 这个过程的思路同样也是设定一个置信度$\alpha$，然后判断阈值是否在置信度可接受范围内。

实际上，我们的训练\测试集很容易产生重叠，所以每一次的测试不一定是相互独立的。

我们可以粗略的推测一下，如果我们的训练测试集出现重叠，那么我们得到的k折测试结果是有一定程度的相关性和相似度的，而我们如果还是假设这些测试结果相互独立，也就是说原本“粘合在一起的一堆结果”，我们把它们视作“没有粘合在一起”，那么就相当于我们假设的可接受范围实际上是偏大的，我们会高估假设成立的概率。

所以我们可以采用“5×2交叉验证”，来缓解这个问题。所谓5×2，就是做5次2折交叉验证，在每次2折交叉验证之前一定要把数据打乱，保证划分不重复。基本思路如下：

• 对于两个学习器A和B，每次2折交叉验证会产生两组测试错误率，我们对它们分别求差，得到第1折上的差值${\mathrm{\Delta }}_i^1$和第2折上的差值 ${\mathrm{\Delta }}_i^2$；

• 对第一次2折验'证的两个结果取平均值 μ '，对每次2折实验结果做方差${{\sigma }^{\prime }}^2$，平均值采用之前第一折的均值 μ'；

• 其概率分布函数为：

  $$T_t^{\prime }=\frac{{\mu }^{\prime }}{\sqrt{0.2\sum _{i=1}^5}{\sigma }_i^2}$$

为什么这样就可以缓解测试结果之间的独立性问题了呢？其实很简单，因为我们的均值只是一次测试结果的一组错误率，此后所有的测试结果在计算方差的时候都用的是前面的一组错误率，因此方差的大小仅仅跟原始数据和第一次测试的错误率有关。但是我觉得这种方法得建立在第一次测试的结果比较贴合实际的基础上才会比较好的说服力（个人的一点想法，欢迎大佬指正）。

4、McNemar检验

这个检验方法的主要思路是针对两个二分类学习器的分类结果列出列联表，然后推出两个学习器性能差别的卡方分布函数，再作假设检验；接下来大致的描述一下这个方法的步骤：

• 首先对A、B两个学习器的二分类结果列出列联表：
  

• 然后取$|e_{01}-e_{10}|$，这个变量服从正态分布；这个检验方法考虑变量

• $$T_{x^2}=\frac{(|e_{01}-e_{10}|-1{)}^2}{e_{01}+e_{10}}$$

• 这是一个自由度为1的卡方分布，剩余的假设检验步骤同上：做出假设置信度、推出可接受的范围，检验假设阈值是否在可接受范围内、得出结论。

5、Friedman检验和Nemenyi后续检验

交叉验证t检验和McNemar检验只适用于两两比对，当要比对多个算法的学习器的时候，显然将算法两两比对太麻烦了，所以引入一种可以在同一组数据集上对多个算法进行比对的检验方法。

F检验法的基本思想是在同一组数据集上，根据测试结果对学习器的性能进行排序，赋予序值1,2,3…，相同则平分序值，如下图所示：

性能越好，赋予的值就越小，然后计算出每个算法在各个数据集上的平均序值$r_i$。

这里需要注意，表中的数据只是一个特例，有了这个平均序值并不能完全说明序值小的算法一定更好，因为针对不同的数据集，也许A算法会不如B算法，而且两种学习器在同一个数据集上也可能会有相似的结果，所以我们需要用一个估计阈值，来判定哪个算法更加好。

假设在N个数据集上比较k个算法，$r_i$的均值和方差分别是$(k+1)/2$和$(k^2-1)/12N$，得到分布函数（推导过程略）

$$T_{X^2}=\frac{12N}{k(k+1)}(\sum _{i=1}^k{r}_i^2-\frac{k(k+1{)}^2}{4})$$$$T_F=\frac{(N-1)T_{X^2}}{N(k-1)-T_{X^2}}$$

$T_{X^2}$为原始Friedman检验分布函数，$T_F$为F检验分布函数；这个算法中，西瓜书明确的给了一个临界值表：

是否可接受的检验仍然同上。

如果所有算法的性能相同这个假设被拒绝了，则需要进行后续检验，来对算法做一个进一步的比较。因为前面的步骤我们只是了解了这k个算法并不是全部性能相同，现在我们需要把性能不相同的学习器“找出来”，并且比较出孰优孰劣。

下面介绍一下Nemenyi检验算法的具体过程：

基本原理是根据两个算法的平均序值之差与CD值比较，如果均值差超过CD值，则说明这两个学习器的性能有差别。

CD值计算公式如下：

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

其中$q_{\alpha }$值的取值表如下：

如果两个序值之差大于CD值，那么平均序值小的算法在一定程度上是要优于平均序值大的算法。

所以回过头来看，平均序值只是一个参考的方面，我们还需要在Friedman检验和Nemenyi后续检验的前提下，才可以比较严谨的用平均序值来衡量算法的优劣。

---

2.5 偏差与方差

定义和公式

1. 偏差-方差分解是解释学习器泛化性能的重要工具。在学习算法中，偏差指的是预测的期望值与真实值的偏差，方差则是每一次预测值与预测值得期望之间的差均方。实际上，偏差体现了学习器预测的准确度，而方差体现了学习器预测的稳定性。

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

   学习算法的期望预测为

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

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

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

   噪声为（假定噪声期望为0，即${\mathbb{E}}_D[y_D-y]=0$.）

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

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

   $$bia{s}^2(x)=(\overline{f}(x)-y{)}^2$$

   则有

   $$E(f;D)=bia{s}^2(x)+var(x)+{\epsilon }^2$$

   也就是说，泛化误差可分解为偏差、方差与噪声之和。

3. 回顾偏差、方差、噪声的含义：

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

偏差-方差窘境

1. 偏差-方差分解说明，泛化性能是学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。给定学习任务，为了取得好的泛化性能，则需使偏差较小，即能够充分拟合数据；并且使方差较小，即使得数据扰动产生的影响小。

2. 偏差-方差窘境(Bias-variance Dilemma)：方差和偏差具有矛盾性，这就是常说的偏差-方差窘境，随着训练程度的提升，期望预测值与真实值之间的差异越来越小，即偏差越来越小，但是另一方面，随着训练程度加大，学习算法对数据集的波动越来越敏感，方差值越来越大。