🏠 总目录📚 本教程 09 · PAC 学习 ← →

09 · 从问题进入原章节

说“学得足够好”时,误差和失败概率各限什么?

ε 限制允许的误差,δ 限制保证失败的概率;样本复杂度还依赖假设类与可实现性前提。

读后可检查:能分开解释两个参数,并说明有限假设空间的界何时有用、何时松。

PAC 的两个不同保证左侧误差阈值 epsilon 限制学到的假设错得多远;右侧失败概率 delta 限制这个误差保证有多大机会失效。两者不是同一种误差。ε · 允许的误差学得有多接近δ · 失败概率保证有多可靠
两项保证需要同时读;样本界还取决于假设空间和课程正文写明的条件。
📑 本页目录(点开跳转)

09 · PAC 学习:要多少数据才够

⏱ 24 分钟 | 在明确假设下,给出样本量的充分保证


🎯 一句话

PAC = Probably Approximately Correct(大概率地、近似正确)。 它把“学得还行”拆成两个可以区分的问题:预测允许错多少?抽到一批坏训练样本的风险允许多大?

本页先讲有限分类规则集合。这些界不是项目数据量的精确报价,也不是少一个样本就一定失败的门槛。

🧠 一、为什么要区分“大概率”和“近似”

想象用不同的训练样本重复学习同一个分类任务:

问题 看什么 对应符号
这次学出的规则,面对新样本错多少? 真实分布上的分类错误率 ε:允许的错误率上限
换一批训练样本,会不会选出太差的规则? 对随机训练集重复抽样时,保证失败的概率 δ:允许的失败概率

例如 ε = 0.1、δ = 0.05,意思是:以至少 95% 的抽样概率,学出的规则真实错误率不超过 10%。 不是“每次预测有 95% 把握”,也不是“训练准确率至少 90%”就够了。

有限数据可能漏掉重要区域;随机抽样也可能碰巧不具代表性。PAC 用这两个量描述一般情形的保证,不是说每一个简单任务都绝不可能被有限数据完全确定。


📐 二、PAC 的正式定义

在本节的可实现分类设定中,先固定假设类 H,并假设真实分类规则可以由 H 中的规则表示。

若存在同一个学习算法和样本量函数 m_H(ε, δ),使得对任意 0 < ε、δ < 1、任意满足上述设定的数据分布 D,抽取至少 m_H(ε, δ) 个独立同分布样本时,都有:

$$P_{S\sim\mathcal D^m}\Big(\underbrace{\mathrm{err}_{\mathcal D}(h_S)}_{\text{真实分类错误率}}\le\varepsilon\Big)\ge 1-\delta$$

就称 H 在这个设定下 PAC 可学习。这里 h_S 是算法用训练集 S 得到的规则;概率是对训练集的随机抽样而言的。

可学习和高效可学习要分开。 上面是统计保证;若还要求样本数和运行时间关于任务规模、1/ε、1/δ 等是多项式,则进一步讨论高效 PAC 学习。不是有样本界就一定算得动。

符号 含义 本页示例
ε 允许的真实分类错误率上限 0.1
δ 允许保证失败的抽样概率 0.05
err_D 对真实分布中新样本的错误率,不是训练错误率 未知,要靠理论给出保证
m 训练样本数 整数
H 学习前固定的候选规则集合 下一节先要求有限

ε 描述规则的错误率,δ 描述这条保证有多可靠。 分清这两个,再看样本量公式。


🔢 三、⭐ 核心结论:样本复杂度界

以下四项必须同时成立:

  1. H 是学习前固定的有限分类规则集合。
  2. 可实现: H 中存在真实分类错误率为 0 的规则。
  3. m 个带标签样本来自同一分布,且相互独立。
  4. 学习器返回 H 中对这批训练样本全部分对的规则;这里可用经验风险最小化(ERM)找到它。

此时,一个足够的样本量条件是:

$$m \ge \frac{1}{\varepsilon}\left(\ln|\mathcal H|+\ln\frac{1}{\delta}\right)$$

满足它,就得到上一节至少 1−δ 的概率保证。不满足它,只表示这条界不给保证,不表示学习必然失败。 对于有噪声的任务,要看第五节的 agnostic 版本。

三个因素分别怎么变

下表只比较这个公式,其他量保持不变;不是实际训练的收益预测。

改变什么 公式右侧如何变化 读法
H 的大小增加 随 ln(H 的大小) 增加 更多候选可能碰巧在训练集全对,需要排除它们
ε 减半 变为原来的 2 倍 更严格的错误率要求,提高这条充分界
δ 减小 随 ln(1/δ) 增加 更可靠的保证也有样本代价

🔑 最实用的一条洞察

对数增长不等于“直接乘一个对数值”。 固定 ε、δ,把 H 的大小乘以 1000,公式右侧增加的是 ln(1000)/ε。

取 ε = 0.1、δ = 0.05:

候选规则数 公式右侧 向上取整后的充分样本数
1000 99.03 100
1,000,000 168.11 169

不是乘以 7。类似地,固定 H 的大小为 1000,把 δ 从 0.1 改成 0.001,右侧从约 92.10 变成 138.16,是 1.5 倍,不是固定 3 倍。

若把 ε 从 0.05 改为 0.01,其他条件不变,这个界会变为 5 倍。不能据此保证“把数据增至 5 倍,测试准确率就会从 95% 变成 99%”:真实学习曲线仍需实验。

📐 这个界怎么来的:指数不等式与联合界

第一步:看一个坏规则。 若它的真实错误率大于 ε,在一个新样本上碰巧正确的概率小于 1−ε。

第二步:看 m 个独立样本。 它全部分对的概率至多为:

$$(1-\varepsilon)^m\le e^{-\varepsilon m}$$

第三步:把所有候选坏规则合起来。 用联合界,“至少有一个坏规则通过了全部样本”的概率至多为:

$$|\mathcal H|e^{-\varepsilon m}$$

第四步:把这个风险压到 δ 以下。

$$|\mathcal H|e^{-\varepsilon m}\le\delta \quad\Longrightarrow\quad m\ge\frac{\ln|\mathcal H|+\ln(1/\delta)}{\varepsilon}$$

所以,以至少 1−δ 的概率,没有坏规则能在训练集全对。学习器又确实返回一个训练集全对的规则,因此它不是坏规则。这就是不能遗漏第 4 个条件的原因。


🧮 四、算个具体的数

例 1:学习布尔合取式

每个布尔特征有三种选择:作为正条件出现、取反出现、不出现。例如“x₁ 为真,而且 x₃ 为假”。

考虑这种每个特征最多出现一次、排除同时包含某特征及其反面的合取式,约定空合取为真,则 n 个特征对应 3ⁿ 个候选规则:

$$|\mathcal H|=3^n,\qquad \ln|\mathcal H|=n\ln3$$

固定 ε = 0.1、δ = 0.05,并满足第三节前提:

特征数 n 公式右侧(约) 向上取整
10 139.82 140
20 249.68 250
100 1128.57 1129

这里公式随 n 线性增长。“能用少量样本给保证”不等于所有真实任务都这么简单:可实现与候选类限制仍然重要。

例 2:一个对比(说明 H 的大小的影响)

n 个布尔特征有 2ⁿ 种输入。若允许任意二分类函数,每种输入都可独立选标签,候选数就是:

$$|\mathcal H|=2^{2^n},\qquad \ln|\mathcal H|=2^n\ln2$$

同样取 n = 20、ε = 0.1、δ = 0.05,这条充分界向上取整为 7,268,205 个样本,而上面的合取式类为 250 个。

看的是同一个界在两个候选类上的差别。不能说学习任意布尔函数“至少必须有 727 万样本”:这是充分上界,不是最小需求的下界。

限制候选类能帮助给出更小的样本保证,但要付出风险:真实关系可能被排除在外。这是 第 11 章「没有免费的午餐」里归纳偏置的一种具体体现。


⚠️ 五、这个界的三个局限(必须知道)

局限 对读者意味着什么
可能很宽松 不能把最坏情况的充分保证当作项目数据预算,也没有通用的“除以 10 或 100”换算
只适用于有限 H 实值参数模型的函数集合往往无限,这个计数界不能直接代入;可继续看第 10 章的 VC 维
假设可实现 有标签噪声或模型表达不了真实关系时,需要另一种保证

关于第三点:agnostic PAC

不再要求存在零错误规则,而是要求:学出的规则比 H 中最好的规则,真实错误率至多多 ε。 仍以至少 1−δ 的抽样概率成立:

$$\mathrm{err}_{\mathcal D}(\hat h)\le \min_{h\in\mathcal H}\mathrm{err}_{\mathcal D}(h)+\varepsilon$$

对于有限 H、独立同分布样本、0–1 分类损失和精确 ERM,一条由 Hoeffding 不等式与联合界得到的充分条件为:

$$m\ge\frac{2}{\varepsilon^2} \left(\ln|\mathcal H|+\ln\frac{2}{\delta}\right)$$

这里 ε 是相对于类内最优的额外错误率,不是总错误率。这个充分界按 1/ε² 增长:ε 减半,右侧变为 4 倍,仍不保证实际所需样本恰好变为 4 倍。

为什么系数是 2,而不是 1/2?

先让 H 中每个规则的训练错误率与真实错误率相差不超过 ε/2。需要跨过两次这个差距:从选中规则的真实错误率到训练错误率,再从类内最优规则的训练错误率回到真实错误率。

ERM 保证中间的训练错误率比较不吃亏,两次各 ε/2 合起来才是 ε。将 ε/2 代入 Hoeffding 的双侧界,得到:

$$2|\mathcal H|\exp\left(-2m(\varepsilon/2)^2\right)\le\delta$$

解出 m 就是上面的 2/ε²。用 ε 而非 ε/2 做一致偏差界,只能经这条推导保证至多 2ε 的额外错误率。

推导口径可对照 MIT 6.790:一致收敛如何保证 agnostic PAC 学习。这里并未声称这个常数是所有问题中最紧的常数。

那学它还有什么用?

先区分三件事:条件是否成立、理论给出哪种保证、实际任务还有哪些证据。 PAC 帮你理解复杂度、数据量与容许误差的权衡,也为 VC 维和其他泛化分析作准备;不能替代具体任务的验证。


🔗 六、和站内其他章的关系

相关的地方 可以怎样连接,不能怎样推广
模型复杂度与过拟合 更多候选会提高这个界;样本少于界不等于已经过拟合
数据量与泛化 条件不变时,更多独立样本能改善保证;不是每次测试分数必涨
正则化 限制候选集合或偏向某类函数,可控制有效复杂度;软惩罚不一定改变集合的字面大小
小数据与简单模型 更强的限制可能降低估计难度,也可能排除正确规律
CNN 的图像归纳偏置 结构假设可能有帮助;这条有限集合公式本身不证明 CNN 必胜 MLP
基础教程第 5 章的学习曲线 学习曲线是实测;理论界是满足前提时的保证,两者不是同一条曲线

第 2 章从先验看正则化,第 8 章讨论偏差与方差,第 10 章讨论复杂度。它们提供互补视角,使用时要核对各自的模型、损失和条件。


🔗 这一章连到哪里

去哪 为什么
ML基础 05 区分训练、验证、测试与实测学习曲线;本页的训练样本界不直接回答验证集要留多大
Kaggle 22 看公榜波动和反复选择的风险;不要把本页有限类公式直接当作 shake-up 的完整解释
上线之后 12 A/B 实验也问样本量,但 MDE、显著性和检验功效属于另一套假设,不能和本页公式混算

✅ 检查点

  1. ε = 0.1、δ = 0.05 分别在描述什么?
  2. err_D 与训练错误率有什么区别?概率公式里的随机性来自哪里?
  3. 使用第三节有限类公式,需要哪四个前提?
  4. H 的大小乘以 1000,是否意味着样本界乘以 7?ε 减半呢?
  5. 有限类界的推导用了哪两个工具?为什么学习器必须返回训练集全对的规则?
  6. n = 20 时,两种候选类的界各是多少?能把它们说成最低必需样本量吗?
  7. agnostic PAC 的 ε 指什么?为什么上面的推导先控制 ε/2?
👀 答案
  1. ε 是真实分类错误率的容许上限;δ 是抽样导致这项保证失败的容许概率。不是单次预测的置信度。
  2. err_D 面向同分布的新样本,训练错误率只看已观察样本;公式中的概率是对训练集 S 的随机抽样而言的。
  3. 预先固定的有限 H、可实现、独立同分布抽样、返回 H 中训练错误为 0 的规则。
  4. 不是。固定 ε、δ 时增加 ln(1000)/ε;倍率取决于原来的 H 和 δ。固定其他量,将 ε 减半会让这个可实现版本的充分界变为 2 倍。
  5. 指数不等式与联合界排除“坏规则恰好训练全对”的事件;若算法根本不选训练全对的规则,就不能直接使用这个结论。
  6. 合取式类为 250,任意布尔函数类为 7,268,205,都是指定条件下的充分界,不是实际最低需求。
  7. ε 是相对 H 内最优规则的额外真实错误率。比较 ERM 与类内最优时跨过两次训练/真实差距,各控制 ε/2,合计才是 ε。

本节回顾

⚡ 走神救援

先记住这几件事

下一节 👉 10-VC维.md ⭐

打卡记录保存在你的浏览器里,首页能看到总进度