Agnostic PAC学习最优算法：Python模拟样本划分与模型选择

这次我们不聊能跑的 WebUI也不聊模型推理的显存占用而是回到机器学习的底层问题在 Agnostic PAC 学习框架下算法要怎样设计才算“最优”这类问题在论文里看起来很抽象但如果用 Python 把它实现出来跑一组模拟实验你会发现它和平时说的“过拟合、模型选择、训练集划分”直接相关。先给结论这篇文章讨论的是一个面向 Agnostic PAC 学习的理论算法方向。它的核心目标不是给你一个“开箱即用”的工具而是给出样本复杂度层面的最优构造思路。文章会从 PAC 的背景开始把“最优”拆成“率最优”和“常数最优”两层再给出一套可运行的 Python 模拟实现最后用实验数据说明它和普通 ERM 的区别。如果你关心小样本下的模型选择、理论算法的落地验证或者想搞懂论文里“minimax 最优”到底意味着什么这篇文章可以收藏。1. 核心能力速览能力项说明算法类型统计学习理论中的 Agnostic PAC 学习算法目标设定数据分布未知且不假设标签由某个假设确定学习误差尽可能逼近假设类内的最优误差样本复杂度依赖假设类复杂度有限假设类下典型为 O(log|H| / ε²)最优性含义分为 minimax 率最优与常数最优文章主要讨论如何通过独立样本划分与候选集选择逼近最优运行方式Python 数值模拟不需要 GPU不依赖特殊硬件接口能力可封装为离线学习函数不适合直接做实时在线 API批量任务可在多个数据集、多个假设类、多组随机种子下批量重复实验适用场景理论验证、模型选择逻辑研究、小样本学习分析、主动学习前置研究从实用角度看它不是一个“装好就出图”的工程工具而是一个可以写进论文、也可以用来解释模型选择现象的算法思路。下面把背景、算法、实现和实验一次讲清楚。2. PAC 学习与 Agnostic 学习背景PACProbably Approximately Correct学习最早由 Valiant 提出。它的核心问题是给定一个假设类 H给定样本规模 m算法能否以高概率返回一个误差足够小的假设用数学语言描述就是对任意数据分布 D任意假设类 H任意误差阈值 ε任意置信度 δ算法需要满足至少以 1 - δ 的概率成立最终假设 h 的泛化误差 L_D(h) 不超过假设类内最优误差加上 ε。标准的 PAC 设定有一个前提真实标签确实由某个 h* ∈ H 生成。也就是说数据本身“可分”。但现实中绝大多数数据集都不是如此。你无法保证“一条决策边界就能解释所有标签”于是就有了 Agnostic PAC 学习。Agnostic 的意思是“不可知的”。在 Agnostic PAC 框架下我们不再假设 h* 存在只要求[ L_D(\hat h) \le \inf_{h \in H} L_D(h) \epsilon ]这里 inf 表示假设类 H 里能做到的最优误差。换句话说我们不要求模型完美拟合数据只要求它尽可能逼近 H 能达到的下界。这个改动的意义非常大。它直接对应工程里的常见情况标签中存在噪声特征无法完全区分类别模型容量不足以覆盖真实规律。此时学习算法就不只是在“拟合函数”而是在“在给定假设类内做近似最小化”。最朴素的做法叫做 ERM经验风险最小化[ \hat h \arg\min_{h \in H} \frac{1}{m} \sum_{i1}^{m} \ell(h(x_i), y_i) ]ERM 在统计上已经被证明是 Agnostic PAC 可学习的。对于有限假设类它可以达到[ m \ge O\left(\frac{\log |H| \log(1/\delta)}{\epsilon^2}\right) ]这也是大多数教材里的标准结果。但问题是这个界里的常数离“最优”还有距离。如果只追求“能学”ERM 够用如果追求“样本效率最优”就需要更精细的构造。3. 算法思想与最优性定义要理解“最优 Agnostic PAC 算法”首先要定义什么叫“最优”。这里有两个层次。3.1 率最优率最优指的是样本复杂度的增长速度达到理论下限。在有限假设类下要求的样本量 m 随 1/ε² 增长又随 log|H| 增长这两个数量级都是无法避免的。ERM 已经达到了这个数量级所以它是率最优的。3.2 常数最优更难的是常数最优。比如同样都是 O(log|H| / ε²)前面的常数是 2 还是 1在小样本场景下差别很大。常数最优要求在固定误差 ε 和置信度 δ 时样本复杂度尽量逼近 minimax 下界。已知的一个关键现象是如果把训练和选择混在一起ERM 的误差上界会有额外的方差项而通过把样本切成两份一份用来训练一份用来做独立验证可以改善常数。这种独立验证策略在参数估计里叫 “sample splitting”在统计学习里有时也叫 “sub-sampling”。它的思想非常简单训练误差会过拟合但如果候选假设的数量有限那么用独立样本评估候选误差就能通过 union bound 同时控制所有候选假设的偏差。这个策略带来的提升在小样本下非常明显。3.3 为什么随机化也有帮助针对常数最优另一个常用技巧是随机化选择。传统 ERM 固定选训练误差最小的那个假设但这在有限样本下可能“碰巧”选中一个在训练集上表现好、在分布上表现差的假设。随机化算法会以一定概率接受那些训练误差略高的假设用验证集的评估结果来纠偏。这个思路在后来的在线学习、bandit、模型选择中都有类似体现。简单说最优 Agnostic PAC 算法并不只是“最小化训练误差”而是在“假设复杂度”和“样本信息”之间做更精细的权衡。4. 算法形式化描述这里给出一个容易落地实现的算法版本。它基于“样本划分 候选集评估”适合有限假设类也容易扩展到结构化假设类。算法输入样本集 S {(x₁,y₁), ..., (xₘ,yₘ)}假设类 H {h₁, ..., h_N}训练比例 α通常取 0.5 或 0.6置信度参数 δ误差上界参数 ε。算法步骤将样本集 S 随机划分为 S_train 和 S_val比例分别为 α 和 1 - α。在 S_train 上计算每个假设 h 的经验误差。[ \hat L_{train}(h) \frac{1}{|S_{train}|} \sum_{(x,y) \in S_{train}} \ell(h(x), y) ]在 S_val 上计算每个假设 h 的验证误差。[ \hat L_{val}(h) \frac{1}{|S_{val}|} \sum_{(x,y) \in S_{val}} \ell(h(x), y) ]引入复杂度正则项。对有限假设类可以用[ \text{penalty}(h) \sqrt{\frac{\log(1/\delta) \log N}{2 |S_{val}|}} ]综合评分[ \text{score}(h) \hat L_{val}(h) \text{penalty}(h) ]输出 score 最小的假设。这个算法和纯 ERM 的区别在于决策使用独立验证集而不是训练集。它可以有效避免训练阶段过拟合带来的选择偏差。在实现上它比 ERM 多一次样本划分和一次验证集计算但逻辑更接近工程里“训练集 验证集”的标准做法。5. Python 实现一个可运行的 Agnostic PAC 模拟下面给出一套完整实现。为了让读者能直接跑起来我使用 numpy 手工构造数据不依赖深度学习框架。环境只需要 Python 3.9 和 numpy。5.1 环境准备python -m venv pac_env source pac_env/bin/activate # Windows 下为 pac_env\Scripts\activate pip install numpy matplotlib这里不需要 CUDA不需要 GPU也不需要安装 PyTorch。整个模拟在 CPU 上可以在几秒内完成。5.2 构造 Agnostic 数据集构造一个一维二分类问题。真实分布使用[ y^* \mathbb{I}(x 0.5) ]但标签以 0.25 的概率翻转。这样数据不是严格可分的任何阈值分类器都无法做到零误差因此这是一个标准的 Agnostic 设定。import numpy as np def make_agnostic_data(n_samples, noise0.25, seed0): rng np.random.default_rng(seed) X rng.uniform(0, 1, sizen_samples) y_star (X 0.5).astype(int) flip rng.uniform(0, 1, sizen_samples) noise y np.where(flip, 1 - y_star, y_star) return X, y5.3 定义有限假设类使用阈值分类器集合[ H { h_t(x) \mathbb{I}(x t) \mid t \in {0.1, 0.2, ..., 0.9} } ]这是一个规模很小的有限假设类方便可视化也方便快速算出最优结果。class ThresholdHypothesis: def __init__(self, threshold): self.threshold threshold def predict(self, X): return (X self.threshold).astype(int) def make_hypothesis_space(): thresholds np.arange(0.1, 1.0, 0.1) return [ThresholdHypothesis(t) for t in thresholds]5.4 实现 ERM 与 Split-PAC 算法先实现误差计算函数。def zero_one_loss(h, X, y): pred h.predict(X) return np.mean(pred ! y) def train_val_split(X, y, train_ratio0.5, seed0): rng np.random.default_rng(seed) n len(X) indices rng.permutation(n) n_train int(n * train_ratio) train_idx indices[:n_train] val_idx indices[n_train:] return X[train_idx], y[train_idx], X[val_idx], y[val_idx]然后实现两个算法。第一个是纯 ERMdef erm_learner(X, y, H): best_h None best_err float(inf) for h in H: err zero_one_loss(h, X, y) if err best_err: best_err err best_h h return best_h, best_err第二个是样本划分后的 Agnostic PAC 算法def agnostic_pac_learner(X, y, H, train_ratio0.5, delta0.1, seed0): X_train, y_train, X_val, y_val train_val_split(X, y, train_ratio, seed) train_errors [] val_errors [] for h in H: train_errors.append(zero_one_loss(h, X_train, y_train)) val_errors.append(zero_one_loss(h, X_val, y_val)) train_errors np.array(train_errors) val_errors np.array(val_errors) N len(H) m_val len(X_val) penalty np.sqrt((np.log(1.0 / delta) np.log(N)) / (2.0 * m_val)) scores val_errors penalty best_idx int(np.argmin(scores)) return H[best_idx], scores[best_idx]这个实现完全对应第 4 节的算法描述。penalty 项来自 union bound 对有限假设类验证误差的修正样本量越小penalty 越大。5.5 主程序对比两种算法写一个主程序在不同样本量下比较 ERM 和 Split-PAC 的泛化误差。def evaluate_hypothesis(h, n_eval100000, noise0.25, seed1): X_eval, y_eval make_agnostic_data(n_eval, noise, seed) return zero_one_loss(h, X_eval, y_eval) def main(): H make_hypothesis_space() sample_sizes [50, 100, 200, 400, 800, 1600] results [] for n in sample_sizes: X, y make_agnostic_data(n, seed42) h_erm, _ erm_learner(X, y, H) h_pac, _ agnostic_pac_learner(X, y, H, train_ratio0.5, delta0.1, seed42) erm_err evaluate_hypothesis(h_erm) pac_err evaluate_hypothesis(h_pac) results.append((n, erm_err, pac_err)) print(fn{n:5d} | ERM err{erm_err:.4f} | PAC err{pac_err:.4f}) if __name__ __main__: main()运行后每行会输出一个样本量下两个算法的近似泛化误差。由于每个算法只跑一次单次结果会有波动更严谨的做法是重复多次取平均值。下一节会做这件事。6. 功能测试与效果验证6.1 判断标准对 Agnostic PAC 学习算法判断成功的标准有两个泛化误差是否接近假设类内的最优误差在相同样本量下是否比 ERM 更稳定、更少出现过拟合。在这个模拟里最优阈值大约是 t 0.5。由于噪声为 0.25贝叶斯最优误差约为 0.25。任何算法都不可能低于这个值。6.2 批量重复实验单次实验随机性太大应该做重复实验。下面这个函数跑 200 次统计平均误差和中位误差。def repeated_experiment(n_samples, n_repeats200, noise0.25): erm_errors [] pac_errors [] H make_hypothesis_space() for seed in range(n_repeats): X, y make_agnostic_data(n_samples, noise, seedseed) h_erm, _ erm_learner(X, y, H) h_pac, _ agnostic_pac_learner(X, y, H, train_ratio0.5, delta0.1, seedseed) erm_errors.append(evaluate_hypothesis(h_erm, seedseed)) pac_errors.append(evaluate_hypothesis(h_pac, seedseed)) return { erm_mean: float(np.mean(erm_errors)), erm_median: float(np.median(erm_errors)), pac_mean: float(np.mean(pac_errors)), pac_median: float(np.median(pac_errors)), } if __name__ __main__: for n in [50, 100, 200, 400]: print(n, repeated_experiment(n))这个输出会显示一个常见现象当样本量比较小时纯 ERM 的均值偏高因为它在训练集上选择的阈值可能偏离真实边界Split-PAC 算法因为有独立验证集修正误差更稳定。6.3 预期结果解读在小样本下Split-PAC 的优势通常体现在中位数误差上。当样本量变大时两者的误差都会趋向贝叶斯最优的 0.25差距逐渐缩小。这说明样本划分策略在小样本、高噪声环境下收益最明显。需要注意不同随机种子下单次实验波动可能很大。更可靠的验证方式是增加重复次数或者把样本量范围拉大。这种吞吐量测试本身也属于批量实验的一种适合用来理解算法的稳定性。7. 性能分析与计算开销观察7.1 时间复杂度假设假设类大小为 N样本量为 m简单实现的计算开销是训练误差计算O(Nm)验证误差计算O(Nm)排序或扫描选择O(N)。ERM 只需要前两项中的训练部分Split-PAC 需要训练加验证整体多出约一倍的误差计算。在假设类很大时比如 N 10000m 1000这个开销是千万级别仍然可以在 CPU 秒级完成。7.2 空间复杂度两个算法都只需要保存每个假设的误差标量空间复杂度为 O(N)。不会因为样本量增大而显著增加内存。7.3 如何降低计算成本如果假设类规模太大可以先用训练误差筛选出 top-K 候选再在验证集上精确评估。如果单个假设训练成本高比如每个假设是一个神经网络可以把“假设类”理解为超参数搜索空间用随机搜索代替全枚举。如果样本量很大可以降低验证集比例而不是固定 0.5。7.4 与普通 GPU 推理项目的差异这类算法不依赖显存也没有显存占用观察的必要。它的“资源占用”主要体现在 CPU 计算时间和内存上。运行时间受假设类大小和样本量的线性影响和分辨率、batch size 的概念完全不同。8. 常见问题与排查方法问题现象可能原因排查方式解决方案小样本下算法结果不稳定单次实验随机性太强增加重复次数用均值或中位数比较重复 200 次以上再做结论Split-PAC 比 ERM 误差还高验证集比例设置不合理检查验证集样本量是否过小调整 train_ratio 为 0.6 或 0.7penalty 项过大导致总是选复杂度低的假设假设类很大但验证集很小检查 m_val 的数量级增大样本量或降低 delta训练误差为 0验证误差很高过拟合对比训练误差和验证误差使用验证集选择或增加正则项通过网格搜索得到的阈值只有整数几个不精确阈值网格过粗打印候选阈值列表在假设类中增加更细的阈值标签噪声比例过高所有算法误差都接近 0.5数据本身几乎不可学计算贝叶斯最优误差降低噪声比例或重新构造数据运行时间过长N 或 m 过大统计候选假设数量和样本数量使用 top-K 预筛或随机搜索多次运行结果完全一致随机种子固定检查代码中是否固定 seed需要更严谨实验时换不同 seed9. 最佳实践与使用建议9.1 第一次先跑小规模基线建议先用非常小的假设类比如 9 个阈值分类器跑通整条链路后再扩大。这样能快速验证代码逻辑也不会被随机波动带偏。9.2 把“假设类”当作模型选择的抽象这个算法的意义不只是理论。在日常训练中“假设类”可以理解为一个模型配置空间。比如你有一组超参数组合每个组合对应一个候选模型。Split-PAC 的思路对应实际工作中的“训练集 验证集 模型选择”区别只是理论上会给出显式的 penalty。9.3 样本划分比例要结合数据量判断当样本量只有几十时分出一半做验证会让训练数据太少反而可能性能变差。此时更稳妥的做法是提高 train_ratio或者使用交叉验证。交叉验证会增加计算量但在小样本下更稳定。9.4 批量实验要固定随机种子如果你要比较多个算法的好坏固定同一组随机种子让它们面对相同的数据划分和相同的数据扰动。这样可以消除一部分方差。9.5 将结果保存为可复现格式建议每次实验都保存以下内容样本量假设类规模train_ratiodelta随机种子每个算法的最终误差。用 CSV 或 JSON 记录方便后续画图和复盘。9.6 边界与合规提醒这篇文章里的模拟完全使用合成数据不涉及真实用户信息、隐私数据或受版权保护的数据。如果在实际业务中把类似逻辑用于真实数据需要注意数据授权、隐私保护和模型发布前的效果复核。涉及人脸、声音、文字作品等数据时必须确认是否有合法授权。10. 总结与下一步这个方向最值得尝试的点是把一个看起来很理论的 Agnostic PAC 最优性问题变成一个可以直接运行的 Python 实验。你不必完全复现论文里的复杂构造只需要实现最简单的样本划分版本就能观察到 ERM 在小样本高噪声场景下的不稳定也能理解为什么独立验证集对模型选择如此重要。建议你先跑通第 5 节的代码分别试试样本量为 50 和 500 时的表现再手动调整 noise 参数观察变化。最容易踩的坑是忽略随机波动单次实验结果没有说服力必须做重复实验看均值和中位数。后续可以扩展的方向包括把阈值分类器换成决策树或线性模型观察假设类复杂度对样本需求的影响把二分类换成多分类验证 union bound 适应性把离线批量实验改成在线学习流程观察逐步到来的样本如何影响模型选择引入交叉验证替代固定比例划分比较两者的稳定性和计算成本。把这些扩展做完你对 PAC 学习、模型选择和小样本学习的理解会比只看论文提高一大截。建议收藏备用后续做实验时可以照着这套流程直接改。