不可知 PAC 可学习性

形式目标 ​

假设类 $\mathcal{H}$ 不可知 PAC 可学习，若存在算法和有限样本函数，使对任意允许分布 $D$，

$$\text{Pr}(R_D(A(S))\le \underset{h\in \mathcal{H}}{inf}{R}_D(h)+\epsilon )\ge 1-\delta .$$

基准是类内最优风险，不是随机猜测的 $1/2$，$\epsilon$ 是超额风险而非绝对错误率。数据仍通常 IID；“agnostic”只移除存在类内零风险目标的假设。

对 $[0,1]$ 有界损失，有限类的典型样本量是 $O((\log |\mathcal{H}|+\log \left(1/\delta \right))/{\epsilon }^2)$，因为要双边估计风险。可实现一致学习只需排除错误超过 $\epsilon$ 的假设，常得到 $1/\epsilon$，两种速率不能换用。

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

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

再对 $h$ 取下确界即可。有限类用 Hoeffding 和并集界让该好事件成立，平方精度由双边均值估计产生。

设比较类只有“总预测 0”和“总预测 1”，真实正类率为 $0.6$。类内最好风险是 $0.4$，不可知目标要求接近 $0.4$，不是达到接近零，也不是仅好于随机猜测。输出更复杂的概率规则可以是 improper，但基准仍须明确为这两个常量规则。

与 PAC 的关系 ​

不可知保证应用到可实现分布时也给 PAC 保证，因此更强；反向需额外结构。Improper 输出仍可与 $\mathcal{H}$ 比。若损失无界或不可积，样本复杂度还需尾部条件，不能仅凭类的 VC 维套用有界损失结论。

参考资料

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