PAC-Bayes-kl 界

形式陈述 ​

两个 KL 必须分开 ​

PAC-Bayes 泛化界公理库PAC-Bayes 泛化界PAC-Bayes bound · PAC-Bayes proof template以先验到数据依赖后验的 KL 散度支付换测度代价，将先验下的指数矩控制转成同时覆盖所有 Gibbs 后验的泛化证书。同时出现两种相对熵。第一种

$$\mathrm{KL}(Q\Vert P)$$

比较假设空间上的后验 $Q$ 与数据无关先验 $P$，衡量学习后重新分配了多少描述质量。第二种是两个 Bernoulli 参数间的二元相对熵公理库KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。

$$\mathrm{kl}(q\Vert p)=q\log \frac{q}{p}+(1-q)\log \frac{1-q}{1-p}.$$

它比较经验风险 $q$ 与总体风险 $p$。两者共享 KL 几何，却位于不同空间，不能合并成一项或交换方向。

定理 ​

设损失 $\ell (h,z)\in [0,1]$，样本 $S\sim D^m$。对任意不依赖 $S$ 的先验分布 $P$，以至少 $1-\delta$ 的概率，下面的不等式同时对所有后验 $Q$ 成立：

$$\mathrm{kl}({\hat{R}}_S(Q)\Vert R_D(Q))\le \frac{\mathrm{KL}(Q\Vert P)+\log \frac{2\sqrt{m}}{\delta }}{m},$$

其中

$${\hat{R}}_S(Q)={\mathbb{E}}_{h\sim Q}{\hat{R}}_S(h),R_D(Q)={\mathbb{E}}_{h\sim Q}{R}_D(h).$$

常数项有多种严谨版本，例如 $\log ((m+1)/\delta )$ 或更精细的矩界；选用哪一版必须与证明中的 Bernoulli 指数矩估计一致。稳定内容是二元 kl 左侧和 $m^{-1}(\mathrm{KL}(Q\Vert P)+\log \left(1/\delta \right))$ 右侧。

如何读成风险上界 ​

记右侧为 $c$。定理并未直接写出 $R_D(Q)$，而是把它限制在集合

$$\{p\in [0,1]:\mathrm{kl}({\hat{R}}_S(Q)\Vert p)\le c\}$$

中。定义上侧反演

$${\mathrm{kl}}_{+}^{-1}(q,c)=sup\{p\in [q,1]:\mathrm{kl}(q\Vert p)\le c\},$$

即可得到

$$R_D(Q)\le {\mathrm{kl}}_{+}^{-1}({\hat{R}}_S(Q),c).$$

通常用二分搜索稳定求解，无需为它发明闭式近似。

当 ${\hat{R}}_S(Q)=0$ 时，

$$\mathrm{kl}(0\Vert p)=-\log (1-p),$$

所以 $p\le 1-e^{-c}\approx c$。这给出接近 $1/m$ 的可实现型行为。若先用 Pinsker 不等式把 kl 粗化为 $2(p-q{)}^2$，只能得到 $\sqrt{c}$ 级偏差，正好丢掉低经验风险附近的非对称优势。

证明骨架 ​

对固定 $h$，二项型矩估计控制

$${\mathbb{E}}_S\exp (m\mathrm{kl}({\hat{R}}_S(h)\Vert R_D(h))).$$

随后利用 change-of-measure 不等式，把 $Q$ 下的函数期望转成 $P$ 下的对数矩母函数，并支付 $\mathrm{KL}(Q\Vert P)$。最后用 Markov 不等式产生 $\log \left(1/\delta \right)$，再通过凸性把假设逐点风险合并成 Gibbs 风险。因为高概率事件对所有 $Q$ 同时成立，$Q$ 可以在观察数据后选择。

直觉

右侧的 posterior–prior KL 衡量学习器从先验编码中走了多远，左侧的 Bernoulli kl 则保留经验风险与总体风险之间的不对称几何。尤其当经验风险接近零时，二元 kl 允许总体风险按 $1/m$ 级收缩，而平方根型对称松弛会把这一优势抹掉。

先验并非“相信某个模型正确”的口号，而是数据出现前分配给各假设的描述质量。后验可以依数据选择，因为定理在一个共同高概率事件上同时覆盖所有 $Q$；先验若也用同一数据调整，就会破坏这条统一 change-of-measure 账目。

例子与边界

一个有限类特例 ​

若 $H$ 有限、$P$ 为均匀先验，而 $Q={\delta }_h$ 集中在单个数据选择的分类器上，则

$$\mathrm{KL}(Q\Vert P)=\log |H|.$$

PAC-Bayes-kl 界便成为有限类 Occam 界的精细风险版本。若先验对某些简洁假设给更大质量，复杂度会变成 $\log (1/P(h))$；这是可审计的编码偏好，不是看到数据后把先验移到最终答案附近。

边界 ​

该风险是每次预测先从 $Q$ 抽取 $h$ 的 Gibbs 风险，不自动等于多数投票或后验均值分类器的风险。把 Gibbs 界转成确定性聚合器的保证需要额外关系。先验若使用同一训练数据构造，也会破坏定理；数据依赖先验必须通过样本切分、超先验或专门界处理。

损失超过 $[0,1]$ 时，二元 kl 形式不再直接适用。可先有原则地缩放有界损失，或采用适合次高斯、重尾损失的 PAC-Bayes 变体，不能把数值截进 $[0,1]$ 后仍声称控制原风险。

推论与应用

有限类、均匀先验与点质量后验把复杂度项化为 $\log |H|$；非均匀先验则给每个假设不同的 $\log (1/P(h))$ 代价。分层模型和随机化分类器可借此表达结构偏好，而不必把全部候选压成同一个最坏基数。

实际使用时，应数值反演 ${\mathrm{kl}}_{+}^{-1}$，并报告先验、后验、Gibbs 风险和所用常数版本。若最终输出是多数投票、后验均值或单个抽取后固定的模型，还需额外证明它与 Gibbs 风险的关系。

参考资料

• Matthias Seeger, “PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification,” Journal of Machine Learning Research 3, 2002.
• John Langford and Matthias Seeger, “Bounds for Averaging Classifiers,” Technical Report CMU-CS-01-102, 2001.
• David A. McAllester, “Some PAC-Bayesian Theorems,” COLT, 1998.