PAC 可学习性

定义中的量词 ​

沿用批量统计学习问题公理库统计学习问题Statistical learning problem从未知分布的有限观测中选择决策规则，并以样本外表现评价其质量。的 IID 协议，二分类类 $\mathcal{H}$ 是 PAC 可学习的，若存在算法 $A$ 和函数 $m_{\mathcal{H}}(\epsilon ,\delta )$，使对任意分布 $D_X$、任意目标 $h^{\ast }\in \mathcal{H}$，从 $X_i\sim D_X$ 与 $Y_i=h^{\ast }(X_i)$ 得到至少 $m_{\mathcal{H}}$ 个样本后，

$$\text{Pr}(R(A(S))\le \epsilon )\ge 1-\delta .$$

概率对样本和算法随机性取；分布与目标在外层任意。PAC 的“approximately correct”是总体错误至多 $\epsilon$，“probably”是失败概率至多 $\delta$。

把量词完整展开，要求存在同一个 $A$，使

$$\mathrm{\forall }\epsilon ,\delta \in (0,1),\mathrm{\forall }{D}_X,\mathrm{\forall }{h}^{\ast }\in \mathcal{H},m\ge m_{\mathcal{H}}(\epsilon ,\delta )⟹{\text{Pr}}_{S,U}\{R_{D_X}(A(S,U),h^{\ast })\le \epsilon \}\ge 1-\delta .$$

训练标签来自 $h^{\ast }$，风险却在新的 $X\sim D_X$ 上计算。算法可以不知道 $D_X$ 与 $h^{\ast }$；若允许它们作为输入，学习问题会被预先解答。

信息论 PAC 只要求每个 $\epsilon ,\delta$ 存在有限样本界；若还要求其及运行时间对 $1/\epsilon ,\log \left(1/\delta \right)$ 和表示长度为多项式，才是高效 PAC公理库高效 PAC 学习Efficient PAC learning在 PAC 统计保证之外，要求样本处理、运行时间与输出评价均为多项式。。输出可 proper 或 improper，必须另行注明。

边界 ​

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

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

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

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

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

阈值类给出非有限类的标准真例。对可实现样本，取最大负例与最小正例之间的任一阈值；若输出风险仍大于 $\epsilon$，真实阈值一侧必有质量至少 $\epsilon$ 的“危险区间”未被样本命中，其概率至多 $(1-\epsilon {)}^m$。因此 $m\ge \log \left(1/\delta \right)/\epsilon$ 已足够，说明不可数参数类也能 PAC 学习。

非例是所有二元函数类：算法可一致拟合任意有限样本，但未见点可由目标任意标注。PAC 失败的原因不是参数无限，而是类保留了无限打散能力；这正是 VC 理论接手刻画的边界。

参考资料

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