学习困难性的归约

为什么普通 many-one 图像不够 ​

判定问题归约通常把一个输入映成另一个输入；学习算法接收的却是来自未知分布的随机样本，并只承诺低预测误差和一定成功概率。证明学习困难，必须说明如何高效生成 learner 看到的样本、怎样把低风险输出译回源问题答案，以及小风险为何足以跨过判定 gap。

一个归约模板 ​

从源实例 $x$ 出发，归约应在多项式时间内完成四件事：

1. 构造目标类中可多项式表示的概念或标注机制；
2. 模拟允许分布 $D_x$ 的 IID 样本 oracle，且每个样本可高效生成；
3. 调用假设中的高效 learner，以精度 $\epsilon$、置信度 $1-\delta$ 得到可求值预测器；
4. 用该预测器或其风险差恢复源答案，并证明 YES/NO 情形至少相隔可检测 gap。

总运行时间还要包含 learner 的样本数、输出表示和求值成本。若 learner 随机，归约的成功概率可用独立重复放大，但每次运行与最终判决规则必须可实现。

分布与误差 gap ​

设 YES 实例产生某种可学习标注结构，而 NO 实例保证任何允许输出在 $D_x$ 下风险至少高出 $g$。选择 $\epsilon <g/3$ 并能用独立验证样本估计风险到 $g/3$，才可把 learner 的保证变成判定。若难点只落在 $D_x$ 的指数小概率区域，常数风险保证看不见它；若 $D_x$ 本身不可高效采样，归约也没有给真实 learner 输入。

SAT 到 proper 学习的具体模板 ​

给定含 $m$ 个子句的 CNF 公式 $\mathrm{\Phi }$，把实例空间取为这些子句，令每个赋值 $a$ 表示一个假设

$$h_a(C)=\mathbf{1}\{a\text{ 满足子句 }C\}.$$

在 $\mathrm{\Phi }$ 可满足时，取一个满足赋值作目标概念，并让 $D_{\mathrm{\Phi }}$ 在 $m$ 个子句上均匀分布；归约能高效抽取随机子句及其标签 $1$。假设存在输出仍属于 $\{h_a\}$ 的高效 proper learner，以精度 $\epsilon <1/m$ 学习这批全正样本，那么低于 $1/m$ 的总体错误率迫使它在每个子句上都输出 $1$，对应的赋值就是 $\mathrm{\Phi }$ 的满足见证。公式不可满足时，没有 proper 输出能通过逐子句验证。因此这样的 learner 会给出 SAT 的随机化多项式时间求解路径，困难性结论须明确写成相应的复杂度假设，例如 $\mathrm{NP}⊈\mathrm{RP}$。

这个构造同时暴露表示与输出类为何不能省略。若允许完全 unrestricted 的 improper learner，常数函数 $h(C)\equiv 1$ 对该分布零错误，却不编码任何共同满足所有子句的赋值；归约随即失效。要排除 improper learner，必须另造能从任意低风险输出解码见证的表示保持归约，而不是把 ERM 或 proper 困难性换个标题。

关键辨析 ​

证明某类 ERM 是 NP-hard，只排除了“精确求这个经验最优”的路径。improper learner 可能输出类外预测器，近似或非 ERM 算法也可能绕开该优化问题，所以不能据此直接宣布该类不可高效 PAC 学习。反过来，密码学困难性常依平均情形或伪随机假设，必须明确复杂度假设，不能模糊写成“除非 P=NP”。

多项式时间归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。提供复杂度传递语言；本页增加学习专有的分布接口、风险量词和表示约束。统计与计算复杂度公理库学习的统计复杂度与计算复杂度Statistical-computational complexity of learning分开衡量数据量、求解代价和输出表示，避免把统计可学误读为计算可解。的分离正是这些归约要保护的对象。

参考资料

• Michael Kearns, Umesh Vazirani, An Introduction to Computational Learning Theory, MIT Press, 1994.
• Leonard Pitt, Leslie Valiant, Computational Limitations on Learning from Examples, JACM, 1988.