不可知 PAC 可学习性

形式陈述 ​

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

概率来自 IID 样本与独立算法随机性，分布 $D$ 在外层任意。量词次序是先固定同一个学习器和样本界，再让任意分布接受检验；样本界可以依赖类、损失、精度和置信度，但不能依赖未知的 $D$。允许每个分布分别挑一个已经知道其最优规则的算法，会把学习要求变成空话。基准是类内最优风险，即超额风险理路超额风险与误差分解Excess risk · Error decomposition把相对最优决策的风险差拆成逼近、估计和优化来源。的比较点，不是随机猜测的 $1/2$；$\epsilon$ 控制风险差，不是绝对错误率。若输出不要求属于 $\mathcal{H}$，必须声明输出类与可测性，但比较基准仍是 $\underset{h\in \mathcal{H}}{inf}{R}_D(h)$。

对 $[0,1]$ 有界损失和有限类，Hoeffding 不等式理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。与并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。给

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

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

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

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