计算学习理论

误差

给定样例集 D，y ∈{-1, +1}，样本是独立同分布采样。
泛化误差为

经验误差为

h为输入空间到输出空间的一个映射。

我们需要解决的问题有两个：

给定一个训练集 D，我们希望基于机器学习算法f学得的模型所对应的假设 h 尽可能的接近目标概念 c，这就是“概率”“近似正确”的含义。形式化的说，令 δ 表示置信度，可定义

PAC辨识（PAC Identify）：

其中，0 < ϵ，δ < 1。

即，学习算法f能以较大的概率（至少 1 - δ）学得目标概念 c 的近似（误差最多为 ϵ）。如果模型在短时间内利用少量的(多项式级别)样本就能学得目标概念 c 的近似，则称概念类 c 对假设空间 H 而言是 PAC可学习 的。

引入一个引理

该引理表明，样例数量 m 越大，|Eout(h)−Ein(h)|≤ϵ发生的可能性就越大。
根据该引理，可以得到要如下定理

从上式中，我们可以得到，样例数一定的情况下，模型越复杂（假设空间的假设数越多），|Eout(h)−Ein(h)|≤ϵ发生的可能性就越小。

综合上述，我们得到一个关于假设空间大小|H|的矛盾：样例数m一定的情况下，如果|H|很大，模型就足够复杂，就可以更好的拟合样例，但是会使泛化误差和经验误差的差距很大；如果|H|很小，可以使泛化误差和经验误差很接近，但是模型非常简单，经验（泛化）误差都比较大。

在现实中，学习任务面临的通常是无限的假设空间，例如实数域中的所有区间，这就使上式中的|H|失去了一定的意义（因为假设空间都很大），因此我们需要引入一个相对于上式更"紧"的条件。我们先引入增长函数。

增长函数

表示假设空间 H 对 m 个样例所能赋予标记的最大可能结果数。

我们得到了一个更紧的上界

这个不等式也从侧面揭示了为什么 CNN 等精度很高的算法需要非常大量的训练集，而线性回归等算法只需很少的训练集就能收敛。

介绍两个重要的概念：

对分（dichotomy）：对二分类问题来说，H 中的假设对 D 中示例赋予标记的没每种可能结果成为对 D 的一种“对分”。
打散（shattered）：若假设空间 H 能实现示例集 D 上的所有对分，即 Π_H (m)=2^m，则称示例集 D 能被假设空间 H “打散”。