跳转至

Conformal prediction with conditional guarantees

作者: Isaac Gibbs, John J Cherian, Emmanuel J Candès
来源: Journal of the Royal Statistical Society Series B
主题: 数理统计 / 假设检验
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么： 共形推断旨在为任意黑箱预测模型构造分布自由的预测集，并在有限样本下提供覆盖率保证。其根本统计问题是：如何在不依赖任何分布假设的前提下，不仅保证总体平均意义上的边际覆盖，还能让覆盖保证对特定个体或特定子群成立（即条件覆盖）。当前该方向处于“边际覆盖理论已成熟、条件覆盖的有限样本不可能定理已确立、介于两者之间的插值与近似条件覆盖正在活跃探索”的阶段。

发展脉络： - 奠基工作：Vovk 等人确立了共形推断的基本框架，证明了在数据可交换假设下，标准共形方法可提供精确的有限样本边际覆盖（\(1-\alpha\)）。Vovk (2012) 开始探索归纳共形推断的条件有效性，指出仅能控制无条件覆盖概率。 - 不可能定理与 Gap 确立：Barber, Candès, Ramdas, Tibshirani (2019) 证明了核心瓶颈：在没有分布假设的有限样本设定下，精确的条件覆盖是不可能的（任何满足精确条件覆盖的预测集必然对几乎所有 \(x\) 输出整个样本空间）。这一结论将领域推向了“寻找边际与条件之间可行折中”的路线。 - 主要进展（子群与偏移）： - 子群条件覆盖：Romano et al. (2020a) 的 Mondrian 共形推断和 Vovk 早期工作，只能在预先指定、互不相交的有限子群上提供条件覆盖保证。 - 协变量偏移下的覆盖：Tibshirani et al. (2019) 证明，若测试与训练的协变量密度比已知，加权共形推断可保证边际覆盖；Qiu et al. (2022) 和 Yang et al. (2022) 将此扩展至未知偏移，但均只针对单一、固定的偏移提供保证。 - 更强的多有效性保证：Jung et al. (2022) 提出 BatchGCP，在有限相交子群集合上同时实现组条件覆盖与阈值条件覆盖；Guan (2021) 提出局部化共形推断，在局部区域提供近似覆盖。 - 当前 Frontier 与本文位置：上述进展要么局限于有限离散子群，要么只针对单一偏移。本文填补了两者之间的空白：将条件覆盖重新表述为“对一族协变量偏移的覆盖”，定义了从边际到条件的插值谱系。对于有限维偏移族（如有限子群），给出对所有偏移的精确有限样本覆盖；对无限维族，量化覆盖误差并提供可调超参数。

子线索聚类： 1. 近似条件覆盖与适应性：致力于让预测集长度适应异方差或局部特征。Romano et al. (2019) 提出共形化分位数回归（CQR）；Sesia & Romano (2021) 用条件直方图实现自适应；Chernozhukov et al. (2021) 提出分布共形推断。这些方法有良好的经验条件覆盖，但理论上只保证边际覆盖。 2. 子群/多有效性覆盖：致力于在预定义的离散结构上提供硬理论保证。Romano et al. (2020b) 的等化覆盖；Jung et al. (2022) 的多有效性覆盖；Vovk (2012) 的 Mondrian 共形。这些方法无法处理连续或无限维的条件结构。 3. 协变量偏移下的覆盖：Tibshirani et al. (2019) 的加权共形；Yang et al. (2022) 的双重稳健校准（利用半参数有效影响函数）；Qiu et al. (2022) 的一步法。这些只针对单一偏移，无法同时保证对一族偏移的覆盖。

这个方向在追问的核心问题： 1. 在分布自由与有限样本约束下，条件覆盖的精确不可能性边界在哪里？（Barber et al. 2019 已给出绝对不可能定理，但近似条件的误差界尚未完全刻画） 2. 如何在边际覆盖与条件覆盖之间找到可计算、有理论保证的插值？ 3. 当面临未知协变量偏移时，如何在不依赖密度比精确估计的前提下，提供稳健的覆盖保证？

⚠️ 作者的 framing： - 作者将条件覆盖的缺口 frame 为“对一族协变量偏移的覆盖问题”，使得原本看似零散的子群覆盖与单一偏移覆盖，统一为同一个数学框架下的特例，从而让本文的“同时保证对所有偏移的覆盖”成为“显然的下一步”。 - 被淡化的竞争路线：Yang et al. (2022) 和 Qiu et al. (2022) 利用半参数效率理论（影响函数）处理未知偏移，本文仅在引言中提及它们“估计偏移”，但未将其半参数高阶校正思路与本文的有限样本加权框架进行理论对比（如效率损失或偏差-方差权衡）。 - 明显该引但未出现的文献：半参数效率界与高阶影响函数（HOIF）在处理无限维偏移/干扰参数时的理论界文献（如 Robins et al. 2008 的高阶影响函数理论）。本文在无限维情形下量化覆盖误差时，本质上遇到的是干扰参数问题，但未引用半参数界的经典文献来定位其误差界的紧致性。

张力： 未见明显对立引用。Barber et al. (2019) 的“不可能定理”与本文的“无限维族下存在可控误差”并不矛盾，前者说的是“精确”不可能，后者允许“近似”。但存在一个隐含张力：Barber et al. (2019) 指出任何非平凡预测集的条件覆盖误差下界为 \(O(1/\sqrt{n})\)，本文在无限维族下的误差界是否达到了这个 minimax 下界，文中未明确论证。

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

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

  • 符号与指标：
  • \(X \in \mathcal{X}\)：协变量（特征），\(Y \in \mathcal{Y}\)：响应变量。
  • \(n\)：校准集样本量，\(m\)：测试集样本量。
  • \(\alpha \in (0,1)\)：目标误覆盖率（如 \(\alpha=0.1\) 则目标覆盖 \(90\%\)）。
  • \(\mathcal{W}\)：协变量偏移函数类（即本文核心研究对象），\(w: \mathcal{X} \to \mathbb{R}_{\ge 0}\) 为偏移函数。
  • 潜在/目标量：
  • \(\mathcal{C}(x)\)：给定协变量 \(x\) 时输出的预测集（本文要构造的对象）。
  • 条件覆盖率 \(P(Y \in \mathcal{C}(X) \mid X=x)\)：想要但观测不到的总体量，无法在有限样本下精确保证。
  • 模型与数据生成机制：
  • 训练数据 \((X_i, Y_i) \sim P\)，\(i=1,...,n\)；测试数据 \((X_{n+j}, Y_{n+j}) \sim Q\)，\(j=1,...,m\)。
  • \(P\) 与 \(Q\) 的关系：\(Q(x,y) = w(x) P(x,y) / E_P[w(X)]\)，即协变量偏移模型（条件分布 \(P(y|x)\) 不变，边际分布 \(X\) 改变）。当 \(w(x)=1\) 时，\(Q=P\)（无偏移，即标准共形设定）。
  • 可观测数据：
  • 校准集 \(\{(X_i, Y_i)\}_{i=1}^n\)（来自 \(P\)，完全观测）。
  • 测试集特征 \(\{X_{n+j}\}_{j=1}^m\)（来自 \(Q\)，观测到 \(X\) 但观测不到 \(Y\)）。
  • 偏移函数类 \(\mathcal{W}\)：作为先验知识给定（如“所有有界 Lipschitz 函数”或“指示特定子群的函数”），不观测测试集的 \(Y\)，也不直接观测 \(Q\) 的密度。

第二步：最小内核——有限子群下的精确覆盖

剥掉所有无限维、Lipschitz 类等一般性设定，支撑本文的最小内核是：将条件覆盖转化为对一族特定协变量偏移的覆盖，并在有限维偏移类下，通过加权分位数同时实现精确有限样本保证。

最简特例：有限子群条件覆盖（\(\mathcal{W}\) 为有限指示函数集）

假设我们只关心两个预定义子群（如性别男/女）的条件覆盖。设 \(\mathcal{W} = \{w_1, w_2\}\)，其中 \(w_1(x) = \mathbb{I}(x \in \text{男})\), \(w_2(x) = \mathbb{I}(x \in \text{女})\)。

  1. 要证的命题退化成什么： 对任意 \(w \in \{w_1, w_2\}\)，要求 \(P_{Q_w}(Y \in \mathcal{C}(X)) \ge 1-\alpha\)，其中 \(Q_w\) 是偏移后的分布。由于 \(w\) 是子群指示函数，\(P_{Q_w}(Y \in \mathcal{C}(X))\) 正是子群内的条件覆盖率 \(P(Y \in \mathcal{C}(X) \mid X \in \text{该子群})\)。目标：构造一个统一的 \(\mathcal{C}(x)\)，使得男性和女性的覆盖率同时精确达到 \(1-\alpha\)。

  2. 证明怎么走、为什么成立：

  3. 标准共形的困境：标准共形取校准集残差的 \((1-\alpha)(1+1/n)\) 分位数 \(\hat{q}\) 作为阈值，保证 \(P(Y \in \mathcal{C}(X)) \ge 1-\alpha\)（边际覆盖）。但若男性残差普遍偏大，男性的条件覆盖率可能远低于 \(1-\alpha\)；女性可能远高于 \(1-\alpha\)。
  4. 本文的关键想法：对每个偏移 \(w_k\)，定义加权分位数 \(\hat{q}_k\)。在校准集上，给样本 \(i\) 分配权重 \(w_k(X_i)\)（男性样本在 \(w_1\) 下权重为 1，女性为 0；反之亦然）。寻找阈值 \(\hat{q}_k\)，使得加权经验覆盖率恰为 \(1-\alpha\)：
    \[\frac{\sum_{i=1}^n w_k(X_i) \mathbb{I}(V_i \le \hat{q}_k) + w_k(X_{n+j}) \mathbb{I}(V_{n+j} \le \hat{q}_k)}{\sum_{i=1}^n w_k(X_i) + w_k(X_{n+j})} \ge 1-\alpha\]
    （其中 \(V\) 为非一致性分数，越小越好）。
  5. 核心跳跃：由于 \(\mathcal{W}\) 是有限的（维度 \(K=2\)），我们可以同时求解 \(K\) 个加权分位数 \(\hat{q}_1, \hat{q}_2\)。因为加权经验分布是离散的，且不同 \(w\) 下的加权样本有重叠，关键在于证明：存在一个统一的预测集 \(\mathcal{C}(x) = \{y: V(x,y) \le \hat{q}(x)\}\)，其中 \(\hat{q}(x)\) 根据 \(x\) 所属子群选择对应的 \(\hat{q}_k\)，能同时满足所有 \(K\) 个加权覆盖约束。
  6. 为什么成立（技术直觉）：这本质上是将共形推断的“单分位数校准”推广为“多约束同时校准”。在有限维下，由于每个 \(w_k\) 只激活一部分样本，加权分位数 \(\hat{q}_k\) 的计算互不干扰（在指示函数下完全解耦），且每个 \(\hat{q}_k\) 的有限样本覆盖保证由加权可交换性直接得出（Tibshirani et al. 2019 的加权共形定理）。因此，只要对每个子群独立运行一次加权共形，即可同时保证所有子群的精确覆盖。

在这个最简特例中，本文的数学本质是：将条件覆盖的不可达目标，通过“偏移函数”的参数化，转化为有限个加权边际覆盖约束的联立求解问题。无限维情形的困难，正是来自于这有限个约束变成了无限个，导致联立求解不可行，必须引入近似与误差量化。

三、这篇论文做了什么

三句话： ① 研究了分布自由预测集在有限样本下如何同时满足一族协变量偏移下的覆盖保证（插值边际与条件覆盖）； ② 核心工具是将条件覆盖重构为对偏移族的加权覆盖，并利用校准集上的加权分位数校准与 McShane-Whitney 扩展定理构造预测集； ③ 主要结论是：对有限维偏移族可实现精确有限样本覆盖，对无限维族可量化覆盖误差并由超参数控制误差界。

关键设定与假设： - 偏移族 \(\mathcal{W}\)：核心设定。\(\mathcal{W}\) 是一族从 \(\mathcal{X}\) 到 \(\mathbb{R}_{\ge 0}\) 的函数。有限维情形（如有限子群指示函数、线性函数族）与无限维情形（如所有有界 Lipschitz 函数、所有有界函数）有本质不同。 - 加权可交换性：假设校准集与测试点在加权意义下可交换，即 \((w(X_1),...,w(X_n), w(X_{n+j}))\) 的联合分布在对应权重下对称。这是 Tibshirani et al. (2019) 的标准假设，本文直接继承，未作放宽。 - 非一致性分数：给定任意黑箱模型输出的分数 \(V(x,y)\)（如残差绝对值），假设 \(Y\) 越符合预测则 \(V\) 越小。这是共形推断的标准设定，本文的构造完全依赖于 \(V\) 的选择，好的 \(V\)（如 CQR 分数）决定预测集的适应性长度。

主要结果：

  1. 定理 1（有限维偏移族的精确覆盖）：
  2. 陈述：若 \(\mathcal{W}\) 的维度有限（如包含 \(K\) 个函数），存在预测集构造 \(\mathcal{C}(x)\)，使得对所有 \(w \in \mathcal{W}\)，在有限样本下精确满足 \(P_{Q_w}(Y \in \mathcal{C}(X)) \ge 1-\alpha\)。
  3. 直觉：对每个 \(w\) 计算加权分位数，由于 \(K\) 有限，可独立校准 \(K\) 次，拼装成最终预测集。
  4. 必要条件：校准集样本量 \(n\) 需足够大，使得每个 \(w\) 激活的加权样本数不为零。

  5. 解决的技术难点：打破了“精确条件覆盖不可能”的魔咒，关键在于目标不是“对所有 \(x\) 的条件覆盖”，而是“对 \(\mathcal{W}\) 中所有 \(w\) 的覆盖”，后者在有限 \(K\) 下是有限个约束，可行。

  6. 定理 2-3（无限维偏移族的误差量化）：

  7. 陈述：对无限维 \(\mathcal{W}\)（如 Lipschitz 类），精确覆盖不可能，但本文构造的预测集对任意 \(w \in \mathcal{W}\) 的覆盖误差有界：\(P_{Q_w}(Y \in \mathcal{C}(X)) \ge 1-\alpha - \epsilon(\mathcal{W}, n, \lambda)\)，其中 \(\lambda\) 是可调超参数，\(\epsilon\) 是可计算的误差上界。
  8. 直觉：无限维族无法逐一校准，但通过选取一个“代表性”的有限子集 \(\mathcal{W}_0\) 进行校准，然后利用 \(\mathcal{W}\) 的结构（如 Lipschitz 连续性），将 \(\mathcal{W}_0\) 的覆盖保证“平滑扩展”到整个 \(\mathcal{W}\)。误差 \(\epsilon\) 取决于 \(\mathcal{W}\) 的复杂度与 \(\mathcal{W}_0\) 的覆盖半径。
  9. 必要条件：\(\mathcal{W}\) 需有特定的函数类结构（如 Lipschitz 常数有界），且非一致性分数函数需满足相应的平滑性。
  10. 解决的技术难点：将无限维干扰参数（偏移函数）的覆盖误差，归结为有限维校准点的插值误差，并用 McShane-Whitney 扩展定理控制最坏情况下的误差衰减。

证明路线与技术技巧：

  • 整体路线（5步）：
  • 重构目标：将条件覆盖 \(P(Y \in \mathcal{C}(X) \mid X=x) \ge 1-\alpha\) 写成等价形式：对偏移 \(w(x)\)，\(E_{P}[w(X)\mathbb{I}(Y \in \mathcal{C}(X))] / E_{P}[w(X)] \ge 1-\alpha\)。
  • 加权分位数校准：对给定的 \(w\)，在校准集上计算加权经验分布，取其 \((1-\alpha)\) 分位数 \(\hat{q}_w\)，由加权可交换性保证对该 \(w\) 的覆盖。
  • 多约束联立（有限维）：对 \(\mathcal{W}=\{w_1,...,w_K\}\)，计算 \(K\) 个分位数 \(\hat{q}_{w_k}\)，构造 \(\hat{q}(x) = \max_{k} \{ \hat{q}_{w_k} : w_k(x) > 0 \}\)（取最大值以确保所有约束同时满足）。
  • 连续扩展（无限维）：对无限维 \(\mathcal{W}\)，选取有限网格 \(\mathcal{W}_0\)，计算 \(\hat{q}_{w_0}\)。定义 \(\hat{q}(x) = \sup_{w_0 \in \mathcal{W}_0} \{ \hat{q}_{w_0} - \lambda \|w_0 - w_x\| \}\)，其中 \(w_x\) 是理想中针对 \(x\) 的偏移，\(\lambda\) 是惩罚超参数。

  • 误差控制：利用 \(\mathcal{W}\) 的 Lipschitz 性质与 McShane 扩展，证明上述 \(\hat{q}(x)\) 对任意 \(w \in \mathcal{W}\) 的覆盖缺失不超过 \(\lambda \cdot \text{直径}(\mathcal{W})\) 级别的量。

  • 关键跳跃点：

  • 从“单偏移的加权分位数”到“多偏移的联立保证”的跳跃：作者发现，要同时满足多个 \(w\) 的覆盖，预测集的阈值必须取所有相关 \(w\) 对应阈值的上确界（max）。这会导致预测集变宽（保守），但这是有限样本精确保证的必然代价。

  • 无限维下的扩展跳跃：如何用有限网格 \(\mathcal{W}_0\) 的分位数去定义未校准偏移 \(w\) 的分位数？作者引入了带 \(\lambda\) 惩罚的下确界/上确界构造，这是全文最吃功夫的地方，直接决定了误差界的形式。

  • 技术技巧点名：

  • 加权共形分位数：源自 Tibshirani et al. (2019)，用于在校准集上实现单一偏移下的精确覆盖，本文作为基础模块。
  • McShane-Whitney 扩展定理：经典实分析工具（McShane 1934, Whitney 1934），用于将定义在有限网格 \(\mathcal{W}_0\) 上的分位数函数 \(\hat{q}_{w_0}\)，保 Lipschitz 常数地扩展到整个 \(\mathcal{W}\) 上，从而构造全局 \(\hat{q}(x)\)。
  • 小球方法：源自 Mendelson (2014)，本文在证明无限维类的覆盖误差界时，引用其定理控制经验过程的下界偏差，用于证明加权分位数在校准集上的集中性（避免依赖亚高斯尾假设，适应重尾分布）。

真实例子与应用： - Starcraft II 数据集（子群条件覆盖）：预测玩家行为，将地图难度（Easy/Hard）作为预定义子群。本文方法在两个子群上均实现精确 90% 覆盖，而标准共形在 Hard 子群上覆盖不足（约 85%），在 Easy 上过度覆盖（约 93%）。 - RxRx1 数据集（无限维偏移/协变量偏移）：来自 WILDS 基准（Koh et al. 2021），预测细胞反应，面临实验批次偏移。本文将偏移建模为 Lipschitz 类，通过调整 \(\lambda\)，在保持总体覆盖 90% 的同时，将最坏批次（偏移最大）的覆盖缺失从标准共形的 10% 以上降至约 3-5%。 - 想说明什么：1) 有限维下精确条件覆盖的可行性及与标准共形的对比优势；2) 无限维下 \(\lambda\) 参数对误差的直观控制作用，展示在真实协变量偏移中，无需知道精确密度比即可显著改善最坏情况覆盖。

🔎 结论是否比证明窄： - 本文在无限维情形下声称“ practitioner 可以通过 \(\lambda\) 控制误差”，但定理给出的误差界 \(\epsilon\) 依赖于 \(\mathcal{W}\) 的 Lipschitz 常数与直径，这些在真实数据中是未知且不可估的。定理严格证明了“若 \(\mathcal{W}\) 满足某 Lipschitz 条件，则误差 \(\le \epsilon\)”，但被泛泛 claim 为“可控制的误差”，回避了 \(\mathcal{W}\) 结构假设本身的不可检验性。 - 引言中提及本文方法“可直接嵌入现有分割共形推断流程”，但理论证明中要求 \(\mathcal{W}_0\) 网格的选取依赖对 \(\mathcal{W}\) 结构的先验知识，这在黑箱流程中并非完全“无需假设”。

四、开放问题（点到为止）

  1. 无限维偏移下的 minimax 最优性：本文给出的覆盖误差界 \(\epsilon(\mathcal{W}, n, \lambda)\) 是否在 minimax 意义下紧致？Barber et al. (2019) 给出条件覆盖误差的 \(O(1/\sqrt{n})\) 下界，本文的界是否匹配此速率？（扎根：Theorem 3 的误差界形式与 Barber et al. 2019 的 Theorem 2 下界对比）
  2. 偏移族 \(\mathcal{W}\) 的数据驱动选取与检验：本文假设 \(\mathcal{W}\) 为先验给定，真实数据中如何根据校准集选取 \(\mathcal{W}\) 并保证选取过程不破坏覆盖保证？（扎根：Section 5 讨论无限维类时，\(\mathcal{W}_0\) 网格的选取依赖先验，未讨论数据驱动的 \(\mathcal{W}\) 选取）
  3. 与半参数效率理论的结合：在未知协变量偏移下，Yang et al. (2022) 利用影响函数实现了双重稳健校准，本文的加权分位数扩展是否可嵌入 HOIF 框架以减小高维偏移下的误差？（扎根：引言提及 Yang et al. 2022 仅在“估计偏移”层面，未在理论层面对比半参数效率界）
  4. 最坏偏移下的计算复杂度：当 \(\mathcal{W}\) 为无限维时，求解 \(\hat{q}(x) = \sup_{w_0} \{\hat{q}_{w_0} - \lambda \|w_0 - w_x\|\}\) 的计算成本如何？是否存在统计-计算权衡？（扎根：Section 4 构造 \(\hat{q}(x)\) 的 sup 运算，在连续 \(\mathcal{W}\) 下可能需遍历网格）

Maintained by 陈星宇 · Homepage · Source on GitHub

评论