📚 计算学习理论笔记
计算学习理论研究“机器学习算法在什么条件下能学好”，即：样本复杂度、泛化误差上界、可学习性的数学基础。核心工具：PAC学习、VC维、Rademacher复杂度、稳定性。
🎯 一、PAC 学习（Probably Approximately Correct）
PAC 学习 = “大概率近似正确”学习 —— 可学习性的标准定义。
✅ 1. PAC 可学习定义
| 项目 | 描述 |
|---|---|
| 输入 | 概念类$\mathcal{C}$、假设空间 $\mathcal{H}$、数据分布 $\mathcal{D}$、误差参数 $\epsilon > 0$、置信参数 $\delta > 0$ |
| 要求 | 存在算法$\mathcal{A}$ 和多项式函数 $poly(1/\epsilon, 1/\delta, n, size(c))$ |
| 条件 | 当样本数$m \geq poly(\cdot)$ 时，算法输出 $h \in \mathcal{H}$ 满足： |
|
| 符号 | $R(h) = P_{\mathbf{x} \sim \mathcal{D}} [h(\mathbf{x}) \neq c(\mathbf{x})]$：泛化误差 |
📌 通俗解释：给足够样本，就能高概率学出低误差模型。
✅ 2. 有限假设空间的样本复杂度
（1）可分情形（存在 $h$ 使训练误差=0）
| 项目 | 公式/描述 |
|---|---|
| 样本复杂度 | $$ m \geq \frac{1}{\epsilon} \left( \ln |
| 泛化保证 |
|
| 关键点 | 假设空间越大（$\ln |
（2）不可分情形（无完美 $h$）
| 项目 | 公式/描述 |
|---|---|
| 样本复杂度 | $$ m \geq \frac{2}{\epsilon^2} \left( \ln |
| 泛化保证 |
|
| 关键点 | 误差界是“相对最优假设的差距”，样本需求更高（$1/\epsilon^2$） |
🧠 二、VC 维（Vapnik-Chervonenkis Dimension）
VC 维 = 衡量假设空间 $\mathcal{H}$ 复杂度的指标 → 决定泛化能力。
✅ 1. 核心定义
| 概念 | 定义 |
|---|---|
| 打散（Shatter） | $\mathcal{H}$ 能实现样本集 $D$（大小 $d$）的所有 $2^d$ 种标记组合 |
| VC 维 |
|
📌 例子：二维线性分类器 VC 维 = 3（能打散任意 3 个不共线点，不能打散 4 个点）
✅ 2. 泛化误差界（基于 VC 维）
| 项目 | 公式/描述 |
|---|---|
| 增长函数上界 |
|
| 泛化误差界 |
|| 关键结论 | VC 维$d$ 越大 → 泛化误差上界越大 → 越容易过拟合 |
✅ 3. 常见模型 VC 维
| 模型 | VC 维 | 说明 |
|---|---|---|
| d 维线性分类器 | $d + 1$ | 如感知机、SVM（线性核） |
| 实轴区间分类器 | 2 | 能打散任意 2 点 |
| 平面凸多边形分类器 | 无限 | 可打散任意多点 |
| 决策树（有限叶节点） | 有限 | 与叶节点数相关 |
| 神经网络 | 高（与参数相关） | 通常很大，需正则化 |
🌊 三、Rademacher 复杂度
Rademacher 复杂度 = 衡量 $\mathcal{H}$ 拟合随机噪声的能力 → 越小泛化越好。
✅ 1. 定义
| 类型 | 公式 |
|---|---|
| 经验 Rademacher 复杂度 |
|
| Rademacher 复杂度 |
|| 符号说明 | $\sigma_i$：独立 Rademacher 变量（±1，概率各 0.5） |
📌 直观：复杂模型能拟合噪声 → $\hat{\mathfrak{R}}_S$ 大 → 易过拟合
✅ 2. 泛化误差界
| 情形 | 公式 |
|---|---|
| 基于$\mathfrak{R}_m$ |
|| 基于$\hat{\mathfrak{R}}_S$ |
|
📌 优势：比 VC 维更紧致，适用于实值函数（如回归、SVM）
🧭 四、稳定性（Stability）
稳定性 = 算法对单样本扰动的鲁棒性 → 越稳定，泛化越好。
✅ 1. $\beta$-稳定定义
| 项目 | 描述 |
|---|---|
| 训练集 | $S = \{\mathbf{x}_1, …, \mathbf{x}_m\}$，$S^{(i)}$ = 替换第 $i$ 个样本后的集合 |
| 输出假设 | $h_S$ = 算法在 $S$ 上输出，$h_{S^{(i)}}$ = 在 $S^{(i)}$ 上输出 |
| $\beta$-稳定 | $$ \forall \mathbf{x}, \quad |
📌 例子：正则化模型（岭回归、SVM）通常是稳定的
✅ 2. 稳定性与泛化误差
| 项目 | 公式/描述 |
|---|---|
| 期望泛化误差 | $$ |
| 关键结论 | $\beta$ 越小 → 算法越稳定 → 泛化误差越小 |
| 优势 | 适用于任意算法，解释正则化为何有效 |
📊 五、四大理论工具对比表
| 工具 | 核心思想 | 适用范围 | 是否依赖数据分布 | 是否紧致界 | 典型应用场景 |
|---|---|---|---|---|---|
| PAC 学习 | 样本复杂度保证 | 有限假设空间 | ❌ | ✅（可分） | 估算所需样本量 |
| VC 维 | 假设空间复杂度 | 二分类 | ❌ | ⚠️（较松） | 模型选择、理论分析 |
| Rademacher 复杂度 | 拟合噪声能力 | 实值函数 | ✅ | ✅ | 回归、SVM、深度学习 |
| 稳定性 | 算法对样本扰动的鲁棒性 | 任意算法 | ✅ | ✅ | 正则化设计、算法分析 |
📌 选择建议：
- 理论证明 → VC 维、Rademacher
- 算法设计 → 稳定性（加正则化、早停）
- 样本量估算 → PAC 学习
- 实践调参 → 用验证集，但理论指导方向
✅ 六、一句话终极总结
PAC 学习 = “多少样本够用？”
VC 维 = “模型有多复杂？”
Rademacher = “模型多爱拟合噪声？”
稳定性 = “换一个样本，结果变多少？”
—— 四大工具，共同回答“为什么机器学习能泛化”
📌 七、复习重点提示
| 概念 | 必背公式/结论 |
|---|---|
| PAC 可分情形 | $$ m \geq \frac{1}{\epsilon} \left( \ln |
| VC 维定义 | 能打散的最大样本数 |
| VC 泛化界 |
|
| Rademacher 泛化界 |
|
| 稳定性结论 |
|
