高效 PAC 学习

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

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

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

在 $d$ 位输入上，单调合取式由所选变量子集确定，共有 $2^d$ 个。固定置信度时，一致学习的样本界是 $O(d/\epsilon )$；逐一枚举这 $2^d$ 个候选却可能耗费指数时间。这只是一个低效实现：从包含全部变量的合取式开始，删除在任一正例上为零的变量，就能在 $O(md)$ 时间内得到一致的单调合取式。因此该类本身高效可学。若改为全部布尔真值表，候选数是 $2^{2^d}$、VC 维是 $2^d$，不能继续沿用前一个样本界。阈值类则可在比较模型中排序并扫描，使用 $O(m\log (m+1))$ 次比较，预测只需一次比较；数值编码与比较的位成本另计。

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

运行时间应包括实际的数据访问、样本生成、假设构造与预测开销。若算法明确完整扫描 $m$ 个各含 $d$ 位的样本，读入成本就是 $\mathrm{\Omega }(md)$；随机访问算法却可能跳过无关坐标或忽略多余样本，所以这不是所有学习器的无条件下界。样本或成员 oracle 的调用次数也不能代替总时间：生成一个长度 $d$ 的查询、处理响应及维护模型都要按所选计算模型计费。

效率结论也应保留表示选择。DNF、决策树或线性阈值的“规模 $n$”含义不同；目标概念最短表示很小，不保证学习器知道这份表示。Proper 与 Improper 学习理路Proper 与 Improper 学习Proper learning · Improper learning区分比较类与学习器实际允许输出的函数类。进一步区分输出类是否受限，统计复杂度与计算复杂度理路学习的统计复杂度与计算复杂度Statistical-computational complexity of learning分开衡量数据量、求解代价和输出表示，避免把统计可学误读为计算可解。则把数据、求解和表示三项放进同一资源账本。没有输入维度、目标表示长度和输出编码三项，单写 poly 无法被检验。