统一PAC-Bayes框架：随机集合上的数据依赖假设空间

1 引言

传统的PAC学习理论假设假设空间 $\mathcal{H}$ 是固定的（与数据无关）。然而，现代机器学习算法（如深度学习、神经网络架构搜索）使用的假设空间往往是数据依赖的（data-dependent）——假设空间本身由训练数据构造，例如：

• 通过验证集选择的模型族
• 通过预训练模型初始化的网络
• 通过无监督预训练发现的特征空间
• 通过超参数优化选择的搜索空间

对于这些数据依赖的假设空间，传统的PAC-Bayes边界不再适用，因为标准的PAC-Bayes分析假设假设空间是预定义的且不依赖于数据。

DUPUIS等(JMLR 2024)提出了革命性的解决方案：将PAC-Bayes框架建立在**随机集合（Random Set）**理论之上，为数据依赖假设空间提供统一的泛化分析工具。¹

---

2 传统PAC-Bayes在数据依赖场景下的失效

2.1 数据依赖假设空间的例子

例1：神经网络架构搜索（NAS）

搜索空间 $\mathcal{H}$ 是通过验证集性能选择的：

$${\mathcal{H}}_{\text{NAS}}=\{h\in {\mathcal{H}}_{\text{candidate}}:R_{\text{val}}(h)\le \tau \}$$

这里 ${\mathcal{H}}_{\text{NAS}}$ 直接依赖于验证数据。

例2：预训练模型初始化

先验 $P$ 是通过在大规模无标签数据上预训练得到的：

$$P_{\text{pretrain}}=\arg \underset{P\in \mathcal{P}}{\min }{\mathbb{E}}_{x\sim {\mathcal{D}}_{\text{pretrain}}}[\text{ReconstructionError}(x,P)]$$

例3：贝叶斯优化搜索空间

假设空间随搜索过程动态调整：

$${\mathcal{H}}_t=\{h:{\mu }_t(h)\pm {\sigma }_t(h)\le \tau \}$$

2.2 标准PAC-Bayes分析的困境

标准PAC-Bayes边界要求：

$$R(Q)\le {\hat{R}}_S(Q)+\sqrt{\frac{\text{KL}(Q\Vert P)+\ln (1/\delta )}{2m}}$$

问题：当 $P$ 和 $\mathcal{H}$ 依赖于训练数据时：

• 先验 $P$ 与数据相关 → $\text{KL}(Q\Vert P)$ 的PAC保证失效
• 假设空间 $\mathcal{H}$ 动态变化 → 经验风险估计有偏

2.3 现有方法的局限

方法	处理数据依赖的方式	局限性
条件PAC-Bayes	条件化于训练数据	边界可能变空
覆盖数方法	忽略先验信息	边界过于宽松
数据依赖先验	直接使用数据依赖先验	缺乏理论保证

---

3 随机集合理论基础

3.1 随机集合的定义

定义1（随机集合）：设 $(\Omega ,\mathcal{F},\mathbb{P})$ 是概率空间。随机集合是一个可测映射：

$$\mathcal{X}:\Omega \to \mathcal{K}(\Theta )$$

其中 $\mathcal{K}(\Theta )$ 是参数空间 $\Theta$ 上的非空紧集的集合。

3.2 随机集合的概率论

落影（Selection）：随机集合 $\mathcal{X}$ 的落影定义为：

$$\text{Sel}(\mathcal{X})=\left\{\theta \in \Theta :\exists \omega \in \Omega ,\theta \in \mathcal{X}(\omega )\right\}$$

分布函数：随机集合 $\mathcal{X}$ 的分布函数为：

$$F_{\mathcal{X}}(A)=\mathbb{P}(\omega :\mathcal{X}(\omega )\cap A\ne \varnothing )$$

3.3 随机集合上的积分

Aumann积分：设 $f:\Theta \to \mathbb{R}$ 是可测函数。$f$ 在随机集合 $\mathcal{X}$ 上的Aumann积分为：

$${\int }_{\mathcal{X}}f(\theta )d\theta ={\mathbb{E}}_{\omega }\left[{\int }_{\mathcal{X}(\omega )}f(\theta )d\theta \right]$$

在机器学习中的应用：将假设空间 $\mathcal{H}$ 视为随机集合，则期望风险可以写为：

$$R(Q)={\int }_{\mathcal{H}}R(h)dQ(h)={\int }_{\mathcal{H}}{\mathbb{E}}_z[\ell (h,z)]dQ(h)$$

---

4 随机集合上的PAC-Bayes框架

4.1 核心思想

DUPUIS等(2024)的核心思想是：将PAC-Bayes分析建立在随机集合上，而非固定的假设空间上。

不再假设存在固定的 $\mathcal{H}$，而是假设 $\mathcal{H}$ 本身是从某个随机集合生成过程中产生的：

$$\mathcal{H}=\mathcal{H}({\mathcal{D}}_{\text{aux}})$$

其中 ${\mathcal{D}}_{\text{aux}}$ 是辅助数据（如验证集、预训练数据等）。

4.2 随机假设空间的PAC-Bayes设置

定义2（随机假设空间上的PAC-Bayes学习）：

1. 数据生成：从分布 $\mathcal{D}$ 中采样训练集 $S\sim {\mathcal{D}}^m$
2. 辅助数据：从分布 ${\mathcal{D}}_{\text{aux}}$ 中采样辅助集 $A\sim {\mathcal{D}}_{\text{aux}}^{m^{\prime }}$
3. 随机假设空间：${\mathcal{H}}_A$ 是由辅助数据 $A$ 构造的随机集合
4. 先验生成：先验 $P_A$ 是 ${\mathcal{H}}_A$ 上的概率分布，依赖于 $A$
5. 学习：给定 $S$ 和 $A$，学习后验 $Q_{S,A}$

关键：所有随机性（$S,A,Q_{S,A}$）都在随机集合框架下统一处理。

4.3 随机集合上的PAC-Bayes边界

定理1（随机集合PAC-Bayes边界）：设 ${\mathcal{H}}_A$ 是由辅助数据 $A$ 生成的随机假设空间，$P_A$ 是在 ${\mathcal{H}}_A$ 上的先验。则对任意后验 $Q_{S,A}$ 和置信度 $\delta \in (0,1)$，以至少 $1-\delta$ 的概率：

$$R(Q_{S,A})\le {\hat{R}}_S(Q_{S,A})+\sqrt{\frac{\text{KL}(Q_{S,A}\Vert P_A)+\ln (1/\delta )+\ln {\mathbb{E}}_A\left[\frac{1}{{\mu }_A({\mathcal{H}}_A)}\right]}{2m}}$$

其中 ${\mu }_A$ 是 ${\mathcal{H}}_A$ 上的某个参考测度。

新项 $\ln {\mathbb{E}}_A[1/{\mu }_A({\mathcal{H}}_A)]$ 的解释：

• ${\mu }_A({\mathcal{H}}_A)$：随机假设空间的”体积”
• 当 ${\mathcal{H}}_A$ 很大时，$1/{\mu }_A({\mathcal{H}}_A)\to 0$，对数项为负 → 收紧边界
• 当 ${\mathcal{H}}_A$ 很小时，$1/{\mu }_A({\mathcal{H}}_A)\to \infty$，对数项为正 → 放松边界

4.4 随机假设空间的体积估计

核心挑战：如何估计 ${\mu }_A({\mathcal{H}}_A)$？

定理2（体积估计）：对于常见的随机假设空间，${\mu }_A({\mathcal{H}}_A)$ 可以通过以下方式估计：

假设空间类型	构造方式	体积估计
基于验证集	${\mathcal{H}}_A=\{h:R_{\text{val}}(h)\le \tau \}$	${\mu }_A({\mathcal{H}}_A)\approx \mathbb{P}(R_{\text{val}}(h)\le \tau )$
基于预训练	${\mathcal{H}}_A=B(P_{\text{pretrain}},r)$	${\mu }_A({\mathcal{H}}_A)\propto r^d$
基于NAS	${\mathcal{H}}_A$ 由搜索过程决定	${\mu }_A({\mathcal{H}}_A)={\prod }_i{p}_i$

---

5 统一边界定理

5.1 统一框架

DUPUIS等(2024)证明了一个统一PAC-Bayes边界，涵盖了多种现有的边界作为特例：

定理3（统一PAC-Bayes边界）：设 ${\mathcal{H}}_A$ 是随机假设空间，$P_A$ 是先验，$Q_{S,A}$ 是后验。则：

$$R(Q_{S,A})\le {\hat{R}}_S(Q_{S,A})+\underset{\text{标准PAC-Bayes项}}{\underbrace{\sqrt{\frac{\text{KL}(Q_{S,A}\Vert P_A)}{2m}}}}+\underset{\text{数据依赖项}}{\underbrace{\sqrt{\frac{\varphi (A)}{2m}}}}+\underset{\text{置信度项}}{\underbrace{\sqrt{\frac{\ln (1/\delta )}{2m}}}}$$

其中 $\varphi (A)=\ln {\mathbb{E}}_A[1/{\mu }_A({\mathcal{H}}_A)]$。

5.2 特殊情况的恢复

情况1：标准PAC-Bayes（假设空间固定）

当 $\mathcal{H}$ 固定且 $\mu (\mathcal{H})=1$ 时：

$$\varphi (A)=\ln (1/1)=0$$

边界退化为标准PAC-Bayes边界。

情况2：条件PAC-Bayes

当条件化于 $A$ 时：

$$R(Q_{S,A}|A)\le {\hat{R}}_S(Q_{S,A})+\sqrt{\frac{\text{KL}(Q_{S,A}\Vert P_A)+\ln (1/\delta )}{2m}}$$

情况3：覆盖数边界

当使用覆盖数 $N(ϵ,{\mathcal{H}}_A,d)$ 时：

$$\varphi (A)=\ln N(ϵ,{\mathcal{H}}_A,d)$$

5.3 关键引理：随机集合的McMillan定理

引理（McMillan定理的随机集合版本）：设 ${\mathcal{H}}_A$ 是由 $A$ 生成的随机假设空间。则：

$${\mathbb{E}}_{S,A}\left[\underset{h\in {\mathcal{H}}_A}{\sup }|{\hat{R}}_S(h)-R(h)|\right]\le {\mathbb{E}}_A\left[\sqrt{\frac{2\ln (1/{\mu }_A({\mathcal{H}}_A))}{m}}\right]$$

直觉：随机假设空间的”体积” ${\mu }_A({\mathcal{H}}_A)$ 越大，泛化误差的上界越小。这与直觉相反，但可以通过选择偏差来解释：更大的假设空间通常意味着更好的数据拟合，因此泛化误差不一定更大。

---

6 在神经网络中的应用

6.1 预训练模型初始化

应用场景：在大规模数据上预训练的模型作为先验，然后在下游任务上进行变分微调。

随机假设空间：以预训练模型 ${\theta }_{\text{pretrain}}$ 为中心的球：

$${\mathcal{H}}_A=\{\theta :\Vert \theta -{\theta }_{\text{pretrain}}{\Vert }_2\le R\}$$

PAC-Bayes边界：

$$R(Q_{S,A})\le {\hat{R}}_S(Q_{S,A})+\sqrt{\frac{\text{KL}(Q_{S,A}\Vert P_A)}{2m}}+\sqrt{\frac{d\ln (R/ϵ)}{2m}}$$

其中 $d$ 是参数空间的维度，$ϵ$ 是覆盖精度。

6.2 神经网络架构搜索

应用场景：在验证集上选择最优架构。

随机假设空间：

$${\mathcal{H}}_A=\{h_{\alpha }:\alpha \in \mathcal{A},R_{\text{val}}(h_{\alpha })\le \tau \}$$

其中 $A$ 是验证集，$\mathcal{A}$ 是架构空间。

PAC-Bayes边界：

import numpy as np
from scipy.stats import norm
 
class RandomSetPACBayes:
    """
    随机集合PAC-Bayes边界计算器
    
    用于数据依赖假设空间的泛化分析
    """
    def __init__(self, hypothesis_space_type='nas'):
        self.type = hypothesis_space_type
        
    def compute_volume_term(self, A, coverage_epsilon=1e-3):
        """
        计算体积项 φ(A) = ln E[1/μ_A(H_A)]
        
        这个项衡量了随机假设空间的"信息量"
        """
        if self.type == 'nas':
            # NAS场景：假设空间体积与候选架构数成正比
            n_candidates = len(A)  # 候选架构数
            volume = n_candidates * coverage_epsilon
            phi_A = np.log(1.0 / (volume + 1e-10))
            
        elif self.type == 'pretrain':
            # 预训练场景：假设空间体积与预训练数据量相关
            n_pretrain = len(A)  # 预训练样本数
            d = 1e6  # 参数维度（假设）
            volume = (n_pretrain / d) ** 0.5
            phi_A = np.log(1.0 / (volume + 1e-10))
            
        elif self.type == 'validation':
            # 验证集选择场景
            n_val = len(A)
            n_total = 100000  # 总候选数
            # 通过验证集筛选后的候选比例
            selected_ratio = n_val / n_total
            volume = selected_ratio * coverage_epsilon
            phi_A = np.log(1.0 / (volume + 1e-10))
        
        return max(phi_A, 0)  # 确保非负
    
    def pac_bayes_bound_random_set(self, emp_risk, kl_div, m, delta=0.05,
                                   A=None, hypothesis_space_type='nas'):
        """
        随机集合PAC-Bayes边界
        
        R(Q) ≤ emp_risk + sqrt((KL + φ(A) + ln(1/δ)) / (2m))
        """
        # 计算体积项
        phi_A = self.compute_volume_term(A, coverage_epsilon=1e-3)
        
        # 标准PAC-Bayes项
        complexity_standard = np.log(2 * np.sqrt(m) / delta)
        
        # 总复杂度
        total_complexity = kl_div + phi_A + complexity_standard
        
        # 边界
        bound = emp_risk + np.sqrt(total_complexity / (2 * m))
        
        return {
            'risk_bound': bound,
            'volume_term': phi_A,
            'standard_term': np.sqrt((kl_div + complexity_standard) / (2 * m)),
            'data_dependent_term': np.sqrt(phi_A / (2 * m))
        }
 
def compare_pac_bayes_bounds():
    """
    比较标准PAC-Bayes与随机集合PAC-Bayes边界
    """
    calc = RandomSetPACBayes()
    
    # 不同场景的参数
    scenarios = [
        {'name': 'Standard PAC-Bayes', 'type': None, 'kl': 100, 'emp_risk': 0.1, 'm': 10000},
        {'name': 'NAS (10 candidates)', 'type': 'nas', 'kl': 100, 'emp_risk': 0.1, 'm': 10000, 'n_candidates': 10},
        {'name': 'NAS (1000 candidates)', 'type': 'nas', 'kl': 100, 'emp_risk': 0.1, 'm': 10000, 'n_candidates': 1000},
        {'name': 'Pretrained (large data)', 'type': 'pretrain', 'kl': 10, 'emp_risk': 0.05, 'm': 10000, 'n_pretrain': 1000000},
        {'name': 'Pretrained (small data)', 'type': 'pretrain', 'kl': 50, 'emp_risk': 0.08, 'm': 10000, 'n_pretrain': 10000},
    ]
    
    results = []
    for s in scenarios:
        if s['type']:
            A = list(range(s.get('n_candidates', s.get('n_pretrain', 1000))))
            result = calc.pac_bayes_bound_random_set(
                s['emp_risk'], s['kl'], s['m'], 
                A=A, hypothesis_space_type=s['type']
            )
        else:
            # 标准PAC-Bayes
            bound = s['emp_risk'] + np.sqrt((s['kl'] + np.log(2*np.sqrt(s['m'])/0.05)) / (2*s['m']))
            result = {'risk_bound': bound, 'volume_term': 0}
        
        results.append({
            'scenario': s['name'],
            'bound': result['risk_bound'],
            'volume_term': result.get('volume_term', 0)
        })
        
        print(f"{s['name']}: bound={result['risk_bound']:.4f}, φ(A)={result.get('volume_term', 0):.4f}")
    
    return results

6.3 迁移学习

应用场景：从源任务迁移知识到目标任务。

随机假设空间：

$${\mathcal{H}}_A=\{h:h=h_{\text{source}}+\Delta h,\Vert \Delta h\Vert \le R\}$$

PAC-Bayes边界分析：

迁移设置	假设空间体积	边界效果
同领域迁移	大（允许大的参数变化）	放松边界，但允许灵活适应
跨领域迁移	小（约束参数变化）	收紧边界，保证泛化
零样本迁移	极小（不允许参数变化）	极紧边界，但可能限制表达

---

7 与其他数据依赖方法的比较

7.1 综合比较

方法	处理数据依赖的方式	边界类型	可扩展性
标准PAC-Bayes	忽略（假设固定）	点估计	✅
条件PAC-Bayes	条件化	点估计	✅
覆盖数	忽略	上界	✅
算法稳定性	算法属性	期望	✅
本文方法	随机集合	统一框架	✅

7.2 统一性优势

DUPUIS等的框架提供了一种统一视角来理解不同类型的数据依赖边界：

1. 标准PAC-Bayes：当假设空间固定时恢复
2. 条件PAC-Bayes：当条件化于辅助数据时恢复
3. 覆盖数边界：当使用覆盖数估计体积时恢复
4. 算法稳定性：当假设空间由算法隐式决定时恢复

---

8 总结

8.1 核心贡献

1. 随机集合框架：将PAC-Bayes分析建立在随机集合理论上，解决了数据依赖假设空间的问题
2. 统一边界：提出了涵盖多种现有边界的统一PAC-Bayes边界
3. 体积项分析：引入了 $\varphi (A)=\ln {\mathbb{E}}_A[1/{\mu }_A({\mathcal{H}}_A)]$ 这一新概念，衡量随机假设空间的信息量
4. 应用广泛：适用于预训练、NAS、迁移学习等多种实际场景

8.2 与本 Wiki 其他内容的联系

• 参见 PAC-Bayes边界理论 获取基础框架
• 参见 PAC-Bayes边界有效性分析 了解边界有效性问题
• 参见 神经网络架构搜索 了解NAS应用场景

---

Footnotes

1. Dupuis, B., Viallard, P., Deligiannidis, G., & Simsekli, U. (2024). “Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets.” JMLR, 25:1-55. ↩