跳转至

Aggregating Conformal Prediction Sets via α-Allocation

讲者: Yue Yu
会场: Advances in Statistical Inference and Machine Learning
报告题目: Aggregating Conformal Prediction Sets via α-Allocation
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

本文研究的子问题是：在 conformal prediction 框架下，如何利用多个非一致性得分函数（nonconformity scores）来构造预测集，使得在保证覆盖概率的前提下，预测集的平均大小（或个体大小）尽可能小。Conformal prediction 本身已成熟（分布自由、有限样本覆盖），但多得分聚合的效率优化是当前活跃的开放问题。

发展脉络（history）

  • 奠基工作：Vovk et al. (2005) 提出 split conformal prediction，给定一个得分函数即可构造有限样本有效的预测集。Lei et al. (2018) 将 Bonferroni 型交集思想用于多得分，但分配是固定的（等分或先验），未数据驱动。
  • 主要进展：
  • 得分选择：Yang and Kuchibhotla (2025) 提出 EFCP/VFCP，从候选得分中选一个最优的（最小化预测集大小），但只选一个，可能丢失信息。Liang et al. (2024) 用全共形化改进效率。
  • 集合级合并：Gasparin and Ramdas (2024) 用多数投票合并多个 1−α 水平集，保证覆盖但不优化大小。Qin et al. (2024) 用 Cauchy 组合 p 值合并，同样不优化。
  • 得分级组合：Luo and Zhou (2025) 加权平均得分，但假设得分可比较（尺度一致），实际中常违反。
  • 效率优化：Kiyani et al. (2024) 直接最小化预测集大小，但只针对单个得分；Xie et al. (2024) 用 boosting 改进得分，但仍是单得分。
  • 当前 frontier：如何数据驱动地分配置信水平到多个得分，使交集大小最小，同时保持覆盖。本文 COLA 直接填补此 gap。
  • 本文位置：作者称“a unified, data-driven framework for efficiently aggregating multiple scores has not been provided”（Section 1.1 末句）。COLA 通过优化 α 分配实现聚合，是第一个系统处理此问题的框架。

子线索聚类

  1. 得分选择（Yang & Kuchibhotla 2025; Liang et al. 2024）：从 K 个得分中选一个，用其构造预测集。优点是简单，缺点是在无单一优势得分时效率低。
  2. 集合级合并（Gasparin & Ramdas 2024; Qin et al. 2024; Wu et al. 2023; Wong et al. 2025）：合并多个 1−α 水平集（多数投票或 p 值合并），保证覆盖但不优化大小。作者指出“they ignore the conformal machinery and therefore do not optimize the weights”（Section 1）。
  3. 得分级组合（Luo & Zhou 2025; Patel et al. 2025）：加权平均得分或预测模型，但假设得分可比较，实际中“often violated”（Section 1）。
  4. 效率导向的得分改进（Xie et al. 2024; Kiyani et al. 2024; Bai et al. 2022）：优化单个得分或直接优化预测集大小，但未涉及多得分聚合。

核心问题与瓶颈

  • 核心问题：给定 K 个得分函数，如何分配置信水平 α₁,…,α_K（和为 α）使得交集预测集最小，同时保证覆盖？
  • 已知瓶颈：
  • 分配必须数据驱动，但数据依赖会破坏交换性，导致有限样本覆盖失效。
  • 优化目标（交集大小）是 α 的阶梯函数，组合优化困难（K 大时网格搜索不可行）。
  • 个体化分配需要条件覆盖，而分布自由下有限样本条件覆盖不可能（Barber et al. 2021），只能追求渐近条件覆盖。

⚠️ 作者的 framing

作者将缺口 frame 为：“existing approaches for score selection or aggregation have primarily targeted at improving average size efficiency, failing to adapt choices to individual test points”（Section 1 末段）。因此 COLA-l 被定位为“个性化”方案。竞争路线（得分选择、集合合并）被淡化：作者指出它们要么只选一个得分（可能丢失信息），要么不优化权重。明显该被引但未出现：没有讨论如何将多得分聚合与 conformal training（如 Einbinder et al. 2022）结合；也没有讨论当得分来自不同数据源（如联邦学习）时的隐私或通信约束。值得研究者去查：是否有工作将多得分聚合与交叉拟合（cross-fitting）结合以同时保证覆盖和效率？

张力

未见明显对立引用。各子线索之间是互补而非矛盾关系：得分选择是 COLA 的特例（当 Θ 限制为单支撑时），集合合并是 COLA 的固定分配特例（α_k = α/K 等）。作者在 Section 2.2 明确说“COLA-e reduces to EFCP”当 Θ 限制为单支撑。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • 符号：
  • \( (X_i, Y_i) \in \mathcal{X} \times \mathcal{Y} \)：i.i.d. 样本，\( i=1,\dots,n \) 为 hold-out 数据，\( (X_{n+1}, Y_{n+1}) \) 为测试点（\( X_{n+1} \) 观测，\( Y_{n+1} \) 未知）。
  • \( S_k(x,y) \in \mathbb{R} \)：第 k 个非一致性得分函数（固定、预训练），\( k=1,\dots,K \)。
  • \( \alpha \in (0,1) \)：名义误覆盖水平（如 0.1）。
  • \( \Theta = \{ \alpha \in \mathbb{R}^K : \alpha_k \ge 0, \sum_k \alpha_k = \alpha \} \)：可行分配集。
  • \( \widehat{C}_k(x; \alpha_k) = \{ y : S_k(x,y) \le Q_{\alpha_k}(\{S_k(X_i,Y_i)\}_{i=1}^n \cup \{\infty\}) \} \)：第 k 个 conformal 预测集，水平 1−α_k。
  • \( C_k(x; \alpha_k) = \{ y : S_k(x,y) \le q_{k,\alpha_k} \} \)：总体（oracle）预测集，其中 \( q_{k,\alpha} \) 是 \( S_k(X_{n+1},Y_{n+1}) \) 的 1−α 分位数。
  • \( L(\alpha) = \mathbb{E}_{X_{n+1}}[ |\cap_{k=1}^K C_k(X_{n+1}; \alpha_k)| ] \)：oracle 期望交集大小。
  • \( L_n(\alpha) = \frac{1}{n} \sum_{i=1}^n |\cap_{k=1}^K \widehat{C}_k(X_i; \alpha_k)| \)：经验平均交集大小。
  • \( \alpha^* \in \arg\min_{\alpha\in\Theta} L(\alpha) \)：oracle 最优分配。

  • \( \widehat{\alpha} \)：经验最优分配（由 \( L_n \) 最小化得到）。

  • 模型：无分布假设，仅要求 \( (X_i,Y_i) \) i.i.d. 来自某联合分布 P。得分函数 \( S_k \) 是固定的（由外部训练数据得到，本文不涉及训练过程）。Conformal prediction 的覆盖保证基于交换性。

  • 可观测数据：观测到 \( \{(X_i,Y_i)\}_{i=1}^n \) 和测试点 \( X_{n+1} \)。不可观测：\( Y_{n+1} \)（要预测的响应）。潜在量：每个得分对应的总体分位数 \( q_{k,\alpha} \)，以及 oracle 最优分配 \( \alpha^* \)，这些只能通过样本估计。

第二步：最小内核

最简特例：K=2，两个残差得分 \( S_1(x,y)=|y-\widehat{\mu}_1(x)| \)，\( S_2(x,y)=|y-\widehat{\mu}_2(x)| \)，来自两个不同的预测模型（如 OLS 和随机森林）。假设响应 Y 是一维连续变量。此时每个 conformal 预测集是区间：\( \widehat{C}_k(x;\alpha_k) = [\widehat{\mu}_k(x) - \widehat{q}_{k,\alpha_k}, \widehat{\mu}_k(x) + \widehat{q}_{k,\alpha_k}] \)，其中 \( \widehat{q}_{k,\alpha_k} \) 是残差绝对值的样本 1−α_k 分位数。交集 \( \widehat{C}_1 \cap \widehat{C}_2 \) 也是区间（或空集），其长度为 \( \min(\widehat{\mu}_1+\widehat{q}_1, \widehat{\mu}_2+\widehat{q}_2) - \max(\widehat{\mu}_1-\widehat{q}_1, \widehat{\mu}_2-\widehat{q}_2) \) 的正部。

核心思路：我们希望分配 α₁ 和 α₂（α₁+α₂=α）使得这个交集区间平均长度最小。直觉上，如果模型 1 更准确（残差小），则 \( \widehat{q}_{1,\alpha_1} \) 随 α₁ 增长较慢，因此应给模型 1 分配更大的 α₁（即更小的 1−α₁ 水平，更紧的区间），而给模型 2 分配很小的 α₂（使其区间很宽，几乎不限制交集）。Oracle 分配 \( \alpha^* \) 由总体分位数决定。COLA-e 用样本数据估计 \( \alpha^* \)：对每个候选 α 计算训练集上平均交集长度，选最小的那个。例如，若模型 1 明显优于模型 2，则最优分配可能是 \( \alpha_1 \approx \alpha, \alpha_2 \approx 0 \)，此时 COLA-e 退化为 EFCP（选模型 1）。若两个模型各有优劣（如在不同 x 区域），则最优分配可能让两者都贡献，产生比任何单个模型更小的交集。

为什么这抓住了核心：整个论文的数学困难在于：① 经验分配 \( \widehat{\alpha} \) 依赖数据，破坏交换性，导致有限样本覆盖失效（需渐近分析）；② 优化目标 \( L_n(\alpha) \) 是 α 的阶梯函数（因为分位数在样本点跳跃），组合优化困难；③ 个体化分配需要条件分位数估计，引入核平滑和额外收敛速率。但核心想法就是“分配 α 预算到多个区间，取交集以缩小总长度”，这个想法在 K=2 的区间情形下完全透明。

三、这篇论文做了什么

三句话

  1. 研究问题：如何通过数据驱动地分配置信水平 α 到 K 个 conformal 预测集（每个由不同得分函数定义），然后取交集，以最小化预测集大小同时保证覆盖。
  2. 核心方法：提出 COnfidence-Level Allocation (COLA) 框架，包括四个变体：COLA-e（经验风险最小化，渐近有效）、COLA-s（样本分割，有限样本有效）、COLA-f（全共形化，有限样本有效）、COLA-l（个体化分配，渐近条件覆盖）。
  3. 主要结论：在温和条件下，COLA-e 和 COLA-s 达到渐近最优分配（期望大小收敛到 oracle 值），COLA-l 达到渐近条件覆盖和局部 oracle 大小。模拟和真实数据表明 COLA 比现有基线（EFCP、VFCP、Majority Vote、SAT）产生更小的预测集。

关键设定与假设

  • 设定：i.i.d. 数据，K 个固定得分函数 \( S_k \)。每个得分可构造 conformal 预测集 \( \widehat{C}_k(x;\alpha_k) \)。最终预测集为交集 \( \cap_k \widehat{C}_k(x;\widehat{\alpha}_k) \)。
  • 假设（以 Theorem 2 为例）：
  • Assumption 1：(a) 得分分布函数连续；(b) 分位数函数 Lipschitz 连续（密度有正下界）；(c) 极小 α_k 不改变交集（截断性质）；(d) 交集大小一致有界。
  • Assumption 2：(a) 每个得分对应的水平集可表示为至多 m 个区间的并（回归中 m=1 常见）；(b) 水平集大小关于阈值 Lipschitz（得分变化导致大小变化有界）。
  • 相比已有文献：Yang and Kuchibhotla (2025) 的 EFCP 假设类似但只针对单得分选择；本文需要额外假设 (c) 和 (d) 以处理多得分交集。Assumption 2 是本文特有的，用于从分位数收敛推导交集大小收敛。

主要结果

  • Theorem 1（COLA-e 渐近覆盖）：\( P(Y_{n+1} \in \widehat{C}_e) \ge 1-\alpha - O(\sqrt{\log(Kn)/n}) \)。仅需 i.i.d.，比 EFCP 的 \( O(\sqrt{\log K/n}) \) 稍慢，因为分配空间更大。
  • Theorem 2（COLA-e 渐近效率）：在 Assumptions 1-2 下，\( \mathbb{E}[|\widehat{C}_e|] - L(\alpha^*) = O_p( m L_q L_s \sqrt{\log K/n} + M \sqrt{K\log n/n} ) \)。要求 \( K=o(n/\log n) \)。
  • Theorem 3（COLA-s 有限样本覆盖）：若校准集与测试点可交换，则 \( P(Y_{n+1} \in \widehat{C}_s) \ge 1-\alpha \)（精确有限样本）。
  • Corollary 1（COLA-s 渐近效率）：类似 Theorem 2，但速率由 \( n_{\min} = \min(n_{tu}, n_{cal}) \) 控制。
  • Theorem 4（COLA-f 有限样本覆盖）：全共形化版本也保证 \( \ge 1-\alpha \)。
  • Theorem 5（COLA-l 渐近条件覆盖）：在核平滑假设下，条件覆盖 \( \ge 1-\alpha - K\cdot O( \sqrt{\log(Kn)/(n h_n^d)} + \tau h_n \log(1/h_n) ) \)。第二部分在更强条件下将 K 因子改进为 log K。
  • Theorem 6（COLA-l 渐近效率）：条件期望大小收敛到局部 oracle 值，速率 \( O( m L_q L_s (\sqrt{\log(Kn)/(n h_n^d)} + \tau h_n \log(1/h_n) ) ) \)。选择 \( h_n \asymp n^{-1/(d+2)} \) 得 \( n^{-1/(d+2)} \log n \) 速率。

证明路线与技术技巧

Theorem 1 证明路线： 1. 利用条件概率分解：\( P(Y_{n+1} \notin \widehat{C}_e | \mathcal{D}) \le \frac{1}{n}\sum_i \mathbf{1}\{Y_i \notin \cap_k \widehat{C}_k(X_i;\widehat{\alpha}_k)\} + W \)，其中 \( W = \sup_t |\frac{1}{n}\sum_i \prod_k \mathbf{1}\{S_{k,i} \le t_k\} - \mathbb{E}[\prod_k \mathbf{1}\{S_k \le t_k\}]| \)。 2. 第一项 ≤ α（因为 \( \widehat{\alpha} \) 满足 \( \sum_k \widehat{\alpha}_k = \alpha \)，且每个 \( \widehat{C}_k \) 的误覆盖比例 ≤ \( \widehat{\alpha}_k \)）。 3. 第二项 W 用 multivariate DKW 不等式（Naaman 2021）控制：\( \mathbb{E}[W] \le K(n+1)e^{-2nt^2} + t \)，取 \( t = \sqrt{\log(Kn)/n} \) 得 \( O(\sqrt{\log(Kn)/n}) \)。

关键跳跃点：W 的 bound 需要处理 K 维经验过程，但作者巧妙地用 union bound 和单变量 DKW 的乘积形式，未用更复杂的 VC 维工具。

Theorem 2 证明路线： 1. 分解 \( L(\widehat{\alpha}) - L(\alpha^*) \le 2 \sup_\alpha |L_n(\alpha) - L(\alpha)| \)。 2. 进一步分解为 Π₁（估计误差：用样本分位数代替总体分位数导致的交集大小偏差）和 Π₂（经验平均与总体期望的偏差）。 3. Π₁ 的 bound：用 Lemma 1（分位数一致收敛，基于 DKW 和 Lipschitz）得到 \( |\widehat{C}_k \triangle C_k| \le L_q L_s \sqrt{\log(2K/\delta)/(2n)} \)。再用 Lemma 2（区间并的交集对称差 bound）得到 Π₁ = \( O(m L_q L_s \sqrt{\log K/n}) \)。 4. Π₂ 的 bound：构造函数类 \( \{g_\alpha(x) = |\cap_k C_k(x;\alpha_k)| : \alpha \in \Theta\} \)，证明其关于 α 是 Lipschitz（系数 \( L_s L_q \)）。用 ϵ-net 覆盖 Θ（ℓ₁ 范数，ϵ = \( M/(L_q L_s) \cdot \sqrt{K\log n/(2n)} \)），对每个固定 α 用 McDiarmid 不等式，再 union bound 和 Lipschitz 延拓，得 Π₂ = \( O_p(M \sqrt{K\log n/n}) \)。 5. 最后结合 Π₁ 和 Π₂ 得期望大小收敛。

技术技巧点名： - Multivariate DKW（Naaman 2021）：用于 Theorem 1 中控制 K 维经验过程。 - ϵ-net + McDiarmid：用于控制经验过程 sup 的偏差，是经典技巧，但需要 Lipschitz 性质（Lemma 1 和 Assumption 1(b) 保证）。 - Lemma 2（区间并的交集对称差 bound）：本文自创的引理，将每个得分水平集视为至多 m 个区间的并，然后证明交集对称差被各分量对称差之和的常数倍控制。这是处理一般得分（如分位数回归得分）的关键。 - 局部化 conformal prediction（Guan 2022）：用于 COLA-l，用核权重构造条件分位数估计，再用类似技巧证明条件覆盖和效率。

真实例子与应用

  • 模拟实验（Section 4.1-4.2）：三个合成数据情形（不同学习算法、不同非一致性度量、不同特征子集），比较 COLA-e/s 与 EFCP、VFCP、Majority Vote、SAT、Random。结果显示 COLA 在多数情形下产生更小预测集，且覆盖接近名义水平。特别在 Case 2（不同非一致性度量）中，COLA 显著优于 EFCP/VFCP，说明分配优于选择。个体化实验（Section 4.2）显示 COLA-l 在条件覆盖和局部大小上优于 COLA-e。
  • 真实数据（Section 4.3）：三个 UCI 数据集（Blog Feedback, Concrete Strength, Superconductivity），使用三种非一致性度量（残差、缩放残差、分位数回归得分）。COLA-e/s 在覆盖接近 90% 的同时，预测集大小比 EFCP/VFCP 小 10-40%，比 Majority Vote 小 50% 以上。例如 Blog 数据集：COLA-e 大小 13.36，EFCP 22.39，Majority Vote 48.10。
  • 这些例子想说明：① COLA 在多种设定下均能有效缩小预测集；② 当得分间无单一优势时，分配比选择更优；③ 个体化分配能进一步改善局部效率。

🔎 结论是否比证明窄

  • Theorem 1 的覆盖下界是 \( 1-\alpha - O(\sqrt{\log(Kn)/n}) \)，但作者在 Section 2.2 称“COLA-e satisfies asymptotically optimal allocation”，而 optimal allocation 定义（Definition 1）要求覆盖 \( \ge 1-\alpha + o(1) \)，Theorem 1 确实满足（因为 \( O(\sqrt{\log(Kn)/n}) = o(1) \)），所以一致。
  • Theorem 2 的效率 bound 依赖于 Assumption 2（水平集为区间并），但作者在 Section A.8 对分类问题给出了一个更弱的 bound（Theorem 7），只要求 i.i.d.，但效率损失为 \( O_p(M\sqrt{\log(Kn)/n}) \)，且 oracle 比较的是 \( \alpha^* - W_f' \cdot \mathbf{1}_K \)（有偏移）。这意味着在分类中，COLA-e 的渐近效率不如回归中干净。作者在正文中未强调此限制，只说“Extensions to the classification setting are provided in Section A.8”，但 Theorem 7 的结论比 Theorem 2 弱（有偏移项）。这是值得注意的窄化。
  • COLA-f 的效率没有理论保证，只有实证结果（Section C.1.3）。作者在 Conclusion 中承认“a theoretical analysis of COLA-f’s efficiency... is needed”。

四、开放问题

  1. COLA-f 的效率理论：作者在 Conclusion 指出“a theoretical analysis of COLA-f’s efficiency, in the spirit of Liang et al. (2024), is needed”。目前只有有限样本覆盖保证，无大小收敛速率。扎根于 Section 5 第一句 future work。

  2. 大规模优化：作者提到“more computationally effective optimization procedures are required to find global solutions in large-scale settings reliably”（Section 5）。当前 stepwise 算法复杂度 \( O(K (\alpha n)^{k_{\max}-1}) \)，当 K 很大时仍可能昂贵。是否有凸松弛或随机优化方法？扎根于 Section 5 第二句 future work。

  3. 其他最优性概念：作者提出“beyond size efficiency, other notions of optimality deserve attention, such as allocating the budget α to maximize the utility of prediction-based decisions under the coverage constraint”（Section 5）。例如，在个性化医疗中，预测集大小可能不是唯一目标，还需考虑决策损失。扎根于 Section 5 末句。

  4. 条件覆盖的有限样本 impossibility 与近似：Barber et al. (2021) 已证明分布自由下有限样本条件覆盖不可能，但 COLA-l 只达到渐近条件覆盖。是否有办法在有限样本下达到某种近似条件覆盖（如局部化后的近似界）？这涉及 Guan (2022) 和本文 Theorem 5 的速率，但未讨论有限样本非渐近 bound。可查近期工作如 Gibbs et al. (2025) 是否提供了更紧的有限样本条件覆盖 bound。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论