可实现与不可知学习

两种设定 ​

二分类分布对 $\mathcal{H}$ 可实现，若存在 $h^{\ast }\in \mathcal{H}$ 使 $R(h^{\ast })=0$。例如标签恰由某个实线阈值产生。有限样本上找到零训练误差规则只叫“一致”，并不证明分布可实现：丰富类也能偶然拟合含噪样本。

不可知设定移除零风险假设，目标改为

$$R(A(S))\le \underset{h\in \mathcal{H}}{inf}R(h)+\epsilon .$$

它并非“完全无假设”：IID、固定损失、比较类和概率目标仍在。对平方回归等一般损失，零风险本就不自然，类内超额风险才是稳定表述。

噪声与错设不是一回事 ​

若 Bayes 风险为零但类不含 Bayes 规则，问题对 $\mathcal{H}$ 仍不可实现，这是模型错设。若类含 Bayes 规则而标签内在随机，Bayes 风险也可为正。两者都进入不可知比较，却有不同来源。分类噪声模型公理库分类噪声模型Classification noise model · Random classification noise类内真概念的标签以固定且独立的小于二分之一概率翻转。则在可实现真概念之上规定结构化翻转，位于两端之间。

可实现性也不承诺能计算出一致规则。PAC公理库PAC 可学习性PAC learnability · Probably Approximately Correct learning在可实现设定中，以有限样本和高概率达到任意小总体错误的可学习性。加入样本与概率量词；高效 PAC 再要求多项式时间。存在、统计可学和计算可解是三层问题。

设 $X\in \{1,2,3,4\}$ 均匀，阈值类规定 $h_a(x)={\mathbf{1}}_{\{x\ge a\}}$。标签 $0,0,1,1$ 由 $a=3$ 完全实现；标签 $0,1,0,1$ 则不由任何单阈值实现，即使标签是确定的、Bayes 风险为零，类内最优仍至少错一个点，风险为 $1/4$。这把“标签有噪声”和“类选错了”清楚分开。

一般损失下，“存在零经验损失规则”也可能没有稳定意义。对连续噪声回归，有限样本可被高次插值多项式逐点穿过，平方训练损失为零，但总体风险未必接近类内最优。不可知目标比较真实风险而非是否插值，正是为了容纳噪声、错设和有限样本偶合。

两种设定对应不同证明信息。可实现一致分类知道类内最优经验与总体风险都为零，可只控制坏规则“幸存”的单侧事件；不可知学习不知道最优经验值，需要比较两个带噪风险并通常做双侧估计。这正是有限类样本率从 $1/\epsilon$ 变为 $1/{\epsilon }^2$ 的来源之一。

结构化噪声模型不会简单落在二选一标签中。Classification noise 仍有隐藏的类内真概念，但观测风险最低值为 $\eta >0$；从零风险定义看它不可实现，从可恢复结构看又强于完全不可知。使用哪个定理必须跟随观测分布的形式条件。

参考资料

• Kearns, Vazirani, An Introduction to Computational Learning Theory, 1994.
• Shalev-Shwartz, Ben-David, Understanding Machine Learning, Chs. 2–3.