PAC 可学习性 | Codeboy's Blog

形式陈述

沿用批量统计学习问题的 IID 协议和 0–1 损失。非空二分类类 $\mathcal H\subseteq\{0,1\}^{\mathcal X}$ 是 PAC 可学习的，若存在同一个学习器 $A$ 和样本复杂度函数 $m_{\mathcal H}(\varepsilon,\delta)$ ，使对任意输入分布 $D_X$ 、任意目标 $h^*\in\mathcal H$ ，样本满足

X_i\overset{\mathrm{iid}}{\sim}D_X, \qquad Y_i=h^*(X_i),

且 $m\ge m_{\mathcal H}(\varepsilon,\delta)$ 时，

\Pr_{S,U}\!\left( \Pr_{X\sim D_X}[A(S,U)(X)\ne h^*(X)] \le\varepsilon \right) \ge1-\delta.

内层概率是新输入上的总体分类错误，外层概率来自训练样本与独立算法种子。PAC 的 approximately correct 是总体错误至多 $\varepsilon$ ，probably 是外层失败概率至多 $\delta$ 。

量词顺序是先固定同一个 $A$ 和 $m_{\mathcal H}$ ，再遍历 $\varepsilon,\delta,D_X,h^*$ 与所有足够大的 $m$ 。训练标签来自 $h^*$ ，风险却在新的 $X\sim D_X$ 上计算。学习器只接收样本和独立随机种子，不接收 $D_X$ 或 $h^*$ ；把未知对象作为输入会预先解答学习问题。

信息论 PAC 只要求每个 $\varepsilon,\delta$ 存在有限样本界。输出始终属于 $\mathcal H$ 时是 proper；improper 只表示输出不必属于 $\mathcal H$ ，并不要求预先声明的输出类包含 $\mathcal H$ 。两者使用同一个类内目标 $h^*$ 。若还要求样本、运行时间、输出长度与预测时间在规定表示参数上为多项式，才是高效 PAC。输出约束与计算效率是两个独立维度。

直觉

PAC 的量词把“对某份数据拟合得好”提升成“同一个学习器面对任意允许分布和类内目标，都能随数据增加达到任意精度”。学习器不知道世界选择了哪个分布和概念，只能从样本缩小候选；probably 与 approximately 分别控制抽样失败和剩余总体错误。

PAC 可学习性：训练随机性上的高置信保证包住总体分类误差 — 外层置信与内层错误

例子与边界

定义是可实现分支：标签由类内目标无噪声产生。有限样本一致并不自动 PAC，仍需控制类复杂度；所有函数类便能一致记忆而不能泛化。现代定义也不同于 Valiant 1984 原文的特定布尔概念、正负样本与计算约束，引用历史结果时应说明采用哪个版本。

有限类给出一个完整见证。若算法返回任意一致假设，对错误率至少为 $\varepsilon$ 的固定 $h$ ，它在 $m$ 个 IID 点上一次也不犯错的概率至多 $(1-\varepsilon)^m\le e^{-m\varepsilon}$ 。对全部 $|\mathcal H|$ 个坏假设求并，令

|\mathcal H|e^{-m\varepsilon}\le\delta,

便得 $m\ge(\log|\mathcal H|+\log(1/\delta))/\varepsilon$ 。这不只证明某次训练成功，而是给出了满足 PAC 全部量词的同一个算法与样本函数。

PAC 可学习性是类和表示协议的性质，不是某份数据的标签。对一个固定分布表现好不能替代“对所有分布”；允许算法预先知道目标 $h^*$ 也会使定义空洞。标准参数域取 $0<\varepsilon,\delta<1$ ，否则精度或置信要求会失去通常意义。

阈值类给出非有限类的标准真例。令 $\mathcal X=\mathbb R$ ，并取 $\mathcal H=\{h_a:a\in\mathbb R\cup\{+\infty\}\}$ ，其中 $h_a(x)=\mathbf1\{x\ge a\}$ 且约定 $h_{+\infty}\equiv0$ 。学习器输出样本中最小正例的位置；若没有正例，则输出 $h_{+\infty}$ 。输出阈值不会落在真实阈值左侧，错误只可能来自真实阈值与最小正例之间的正类质量。若该错误质量超过 $\varepsilon$ ，样本就必须完全漏掉一个质量至少为 $\varepsilon$ 的正类区间，因此

\Pr(R(A(S))>\varepsilon) \le(1-\varepsilon)^m \le e^{-m\varepsilon}.

所以 $m\ge\log(1/\delta)/\varepsilon$ 足够。这个单侧算法避免了未说明的两侧并集常数，也展示不可数参数类仍可 PAC 学习。

非例是所有二元函数类：算法可一致拟合任意有限样本，但未见点可由目标任意标注。它的不可学性来自无限打散能力，与参数集合是否无限无关；这正是 VC 理论接手刻画的边界。

推论与应用

有限 VC 维给二元类的分布无关 PAC 可学习性提供精确结构刻画；有限类的并集界和阈值类的危险区间则分别展示离散与连续类如何实现定义。样本复杂度界继续量化 $\varepsilon,\delta$ 与类复杂度的依赖。

从数据设定看，可实现 PAC 是不可知 PAC在类内最优风险为零、标签由类内目标生成时的特殊分支；这正是本页 special_case_of 的方向。不可知保证因覆盖更多分布而更强，应用到可实现分布时会推出本页保证。再加入表示长度和多项式时间得到高效 PAC。三个层次分别改变数据假设、风险基准与计算资源，不能只凭共同的 PAC 名称互换定理。

参考资料

Leslie Valiant, “A Theory of the Learnable,” 1984.
Blumer et al., “Learnability and the Vapnik–Chervonenkis Dimension,” 1989.

形式陈述 ​

反向链接

形式陈述