跳转至

Conformal Prediction Through the Lens of Hypothesis Testing: Universality, Impossibility, and Optimality

作者: Ryan J. Tibshirani, Rina Foygel Barber, Aaditya Ramdas
主题: 数理统计 / 假设检验
相关性: 7/10
链接: https://arxiv.org/abs/2608.27310

一、领域脉络与小综述

这个方向是什么

本文研究的子方向是共形预测（Conformal Prediction）的理论基础。共形预测是一种无分布（distribution-free）的预测方法，它能在几乎不依赖数据生成分布假设（仅需可交换性）的前提下，为新的观测值构造一个预测集，并保证有限样本下的边际覆盖概率。该方向的核心统计问题是：在仅假设数据可交换（或i.i.d.）时，如何构造预测集，使其覆盖概率有有限样本保证，同时尽可能提高效率（即缩小预测集的平均大小）？ 当前该领域已相当成熟，有大量算法变体和应用，但其理论根基——特别是与经典假设检验理论的严格联系——仍有待系统梳理。

发展脉络（history）

本文的introduction和参考文献勾勒出一条清晰的脉络：

  1. 奠基工作（1990s-2000s）：Vovk及其合作者（Vovk et al., 1999; Shafer & Vovk, 2008）开创了共形预测。他们最初就将共形预测定义为“反演p值”的过程，并频繁将其与Gosset、Fisher、Neyman等人的早期工作联系起来（见本文第1节引用）。Shafer & Vovk (2008) 的教程是这一时期的标志性综述，系统介绍了共形预测的在线设定和基本理论。留下的口子：虽然他们提到了与假设检验的类比，但并未将这一联系形式化到足以推导新结果的程度。

  2. 统计文献的引入与明确化（2010s）：Lei等人（Lei et al., 2014; Lei & Wasserman, 2014; Lei et al., 2018）将共形预测引入主流统计学界。他们明确将共形预测集解释为对原假设 \(H_0: Y_{n+1} = y\) 的检验的反演（见本文第1节引用）。Lei et al. (2018) 是这一时期的代表作，系统比较了全共形和分裂共形方法，并讨论了渐近条件覆盖。留下的口子：他们关注的是对单个新观测值 \(Y_{n+1}=y\) 的检验，而非对整体数据可交换性的检验。这一视角差异是本文的出发点。

  3. 理论深化与统一（2020s至今）：Angelopoulos et al. (2025) 的书籍和Barber & Tibshirani (2026) 的工作代表了当前的前沿。前者系统整理了共形预测的证明策略；后者提出了一个统一框架，将标准共形、加权共形、非可交换共形等方法都视为反演基于“部分信息”的假设检验。留下的口子：Barber & Tibshirani (2026) 的框架是通用的，但本文作者认为，对于标准共形预测本身，一个更贴近经典假设检验形式化框架的视角（即检验整体可交换性）能带来更直接的理论收益。

  4. 本文的位置：本文（Tibshirani, Barber, Ramdas, 2026）位于这条脉络的“理论再审视”节点。它不提出新算法，而是将共形预测重新解释为对“n+1个样本联合分布可交换性”这一原假设的置换检验的反演。这一视角转换使得经典假设检验理论（Neyman-Pearson引理、Neyman结构、Le Cam-Kraft定理）可以直接、精确地翻译为共形预测的结论，从而复现了已知的普适性和不可能性结果，并推导出一个新的有限样本最优性结果。

子线索聚类

这些被引文献大致落在以下子线索上：

  • 标准共形预测的理论与算法：Vovk et al. (1999, 2022), Shafer & Vovk (2008), Lei et al. (2018), Angelopoulos et al. (2025)。这一簇关注在可交换性假设下，如何构造预测集并保证边际覆盖。核心工具是置换检验和p值反演。
  • 条件覆盖与效率：Lei & Wasserman (2014), Lei et al. (2014), Sadinle et al. (2019), Izbicki et al. (2020)。这一簇研究如何使预测集在给定协变量 \(X_{n+1}\) 时也具有（渐近）条件覆盖，或如何通过最优得分函数（如逆条件密度）提高效率。核心工具是密度估计和Neyman-Pearson引理（在渐近或oracle层面）。
  • 统一框架与扩展：Barber & Tibshirani (2026), Zhang & Zhao (2023), Nair & Janson (2026)。这一簇试图用更抽象的假设检验语言（如条件随机化检验、部分信息）来统一共形预测的各种变体，并将其扩展到非可交换数据（如自适应收集的数据）。
  • 经典假设检验理论：Neyman & Pearson (1933), Lehmann & Scheffé (1950), Kraft (1955), Lehmann & Romano (2022)。这是本文借用的理论工具库，而非共形预测文献本身。它们提供了Neyman结构、有界完全性、最不利分布等核心概念。

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

  1. 覆盖保证：在仅假设可交换性时，如何构造预测集使其有限样本覆盖概率至少为 \(1-\alpha\)？——已由标准共形预测完美解决。
  2. 效率（预测集大小）：在所有满足覆盖保证的方法中，哪个方法能给出最小的平均预测集？——本文的Theorem 7给出了有限样本下的精确答案（逆条件密度得分）。
  3. 条件覆盖的可能性：能否在无分布假设下，保证给定 \(X_{n+1}=x\) 的条件覆盖？——已知不可能（Theorem 5），除非预测集是平凡的。
  4. 普适性：所有满足覆盖保证的方法，是否必然具有共形预测的形式？——是的（Theorem 3）。

已知瓶颈：条件覆盖的不可能性是根本瓶颈；有限样本最优性结果依赖于已知条件密度 \(p_{Y|X}\)，而实际中该密度未知，需要估计，这引入了估计误差与效率之间的权衡。

⚠️ 作者的 framing

  • 作者把缺口 frame 成什么：作者认为，虽然共形预测与置换检验的联系广为人知，但大多数文献（包括Lei et al. 2018）将其视为对“\(Y_{n+1}=y\)”这一假设的检验。作者提出，应将其视为对“\(Z_1, \ldots, Z_{n+1}\) 联合分布可交换”这一原假设的检验。这一“简单”的视角转换（见第2.3节）使得经典假设检验理论（Neyman结构、有界完全性、Neyman-Pearson引理）可以直接、精确地应用于共形预测，从而“直接翻译”出普适性、不可能性和最优性结果。作者强调，这些不是类比，而是直接推导。
  • 哪些竞争路线被他淡化或回避了：作者明确将本文限定于“标准共形预测”（即可交换数据下的基本方法），回避了Barber & Tibshirani (2026) 中讨论的加权共形、非可交换共形等更广泛的变体。作者在第7节（Discussion）中承认，假设检验工具应能扩展到这些变体，但本文不处理。此外，作者淡化了实际中如何估计最优得分函数的问题——Theorem 7假设 \(p_{Y|X}\) 已知，而实际中这是一个困难的非参数估计问题。
  • 什么明显该被引 / 该存在、却没出现在 intro 里？：未见明显缺失。本文的引用覆盖了共形预测的奠基工作、统计文献中的关键进展、以及经典假设检验理论的核心文献。一个可能的补充是更系统地引用关于经验过程或U-统计量在共形预测中应用的工作，但这并非本文核心。

张力

未见明显对立引用。被引工作之间在基本结论上是一致的（如覆盖保证、条件覆盖的不可能性），只是在视角和推广方向上有所不同。

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

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

  • 符号：
    • \(Z_i = (X_i, Y_i)\)：第 \(i\) 个样本，包含协变量 \(X_i\) 和响应 \(Y_i\)。
    • \(n\)：训练样本量。\(n+1\) 是总样本量（包括新观测）。
    • \(X_{n+1}\)：新观测的协变量（已知）。
    • \(Y_{n+1}\)：新观测的响应（未知，待预测）。
    • \(C_n(X_{n+1})\)：基于前 \(n\) 个样本和 \(X_{n+1}\) 构造的预测集，是 \(Y_{n+1}\) 可能取值的集合。
    • \(\alpha \in [0, 1]\)：预设的误差水平。目标是 \(P(Y_{n+1} \in C_n(X_{n+1})) \ge 1-\alpha\)。
    • \(s_i^y\)：当假设 \(Y_{n+1}=y\) 时，第 \(i\) 个样本的“符合度分数”（conformity score）。分数越低，表示该样本越“符合”整体模式。
    • \(U = \langle Z \rangle\)：样本集合 \(Z = (Z_1, \ldots, Z_{n+1})\) 的多重集（multiset），即不考虑顺序的样本集合。这是一个充分统计量。
    • \(\phi(Z)\)：一个检验函数，\(\phi(Z)=1\) 表示拒绝原假设，\(\phi(Z)=0\) 表示不拒绝。
    • \(p\)：置换检验的p值。
    • \(\mu\)：响应空间 \(\mathcal{Y}\) 上的一个测度（如Lebesgue测度或计数测度），用于衡量预测集的大小（效率）。
  • 模型：
    • 数据生成机制：假设 \((Z_1, \ldots, Z_{n+1})\) 是可交换的（exchangeable），即其联合分布在任意排列下不变。这比i.i.d.假设更弱。在本文大部分讨论中，进一步假设它们是i.i.d.的，即 \(Z_i \sim P_{X,Y}\)。
    • 已知量：样本量 \(n\)，误差水平 \(\alpha\)，一个用于计算分数的算法 \(A\) 和损失函数 \(\ell\)（或更一般的对称得分函数 \(s\)）。
    • 待估对象：预测集 \(C_n(X_{n+1})\)。它不是一个参数，而是一个集合值估计量。
  • 可观测数据：
    • 可观测：前 \(n\) 个样本 \((X_1, Y_1), \ldots, (X_n, Y_n)\)，以及新观测的协变量 \(X_{n+1}\)。
    • 不可观测（潜在）：新观测的响应 \(Y_{n+1}\)。这正是我们要预测的对象。在构造预测集时，我们会“假装” \(Y_{n+1}=y\) 取遍所有可能的值，然后看哪个 \(y\) 能被接受。

第二步：讲最小内核

本文的核心数学思想可以浓缩为以下最简特例：

最简特例：假设 \(d=1\)（协变量是一维的），响应 \(Y\) 是连续的（\(\mathcal{Y} = \mathbb{R}\)），且我们使用一个极其简单的得分函数：绝对残差。即，我们有一个算法 \(A\)，它基于数据 \((z_1, \ldots, z_k)\) 输出一个条件均值预测器 \(\hat{f}(x)\)。得分函数定义为 \(s((x, y); z) = |y - \hat{f}(x)|\)。

在这个特例下，本文的核心思路是什么？

  1. 传统观点：对于每个候选值 \(y\)，我们构造一个“扩充”数据集 \(Z^y = (Z_1, \ldots, Z_n, (X_{n+1}, y))\)。然后，我们计算一个置换p值，检验原假设“\(Y_{n+1}=y\)”。如果p值大于 \(\alpha\)，我们就将 \(y\) 纳入预测集。这个p值是通过比较 \(Y_{n+1}\) 的得分 \(s_{n+1}^y\) 与所有 \(n+1\) 个得分的排序来计算的。

  2. 本文的新视角：我们不检验“\(Y_{n+1}=y\)”，而是检验一个更大的原假设：“整个数据集 \(Z^y = (Z_1, \ldots, Z_n, (X_{n+1}, y))\) 是可交换的”。注意，这个原假设是关于 \(n+1\) 个样本的联合分布的，而不是关于单个 \(Y_{n+1}\) 的。

  3. 为什么这个视角有用？

    • 普适性：经典假设检验理论（Lehmann & Romano, 2022, Theorem 4.3.2）告诉我们：对于一个足够“丰富”的原假设类（这里是所有可交换分布），一个检验要控制第一类错误，必须具有“Neyman结构”。对于可交换分布，这意味着检验必须基于多重集 \(U = \langle Z \rangle\) 进行条件化。而置换检验正是这样做的。因此，任何有效的预测集方法，本质上都必须是一个置换检验的反演。这就直接证明了共形预测的普适性（Theorem 3）。
    • 最优性：现在，我们想在所有有效的预测集方法中，找到效率最高的那个。效率由 \(E[\mu(C_n(X_{n+1}))]\) 衡量。通过一个巧妙的变换（公式25），这个问题等价于：在控制第一类错误（覆盖）的前提下，最大化对某个特定备择假设 \(Q\) 的检验功效（power）。这个备择假设 \(Q\) 对应于一个“理想”的分布，其中 \(Y_{n+1}\) 的分布由测度 \(\mu\) 决定。然后，Neyman-Pearson引理告诉我们，最优检验是似然比检验。对于我们的问题，这个似然比检验的统计量恰好是 \(1/p_{Y|X}(Y_{n+1}|X_{n+1})\)。因此，最优的预测集方法，就是使用逆条件密度作为得分函数的共形预测器（Theorem 7）。

一句话总结：本文的核心数学贡献是将共形预测的效率问题转化为一个经典的假设检验问题（控制第一类错误 vs. 最大化功效），从而直接应用Neyman-Pearson理论得到有限样本下的最优解。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：本文从假设检验的视角重新审视标准共形预测的理论基础，旨在用经典假设检验理论（Neyman结构、有界完全性、Neyman-Pearson引理）来统一解释和推导共形预测的普适性、不可能性和最优性。
  2. 核心工具/方法：核心工具是置换检验、Neyman结构（Theorem 2）、Le Cam-Kraft定理（Theorem 4）和Neyman-Pearson引理（Theorem 6）。方法上，作者将共形预测集 \(C_n(X_{n+1})\) 重新定义为对原假设“\(Z_1, \ldots, Z_{n+1}\) 可交换”的置换检验的反演。
  3. 主要结论：① 任何在可交换分布类上有效的预测集方法，必然等价于某个共形预测器（普适性，Theorem 3）。② 任何在i.i.d.分布类上满足条件覆盖（给定 \(X_{n+1}=x\)）的预测集方法，其效率不可能优于一个随机猜测的平凡方法（不可能性，Theorem 5）。③ 在所有在可交换分布类上有效的预测集方法中，效率最优的是使用逆条件密度 \(1/p_{Y|X}(y|x)\) 作为得分函数的共形预测器（最优性，Theorem 7）。

关键设定与假设

  • 可交换性：数据 \((Z_1, \ldots, Z_{n+1})\) 的联合分布在任意排列下不变。这是共形预测有效性的核心假设。本文的普适性和最优性结果均基于此。
  • 得分函数的对称性：标准共形预测要求得分函数 \(s((x,y); z)\) 对输入数据 \(z\) 的顺序不敏感（公式6）。本文指出，这一对称性并非有效性所必需，而是一个计算上的便利条件（见第2.2节末尾）。普适性结果（Theorem 3）的第一部分不要求此对称性。
  • 测度 \(\mu\) 的 \(\sigma\)-有限性：用于衡量预测集大小的测度 \(\mu\) 需要是 \(\sigma\)-有限的（如Lebesgue测度）。这在处理连续响应时是标准假设。
  • 条件密度的正性：最优性结果（Theorem 7）要求条件密度 \(p_{Y|X=x}(y) > 0\) 对所有 \(y\) 和几乎所有 \(x\) 成立。这是一个技术性假设，确保逆密度得分是良定义的。
  • 与已有文献的对比：相比Lei et al. (2018) 等工作的渐近最优性，本文的Theorem 7是有限样本的。相比Hoff (2023) 的有限样本结果，本文的约束集是“在可交换分布类上有效”，而Hoff的约束集是“在i.i.d.分布类上精确有效”。本文的约束集更弱（允许保守性），因此结论更强（最优性在所有有效方法中成立，而不仅仅是共形方法中）。

主要结果

  • Theorem 3 (Universality)：任何在可交换分布类上具有 \(1-\alpha\) 边际覆盖的预测集方法，必然可以表示为某个置换检验的反演，即具有共形预测的形式（公式16）。如果该预测集对前 \(n\) 个样本的顺序不变，则它等价于标准共形预测（公式15）。直觉：可交换分布类足够“丰富”，使得任何有效检验都必须基于多重集（Neyman结构），而基于多重集的检验就是置换检验。
  • Theorem 5 (Impossibility of Conditional Coverage)：假设 \(\mu(\mathcal{Y}) < \infty\)。任何在i.i.d.分布类上满足条件覆盖（给定 \(X_{n+1}=x\)）的预测集方法，其在任意非原子点 \(x_0\) 处的期望测度至少为 \(\mu(\mathcal{Y})(1-\alpha)\)。这意味着其效率不可能优于一个以概率 \(1-\alpha\) 输出整个 \(\mathcal{Y}\)、以概率 \(\alpha\) 输出空集的平凡方法。直觉：条件覆盖的要求过于严格，它等价于要求检验在由“点质量”构成的备择假设类上也有功效，而Le Cam-Kraft定理表明，由于该备择假设类与零假设类的凸包在总变差距离下不可区分，任何有效检验都必然是无功效的。
  • Theorem 7 (Optimality)：假设 \(\mu\) 是 \(\sigma\)-有限的，且 \(p_{Y|X=x}(y) > 0\)。在所有在可交换分布类上具有 \(1-\alpha\) 边际覆盖的预测集方法中，效率 \(E[\mu(C_n(X_{n+1}))]\) 由以下随机化共形预测器达到：
    \[C_n^*(X_{n+1}) = \left\{ y: \frac{1}{n+1} \sum_{i=1}^{n+1} \left[ \mathbf{1}\{s_i^y > s_{n+1}^y\} + V \cdot \mathbf{1}\{s_i^y = s_{n+1}^y\} \right] > \alpha \right\}\]
    其中 \(V \sim \text{Unif}[0,1]\)，得分函数为 \(s((x,y); z) = 1/p_{Y|X=x}(y)\)。直觉：通过公式(25)将效率问题转化为功效问题，然后应用Neyman-Pearson引理。最优检验的似然比统计量恰好是逆条件密度，因此最优得分函数就是逆条件密度。必要条件：需要知道真实的条件密度 \(p_{Y|X}\)。这是一个oracle结果。

证明路线与技术技巧

  • 整体路线：

    1. 建立对偶性：首先建立预测集与假设检验之间的对偶性（Proposition 1）。一个有效的预测集等价于一个有效检验的反演。
    2. 普适性证明：将“有效预测集”对应到“有效检验”。利用Neyman结构定理（Theorem 2），证明对于可交换分布类，任何有效检验都必须具有Neyman结构，即必须基于多重集 \(U\) 进行条件化。然后证明，基于多重集条件化的检验等价于置换检验。因此，任何有效预测集都等价于置换检验的反演，即共形预测。
    3. 不可能性证明：将“条件覆盖”对应到“在特定备择假设类上的有效性”。利用Le Cam-Kraft定理（Theorem 4），证明该备择假设类与零假设类的凸包在总变差距离下不可区分，因此任何有效检验在该备择假设下都是无功效的。这直接转化为预测集效率的下界。
    4. 最优性证明：将“效率”通过公式(25)转化为“功效”。问题变为：在控制第一类错误（对可交换分布）的前提下，最大化对特定备择假设 \(Q\) 的功效。这是一个经典的Neyman-Pearson问题。通过构造一个最不利分布（即均匀分布 \(P_u'\)），应用Neyman-Pearson引理（Theorem 6），得到最优检验是似然比检验，其统计量为 \(1/p_{Y|X}(Y_{n+1}|X_{n+1})\)。将该检验反演回预测集，即得到最优共形预测器。

  • 关键跳跃点：

    • 公式(25)：将效率 \(E[\mu(C_n)]\) 与备择假设 \(Q\) 下的第二类错误联系起来。这是整个最优性证明的枢纽，作者在致谢中提到是用AI brainstorm出来的。
    • 证明 \(U = \langle Z \rangle\) 是“单侧有界完全”的（Section 3）：这是应用Neyman结构定理的关键。作者证明了对于可交换分布类，该性质成立，但对于i.i.d.分布类则不成立（Appendix A.2）。这解释了为什么普适性结果依赖于可交换性，而非i.i.d.。
    • 构造最不利分布 \(P_u'\)（Section 6.1）：在应用Neyman-Pearson引理时，需要处理复合零假设。作者巧妙地证明了，对于给定的多重集 \(u\)，均匀分布 \(P_u'\) 就是最不利分布，从而将问题简化为一个点对点的检验问题。

  • 技术技巧点名：

    • Neyman结构：用于推导普适性。
    • Le Cam-Kraft定理：用于推导不可能性。
    • Neyman-Pearson引理：用于推导最优性。
    • 置换检验：作为连接共形预测与经典理论的桥梁。
    • 总变差距离：用于证明条件覆盖的不可能性。
    • 随机化检验：最优预测集涉及一个随机化变量 \(V\)，用于处理得分相等的情况，这是Neyman-Pearson引理的标准要求。

真实例子与应用

本文为纯理论工作，无实证例子。唯一的“例子”是第6.3节和Appendix A.6中用于说明最优得分（公式41）与student化得分（公式42）区别的一个模拟示例（图1）。该示例使用高斯异方差模型，展示了最优得分如何通过引入 \(\log \hat{\sigma}(x)\) 项来在高方差区域缩小预测集，从而在平均意义上更高效。这个例子想说明：最优得分函数（逆条件密度）在实践中可以通过一个“plug-in”策略来近似，并且这种近似与常见的启发式方法（如student化残差）有本质区别，能带来效率提升。

🔎 结论是否比证明窄

  • Theorem 7 (Optimality) 的结论是严格的，但它的适用范围比其陈述可能暗示的要窄。它假设条件密度 \(p_{Y|X}\) 是已知的。在实际中，这需要估计，而估计误差会破坏最优性。作者在第6.3节讨论了如何用估计的 \(\hat{f}\) 和 \(\hat{\sigma}\) 来近似，但这并非证明的一部分。因此，该定理是一个oracle最优性结果，而非一个可直接使用的算法。
  • Theorem 5 (Impossibility) 的结论是严格的，但它针对的是条件覆盖（给定 \(X_{n+1}=x\)）。它不排除在更弱的条件（如“近似条件覆盖”或“局部条件覆盖”）下存在非平凡方法。作者在讨论中未明确提及这一点，但这是文献中已知的（如Izbicki et al. 2020）。
  • 作者在第7节（Discussion）中承认，本文的结果仅限于标准共形预测，并推测假设检验工具可以扩展到更广泛的变体。这是一个conjecture，而非证明。

四、开放问题

  1. 最优得分函数的估计：Theorem 7 给出了oracle最优得分 \(1/p_{Y|X}\)。一个核心的开放问题是：当 \(p_{Y|X}\) 未知，需要用非参数或机器学习方法估计时，估计误差如何影响预测集的效率和覆盖？是否存在一个“估计-效率”的权衡，类似于半参数理论中的“偏差-方差”权衡？ 扎根于：Theorem 7 本身假设密度已知，而第6.3节的plug-in策略只是启发式讨论。
  2. 非可交换设定的最优性：本文的最优性结果依赖于可交换性假设。对于Barber & Tibshirani (2026) 中讨论的加权共形、非可交换共形等变体，是否存在类似的最优性结果？最优得分函数的形式会如何变化？ 扎根于：第7节（Discussion）提到“the relevance of hypothesis-theoretic tools should extend beyond the standard setting”。
  3. 条件覆盖的“近似”可能性：Theorem 5 证明了精确条件覆盖的不可能性。但文献中（如Izbicki et al. 2020）有方法能实现渐近条件覆盖。一个开放问题是：能否刻画在有限样本下，达到“近似条件覆盖”（如 \(P(Y_{n+1} \in C_n(x) | X_{n+1}=x) \ge 1-\alpha - \epsilon\)）所需的最小效率损失？ 扎根于：Theorem 5 的结论是“不可能”，但未给出“近似”情况下的量化下界。
  4. 普适性定理的逆否命题：Theorem 3 说“所有有效方法都是共形方法”。其逆否命题是“非共形方法必然无效”。一个有趣的开放问题是：是否存在非共形但有效的预测集方法？ 例如，通过使用不同于置换检验的检验（如基于鞅的检验）来反演。扎根于：Theorem 3 的证明依赖于Neyman结构，而Neyman结构要求零假设类足够“丰富”。对于更窄的零假设类（如参数模型），非共形方法（如基于t分布的预测区间）是有效的。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论