高效 PAC 学习

资源参数 ​

高效 PAC 学习要求样本数和运行时间对输入维度或目标表示长度 $n$、$1/\epsilon$、$\log \left(1/\delta \right)$ 为多项式。输出假设还须有多项式长度，并能在新输入上高效评价；否则“训练结束”没有形成可用算法。

实线阈值可排序扫描，在多项式时间返回 proper ERM。相反，有限 VC 维只控制信息量：它可保证某个信息论学习器存在，却不保证一致假设搜索、经验优化或输出表示高效。

定义必须注明计算模型。离散输入通常用 Turing/位复杂度；实值模型若把任意精度实数运算视为一步，会隐藏编码长度。Proper 与 improper 效率也可能不同，后者可用更易优化的表示绕过类内搜索。

样本复杂度多项式而运行时间指数的算法仍是 PAC 可学，但不是高效 PAC。反过来，训练程序运行快却没有统一风险保证，也不能仅凭工程速度称为高效可学习。

设输入是 $n$ 位布尔向量。枚举全部 $2^n$ 个候选合取式或真值表，即使只需 $O(n/\epsilon )$ 个样本，运行时间仍可能指数；这展示了统计高效不等于计算高效。阈值类则可排序 $m$ 个实数并扫描，时间 $O(m\log m)$，输出一个阈值即可在 $O(1)$ 次比较内预测。

“多项式于 $1/\epsilon$”也排除了把所需精度按二进制位数误读。若输入直接给容差的二进制编码长度 $k=\log \left(1/\epsilon \right)$，多项式于 $1/\epsilon =2^k$ 对编码长度仍是指数；计算学习理论通常有意采用精度参数的数值倒数作为资源尺度。实数参数还需说明所需位精度，否则单位成本实数运算可能藏起巨大表示。

学习器还必须读得完自己的样本，所以运行时间至少与输入编码总长度同阶。若每个样本含 $n$ 位，声称时间只依赖 $\log m$ 却未说明随机访问或查询模型，通常连全部标签都没有读取。查询学习可以只访问部分数据，但这时资源应明确叫查询复杂度，而非普通 RAM/Turing 运行时间。

效率结论也应保留表示选择。DNF、决策树或线性阈值的“规模 $n$”含义不同；目标概念最短表示很小，不保证学习器知道这份表示。没有输入维度、目标表示长度和输出编码三项，单写 poly 无法被检验。

参考资料

• Leslie Valiant, 1984.
• Kearns, Vazirani, An Introduction to Computational Learning Theory, 1994.