跳转至

Aggregating conformal prediction sets via $ \alpha $-allocation

作者: Congbin Xu, Yue Yu, Zhaojun Wang, Changliang Zou, Haojie Ren
来源: Biometrika
主题: 数理统计 / 假设检验
相关性: 5/10
机构绿灯: Shanghai Jiao Tong University(US News 前 50,免分进入精读)
链接: https://doi.org/10.1093/biomet/asag048


一、领域脉络与小综述

这个方向是什么

本文所处的子方向是 conformal prediction 中的多分数聚合(multi-score aggregation)。其根本的统计问题是:在分布自由的有限样本覆盖保证(finite-sample coverage guarantee)框架下,如何利用多个 nonconformity score(非符合度分数)来构造比单一分数更小的预测集。这个问题的张力在于:conformal prediction 的核心卖点是"不依赖分布假设、有限样本覆盖精确",但代价是预测集往往偏大;引入多个分数可以携带更多信息,但如何在不破坏覆盖保证的前提下聚合它们,是一个机制设计问题。该方向当前处于活跃发展阶段——从早期的 score 选择(用数据挑一个最好的分数),到近年来的分数加权、分数组合,再到本文的置信水平分配(α-allocation),属于方法论的精细化推进。

发展脉络(history)

从 introduction 和参考文献可以梳理出这条线:

  • 奠基工作:Vovk et al. (2005) 的 conformal prediction 框架确立了"通过交换性(exchangeability)获得有限样本覆盖"这一核心机制。这是整个方向的公理基础——所有后续工作都在这个框架内操作。
  • 主要进展之一——分数选择:Lei et al. (2018) 和 Romano et al. (2019) 的 split conformal 与 CQR(conformalized quantile regression)确立了"用样本分裂构造 nonconformity score、再用分位数校准"的标准范式。这解决了"如何用一个分数构造预测集"的问题,但留下"多个分数怎么办"的口子。
  • 主要进展之二——分数聚合的早期尝试:Yang & Kuchibhotla (2021) 和 Gasparin & Ramdas (2022) 尝试通过选择或加权来组合多个分数。作者在引言中评价这些方法"要么需要额外的样本分裂来选分数,要么在分数数量多时效率损失明显"——这是作者对竞争路线的定位。
  • 当前 frontier:如何在不牺牲有限样本覆盖的前提下,让多个分数同时发挥作用。本文的位置是:把"选择"换成"分配"——不是选一个分数,而是给每个分数分配一个置信水平,然后取交集。这个思路的数学本质是:把多重检验中的 α-allocation(错误率分配)思想移植到 conformal inference 中。

子线索聚类

被引文献大致落在两条子线索上:

  1. 单分数 conformal 的精细化(Vovk et al. 2005; Lei et al. 2018; Romano et al. 2019; Barber et al. 2021):这条线在"给定一个分数,如何最优地构造预测集"上已经成熟,包括加权分位数、局部适应性等。本文的 baseline 主要来自这条线。
  2. 多分数的组合与选择(Yang & Kuchibhotla 2021; Gasparin & Ramdas 2022; 以及本文引用的其他 aggregation 工作):这条线在"如何利用多个分数"上仍在探索。本文的贡献是提出一种新的聚合机制(交集 + 置信水平分配),并给出两种变体(样本分裂版和完全 conformal 版)。

这个方向在追问的核心问题

  • 问题 1:多个 nonconformity score 各自携带不同信息(如一个对尾部敏感、一个对中心敏感),如何把它们的信息同时利用起来,而不是被迫选一个?
  • 问题 2:聚合后的预测集能否在保持覆盖的同时,严格小于任何单一分数构造的预测集?这个"严格改进"在什么条件下成立?
  • 问题 3:能否做到条件覆盖(conditional coverage)而不只是边际覆盖(marginal coverage)?——这是 conformal inference 的长期痛点,本文的 individualized allocation 试图在局部层面逼近这一点。

已知瓶颈:有限样本覆盖保证与条件覆盖之间存在根本张力(Barber et al. 2021 已证明无免费午餐);多分数聚合容易导致过拟合(用数据选分数会消耗样本);交集操作虽然缩小集合,但可能破坏覆盖的精确性。

⚠️ 作者的 framing(这是作者的说法)

作者把缺口 frame 成:"现有方法要么选一个分数(浪费信息),要么需要额外的样本分裂(降低效率),我们提出一种同时利用所有分数且不需要额外样本的聚合策略。" 这个 framing 让本文成为"显然的下一步"——既然选择是次优的,那就分配。

被淡化或回避的竞争路线: - 分数加权(如学习一个权重向量来组合分数)被作者一笔带过,理由是"权重学习需要额外样本或优化,且缺乏有限样本保证"。但加权方法在实证中往往表现不错,作者没有深入对比。 - e-values / betting-based 方法(如 Vovk & Wang 的 e-value 框架)没有被引入——这是一个明显的缺席,因为 e-value 的乘积/求和聚合与 α-allocation 在数学结构上有亲缘关系。

值得研究者去查的问题:为什么 introduction 没有引用 Vovk & Wang (2021) 的 e-value 聚合工作?是作者认为不相关,还是刻意回避?这可能是本文的一个盲区。

张力

未见明显对立引用。但有一个潜在张力值得注意:有限样本覆盖(split conformal 的卖点)与渐近条件覆盖(本文 individualized allocation 的目标)之间的取舍——作者承认有限样本覆盖只能做到边际,条件覆盖是渐近的。这与 Barber et al. (2021) 的 impossibility result 之间存在微妙关系,作者没有正面处理。


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

第一步:符号、模型、可观测数据

符号(逐个点名):

  • \(X \in \mathcal{X}\):特征向量,随机变量,可观测。
  • \(Y \in \mathcal{Y}\):响应变量,随机变量,可观测(训练时)。
  • \((X_i, Y_i)_{i=1}^n\):训练样本,i.i.d. 或可交换,可观测。
  • \(X_{n+1}\):新样本的特征,可观测;\(Y_{n+1}\):新样本的响应,不可观测,是预测目标。
  • \(\hat{\mu}_k(\cdot)\):第 \(k\) 个 nonconformity score 对应的预测模型(如回归函数估计),由训练数据得到,视为固定。
  • \(S_k(x) = s_k(x, \hat{\mu}_k)\):第 \(k\) 个 nonconformity score 函数,将 \((x, y)\) 映射为一个实数,衡量"\(y\) 与预测模型的不一致程度"。这是可计算的(给定模型后)。
  • \(S_k(X_i, Y_i)\):训练样本上的 score 值,可观测。
  • \(\hat{q}_k(1-\alpha_k)\):第 \(k\) 个 score 的经验分位数(基于训练样本),是估计量。
  • \(\alpha_k\):分配给第 \(k\) 个预测集的置信水平(错误率),是设计参数,满足 \(\sum_k \alpha_k = \alpha\)。
  • \(\alpha\):总的目标错误率(如 0.1),是用户指定的常数。
  • \(\hat{C}_k(X_{n+1}) = \{y : S_k(X_{n+1}, y) \leq \hat{q}_k(1-\alpha_k)\}\):第 \(k\) 个 conformal 预测集,可计算。
  • \(\hat{C}_{\text{agg}}(X_{n+1}) = \bigcap_k \hat{C}_k(X_{n+1})\):聚合预测集(交集),可计算。
  • \(\alpha_k(x)\):individualized allocation 中的局部置信水平,是 \(x\) 的函数,需要估计。
  • \(p_k(x)\):第 \(k\) 个 score 在给定 \(x\) 时的条件分布,不可观测,是理论分析中的对象。

模型:

  • 数据生成机制:\((X_i, Y_i) \overset{\text{i.i.d.}}{\sim} P\),\(P\) 未知但固定。交换性假设成立。
  • 统计模型:无参数模型(distribution-free)。唯一的结构假设是交换性。
  • 要估的对象:预测集 \(\hat{C}_{\text{agg}}(X_{n+1})\),使得 \(\mathbb{P}(Y_{n+1} \in \hat{C}_{\text{agg}}(X_{n+1})) \geq 1-\alpha\)(边际覆盖),或 \(\mathbb{P}(Y_{n+1} \in \hat{C}_{\text{agg}}(X_{n+1}) \mid X_{n+1}=x) \to 1-\alpha\)(渐近条件覆盖)。

可观测 vs 不可观测:

  • 可观测:所有训练样本的 \((X_i, Y_i)\);给定模型后所有 score 值;新样本的 \(X_{n+1}\)。
  • 不可观测:新样本的 \(Y_{n+1}\);score 的条件分布 \(p_k(x)\);最优的 \(\alpha_k\) 分配(因为它依赖未知分布)。

第二步:最小内核

最小特例:假设只有 两个 nonconformity score,\(S_1\) 和 \(S_2\),且总错误率 \(\alpha = 0.1\)。目标:构造 \(\hat{C}_{\text{agg}} = \hat{C}_1 \cap \hat{C}_2\),其中 \(\hat{C}_k\) 用置信水平 \(\alpha_k\) 构造,\(\alpha_1 + \alpha_2 = 0.1\)。

朴素做法:\(\alpha_1 = \alpha_2 = 0.05\)。每个预测集覆盖概率 \(1-0.05 = 0.95\),交集覆盖概率 \(\geq 1 - 0.05 - 0.05 = 0.9\)(Bonferroni)。但交集可能很小,甚至为空。

本文的核心思想:\(\alpha_1\) 和 \(\alpha_2\) 不一定要均分。如果 \(S_1\) 比 \(S_2\) 更"尖锐"(即 \(S_1\) 构造的预测集在相同置信水平下更小),那么应该给 \(S_1\) 分配更大的错误率预算(即更小的 \(\alpha_1\),更紧的预测集),给 \(S_2\) 分配更小的错误率预算(更大的 \(\alpha_2\),更松的预测集)。这样交集的大小由"最紧的那个"主导,而覆盖由"最松的那个"兜底。

数学命题(最小内核):给定两个 score 函数 \(S_1, S_2\) 和总错误率 \(\alpha\),存在一个最优分配 \((\alpha_1^*, \alpha_2^*)\),使得 \(\mathbb{E}[|\hat{C}_1 \cap \hat{C}_2|]\) 最小化,同时满足 \(\mathbb{P}(Y_{n+1} \in \hat{C}_1 \cap \hat{C}_2) \geq 1-\alpha\)。这个最优分配可以通过一个一维优化问题求解(因为 \(\alpha_2 = \alpha - \alpha_1\),只有一个自由参数)。

为什么这个内核是"最小"的:它抓住了本文的全部本质——把多重检验中的错误率分配问题移植到 conformal 预测集的交集构造上。所有后续的推广(多个 score、individualized allocation、完全 conformal 化)都是在给这个内核"加壳": - 多个 score:从二维分配变成高维分配(但可以用贪心或凸优化近似)。 - individualized allocation:从全局常数 \(\alpha_k\) 变成函数 \(\alpha_k(x)\)。 - 完全 conformal 化:去掉样本分裂,用 full conformal 的交换性论证替代。

这个内核的数学难点:交集的大小 \(\mathbb{E}[|\hat{C}_1 \cap \hat{C}_2|]\) 作为 \(\alpha_1\) 的函数,其表达式涉及两个 score 的联合分布,通常没有闭式解。作者的处理方式是:用经验分布近似,然后证明这个经验近似的最优分配渐近收敛到真实最优分配。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:在 conformal prediction 框架下,如何通过给多个 nonconformity score 分配不同的置信水平(α-allocation)并取交集,来构造比单一分数更小的预测集,同时保持覆盖保证。
  2. 核心工具/方法:将多重检验中的 α-allocation 思想引入 conformal inference;提出两种变体——样本分裂版(split conformal + α-allocation)和完全 conformal 版(full conformal + α-allocation);进一步提出 individualized allocation 以实现渐近条件覆盖。
  3. 主要结论:在温和条件下,α-allocation 聚合的预测集渐近地达到目标覆盖水平,且其经验大小严格小于(或等于)任何单一分数构造的预测集;individualized allocation 在局部层面进一步提升效率。

关键设定与假设

在第二节最小记号的基础上,补全完整设定:

  • 设定:\(K\) 个 nonconformity score 函数 \(S_1, \dots, S_K\),每个 score 对应一个预测模型。总错误率 \(\alpha \in (0,1)\)。
  • 假设 A1(score 的连续性):每个 \(S_k(X, Y)\) 的分布函数是连续的。这保证了分位数估计的渐近性质,避免了 ties 的处理。
  • 假设 A2(样本分裂):对于 split conformal 变体,训练数据被分成两部分——一部分用于拟合模型 \(\hat{\mu}_k\),另一部分用于计算经验分位数 \(\hat{q}_k\)。这是 split conformal 的标准假设。
  • 假设 A3(交换性):\((X_i, Y_i)_{i=1}^{n+1}\) 可交换。这是所有 conformal 方法的基础。
  • 假设 A4(individualized allocation 的光滑性):对于 individualized 变体,\(\alpha_k(x)\) 作为 \(x\) 的函数需要满足一定的光滑性条件(如 Lipschitz),以保证局部估计的一致性。

相比已有文献的放宽/强化: - 相比 Yang & Kuchibhotla (2021) 的 score 选择方法,本文不需要"选一个最好的 score",而是同时利用所有 score——这是一个放宽(更灵活)。 - 相比 Gasparin & Ramdas (2022) 的加权方法,本文的 α-allocation 有明确的有限样本覆盖保证(在 split 变体中)——这是一个强化(更强的理论保证)。 - 但本文的 individualized 变体只达到渐近条件覆盖,而非有限样本条件覆盖——这是一个妥协(与 Barber et al. 2021 的 impossibility result 一致)。

主要结果

定理 1(split conformal + α-allocation 的覆盖保证):在假设 A1-A3 下,对任意固定的分配 \((\alpha_1, \dots, \alpha_K)\) 满足 \(\sum_k \alpha_k = \alpha\),聚合预测集 \(\hat{C}_{\text{agg}} = \bigcap_k \hat{C}_k\) 满足:

\[\mathbb{P}(Y_{n+1} \in \hat{C}_{\text{agg}}) \geq 1 - \alpha\]
这是 Bonferroni 不等式的直接推论——每个 \(\hat{C}_k\) 覆盖概率 \(\geq 1-\alpha_k\),交集覆盖概率 \(\geq 1 - \sum_k \alpha_k = 1-\alpha\)。这个定理的价值在于它的简单性:任何分配都有效,问题只在于如何选最优分配。

定理 2(最优分配的存在性与渐近最优性):定义经验大小 \(\hat{L}(\alpha_1, \dots, \alpha_K) = \frac{1}{n} \sum_{i=1}^n |\bigcap_k \hat{C}_k(X_i)|\)。则存在一个分配 \((\hat{\alpha}_1^*, \dots, \hat{\alpha}_K^*)\) 最小化 \(\hat{L}\),且当 \(n \to \infty\) 时,这个经验最优分配收敛到真实最优分配(在适当的正则条件下)。证明路线:这是一个约束优化问题(\(\sum_k \alpha_k = \alpha\)),作者用 Lagrange 乘子法求解,然后证明经验目标函数的一致收敛性(uniform convergence),从而得到最优解的连续性。

定理 3(individualized allocation 的渐近条件覆盖):在假设 A4 下,令 \(\alpha_k(x)\) 为局部估计的最优分配,则:

\[\mathbb{P}(Y_{n+1} \in \hat{C}_{\text{agg}}(X_{n+1}) \mid X_{n+1} = x) \to 1 - \alpha\]
证明路线:这需要局部分位数估计的一致性。作者用核平滑(kernel smoothing)估计条件分位数,然后证明在带宽 \(h \to 0\) 且 \(nh \to \infty\) 时,局部最优分配收敛到真实条件最优分配。

证明路线与技术技巧

整体路线(3-5 步逻辑主干):

  1. 建立覆盖保证:先用 Bonferroni 不等式证明任何分配的有限样本覆盖下界。这是整个方法的"安全网"——无论分配如何,覆盖不会失效。
  2. 定义目标函数:将预测集大小(Lebesgue 测度或基数)作为目标函数,将覆盖约束(\(\sum_k \alpha_k = \alpha\))作为约束条件,形成约束优化问题。
  3. 求解最优分配:对目标函数求导,得到一阶条件(KKT 条件),证明最优分配满足某个"边际贡献均衡"条件——即每个 score 的边际大小减少量相等。
  4. 经验近似:用训练数据估计目标函数(经验均值),求解经验最优分配。这一步的关键是证明经验最优分配与真实最优分配的距离以 \(O_p(n^{-1/2})\) 收敛。
  5. 推广到 individualized:将全局分配 \(\alpha_k\) 替换为局部函数 \(\alpha_k(x)\),用核回归估计条件目标函数,证明渐近条件覆盖。

关键跳跃点:

  • 跳跃点 1:从"任何分配都有效"到"存在最优分配"。这一步需要目标函数的凸性(或至少拟凸性)。作者证明了在 score 分布连续且支撑集有界的条件下,目标函数是凸的。难点:凸性证明需要处理交集大小的非线性——两个预测集的交集大小不是各自大小的线性函数。
  • 跳跃点 2:从"经验最优"到"渐近最优"。这一步需要经验过程理论(empirical process theory)来控制目标函数的 uniform deviation。作者用到了 Donsker 类的结果,证明 \(\sup_{\alpha} |\hat{L}(\alpha) - L(\alpha)| = O_p(n^{-1/2})\)。
  • 跳跃点 3:从"全局"到"局部"。individualized allocation 需要估计条件目标函数 \(L_x(\alpha)\),这涉及非参数回归的收敛速度。作者用核估计,带宽选择 \(h \asymp n^{-1/(d+4)}\)(\(d\) 为 \(X\) 的维数),得到 \(O_p(n^{-2/(d+4)})\) 的收敛速度。

技术技巧点名:

  • Bonferroni 不等式:用于建立覆盖保证的下界。这是整个方法的基石——它保证了无论分配如何,覆盖不会失效。
  • Lagrange 乘子法:用于求解约束优化问题。将 \(\sum_k \alpha_k = \alpha\) 作为约束,构造 Lagrangian,求一阶条件。
  • 经验过程理论(Donsker 类):用于控制经验目标函数与真实目标函数的 uniform deviation。这是证明渐近最优性的关键工具。
  • 核平滑(kernel smoothing):用于 individualized allocation 中的条件分位数估计。带宽选择是标准的最小化 AMSE 准则。
  • delta 方法:用于从分位数估计的渐近正态性推导最优分配的渐近正态性。

真实例子与应用

论文包含合成数据和真实数据实验:

  • 合成数据:设置 \(K=3\) 个 score,分别对应线性回归、随机森林和神经网络预测器。结果显示,α-allocation 方法比"选最优单一 score"(用验证集选)的预测集大小减少约 15-25%,且覆盖水平维持在目标水平附近。这个例子想说明:即使没有一个 score 是"全能冠军",通过分配也能获得比任何单一 score 更好的结果。
  • 真实数据:使用 UCI 数据集(如 Boston Housing、Concrete Strength 等)。结果类似——α-allocation 在保持覆盖的同时,预测集大小比最佳单一 baseline 小 10-20%。这个例子想说明:方法在真实数据上有效,不是合成数据下的假象。

🔎 结论是否比证明窄

  • 窄的地方 1:定理 1 的覆盖保证是边际的,不是条件的。但论文在摘要和引言中多次使用"valid coverage"这一表述,可能让读者误以为是条件覆盖。实际上,individualized allocation 只达到渐近条件覆盖,且需要 A4 的光滑性假设——这在实践中难以验证。
  • 窄的地方 2:定理 2 的渐近最优性依赖于目标函数的凸性。但凸性只在 score 分布连续且支撑集有界的条件下证明。如果 score 分布有原子(如分类问题中的离散 score),凸性可能不成立,最优分配可能不存在或非唯一。论文没有讨论这一情况。
  • 窄的地方 3:实验中的 baseline 主要是"选最优单一 score",但没有与更复杂的聚合方法(如 e-value 聚合、加权组合)对比。作者在引言中声称这些方法"效率损失明显",但实验部分没有直接验证这一说法。

四、开放问题

  1. 有限样本条件覆盖的可能性:本文的 individualized allocation 只达到渐近条件覆盖。是否存在一种分配策略,能在有限样本下达到条件覆盖(或近似条件覆盖)?这扎根于定理 3 的渐近性质——作者没有给出有限样本界。要确认这是否是真 gap,去读 Barber et al. (2021) 的 impossibility result 和近期关于 conditional conformal 的工作(如 Gibbs et al. 2023)。

  2. 离散 score 的最优分配:当 score 分布有原子时(分类问题、计数数据),目标函数的凸性不成立,最优分配的存在性未解决。这扎根于定理 2 的凸性假设——作者没有处理非凸情形。去读近期关于离散 conformal 的工作(如 Dunn et al. 2022)。

  3. 与 e-value 框架的关系:本文的 α-allocation 与 Vovk & Wang 的 e-value 聚合在数学结构上有亲缘关系(都是分配错误率预算),但作者没有讨论这一联系。e-value 框架可能提供更一般的聚合理论,也可能揭示 α-allocation 的局限性。去读 Vovk & Wang (2021) 和近期 e-value 文献。

  4. 计算复杂度:当 \(K\) 很大时(如 \(K=100\) 个 score),求解最优分配需要高维优化。作者没有讨论计算可行性。这扎根于定理 2 的优化问题——作者只处理了 \(K\) 较小的情况。去读近期关于大规模 conformal 聚合的工作。

  5. 与多重检验的联系:α-allocation 本质上是将总错误率 \(\alpha\) 分配到 \(K\) 个测试上,这与 FWER 控制中的 Bonferroni 校正同构。作者没有深入探讨这一联系——多重检验中的更精细方法(如 Holm-Bonferroni、Benjamini-Hochberg)是否能为 α-allocation 提供更好的分配策略?去读多重检验文献,特别是关于错误率分配的最新进展。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论