CS229-4 Learning Theory

创建：2026/6/1 科研机器学习 CS229

学习理论研究训练误差与泛化误差的关系。有限假设类用 Hoeffding inequality + union bound 得到 uniform convergence；无限假设类用 VC dimension 衡量模型复杂度，分析泛化所需样本量。

1. Bias / Variance Tradeoff

Bias： 模型的系统性偏差
Variance： 模型对训练数据扰动的敏感程度

情况	训练误差	测试误差	问题
High Bias	高	高	模型太简单
High Variance	低	高	模型太复杂
合适	较低	较低	泛化较好

2. 训练误差与泛化误差

训练误差（Empirical Error）：

\hat{ε} (h) = \frac{1}{m} \sum_{i = 1}^{m} 1 {h (x^{(i)}) \neq y^{(i)}}

模型在训练集上犯错的比例。

泛化误差（Generalization Error / True Error）：

ε (h) = P_{(x, y) \sim D} (h (x) \neq y)

模型在真实分布上新样本犯错的概率。

3. Empirical Risk Minimization (ERM)

从假设类 $H$ 中选择训练误差最小的模型：

\hat{h} = \arg min_{h \in H} \hat{ε} (h)

其中 $H$ 叫 hypothesis class（候选模型集合）。

4. Uniform Convergence

我们希望对所有 $h \in H$ ，训练误差都接近真实误差：

| \hat{ε} (h) - ε (h) | \leq γ

如果这个性质对所有 $h$ 同时成立，就叫 uniform convergence——意味着每个模型的训练误差都是它真实误差的可靠估计。

为什么 uniform convergence 能保证 ERM 可靠？

设 $\hat{h} = \arg min_{h \in H} \hat{ε} (h)$ ， $h^{*} = \arg min_{h \in H} ε (h)$ 。若 uniform convergence 成立（ $| \hat{ε} (h) - ε (h) | \leq γ$ 对所有 $h$ 成立），则：

ε (\hat{h}) \leq \hat{ε} (\hat{h}) + γ \leq \hat{ε} (h^{*}) + γ \leq ε (h^{*}) + 2 γ

即 ERM 选出的模型，真实误差最多比候选类中最好的模型差 $2 γ$ 。（完整推导见附录 A）

5. 有限假设类

假设 $| H | = k$ ，有限个候选模型。

5.1 Hoeffding Inequality

对固定 $h$ ，每个样本的分类对错可视为 Bernoulli 随机变量 $Z_{i} = 1 {h (x^{(i)}) \neq y^{(i)}}$ ，则 $\hat{ε} (h) = \frac{1}{m} \sum_{i = 1}^{m} Z_{i}$ 是 $ε (h)$ 的估计。Hoeffding inequality 给出：

P (| \hat{ε} (h) - ε (h) | > γ) \leq 2 \exp (- 2 γ^{2} m)

含义： 对固定模型，训练误差偏离真实误差的概率随样本数指数级下降。

5.2 Union Bound → Uniform Convergence

用 union bound 扩展到整个 $H$ （推导见附录 B）：

P (\exists h \in H : | \hat{ε} (h) - ε (h) | > γ) \leq \sum_{h \in H} P (| \hat{ε} (h) - ε (h) | > γ) \leq 2 k \exp (- 2 γ^{2} m)

5.3 Sample Complexity

设失败概率不超过 $δ$ ，即 $2 k \exp (- 2 γ^{2} m) \leq δ$ ，解得：

m \geq \frac{1}{2 γ^{2}} \log \frac{2 | H |}{δ}

只要样本数满足此条件，就能以至少 $1 - δ$ 的概率保证 $\forall h \in H, | \hat{ε} (h) - ε (h) | \leq γ$ 。

想要误差更准（ $γ$ 小）→ 样本量 $1 / γ^{2}$ 级别增长
想要置信度更高（ $δ$ 小）→ 样本量 $\log (1 / δ)$ 级别增长
模型集合更大（ $| H |$ 大）→ 样本量 $\log | H |$ 级别增长

6. 无限假设类与 VC Dimension

当 $| H | = \infty$ 时，上述 $\log | H |$ 的 bound 失效，需要新的复杂度度量——VC Dimension。

6.1 Shattering

给定点集 $S = {x^{(1)}, x^{(2)}, \dots, x^{(d)}}$ ，如果对任意标签分配 $y^{(i)} \in {0, 1}$ ，都存在 $h \in H$ 能完美分类，则称 $H$ shatters $S$ 。

VC dimension $VC (H)$ 定义为 $H$ 能 shatter 的最大点集大小。

例子： 二维平面线性分类器 $h_{w, b} (x) = 1 {w^{T} x + b \geq 0}$ 的 VC dimension 为 $3$ 。更一般地， $n$ 维线性分类器的 VC dimension 为 $n + 1$ 。

6.2 泛化界

VC dimension 为 $d$ 的假设类，泛化界依赖 $d$ 而非 $| H |$ ，大致形式：

m = O (\frac{1}{γ^{2}} (d \log \frac{1}{γ} + \log \frac{1}{δ}))

核心结论：

有限 $H$ ： 复杂度由 $\log | H |$ 控制
无限 $H$ ： 复杂度由 VC dimension 控制

附录 A：ERM 界推导

第 4 节中 uniform convergence 保证 ERM 可靠的推导，分步展开如下。

设 $\hat{h}$ 为 ERM 选出的模型， $h^{*}$ 为 $H$ 中真实最优模型。若 $| \hat{ε} (h) - ε (h) | \leq γ$ 对所有 $h \in H$ 成立，则：

第一步 — 对 $\hat{h}$ 使用 uniform convergence：

ε (\hat{h}) \leq \hat{ε} (\hat{h}) + γ

第二步 — $\hat{h}$ 是训练误差最小的，所以其训练误差不超过 $h^{*}$ 的训练误差：

\hat{ε} (\hat{h}) \leq \hat{ε} (h^{*})

第三步 — 对 $h^{*}$ 使用 uniform convergence：

\hat{ε} (h^{*}) \leq ε (h^{*}) + γ

串联三步即得：

ε (\hat{h}) \leq ε (h^{*}) + 2 γ

附录 B：Union Bound 推导

第 5.2 节中将 Hoeffding bound 从单个假设扩展到整个 $H$ 的过程。

设 $H = {h_{1}, h_{2}, \dots, h_{k}}$ ，定义事件 $A_{i}$ 为"第 $i$ 个假设的训练误差偏离真实误差超过 $γ$ "：

A_{i} = {| \hat{ε} (h_{i}) - ε (h_{i}) | > γ}

那么" $H$ 中存在某个假设偏差超过 $γ$ "即所有 $A_{i}$ 的并集：

P (\exists h \in H : | \hat{ε} (h) - ε (h) | > γ) = P (A_{1} \cup A_{2} \cup \dots \cup A_{k})

由 union bound：

P (A_{1} \cup A_{2} \cup \dots \cup A_{k}) \leq \sum_{i = 1}^{k} P (A_{i})

代入每个 $A_{i}$ 的定义和 Hoeffding bound $P (A_{i}) \leq 2 \exp (- 2 γ^{2} m)$ ：

P (\exists h \in H : | \hat{ε} (h) - ε (h) | > γ) \leq \sum_{i = 1}^{k} 2 \exp (- 2 γ^{2} m) = 2 k \exp (- 2 γ^{2} m)

LOADING