Proper 与 Improper 学习

定义 ​

给定比较类 $\mathcal{H}$，proper learner 总输出 $A(S)\in \mathcal{H}$。Improper learner 可输出更大类 ${\mathcal{H}}^{\prime }$ 中的规则，但评价仍相对 $\underset{h\in \mathcal{H}}{inf}R(h)$。若基准也换成 ${\mathcal{H}}^{\prime }$，讨论的已是另一个问题。

设 $\mathcal{H}$ 是决策树桩。Boosting 输出

$$H(x)=\mathrm{sign}\sum _{t=1}^T{\alpha }_t{h}_t(x),h_t\in \mathcal{H},$$

加权投票通常不是单个树桩，所以相对树桩类是 improper，却仍可与最好树桩比较。相对所有有限树桩集成，它又可能是 proper；术语始终依赖参照类。

统计与计算影响 ​

放宽输出可改善最优样本界，也可能绕开类内经验优化困难。它不自动保证高效：任意函数若没有有限表示，无法存储或在新输入上求值。高效学习还要求输出表示和评价时间为多项式。

Improper 不是“错误输出”，proper 也不表示更准确。二者只描述输出约束。结论若不同时写清比较类与输出类，便无法判断样本复杂度和计算要求究竟约束了谁。

另一个可核对的例子来自区间。若比较类是实线单区间指示函数，输出两个区间的并便是 improper，即使它在当前样本上更准确。若定理保证其风险不超过最好单区间加 $\epsilon$，输出仍完成了原比较任务；但部署系统若只接受两个端点，四端点表示就违反外部格式约束。Properness 因而可能是产品接口或可解释性要求，而不只是证明术语。

放宽输出类还改变“存在最优者”的问题。比较基准可以是 $\underset{h\in \mathcal{H}}{inf}R(h)$，即便最优值不在 $\mathcal{H}$ 中达到；improper learner 也不能据此声称超过了一个不存在的具体 $h^{\ast }$. 风险保证应继续使用下确界，输出表示和评价成本则单独验证。

Properness 也不等于一致性。Proper learner 可以返回类内但训练错误非最小的规则；improper learner 可以输出零训练错误的类外规则。前者描述输出归属，后者描述经验约束，两条轴互不推出。

在可实现目标类 $\mathcal{C}$ 与输出假设类 $\mathcal{H}$ 分开的经典记号中，还可能要求 $\mathcal{C}\subseteq \mathcal{H}$。若输出类不含目标表示，却仍能以另一种函数表示相同输入—输出映射，函数层面是否 proper 要按规范类定义，不能只比较语法。

参考资料

• Steve Hanneke, “The Optimal Sample Complexity of PAC Learning,” 2016.
• Shalev-Shwartz, Ben-David, Understanding Machine Learning, 2014.