Multi-model Online Conformal Prediction with Graph-Structured Feedback

基本信息

• 论文ID: 2506.20898
• 标题: Multi-model Online Conformal Prediction with Graph-Structured Feedback
• 作者: Erfan Hajihashemi, Yanning Shen (University of California, Irvine)
• 分类: cs.LG
• 发表时间/会议: Transactions on Machine Learning Research (10/2025)
• 论文链接: https://arxiv.org/abs/2506.20898

摘要

Online conformal prediction has demonstrated its capability to construct a prediction set for each incoming data point that covers the true label with a predetermined probability. To cope with potential distribution shift, multi-model online conformal prediction has been introduced to select and leverage different models from a preselected candidate set. Along with the improved flexibility, the choice of the preselected set also brings challenges. A candidate set that includes a large number of models may increase the computational complexity. In addition, the inclusion of irrelevant models with poor performance may negatively impact the performance and lead to unnecessarily large prediction sets. To address these challenges, we propose a novel multi-model online conformal prediction algorithm that identifies a subset of effective models at each time step by collecting feedback from a bipartite graph, which is refined upon receiving new data. A model is then selected from this subset to construct the prediction set, resulting in reduced computational complexity and smaller prediction sets. Additionally, we demonstrate that using prediction set size as feedback, alongside model loss, can significantly improve efficiency by constructing smaller prediction sets while still satisfying the required coverage guarantee. The proposed algorithms are proven to ensure valid coverage and achieve sublinear regret. Experiments on real and synthetic datasets validate that the proposed methods construct smaller prediction sets and outperform existing multi-model online conformal prediction approaches.

研究背景与动机

1. 要解决的问题：现有多模型在线共形预测方法在处理分布漂移时面临计算复杂度高和预测集过大的问题。传统方法需要对所有候选模型进行更新和评估，当候选集包含大量模型或性能较差的模型时，会导致效率低下。
2. 问题的重要性：在安全关键应用（如自动驾驶、医疗诊断）中，需要可靠的不确定性量化来确保决策的可信度。共形预测能够在不依赖分布假设的情况下提供有效的预测集，但在在线环境中需要应对数据分布的动态变化。
3. 现有方法的局限性：
   • 计算复杂度随候选模型数量线性增长
   • 包含低性能模型会负面影响整体表现
   • 缺乏有效的模型选择机制来动态适应分布变化
4. 研究动机：开发一种能够自适应选择有效模型子集的多模型在线共形预测算法，在保证覆盖率的同时降低计算复杂度并减小预测集大小。

核心贡献

1. 提出了GMOCP算法：设计了基于图结构反馈的多模型在线共形预测算法，通过二分图动态识别有效模型子集
2. 构建了自适应图生成框架：基于模型历史表现动态构建和更新二分图，实现模型的在线选择
3. 开发了EGMOCP扩展算法：将预测集大小作为额外反馈信号，进一步提升预测效率
4. 提供了理论保证：证明了算法的有效覆盖率和亚线性遗憾界
5. 在多个数据集上验证了有效性：在CIFAR-10C、CIFAR-100C等数据集上实现了更小的预测集和更低的计算复杂度

方法详解

任务定义

给定历史数据 $\{(X_τ, Y^{true}_τ)\}^{t-1}_{τ=1}$ 和新输入 $X_t$，构建预测集 $C^m_α(X_t) ⊆ Y$ 使得真实标签 $Y^{true}_t$ 以概率 $1-α$ 包含在预测集中，其中 $α$ 为误覆盖概率。

模型架构

1. 二分图结构设计

• 模型节点：$\{v^{(l)}_1, ..., v^{(l)}_M\}$ 表示M个候选模型
• 选择节点：$\{v^{(s)}_1, ..., v^{(s)}_J\}$ 表示J个选择节点
• 连接约束：每个选择节点最多连接N个模型节点

2. 图生成算法

模型节点连接概率： $p^m_t = (1 - η_e) \frac{w^m_t}{\sum^M_{\bar{m}=1} w^{\bar{m}}_t} + \frac{η_e}{M}$

其中 $η_e$ 为探索系数，$w^m_t$ 为模型权重。

3. 模型权重更新

使用重要性采样损失估计： $w^m_{t+1} = w^m_t \exp(-ε l^m_t / 2^b)$

其中损失函数为： $l^m_t = \frac{L(\bar{α}^m_t, α^m_t)}{q^m_t} I\{m ∈ S_t\}$

4. 自适应误覆盖概率更新

使用Scale-Free在线梯度下降： $α^m_{t+1} = α^m_t - η \frac{∇_{α^m_t} L(\bar{α}^m_t, α^m_t)}{\sqrt{\sum^t_{τ=1} \|∇_{α^m_τ} L(\bar{α}^m_τ, α^m_τ)\|^2_2}}$

技术创新点

1. 图结构反馈机制：通过二分图动态选择模型子集，避免对所有模型的更新
2. 双重反馈设计：EGMOCP同时考虑预测损失和预测集大小作为反馈信号
3. 自适应探索-利用平衡：通过不同的探索系数实现多层次的探索策略

实验设置

数据集

1. CIFAR-10C/CIFAR-100C：包含15种腐败类型，5个严重程度级别
2. TinyImageNet-C：200类的腐败版本数据集
3. 合成数据集：3000个样本，20个类别，模拟分布漂移

评价指标

• Coverage：预测集包含真实标签的百分比
• Avg Width：预测集的平均大小
• Run Time：算法运行时间
• Single Width：大小为1且正确覆盖的预测集百分比

对比方法

• MOCP：多模型在线共形预测基线方法
• COMA：共形在线模型聚合方法
• 单模型方法：ACI、FACI、DECAY、SAOCP

实现细节

• 目标覆盖率：90% (α = 0.1)
• 超参数：ε = 0.5, η = 0.05, β = 0.05
• 时间步数：T = 6000
• 批次大小：500个样本

实验结果

主要结果

在CIFAR-100C数据集上的突发分布漂移实验中：

• GMOCP相比MOCP实现了更快的运行时间（约50%提升）和相似的预测集大小
• EGMOCP显著减小了预测集大小，从MOCP的12.63降至6.18，同时保持90%的目标覆盖率
• 单宽度比例从22.43%提升至29.91%

消融实验

1. 图参数影响：测试不同的N（模型节点数）和J（选择节点数）组合
2. 探索策略：比较不同探索系数设置的效果
3. 反馈机制：验证预测集大小反馈的有效性

案例分析

通过DenseNet121的三种训练配置（120D、10R、1R）展示：

• 高性能模型（120D）获得最高权重和选择概率
• EGMOCP能有效识别并偏向选择性能更好的模型
• 预测集大小与模型性能呈负相关

实验发现

1. 计算效率提升：GMOCP的每步复杂度为O(Nt + JMN)，相比MOCP的O(Mt)在N << M时显著降低
2. 预测质量改善：EGMOCP通过双重反馈机制实现更小的预测集
3. 鲁棒性验证：在多种分布漂移场景下保持稳定性能

相关工作

1. 共形预测基础：基于Vovk等人的经典框架，扩展到在线环境
2. 自适应共形预测：Gibbs & Candès的时变误覆盖概率方法
3. 多模型方法：与Hajihashemi & Shen、Gasparin & Ramdas的工作对比
4. 在线学习理论：借鉴专家学习和多臂老虎机的思想

结论与讨论

主要结论

1. 图结构反馈机制能有效减少计算复杂度并提升预测效率
2. 预测集大小作为反馈信号显著改善算法性能
3. 理论保证与实验结果一致，验证了方法的有效性

局限性

1. 图构建需要额外的超参数调优
2. 在候选模型质量相近时改善有限
3. 理论分析基于特定的损失函数假设

未来方向

1. 探索更复杂的图结构和更新策略
2. 扩展到回归任务和其他不确定性量化方法
3. 研究在强分布漂移下的适应性

深度评价

优点

1. 方法创新性强：图结构反馈机制为多模型选择提供了新思路
2. 理论基础扎实：提供了覆盖率和遗憾界的严格证明
3. 实验设计全面：涵盖多种数据集和分布漂移场景
4. 实用价值高：显著降低计算复杂度的同时提升预测质量

不足

1. 超参数敏感性：需要调节多个图相关参数
2. 适用场景限制：在模型质量差异不大时优势不明显
3. 理论分析复杂：证明过程较为繁琐，实用性有待验证

影响力

1. 学术贡献：为在线不确定性量化领域提供了新的技术路线
2. 应用前景：在需要实时决策的安全关键系统中具有重要价值
3. 可复现性：算法描述详细，实验设置清晰

适用场景

1. 需要实时不确定性量化的在线学习系统
2. 面临分布漂移的动态环境
3. 计算资源受限但需要多模型融合的场景
4. 安全关键应用中的可靠预测需求

参考文献

1. Vovk, V., Gammerman, A., & Shafer, G. (2005). Algorithmic learning in a random world
2. Gibbs, I., & Candès, E. J. (2021). Adaptive conformal inference under distribution shift
3. Hajihashemi, E., & Shen, Y. (2024). Multi-model ensemble conformal prediction in dynamic environments
4. Gasparin, M., & Ramdas, A. (2024). Conformal online model aggregation