《人工智能》19.5：深度解析PAC学习理论与样本复杂性
19.5 机器学习理论
阅读前导
在熟悉了模型选择、损失函数、正则化及超参数调整等机器学习实践流程后，本节将视角从“如何操作”升华为“为何可行”以及“存在何种根本性制约”。它为之前讨论的所有方法提供了坚实的数学保证和边界界定。
AI导读
1. 探究学习理论的必要性
教材内容
我们如何确信所学的假设能精准预测未观测的数据？即在不知晓目标函数 f 的情况下，如何判断假设 h 是否逼近 f？这一命题历史悠久，奥卡姆、休谟等学者皆有涉猎。近几十年来，新挑战接踵而至：获取优质假设需要多少样本？应选择何种假设空间？若空间复杂，能否找到全局最优还是仅能局部最优？假设的复杂度应如何控制？如何规避过拟合？
观察决策树在餐厅等待问题上的学习曲线（图19-7），增加训练数据能提升准确率。然而，这种提升仅限于特定算法与问题。是否存在普适法则来衡量所需样本量？此类问题统称为计算学习理论，它是AI、统计学与计算机理论的交汇点。
其核心原理在于：少量训练后，高度不匹配的假设将被高概率剔除，因它们会做出错误预测。若假设与足够多样本一致，则极大概率是概率近似正确（PAC）的。
任何能输出概率近似正确假设的算法即称为PAC学习算法。这为各类学习算法提供了性能界限。与所有理论一样，PAC学习基于公理逻辑。其“基础”是19.4节的平稳性假设，即未来样本源自固定分布 P(E)=P(X,Y)。此外，假定真实函数 f 是确定性的且属于假设空间 H。
最基础的PAC定理针对布尔函数，采用0/1损失。此前非正式定义了错误率，此处给出正式定义：从平稳分布提取样本的泛化误差期望。即 error(h) 是假设对新样本分类错误的概率，这与学习曲线测量的量一致。
若假设 error(h)≤ε，则称其为近似正确，ε 为小常数。
我们将证明，存在 N，使得基于 N 个样本训练后，所有一致性假设以高概率近似正确。近似正确假设在空间中“接近”真实函数，位于 f 周围的 ε 球内。球外区域记为 Hbad。
对于严重错误的假设 hb∈Hbad，其与前 N 个样本一致的概率有界。因 error(hb)>ε，与单样本一致概率 ≤ 1-ε。样本独立，与 N 个一致的概率 ≤ (1-ε)^N。
“Hbad 中至少有一个一致性假设”的概率上界为各假设概率之和：P(Hbad含一致性假设) ≤ |Hbad|(1-ε)^N ≤ |H|(1-ε)^N。
设此概率 ≤ δ。利用 1-ε ≤ e^-ε 和大样本数（19-1），可得结论。因此，学习算法在观测足够样本后，以 ≥ 1-δ 概率返回错误率 ≤ ε 的假设。即概率近似正确。所需样本量 N 称为样本复杂性。
若 H 是 n 属性上的所有布尔函数，则 |H|=2^n，样本复杂性为 2^n。因所有可能样例也是 2^n，表明在布尔函数类中 PAC 学习需观测几乎所有样例。
换个角度看：H 假设过多，能区分任意样例。对任意 N 个样例，一致假设集既含预测 xN+1 为正的，也含预测为负的。要获真实泛化，需限制 H，但可能排除真实假设。
避免困境的三种方法：1. 利用先验知识。2. 算法优先返回简单假设（如决策树）。3. 研究布尔函数的可学习子集。方法3假设受限空间含接近 f 的假设，利于泛化和搜索。
PAC学习示例：决策列表学习
现在展示 PAC 学习如何应用于决策列表。决策列表是一系列测试，每个测试是文字的合取。若测试相符，返回指定值；不符则处理下一测试。
决策列表类似决策树但结构更简，仅单向分支。单个测试更复杂。图19-10 展示了代表餐厅等待问题的决策列表。
若测试无大小限制，可表示任意布尔函数。限制测试大小 ≤ k，则算法可从少量样本泛化。记为 k-dl。k-dl 是 k-DT（深度 ≤ k 的决策树）的子集。图19-10 是 2-DL。
首要任务是证明 k-dl 可学习，即合理样本下可精确近似。
需计算假设数量。n 属性且文字 ≤ k 的合取式集记为 Conj(n,k)。决策列表由测试组成，测试结果为 Yes/No/不在列表中。测试数 ≤ 2 * Conj(n,k) - 1。排列顺序不同，故 |K-DL(n)| ≤ Conj(n,k) * ...
计算得出样本数 N 是 n 的多项式。故对较小 k，返回一致列表的算法可在合理样本下 PAC 学习 k-dl。
下一任务是找到有效算法。采用 Decision-List-Learning 贪心算法：反复找与训练集子集一致的测试，加入列表，移除样例，重复直至无样例。图19-11。
算法未规定选择方法。优先选小测试且匹配最多同分类样例是合理选择，使列表紧凑。
最简策略：找与任意同分类子集匹配的最小测试 t。图19-12 显示效果良好。此问题决策树学习更快但波动大，两者准确率均超 90%。
图19-11 学习决策列表的算法；图19-12 餐厅等待问题的学习曲线，对比了决策列表与决策树。