PAC-Bayes-kl 界

两个 KL 必须分开 ​

PAC-Bayes-kl 界同时出现两种相对熵。第一种

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

比较假设空间上的后验 $Q$ 与数据无关先验 $P$，衡量学习后重新分配了多少描述质量。第二种是两个 Bernoulli 参数间的二元相对熵

$$\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$ 可以在观察数据后选择。

一个有限类特例 ​

若 $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]$ 后仍声称控制原风险。

参考资料

• Matthias Seeger, “PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification,” JMLR, 2002.
• John Langford and Matthias Seeger, “Bounds for Averaging Classifiers,” 2001.
• David McAllester, foundational PAC-Bayes bounds, 1998–1999.