第一章模型评估与选择

经验误差与过拟合

基本术语

精度： $m$ 个样品有 $a$ 个分类错误，错误率 $E = a / m$ ,精度等于 $1 - a / m$
训练误差：学习器在训练集上的误差
泛化误差：学习器在新样品上的误差
过拟合：把训练样本自身的一些特点当做了所有潜在样本都具有的一般性质，导致泛化能力下降
欠拟合：对训练样本的一般性质尚未学好。

模型评估中，理想的方法是根据泛化误差来选择模型，但是无法获得泛化误差，训练误差又由于过拟合现象的存在不适合作为标准。

为什么过拟合不可避免

机器学习通常是NP难的问题，甚至更难。有效的学习算法必然是在多项式时间内运行完成的，若可以彻底避免过拟合，那么通过经验误差最小化就可以获得最优解。这就意味着我们证明了“ $P \neq N P$ ”。

事实上，目前科学界普遍相信P≠NP，所以遇到NP-Complete的问题，就直接标注这是一道难题，使用近似解吧！这是一个不怎么乐观的看法，难道说我们真的无法把这样的难题给解决掉了吗？可能未必啦！仔细想想我们也许还有另外一个方法，只要我们创建一个NTM就可以把这些难题给解决掉啦！不过询问过专家，专家补充：连量子电脑也都普遍不被认为是一个NTM。

很好的一篇文章浅谈演算法复杂度分界：什么是P, NP, NP-Complete, NP-Hard问题
所以过拟合是无法避免的

评估方法

通过实验的方法来对学习器的泛化误差进行评估。使用一个“测试集”来测试学习器对新样本的判别能力，然后以测试集上的测试误差作为泛化误差的近似。

留出法

直接将数据集划分为两个互斥的集合，其中一个作为训练集 $S$ ，另一个作为测试集 $T$ ,即 $D = S ⋃ T, S ⋂ T = ϕ$

缺点：若令训练集 $S$ 包含绝大多数样本，则训练出来的模型可能更接近于用 $D$ 训练出来得模型，但是由于 $T$ 比较小，评估结果可能不够稳定准确；若令测试集 $T$ 多包含一些样本，则训练集 $S$ 与 $D$ 的差别更大了，被评估的模型与D训练出来的模型相比可能有较大差别，从而降低了评估结果的保真性。

交叉验证法

将数据集 $D$ 划分为 $k$ 个大小相同的互斥子集，即 $D = D_{1} ⋃ D_{2} ⋃ . . . ⋃ D_{k}, D_{i} ⋃ D_{j} ⋃ = ϕ (i \neq j)$ ,然后每次用 $k - 1$ 个子集的并集作为训练集，余下的那个子集作为测试集，这样就可以获得 $k$ 组训练、测试集，从而可进行 $k$ 次训练，最终返回的是这 $k$ 个测试结果的均值。
第一章模型评估与选择

自助法

给定包含 $m$ 个样本的数据集 $D$ ,我们对它进行采样产生的数据集 $D^{‘}$ :每次随机从 $D$ 中挑选一个样本，将其拷贝放入 $D^{‘}$ ，然后将该样本放回初始数据集 $D$ 中，使得该样本在下次采样时仍有可能被采到，重复 $m$ 次，得到了包含 $m$ 个样本的数据集 $D^{‘}$ ,样本在 $m$ 次采样中始终不被采到的概率为 $(1 - 1 / m)^{m}$ ，取极限得到：

l i m_{n \to + \infty} (1 - 1 / m)^{m} = 1 / e = 0.368

即通过自助采样，初始数据集 $D$ 中约有 $36.8 %$ 的样本未出现在采样数据集 $D^{‘}$ 中，于是我们可以将 $D^{‘}$ 作为训练集， $D \D^{‘}$ 作为测试集，这样，实际评估的模型与期望评估的模型都使用 $m$ 个训练样本，而我们仍有数据总量的 $1 / 3$ ,没有在训练集中出现的样本用于测试。

调参与最终模型

大多数学习算法都有些参数需要设定，参数配置不同，学得模型的性能往往有显著的差别。因此，在进行模型评估与选择时，除了需要对适用学习算法进行选择，还需要对算法参数进行设定，这就是通常所说的“参数调节”。

性能度量

评估方法是评估泛化能力的实验估计方法,而性能度量则是泛化能力的度量标准。最常用的性能度量标准是均方误差：

E (f; D) = \frac{1}{m} \sum_{i = 1}^{m} (f (x_{i}) - y_{i})^{2} （ 离 散 ）

E (f; D) = \int_{x \sim D} (f (x_{i}) - y_{i})^{2} （ 连 续 ）

其中 $D = (x_{1}, y_{1}), (x_{2}, y_{2}), . . ., x_{m}, y_{m}$ , $y_{i}$ 表示实例 $x_{i}$ 的真实标记， $f$ 表示需要评估的学习器， $f (x)$ 表示预测值，y表示预测值。

错误率与精度

分类错误率：

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

精度定义为：

a c c (f; D) = \frac{1}{m} \sum_{i = 1}^{m} I (f (x_{i}) = y_{i}) = 1 - E (f; D)

更一般的，对于数据分布 $D$ 和概率密度 $P (.)$ :

E (f; D) = \int_{x \sim D} I (f (x_{i}) \neq y_{i}) p (x) d x

a c c (f; D) = \int_{x \sim D} I (f (x_{i}) = y_{i}) = 1 - E (f; D)

查全率与查准率

正确肯定（True Positive,TP）：预测为真，实际为真
正确否定（True Negative,TN）：预测为假，实际为假
错误肯定（False Positive,FP）：预测为真，实际为假
错误否定（False Negative,FN）：预测为假，实际为真
查准率：在所有预测为真的样例中，预测成功的概率（越高越好）
$P = \frac{T P}{T P + T N}$
查全率：在所有实际为真的样例中，被成功预测的概率(越高越好)
$R = \frac{T P}{T P + F N}$
$F 1$ :
$F 1 = \frac{2 * P * R}{P + R} = \frac{2 * T P}{样例总数 + T P - T N}$
$F_{β}$

F_{β} = \frac{(1 + β^{2}) * P * R}{β^{2} * P + R}

其中 $β > 0$ ,衡量了查全率对查准率的相对重要性，当 $β = 1$ 时， $F_{β}$ 退化为 $F_{1}$ ,此时查全率与查准率同等重要，当 $β > 1$ 时，查全率有更大的影响，当 $β < 1$ 时，查准率有更大的影响。

ROC与AUC

参考python 绘制ROC曲线

比较检验

假设检验

偏差与方差

偏差-方差分解

$x$ :测试样本
$y_{D}$ : $x$ 在数据集中的标记
$f (x; D)$ :训练集 $D$ 上学的模型 $f$ 在 $x$ 上的预测值

学习算法的期望预测为：

\bar{f} (x) = E_{D} [f (x; D)]

使用样本数相同的不同训练集产生的方差：

v a r (x) = E_{D} [(f (x; D) - \bar{f} (x))^{2}]

噪声：

ϵ^{2} = E_{D} [(y_{D} - y)^{2}]

偏差：真实值与预测值之间的差别：

b i a s^{2} (x) = (\bar{f} (x) - y)^{2}

期望泛化误差：

E (f; D) = E_{D} [(f (x; D) - y_{D})^{2}] = E_{D} [(f (x; D) - \bar{f} (x) + \bar{f} (x) - y_{D})^{2}] = E_{D} [(f (x; D) - \bar{f} (x))^{2}] + E_{D} [(\bar{f} (x) - y_{D})^{2}] + E_{D} [2 (f (x; D) - \bar{f} (x)) (\bar{f} (x) - y_{D})]

假设噪音的期望为0，即：

E_{D} [(y_{D} - y)^{2}] = 0

则：

E (f; D) = E_{D} [(f (x; D) - \bar{f} (x))^{2}] + E_{D} [(\bar{f} (x) - y_{D})^{2}] = E_{D} [(f (x; D) - \bar{f} (x))^{2}] + E_{D} [(\bar{f} (x) - y + y - y_{D})^{2}] = E_{D} [(f (x; D) - \bar{f} (x))^{2}] + E_{D} [(\bar{f} (x) - y)^{2}] + E_{D} [(\bar{y} - y_{D})^{2}] + 2 E_{D} [(\bar{f} (x) - y) (y - y_{D})]

E (f; D) = b i a s^{2} (x) + v a r (x) + ϵ^{2}

即泛化误差可以分解为偏差，方差与噪音之和，偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本省的拟合能力；方差度量了同样大小的训练集的变动所导致的学习性能的变化，即可花了数据扰动所造成的影响；噪音则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画额学习问题本省的难度。偏差-方差分解说明，泛化性能是由学习算法的能力，数据的充分性以及学习任务本省的难度决定的。
第一章模型评估与选择

泛化误差与偏差，方差的关系图说明偏差与方差是由冲突的，当训练不足的时候，学习器的拟合能力不够强，数据的扰动不足以使学习器产生显著变化，吃屎偏差主导了泛化错误率；随着训练强度的加深，学习器的拟合能力逐渐增强，训练数据的发生的扰动逐渐被学习器学到，方差逐渐主导了泛化错误率，在训练程度充足之后，学习器的拟合能力已非常强，训练数据发生的轻微扰动都回到主学习器发生显著变化。若训练数据自身的，非全局的特性被学习器学到，则将发生过拟合。

第一章 模型评估与选择