NeurIPS 2026 学习理论 Learning Theory 符合预测生成模型覆盖分配混合整数线性规划高密度区域

Generative Conformal Prediction with Optimized Coverage Allocation¶

会议: NeurIPS 2026
arXiv: 2410.13735
领域: 学习理论 / Learning Theory
关键词: 符合预测, 生成模型, 覆盖分配, 混合整数线性规划, 高密度区域

一句话总结¶

针对传统符合预测在多模态与异质分布下不确定性区间过于保守的问题，本文提出三阶段框架 ORCA，利用生成模型采样结合局域密度排名将覆盖分配转化为混合整数线性规划，在保证有限样本有效性的同时渐进收敛至神谕最高密度区域。

研究背景与动机¶

符合预测（Conformal Prediction, CP）作为一种模型无关的不确定性量化框架，能够在严格的有限样本可交换性假设下提供具有统计覆盖保证的预测区间。然而，当条件分布呈现复杂的多模态、异方差或流形几何结构时，传统符合预测构造的预测集往往过于宽泛和保守。这种预测效率低下的根源通常来自两方面：一是底层预测模型表达能力有限（如点预测回归或分位数回归难以完整刻画复杂的条件分布），二是传统非一致性得分设计过于单一（如仅依赖标量残差），无法充分利用分布层面的几何丰富度。

尽管近期已有方法尝试引入生成模型进行符合预测（例如概率符合预测 PCP 通过条件采样将不确定性集建模为以生成样本为中心的球体并集），但现有方案往往将多样本残差粗暴坍缩为单个标量统计量，赋予所有生成样本完全相同的球半径。这导致低密度噪声区域与高密度真实模态被无差别同等扩张；而在采样样本数较少时，长尾分布更会导致整体半径急剧膨胀，严重损害预测集的实用性与紧致度。

解决该瓶颈的切入点在于联合建模生成分布的局部拓扑并自适应分配覆盖预算。核心 idea：利用生成模型采样并基于平均 $m$ 最近邻距离对样本做局域密度排序，将排序后的距离向量转化为基于体积代理的覆盖优化问题，通过混合整数线性规划（MILP）在有限样本校准下为不同密度层级自适应分配紧致半径。

方法详解¶

整体框架¶

ORCA（Optimized Ranking and Coverage Allocation）是一个分为三个阶段的生成符合预测框架。给定已拟合的条件生成模型 $\hat{p}(Y|X)$ 与留出数据集 $\mathcal{D} = \mathcal{D}_{\text{explore}} \cup \mathcal{D}_{\text{calib}}$： 1. 探索阶段（Stage 1）：在探索集 $\mathcal{D}_{\text{explore}}$ 上为每个样本条件生成 $K$ 个预测点，利用平均 $m$ 最近邻（$m$-NN）距离估计局部密度代理并对生成点排序，构建保真分布几何的排序距离向量； 2. 分位数优化阶段（Stage 2）：将覆盖目标建模为各排序层级球体体积总和的极小化问题，精确转化为混合整数线性规划（MILP）或贪心松弛求解，得到各秩次的最佳分位数阈值方向； 3. 符合校准与预测阶段（Stage 3）：在校准集 $\mathcal{D}_{\text{calib}}$ 上评估相对非一致性得分，计算单标量缩放因子 $t_\alpha$ 实现严格的有限样本边际覆盖保证，并在测试点处形成自适应半球并集。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["输入：条件生成模型与留出集划分"] --> Stage1["局域密度感知排序与距离向量构建<br/>条件采样 K 个点并按 m-NN 平均距离由密到疏排序"]
    Stage1 --> Stage2["基于体积代理的最优覆盖分配与 MILP 求解<br/>极小化多层级体积预算并约束经验覆盖率不低于 1-α"]
    Stage2 --> Stage3["相对非一致性得分校准与预测集生成<br/>计算标量缩放系数 t_α 形成自适应异质半径球并集"]
    Stage3 --> Out["输出：有限样本有效且逼近神谕 HDR 的紧致预测集"]

关键设计¶

1. 局域密度感知排序与距离向量构建：捕捉条件分布的非均质几何结构 传统方法仅计算真实标签到生成采样的最小距离，丢弃了生成点间的拓扑信息。ORCA 在探索集样本 $X_i$ 上采样 $\{ \hat{Y}_{i,k} \}_{k=1}^K \sim \hat{p}(\cdot|X_i)$，计算每个生成点到其它采样点的平均 $m$ 最近邻距离 $\bar{D}_{i,k} = \frac{1}{m} \sum_{l=1}^m D_i(k, (l))$，并按照 $\bar{D}_{i,j(1)} \le \dots \le \bar{D}_{i,j(K)}$ 进行升序排序。此处的序索引 $j(r)$ 对应第 $r$ 个最密集局域点。随后计算观测标签 $Y_i$ 到各个排序生成点的欧氏距离，形成保留完整多模态信息的秩次距离向量： $$E_i = (E_{i,1}, \dots, E_{i,K}), \quad E_{i,r} = \| Y_i - \hat{Y}_{i,j(r)} \|$$ 该设计将标量残差升维为向量残差，使较小的 $r$ 专注高密度核心区域，较大的 $r$ 捕捉稀疏尾部与不确定性边界。渐进理论证明，当 $K \to \infty, m \to \infty, m/K \to 0$ 时，该排序概率以 $1 - o(1)$ 严格收敛于条件密度 $p(\cdot|x)$ 的真实递减顺序。

2. 基于体积代理的最优覆盖分配与 MILP 求解：将几何覆盖松弛为全局可解规划 为了使预测集尽量紧致，ORCA 不直接计算复杂重叠几何区域的高维体积积分，而是采用加法代理体积预算 $\sum_{r=1}^K (Q_r(\beta_r))^d$（其中 $d$ 为输出空间维度）。通过在探索集上定义覆盖指示函数 $\hat{S}_i(\beta) = \max_{r \in [K]} \mathbb{I}\{ E_{i,r} \le Q_r(\beta_r) \}$，将覆盖优化问题形式化为： $$\min_{\beta} \sum_{r=1}^K (Q_r(\beta_r))^d \quad \text{s.t.} \quad \frac{1}{n_1} \sum_{i=1}^{n_1} \hat{S}_i(\beta) \ge 1 - \alpha$$ 直接网格搜索需要评估 $n_1^K$ 种配置，在计算上不可行。本文将各秩次距离的阶统计量 $E_{(1),r} \le \dots \le E_{(n_1),r}$ 视为候选断点，引入增量体积代价 $c_{r,\ell} = E_{(\ell),r}^d - E_{(\ell-1),r}^d$ 与前缀二值变量 $z_{r,\ell} \in \{0,1\}$、样本覆盖变量 $y_i \in \{0,1\}$，将其重构为严格等价的混合整数线性规划（MILP）： $$\min_{z,y} \sum_{r=1}^K \sum_{\ell=1}^{n_1} c_{r,\ell} z_{r,\ell} \quad \text{s.t.} \quad y_i \le \sum_{r=1}^K \sum_{\ell=1}^{n_1} a_{i,r,\ell} z_{r,\ell}, \quad \sum_{i=1}^{n_1} y_i \ge \lceil n_1(1-\alpha) \rceil, \quad z_{r,\ell} \ge z_{r,\ell+1}$$ 该 MILP 保证全局最优解。为了应对大样本扩展性，进一步提出了多项式复杂度的线性规划松弛配前缀截断算法（ORCA-LP）与基于跳跃的部分集合覆盖贪心算法（ORCA-Greedy），使成千上万样本能在数秒至数十秒内求解完成。

3. 相对非一致性得分校准与预测集生成：闭环保真有限样本覆盖 在 Stage 2 确定最佳半径阈值方向 $Q_r(\hat{\beta}_r)$ 后，为确保严格的有限样本边际覆盖率而不破坏统计交换性，Stage 3 在独立的校准集 $\mathcal{D}_{\text{calib}}$ 上统一定义相对非一致性得分： $$S_i = \min_{r \in [K]} \frac{E_{i,r}}{Q_r(\hat{\beta}_r)}$$ 其中 $S_i < 1$ 代表被过度覆盖，$S_i > 1$ 代表覆盖不足。通过在校准集得分经验分布上选取第 $\lceil (n_2+1)(1-\alpha) \rceil$ 阶分位数得到全局缩放系数 $t_\alpha$，将各秩次最终预测半径设为 $R_r(\alpha) = t_\alpha Q_r(\hat{\beta}_r)$。最终预测集为以测试点生成样本为中心的球体并集： $$\hat{\mathcal{C}}_{\text{ORCA}}(X_{\text{test}}) = \bigcup_{r=1}^K \Big\{ y: \| y - \hat{Y}_{\text{test},j(r)} \| \le R_r(\alpha) \Big\}$$ 由于测试得分与校准集得分服从完全可交换分布，该机制证明可在任意样本容量下严格满足 $\Pr(Y_{\text{test}} \in \hat{\mathcal{C}}_{\text{ORCA}}(X_{\text{test}})) \ge 1 - \alpha$，且在大样本极限下预测集在勒贝格测度意义下对称差收敛于真实的神谕最高密度区域（HDR）。

实验关键数据¶

主实验¶

在 6 个合成数据集（Circles, Moon, S-shape, Spiral, Roll, Mixture Gaussian）及 7 个真实世界基准（Facebook Comment Volume Fb1/Fb2, BlogFeedback, Protein Bio, MEPS 19-21, Bike 2D 轨迹, Temperature）上，作者与 CQR、CHR、DCP、DistSplit、CDSplit、CRD、R2CCP 以及同属生成范式的 PCP 进行了系统评估（名义覆盖率设为 $1-\alpha=0.90$）。

数据集	指标	CQR	CHR	PCP	ORCA (本文)	相对 PCP 效率提升
Circles (合成)	边际覆盖率预测集大小 (Eff)	$0.90 \pm 0.01$ $1.70 \pm 0.01$	$0.90 \pm 0.01$ $1.49 \pm 0.06$	$0.90 \pm 0.01$ $0.68 \pm 0.31$	$0.90 \pm 0.01$ $0.63 \pm 0.24$	-7.4%
S-shape (合成)	边际覆盖率预测集大小 (Eff)	$0.90 \pm 0.01$ $3.36 \pm 0.02$	$0.90 \pm 0.01$ $3.34 \pm 0.02$	$0.90 \pm 0.02$ $0.58 \pm 0.01$	$0.90 \pm 0.01$ $0.51 \pm 0.05$	-12.1%
Fb1 (真实)	边际覆盖率预测集大小 (Eff)	$0.90 \pm 0.00$ $14.78 \pm 2.31$	$0.90 \pm 0.01$ $11.23 \pm 1.34$	$0.90 \pm 0.01$ $7.79 \pm 0.28$	$0.90 \pm 0.02$ $3.70 \pm 1.75$	-52.5%
Blog (真实)	边际覆盖率预测集大小 (Eff)	$0.90 \pm 0.02$ $16.18 \pm 2.61$	$0.90 \pm 0.02$ $10.26 \pm 1.77$	$0.90 \pm 0.01$ $8.27 \pm 0.21$	$0.90 \pm 0.01$ $3.61 \pm 1.27$	-56.3%
Bike ($\times 10^{-3}$)	边际覆盖率预测集大小 (Eff)	$0.90 \pm 0.01$ $0.54 \pm 0.02$	$0.90 \pm 0.01$ $0.49 \pm 0.02$	$0.90 \pm 0.02$ $0.46 \pm 0.03$	$0.90 \pm 0.02$ $0.36 \pm 0.00$	-21.7%

消融与敏感性分析¶

在 S-shape 数据集上，针对 Stage 2 求解器类型与采样数 $K$ 的运行耗时与预测集效率进行了消融对比；并在 MNIST-VAE 任务上进行了输出空间度量方式的消融实验。

求解策略 / 模块设置	$K=10$ (耗时 / Eff)	$K=15$ (耗时 / Eff)	$K=20$ (耗时 / Eff)	$K=25$ (耗时 / Eff)	说明
PCP (统一标量半径基线)	0.00s / 0.75	0.00s / 0.48	0.00s / 0.37	0.00s / 0.34	无优化分配，低密度球半径不压缩
ORCA-MILP (精确规划)	11.95s / 0.67	16.97s / 0.35	23.15s / 0.32	40.96s / 0.31	全局最优体积分配，保证精确性
ORCA-LP (线性松弛+前缀截断)	1.50s / 0.67	2.88s / 0.37	5.22s / 0.34	8.94s / 0.36	多项式时间，体积接近全局最优
ORCA-Greedy (跳跃式贪心覆盖)	0.02s / 0.66	0.03s / 0.35	0.06s / 0.32	0.09s / 0.32	耗时下降 2-3 个数量级，效率无损

在 MNIST-VAE 高维图像生成实验中，评估预测集偏离真实类别错误率（Off-Class Rate, OCR，越低越好）： - 像素空间 $\ell_2$ 距离：PCP OCR = 0.374，ORCA OCR = 0.338（覆盖率 0.900）； - 隐空间余弦距离：PCP OCR = 0.090，ORCA OCR = 0.054（覆盖率 0.897）； - 学习型隐空间度量（Learned Latent Metric）：PCP OCR = 0.062，ORCA OCR = 0.019（覆盖率 0.905，语义纯度大幅提升）。

关键发现¶

复杂多峰下显著压缩体积：在 Blog 与 Fb1 等长尾及多模态数据上，ORCA 相比 PCP 将预测集大小压缩了超过 50%，且明显优于基于连续区间的传统基线（CQR、CHR），证明在密集区增大覆盖、在稀疏区压缩半径能极大避免无效覆盖浪费。
ORCA-Greedy 是极佳的工程默认实现：当 $K=20$ 时，ORCA-Greedy 仅耗时 0.06 秒即可达到与耗时 23.15 秒的精确 MILP 相同的预测集效率（Eff 均为 0.32），且根据符合校准理论，Stage 2 的求解精度不会破坏 Stage 3 的有限样本覆盖保证。
近邻排序参数稳健性：当 $m \ge 7$ 时，ORCA 相比 PCP 的效率增益趋于平稳（增益约为 28%~31%）；当 $m$ 过小时因近邻方差过大而导致排名不稳定。

亮点与洞察¶

将生成采样与离散组合优化巧妙解耦：利用探索集将非凸的几何区域体积极小化转化为精确的 MILP 形式，解耦了「寻找各模态最优覆盖比例」与「有限样本校准」两个目标，兼具理论完备性与统计严谨性。
理论架通符合预测与神谕最高密度集（HDR）：严格证明了当采样数与校准样本数趋于无穷时，局部密度排序与分位数优化驱动的预测集对称差收敛至神谕 HDR，为优化驱动的符合预测奠定了坚实统计基础。
通用度量空间的良好拓展性：方法完全不局限于标量或欧氏空间，只需提供有效度量即可直接推广到图像隐空间乃至图嵌入结构的不确定性量化。

局限与展望¶

可加性体积代理对重叠球体的松弛偏差：Stage 2 的目标函数对各秩次球体体积做简单累加，未显式减去重叠区域交集体积，在高维稠密采样下可能使优化目标与实际勒贝格测度存在轻微代理间隙。
生成模型极端误设的稳健性依赖：当条件生成器严重欠拟合或极端平滑时（如超参数单叶样本数极大时），生成的假样本可能扭曲局域密度排序，进而弱化效率提升幅度。
高维语义度量的自动构建：在图像、分子等非结构化输出上，预测集的几何形态严重依赖预训练度量，探索端到端联合学习生成度量与覆盖分配是值得探索的方向。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次联合结合生成分布采样拓扑与 MILP 覆盖分配，并建立渐进 HDR 等价性。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖 6 种合成数据、7 种真实基准、2D 轨迹以及 MNIST-VAE 高维度量消融。
写作质量: ⭐⭐⭐⭐⭐ 逻辑严密，数学符号规范，MILP 重构与收敛性证明完整。
价值: ⭐⭐⭐⭐⭐ 为现代生成模型的不确定性量化与可信决策提供了通用的即插即用方法。

数据集	指标	CQR	CHR	PCP	ORCA (本文)	相对 PCP 效率提升
Circles (合成)	边际覆盖率预测集大小 (Eff)	\(0.90 \pm 0.01\) \(1.70 \pm 0.01\)	\(0.90 \pm 0.01\) \(1.49 \pm 0.06\)	\(0.90 \pm 0.01\) \(0.68 \pm 0.31\)	\(0.90 \pm 0.01\) \(0.63 \pm 0.24\)	-7.4%
S-shape (合成)	边际覆盖率预测集大小 (Eff)	\(0.90 \pm 0.01\) \(3.36 \pm 0.02\)	\(0.90 \pm 0.01\) \(3.34 \pm 0.02\)	\(0.90 \pm 0.02\) \(0.58 \pm 0.01\)	\(0.90 \pm 0.01\) \(0.51 \pm 0.05\)	-12.1%
Fb1 (真实)	边际覆盖率预测集大小 (Eff)	\(0.90 \pm 0.00\) \(14.78 \pm 2.31\)	\(0.90 \pm 0.01\) \(11.23 \pm 1.34\)	\(0.90 \pm 0.01\) \(7.79 \pm 0.28\)	\(0.90 \pm 0.02\) \(3.70 \pm 1.75\)	-52.5%
Blog (真实)	边际覆盖率预测集大小 (Eff)	\(0.90 \pm 0.02\) \(16.18 \pm 2.61\)	\(0.90 \pm 0.02\) \(10.26 \pm 1.77\)	\(0.90 \pm 0.01\) \(8.27 \pm 0.21\)	\(0.90 \pm 0.01\) \(3.61 \pm 1.27\)	-56.3%
Bike (\(\times 10^{-3}\))	边际覆盖率预测集大小 (Eff)	\(0.90 \pm 0.01\) \(0.54 \pm 0.02\)	\(0.90 \pm 0.01\) \(0.49 \pm 0.02\)	\(0.90 \pm 0.02\) \(0.46 \pm 0.03\)	\(0.90 \pm 0.02\) \(0.36 \pm 0.00\)	-21.7%