学习理论——从数据中能学到什么

父节点：math

计算学习理论与统计学习理论：泛化（generalization）的数学——有限多个样本，什么时候才能确定一条在未见过的数据上也成立的规则？

让这件事不平凡的陷阱。 对任何一份有限样本，都有无穷多条规则同样吻合——你总能拟合住见过的那些点，却在其余地方全错。所以学习本来是不可能的，除非你事先限制自己的假设空间（一种归纳偏置，inductive bias）。这个领域画出的，正是这样一条精确的边界：一个受限的假设类，究竟能学到什么、学不到什么。

设定（以下每篇笔记都使用这套符号）

对象

输入（inputs）存在于一个空间 X 中（点、邮件、图像）；每个输入都有一个真实的标签，记作 + 或 −。

目标（target）c 是那条未知的真实规则 c: X → {+,−}——也就是你要学习的东西。

输入来自一个未知分布 D；你的样本是从 D 中独立抽出的 m 个带标签样例 (x₁,y₁), …, (xₘ,yₘ)。

你事先固定一个假设类 H——也就是你愿意考虑的候选规则菜单（这正是你的偏置所在）：例如所有直线边界、所有轴对齐矩形、或所有深度不超过 5 的决策树。假设（hypothesis）h ∈ H 是这份菜单里的一条规则，一个函数 h: X → {+,−}（输入→预测标签）。学习 = 从菜单 H 中挑出最好的 h。

泛化误差 err(h) = 对一个从 D 中新抽出的 x，h(x) ≠ c(x) 的概率（即 h 在未见数据上与真相不符的频率）。

ε = 你要求的精度（err ≤ ε）；δ = 置信度（允许失败的概率）；m = 样本量。

目标： 仅凭样本，挑出一个 err(h) 很小的 h ∈ H——并且要能够保证这一点。

假设类

固定一个实例空间 $X$ 和二元标签集合 $Y = \{+,-\}$ 。假设是一个函数 $h : X \to Y$ 。假设类是函数空间的一个子集
$H \;\subseteq\; Y^X \;:=\; \{\, f \mid f : X \to Y \,\},$
所以 h ∈ H 就是普通的集合归属关系。等价地，把每个 $h$ 等同于集合 $h^{-1}(+) = \{\, x \in X : h(x) = + \,\}$ ，一个类就是一个子集族 $H \subseteq 2^X$ ；而这一对 $(X, H)$ ，正是 Vapnik–Chervonenkis 理论中的范围空间（range space）／集合系统（set system）。

这里的"类"（class）只是对那个集合／族的宽松称呼——不是集合论意义上的真类（proper class）。H 可以是无穷的（所有阈值、所有直线），但仍然是一个普通集合；有限的 VC dimension 会让它在有效意义上保持"小"（Sauer–Shelah：在 n 个点上只有 O(nᵈ) 种标注方式，而不是 2ⁿ 种）。

笔记

pac ——Valiant 的框架：以近似（误差 ≤ ε）、大概率（概率 ≥ 1−δ）的方式，从多项式数量的样本中完成学习。
vc-dimension ——假设类的容量；基本定理：PAC 可学 ⟺ VC 维有限。
no-free-lunch ——不存在万能学习器；学习必须依赖先验偏置——而这个偏置本身无法被学到。

唯一要记住的边界

可学 ⟺ 容量（VC）有限。 灵活性太少，拟合不了真相；灵活性太多，则无法泛化（它能拟合任何标注，包括噪声）。学习存在于两者之间，而你所需要的数据量，随你允许的容量增长。