机器学习-第二章

经验误差与过拟合

错误率=\(\frac{分类错误的样本}{总样本数}\)
精度=1-错误率
学习器的实际预测输出与样本的真实输出之间的差异被称为“误差” 学习器在训练集上的误差为“训练误差”、在新样本上的误差为“泛化误差” 我们的目标是让学习器的泛化误差最小，而实际上因为新样本的不确定，我们只能尽可能地让学习器的训练误差最小。 过拟合是指学习器在通过训练集样本进行训练时，学习能力过于强大，把那些只属于训练集的，但并非是一般化的特征也都学到了；相对于过拟合的概念就是欠拟合。 在现实生活中，对于某一问题，我们有多种可供选择的算法，而每个算法又因不同的参数配置产生出不同的模型。那么如何选择模型呢？其标准自然是选择泛化误差最小的，但我们却无法直接得到泛化误差；同时，训练误差也因为存在过拟合问题从而不适合作为标准。于是我们采取了一种评估方法，即，选用部分样本作为训练集，训练学习器，接下来将训练好的该学习器放在另一部分的样本（测试集）中进行测试，由此得到测试误差。我们将测试误差作为泛化误差的近似，从而对学习器的好坏进行评估。 如何将手头上的数据分为训练集和测试集进行测试，就要采用以下的方法：

评估方法

留出法

将数据集（D）划分成两个互斥的部分，比如有1000个样本的数据集，选用其中的700个作为训练集，剩下的300个用作测试集。（划分数据集时要注意保持数据分布的一致性，即保证训练集和测试集是无差异的）。 之后计算测试误差，比如使用上述的700个样本的数据集D训练模型，将得到的模型在300个样本的测试集中进行测试，发现其将测试集中的90个样本分类错了。就可以得到错误率为\(\frac{90}{300}\)=30%，那么，精度=1-错误率=70% 然后将划分过程随机重复多次，比如进行100次的划分。每次都得到一个错误率，最后留出法就是对这100个错误率进行平均，看所使用的模型的平均错误率有多高。 一般情况下，会将总样本中的\(\frac2{3}\)_{$\frac4{5}$的样本用作训练集，余下的$\frac1{3}$}\(\frac1{5}\)作为测试集。

交叉验证法

留出法是划分为2个部分，而交叉法则是将数据D集划分为k个部分（k>2），所以这一方法又被称为“k折交叉验证”。 比如一般会设置k=10，即划分为10个部分，之后就用9个（k-1个）当做训练集，剩下的1个做测试集。将这10份中，每个都作为测试集1次（其余的另9个作为训练集），就会得到10次结果。另外再把原数据集按照不同的划分方式再划分几次，比如5次，这样就会得到50个训练结果（5次×10折）。 交叉验证的一个极端的办法就是将数据集D（共包含m个样本）划分为m个部分，即k=m。这被称为“留一法”，每个子集中只有一个样本。这样训练集（k-1）≈总数据集（m），这样训练出的效果也就跟使用总数据集几乎是一个效果。但是当数据集中样本过大时，这样的计算量就过大了(如有1百万个数据样本就需要训练1百万个模型)。

自助法

前两个方法由于保留了部分样本用于测试，因此实际评估的模型所使用的训练集比总数据集小。另外，尽管留一法受训练样本规模变化小，但是计算复杂度高。所以为了减少训练样本规模不同造成的影响，同时高效地进行试验估计，就采用自助法（bootstrapping） 对于包含m个样本的数据集D，使用自助采样法对其采样，产生新的数据集D’。 即，每次随机从D中挑选一个样本，放入D’中，然后将该样本再放回D中，再次从D中随机挑选出一个样本（刚才被挑选出的样本仍有可能再次被选到），放入D’中，不断重复这一过程m次。这样新生成的数据集D’中也就有了和D一样的样本个数。 因为是重复采样，所以仍然会有一些样本一次都没有被选入D’中，这一始终不被采样到的概率是\((1−\frac{1}m)m\),其极限为\(\frac{1}e\)(≈37%)。这样，始终不被采样的这37%的数据就可以用于测试集。 自助法在数据集较小，难以划分训练/测试集时很有用。 但是，自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差。因此，在数据量足够时，更多会采用留出法和交叉验证法。

调参与最终模型

大多数学习算法都有参数需要设定。在选择完算法后，对于算法的参数进行调节就是调参。 我们可以对一个算法中所需要的每种参数配置都训练出模型，然后挑选出最好的模型中所使用的参数。 然而现实中，试遍所有参数几乎是不可能的，于是我们就会对每个参数选定一个范围和变化步长进行计算。比如在[0，0.2]的范围内以0.05为步长，测试0，0.05，0.10，0.15，0.20这五个参数。然后从这5个数中选择最合适的。 当算法和参数已经选定好之后，这时需要再用所有的数据m，即用整个数据集D来再度训练模型。

性能度量

衡量模型能力的泛化能力的评价标准就是性能度量。在对比不同的模型能力的时候，使用不同的性能度量往往会导致不同的评判结果。
我们使用均方误差来对学习器的性能进行度量，即，学习器(f)对每个样本(\(x_i\))计算得到的数值(\(f(x_i)\))与真实数值(\(y_i\))进行比较，得到预测值与真实值的误差，然后对每个样本计算得到的误差进行求和，最后再求出均值。

均方误差=$$\frac{1}m\sum_{i=1}^{{m}(f(x_i)-y_i)}2$$

错误率与精度

结合本章开头提到的错误率与精度，对于数据集D：

分类错误率=$$\frac{1}m\sum_{i=1}^{m}Ⅱ(f(x_i)\not=y_i)$$

(Ⅱ在这里表示指示函数，即它后面的函数取值或者为0，或者为1)

精度=1-分类错误率=分类错误率=$$\frac{1}m\sum_{i=1}^{m}Ⅱ(f(x_i)=y_i)$$

查准率、查全率与F1

错误率与精度虽然常用，但是并不能满足所有任务需求。有时我们希望知道的是“被当作好西瓜挑出来的西瓜中确实是好西瓜的比例”或者“真正的好瓜中有多少是被伯乐挑出来了”。此时就会出现四种情况。

真正例（TP：好的西瓜，并且模型也认为是好的西瓜）

假正例（FP：坏的西瓜，但是模型认为是好的西瓜）

假反例（FN：好的西瓜，但是模型认为是坏的西瓜）

真反例（TN：坏的西瓜，并且模型也认为是坏的西瓜）
于是有：

查准率Precision=$$\frac{真正例（TP）}{真正例（TP）+假正例（FP）}$$；即，被当作好西瓜挑出来的西瓜中确实是好西瓜的比例

查全率Recall=$$\frac{真正例（TP）}{真正例（TP）+假反例（FN）}$$；即，真正的好瓜中有多少是被伯乐挑出来了

查准率与查全率是对矛盾的度量。因为比如查准率高，就意味着模型越保守，只会选择那些非常有把握的瓜，这样漏掉的好瓜也会增多。

如果我们有多个模型，则可以分别计算每个模型的查准率和查全率来比较模型的好坏。比如，我们有一个模型A来预测西瓜的好坏，对于每个样本（100个）输入，它输出一个计算结果（模型的预测值100个，即每个瓜的得分）。我们将这100的得分从大到小排序，分数越大的瓜就表示模型预测这个瓜更好。这时我们来设定阈值，比如好瓜的得分标准是60分，80分还是90分等等。每设定一个阈值（相当于将上图中间的区分左右两边颜色的竖线从最左一直移到最后），就可以计算出一次该阈值下，模型A的好坏瓜预测情况的查准率和查全率。如下图中的左图所示，横轴是查全率，纵轴是查准率，绿色曲线是模型A的数值变化，蓝线是模型B。判断这两个模型的好坏，只要看哪一个曲线在外面就可以了，因为在外面的曲线上任选一点，得到一对查准率和查全率，里面曲线上具有相同查准率（or查全率）的那一点，它相应的查全率（or查准率）肯定要小于外面曲线上的。

我们在该图上如果画上函数y=x的直线，那么该直线与模型A（绿色）和B（蓝色）的曲线的交点就是在该曲线上查全率=查准率的点（平衡点 Break-Even Point）。显然可以发现，绿色曲线的平衡点的数值肯定要小于蓝色曲线的（该点上绿色曲线的查准率和查全率都要高于蓝色曲线），于是就可以判断，蓝色曲线（模型B）要优于绿色曲线（模型A）。

除了比较平衡点之外，更常用的是被称为F1度量的办法来比较不同的模型的优劣。

\[F1=\frac{2×查准率×查全率}{查准率+查全率}=\frac{2×真正例}{总样本数+真正例-真反例}
\]

实际上，F1的含义如下

\(\frac1{F1}=\frac1{2}(\frac1{查准率}+\frac1{查全率})\)，本质上还是平衡点，只是这一公式比算术平均（\(\frac{查准率+查全率}2\)）或者几何平均(\(\sqrt{查准率×查全率}\))更重视最小值。

不同应用中，对于查准率和查全率的重视程度不同：比如在商品推荐系统中，为了尽可能不打扰用户，推荐顾客更感兴趣的东西，查准率更重要；而在逃犯信息检索系统中，希望少漏掉逃犯，此时查全率更重要。

于是引进一个参数\(\beta\),得到F1度量的一般形式--\(F_\beta\)。当\(\beta\)>1时，查全率有更大影响，而\(\beta\)<1时查准率有更大影响。

\(F_\beta=\frac{(1+\beta^2)×查准率×查全率}{(\beta^2×查准率)+查全率}\)

ROC与AUC

很多学习器是为测试样本产生一个相应的预测值，然后设定一个阈值（截断点），来与生成的预测值进行比较，如果大于阈值则是正例，小于就是反例。例如可将预测值的范围设置在[0.0 1.0]之内，然后设定0.5为阈值，大于0.5的就当是正例。

在不同任务中可以根据需求来选择截断点的值。我们将预测的值从大到小排列出来，如果我们重视查准率，就可以把截断点的值设得高一些，只选择排名靠前的那些预测值，认为满足这一截断点值的瓜的评分才代表是好瓜；如果重视查全率，就可以把截断点的值设置得低一些。假设西瓜基本上是长得越大越成熟、也越甜，那么如果我们以个头作为西瓜的好坏标准的话，截断点选择的数值越大，那么比截断点值还要个头大的瓜肯定大都是好瓜（查准率高），为了让个头虽然不是很大但也仍然很甜的瓜也被选进来的话（查全率高），我们就需要把截断点的值选择的相对低一点。

这样，我们对于某一个模型预测出来的值，可以试遍所有的阈值，然后在每个阈值下计算出如下两个指标（这跟上一接所述的查准、查全率曲线非常接近，只是计算时的分母和分子略有不同）：

真正例率=\(\frac{真正例}{真正例+假反例}\)=\(\frac{被模型正确预测出的正例数}{实际情况下的所有正例数}\)=查全率（真正的好瓜中有多少是被伯乐挑出来了）

假正例率=\(\frac{假正例}{假正例+真反例}\)=\(\frac{实际情况下是反例的被模型误以为是正例的个数}{实际情况下的所有反例数}\)=坏瓜中间被当作好瓜挑出来的比例

我们肯定是希望得到一个真正例率高同时假正例率低的模型，为了更直观地看到不同模型的这两个指标的的差别，我们将每对(假正例率，真正例率)值的当作一个坐标（x,y）画出来，即以真正例率为纵轴坐标、假正例率为横轴坐标绘制。这样就会形成一个曲线，我们把这条曲线称之为ROC（Receiver Operating Characteristic）曲线---ROC曲线本身也是二战时候用于检测敌机的雷达分析技术，后来多用于生物、心理学、制药等领域，是比如判断几种不同的药物的好坏的评估办法之一。

参看上图的右边的两条曲线，很明显，蓝色曲线代表的模型较好，因为和绿色的相比，当他们假正例率相同的情况下，蓝色曲线的真正例率都是要高的。为了在量上对这两个模型进行比较，我们使用AUC（Area Under ROC curve）计算面积，即用积分计算出每条ROC曲线下方区域、和横纵轴形成的类似扇形区域的面积，然后面积越大的就表示该模型越好。

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

把坏瓜错划分成好瓜，或者好瓜错划分成坏瓜虽然都是错误划分，但是其造成的后果会不同。好瓜当成坏瓜只是扔掉了一只瓜，但是坏的当成好的吃了可能会吃坏肚子上医院，成本更高。我们将不同类型错误所造成的不同损失的情况称为“非均等代价（unequal cost）”

对于这种代价，记为\(cost_{ij}\)，即表示将第i类样本预测为第j类样本的代价。以二分类任务为例（第0类和第1类），则会有两种情况，分别是\(cost_{01}\)和\(cost_{10}\)，假设0类表示坏瓜，1类表示好瓜，那么显然\(cost_{01}\>>cost_{10}\)

在非均等代价的情况下，我们不仅希望错误率低，还希望总体代价也很低。即\(cost_{01}\)与\(cost_{10}\)的和的均值很低。这里我们采用一个指标：

代价敏感（cost-sensitive）=\(\frac1{m}(\sum_{x_{i}\in{D^+}}Ⅱ(f(x_i)\not=y_i)×cost_{01}+\sum_{x_{i}\in{D^-}}Ⅱ(f(x_i)\not=y_i)×cost_{10})\)

其中\(D^+D^-\)分别表示数据集D中正例子集和反例子集

比较检验

虽然有了性能度量方法，但是我们却并不能直接通过比较不同模型的性能度量值的大小来决定模型的好坏。因为

1）实验评估得到的是测试集上的性能，这与我们希望比较的泛化性能未必一致

2）测试集上的性能与测试集本身的选择有关，不同大小的测试集得到的结果会不同，而且相同大小的测试集中如果测试样例不同，结果也可能会不同

3）很多机器学习算法本身有随机性，即便在同一测试集上使用相同的参数设置运行，每次运行得到的记过也会不同。

所以我们使用统计假设检验对学习器的性能进行比较

假设检验

假设是指对学习器泛化错误率分布的猜想。我们需要根据测试错误率来推断出与其接近的泛化错误率。

我们希望知道的是泛化错误率\(\epsilon\)（=学习器在一个样本上犯错的概率），测试错误率为\(\widehat{\epsilon}\)（=我们从测试样本中实际得到的犯错概率）

P\((\widehat{\epsilon},\epsilon)\)\(=\)\(\begin{pmatrix}m\\\widehat{\epsilon}×m\end{pmatrix}\epsilon^{\widehat{\epsilon}×m}(1-\epsilon)^{m-{\widehat{\epsilon}×m}}\)

这正是一个二项式分布，即表示在m次事件中，碰巧发生\(\widehat{\epsilon}×m\)次情况的概率。假设我们有一个模型来预测一张图片是男是女，模型用的是根据头发长短来判断的办法，一般情况下模型都是预测准确的（短发为男、长发为女），但是总体而言有3%（泛化错误率）的概率会预测错（因为有时男生也会是长发）。因为我们每次测试的样本有限，可能碰巧在测试的样本集中间混入了比较多的长头发的男生，于是模型就很容易预测错，出现了更高的例如5%的错误概率（测试错误率）。上述公式即表示样本错误率应该为3%概率时，但因为样本选择的问题以致于我们观测到了错误率为5%的情况的概率。

假设我们有10个样本，并假定泛化错误率为0.3，那么观测到3个样本被错误分类的可能性会很大，而错误分类出4、5、6个甚至更多的概率会比较小。此时我们的假设检验即为检验“泛化错误率是否不大于0.3”这一判断。于是对错误分类出4个、5个...10个等7种情况的概率进行求和（\(\alpha=\sum_{i=4}^{10}P_i\)），一般情况下会选择0.05或0.1作为显著度标准，看超出3个分类错误的情况的概率值和\(\alpha\)是否大于0.05或0.1，如果大于则拒绝假设，认为返回错误率大于0.3；小于的话则接受假设。

在对单个学习器的泛化性能的假设进行检验时,很多时候我们并非只进行一次留出法估计，而是重复多次留出法或是交叉验证法进行多次训练或测试。这样我们就会得到多个测试错误率。首先假设我们认为泛化错误率是一个值，即\(\epsilon\)，然后实际上我们重复计算得到了k个测试错误率，\(\widehat{\epsilon}_1,\widehat{\epsilon}_2,...,\widehat{\epsilon}_k\),我们对这k个测试错误率求出平均值\(\mu\)和方差\(\sigma^2\)，考虑到这k个测试错误率可以看作是泛化错误率\(\epsilon\)的独立采样，于是变量\(\tau_t=\frac{\sqrt{k}(\mu-\epsilon)}{\sigma}\)就服从自由度为k-1的t分布。

然后我们使用t-test来检验我们假定的泛化错误率\(\epsilon\)和得到的平均测试错误率\(\mu\)是否相同，即“\(\epsilon\)\(=\)\(\mu\)”是否成立。在\(1-\alpha\)概率内观测到的最大错误率即临界值（比如0.3）。如果平均错误率与我们认为的泛化错误率之差（\(|\mu-\epsilon|\)）在临界值范围内则不能拒绝\(\mu=\epsilon\)的假设。此时认为\(\epsilon\)等于平均值\(\mu\)。否则可拒绝该假设（因为概率极低的事件频繁发生了），认为泛化错误率明显不应该是我们设定的\(\epsilon\)（比如0.3）这个值。

交叉验证t检验（两个模型的比较，使用交叉法时）

以上是对单个学习器泛化性能的假设进行检验，但更多情况下我们需要对不同的学习器性能进行比较，交叉验证t检验即是比较方法之一。

对于两个学习器A和B，如果他们的性能相同，则他们的测试错误率应该相同，即，\(\epsilon_i^A=\epsilon_i^B\)。我们可以使用成对t检验（paired t-tests）进行检验，对k折交叉验证产生的k对测试错误率求差，\(\Delta_i=\epsilon_i^A-\epsilon_i^B\),然后看该差是否显著不等于零。

然而，通常情况下由于样本有限，使用交叉验证等实验估计方法时，不同轮次的训练集会有一定程度的重叠，这导致测试错误率实际上并不独立、产生过高估计假设成立的概率。为了缓解这一问题，可采用“5×2交叉验证”。即做5次2折交叉验证。在每次2折交叉验证之前随机将数据打乱，是的5次交叉验证中的数据划分不重复。这里的一个技巧是，用于t检验的平均值\(\mu\)，并不是5×2次计算的数值的平均值，而是只使用第1折交叉验证时模型A和模型B的差值来做平均，即\(\mu=0.5(\Delta_1^1+\Delta_1^2)\),由此缓解测试错误率的非独立性。但是方差计算时使用了每次2折实验的结果。然后用自由度为5的t分布进行统计检验。

McNemar检验（两个模型的比较，使用留一法时）

McNemar检验是指这样一种检验：比如全班20个人的考试中

第一次考试结果为：7人及格、13人不及格

第二次考试结果为：14人及格、6人不及格

那么第二次考试结果是否比第一次好呢？如果采用Fisher检验的话，这两次考试是无区别的，但是如果我们仔细看数据，会发现如下结果：

两次考试都及格和都不及格的分别是6人和5人。除了他们之外，

第一次不及格但是第二次及格的：8人（成绩变好）

第一次及格但是第二次不及格的：1人（成绩变坏）

由此可以发现，实际上第二次考试结果是比第一次要好的，McNemar检验就是忽略掉那些两次考试没有变化的人，而专注有变化的人（8人变好、1人变坏）之间是否是有差异的。这一检验的本质相当于二项式检验（是实际计算中采用卡方检验），等同于判断9次掷硬币后出现了8次正面、1次反面的情况是否是正常的。

于是对于在二分类问题下，使用留出法的两个模型A和B进行比较检验时，就是忽略那些在两个模型下都同时判断为正确或错误的那些样本，比较在A模型中判断为正确但是B模型判断为错误的样本\(e_{01}\)和**B模型中判断为正确但是A模型判断为错误的样本\(e_{10}\)$*的数量是否相等。此时统计量服从自由度为1（k=1）的卡方分布，所以进行卡方检验即可。

Friedman检验和Nemenyi检验（多个模型的比较）

对于多个模型本来可以采用方差分析进行比较检验，但是因为不能保证样本能满足正态分布，所以采用Friedman检验。

具体比如有A、B、C三个模型，以及多个数据集（D1、D2、D3、D4）。

这里对于每个数据集，对A、B、C这三个模型的好坏进行排名（第1、2、3名），然后比较三个模型在所有数据集下的排名的平均值（比如算法A在四个数据集下排名都是第一，那么其均值也是第一）。要检验的假设就是这三个模型的排名均值是否是相同的。

进一步如果检验结果发现“这三个算法的性能相同”的假设不成立，那么就意味着这三者的性能显著不同。于是采取后续检验（post-hoc test）来进一步区分各算法。

偏差与方差

对于学习算法除了通过实验估计其泛化性能外，人们往往还希望了解它为什么具有这样的性能。我们可以把泛化误差分解为如下的公式情况。

\(泛化误差=bisa^2(x)+var(x)+\epsilon^2\)

其中的bias表示偏差，即我们期望学习算法所计算出的输出与真实结果的偏离程度（代表的是算法本身的拟合能力）；var表示方差，即使所使用的训练集大小都是相同的，但如果训练集不同（或者说变动），也会导致学习性能发生变化（代表的是数据扰动带来的影响）；\(\epsilon\)表示噪声，表达了当前任务下任何学习算法所能达到的期望泛化误差的下限（代表的是学习问题本身的难度）。

偏差与方差是相互冲突的，当训练不足、学习器的拟合能力还不强时，训练数据的扰动不足以让学习器产生显著变化，此时偏差主导了泛化错误率；随着训练加深，学习器的拟合能力增强，方差将主导泛化误差；等到充分训练之后，学习器的拟合能力已经非常强，训练数据的任何轻微扰动都会导致学习器发生显著变化，若训练数据自身的、非全局性的特性被学习器学到了的话，就会出现过拟合。