样本复杂度、精度与置信度

量词顺序 ​

分布无关样本复杂度描述：当 $m\ge m_{\mathcal{H}}(\epsilon ,\delta )$ 时，

$$\mathrm{\forall }D,{\text{Pr}}_{S\sim D^m,U}\{R_D(A(S,U))-R_D^{\mathrm{b}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{h}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{k}}\le \epsilon \}\ge 1-\delta .$$

先固定任意允许分布，再对样本和算法随机性取概率。$\epsilon$ 控制风险精度，$\delta$ 控制失败概率；两者都不是训练轮数。

对 Bernoulli 均值，Hoeffding 给

$$\text{Pr}(|\hat{p}-p|>\epsilon )\le 2e^{-2m{\epsilon }^2},$$

故 $m\ge \log \left(2/\delta \right)/(2{\epsilon }^2)$ 足够。精度减半约需四倍样本，置信失败率只按对数进入。但可实现一致分类常有 $1/\epsilon$ 速率，这个例子不是万能公式。

边界与版本 ​

应区分充分上界与最优样本数、分布无关与分布依赖、期望与高概率、可实现错误与不可知超额风险。渐近一致性只说 $m\to \mathrm{\infty }$ 时收敛，不能替代有限 $m(\epsilon ,\delta )$；运行时间、查询次数和在线跨度 $T$ 也是不同资源。

独立重复有时能做概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。，但学习器输出好坏未必可验证，多数投票也可能离开原类，所以 $\log \left(1/\delta \right)$ 不能总由一句“重复即可”证明。

把数字代入可校准量级。若希望 Bernoulli 均值误差不超过 $0.05$，失败概率至多 $0.01$，上式给

$$m\ge \frac{\log 200}{2(0.05{)}^2}\approx 1060.$$

这是分布无关的充分条件，不表示 1059 个样本必然失败，也不表示它是最优常数。若事先知道 $p$ 很接近零，利用方差的 Bernstein 型区间可能更省样本；这属于分布条件更强的界。

多参数大 O 也须说明保持哪些量变化。$m=O((d+\log \left(1/\delta \right))/{\epsilon }^2)$ 表示存在统一常数，使所有规定范围内的 $d,\epsilon ,\delta$ 都受控；不能固定 $\delta =0.05$ 做实验后声称已经验证其对数依赖，更不能把训练耗时随 $m$ 增长误报成样本复杂度。

参考资料

• Leslie Valiant, “A Theory of the Learnable,” 1984.
• Steve Hanneke, “The Optimal Sample Complexity of PAC Learning,” 2016.