PAC 可学习性

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

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

有限类给出一个完整见证。若算法返回任意一致假设，对错误率至少为 $\epsilon$ 的固定 $h$，它在 $m$ 个 IID 点上一次也不犯错的概率至多 $(1-\epsilon {)}^m\le e^{-m\epsilon }$。对全部 $|\mathcal{H}|$ 个坏假设使用并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，令

便得 $m\ge (\log |\mathcal{H}|+\log \left(1/\delta \right))/\epsilon$。这不只证明某次训练成功，而是给出了满足 PAC 全部量词的同一个算法与样本函数。关键好事件是“所有坏假设都被至少一个训练点排除”，而不是“某个预先指定的好假设存活”。因此即使算法根据样本任意打破一致假设之间的平局，结论仍成立；可实现条件保证目标 $h^{\ast }$ 自己不会被排除，候选集合不会为空。

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

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

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

反例须注明输入域：在含任意大有限子集的无限域上，所有二元函数构成的类可以一致拟合训练集，却没有统一有限样本 PAC 保证；未见点的标签完全不受已见点约束。在固定 $N$ 点域上，同样的“所有二元函数”却只有 $2^N$ 个，上面的有限类证明直接给出 $m\ge (N\log 2+\log \left(1/\delta \right))/\epsilon$ 的充分界。问题不在于是否允许任意函数这个口号，而在于对整个允许域是否存在统一的容量控制。

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

从数据设定看，可实现 PAC 是不可知 PAC理路不可知 PAC 可学习性Agnostic PAC learnability不假定类内零风险真规则，而要求高概率接近比较类中的最佳风险。在类内最优风险为零、标签由类内目标生成时的特殊分支。不可知保证因覆盖更多分布而更强，应用到可实现分布时会推出本页保证。再加入表示长度和多项式时间得到高效 PAC。三个层次分别改变数据假设、风险基准与计算资源，不能只凭共同的 PAC 名称互换定理。