Proper 与 Improper 学习

形式陈述

定义

在一个已固定的统计学习问题中，给定比较假设类 $\mathcal H$ ，proper learner 总输出 $A(S)\in\mathcal H$ 。Improper learner 可输出更大类 $\mathcal H'$ 中的规则，但评价仍相对 $\inf_{h\in\mathcal H}R(h)$ 。若基准也换成 $\mathcal H'$ ，讨论的已是另一个问题。

直觉

Properness 描述的是“输出落在哪个类”，不是“输出是否正确”。同一个投票函数相对树桩类可能是 improper，相对树桩集成类却是 proper；术语必须连同比较类和输出类一起使用，离开参照类便没有绝对含义。

例子与边界

树桩投票

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

H(x)=\operatorname{sign}\sum_{t=1}^T\alpha_th_t(x),\quad h_t\in\mathcal H,

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

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

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

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

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

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

推论与应用

放宽输出可改善最优样本界，也可能绕开类内经验优化困难，但它不自动保证高效：任意函数若没有有限表示，无法存储或在新输入上求值。统计复杂度与计算复杂度因此还要单独核对输出编码与评价成本；VC 类样本复杂度界中的最优存在性结论也必须注明是否允许 improper learner。输出约束是统计、计算与部署接口共同使用的一条轴，不能被“更灵活”或“更准确”替代。

参考资料

Steve Hanneke, “The Optimal Sample Complexity of PAC Learning,” Journal of Machine Learning Research 17(38), 2016, pp. 1–15.
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chs. 2 and 6.

形式陈述 ​

定义 ​

树桩投票 ​

反向链接

形式陈述

定义

树桩投票