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

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

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

机器学习面临的问题通常是NP难甚至更难，而有效的学习算法必然使能够在多项式时间内运行完成，如果可以彻底避免过拟合，则我们通过经验误差最小化就能获得最优，这就意味着我们构造性地证明了“P=NP”，所以只要相信P$\ne$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^{m}_{i=1}(f(x_i)\ne y_i)$

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

准确，召回和F1

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

$F1=\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)，我们将样本集中的样例按从大到小排列(最可能到最不可能)。并按改顺序划分成若干子集，计算每个子集的真正例率$TPR=\frac{TP}{TP+FN}$和假正例率$FPR=\frac{FP}{TN+FP}$ 然后我们以TPR为横轴，FPR为纵轴，画出来的曲线就叫做ROC曲线，ROC曲线下的面积就叫做AUC(Area Under ROC Curve)

其他

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

比较检验

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

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

假设检验

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

$P(\hat{\epsilon};\epsilon) = \begin{pmatrix}m \\\\ \hat{\epsilon}\times m \end{pmatrix} \epsilon^{\hat{\epsilon}\times m}(1-\epsilon)^{m-\hat{\epsilon}\times m}$

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

$\bar{\epsilon}=max\epsilon\qquad s.t. \sum^{m}_{i=\epsilon_0\times m+1}\begin{pmatrix}m \\\\ i\end{pmatrix} \epsilon^{i}(1-\epsilon)^{m-i} <\alpha$

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

$\tau_t=\frac{\sqrt{k}(\mu-\epsilon_0)}{\epsilon}$

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

McNemar检验

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

$\tau\_{\chi^2}=\frac{(|e\_{01}-e\_{10}|-1)^2}{e\_{01}+e\_{10}}$

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

多算法比较

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

偏差和方差(bias variance)

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

$\begin{eqnarray} E(f;D)&=&\mathbb{E}\_D[(f(x;D)-y_D)^2] \\\\ &=& \mathbb{E}\_D[(f(x;D)-\bar{f}(x))^2] + (\bar{f}(x)-y)^2 +\mathbb{E}\_D[(y_D-y)^2] \\\\ &=&bias^2(x) + var(x) +\varepsilon^2 \end{eqnarray}$

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