PAC-Bayes-kl 界

形式陈述 ​

两个 KL 必须分开 ​

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

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

它比较经验风险 $q$ 与总体风险 $p$。本页对数均取自然对数，边界采用相对熵的连续延拓约定。两者共享 KL 几何，却位于不同空间，不能合并成一项或交换方向。

定理 ​

沿用PAC-Bayes 框架理路PAC-Bayes 框架PAC-Bayesian framework · PAC-Bayes以数据无关先验和数据依赖后验之间的 KL，控制随机化 Gibbs 预测器的风险。的可测假设空间与联合可测有界损失，设样本 $S\sim D^m$，$m\ge 1$，$0<\delta <1$。对任意不依赖 $S$ 的先验分布 $P$，以至少 $1-\delta$ 的概率，下面的不等式同时对所有后验 $Q$ 成立：

其中

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

如何读成风险上界 ​

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

中。定义上侧反演

即可得到

当 $0<q<1$、$0<c<\mathrm{\infty }$ 时，先取 $b<1$ 使 $\mathrm{kl}(q\Vert b)>c$；这样的 $b$ 存在，因为 $p\uparrow 1$ 时该 KL 趋于无穷。在闭区间 $[q,b]$ 上对连续函数 $\mathrm{kl}(q\Vert p)-c$ 使用二分法理路二分求根法Bisection method以端点异号区间为不变量，给出可验证误差界、对数成本和有限精度停止条件。，便得到有括区间的数值证书。$c=0$ 时上界为 $q$，$q=1$ 或 $c=+\mathrm{\infty }$ 时上界为 $1$。

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

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

证明骨架 ​

对固定 $h$，令 $p=R_D(h)$。当损失只取 $0,1$ 且 $0<p<1$ 时，错误数 $K\sim \mathrm{Bin}(m,p)$，用二项概率公式理路二项分布Binomial distribution固定次数独立同概率 Bernoulli 试验中成功总数的离散分布。消去 $p$ 后得到

其中端点采用 $0^0=1$。Maurer 的矩估计给出 $m\ge 8$ 的上界，$1\le m\le 7$ 可直接核对上述有限和。对一般 $[0,1]$ 损失，指数二元 KL 是样本损失向量的凸函数；逐坐标用连接 $0,1$ 的弦作上界，再利用 IID 性，便把期望控制为同均值 Bernoulli 情形。若 $p=0$ 或 $1$，有界损失本身几乎必然恒定，指数矩为 $1$。

把 $F_S(h)=m\mathrm{kl}({\hat{R}}_S(h)\Vert R_D(h))$ 和 $C_m=2\sqrt{m}$ 代入指数矩—换测度模板理路PAC-Bayes 泛化界PAC-Bayes bound · PAC-Bayes proof template以先验到数据依赖后验的 KL 散度支付换测度代价，将先验下的指数矩控制转成同时覆盖所有 Gibbs 后验的泛化证书。，得到同时覆盖所有后验的 $E_Q{F}_S$ 上界。最后对二元 KL 的联合凸性应用Jensen 不等式理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。：

边界取扩展实值凸函数的约定；有限 KL 后验在共同事件上有有限右侧。两步结合即得定理，也说明为什么样本中的 $Q$ 可以在看到数据之后选择。