不可知 PAC 可学习性

形式陈述 ​

相对于可实现 PAC公理库PAC 可学习性PAC learnability · Probably Approximately Correct learning在可实现设定中，以有限样本和高概率达到任意小总体错误的可学习性。，不可知设定公理库可实现与不可知学习Realizable learning · Agnostic learning区分类内是否存在零风险解释，以及学习目标是否只是接近类内最优。不再假定类内存在零风险真规则。对固定有界可测损失，非空假设类 $\mathcal{H}$ 不可知 PAC 可学习，若存在同一个学习器 $A$ 和有限样本函数 $m_{\mathcal{H}}$，使对所有 $0<\epsilon ,\delta <1$、所有 $D$、所有 $m\ge m_{\mathcal{H}}(\epsilon ,\delta )$，都有

$${\text{Pr}}_{S\sim D^m,U}(R_D(A(S,U))\le \underset{h\in \mathcal{H}}{inf}{R}_D(h)+\epsilon )\ge 1-\delta .$$

概率来自 IID 样本与独立算法随机性，分布 $D$ 在外层任意。基准是类内最优风险，即超额风险公理库超额风险与误差分解Excess risk · Error decomposition把相对最优决策的风险差拆成逼近、估计和优化来源。的比较点，不是随机猜测的 $1/2$；$\epsilon$ 控制风险差，不是绝对错误率。若输出不要求属于 $\mathcal{H}$，必须声明输出类与可测性，但比较基准仍是 $\underset{h\in \mathcal{H}}{inf}{R}_D(h)$。

对 $[0,1]$ 有界损失和有限类，Hoeffding 与并集界给

$$\text{Pr}(\underset{h\in \mathcal{H}}{sup}|R_D(h)-{\hat{R}}_S(h)|>\alpha )\le 2|\mathcal{H}|e^{-2m{\alpha }^2}.$$

取 $\alpha =\epsilon /2$，只要

$$m\ge \frac{2}{{\epsilon }^2}\log \frac{2|\mathcal{H}|}{\delta },$$

ERM 的类内超额风险就至多 $\epsilon$。可实现一致学习只需排除错误超过 $\epsilon$ 却保持零训练误差的候选，常得到 $1/\epsilon$；两种速率来自不同事件，不能换用。

推导来自 ERM 的比较链。若好事件上 $\underset{h}{sup}|R(h)-\hat{R}(h)|\le \epsilon /2$，则对任意 $h\in \mathcal{H}$，

$$R({\hat{h}}_{\mathrm{ERM}})\le \hat{R}({\hat{h}}_{\mathrm{ERM}})+\epsilon /2\le \hat{R}(h)+\epsilon /2\le R(h)+\epsilon .$$

若下确界未达到，就先取满足 $R(h_{\eta })\le \underset{h}{inf}R(h)+\eta$ 的比较器，再令 $\eta \downarrow 0$。有限类用前述 Hoeffding—并集界让好事件成立，平方精度由双边均值估计产生。

直觉

可实现学习只需排除那些真实错误已经超过容忍度、却碰巧在样本上零错的规则；不可知学习必须比较两个都带采样噪声的风险。因此前者常出现 $1/\epsilon$ 的单侧速率，后者则出现 $1/{\epsilon }^2$ 的均值估计速率。

例子与边界

设比较类只有 $h_0\equiv 0$ 与 $h_1\equiv 1$，真实正类率为 $p=0.6$。在 0–1 损失下

$$R(h_0)=0.6,R(h_1)=0.4,$$

所以类内最优风险是 $0.4$。ERM 根据样本正类比例 $\hat{p}$ 作多数选择；它错误选择 $h_0$ 的事件是 $\hat{p}\le 1/2$。Hoeffding 给

$$\text{Pr}(\hat{p}\le 1/2)\le e^{-2m(0.6-0.5{)}^2}=e^{-0.02m}.$$

例如 $m=150$ 时该上界约为 $e^{-3}<0.05$。错误选择会多付 $0.2$ 风险，因此当所需超额精度小于 $0.2$ 时，成功概率正由这次均值比较控制。目标是接近 $0.4$，不是接近零，也不是口头上的“好于随机猜测”。

与 PAC 的关系 ​

不可知保证应用到类内最优风险为零的分布时也给可实现 PAC 保证，因此覆盖的分布更广；反向结论需统计学习基本定理等附加设定。概念层级上，可实现 PAC 是本页数据模型的特殊情形，所以 special_case_of 边从 PAC 指向本页，而非相反。若损失无界或不可积，样本复杂度还需尾部条件，不能仅凭类的 VC 维套用有界损失结论。

推论与应用

有限类通过双侧集中和并集界得到不可知 PAC 保证；有限 VC 维则由一致收敛与 ERM 推出一般二元类的结论。代理损失学习还需一条校准函数，把代理超额风险转换回目标分类风险。

结构化噪声条件位于可实现与完全不可知之间：它们保留关于 Bayes 边界或隐藏概念的额外信息，因而可能获得更快速率。使用这些结果时必须明确观测风险基准和噪声量词，不能只把数据称作“有噪声”。

参考资料

• David Haussler, “Decision Theoretic Generalizations of the PAC Model,” 1992.
• Shalev-Shwartz, Ben-David, Understanding Machine Learning, 2014.