VC 类的样本复杂度界

形式陈述 ​

设二元假设类 $H$ 的 VC 维为 $d\ge 1$，$0<\epsilon <1/8$、$0<\delta <1/100$。在通常可测性条件下，对每个这样的 $H$，存在一个可能 improper 的学习器 $L_H$：对任意可由 $H$ 实现的分布，只要

$$m\ge C\frac{d+\log \left(1/\delta \right)}{\epsilon },$$

就有

$${\text{Pr}}_{S\sim D^m}[R_D(L_H(S))\le \epsilon ]\ge 1-\delta .$$

反向存在一般 VC 类与分布，使任何学习器都需要 $c(d+\log \left(1/\delta \right))/\epsilon$ 个样本。因而可实现 PAC 的最优信息论量级是

$$m_{\mathrm{P}\mathrm{A}\mathrm{C}}(\epsilon ,\delta )=\mathrm{\Theta }\left(\frac{d+\log \left(1/\delta \right)}{\epsilon }\right).$$

这里上界的量词是“对每个类存在学习器”，下界则是“存在困难类与分布约束任意学习器”；两者都不能改写为任意一致 ERM 自动最优。不可知情形以类内最优风险为比较基准，其对应量级为

$$m_{\mathrm{a}\mathrm{g}\mathrm{n}\mathrm{o}\mathrm{s}\mathrm{t}\mathrm{i}\mathrm{c}}(\epsilon ,\delta )=\mathrm{\Theta }\left(\frac{d+\log \left(1/\delta \right)}{{\epsilon }^2}\right).$$

三种常被混在一起的界 ​

在可实现情形，一致 ERM 输出训练错误为零的 $h$。固定一个总体错误超过 $\epsilon$ 的假设，它在 $m$ 个 IID 样本上仍全对的概率至多 $(1-\epsilon {)}^m\le e^{-m\epsilon }$。用增长函数计数样本上可区分的坏行为并取并集，得到经典教材界

$$m=O\left(\frac{d\log \left(1/\epsilon \right)+\log \left(1/\delta \right)}{\epsilon }\right).$$

这里的 $\log \left(1/\epsilon \right)$ 来自这条证明路线，不是 VC 类可学习性的必然价格。精细的样本压缩/leave-one-out 型构造与递归学习器可消去它，得到上述最优 $O((d+\log \left(1/\delta \right))/\epsilon )$。

不可知情形没有“坏假设在样本上全对”这一单边事件。经验风险差是带噪平均量，要分辨类内最优与差 $\epsilon$ 的候选，通常需要方差尺度 $1/{\epsilon }^2$；VC 一致收敛给出匹配的

$$O\left(\frac{d+\log \left(1/\delta \right)}{{\epsilon }^2}\right)$$

量级（采用更精细的 VC/Rademacher 界可避免无关对数）。

具体例子：$d=1$ 阈值为何是 $1/\epsilon$ ​

令 $H$ 是 $[0,1]$ 上阈值分类器，目标阈值为 $a$，输入均匀分布。若学习器输出的阈值与 $a$ 相隔超过 $\epsilon$，中间区间的概率质量便超过 $\epsilon$。在可实现数据中，只要样本落入 $a$ 两侧各自宽度约 $\epsilon$ 的关键区间，就能把误差夹到常数量级的 $\epsilon$ 内；漏掉一个关键区间的概率按 $e^{-m\epsilon }$ 衰减，所以 $m\asymp \log \left(1/\delta \right)/\epsilon$。

这个例子也给出下界图像：若关键区间没有样本，两个相隔 $\epsilon$ 的阈值产生完全相同的观测，学习器无法知道真实者是谁。高维下界则在被打散的 $d$ 个位置上安排许多独立难点，使所需样本线性依赖 $d$。

算法限制与边界 ​

“最优样本复杂度”允许在定义指定的输出范围内选择最合适的 learner。某个自然的一致 ERM、某种固定 tie-breaking，或强制 proper 的学习器可能带有额外对数或结构代价；不能从存在一个最优 learner 推出所有 proper ERM 都最优。反过来，允许 improper 输出也不会改变上面一般二元 VC 学习的基本量级，但在特定类和计算限制下会显著改变可实现算法。

若 $d=0$、$\epsilon$ 接近常数或 $\delta$ 不小，精确公式需要处理退化项；本页的 $\mathrm{\Theta }$ 陈述针对非退化参数区间。把不可知的 ${\epsilon }^{-2}$ 套到可实现数据会丢失单边结构，把教材式 $d\log \left(1/\epsilon \right)/\epsilon$ 称作信息论下界则把证明松弛误当成问题本身。

参考资料

• Steve Hanneke, “The Optimal Sample Complexity of PAC Learning,” JMLR, 2016.
• Anselm Blumer et al., 1989.
• Martin Anthony and Peter Bartlett, Neural Network Learning: Theoretical Foundations.