简介
此章节介绍了对模型的评估方法，以及对两个或多个模型进行比较的方法。
概念
错误率（error rate）：如果在 m 个样本中有 a 个样本分类错误，则错误率为 E = a / m 。
精度（arrcuracy）：精度为 1 - a / m，即精度 = 1 - 错误率。
误差（error）：学习器的实际预测输出与样本的真实输出之间的差异称为误差。其中，学习器在训练集上的误差称为训练误差（training error）或经验误差（empirical error），在新样本上的误差称为泛化误差（generalization error），在训练集（testing set）上的误差被称为测试误差（testing error）。
过拟合（overfitting）：学习器将训练样本的性质学得“太好”，过于拟合训练样本而导致泛化性能下降，对于新的样本无法做出正确的判别。
欠拟合（underfitting）：学习器没有学好训练样本的一般性质，对样本的拟合程度较低。
参数调节（parameter tuning）：简称调参，即对算法的参数进行调节。一般对每个参数选定一个范围和变化步长，例如在 [0, 0.2] 范围内以 0.05 为步长，则实际要评估的候选参数值有 5 个，从这 5 个参数值中选取最佳的 1 个作为最终的结果。
验证集（validation set）：模型评估与选择中用于评估测试的数据集称为验证集。在研究对比不同算法的泛化性能时，我们用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集和验证集，基于验证集上的性能来进行模型选择和调参。
性能度量（performance measure）：性能度量是衡量模型泛化能力的评价标准。对比不同模型的能力时，不同的性能度量通常会返回不同的结果。
规范化（normalization）：将不同变化范围的值映射到相同的固定范围中，常见的是 [0, 1]，此时亦称归一化。
评估方法
留出法（hold-out）：
将数据集 D 划分为两个互斥的集合，其中一个集合作为训练集 S，另一个作为测试集 T，即 D = S ∪ T， S ∩ T = ∅ 。在 S 上训练出模型后，用 T来评估测试误差，作为对泛化误差的估计。
留出法通常采用分层采样（stratified sampling）对数据集进行划分，即在训练集 S 和测试集 T 中，正例和反例的数量应当相同。一般采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。
通常将 2/3 ~ 4/5 的数据划分为训练集，将剩下的数据划分为测试集。一般可以用 70% 作为训练集，30% 作为测试集。
交叉验证法（cross validation）：
将数据集 D 划分为 k 个大小相似的互斥子集，即 D = D1 ∪ D2 ∪ ... ∪ Dk，Di ∪ Dj = ∅ （i ≠ j）。每个子集 Di 尽可能保持数据分布的异质性，即从 D 中通过分层采样得到。每次用 k - 1 个子集的并集作为训练集，剩下的那个子集作为测试集，重复 k 次后得到 k 个测试结果，取 k 个测试结果的平均值为最终的评估结果。通常把交叉验证法称为k 折交叉验证（k-fold cross validation），其中 k 最常用的取值是 10，即 10 折交叉验证；其他常用的 k 值有 5、20等。
假设数据集 D 中包含 m 个样本，令 k = m，则得到了留一法（Leave-One-Out，简称 LOO）。
自助法（bootstrapping）：
给定包含 m 个样本的数据集 D，每次随机从 D 中挑选一个样本拷贝放入（D 中仍有 m 个样本）训练集 S，重复 m 次后训练集 S 中就有了 m 个样本，其中有一部分样本会在 S 中多次出现。样本在挑选过程中始终不被选择到的概率为
取极限得
即数据集 D 中约有 36.8% 的样本未出现在训练集 S 中。取 D \ D' 为测试集 T，则 T 中拥有约 1 / 3 的样本数据。这样的测试结果，亦称包外估计（out-of-bag estimate）。
自助法在数据集较小、难以有效划分训练/测试集时很有用。然而，自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差。
性能度量
均方误差（mean squared error）：
回归任务最常用的性能度量是均方误差
更一般的，对于数据分布 D 和概率密度函数 p(·) ，均方误差可以描述为
错误率（error rate）与精度（accuracy）：
对样例集 D，分类错误率的定义为
精度定义为
更一般的，对于数据分布 D 和概率密度函数 p(·) ，错误率可以描述为
精度描述为
查准率（precision）、查全率（recall）与 F1：
查准率表示在所有被认为是正确的样例中，有多少个被正确分类的样例；而查全率表示在所有本身即是正确的样例中，有多少个被正确分类的样例。
对于二分类问题，分类结果的混淆矩阵（confusion matrix）为
查准率 P 与查全率 R 分别定义为
我们根据学习器的预测结果对样例进行排序，排在前面的是学习器认为最可能是正例的样本，排在最后的是学习器认为最不可能是正例的样本。按此顺序逐个把样本作为正例进行预测，每次计算出相应的查全率、查准率，以查准率为 y 轴、查全率为 x 轴作图，则可以得到查准率-查全率曲线，简称 P-R 曲线。实际应用中的 P-R 曲线通常是非单调、不平滑的，且在很多局部有上下波动，如
平衡点（Break-Even Point，简称 BEP）是一个用于比较学习器的性能度量，它是查准率 = 查全率时的取值，如图中的 BEP 是 0.55。基于 BEP 值的高低可以比较出学习器的优劣。
但是 BEP 还是过于简化，更常用的是 F1 度量：
F1度量的一般形式——Fβ，能让我们表达出对查准率/查全率的不同偏好，它定义为
其中 β > 0度量了查全率对查准率的相对重要性。β = 1 时退化为标准的 F1；β > 1 时查全率更重要；β < 1 时查准率更重要。
当执行多分类任务或在多个数据集上进行训练/测试时，每两两类别的组合都对应一个混淆矩阵。对每个混淆矩阵都计算出相应的查准率和查全率，记为（P1, R1），(P2, R2），...，（Pn, Rn），再计算平均值，就得到了宏查准率（macro-P）、宏查全率（macro-R），以及相应的宏F1（macro-F1）：
还可以先将每个混淆矩阵的对应元素进行平均，得到TP、FP、TN、FN的平均值，再基于这些值计算出微查准率（micro-P）、微查全率（micro-R），以及相应的微F1（micro-F1）：
ROC 曲线（Receiver Operating Characteristic curve） 与 AUC（Area Under ROC Curve）：
ROC 曲线全称是受试者工作特征曲线，与 P-R 曲线相似，我们根据学习器的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测，每次计算出相应的真正例率（True Positive Rate，简称 TPR）、假正例率（False Positive Rate，简称 FPR），以TPR为 y 轴、FPR为 x 轴作图，则可以得到 ROC 曲线。
其中 TPR 与 FPR 的定义为
得到 ROC 图：
其中 AUC 表示 ROC 曲线下的面积，用于比较学习器的性能优劣，一般面积更大的学习器的性能更为优良。AUC 可估算为
形式化地看，AUC 考虑的是样本预测的排序质量，因此它与排序误差有紧密联系。给定 m+ 个正例和 m- 个反例，令 D+ 和 D- 分别表示正、反例集合，则排序损失（loss）定义为
因此有
代价敏感错误率与代价曲线
在现实任务中，常常有不同类型的错误会造成不同的损失的情况，即错误分类为正例造成的损失可能远远超过（或小于）错误分类为反例造成的损失，因此可为错误赋予非均等代价（unequal cost）。
例如二分类代价矩阵：
在矩阵中，若将第 0 类判别为第 1 类所造成的损失更大，则 cost01 > cost10；损失程度相差越大，cost01 与 cost10 的差值越大。
此时的代价敏感（cost-sensitive）错误率为
在非均等代价下，需要用代价曲线（cost curve）代替 ROC 曲线来反映出学习器的期望总体代价。代价曲线图的 x 轴是取值为 [0, 1] 的正例概率代价
其中 p 是样例为正例的概率；y 轴是取值为 [0, 1] 的归一化代价
ROC 曲线上每一点对应了代价平面上的一条线段，设 ROC 曲线上的点的坐标为（FPR，TPR），则先计算出 FNR = 1 - TPR，再在代价平面上绘制一条从（0，FPR）到（1，FNR）的线段，线段下的面积表示该条件下的期望总体代价，所有线段的下界围成的面积即为所有条件下学习器的期望总体代价，如
比较检验
统计假设检验（hypothesis test）
通常以统计假设检验方法来比较学习器性能。书中以错误率为性能度量，用 ϵ 表示，即有泛化错误率 ϵ 和 测试错误率 ϵ^，则泛化错误率为 ϵ 的学习器被测得测试错误率为 ϵ^ 的概率为
解方程
可知，在 ϵ = ϵ^ 时 P 最大，|ϵ - ϵ^| 增大时 P 减小。
二项检验（binomial test）
我们可使用二项检验来对 ϵ 进行假设检验，如检验 ϵ <= ϵ0（即泛化错误率是否不大于 ϵ0）：
其中 1 - α 反映了结论的置信度（confidence）。
t 检验（t-test）
当通过多次重复留出法或是交叉验证法等进行多次训练/测试，我们会得到多个测试错误率，此时可使用 t 检验。假定我们得到了 k 个测试错误率，则平均测试错误率 μ 和方差 σ^2 为
考虑到这 k 个测试错误率可看作泛化错误率 ϵ0 的独立采样，则变量
服从自由度为 k - 1 的 t 分布。
交叉验证 t 检验
对两个学习器 A 和 B，我们可以用成对 t 检验（paired t-tests）来进行比较检验。先对每对测试错误率求差，△ = ϵA - ϵB，若两个学习器性能相同，则差值的均值应该为 0 。因此，可根据差值△1，△2，...，△k 来对学习器 A 与 B 性能相同做 t 检验，若变量
小于临界值，则假设不能被拒绝，即认为两个学习器的性能没有显著差别。
5 x 2 交叉验证是做 5 次 2 折交叉验证之前随机将数据打乱。同样由上述检验方法可得
变量
服从自由度为 5 的 t 分布。
McNemar 检验
对二分类问题，可以获得两学习器分类结果的差别，如列联表（contingency table）：
若我们做的假设是两学习器性能相同，则应有 e01 = e10，那么变量 |e01 - e10| 应当服从正态分布。McNemar 检验考虑变量
服从自由度为 1 的卡方分布，即标准正态分布变量的平方。
Friedman 检验与 Nemenyi 后续检验
假定我们用 D1、D2、D3 和 D4 个数据集对算法 A、B、C 进行比较。首先，使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果，然后在每个数据集上根据测试性能由好到坏排序，并赋予序值 1，2， ...；并对每一列的序值求平均，得到平均序值，可得
然后，使用 Friedman 检验来判断这些算法是否性能都相同，若相同，则它们的平均序值应该相同。假定我们在 N 个数据集上比较 k 个算法，令 ri 表示第 i 个算法的平均序值，则 ri 的均值和方差分别为 (k + 1) / 2 和 (k^2 + 1) / 12。变量
在 k 和 N 都较大时，服从自由度为 k - 1 的卡方分布。
然而，上述这样的原始 Friedman 检验过于保守，现在通常使用变量
服从自由度为 k - 1 和 (k - 1)(N - 1) 的 F 分布。
若所有算法的性能相同这个假设被拒绝，则说明算法的性能显著不同。这是需进行后续检验（post-hoc test）来进一步区分各算法。常用的有 Nemenyi 后续检验。
Nemenyi 检验计算出平均序值差别的临界值域
若两个算法的平均序值之差超出了临界值域 CD，则以相应的置信度拒绝两个算法性能相同这一假设。
偏差（bias）与方差（variance）
以回归任务为例，学习算法的期望预测为
方差为
噪声为
偏差为
算法的期望泛化误差为
也就是说，泛化误差可分解为偏差、方差、噪声之和。
小结
在此章节学到了如何对学习器的性能进行评估、比较，为以后评估各种学习器的性能打好基础。各种的统计假设检验方法也凸显了现在机器学习中统计学的重要性，从侧面说明了现在是统计学习主导潮流。要研究这一块，相比牢固的概率论和统计学基础是必不可少的。当然，除此之外的各种数学基础也是必要的。
在写此小记的时候突然发现方差竟然是以 n - 1 作为分母，而不是 n。好像我以前一直没有注意到这个问题。随即去网上搜了下资料，顺便自己推了一下证明式，感觉写得还行，贴出来留作纪念
