从工程视角读懂《An Optimal Agnostic PAC Algorithm》不可知学习、最优样本复杂度与模型选择的底层逻辑当你把一个分类模型的准确率从 91% 追到 91.5%你花掉的每一万条新标注数据背后都有一个非常实际的问题这个模型离当前任务的最优可能表现到底还有多远如果最优差距已经被压缩得很小继续加样本就是在买彩票如果差距还很大加样本才是理性投入。学习理论里有一套框架专门用来回答这类问题叫PAC 学习。而An Optimal Agnostic PAC Algorithm这个标题把 PAC 学习中三个关键问题一次性推到台前学习目标不必“完美”Agnostic、算法必须真能跑Algorithm、样本需求不能被浪费Optimal。很多人看到这种标题第一反应是“又是一篇纯数学论文跟工程没关系”。但我反而觉得它和做模型评估、做数据集规划、做模型选择的工程同学关系很大。因为这套理论的核心结论是在一个固定假设类里即使真实数据充满噪声也存在一种算法用最少的样本量保证你学到的模型几乎和这个假设类里最好的模型一样好。这里的“最少”是被理论下界钉死的。本文将从一个阈值分类器的最小例子讲起逐步拆解 PAC、Agnostic、Optimal 这三个词最后用 Python 把抽象保证变成可视化曲线。文章不需要很强的数学背景但如果你打算深入学习机器学习理论我会在结尾给出一条完整的学习路径。1. 这篇文章真正要解决的问题先把这个标题拆开看它其实对应着四个工程问题第一PACProbably Approximately Correct问的是你训练出来的“好模型”到底好到什么程度这种好是有概率保证的还是碰运气在经典 PAC 框架下我们允许模型犯一点错误也允许它以很小的概率失败但除此之外算法必须在绝大多数数据集上都有稳定表现。第二Agnostic不可知问的是当数据本身不配合比如存在标签噪声、特征重叠、样本分布漂移时学习任务还定得清楚吗经典的 PAC 学习假设数据存在一个完美标签函数这在现实里几乎不成立。Agnostic 学习把这个理想化假设去掉不再要求模型学到“正确答案”只要求模型尽量接近假设类里能做的最好的水平。第三Algorithm 强调的是理论学家不能只说“存在一个学习器”然后就不管了。标题里的 Algorithm 意味着这个结果是一个真正可执行的算法而不是一个抽象的存在性证明。第四Optimal 问的是手里的训练样本有没有被浪费如果你用 100 万条样本才能达到某个误差而理论上 50 万条就够那这个算法就不是最优的。所谓最优是指样本复杂度达到了理论下界不多不少。围绕这四个问题读完本文你可以得到三样东西理解 PAC 与 Agnostic PAC 的数学定义和直觉知道它们在保证什么、不保证什么。理解“最优算法”的判定标准也就是样本复杂度下界。把理论结论转化为工程判断数据量规划、模型选择、以及如何判断“是否还有提升空间”。2. 基础概念PAC 学习到底在保证什么PAC 学习由 Leslie Valiant 在 1984 年提出是机器学习理论中最基础的分析框架。它的目标很简单给定一堆带标签样本希望找到一个假设 (h)让它在未知数据分布 (D) 上的期望误差尽量小。为了把一个想法讲清楚我们用二分类作为例子。假设你有一个数据分布 (D)样本是 (x)标签是 (y \in {0,1})。一个假设 (h) 的“真实误差”定义为[ L_D(h) \mathbb{E}_{(x,y) \sim D}[\mathbb{1}[h(x) \neq y]] ]这个真实误差也叫泛化误差。它衡量的是把 (h) 放到整个未知分布上平均每预测一个样本犯错概率是多少。问题在于我们只能拿到有限数据集 (S {(x_1,y_1), \dots, (x_m,y_m)})并不清楚 (D) 到底是什么。于是只能先计算训练集上的经验误差[ L_S(h) \frac{1}{m} \sum_{i1}^{m} \mathbb{1}[h(x_i) \neq y_i] ]PAC 学习的核心就是给“经验误差和真实误差之间的差距”一个概率保证。形式化地说如果存在一个学习算法 (A)对任意 (\epsilon 0) 和 (\delta 0)只要训练样本量 (m) 足够大算法输出的假设 (h_A) 都能满足[ \Pr_{S \sim D^m} \left[ L_D(h_A) \le \min_{h \in H} L_D(h) \epsilon \right] \ge 1 - \delta ]那么我们就说这个学习问题是 PAC 可学的。这里的 (\epsilon) 可以理解为“允许差多少”比如允许最终误差比最优假设差 5%(\delta) 是“允许失败的概率”比如 95% 置信度也就是 (\delta 0.05)。PAC 保证的意思是不是每次训练都成功但绝大多数时候都会成功。为了更容易记忆你可以把它类比成面试招聘候选人的分布未知面试官只能通过有限几轮面试判断水平。PAC 保证的是在面试了足够多的人之后招进来的人有 95% 的概率不会比“市场上能达到的最好候选人”差太多。值得注意的是上面这个公式其实是Agnostic PAC的定义只不过很多人平时会把 PAC 和 Agnostic PAC 混着说。在 Valiant 原始定义里还存在一个假设数据是由某个真实概念 (c) 生成的而且 (c \in H)。换句话说存在一个完美答案只是你需要通过样本把它找出来。这种设定叫Realizable PAC它比现实情况要理想得多。3. Agnostic去掉“存在完美分类器”的天真假设如果我们直接拿着经典 PAC 的定义去套现实问题很快就会撞墙。以垃圾邮件分类为例什么才是一封邮件“真正的标签”不同用户对垃圾邮件的定义不同同一封邮件今天可能被标记为广告明天可能被标记为正常邮件标注员自己也可能出错。你很难说存在一个完美的 (c)让所有数据都严格由它生成。更常见的情况是数据本身带有噪声特征空间里有无法避免的重叠最好的分类器也只能把误差压到某个下限这个下限大于 0。这个“下限”在统计学习里叫贝叶斯误差也就是在当前特征信息下理论上最优分类器能达到的误差。Agnostic 学习的出现正是为了在“不存在完美分类器”的现实里仍然给学习算法一个清晰的目标。Agnostic PAC 的定义和上一节写的一样学习算法不需要把误差压到 0它只需要以高概率达到“假设类里最优假设的误差 (\epsilon)”。更直白一点[ L_D(\hat h) \le \inf_{h \in H} L_D(h) \epsilon ]Agnostic 学习的意义是把学习目标从“绝对准确”换成“相对最优”。如果我提前限定了假设类 (H)比如“只能使用线性分类器”那么 Agnostic 学习的目标就是在全体线性分类器里找到一个和最好的线性分类器几乎一样好的模型。它没有承诺你一定赶上贝叶斯误差因为线性分类器可能本身就不如非线性分类器。这里有一个非常容易误解的地方Agnostic 并不是“不做任何假设”或“不需要任何先验”。它依然有两个前提一是样本仍然是独立同分布采样的二是你仍然需要指定一个假设类 (H)。它去掉的只是“存在完美概念且这个概念落在 (H) 里”这个不现实的假设。可以用一个表来对比两者维度经典 PACRealizableAgnostic PAC数据生成方式存在目标概念 (c)且 (c \in H)任意分布不需要存在完美分类器学习目标误差接近 0误差接近假设类里最优假设训练误差参考值训练误差趋向 0训练误差趋向下面的“地板”样本复杂度0-1 损失VC 维为 (d)(\Theta((d \log(1/\delta))/\epsilon))(\Theta((d \log(1/\delta))/\epsilon^2))更贴近的现实场景理想化教科书问题真实工业数据、带噪声标签、特征重叠为什么 Agnostic 的样本复杂度明显更高直觉上在 Realizable 设定里训练误差一旦为 0你就有很强的信心认为模型已经学到了正确的规律而在 Agnostic 设定里训练误差永远不可能为 0你只能估计“最优误差大概是多少”。用统计学的语言说估计一个非零的均值比估计一个零均值要困难方差项无法消除所以需要更多样本。从工程视角看Agnostic 框架更值得信赖。它不依赖“数据必须是干净完美”的运气而是让你思考一个更有价值的问题在我能接受的模型复杂度范围内最好的模型能做到多好我现在做的模型距离这个上限还有多远4. ERM最朴素却最强大的不可知学习算法我们知道了 Agnostic PAC 的学习目标接下来问题是什么算法能实现这个目标最自然的答案是经验风险最小化Empirical Risk Minimization, ERM。ERM 的做法极其简单在假设类 (H) 里挑出训练集上误差最小的那个假设[ \hat h \arg\min_{h \in H} L_S(h) ]工程上你每天都在用 ERM只是没意识到。逻辑回归训练是在线性假设类里最小化对数损失决策树的 CART 算法是在树空间里做贪心的结构风险最小化神经网络用梯度下降找损失较小的参数本质上也接近 ERM 的一种近似实现。ERM 的合理性来自一个核心数学工具一致收敛Uniform Convergence。它说的是如果假设类 (H) 的复杂度足够受限那么在大样本下所有假设的经验误差都会以高概率接近自己的真实误差。把所有“经验误差”和“真实误差”的差距统一控制住再取最小值就能得到[ L_D(\hat h) \le \inf_{h \in H} L_D(h) \epsilon ]控制假设类复杂度的经典指标是VC 维。VC 维衡量的是一个假设类最多能“打散”多少个数据点。VC 维越大假设类的表达能力越强但样本需求也越高。在 0-1 损失、VC 维为 (d) 的 Agnostic PAC 框架下ERM 的样本复杂度满足[ m O\left(\frac{d \log(1/\delta)}{\epsilon^2}\right) ]读者不要被这个式子吓到。它的含义非常直白模型越复杂(d) 越大对误差要求越高(\epsilon) 越小对置信度要求越高(\delta) 越小需要的样本就越多而且误差要求对样本量的影响是平方级的。如果想把误差减半样本量大约要变成原来的 4 倍。这也是为什么在真实项目里模型越复杂越容易在小数据集上产生严重的过拟合。理论上早就给出了明确的警告。5. “最优”的精确含义样本复杂度下界现在终于轮到标题里最重要的词Optimal。在机器学习理论里“最优”这个词需要被严格定义。它不是“运行速度最快”也不是“实现最简单”而是指样本复杂度达到理论下界。也就是说任何一个算法想在任意数据分布上都达到同样的误差保证至少需要这么多样本而某个算法恰好达到了这个量级它就是一个最优算法。这种论证方式叫Minimax 下界。它考虑的是一个“最坏分布”就算学习算法知道所有信息只要样本数量不足某个阈值就一定有某种数据分布让算法失败。因此任何算法都无法绕过这个样本量瓶颈。在 0-1 损失的 Agnostic PAC 学习中公认的下界是[ m \Omega\left(\frac{d}{\epsilon^2}\right) ]这个结果和我们上一节提到的 ERM 上界在 (\epsilon) 和 (d) 的主导阶上完全一致。因此可以得出一个很强的结论对于很多有限 VC 维假设类来说ERM 本身就是一个最优的 Agnostic PAC 算法。看到这里你可能会觉得既然如此那标题里的 “An Optimal Agnostic PAC Algorithm” 还有什么可研究的价值这里的关键在于ERM 并不是唯一的候选甚至不一定是最容易分析或最重要的候选。“最优”可以发生在不同层次样本复杂度常数量级最优。算法对假设类的结构要求更低比如一些无限类。算法在“可实现”realizable和“不可知”agnostic两种设置下同时达到最优不需要提前知道当前任务属于哪一种。算法不依赖额外参数不用设计者根据数据分布微调。所以An Optimal Agnostic PAC Algorithm这类标题通常意味着研究者完成了一件更精细的事给出一个统一的、参数几乎不用调的算法并在理论上证明它的样本复杂度达到下界。这个结果的价值不是“造出一个更好用的新模型”而是从信息论意义上证明达到某种学习目标最少需要多少数据以及哪一种算法能够实现它。理解“最优”这个概念对工程判断也有直接帮助。如果你发现在某个小数据集上任何模型都很难把验证集误差压到某个值以下再去想“是不是模型不够强、训练不够久”之前先问一个问题在这个特征集和标签噪声水平下理论上限是多少很可能你离理论上限已经很近继续堆模型复杂度只会增加样本需求而不是降低误差。6. 用 Python 可视化不可知 PAC 行为纯文字讲理论很容易飘。这一节我们写一点代码把上面几个核心概念落地。6.1 环境与实验设计实验使用 Python 3.8 及以上版本依赖numpy和scikit-learn。如果没有安装可以先执行pip install numpy scikit-learn我们将做两个实验在阈值分类器假设类上做 ERM模拟 Agnostic PAC 的“成功率随样本量变化”曲线。在一个人为生成的带噪声二分类任务上用逻辑回归逼近贝叶斯误差观察“最优差距”。6.2 代码一阈值分类器的 ERM 与 PAC 模拟阈值分类器是所有假设里最容易理解的一种给定一个阈值 (\theta)当 (x \ge \theta) 时预测为正类否则为负类。这个假设类的 VC 维是 1因为一个阈值最多只能打散 2 个点。# pac_demo.py import numpy as np def threshold_erm(x, y): 在阈值分类器集合 {1[x theta] : theta in [0, 1]} 上做经验风险最小化 candidates np.sort(np.unique(np.concatenate([[0.0], x, [1.0]]))) best_theta, best_err
工程视角解读最优Agnostic PAC算法：样本复杂度与模型选择
从工程视角读懂《An Optimal Agnostic PAC Algorithm》不可知学习、最优样本复杂度与模型选择的底层逻辑当你把一个分类模型的准确率从 91% 追到 91.5%你花掉的每一万条新标注数据背后都有一个非常实际的问题这个模型离当前任务的最优可能表现到底还有多远如果最优差距已经被压缩得很小继续加样本就是在买彩票如果差距还很大加样本才是理性投入。学习理论里有一套框架专门用来回答这类问题叫PAC 学习。而An Optimal Agnostic PAC Algorithm这个标题把 PAC 学习中三个关键问题一次性推到台前学习目标不必“完美”Agnostic、算法必须真能跑Algorithm、样本需求不能被浪费Optimal。很多人看到这种标题第一反应是“又是一篇纯数学论文跟工程没关系”。但我反而觉得它和做模型评估、做数据集规划、做模型选择的工程同学关系很大。因为这套理论的核心结论是在一个固定假设类里即使真实数据充满噪声也存在一种算法用最少的样本量保证你学到的模型几乎和这个假设类里最好的模型一样好。这里的“最少”是被理论下界钉死的。本文将从一个阈值分类器的最小例子讲起逐步拆解 PAC、Agnostic、Optimal 这三个词最后用 Python 把抽象保证变成可视化曲线。文章不需要很强的数学背景但如果你打算深入学习机器学习理论我会在结尾给出一条完整的学习路径。1. 这篇文章真正要解决的问题先把这个标题拆开看它其实对应着四个工程问题第一PACProbably Approximately Correct问的是你训练出来的“好模型”到底好到什么程度这种好是有概率保证的还是碰运气在经典 PAC 框架下我们允许模型犯一点错误也允许它以很小的概率失败但除此之外算法必须在绝大多数数据集上都有稳定表现。第二Agnostic不可知问的是当数据本身不配合比如存在标签噪声、特征重叠、样本分布漂移时学习任务还定得清楚吗经典的 PAC 学习假设数据存在一个完美标签函数这在现实里几乎不成立。Agnostic 学习把这个理想化假设去掉不再要求模型学到“正确答案”只要求模型尽量接近假设类里能做的最好的水平。第三Algorithm 强调的是理论学家不能只说“存在一个学习器”然后就不管了。标题里的 Algorithm 意味着这个结果是一个真正可执行的算法而不是一个抽象的存在性证明。第四Optimal 问的是手里的训练样本有没有被浪费如果你用 100 万条样本才能达到某个误差而理论上 50 万条就够那这个算法就不是最优的。所谓最优是指样本复杂度达到了理论下界不多不少。围绕这四个问题读完本文你可以得到三样东西理解 PAC 与 Agnostic PAC 的数学定义和直觉知道它们在保证什么、不保证什么。理解“最优算法”的判定标准也就是样本复杂度下界。把理论结论转化为工程判断数据量规划、模型选择、以及如何判断“是否还有提升空间”。2. 基础概念PAC 学习到底在保证什么PAC 学习由 Leslie Valiant 在 1984 年提出是机器学习理论中最基础的分析框架。它的目标很简单给定一堆带标签样本希望找到一个假设 (h)让它在未知数据分布 (D) 上的期望误差尽量小。为了把一个想法讲清楚我们用二分类作为例子。假设你有一个数据分布 (D)样本是 (x)标签是 (y \in {0,1})。一个假设 (h) 的“真实误差”定义为[ L_D(h) \mathbb{E}_{(x,y) \sim D}[\mathbb{1}[h(x) \neq y]] ]这个真实误差也叫泛化误差。它衡量的是把 (h) 放到整个未知分布上平均每预测一个样本犯错概率是多少。问题在于我们只能拿到有限数据集 (S {(x_1,y_1), \dots, (x_m,y_m)})并不清楚 (D) 到底是什么。于是只能先计算训练集上的经验误差[ L_S(h) \frac{1}{m} \sum_{i1}^{m} \mathbb{1}[h(x_i) \neq y_i] ]PAC 学习的核心就是给“经验误差和真实误差之间的差距”一个概率保证。形式化地说如果存在一个学习算法 (A)对任意 (\epsilon 0) 和 (\delta 0)只要训练样本量 (m) 足够大算法输出的假设 (h_A) 都能满足[ \Pr_{S \sim D^m} \left[ L_D(h_A) \le \min_{h \in H} L_D(h) \epsilon \right] \ge 1 - \delta ]那么我们就说这个学习问题是 PAC 可学的。这里的 (\epsilon) 可以理解为“允许差多少”比如允许最终误差比最优假设差 5%(\delta) 是“允许失败的概率”比如 95% 置信度也就是 (\delta 0.05)。PAC 保证的意思是不是每次训练都成功但绝大多数时候都会成功。为了更容易记忆你可以把它类比成面试招聘候选人的分布未知面试官只能通过有限几轮面试判断水平。PAC 保证的是在面试了足够多的人之后招进来的人有 95% 的概率不会比“市场上能达到的最好候选人”差太多。值得注意的是上面这个公式其实是Agnostic PAC的定义只不过很多人平时会把 PAC 和 Agnostic PAC 混着说。在 Valiant 原始定义里还存在一个假设数据是由某个真实概念 (c) 生成的而且 (c \in H)。换句话说存在一个完美答案只是你需要通过样本把它找出来。这种设定叫Realizable PAC它比现实情况要理想得多。3. Agnostic去掉“存在完美分类器”的天真假设如果我们直接拿着经典 PAC 的定义去套现实问题很快就会撞墙。以垃圾邮件分类为例什么才是一封邮件“真正的标签”不同用户对垃圾邮件的定义不同同一封邮件今天可能被标记为广告明天可能被标记为正常邮件标注员自己也可能出错。你很难说存在一个完美的 (c)让所有数据都严格由它生成。更常见的情况是数据本身带有噪声特征空间里有无法避免的重叠最好的分类器也只能把误差压到某个下限这个下限大于 0。这个“下限”在统计学习里叫贝叶斯误差也就是在当前特征信息下理论上最优分类器能达到的误差。Agnostic 学习的出现正是为了在“不存在完美分类器”的现实里仍然给学习算法一个清晰的目标。Agnostic PAC 的定义和上一节写的一样学习算法不需要把误差压到 0它只需要以高概率达到“假设类里最优假设的误差 (\epsilon)”。更直白一点[ L_D(\hat h) \le \inf_{h \in H} L_D(h) \epsilon ]Agnostic 学习的意义是把学习目标从“绝对准确”换成“相对最优”。如果我提前限定了假设类 (H)比如“只能使用线性分类器”那么 Agnostic 学习的目标就是在全体线性分类器里找到一个和最好的线性分类器几乎一样好的模型。它没有承诺你一定赶上贝叶斯误差因为线性分类器可能本身就不如非线性分类器。这里有一个非常容易误解的地方Agnostic 并不是“不做任何假设”或“不需要任何先验”。它依然有两个前提一是样本仍然是独立同分布采样的二是你仍然需要指定一个假设类 (H)。它去掉的只是“存在完美概念且这个概念落在 (H) 里”这个不现实的假设。可以用一个表来对比两者维度经典 PACRealizableAgnostic PAC数据生成方式存在目标概念 (c)且 (c \in H)任意分布不需要存在完美分类器学习目标误差接近 0误差接近假设类里最优假设训练误差参考值训练误差趋向 0训练误差趋向下面的“地板”样本复杂度0-1 损失VC 维为 (d)(\Theta((d \log(1/\delta))/\epsilon))(\Theta((d \log(1/\delta))/\epsilon^2))更贴近的现实场景理想化教科书问题真实工业数据、带噪声标签、特征重叠为什么 Agnostic 的样本复杂度明显更高直觉上在 Realizable 设定里训练误差一旦为 0你就有很强的信心认为模型已经学到了正确的规律而在 Agnostic 设定里训练误差永远不可能为 0你只能估计“最优误差大概是多少”。用统计学的语言说估计一个非零的均值比估计一个零均值要困难方差项无法消除所以需要更多样本。从工程视角看Agnostic 框架更值得信赖。它不依赖“数据必须是干净完美”的运气而是让你思考一个更有价值的问题在我能接受的模型复杂度范围内最好的模型能做到多好我现在做的模型距离这个上限还有多远4. ERM最朴素却最强大的不可知学习算法我们知道了 Agnostic PAC 的学习目标接下来问题是什么算法能实现这个目标最自然的答案是经验风险最小化Empirical Risk Minimization, ERM。ERM 的做法极其简单在假设类 (H) 里挑出训练集上误差最小的那个假设[ \hat h \arg\min_{h \in H} L_S(h) ]工程上你每天都在用 ERM只是没意识到。逻辑回归训练是在线性假设类里最小化对数损失决策树的 CART 算法是在树空间里做贪心的结构风险最小化神经网络用梯度下降找损失较小的参数本质上也接近 ERM 的一种近似实现。ERM 的合理性来自一个核心数学工具一致收敛Uniform Convergence。它说的是如果假设类 (H) 的复杂度足够受限那么在大样本下所有假设的经验误差都会以高概率接近自己的真实误差。把所有“经验误差”和“真实误差”的差距统一控制住再取最小值就能得到[ L_D(\hat h) \le \inf_{h \in H} L_D(h) \epsilon ]控制假设类复杂度的经典指标是VC 维。VC 维衡量的是一个假设类最多能“打散”多少个数据点。VC 维越大假设类的表达能力越强但样本需求也越高。在 0-1 损失、VC 维为 (d) 的 Agnostic PAC 框架下ERM 的样本复杂度满足[ m O\left(\frac{d \log(1/\delta)}{\epsilon^2}\right) ]读者不要被这个式子吓到。它的含义非常直白模型越复杂(d) 越大对误差要求越高(\epsilon) 越小对置信度要求越高(\delta) 越小需要的样本就越多而且误差要求对样本量的影响是平方级的。如果想把误差减半样本量大约要变成原来的 4 倍。这也是为什么在真实项目里模型越复杂越容易在小数据集上产生严重的过拟合。理论上早就给出了明确的警告。5. “最优”的精确含义样本复杂度下界现在终于轮到标题里最重要的词Optimal。在机器学习理论里“最优”这个词需要被严格定义。它不是“运行速度最快”也不是“实现最简单”而是指样本复杂度达到理论下界。也就是说任何一个算法想在任意数据分布上都达到同样的误差保证至少需要这么多样本而某个算法恰好达到了这个量级它就是一个最优算法。这种论证方式叫Minimax 下界。它考虑的是一个“最坏分布”就算学习算法知道所有信息只要样本数量不足某个阈值就一定有某种数据分布让算法失败。因此任何算法都无法绕过这个样本量瓶颈。在 0-1 损失的 Agnostic PAC 学习中公认的下界是[ m \Omega\left(\frac{d}{\epsilon^2}\right) ]这个结果和我们上一节提到的 ERM 上界在 (\epsilon) 和 (d) 的主导阶上完全一致。因此可以得出一个很强的结论对于很多有限 VC 维假设类来说ERM 本身就是一个最优的 Agnostic PAC 算法。看到这里你可能会觉得既然如此那标题里的 “An Optimal Agnostic PAC Algorithm” 还有什么可研究的价值这里的关键在于ERM 并不是唯一的候选甚至不一定是最容易分析或最重要的候选。“最优”可以发生在不同层次样本复杂度常数量级最优。算法对假设类的结构要求更低比如一些无限类。算法在“可实现”realizable和“不可知”agnostic两种设置下同时达到最优不需要提前知道当前任务属于哪一种。算法不依赖额外参数不用设计者根据数据分布微调。所以An Optimal Agnostic PAC Algorithm这类标题通常意味着研究者完成了一件更精细的事给出一个统一的、参数几乎不用调的算法并在理论上证明它的样本复杂度达到下界。这个结果的价值不是“造出一个更好用的新模型”而是从信息论意义上证明达到某种学习目标最少需要多少数据以及哪一种算法能够实现它。理解“最优”这个概念对工程判断也有直接帮助。如果你发现在某个小数据集上任何模型都很难把验证集误差压到某个值以下再去想“是不是模型不够强、训练不够久”之前先问一个问题在这个特征集和标签噪声水平下理论上限是多少很可能你离理论上限已经很近继续堆模型复杂度只会增加样本需求而不是降低误差。6. 用 Python 可视化不可知 PAC 行为纯文字讲理论很容易飘。这一节我们写一点代码把上面几个核心概念落地。6.1 环境与实验设计实验使用 Python 3.8 及以上版本依赖numpy和scikit-learn。如果没有安装可以先执行pip install numpy scikit-learn我们将做两个实验在阈值分类器假设类上做 ERM模拟 Agnostic PAC 的“成功率随样本量变化”曲线。在一个人为生成的带噪声二分类任务上用逻辑回归逼近贝叶斯误差观察“最优差距”。6.2 代码一阈值分类器的 ERM 与 PAC 模拟阈值分类器是所有假设里最容易理解的一种给定一个阈值 (\theta)当 (x \ge \theta) 时预测为正类否则为负类。这个假设类的 VC 维是 1因为一个阈值最多只能打散 2 个点。# pac_demo.py import numpy as np def threshold_erm(x, y): 在阈值分类器集合 {1[x theta] : theta in [0, 1]} 上做经验风险最小化 candidates np.sort(np.unique(np.concatenate([[0.0], x, [1.0]]))) best_theta, best_err