西瓜书学习笔记

开始学习时间：2020/1/30

作者：谭楷城

第二章：模型评估与选择

2.1 经验误差与过拟合

错误率(error rate)：分类错误的样本数占样本总数的比例。
精度(accuracy)：精度 = 1 - 错误率（常常以百分比的形式书写）
误差(error)：实际预测输出与样本的真实输出之间的差异。
训练误差(training error)/经验误差(empirical error)：学习器在训练集上的误差。
泛化误差(generalization error)：新样本上的误差。

我们实际希望得到的是从新样本上能表现得很好的学习器，即泛化误差小。为了达到这个目的，应该从训练样本中尽可能学出适用于所有潜在样本的“普遍规律”。

学习器把训练样本学得太好了的时候，很可能已经把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质。称之为“过拟合”(overfitting)。相对地，还没有学好训练样本中的一般性质称为“欠拟合”(underfitting)。

简述之，过拟合就是“过配”，欠拟合就是“欠配”。

过拟合的必然存在性

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

在计算机领域，一般可以将问题分为可解问题和不可解问题。不可解问题也可以分为两类：一类如停机问题，的确无解；另一类虽然有解，但时间复杂度很高。可解问题也分为多项式问题(Polynomial Problem，P问题)和非确定性多项式问题(NondeterministicPolynomial Problem，NP问题)

P类问题：可以找到一个多项式时间复杂度的算法去解决的问题；

NP类问题：可以在多项式时间复杂度的算法去验证结果正确性的问题；比如随便拿一个结果，可在多项式时间内验证该结果是否正确，但是想要求解该结果的时间复杂度就不知道了。P类问题一定是NP类问题，但是NP类问题不一定能找到多项式时间复杂度的算法来解决（要是找到了就是P问题了）。所以人们关心的是：是否所有的NP问题都是P问题，即是否有 P=NP（信息学的巅峰问题）

P $\in$ NP

2.2 评估方法

通过实验测试来对学习器的泛化误差进行评估并进而做出选择。为此，需要使用一个"测试集"(testing set)来测试学习器对新样本的判别能力，然后以测试集上的测试误差(testing error)来作为泛化误差的近似。

如何产生测试集？

现在有包含m个样例的数据集 $D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_m,y_m)\}$ ，既要训练，又要测试，如何做到？

答案：对 $D$ 进行适当的处理，从中产生出训练集 $S$ 和测试集 $T$ 。

2.2.1 留出法(hold-out）

将数据集 $D$ 划分成两个互斥的集合。( $D = S\cup T$ ， $S\cap T=\varnothing$ )

在训练集 $S$ 训练得到模型后用 $T$ 评估其测试误差。

在划分训练集与测试集的时候要尽可能保持数据分布的一致性。

如分类任务中至少要保持样本的类别比例相似。

若是从采样(sampling)的角度来看待数据集划分，保留类别比例的采样方式通常称为分层采样(stratified sampling)。例如：

对 $D$ 进行分层采样，获得70%样本的训练集 $S$ 和30%样本的测试集 $T$ 。

保持样本分布的一致性，若样本集 $D$ 包含500个正例和500个反例，则分层采样得到的 $S$ 应该包含350个正例，350个反例，而 $T$ 包含150个正例和150个反例。

对于分层采样选取比例，如果测试集 $T$ 比较小，评估结果可能不够稳定准确。若 $T$ 多包含一些样本，训练集 $S$ 与 $D$ 的差别更大了，降低了评估结果的保真性(fidelity)。这个问题没有完美的解决方案，常见做法是将大约2/3~4/5的样本用来训练，剩余的样本用于测试。

当然，分割的方式有许多种。为了减少分割方式带来的差异，一般要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。例如上面例子中，就可以进行100次随机划分，每次产生一个训练/测试集用于实验评估，100次后就得到100个结果，而留出法返回的则是这100个结果的平均。同时也可以也可以得到估计结果的标准差。

2.2.2 交叉验证法(cross validation)

先将数据集 $D$ 划分为 $k$ 个大小相似的互斥子集并尽可能保持数据分布的一致性（分层采样）。然后每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集。这样就获得了 $k$ 组的训练集和测试集，然后就进行 $k$ 次训练。

返回的是 $k$ 个测试结果的均值。交叉验证法评估结果的稳定性和保真性很大程度上取决于 $k$ 的取值。

通常也把交叉验证法称为 $k$ 折交叉验证(k-fold cross validation)。西瓜书学习笔记第二章

常用的 $k$ 的取值是10，此外还有5，20等。

当然，交叉验证法同样存在多种划分方式。为了减小因为样本划分不同而引入的差别，k折交叉验证也要随机使用不同的划分重复p次。常见的有 $p=10$ ，即10次10折交叉验证。

特殊地，当 $k=m$ 折数等于样本个数（即每个样本作为一折）就得到了交叉验证法的一个特例留一法(Leave-One-Out,简称LOO)。留一法不受随机样本划分方式的影响。

优点是被实际评估的模型与期望评估用D训练出的模型很相似，评估结果往往被认为比较准确。
缺点是在数据集比较大时计算开销大。
NFL定理说明，得到的模型不一定比其他模型好。
- 留出法和交叉验证法由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比 $D$ 小。这必然会引入一些因训练样本规模不同而导致的估计偏差。

2.2.3 自助法(bootstrapping)

以自助采样法为基础，由数据集 $D$ 采样得到 $D'$ ：

每次随机从 $D$ 中挑选一个样本，将其拷贝放入 $D'$ ，然后再将该样本放回到初始数据集 $D$ 中，使得该样本在下次采样时仍有可能被采到。
这个过程重复执行样本个数 $m$ 次，就得到了包含 $m$ 个样本的数据集 $D'$ 。
$(1-\cfrac{1}{m})^m=\cfrac{1}{e}\approx0.368$ 为m次采集中始终不被采到的概率，也就是36.8%的样本未出现在 $D'$ 中。
$D'$ 作为训练集, $D/D'$ 用作测试集。（/表示集合减法）；实际评估模型与期望评估模型都使用的是m个训练样本。
因为有1/3数据总量的数据没有在训练集中出现，这样的测试结果也成为包外估计(out-of-bag estimate)。

优缺点

自助法在数据集比较小，难以有效划分训练/测试集的时候很有用。
能够从初始数据集中产生多个不同的数据集。对集成学习等方法有很大好处。

自助法产生的数据集改变了初始数据集的分布，引入了估计偏差。
初始数据足够的情况下，留出法和交叉验证法更常用一些。

西瓜书学习笔记第二章