经验误差与过拟合

假设有m个样本，a个分类出现了错误，那么错误率$E$为

$$E=\frac{a}{m}$$

$$精度=1 - 错误率$$

误差

预测输出与样本的真实输出之间的差异称为“==误差==”

学习器在训练集上的误差称为“训练误差”或者“经验误差”

在新样本上的误差称为“泛化误差”

过拟合与欠拟合

我们总是希望能够将误差最小化，最终获得准确度高，泛化能力较好的模型。这两者在一定程度是是相互冲突的。模型在测试集的准确度“太好”的时候，泛化能力会下降，在新的样本中表现不佳，称为“==过拟合==”；然而，模型训练的不够好，那么同样无法准确对样本进行预测，这个时候的泛化能力几乎毫无意义，称为“==欠拟合==”

在现实任务中，我们通常有多种学习算法可供选择，甚至不同的参数配置，都会产生不同的模型，那么，我们需要选择合适的学习算法和参数配置，这就是机器学习中的“==模式选择（model selection）==”问题。

评估方法

通过“==测试集(Testing Set)==”来测试学习器对新样本的判断能力，然后把测试集的“测试误差”近似看做泛化误差。

测试样本要满足：

• 测试样本从样本真实分布中独立同分布采样而得
• 测试集与训练集尽量互斥

留出法

“留出法”（hold-out）直接将数据集$D$划分为两个互斥的集合，其中一个作为训练集$S$，另外一个作为测试集$T$。

以二分类举例，假设D=1000,S=700,那么T=300

经过测试集测试，假设有90个样本出现错误，那么$TestingError = \frac{90}{300} \times 100% = 30%$，相应的精度为$70%$。

在进行划分时，要注意数据集中尽量包含各种类别的数据，还要注意多次划分，重复训练评估。因为我们每次划分训练出来的结果都可能存在差异，所以单次评估一般是不可靠的，需要进行多次评估取平均值。

对于数据集，一般取==$\frac{2}{3} - \frac{4}{5}$==作为训练集，剩余部分作为测试集。

交叉验证法

将数据集D划分为k个大小相似的互斥子集，每个子集决斗尽可能保持数据分布的一致性：

每次使用k-1个作为训练集，剩下1个作为测试集，进行k次测试，获得k个验证结果，将平均值作为返回结果。所以交叉验证法称为“k折交叉验证”(k-fold cross validation)。如图所示为10折交叉验证过程：

为了减少因为样本划分不同而产生的误差，我们在进行k折交叉验证的时候随机使用不同的划分重复p次，最后取p次结果的均值，称为：p次k折交叉验证。比如常见的“10次10折交叉验证”

• 特例：留一法

  数据集中的样本只保留一个样本进行测试，这样就不会收到随机样本划分而带来的影响，因此留一法的评估结果一般比较准确

  缺点：数据量较大时，计算量过大。

自助法

自助法以自助采样为基础，给定包含m个数据集的样本$D$，我们对他进行采样产生数据集$D’$:每次随机从D中挑选一个样本，==拷贝==(样本保留在D中，以便下次采样依然可能被采到)放入$D'$；重复m次，获得了包含m个样本的数据集$D'$。可以得到：样本在m次采样中始终不被采到的概率为$(1-\frac{1}{m})^m$,取极限获得：

我们可将$D'$作为训练集，$D$/$D'$作为测试集。实际评估的模型与期望评估的模型都是用m个训练样本，但是我们仍然有大约1/3的数据没有在训练集中出现，可以用于测试，这样的测试结果也被称为“包外估计”(out-of-bag estimate).

这种方法适用于数据量较小，难以有效划分的情况下，此外，对集成学习等方法有很大的帮助。

但是注意，因为改变了原始数据集的分布，这会引入估计误差，因此在数据量充足时，留出法和交叉验证法更常用。

性能度量

性能度量(performance measure)：衡量模型泛化能力的评价标准

性能度量反应了任务需求，模型的好坏是相对的，不进取决于算法和数据，还取决于任务需求。

在预测任务中，给定例集$D = {(x_1,y_1),(x_2,y_2),...,(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 $$

更一般的，对于数据分布和概率密度函数$p(.)$,均方差可描述为：

错误率与精度

错误率：分类错误占的比例

精度：分类正确占的比例

这两个是最常用的性能度量.

查准率、查全率与$F1$

查准率(precision, P) $\to$ 准确度

查全率(recall, R) $\to$ 召回率

错误率和精度虽然常用，但是不能满足所有的需求。

这里仅将书中几处介绍查准率(Precision)和查全率(Recall)意义的描述摘录出来。

(1)瓜农拉来一车西瓜，我们用训练好的模型对这些西瓜进行判别，查准率衡量的是“挑出的西瓜中有多少比例是好瓜”，查全率衡量的是“所有好瓜中有多少比例被挑出来了”。

(2)信息检索中，查准率衡量的是“检索出的信息中有多少比例是用户感兴趣的”，查全率衡量的是“用户感兴趣的信息中有多少被检索出来了”。

商品推荐系统中，为了尽可能少的打扰用户，更希望推荐内容确是用户感兴趣的，此时查准率更重要；在逃犯信息检索系统中，更希望尽可能少漏掉逃犯，此时查全率更加重要。

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

真正例(True Positive, TP)、假正例(Flase Positive, FP)、真反例(True Negative, TN)、假反例(False Negative, FN)

$D_总 = TP+FP+TN+FN$

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

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

查准率是一对矛盾的度量，一般来说，查准率高，查全率就低。但是在一些简单的情况下这两者都可以很高

很多情况下，更具预测结果对样例排序，排在前面的是认为最可能是正例的样本，后面的是最不可能是正例的样本。

按照次顺序逐个把样本作为正例进行预测，则每次可以计算出当前的查全率、查准率，作$P-R$图

若一个学习器的"P-R"曲线被另一个学习器的曲线完全“包住”，则可断言，后者的性能优于前者，例如图中AB优于C。但是如果交叉，那就很难进行断言孰优孰劣，例如AB。

平衡点(Break-Even Point, BEP)就是综合考虑P、R的性能度量，他是$P = R$时的取值，例如图中C的$BEP=0.64$，A的$BEP = 0.8$基于平衡点的比较，可以认为A优于B。

但是,EBP还是过于简化，更常用的是F1度量：

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

已知数据集D，其中标记 $ y_i \in {0,1}$ （1 表示正例，0 表示反例）；设$x_i$ 的二值化预测结果为 $h_i \in {0，1}$，则

调和平均：

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

F1 是查准率和查全率的合成指标，可以理解为综合考虑了查准率和查全率的性能度量指标，这个指标更加面向类别不平衡问题（参见第 66~67 页第 3.6 节），例如某数据集 99%为正例，剩余 1%为反例，此时分类器只须一直预测正例即可获得 1%的错误率，然后这显然并没有什么意义。

由于一些特殊情况下，对于P与R的重视程度不同,所以给出更一般的式子：

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

加权调和平均

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

$\beta \to$R对P相对重要性：

$\beta=1 \to$同样重要，等于F1

$\beta>1 \to$R更重要

$\beta<1 \to$P更重要

很多时候我们有多个二分类混合矩阵，比如：

我们希望在n个二分类混淆矩阵上综合考察P和R:

• 方法一：

  分别计算各混淆矩阵的P和R,记作：

  $$(P_1,R_1),(P_2,R_2),...,(P_n,R_n)$$

  求平均值：

  宏查准率：$macro-P=\frac{1}{n}\sum_{i=1}^np_i$

  宏查全率：$macro-R=\frac{1}{n}\sum_{i=1}^nR_i$

  宏F1:$macro-F1 = \frac{2\times macro-P \times macro-R}{macro-P+macro-R}$

• 方法二：

  将混淆矩阵各对应元素平均，得到：

  $$\overline{TP},\overline{FP},\overline{TN},\overline{FN}$$

  根据结果计算：

  微查准率：$macro-P=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}$

  微查全率：$macro-R=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}$

  微F1:$macro-F1 = \frac{2\times macro-P \times macro-R}{macro-P+macro-R}$

ROC与AUC

受试者工作特征(Receiver Operating Characteristic, ROC)

ROC曲线下面积(Area Under ROC Curve)

很多学习器是微测试样本产生一个实值或者概率预测，然后将这个预测值与一个分类阈值(threshold)进行比较，若大于阈值则为正例，小于阈值则为反例。例如logistic回归中使用sigmod函数将输出限制在0-1，大于0.5为True，反之则为False。

根据实值或者概率预测结果，我们将测试样本按照可能性排序，分类过程相当于在这个序列中选取一个间断点来将样本分为不同的两个部分，前一部分为“正例”，后一部分为“反例”。

不同任务选取不同点，若重视P,则靠前，若重视R,则靠后。

因此排序的质量体现了“一般情况下”泛化性能的好坏，ROC曲线则是从这个角度出发研究学习器的泛化性能。

根据学习器对样例的排序，按此顺序逐个把样本作为正例预测，每次计算两个值绘制ROC曲线：

• 纵轴——“真正例率”(True Positive Rate, TPR)

• 横轴——“假正例率”(False positive Rate, FPR)

两者分别定义为：

对曲线的解释：

先解释两种特殊情形，即“对角线对应于‘随机猜测’模型，而点(0,1)则对应于将所有正例排在所有反例之前的‘理想模型’”。

看一下 ROC 绘图过程：

给定 $m^+$个正例和$m^-$个反例，根据学习器预测结果对样例进行排序，然后把分类阈值设为最大，即把所有样例均预测为反例，此时真正例率和假正例率均为 0（无样例被预测为正例，因此真正例 TP 和假正例 FP 均为 0，根据公式可知真正例率 TPR 和假正例率 FPR 均为 0，在坐标(0,0)处标记一个点，然后将分类阙值依次设为每个样例的预测值，依次将每个样例划分为正例，设前一个标记点坐标为(x,y)：

若当前为真正例,坐标为$(x,y+\frac{1}{m^+})$

若当前为假正例,坐标为$(x+\frac{1}{m^-},y)$

学习器比较时，若一个包住另一个，则可说前者优于后者，若有交叉，则比较AUC大小。

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

为了更好理解，我们将式子变形为：

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

这样可以看出$(x_{i+1}-x_i)$是矩阵的底,$\frac{(y_i+y_{i+1})}{2}$ 是矩阵的高.

排序“损失”(loss)定义为：

$$l_{rank} = \frac{1}{m^+m^-}\sum_{x^+ \in D^+}\sum_{x^- \in D^-}(Ⅱ(f(x^+)<f(x^-))+\frac{1}{2}Ⅱ(f(x^+)=f(x^-)))$$

且:

$AUC = 1-l_{rank}$

未完待续......