【西瓜书】第二章模型的评估和选择

本文是周志华老师《机器学习》第二章模型的评估和选择的学习笔记及部分习题答案。　　
回顾一下模型评估和选择的内容，西瓜书中有些内容也是之前没有看过的，这部分内容记下来备忘。

首先是机器学习的老对头过拟合，对于我们能否彻底避免过拟合 :

机器学习面临的问题通常是NP难甚至更难，而有效的学习算法必然使能够在多项式时间内运行完成，如果可以彻底避免过拟合，则我们通过经验误差最小化就能获得最优，这就意味着我们构造性地证明了“P=NP”，所以只要相信P $\neq$ NP，过拟合就不可避免。
这点倒是我之前没有想过的。

评估方法
为了保证评估时能较好体现模型的泛化能力，我们评估模型时的测试集和训练集应该尽量互斥。
为此我们通常有以下方法来划分训练/测试集：

留出法直接将数据集D划分为两个互斥的集合，其中一个作为训练集，另一个作为测试集，在训练集上训练出模型后，用测试集评估其测试误差。

交叉验证法 (Cross Validation) 将数据集划分为k个大小相似的互斥子集，每次用k-1个子集的并集作为训练集，剩下的1个子集作为测试集。这样可以获得k组训练/测试集，最终返回k个测试结果的均值。CV法的稳定性和保真性在很大程度上取决于k的取值。

自助法 (Bootstraping) 这种方法以自助采样法为基础。给定包含m个样本的训练集D，我们对它进行采样产生数据集D’，每次从D中随机挑选一个样本，拷贝放入D’，使得下次采样时仍可能被采到；重复m次，我们就得到了包含m个样本的数据集D’。该方法在数据集较小，难以有效划分训练/测试集时有用。
这里需要注意，前两种方法都要尽量保证训练集和测试集的数据分布尽量一致。

性能度量

划分好数据集后，我们需要一项指标来反映模型“好”还是“坏”，这里我们就需要性能度量。

错误率和精度

分类任务最常用的性能度量就是错误率和精度。
错误率反映的是分类错误的样本数占样本总数的比例。

E (f; D) = \frac{1}{m} \sum_{i = 1}^{m} (f (x_{i}) \neq y_{i})

而精度则定义为 $a c c (f; D) = 1 - E (f; D)$

准确，召回和F1

对于二分类问题，我们定义四种情况TP,FP,TN,FN，分别对应真正例，假正例，真反例和假反例。
准确 $P = \frac{T P}{T P + F P}$
召回 $R = \frac{T P}{T P + F N}$
准确和召回通常来说是一对矛盾的度量，准确更注重宁可放过坏人，不能冤枉好人，召回则是宁可错杀三千，不能放过一个。
正是召回和准确有所矛盾，所以人们希望能够找到一个同时反应二者的指标。
首先“平衡点”(BEP)就是这样一个度量，它是“召回=准确”时的取值。
还有一个很常见的度量是F1值。

F 1 = \frac{2 \times P \times R}{P + R}

其实F1就是召回和准确的调和平均。
当我们有多个二分类混淆矩阵时，如果我们分别计算出P/R然后计算平均，那么就得到宏准确，宏召回，宏F1。（macro-P/macro-R/macro-F1）。如果是先计算出平均TP/平均FP等再计算出的度量就是微准确，微召回，微F1(micro-P/micro-R/micro-F1)。

ROC&AUC

ROC全称是受试者工作特征(Receiver Operating Characteristic)，我们将样本集中的样例按从大到小排列(最可能到最不可能)。并按改顺序划分成若干子集，计算每个子集的真正例率 $T P R = \frac{T P}{T P + F N}$ 和假正例率 $F P R = \frac{F P}{T N + F P}$ 然后我们以TPR为横轴，FPR为纵轴，画出来的曲线就叫做ROC曲线，ROC曲线下的面积就叫做AUC(Area Under ROC Curve)

其他

其他指标还有可以权衡不同错误类型的代价敏感错误率，期望总体代价等等。

比较检验

有了评估方法和性能度量的单位后，我们如何比较学习器性能呢？是不是可以直接比较数值的大小呢?
当然不行，主要原因如下：

我们希望得到的是泛化性能而不仅仅是测试集性能
测试集的大小/组成不同会有很大的性能差异
机器学习算法本身的随机性

假设检验

那么人们就提出用假设检验来比较这些性能，这里我们用错误率 $ϵ$ 表示性能度量。
对于一个错误率为 $ϵ$ 的学习器，我们在测试集上得到测试错误率为 $\hat{ϵ}$ ，这就意味着在 $m$ 个样本中，有 $\hat{ϵ} \times m$ 个被分类错误，我们容易推出，一个泛化错误率为 $ϵ$ 的学习器在一个 $m$ 样本的测试集上，得到测试错误率 $\hat{ϵ}$ 的概率为：

P (\hat{ϵ}; ϵ) = (\begin{matrix} m \\ \hat{ϵ} \times m \end{matrix}) ϵ^{\hat{ϵ} \times m} (1 - ϵ)^{m - \hat{ϵ} \times m}

这就符合二项分布，在此基础上我们可以使用二项检验来进行假设检验，这里的假设形如” $ϵ \leq ϵ_{0}$ ”，那么在 $1 - α$ 的概率内我们能观测到的最大错误率为：

\bar{ϵ} = m a x ϵ s . t . \sum_{i = ϵ_{0} \times m + 1}^{m} (\begin{matrix} m \\ i \end{matrix}) ϵ^{i} (1 - ϵ)^{m - i} < α

也就是说，如果我们的测试错误率 $\hat{ϵ}$ 小于临界值 $\bar{ϵ}$ 那么我们就在 $1 - α$ 的置信度下接受该假设，否则我们就以 $α$ 的显著度下认为学习器的泛化错误率大于 $ϵ$ 。
有时我们进行多次留出法或者使用CV法，那么就能获得 $k$ 个测试错误率，这时我们可以用他们计算出平均错误率 $μ$ 和方差 $σ^{2}$ 。在此基础上我们也可以使用 $t$ 检验来进行假设检验，这时的假设就是 $μ = ϵ$ 。变量

τ_{t} = \frac{\sqrt{k} (μ - ϵ_{0})}{ϵ}

服从自由度为 $k - 1$ 的t分布。

McNemar检验

对于二分类问题，给定两个学习器A/B，我们可以获得二者学习器分类结果的差别，即二者都正确，都错误，一个正确另一个错误。那么对于假设“两个学习器性能相同” ，就应该有 $e_{01} = e_{10}$ ，那么变量 $| e_{01} - e_{10} |$ 服从正态分布，则变量

τ_χ^{2} = \frac{(| e_01 - e_10 | - 1)^{2}}{e_01 + e_10}

服从自由度为1的 $χ^{2}$ 分布，即标准正态分布的平方。给定显著度 $α$ ，当该变量小于临界值 $χ_{α}^{2}$ 时接受假设，认为两个学习器性能没有显著差别，否则拒绝假设，并认为平均错误率较小的那个学习器性能较优。

多算法比较

前述方法都是对单个算法进行检验或者两个算法比较，当我们对于一份数据集有多个算法时，当然也可以用之前的方法两两比较，但是更直接的我们那可以用基于算法排序的Friedman 检验，若检验后发现“所有算法性能相同”这个假设被拒绝，这时我们可以再用Nemenyi后续检验 来进一步区分各个算法。
这部分内容在西瓜书的p42(ch2.4.4)有所体现。

偏差和方差(bias variance)

除了估计泛化性能外，我们还希望了解为什么有这样的性能，这时可以使用“偏差-方差分解”，以回归任务为例。（分类任务由于损失函数具有跳变性，很难在理论上推导出偏差-方差分解）。 $y_{D}$ 为x在数据集的标记， $y$ 为x的真实标记(噪声的存在使得数据集的数据可能不完全正确), $f (x; D)$ 表示训练集D上学的模型 $f$ 在x上的预测输出。
那么期望预测为 $\bar{f} (x) = E_{D} [f (x; D)]$
我们使用样本数不同的训练集可以产生出方差 $v a r (x)$ 。这时我们将算法的期望泛化误差进行分解：

\begin{array}{rcl} (1) & E (f; D) & = & E_D [(f (x; D) - y_{D})^{2}] \\ (2) \\ (3) & = & E_D [(f (x; D) - \bar{f} (x))^{2}] + (\bar{f} (x) - y)^{2} + E_D [(y_{D} - y)^{2}] \\ (4) \\ (5) & = & b i a s^{2} (x) + v a r (x) + ε^{2} \end{array}

这样，泛化误差就在理论上被优美地分解为偏差，方差和噪声之和。
回顾三者的意义：

偏差刻画了预测结果和真实结果的偏离程度，刻画了学习算法本身的拟合能力。
方差度量了训练集变动造成的学习性能的变化，即学习器的稳定性。
噪声则表达了在当前任务上期望泛化误差的下界，即学习问题本身的难度。

偏差-方差和过拟合欠拟合的关系，之前coursera的ML笔记上也有提到过。