机器学习数学基础 120 章

PAC 可学习性与样本复杂度

层级：C｜建议先修：05-21、08-11

PAC 是 Probably Approximately Correct 的缩写：学习算法以很高概率输出一个近似正确的模型。它把“能否学习”表达为精度 ε\varepsilon、置信度 1−δ1-\delta、样本量和计算量之间的定量关系。

1. 基本设置

输入空间为 X\mathcal X，二分类标签空间为 {0,1}\{0,1\}，假设类为 H\mathcal H。对假设 hh，0-1 风险为

R(h)=P(X,Y)∼D(h(X)≠Y).R(h)=P_{(X,Y)\sim\mathcal D}(h(X)\ne Y).

训练样本由未知分布 D\mathcal D 独立同分布地产生。

2. 可实现情形

若存在 h∗∈Hh^*\in\mathcal H 使 R(h∗)=0R(h^*)=0，称为可实现（realizable）情形。一个一致学习器输出训练误差为 0 的假设。

若对任意分布、任意 ε,δ∈(0,1)\varepsilon,\delta\in(0,1)，当样本量达到某个多项式规模后，算法以至少 1−δ1-\delta 的概率输出 R(h)≤εR(h)\le\varepsilon 的模型，则称 H\mathcal H PAC 可学习。

3. “大概近似正确”

  • Probably：失败概率不超过 δ\delta；
  • Approximately Correct：真实误差不超过 ε\varepsilon。

形式上：

PS∼Dn(R(A(S))≤ε)≥1−δ.P_{S\sim\mathcal D^n}(R(A(S))\le\varepsilon) \ge1-\delta.

外层概率来自训练集抽样的随机性。

4. 有限假设类的可实现样本复杂度

对任意坏假设 hh 满足 R(h)>εR(h)>\varepsilon，它在 nn 个样本上全部预测正确的概率至多为

(1−ε)n≤e−nε.(1-\varepsilon)^n\le e^{-n\varepsilon}.

对最多 ∣H∣|\mathcal H| 个假设使用并集界，失败概率至多

∣H∣e−nε.|\mathcal H|e^{-n\varepsilon}.

令其不超过 δ\delta，得到充分样本量

n≥log⁡∣H∣+log⁡(1/δ)ε.n\ge\frac{\log|\mathcal H|+\log(1/\delta)}{\varepsilon}.

注意可实现情形对 1/ε1/\varepsilon 的依赖是一阶。

5. 不可实现与 agnostic PAC

现实中标签可能有噪声，且假设类不含零风险模型。agnostic PAC 要求输出模型接近类内最优：

R(A(S))≤inf⁡h∈HR(h)+εR(A(S)) \le\inf_{h\in\mathcal H}R(h)+\varepsilon

以至少 1−δ1-\delta 的概率成立。

对有限假设类，用统一 Hoeffding 界可得到数量级

n=O(log⁡∣H∣+log⁡(1/δ)ε2).n=O\left( \frac{\log|\mathcal H|+\log(1/\delta)}{\varepsilon^2} \right).

由于要估计风险差异而非只排除坏的一致假设，依赖通常变为 1/ε21/\varepsilon^2。

6. 样本复杂度

样本复杂度 mH(ε,δ)m_{\mathcal H}(\varepsilon,\delta) 是保证所需精度和置信度的样本数。理想上它应对

1/ε,quadlog⁡(1/δ),quad问题复杂度1/\varepsilon,quad \log(1/\delta),quad \text{问题复杂度}

呈多项式依赖。

PAC 定义强调对任意数据分布都成立，因此给出的是分布无关的最坏情况保证，实际任务可能容易得多。

7. 表示与计算的区别

统计上存在低风险假设，不代表算法能在可接受时间内找到它。PAC 可学习性常还要求训练时间对输入规模、1/ε1/\varepsilon 和 1/δ1/\delta 为多项式。

因此要区分：

  • 信息论或统计可学习：样本足够时存在算法；
  • 计算可学习：还存在高效算法；
  • 优化可达性：具体实现能否找到好解。

8. 无限假设类

线性分类器的参数是连续的，∣H∣=∞|\mathcal H|=\infty，有限类的 log⁡∣H∣\log|\mathcal H| 无法使用。此时需要 VC 维、Rademacher 复杂度、覆盖数或稳定性等有效复杂度。

关键不是参数取值有无穷多个，而是它们能在有限样本上实现多少种不同标记行为。

9. 分布依赖与其他框架

PAC 是一个基线框架。更细的分析可利用间隔、噪声条件、数据流形、压缩、先验或算法稳定性得到更紧的分布依赖界。PAC-Bayes 通过先验与后验分布的 KL 散度控制随机预测器的泛化，与普通 PAC 概念相关但工具不同。

10. 易错点

  1. PAC 中的概率针对训练样本抽取，不是说每个预测都以 1−δ1-\delta 正确。
  2. ε\varepsilon 是风险容忍度，δ\delta 是学习过程失败概率。
  3. PAC 保证通常是充分条件和最坏情况上界，不是精确所需样本数。
  4. 可学习不等于当前工程系统在有限资源下必然学好。

常见问答

Q1：PAC 是否要求数据完全无噪声？
经典可实现 PAC 是无噪声或类内可完全表达；agnostic PAC 允许噪声和模型错设。

Q2：为什么置信度以 log⁡(1/δ)\log(1/\delta) 进入？
集中不等式的尾概率通常指数下降，反解指数得到对失败概率的对数依赖。

Q3：神经网络参数无穷多，是否不可 PAC 学习？
不能据此判断。需要看有效函数复杂度、范数、架构和算法；无限假设类也可能有有限 VC 维或可控复杂度。

Q4：PAC 界很松，还有价值吗？
它给出可学习性的清晰定义，揭示精度、置信度、复杂度和样本量的基本依赖，并为更精细理论提供基线。

练习

  1. 解释 ε\varepsilon 与 δ\delta 分别控制什么。
  2. 推导坏假设在 nn 个样本上保持一致的概率上界。
  3. 对 ∣H∣=1000|\mathcal H|=1000、ε=0.05\varepsilon=0.05、δ=0.01\delta=0.01，用可实现有限类公式给出充分样本量表达式。
  4. 为什么无限参数集合不等于无限有效复杂度？

答案与提示

  1. ε\varepsilon 控制输出模型与目标的误差，δ\delta 控制抽到坏训练集而学习失败的概率。
  2. 每个样本不暴露该假设错误的概率最多 1−ε1-\varepsilon，独立样本相乘得到 (1−ε)n≤e−nε(1-\varepsilon)^n\le e^{-n\varepsilon}。
  3. n≥[log⁡1000+log⁡100]/0.05n\ge[\log1000+\log100]/0.05，向上取整；自然对数下约 231。
  4. 不同参数可能表示相同或在有限样本上相同的函数，复杂度取决于可实现的预测行为而非参数集合基数。