西瓜书笔记2 模型评估与选择

经验误差与过拟合

几个概念问题

精度与错误率

m个样本中有a个样本分类错误，则

错误率 $E=\frac{a}{m}$ 精度 $1-\frac{a}{m}$

误差

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

训练误差（经验误差）：学习器在训练集上的误差

泛化误差：学习器在新样本上的误差

过拟合与欠拟合

过拟合：学习器把训练样本自身的特点当做了所有潜在样本都有具有的一般性质

欠拟合：对训练样本的一般性质尚未学好

评估方法

我们只有一个包含m个样例的数据集$D=\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),…,(\boldsymbol{x}_m,y_m)\}$，如何划分出训练集$S$和测试机$T$呢。

留出法（hold-out）

将数据集$D$划分为两个互斥的集合，其中一个集合作为训练集$S$，另一个作为测试集$T$，即

$$D = S\cup{T},\ S\cap{T}=\varnothing$$

需注意，训练\测试集的划分要尽量保持数据分布的一致性（尽量同分布）。

交叉验证法（cross validation）

将数据集$D$划分为k个大小相似的互斥子集，即

$$D=D_1\cup{D}_2\cup...\cup{D}_k, \ D_i\cap{D}_j=\varnothing(i\neq{j})$$

每个子集都尽可能保持数据分布的一致性。

每次用k-1个子集的并集训练，余下的那个子集测试，这样就获得了k组训练\测试集，结果取k次的均值。称为“k折交叉验证”，k最常用的取值时10。

留一法（Leave-One_out，简称LOO）：$k=m$时的特例。每次拿1个样本测试，其他m-1个样本训练。缺陷：数据集较大时不适用。

自助法（bootstrapping）

在留出法和交叉验证法中，训练集都比D小，这必然会引入一些因训练规模不同而导致的估计偏差（Why？？）。自助法是一个比较好的解决方案。

自助法（以自主采样（bootstrap sampling）为基础）：给定样本集$D$，我们对它进行采样产生数据集$D’$：每次随机从$D$中挑选一个样本，将其拷贝到$D’$中，再将其放回；重复m次。

显然，$D$中有一部分样本会在$D’$中多次出现，而另一部分样本不出现。
做一个简单的估计：样本在m次采样中始终不被采到的概率是$(1-\frac{1}{m})^m$，取极限得

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

即通过自主采样，$D$中约有36.8%的样本未出现在$D’$中。
我们将$D’$作为训练集，$D\setminus{D}’$作为测试集。使我们的训练集规模达到m的同时，还有约36.8的样本可用于测试，这样的测试结果也叫“包外估计(out-of-bag estimate)”

优点：
自助法在训练集较小、难以有效划分训练/测试集是很有用；
能从$D$中产生多个不同的训练集，对集成学习有很大好处；
缺点：
自助法产生的数据集改变了原始数据集的分布，会引入估计偏差。
（因为在初始数据量足够时，留出法和交叉验证法更常用）

性能度量

在预测任务中，给定样例集$D=\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),…,(\boldsymbol{x}_m,y_m)\}$，要评估学习器$f$的性能，就要把学习器预测结果$f(\boldsymbol{x})$与真实标记$y$进行比较，记$\hat{y} = f(\boldsymbol{x})$。

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

$$E(f;D)=\frac{1}{m}\sum_{i=1}^m(\hat{y}_i-y_i)$$

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

$$E(f;\mathcal{D})=\int_{\boldsymbol{x}\sim\mathcal{D}}p(\boldsymbol{x})\cdot(\hat{y}-y)^2d\boldsymbol{x}$$

本节下面重要介绍分类任务中常用的性能度量

错误率与精度

分类任务中最常用的性能度量，既适用于二分类，也适用于多分类。
错误率：分类错误样本数占样本总数比例。

$$E(f;D)=\frac{1}{m}\sum_{i=1}^m\mathbb{I}(f(\boldsymbol{x}_i)\neq{y}_i)$$

精度：分类正确样本数占样本总数比例。

$$acc(f;D)=\frac{1}{m}\sum_{i=1}^m\mathbb{I}(f(\boldsymbol{x}_i=y_i))$$

易知

$$E(f;D)+acc(f;D)=1$$

查准率、查全率、F1

对于二分类问题，可将样例根据其真实类别与学习器预测类别划分为

分类结果混淆矩阵

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

查准率（准确率 precision）

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

查全率（召回率 recall）

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

以西瓜问题为例，假定瓜农拉来一车西瓜，我们用训练好的模型对这些西瓜进行判别。错误率是衡量有多少比例的瓜被误判；查准率是衡量挑出的西瓜中有多少比例是好瓜；查全率是衡量有多少好瓜被挑出来了。

P-R曲线
我们可以根据学习器的预测结果对样例进行排序，排在最前面的是学习器认为“最可能”是正例的样本，排在最后的是学习器认为“最不可能”是正例的样本。（可参考P183的类概率）
按此顺序作为正例进行预测，每次计算出当前的查全率、查准率，进行画图。

(感觉图中，查全率为1.0是，查准率降到0有问题，应该降到精度值吧)

• 若我们更重视“查准率”，则可选择排序中靠前的位置进行截断；若更重视“查全率”，则选择靠后的位置进行截断。
• 若一个学习器的P-R曲线被另一个学习器的曲线完全“包住”，则可断言，后者性能优于前者。（A优于C）
• 如果两个学习器的P-R曲线发生了交叉，则难以一般断言。

平衡点（Break-Even Point，简称BEP）度量
平衡点是“查准率=查全率”时的取值

F1度量

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

在一些应用中，对查全率和查准率的重视程度有所不同。例如商品推荐系统中，希望推荐内容确实是用户感兴趣的，此时查准率更重要；在逃犯信息检索系统中，希望尽可能少漏掉逃犯，查全率更重要。

$F_{\beta}$度量：F1度量的一般形式

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

$\beta>1$时查全率有更大影响，$\beta<1$是查准率有更大影响。

F1是基于查准率和查全率的调和平均定义的：

$$\frac{1}{F1}=\frac{1}{2}\cdot(\frac{1}{P}+\frac{1}{R})$$

$F_{\beta}$则是加权调和平均：

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

与算数平均$(\frac{P+R}{2})$和几何平均$(\sqrt{P\times{R}})$相比，调和平均更重视较小值

ROC与AUC

首先，和P-R曲线一样，按照样本属于正例的概率进行排序。
不同的是，ROC曲线纵轴是“真正率”（True Positive Rate，简称TPR），横轴是“假正率”（False Positive Rate，简称FPR）。

好瓜中有多少比例被挑出来了（recall）

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

坏瓜中有多少比例被挑出来了

$$FPR=\frac{FP}{TN+FP}$$

对角线对应于“随机猜测”模型。

绘制过程：

给定$m^+$个正例和$m^-$个反例，根据学习器预测结果对样例进行排序，然后把分类阈值设为最大，即吧所有样例均预测为反例，此时真正例率和假正例率均为0，在坐标（0,0）处标记一个点。然后将分类阈值依次设为每个样例的预测值，即依次将每个样例划分为正例。设前一个标记点坐标为（$x,y$），当前若为真正例，则对应标记点的坐标为（$x,y+\frac{1}{m^+}$）；当前若为假正例，则对应标记点的坐标为（$x+\frac{1}{m^-},y$），然后用线段连接相邻点即得。

• 若一个学习器的ROC曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者；
• 若两个学习器的ROC曲线发生了交叉，则难以一般性的断言，此时较为合理的判据是比较ROC曲线下的面积，即AUC。

AUC（Area Under ROC Curve）
假定ROC曲线是由坐标$\{(x_1,y_1),(x_2,y_2),…,(x_m,y_m)\}$的点按序连接而形成的。则AUC可以通过计算一个个小矩形进行估算

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

给定$m^+$个正例和$m^-$个反例，令$D^+$和$D^-$表示正反例集合，则排序损失定义为

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

即考虑每一对正、反例，若正例预测值小于反例，则计一个“罚分”；若相等，则计0.5个。

$\ell_{rank}$对应的是ROC曲线之上的面积，即曲线对纵轴进行积分。AUC是曲线对横轴进行积分。因此有

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

简单证明一下

首先不考虑某个正例和反例预测值相等的情况，原因如下：
如果某个正例与反例预测值相等，则将该正例排序在前或者将反例置前，其AUC的值不同，所以AUC应取个平均，即对应排序损失中的0.5个“罚分”。现在讨论固定AUC下的排序损失，暂不考虑相等情况。
则此时排序损失应为

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

曲线对纵轴的积分为：

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

AUC是对横轴的积分，所以（2）式等于$1-AUC$；现在要证明这个积分等于$\ell_{rank}$。


以下证明（1）式等于（2）式：

前一个标记点坐标为$(x_i,y_i)$，当前若为真正例，则对应标记点的坐标为$(x_i,y_i+\frac{1}{m^+})$；当前若为假正例，则对应标记点的坐标为$(x_i+\frac{1}{m^-},y_i)$。即若当前为假正例时$y_{i+1}-y_{i}=0$；若为真正例时$y_{i+1}-y_i=\frac{1}{m^+},x_{i+1}=x_i$。所以（2）式等价于以下（3）式

$$\sum_{\boldsymbol{x}^+\in{D}^+}\frac{x^+}{m^+}=\frac{1}{m^+}\sum_{\boldsymbol{x}^+\in{D}^+}x^+ \tag{3}$$

对于每个真正例坐标$(\boldsymbol{x},y)$，根据绘图规则可知$\boldsymbol{x}$的来历是，每遇到一个假正例便累计$\frac{1}{m^-}$。所以$\boldsymbol{x} = 排序在该真正例前的所有假正例的个数 \times \frac{1}{m^-}$，即

$$\boldsymbol{x}^+=\frac{1}{m^-}\sum_{\boldsymbol{x}^-\in{D}^-}\mathbb{I}(f(\boldsymbol{x}^+)=f(\boldsymbol{x}^-))\tag{4}$$

将（4）式带入（3）式可得（1）式。

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

一般情况下，将A错误分类到B和将B错误分类为A的代价都为1，分类正确的代价都为0。
本节考虑不同的错误类型所造成的后果不同，代价也不同。
二分类任务为例，如图$cost_{ij}$表示将第$i$类样本预测为第$j$类样本的代价。

二分类代价矩阵

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

一般情况下，重要的是代价比例而非绝对值，例如$cost_{01}:cost_{10}=5:1$与$50:10$所起的效果相当。

偏差与方差

我们知道，算法在不同训练集上学得的结果很可能不同，即便这些训练集是来自同一个分布。

对测试样本$\boldsymbol{x}$，令$y_D$为$\boldsymbol{x}$在数据集中的标记，$y$为$\boldsymbol{x}$的真实标记，$f(\boldsymbol{x};D)$为训练集$D$上学得模型$f$在$\boldsymbol{x}$上的预测输出。

以回归任务为例，学习算法的期望预测为：

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

假设算法在样本数相同的不同训练集上学得多个结果，
期望预测，就是多个结果的期望。

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

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

每个不同的训练集上预测的结果，相对期望结果，都有个方差

噪声为

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

数据集中的标记与真实标记不同

期望输出与真实标记的差别称为偏差

$$bias^2(\boldsymbol{x})=(\overline{f}(\boldsymbol{x})-y)^2$$

对算法的期望泛化误差进行分解：

$$E(f;D)=bias^2(\boldsymbol{x})+var(\boldsymbol{x})+\varepsilon^2$$

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

偏差-方差窘境
一般来说，偏差与方差是有冲突的。

• 训练不足时，学习器的拟合能力不够强，训练数据的扰动不足以使学习器产生显著变化，此时偏差主导了泛化错误率；
• 随着训练程度的加深，学习器的拟合能力逐渐增强，训练数据发生的扰动渐渐被学习器学到，方差逐渐主导了泛化错误率；
• 在训练程度充足后，学习器的拟合能力已非常强，训练数据发生的轻微扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特性被学习器学到了，则会发生过拟合。

最后补充一下，吴文达深度学习课里的内容：

两种情景

	情景1	情景2	情景3	情景4
Train set error	1%	15%	15%	0.5%
Dev set error	11%	16%	30%	1%
Problems	High Variance	High Bias	High Variance	Low Variance
			High Bias	Low Bias

第一种情况，问题是方差太大，可能面临过拟合
第二种情况，问题是偏差太大，可能面临欠拟合