跳转至

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

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


一、领域脉络与小综述

这个方向是什么

共形预测(conformal prediction)是一套构造预测集的框架,在仅假设数据可交换(exchangeable)的条件下,保证有限样本的边际覆盖概率 \(P\{Y_{n+1} \in C_n(X_{n+1})\} \ge 1-\alpha\),无需对数据生成分布做任何参数假设。它通过一个“非符合性得分”(nonconformity score)衡量新样本与已有数据的吻合程度,并将得分分位数作为阈值。过去十年,共形预测已成为机器学习不确定性量化的核心工具,但其理论基础长期被视为独立于经典统计推断。本文的核心贡献是将共形预测重新置于经典假设检验框架下,证明其普适性、不可能性和最优性均可由Neyman、Lehmann、Scheffé、Kraft、Le Cam等人的经典理论直接导出。

发展脉络

  • 奠基工作:Vovk等人在1990年代末提出共形预测(Vovk et al., 1999),Shafer & Vovk (2008) 的教程系统介绍了其思想。这些早期工作已强调与假设检验的联系(如Vovk et al., 2022第13.3章),但将共形预测视为对“\(H_0: Y_{n+1}=y\)”的逐点检验的逆。
  • 统计文献中的显式连接:Lei et al. (2013, 2014) 和 Lei & Wasserman (2014) 首次在统计期刊上明确将共形预测集描述为“inverting a test for the null hypothesis \(H_0: Y_{n+1}=y\)”。Lei et al. (2018) 进一步研究了分裂共形预测和条件覆盖。Sadinle et al. (2019) 在分类问题中推导了最优集值分类器的oracle形式(基于条件概率水平集)。
  • 当前frontier:Angelopoulos et al. (2025) 的书籍系统总结了共形预测的理论基础。Barber & Tibshirani (2026) 提出了一个统一框架,将多种共形变体(加权共形、非可交换共形等)视为基于部分信息的假设检验的逆。Hoff (2023) 利用充分统计量的完备性构造了贝叶斯最优预测集(Theorem 4.1),但局限于无协变量情形且效率定义是贝叶斯平均。Dandapanthula & Ramdas (2025) 和 Hore & Ramdas (2026) 在变点检测中提出了“共形Neyman-Pearson引理”。
  • 本文位置:作者声称,将共形预测重新解释为对“\(n+1\)个样本的联合分布可交换”这一原假设的置换检验的逆(而非对\(Y_{n+1}=y\)的检验),使得经典假设检验理论可以直接应用。由此,普适性(Theorem 3)和不可能性(Theorem 5, Corollary 1)成为经典定理的直接推论,而最优性(Theorem 7)是Neyman-Pearson引理在复合原假设下的应用,且是有限样本结果(区别于已有文献的渐近最优性)。

子线索聚类

  1. 共形预测的基础理论:Vovk et al. (1999, 2022), Shafer & Vovk (2008), Angelopoulos et al. (2025)。定义、有效性证明、扩展(分裂共形、加权共形等)。
  2. 与假设检验的显式联系:Lei et al. (2013, 2014, 2018), Lei & Wasserman (2014), Dobriban & Lin (2023), Hoff (2023), Zhang & Zhao (2023), Barber & Tibshirani (2026), Nair & Janson (2026)。这些工作将共形预测视为检验的逆,但大多针对“\(Y_{n+1}=y\)”原假设。
  3. 最优性研究:Sadinle et al. (2019)(分类,oracle水平集),Izbicki et al. (2020)(条件密度估计,渐近最优),Hoff (2023)(贝叶斯最优,有限样本但无协变量),Dandapanthula & Ramdas (2025)(变点检测,共形Neyman-Pearson引理)。这些结果在渐近或特定设定下指向逆条件密度得分。
  4. 不可能性结果:Vovk (2012)(条件覆盖不可能),Lei & Wasserman (2014) Lemma 1(条件覆盖导致平凡预测集)。本文用Kraft-Le Cam定理重新证明。

核心问题与瓶颈

  • 核心问题:① 如何构造有限样本有效的预测集?② 能否实现条件覆盖(给定\(X_{n+1}\))?③ 什么是最优的得分函数?④ 共形预测与经典统计推断(Neyman-Pearson、完备性)有何深层联系?
  • 已知瓶颈:条件覆盖(给定\(X_{n+1}=x\))在非参数设定下不可能非平凡(Vovk 2012; Lei & Wasserman 2014)。最优得分函数在渐近意义下是逆条件密度(\(1/p_{Y|X}\)),但有限样本最优性此前缺乏一般证明。

⚠️ 作者的framing

作者将缺口frame为:已有文献将共形预测与假设检验的联系视为“motivating principles”,但未将其作为严格的理论工具。本文声称“these are not just analogies, and core facts about hypothesis testing directly translate to conformal prediction”(Section 2.3末尾)。作者通过将原假设从“\(Y_{n+1}=y\)”改为“可交换性”,使得经典理论(Neyman结构、Kraft-Le Cam、Neyman-Pearson)可以直接套用。竞争路线(如Hoff 2023的贝叶斯最优框架)被淡化:作者指出Hoff的结果局限于无协变量且效率为贝叶斯平均,而本文的Theorem 7是频率学派有限样本最优性,且允许协变量。明显该被引但未出现:本文未引用近期关于“自适应共形预测”(如Gibbs & Candès, 2021)或“分布自由条件覆盖”的尝试(如Barber et al., 2021),但这些工作可能偏离本文的经典理论焦点。

张力

未见明显对立引用。所有被引工作均承认可交换性下边际覆盖的可行性,以及条件覆盖的不可行性。最优性方面,渐近结果一致指向逆条件密度,本文的有限样本结果与之兼容。


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

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

  • 符号:
  • \(Z_i = (X_i, Y_i)\),\(i=1,\dots,n+1\):第\(i\)个样本,\(X_i\)为协变量(可高维),\(Y_i\)为响应变量。
  • \(n\):训练样本数;\(n+1\):测试样本索引(\(Y_{n+1}\)未知)。
  • \(C_n(X_{n+1})\):基于\(X_{n+1}\)和\(Z_1,\dots,Z_n\)构造的预测集,是\(\mathcal{Y}\)的子集。
  • \(\alpha \in [0,1]\):预设错误率,要求\(P\{Y_{n+1} \in C_n(X_{n+1})\} \ge 1-\alpha\)。
  • \(s((x,y); z)\):得分函数,衡量点\((x,y)\)与数据集\(z\)的“非符合性”。通常要求对称性:\(s((x,y); z) = s((x,y); z_\sigma)\)对任意排列\(\sigma\)(即只依赖于多重集)。
  • \(U = \langle Z \rangle\):多重集(bag),即\(Z_1,\dots,Z_{n+1}\)的无序集合。它是可交换分布族的充分统计量。
  • \(\mu\):\(\mathcal{Y}\)上的\(\sigma\)-有限测度(如Lebesgue测度或计数测度),用于衡量预测集的大小(效率)。
  • \(p_{Y|X}(y|x)\):给定\(X=x\)时\(Y\)的条件密度(关于\(\mu\))。
  • 模型:数据\((Z_1,\dots,Z_{n+1})\)来自可交换分布,即联合分布在任意排列下不变。这比i.i.d.弱,但包含i.i.d.作为特例。没有参数形式假设。
  • 可观测数据:研究者实际观测到\(Z_1,\dots,Z_n\)和\(X_{n+1}\)。\(Y_{n+1}\)是未观测的,需要预测。潜在量:无,但得分函数\(s\)可能依赖于整个增广数据集(包括候选\(y\)),因此计算时需遍历所有\(y\)。

第二步:最小内核

考虑无协变量(即\(X\)退化)、样本量\(n=1\)、连续响应\(Y \in \mathbb{R}\)、测度\(\mu\)为Lebesgue测度、错误率\(\alpha=0.1\)。此时数据为\(Y_1\)(已知)和\(Y_2\)(未知),可交换性等价于\((Y_1,Y_2)\)的联合分布在交换下不变(即i.i.d.)。我们要构造预测集\(C(Y_1)\)使得\(P(Y_2 \in C(Y_1)) \ge 0.9\)。

经典共形预测的做法:选择一个得分函数,例如\(s(y; (y_1, y_2)) = |y - \text{median}(y_1, y_2)|\)?但更简单:取\(s(y; z) = y\)(即得分就是响应值本身)。对于候选\(y\),增广数据为\((Y_1, y)\)。计算置换p值:

\[p = \frac{1}{2} \left[ \mathbf{1}\{s(y; (Y_1, y)) \ge s(y; (Y_1, y))\} + \mathbf{1}\{s(Y_1; (y, Y_1)) \ge s(y; (Y_1, y))\} \right].\]
由于对称性,第一项恒为1,第二项为\(\mathbf{1}\{Y_1 \ge y\}\)。因此\(p = \frac{1}{2}(1 + \mathbf{1}\{Y_1 \ge y\})\)。当\(y \le Y_1\)时,\(p=1\);当\(y > Y_1\)时,\(p=0.5\)。取\(\alpha=0.1\),则\(p > 0.1\)对所有\(y\)成立?实际上\(p\)最小为0.5,因此所有\(y\)都被接受,预测集为整个实数轴。这显然效率极低。

本文的视角:将共形预测视为对可交换性原假设的置换检验的逆。原假设\(H_0\):\((Y_1, Y_2)\)来自可交换分布。对于每个候选\(y\),构造增广数据\((Y_1, y)\),检验该数据是否可交换。使用统计量\(T(z) = s(z_2; z)\)(即最后一个样本的得分)。置换p值为:

\[p = \frac{1}{2} \left[ \mathbf{1}\{T(Y_1, y) \ge T(Y_1, y)\} + \mathbf{1}\{T(y, Y_1) \ge T(Y_1, y)\} \right].\]
若\(s\)对称,则与上述计算一致。但本文的普适性定理(Theorem 3)说:任何在可交换分布族上达到覆盖\(1-\alpha\)的预测集,必须由某个得分函数\(s\)通过上述置换检验反演得到。也就是说,共形预测是唯一可能的方法。这个结论在\(n=1\)时也很直观:给定\(Y_1\),要构造\(Y_2\)的预测集,任何有效方法必须利用\((Y_1,Y_2)\)的对称性,即预测集只能依赖于\(Y_1\)和\(Y_2\)的排序信息。事实上,可以证明:若要求对所有可交换分布覆盖\(\ge 0.9\),则预测集必须几乎处处等于整个\(\mathbb{R}\)(因为任何非平凡区间都会在某些分布下覆盖不足)。这就是不可能性(Theorem 5)的雏形:条件覆盖(这里无协变量,条件覆盖退化为无条件)在非参数设定下必然导致平凡预测集。

最优性内核:假设我们已知条件密度\(p_{Y|X}\)(此处无\(X\),即\(p_Y\))。本文Theorem 7说:最优得分是\(s(y; z) = 1/p_Y(y)\)。在\(n=1\)时,使用该得分,预测集为:

\[C(Y_1) = \left\{ y : \frac{1}{2}\left[ \mathbf{1}\{1/p_Y(y) \ge 1/p_Y(y)\} + \mathbf{1}\{1/p_Y(Y_1) \ge 1/p_Y(y)\} \right] > \alpha \right\}.\]
简化得:\(C(Y_1) = \{ y : p_Y(y) \ge p_Y(Y_1) \}\)(当\(\alpha<0.5\)时)。这恰好是似然比检验的逆:接受那些比观测值\(Y_1\)更可能出现的\(y\)。这个预测集在期望Lebesgue测度下最小。这个例子揭示了最优得分与条件密度的直接联系。


三、这篇论文做了什么

三句话

  1. 研究问题:从假设检验的经典视角重新审视共形预测,证明其普适性(任何有效预测集必为共形类型)、不可能性(条件覆盖必然平凡)和最优性(逆条件密度得分达到有限样本最优效率)。
  2. 核心工具:Neyman结构定理(Theorem 2)、Kraft-Le Cam定理(Theorem 4)、Neyman-Pearson引理(Theorem 6),以及充分统计量(多重集)的有界完全性。
  3. 主要结论:Theorem 3(普适性)、Theorem 5 & Corollary 1(不可能性)、Theorem 7(最优性)。其中最优性结果是新的有限样本结果,不依赖于渐近近似。

关键设定与假设

  • 数据:\((Z_1,\dots,Z_{n+1})\)可交换(或i.i.d.)。记\(\mathcal{P}_{\text{exch}}\)为所有可交换分布类,\(\mathcal{P}_{\text{iid}}\)为所有i.i.d.分布类。
  • 预测集:任意映射\(C_n(X_{n+1})\),可等价写为\(C_n(X_{n+1}) = \{y: \phi(Z_1,\dots,Z_n,(X_{n+1},y)) = 0\}\),其中\(\phi\)是检验函数(取0表示接受)。
  • 得分函数:\(s((x,y); z)\)满足对称性(6):\(s((x,y); z) = s((x,y); z_\sigma)\)对任意排列\(\sigma\)。但普适性定理(Theorem 3)不要求对称性,仅要求预测集本身有效。
  • 效率度量:期望测度\(E_P[\mu(C_n(X_{n+1}))]\),其中\(\mu\)是\(\mathcal{Y}\)上的\(\sigma\)-有限测度。最优性定理(Theorem 7)要求\(\mu\)是\(\sigma\)-有限的,且条件密度\(p_{Y|X}(y|x) > 0\)对\(P_X\)-几乎每个\(x\)和所有\(y\)成立。
  • 与已有文献的对比:普适性结果已知(Vovk et al., 2022 Proposition 2.9; Angelopoulos et al., 2025 Theorem 9.7),但本文用经典Neyman结构理论重新证明。不可能性结果已知(Vovk 2012 Proposition 4; Lei & Wasserman 2014 Lemma 1),本文用Kraft-Le Cam定理证明。最优性结果是新的有限样本结果,区别于已有文献的渐近最优性(如Sadinle et al., 2019; Izbicki et al., 2020)或贝叶斯最优性(Hoff, 2023)。

主要结果

  • Theorem 3(普适性):若预测集\(C_n(X_{n+1})\)对所有可交换分布满足\(P\{Y_{n+1} \in C_n(X_{n+1})\} \ge 1-\alpha\),则它必为共形类型,即存在得分函数\(s\)使得\(C_n(X_{n+1}) = \{y: \text{置换p值} > \alpha\}\)。若\(C_n\)对前\(n\)个样本的顺序不变,则\(s\)可对称化。
  • 直觉:由Theorem 2,任何水平\(\alpha\)检验必须具有Neyman结构(条件于充分统计量\(U=\langle Z \rangle\)时错误率\(\le \alpha\))。对于可交换分布,\(U\)是充分且(单侧)有界完全的,因此Neyman结构等价于检验是置换检验。反演即得。
  • Theorem 5(不可能性,有限测度情形):假设\(\mu(\mathcal{Y}) < \infty\)。若预测集满足条件覆盖:\(P\{Y_{n+1} \in C_n(x) | X_{n+1}=x\} \ge 1-\alpha\)对所有\(x \in \text{supp}(P_X)\)和所有\(P \in \mathcal{P}_{\text{iid}}\)成立,则对任何非原子点\(x_0\),有\(E_P[\mu(C_n(x_0))] \ge \mu(\mathcal{Y})(1-\alpha)\)。即效率不比随机猜测(以概率\(1-\alpha\)输出整个\(\mathcal{Y}\),否则输出空集)好。
  • 直觉:条件覆盖等价于对一类分布\(\mathcal{P}_{\text{cond}}\)的边际覆盖。构造一个分布\(P_0 \in \mathcal{P}_{\text{cond}}\)使得其与备择\(Q_0\)(见(28))的全变差距离为0。由Kraft-Le Cam定理,任何水平\(\alpha\)检验的势不超过\(\alpha\),因此预测集效率下界为\(\mu(\mathcal{Y})(1-\alpha)\)。
  • Corollary 1(无限测度情形):若\(\mu(\mathcal{Y})=\infty\)且\(\sigma\)-有限,则\(E_P[\mu(C_n(x_0))] = \infty\)。即条件覆盖必然导致预测集几乎处处无穷大。
  • Theorem 7(最优性):固定\(P = P_{X,Y}^{n+1}\)(i.i.d.)。在所有对\(\mathcal{P}_{\text{exch}}\)达到覆盖\(1-\alpha\)的预测集中,最小化\(E_P[\mu(C_n(X_{n+1}))]\)的预测集是使用得分\(s((x,y); z) = 1/p_{Y|X}(y|x)\)的随机化共形预测器(见(37))。该预测器在期望测度下最优。
  • 直觉:效率最小化等价于势最大化。对于固定的多重集\(u\),条件分布\(Q_u\)(来自备择)与均匀排列分布\(P'_u\)(来自原假设)之间的Neyman-Pearson最优检验是随机化置换检验,统计量为\(1/p_{Y|X}\)。由于该检验不依赖于\(u\),整体最优。

证明路线与技术技巧

普适性(Theorem 3): 1. 由预测集定义检验\(\phi(Z) = 1\{Y_{n+1} \notin C_n(X_{n+1})\}\),覆盖条件等价于\(E_P[\phi(Z)] \le \alpha\)对所有\(P \in \mathcal{P}_{\text{exch}}\)。 2. 证明多重集\(U=\langle Z \rangle\)是\(\mathcal{P}_{\text{exch}}\)的充分统计量,且满足单侧有界完全性(19)。因此Theorem 2(Neyman结构定理)适用:\(\phi\)必须满足\(E[\phi(Z)|U=u] \le \alpha\)对几乎所有\(u\)。 3. 条件于\(U=u\)时,\(Z\)的条件分布是均匀排列。因此\(E[\phi(Z)|U=u] = \frac{1}{(n+1)!}\sum_{\sigma}\phi(z_\sigma) \le \alpha\)。这等价于\(\phi\)是置换检验(见(22)的证明)。 4. 反演得预测集形式。若预测集对前\(n\)个样本顺序不变,则得分函数可对称化,得到标准共形形式。

不可能性(Theorem 5): 1. 将条件覆盖转化为对\(\mathcal{P}_{\text{cond}}\)的边际覆盖((27))。 2. 定义备择分布\(Q_0 = P_{X,Y}^n \times (\delta_{x_0} \times \frac{\mu}{\mu(\mathcal{Y})})\)。效率\(E_P[\mu(C_n(x_0))] = \mu(\mathcal{Y}) \cdot E_{Q_0}[1-\phi(Z)]\)。 3. 构造\(P_0 \in \mathcal{P}_{\text{cond}}\):将\(x_0\)处的条件分布改为\(\mu/\mu(\mathcal{Y})\),其余不变。则\(P_0\)与\(Q_0\)的全变差距离为0(因为\(x_0\)是非原子点,修改不影响边际)。 4. 由Kraft-Le Cam定理(Theorem 4),任何在\(\mathcal{P}_{\text{cond}}\)上水平\(\alpha\)的检验,其势不超过\(\alpha + TV(\text{conv}(\mathcal{P}_{\text{cond}}), \{Q_0\}) = \alpha\)。因此\(E_{Q_0}[\phi(Z)] \le \alpha\),从而\(E_P[\mu(C_n(x_0))] \ge \mu(\mathcal{Y})(1-\alpha)\)。

最优性(Theorem 7): 1. 将效率写为\(E_P[\mu(C_n(X_{n+1}))] = E_{P_U}[h(\phi, U)]\),其中\(h(\phi, u) = \frac{1}{c_u (n+1)!} E_{Q_u}[1-\phi(Z)]\),\(Q_u\)是条件于\(U=u\)下来自备择\(Q\)的分布。 2. 固定\(u\),问题化为:在\(E_{P'}[\phi] \le \alpha\)对所有\(P' \in \mathcal{P}_{\text{exch}}\)的约束下,最大化\(E_{Q_u}[\phi]\)。 3. 证明均匀排列分布\(P'_u = \frac{1}{(n+1)!}\sum_{\sigma}\delta_{z_\sigma}\)是\(\mathcal{P}_{\text{exch}}\)相对于\(Q_u\)的最不利分布。即,若检验对\(P'_u\)水平\(\alpha\),则对全体\(\mathcal{P}_{\text{exch}}\)水平\(\alpha\)。 4. 应用Neyman-Pearson引理(Theorem 6):最优检验是似然比检验,似然比为\(q_u(z_\sigma)/p'_u(z_\sigma) \propto 1/p_{Y|X}(y_{\sigma(n+1)}|x_{\sigma(n+1)})\)。因此统计量取为\(T(z) = 1/p_{Y|X}(y_{n+1}|x_{n+1})\)。 5. 该检验是随机化置换检验(Proposition 2),且不依赖于\(u\),因此整体最优。反演得预测集形式(37)。

技术技巧: - 单侧有界完全性(19):比传统双侧定义更强,用于处理保守检验(允许\(E[\phi] \le \alpha\)而非严格等于\(\alpha\))。作者在Appendix A.2中说明,对于i.i.d.分布,多重集仅满足双侧完全性,因此Hoff (2023)的结果只能处理精确覆盖;而可交换分布族足够丰富,使得单侧完全性成立。 - Kraft-Le Cam定理:用于将不可能性转化为全变差距离的计算。关键步骤是构造\(P_0\)使得\(TV(P_0, Q_0)=0\),这依赖于非原子点假设。 - Neyman-Pearson引理在复合原假设下的应用:通过识别最不利分布(均匀排列分布),将复合原假设简化为点原假设。 - 随机化置换检验:用于处理得分相等时的离散性,保证精确水平\(\alpha\)。

真实例子与应用

图1:异方差高斯模型,\(n=500\),\(X \sim \text{Unif}[0,2\pi]\),\(Y|X \sim N(\sin(X), (\pi X/30)^2)\)。比较两种得分: - 学生化得分:\(s = |y - \hat{f}(x)| / \hat{\sigma}(x)\),其中\(\hat{f}=\sin\),\(\hat{\sigma}=\pi x/30\)(真实函数)。 - 高效得分(Theorem 7建议):\(s = (y-\hat{f}(x))^2/(2\hat{\sigma}^2(x)) + \log \hat{\sigma}(x)\)。 结果:高效得分产生的预测区间平均窄12.5%。该例子说明理论最优得分在实际中确实更高效,且揭示了学生化得分在异方差下并非最优(因为忽略了\(\log \sigma(x)\)项)。

🔎 结论是否比证明窄

  • Theorem 7假设条件密度\(p_{Y|X}(y|x) > 0\)对所有\(y\)和\(P_X\)-几乎每个\(x\)成立。若密度在某些点为零,则得分无穷,预测集定义需调整。作者未讨论此情形。
  • Theorem 7的效率度量是期望测度\(E[\mu(C_n)]\)。其他效率度量(如中位数测度、最坏情况测度)下的最优性未涉及。
  • 普适性定理(Theorem 3)的证明依赖于单侧有界完全性,而该性质对可交换分布族成立,但对i.i.d.分布族不成立(Appendix A.2)。因此,若将约束从“对所有可交换分布有效”改为“对所有i.i.d.分布有效”,则普适性可能不成立(即存在非共形但有效的预测集)。作者未明确讨论这一点,但Appendix A.2暗示了这种可能性。
  • 不可能性定理(Theorem 5)要求\(x_0\)是\(P_X\)的非原子点。若\(P_X\)有原子,则条件覆盖可能非平凡?作者未讨论。

四、开放问题

  1. 条件密度未知时的最优性:Theorem 7假设已知\(p_{Y|X}\)。实际中需估计,估计误差如何影响效率?能否建立非参数收敛速率下的有限样本最优性?扎根于Theorem 7的假设“已知密度”及Section 6.3的plug-in讨论。
  2. 非可交换数据下的普适性:本文的普适性依赖于可交换分布族的丰富性。对于非可交换数据(如时间序列、自适应收集数据),是否存在类似“任何有效预测集必为某种加权共形类型”的结果?扎根于Section 7第一段:“the relevance of hypothesis-theoretic tools should extend beyond the standard setting”。
  3. 条件覆盖的其他形式:Theorem 5针对“给定\(X_{n+1}=x\)”的条件覆盖。若要求“给定\(X_{n+1} \in A\)”(某集合)的条件覆盖,是否仍有不可能性?扎根于Theorem 5的证明中使用了非原子点假设。
  4. 其他效率度量下的最优性:Theorem 7使用期望测度。若使用中位数测度或最坏情况测度,最优得分是否仍为逆条件密度?扎根于Theorem 7的设定(效率定义为期望测度)。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论