跳转至

Conformal ordering: Distribution-free predictive inference for orders and ranks

作者: Yonghoon Lee, Zhimei Ren
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://arxiv.org/abs/2610.40340


一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是:在分布自由的框架下,如何对多个未观测结果的排序(ordering)与秩(rank)进行预测性推断。具体而言,给定训练数据、校准数据和一组新的测试对象(及其协变量),目标是构造一个对测试对象真实排序的不确定性量化——既可以是"哪些对象之间的相对顺序可以被置信地确定"(图结构),也可以是"每个对象的真实秩落在哪个区间内"(预测区间)。该问题的核心困难在于:排序是多个随机变量之间的联合性质,而非单个变量的边际性质,因此标准的 conformal prediction(逐点覆盖)无法直接推广。该子方向当前处于快速发展的早期阶段:conformal prediction 本身已相当成熟,但将其从"预测集合"推广到"预测结构"(排序、图、秩)是近两三年的新兴前沿。

发展脉络

  • 奠基工作:Conformal Prediction 框架。Vovk et al. [2005] 与 Papadopoulos [2008] 建立了 conformal prediction 的基本框架:在可交换性假设下,利用校准数据构造预测集合,保证有限样本下的边际覆盖。这是整个领域的基石,本文的所有方法都建立在这一框架之上。Angelopoulos and Bates [2021] 与 Angelopoulos et al. [2024] 提供了该领域的系统综述,标志着 conformal prediction 从理论走向广泛应用。
  • 关键转折:从预测集合到预测选择。Jin and Candès [2023] 的 conformal selection 是本文最直接的先驱。该工作首次将 conformal prediction 与多重检验结合:不是预测单个结果,而是选择满足特定条件(如结果超过阈值)的对象,并控制误选率。这一工作将 conformal 框架从"集合覆盖"拓展到"选择/决策",为本文的"图结构推断"铺平了道路。其思想源自 outlier detection(Bates et al. [2023]),并已被 Marandon et al. [2022]、Gui et al. [2024]、Liang et al. [2024] 等扩展。
  • e-value 革命:多重检验的新工具。Wang and Ramdas [2022] 提出的 e-BH 过程是本文 FDR 控制方法的核心工具。与 p-value 不同,e-value 的期望在零假设下至多为 1,且 e-BH 过程对任意依赖结构都成立——这一性质在本文的"随机假设"(假设本身依赖于数据)场景中至关重要。Lee and Ren [2025] 进一步将 e-value 与 conformal 结合,处理层次化数据的选择问题,并允许随机数量的假设。本文的 FDR 控制方法直接建立在这一系列工作之上。
  • 经典排序推断的平行线。与上述 conformal 路线平行,存在一条关于固定参数排序推断的经典文献:Neuhof and Benjamini [2024] 研究特征重要性的排序不确定性;Al Mohamad et al. [2022] 讨论正态样本均值的秩的置信区间;Hung and Fithian [2019] 在指数族中做秩验证;Goldwasser et al. [2025] 和 Sood [2025] 分别扩展到异方差高斯和多元高斯。这些工作处理的是参数(如总体均值)的排序,而非随机变量(如新样本的结果)的排序,与本文的问题设定有本质区别。
  • 最接近的竞争工作。Fermanian et al. [2026] 研究的是"测试点在全样本(校准+测试)中的秩"的预测区间,与本文"测试点之间的相对排序"不同。Neuhof and Benjamini [2026] 研究模型在新任务上的性能秩,假设任务间可交换,也与本文设定不同。这两篇是本文在"预测排序"方向上最接近的邻居,但问题设定均有实质差异。

子线索聚类

  1. Conformal Prediction 及其扩展(Vovk et al. [2005], Papadopoulos [2008], Angelopoulos and Bates [2021], Angelopoulos et al. [2024]):提供分布自由、有限样本有效的预测集合的基本工具。
  2. Conformal Selection 与多重检验(Jin and Candès [2023], Bates et al. [2023], Marandon et al. [2022], Gui et al. [2024], Liang et al. [2024], Lee and Ren [2025]):将 conformal 从"预测"拓展到"选择",引入 FDR/FWER 控制。
  3. e-value 理论(Wang and Ramdas [2022], Grünwald et al. [2024], Shafer [2021], Vovk and Wang [2021], Ramdas and Wang [2025], Ignatiadis et al. [2024a,b], Fischer and Ramdas [2024], Ren and Barber [2024], Lee and Ren [2024], Xu et al. [2025], Goeman et al. [2025]):提供在复杂依赖下仍有效的多重检验工具。
  4. 经典排序/秩推断(Neuhof and Benjamini [2024], Al Mohamad et al. [2022], Hung and Fithian [2019], Goldwasser et al. [2025], Sood [2025]):处理固定参数的排序推断,与本文的随机变量排序形成对照。

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

  1. 如何定义"排序推断"的有效目标? 排序是一个结构对象,不像单个结果那样有自然的"覆盖"概念。本文提出用"不确定性图"(哪些对排序被置信)和"秩的预测区间"作为推断目标,但这只是众多可能目标中的一种。
  2. 如何在多重检验框架下处理"随机假设"? 本文的假设(每对测试对象的排序)本身依赖于数据(由预测模型决定),这与经典多重检验中假设固定的设定不同。e-value 框架天然适应这一场景,但代价是保守性。
  3. 如何平衡误差控制与统计功效? FWER 控制(Bonferroni、partitioning)与 FDR 控制(e-BH)之间存在功效-保证的权衡。本文的 partitioning 方法试图在保证 FWER 的同时减少保守性,但代价是需要更多校准数据。
  4. 推断质量如何依赖预测模型的精度? 与标准 conformal prediction 类似,本文方法的"功效"(区间宽度、图密度)依赖于预测模型 µ̂ 的质量,但误差控制(覆盖、FDR)则完全分布自由。这一"模型依赖的功效"与"模型无关的保证"之间的张力是该领域的核心特征。

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

作者将缺口 frame 为:"conformal prediction 提供了逐点的预测集合,但无法直接回答'这些对象如何排序'这一联合推断问题"。他们声称本文是第一个将 conformal 思想系统性地推广到排序/秩推断的工作,并强调其方法在"仅依赖可交换性、无分布假设"的前提下同时提供 FWER 和 FDR 控制。作者淡化了经典排序推断文献(如 Al Mohamad et al. [2022])的相关性,认为那些工作处理的是参数而非随机变量。值得研究者去查的问题:作者在 intro 中未提及 Fermanian et al. [2026] 的具体方法细节,也未讨论其与本文在"全样本秩 vs. 测试集内排序"上的本质区别;此外,关于 e-value 在随机假设下的有效性,作者引用了 Lee and Ren [2025],但未讨论该结果的证明是否完全覆盖本文的设定。

张力

未见明显对立引用。各条线索之间是互补关系而非竞争关系:conformal 提供工具,e-value 提供多重检验框架,经典排序推断提供问题背景。唯一的潜在张力在于"参数排序"与"随机变量排序"两种问题设定之间的边界,但作者明确选择了后者,且这一选择在 intro 中有清晰论证。

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

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

符号清单(逐个点名):

  • 数据点:\(Z_i = (X_i, Y_i) \in \mathcal{X} \times \mathbb{R}\),其中 \(X_i\) 是协变量(特征),\(Y_i\) 是结果(响应)。\(i \in [n+m]\)。
  • 样本划分:前 \(n\) 个为校准数据 \(\{(X_i, Y_i)\}_{i \in [n]}\),后 \(m\) 个为测试数据 \(\{(X_{n+j}, Y_{n+j})\}_{j \in [m]}\)。注意:测试数据的 \(Y\) 是未观测的。
  • 预测函数:\(\hat{\mu}: \mathcal{X} \to \mathbb{R}\),在独立的训练集上拟合(或从校准+测试中留出),用于预测 \(Y\)。
  • 预测排序:\(\hat{I} \in S_m\)(\(S_m\) 为 \(m\) 个元素的置换群),定义为按 \(\hat{\mu}(X_{n+j})\) 升序排列的测试对象索引。即 \(\hat{I}_k\) 是预测排在第 \(k\) 位的对象。
  • 真实排序:\(I \in S_m\),定义为按真实 \(Y_{n+j}\) 升序排列的测试对象索引。
  • 秩:\(R_j = \sum_{l=1}^m \mathbb{1}\{Y_{n+j} \geq Y_{n+l}\}\),即对象 \(j\) 在 \(m\) 个测试对象中的真实秩(从 1 到 \(m\))。
  • 假设(hypotheses):\(H_{j_1,j_2}: (Y_{n+j_1} - Y_{n+j_2}) \cdot (\hat{\mu}(X_{n+j_1}) - \hat{\mu}(X_{n+j_2})) \leq 0\),即"预测模型对 \(j_1, j_2\) 的排序与真实排序不一致"。拒绝 \(H_{j_1,j_2}\) 意味着我们置信地断言 \(Y_{n+j_1} < Y_{n+j_2}\)(当 \(\hat{\mu}(X_{n+j_1}) < \hat{\mu}(X_{n+j_2})\) 时)。
  • 不确定性图:\((\hat{I}, R)\),其中 \(R \subseteq \{(k_1, k_2): 1 \leq k_1 < k_2 \leq m\}\) 是被拒绝的假设集合(即被置信的排序对)。
  • 误差度量:FWER(至少一个错误拒绝的概率)与 FDR(错误拒绝比例的期望),定义见正文式 (3)(4)。
  • e-value:\(e_{j_1,j_2}\),对每个假设构造的非负随机变量,满足在零假设下 \(\mathbb{E}[e_{j_1,j_2} \cdot \mathbb{1}\{H_{j_1,j_2} \text{ holds}\}] \leq 1\)。
  • 校准分数:\(S_{i_1,i_2} = |\hat{\mu}(X_{i_1}) - \hat{\mu}(X_{i_2})| \cdot \mathbb{1}\{(\hat{\mu}(X_{i_1}) - \hat{\mu}(X_{i_2}))(Y_{i_1} - Y_{i_2}) \leq 0\}\),即"预测排序错误"的校准对的分数(预测差距越大,分数越大)。

模型与可观测数据:

  • 统计模型:仅假设 \((Z_1, \ldots, Z_{n+m})\) 联合可交换(exchangeable)。没有分布形式、独立性、矩条件等任何额外假设。
  • 可观测数据:\((X_i, Y_i)_{i \in [n]}\)(校准)和 \((X_{n+j})_{j \in [m]}\)(测试特征)。不可观测:\((Y_{n+j})_{j \in [m]}\)(测试结果)。
  • 目标(estimand):真实排序 \(I\) 和真实秩 \(R_j\)。这些是随机的(依赖于测试结果),而非固定参数。
  • 关键区分:本文的"假设" \(H_{j_1,j_2}\) 是关于随机变量(测试结果)的陈述,而非关于固定参数的陈述。这使得经典的多重检验理论不能直接应用,需要 e-value 框架。

第二步:最小内核

最简特例:\(m = 2\)(只有两个测试对象)。

在这个特例下,排序推断退化为一个二分类问题:判断 \(Y_{n+1} < Y_{n+2}\) 还是 \(Y_{n+1} > Y_{n+2}\)。假设 \(\hat{\mu}(X_{n+1}) < \hat{\mu}(X_{n+2})\)(预测 \(Y_{n+1}\) 更小),则唯一的假设是 \(H_{1,2}: Y_{n+1} \geq Y_{n+2}\)(预测错误)。

核心问题:如何利用校准数据构造一个决策规则,以 \(\alpha\) 为界控制错误拒绝 \(H_{1,2}\) 的概率?

本文的答案(直觉版): 1. 对校准数据构造"预测排序错误"的分数 \(S_{i_1,i_2}\)(如上定义)。 2. 对测试对 \((n+1, n+2)\),计算预测差距 \(|\hat{\mu}(X_{n+1}) - \hat{\mu}(X_{n+2})|\)。 3. 如果该差距大于校准分数的一个特定分位数(由 \(\alpha\) 决定),则拒绝 \(H_{1,2}\),即置信地断言 \(Y_{n+1} < Y_{n+2}\)。

为什么成立:由于可交换性,测试对的"预测排序错误"分数与校准对的分数是同分布的(在 \(H_{1,2}\) 成立的条件下)。因此,校准分数的分位数给出了测试分数的一个有效上界,从而控制了错误拒绝的概率。这就是 conformal prediction 的核心逻辑——用校准数据的秩来校准测试数据的置信度——被推广到了排序推断。

一般化:当 \(m > 2\) 时,需要对 \(\binom{m}{2}\) 个假设同时进行检验。FWER 控制要求所有错误拒绝的概率之和有界(Bonferroni 或 partitioning),FDR 控制则允许一定比例的错误拒绝(e-BH)。本文的核心技术贡献在于:如何构造有效的 e-value(或 p-value),使得在随机假设、复杂依赖下仍能保证 FWER/FDR 控制。

三、这篇论文做了什么

三句话

  1. 研究了什么问题:在分布自由(仅可交换性)的框架下,如何对多个未观测结果的排序和秩进行预测性推断,并同时控制 FWER 或 FDR。
  2. 核心工具/方法:将排序推断重构为图推断问题,构造 conformal p-value(FWER 控制)和 conformal e-value(FDR 控制),并证明其有限样本有效性。
  3. 主要结论:提出了两种 FWER 控制方法(Bonferroni 型与 partitioning 型)和一种 FDR 控制方法(基于 e-BH),在模拟和真实数据上验证了其误差控制与功效;并给出了一个互补的 hardness 结果,说明在给定样本量下,非平凡推断所需的校准数据量存在下界。

关键设定与假设

  • 核心假设:\((Z_1, \ldots, Z_{n+m})\) 联合可交换。这是 conformal inference 的标准假设,比独立同分布更弱。
  • 附加假设:结果 \(Y_i\) 几乎必然互不相同(无并列),预测值 \(\hat{\mu}(X_i)\) 也几乎必然互不相同。这是技术性假设,可通过随机扰动消除。
  • 预测函数:\(\hat{\mu}\) 在独立的训练集上拟合,与校准和测试数据独立。这是标准的数据划分(split conformal)设定。
  • 相比已有工作的变化:
  • 相比标准 conformal prediction:目标从"逐点预测集合"变为"排序/秩的联合推断",误差度量从"边际覆盖"变为"FWER/FDR"。
  • 相比经典多重检验:假设是随机的(依赖于测试结果),而非固定参数;且假设之间存在复杂依赖(同一测试对象参与多个假设)。
  • 相比 conformal selection(Jin and Candès [2023]):本文的假设是成对比较(\(\binom{m}{2}\) 个),而非单个对象的边际选择;且本文同时处理 FWER 和 FDR。

主要结果

A. FWER 控制(Section 3)

  • 方法 1(Bonferroni 型):对每个假设 \(H_{j_1,j_2}\) 构造 conformal p-value \(p_{j_1,j_2}\)(式 9),拒绝所有 \(p_{j_1,j_2} \le \alpha / \binom{m}{2}\) 的假设。定理 1 证明该过程控制 FWER ≤ α。
  • 方法 2(Partitioning 型):将校准数据分成 \(\binom{m}{2}\) 组,每组对应一个假设,用组内数据构造阈值 \(T_{j_1,j_2}\)。定理 2 证明该过程控制 FWER ≤ α,且通常比 Bonferroni 型更少保守。
  • Hardness 结果(定理 3):证明任何控制 FWER 的过程,若想以高概率产生非空拒绝集,校准数据量 \(n\) 必须至少为 \(\Omega(m/\alpha)\) 量级。这说明了 partitioning 方法在样本量需求上的某种最优性。

B. FDR 控制(Section 4)

  • 核心挑战:conformal p-value 之间存在复杂依赖,直接应用 BH 过程无法保证 FDR 控制。
  • 方法:构造 conformal e-value \(e_{j_1,j_2}\)(式 13),其有效性由引理 2 保证。然后应用 e-BH 过程(Wang and Ramdas [2022]),定理 5 证明该过程控制 FDR ≤ α,且对任意依赖结构成立。
  • 一致性调整:由于 e-value 可能不随预测差距单调递增,作者引入了一个调整步骤(式 17),取所有包含该对的"超集"的最小 e-value,以保证最终拒绝集满足一致性条件(定义 1)。命题 2 证明该调整等价于求解一个整数规划,且与直接应用 e-BH 到调整后的 e-value 等价。

C. 秩的预测区间(Section 3.2, 4.2)

  • 不确定性图 \((\hat{I}, R)\) 可自然导出对每个对象秩的预测区间:\(\hat{C}_j = [1 + |\{l: (\hat{I}_l, \hat{I}_j) \in R^{ord}, \hat{I}_l < \hat{I}_j\}|, m - |\{l: (\hat{I}_j, \hat{I}_l) \in R^{ord}, \hat{I}_l > \hat{I}_j\}|]\)。
  • 定理 4 证明:若图具有 FWER 控制,则所有秩的预测区间同时覆盖真实秩的概率 ≥ 1−α。
  • 定理 6 证明:若图具有 FDR 控制,则秩预测区间满足一个加权风险控制(式 19),其中权重与区间宽度相关。

证明路线与技术技巧

  • 整体路线:先建立单个假设的 conformal p-value/e-value 有效性(引理 1、2),再通过 Bonferroni 或 e-BH 扩展到多重检验,最后通过一致性调整保证图结构的合理性。
  • 关键引理:
  • 引理 1(p-value 有效性):利用可交换性,证明 \(p_{j_1,j_2}\) 在 \(H_{j_1,j_2}\) 下满足 \(\mathbb{P}\{p_{j_1,j_2} \le \alpha\} \le \alpha\)。证明技巧是标准的 conformal 秩论证。
  • 引理 2(e-value 有效性):证明 \(e_{j_1,j_2}\) 满足 \(\mathbb{E}[e_{j_1,j_2} \cdot \mathbb{1}\{H_{j_1,j_2}\}] \le 1\)。证明技巧是构造一个"伪假设"(将测试对与校准对合并),利用可交换性将期望转化为一个可计算的组合计数。
  • 技术技巧点名:
  • 可交换性 + 秩论证:conformal 方法的核心,用于将测试统计量与校准统计量联系起来。
  • e-BH 过程:利用 e-value 的乘法性质,在任意依赖下控制 FDR。
  • 整数规划/单调调整:将一致性约束转化为对 e-value 的单调化处理,保证图结构合理。
  • Hardness 证明:构造一个特定的"困难"分布族,利用 Fano 不等式或类似的对抗性论证,给出样本量下界。

真实例子与应用

  • 模拟实验(Section 5.1):两个设置——线性回归(设置 1)和随机森林(设置 2,含非线性项和异方差)。验证了 FDR 控制(图 4、5)和风险控制(图 6、7),并比较了 e-BH 与 p-BH 的功效。
  • 真实数据(Section 5.2):药物-靶点相互作用(DTI)数据集,来自 DeepPurpose 库(Huang et al. [2020])。任务是对测试药物-靶点对的结合亲和力进行排序推断。结果显示 FDR 被严格控制,且不确定性图能有效识别出高置信的排序关系。
  • 例子想说明什么:方法在模型误设(设置 2)下依然有效,且在实际应用中能提供有意义的排序不确定性量化。

🔎 结论是否比证明窄

  • 定理 3(Hardness) 的证明假设了过程是"一致的"(定义 1),但作者在正文中承认,对于不满足一致性的过程,下界可能不成立。这是一个明确的窄化。
  • 定理 6(FDR 风险控制) 中的权重 \(w_j\) 和距离 \(d\) 是特定选择的,作者在 Remark 中说明,对于更一般的权重/距离,结论可能不成立。
  • 引理 2(e-value 有效性) 的证明依赖于"伪假设"的构造,这要求校准数据可以任意配对。如果校准数据存在结构(如分组),该构造可能失效。作者在正文中未明确讨论这一点。
  • 总体而言:论文的证明是严谨的,但结论的适用范围(一致性、特定权重、可任意配对)比摘要中的表述更窄。这些窄化点正是后续研究的潜在切入点。

四、开放问题

  1. 超越可交换性:本文的核心假设是联合可交换性。当数据存在时间趋势、分组结构或分布漂移时,如何推广?作者在 Discussion 中仅一笔带过,未给出任何具体方向。扎根点:Section 6 "Many open questions remain. Conformal prediction and conformal selection have been studied and extended in these settings beyond exchangeable data..."。

  2. 最优性:定理 3 给出了 FWER 控制的样本量下界,但 FDR 控制的最优样本量需求未知。e-BH 是否在某种意义下最优?扎根点:定理 3 的陈述与证明。

  3. 功效-宽度权衡的定量刻画:论文实证展示了预测区间宽度随 \(\alpha\) 和 \(n\) 的变化,但未给出宽度的理论界。能否给出区间宽度的期望上界(作为 \(n, m, \alpha\) 的函数)?扎根点:Section 5.1 的模拟结果。

  4. 自适应预测器:本文的阈值 \(T_{j_1,j_2}\) 对所有测试对使用相同的校准分位数。能否根据测试对的局部特征(如 \(\hat{\mu}\) 的不确定性)自适应地调整阈值,以提高功效?扎根点:式 (13) 中 e-value 的定义。

  5. 与经典排序推断的桥接:本文处理随机变量的排序,而经典文献(如 Al Mohamad et al. [2022])处理参数的排序。是否存在一个统一框架?扎根点:Section 1.2 对经典文献的讨论。

  6. 计算复杂度:整数规划(式 16)在最坏情况下可能是指数级的。虽然作者给出了等价形式(命题 2),但该等价形式是否总能高效求解?扎根点:命题 2 的陈述。

提示:要确认上述问题是否为真 gap,建议去读近 2-3 年 conformal prediction 与多重检验交叉方向的论文(如 NeurIPS、AISTATS、JRSS-B 等)的引言部分。如果多篇论文的引言都指向同一个问题,那大概率是共识性 gap;如果各说各话,则可能是机会所在。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论