Learn then test: Calibrating predictive algorithms to achieve risk control¶
作者: Anastasios N. Angelopoulos, Stephen Bates, Emmanuel J. Candès, Michael I. Jordan, Lihua Lei
来源: Annals of Applied Statistics
主题: 数理统计 / 假设检验
相关性: 7/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么 这个子方向要解决的根本统计问题是:如何为黑箱机器学习模型的预测提供分布无关的、有限样本的、显式的风险控制。传统的不确定性量化(如置信区间、p值)依赖渐近分布或参数模型假设,而现代ML模型(如深度网络)的误差结构复杂且未知,渐近保证在有限样本下往往不可靠。这个方向当前已进入快速工具化阶段:保形预测已形成标准范式,但将其推广到非单调、多维、复合风险指标的预测集校准,仍处于理论框架刚成型、技术细节正在补全的时期。
发展脉络 - 奠基工作:Vovk 等人在 1990s-2000s 建立了保形预测,核心是利用数据可交换性构造分布无关的预测集,保证边际覆盖率 \(P(Y_{n+1} \in C(X_{n+1})) \ge 1-\alpha\)。Vovk (2012) [3] 提出分裂保形与交叉保形,解决了全保形的计算瓶颈;Barber et al. (2019) [21] 提出 Jackknife+,证明即使模型不稳定也能保证覆盖率。 - 主要进展(从边际覆盖到更一般的风险):保形预测原生只处理覆盖率这一单调风险。Romano et al. (2020) [18] 将其推广到分类的适应性覆盖;Sadinle et al. (2016) [23] 研究了有界错误水平的集合分类器。Bates et al. (2021) [1] 是本文最直接的前身,提出了风险控制预测集,允许控制任意损失(如 FDR、漏报率),但仍受限于参数 \(\lambda\) 必须是一维且风险函数必须对 \(\lambda\) 单调——这排除了大量 ML 任务(如 IoU 控制、多标签 FDR)。 - 当前 frontier 与本文位置:作者在 intro 中明确指出,已有保形/风险控制文献要求 \(\lambda\) 一维且单调,本文(Learn-Then-Test, LTT)通过将校准问题重构为多重假设检验,绕开单调性要求,允许 \(\lambda\) 为多维参数向量、风险为任意函数,从而将分布无关校准的适用范围推到了新的 frontier。
子线索聚类 1. 保形预测的计算与效率改进:Vovk (2012) [3] 的交叉保形、Barber et al. (2019) [21] 的 Jackknife+、Romano et al. (2019) [16] 的保形分位数回归。这一簇在解决"如何不浪费数据地构造预测集"。 2. 保形预测的设定扩展:Tibshirani et al. (2019) [2] 处理协变量偏移下的加权保形;Gibbs & Candès (2021) [20] 处理在线分布偏移下的自适应保形;Fisch et al. (2021) [5] 处理少样本设定;Lei & Candès (2020) [25] 将保形用于反事实与个体处理效应推断。这一簇在解决"当可交换性被打破时,保形还能否工作"。 3. 从覆盖率到更一般的风险控制:Sadinle et al. (2016) [23] 的集合分类器、Bates et al. (2021) [1] 的风险控制预测集(RCPS)。这一簇是本文的直接前驱,在解决"保形能否控制除覆盖率以外的风险"。
这个方向在追问的核心问题 1. 如何在不依赖分布假设下,为任意风险函数提供有限样本保证?(当前主流是保形/RCPS,瓶颈是要求风险对参数单调) 2. 边际覆盖/风险控制与条件覆盖/风险控制之间的鸿沟如何填补?(Barber et al. (2019) [22] 证明了分布无关的条件覆盖不可能,当前瓶颈是寻找有意义的近似条件保证) 3. 当数据不可交换(分布偏移、时间序列)时,校准保证如何维持?(当前主流是加权保形/自适应保形,瓶颈是对偏移程度的量化与保证的保守性)
⚠️ 作者的 framing - 作者把缺口 frame 成什么:作者将缺口 frame 为"保形预测与 RCPS 要求 \(\lambda\) 一维且风险单调,这排除了 IoU 控制、多标签 FDR 等核心 ML 任务",从而让"将校准重构为多重假设检验以绕开单调性"成为显然的下一步。 - 哪些竞争路线被淡化或回避:作者没有讨论贝叶斯不确定性量化(如 BNN、贝叶斯深度学习)这条路线,也没有讨论基于渐近理论的校准(如高维渐近、自助法)。这些路线在特定假设下也能提供风险保证,但作者直接跳过了它们与分布无关路线的对比。 - 什么明显该被引 / 该存在、却没出现在 intro 里:在多重假设检验部分,作者引用了经典的 Bonferroni 与 Holm,但没有引用 Benjamini-Yekutieli (2001)——该工作处理了多重检验中的正依赖与一般依赖结构,而本文的 LTT 检验之间显然存在依赖(共享同一校准集),B-Y 调整可能比 Bonferroni 更紧。此外,闭集检验 与 固定顺序逐步检验 在控制 FWER 时比 Holm 更紧,但未被提及。这些是值得研究者去查的缺口。
张力 未见明显对立引用。保形预测文献内部更多是互补而非矛盾:[22] 证明了条件覆盖不可能,[18] 则在近似条件覆盖上做改进;[1] 要求单调性,本文则绕开单调性。它们在不同设定下得出不同结论,但并非逻辑矛盾。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据交代清楚
- 符号与指标
- \(n\):校准集的样本量。
- \(d\):参数 \(\lambda\) 的维数(LTT 允许 \(d \ge 1\))。
- \(\alpha \in (0,1)\):用户指定的风险容忍水平(如 \(\alpha=0.1\) 表示允许 10% 的风险)。
- \(\lambda \in \Lambda \subseteq \mathbb{R}^d\):校准参数向量(如阈值向量、集合大小参数)。
- \(R(\lambda)\):总体风险函数,即我们要控制的 estimand:\(R(\lambda) = \mathbb{E}[L(Y, f_\lambda(X))]\),其中 \(L\) 是损失函数,\(f_\lambda\) 是以 \(\lambda\) 为参数的预测函数。
- \(\hat{R}_n(\lambda)\):经验风险函数,在校准集上计算:\(\hat{R}_n(\lambda) = \frac{1}{n}\sum_{i=1}^n L(Y_i, f_\lambda(X_i))\)。
- \(\Lambda^*\):安全参数集,即满足 \(R(\lambda) \le \alpha\) 的所有 \(\lambda\) 的集合:\(\Lambda^* = \{\lambda \in \Lambda : R(\lambda) \le \alpha\}\)。
- \(\hat{\Lambda}\):LTT 算法输出的估计安全参数集。
- \(H_\lambda\):针对参数 \(\lambda\) 的零假设:\(H_\lambda : R(\lambda) > \alpha\)(即 \(\lambda\) 不安全)。
-
\(p_\lambda\):针对 \(H_\lambda\) 的 p 值。
-
模型
- 数据生成机制:\((X_i, Y_i) \sim P\),\(P\) 是任意未知分布,唯一要求是校准集与测试集可交换(i.i.d. 即可)。
- 黑箱模型 \(f\) 已在独立训练集上拟合完毕,固定且不再更新。
- 预测函数 \(f_\lambda\) 是 \(f\) 加上参数 \(\lambda\) 的后处理(如取 softmax 输出中概率 \(> \lambda\) 的标签集合)。
-
损失函数 \(L\) 可以是任意函数(如 FDR、IoU、误报率),不要求对 \(\lambda\) 单调。
-
可观测数据
- 研究者实际能观测到的是校准集 \(\{(X_i, Y_i)\}_{i=1}^n\),以及黑箱模型 \(f\) 在校准集上的输出 \(f(X_i)\)。
- 通过组合 \(f(X_i)\)、\(Y_i\) 与 \(\lambda\),可以计算经验损失 \(L(Y_i, f_\lambda(X_i))\),进而得到经验风险 \(\hat{R}_n(\lambda)\)。
- 不可观测:总体风险 \(R(\lambda)\)、总体分布 \(P\)。只能靠假设检验从经验风险推断总体风险。
第二步:最小内核——一维参数、二值损失、Bonferroni 校正
剥掉所有一般性(多维 \(\lambda\)、FDR 控制、逐步检验),LTT 的最小内核是:
设定:\(\lambda \in \Lambda = \{\lambda_1, \lambda_2, ..., \lambda_m\}\) 是 \(m\) 个离散候选参数(如 \(m\) 个不同的阈值)。损失 \(L\) 是 0-1 损失(如预测集是否包含真标签)。风险 \(R(\lambda) = P(L=1)\) 是误报率。我们要找所有满足 \(R(\lambda) \le \alpha\) 的 \(\lambda\)。
核心思路:把"找安全 \(\lambda\)"重构为"在 \(m\) 个假设中筛掉不安全的 \(\lambda\)"。 - 对每个 \(\lambda_j\),定义零假设 \(H_j : R(\lambda_j) > \alpha\)。 - 如果我们能控制 FWER(族错误率,即至少错误地接受一个不安全 \(\lambda\) 的概率)\(\le \delta\),那么输出的集合 \(\hat{\Lambda} = \{\lambda_j : \text{拒绝 } H_j\}\) 满足:
最小内核的证明路线: 1. 构造 p 值:对每个 \(\lambda_j\),经验风险 \(\hat{R}_n(\lambda_j)\) 是 \(n\) 个独立 0-1 变量的均值。在零假设 \(H_j\) 下,\(R(\lambda_j) > \alpha\),由 Hoeffding 不等式:
为什么这个内核重要:它揭示了 LTT 的本质——风险控制保证 = 多重假设检验的 FWER/FDR 控制。保形预测/RCPS 的单调性要求,本质上是为了让这个检验只需要做一次(一维参数的排序天然给出了检验的顺序,单调性保证了顺序即安全性的顺序)。一旦去掉单调性,就必须对整个参数空间做多重检验,Bonferroni/Holm/BY 等经典工具自然登场。
三、这篇论文做了什么¶
三句话 ①研究了如何为任意(非单调、多维)风险函数的 ML 预测提供分布无关的有限样本风险控制保证;②核心方法是将校准问题重构为多重假设检验(LTT 框架),并引入 FWER/FDR 控制技术来筛选安全参数;③主要结论是:在可交换数据与任意未知分布下,LTT 输出的参数集满足 \(P(\forall \lambda \in \hat{\Lambda}, R(\lambda) \le \alpha) \ge 1-\delta\)(FWER 控制)或 FDR 控制,且不需要重新拟合模型。
关键设定与假设 在第二节最小记号基础上补全: - 假设 A1(可交换性):校准集 \((X_i, Y_i)_{i=1}^n\) 与测试点 \((X_{n+1}, Y_{n+1})\) 可交换。统计含义:这是保形预测的基石假设,保证了经验风险的分布与测试风险的联系;相比已有文献(保形/RCPS),这是相同的标准假设。 - 假设 A2(固定模型):黑箱模型 \(f\) 在独立训练集上拟合,校准时不更新。统计含义:避免了数据复用导致的过拟合偏差;与 RCPS [1] 一致,但与全保形/交叉保形 [3, 21] 不同(后者复用数据但通过特殊设计保证有效性)。 - 定义(风险控制预测集):给定 \(\alpha, \delta\),若 \(P(\forall \lambda \in \hat{\Lambda}, R(\lambda) \le \alpha) \ge 1-\delta\),则称 \(\hat{\Lambda}\) 为 \((\alpha, \delta)\)-风险控制预测集。相比 RCPS [1] 的定义(要求 \(P(R(\hat{\lambda}) \le \alpha) \ge 1-\delta\) 且 \(\hat{\lambda}\) 是单点),本文允许输出集合 \(\hat{\Lambda}\),这是去掉单调性后的必然结果——不再有唯一最优 \(\lambda\)。 - 定义:\(H_\lambda : R(\lambda) > \alpha\)。LTT 的目标是筛选出所有 \(R(\lambda) \le \alpha\) 的 \(\lambda\),即接受所有 \(H_\lambda\) 的补假设。
主要结果
定理 1(LTT 的 FWER 控制): - 陈述:对任意有限参数集 \(\Lambda\),若对每个 \(\lambda\) 构造有效 p 值 \(p_\lambda\)(即 \(P(p_\lambda \le \delta' | H_\lambda) \le \delta'\)),并应用 Bonferroni(阈值 \(\delta/|\Lambda|\))或 Holm 逐步检验,则输出的 \(\hat{\Lambda}\) 满足 \(P(\exists \lambda \in \hat{\Lambda} \text{ s.t. } R(\lambda) > \alpha) \le \delta\)。 - 直觉:FWER 控制保证"错误地认为某个不安全参数是安全"的概率 \(\le \delta\),这直接翻译为风险控制保证。 - 必要条件:\(\Lambda\) 必须有限(或可离散化);p 值必须有效(本文通过 Hoeffding/Bentkus 不等式构造)。 - 解决的技术难点:绕开了 RCPS 的单调性要求——不再需要 \(\lambda\) 一维排序,而是对每个 \(\lambda\) 独立检验再做多重校正。
定理 2(LTT 的 FDR 控制): - 陈述:若应用 Benjamini-Hochberg (BH) 逐步检验,在 p 值满足 PRDS(正依赖)条件时,输出的 \(\hat{\Lambda}\) 满足 \(\mathbb{E}[\text{FDP}(\hat{\Lambda})] \le \delta\),其中 \(\text{FDP}(\hat{\Lambda}) = \frac{|\{\lambda \in \hat{\Lambda} : R(\lambda) > \alpha\}|}{|\hat{\Lambda}|}\) 是错误发现比例。 - 直觉:FDR 控制允许少量不安全参数混入,但保证混入的比例期望 \(\le \delta\)。这比 FWER 更宽松,适合参数集很大、允许少量误差的场景。 - 必要条件:p 值需满足 PRDS(本文证明了在损失函数对 \(\lambda\) 单调时,p 值满足 PRDS;对非单调损失,PRDS 可能不成立,此时 BH 仍适用但保证变为 \(\delta \cdot \sum_{i=1}^m 1/i / m\),即 B-Y 调整)。
定理 3(Bentkus p 值): - 陈述:对 0-1 损失,定义 \(p_\lambda^{Bentkus} = \frac{P(Bin(n, \alpha) \le \hat{R}_n(\lambda) \cdot n)}{P(Bin(n, \alpha) \le \lfloor \alpha n \rfloor)}\),则 \(p_\lambda^{Bentkus}\) 是有效 p 值,且比 Hoeffding p 值更紧(尤其在 \(\alpha\) 小或 \(n\) 小时)。 - 直觉:Hoeffding 用尾概率上界 \(e^{-2n\epsilon^2}\),Bentkus 用二项分布的精确尾概率除以最大值,利用了 \(Bin(n, \alpha)\) 的真实分布形状。 - 解决的技术难点:Hoeffding 在 \(\alpha\) 小时极其保守(因为 \(e^{-2n\epsilon^2}\) 不区分 \(\alpha\) 的大小),Bentkus 通过直接与 \(Bin(n, \alpha)\) 比较,将 \(\alpha\) 的信息注入 p 值,显著降低保守性。
证明路线与技术技巧
整体路线(以定理 1 + Hoeffding p 值为例): 1. 构造 p 值:对每个 \(\lambda\),用 Hoeffding 不等式证明 \(p_\lambda^{Hoeffding} = e^{-2n(\hat{R}_n(\lambda) - \alpha)^2}\) 在 \(H_\lambda\) 下满足 \(P(p_\lambda \le \delta') \le \delta'\)。 2. 多重校正:对 \(m = |\Lambda|\) 个 p 值,应用 Bonferroni(阈值 \(\delta/m\))或 Holm 逐步拒绝。 3. FWER 保证:由多重检验的经典理论,FWER \(\le \delta\)。 4. 翻译为风险控制:FWER \(\le \delta\) 等价于 \(P(\hat{\Lambda} \subseteq \Lambda^*) \ge 1-\delta\),即所有被选入 \(\hat{\Lambda}\) 的参数都满足 \(R(\lambda) \le \alpha\)。
关键跳跃点: - 从"风险控制"到"多重检验"的概念跳跃:这是本文的核心创新。已有文献(RCPS)试图直接构造 \(\hat{\lambda}\) 使得 \(R(\hat{\lambda}) \le \alpha\),依赖单调性来保证"一旦某个 \(\lambda\) 安全,更极端的 \(\lambda\) 也安全"。本文放弃单调性,将问题重构为"在 \(m\) 个假设中筛掉不安全的",从而引入多重检验工具箱。 - Bentkus p 值的构造与有效性证明:证明 \(p_\lambda^{Bentkus}\) 是有效 p 值需要用到 Bentkus (2003) [7] 的结果——加权 Rademacher 和的尾概率被正态尾概率控制的上界。本文将二项分布尾概率与 Rademacher 和联系,再利用 Bentkus 的紧界,得到比 Hoeffding 更紧的 p 值。
技术技巧点名: - Hoeffding 不等式:用于构造最简单的 p 值,保守但无需损失函数的任何结构。 - Bentkus 界(Bentkus & Dzindzalieta 2013 [7], Pinelis 2010 [8]):用于构造紧 p 值,利用了 0-1 损失的二项分布结构。 - 无替换抽样浓度不等式(Bardenet & Maillard 2013 [4]):在证明交叉保形+LTT 的变体时使用,处理数据复用带来的依赖。 - Benjamini-Hochberg 逐步检验:用于 FDR 控制,要求 PRDS 条件(本文在单调损失下证明了 PRDS)。 - Holm 逐步检验:用于 FWER 控制,比 Bonferroni 更紧且无需依赖假设。
真实例子与应用
- 多标签分类的 FDR 控制(MS COCO 数据集):
- 数据:MS COCO [10] 的 80 类图像标注,\(n=4000\) 校准集,\(1000\) 验证集。
- 方法:对每张图像,模型输出 80 个类的 softmax 概率,取概率 \(> \lambda\) 的类作为预测集。损失函数为 FDP(错误发现比例)。目标:控制 FDP 的期望(即 FDR)\(\le \alpha\)。LTT 用 BH 检验在 \(\lambda \in \{0.1, ..., 0.9\}\) 中筛选,输出满足 FDR \(\le \alpha\) 的 \(\lambda\) 集合。
- 结果:在 \(\alpha=0.1\) 时,LTT 选出的 \(\lambda\) 在验证集上实现 FDR \(\approx 0.09\),而固定 \(\lambda=0.5\) 的 FDR \(\approx 0.25\)。
-
说明什么:展示了 LTT 在非单调风险(FDP 对 \(\lambda\) 不单调)下的实用性,且 BH 校正比 Bonferroni 更紧。
-
实例分割的 IoU 控制(MS COCO):
- 数据:同上,但任务是对 Mask R-CNN [12] 输出的分割掩码筛选像素,保证掩码与真实掩码的 IoU \(\ge 1-\alpha\)。
- 方法:\(\lambda\) 是像素保留概率阈值,损失 \(L = 1 - \text{IoU}\)。IoU 对 \(\lambda\) 不单调(阈值太高或太低都会降低 IoU)。LTT 用 Holm 检验在 \(\lambda \in \{0.05, ..., 0.95\}\) 中筛选。
- 结果:在 \(\alpha=0.1\) 时,LTT 选出的 \(\lambda\) 集合在验证集上实现 \(E[1-\text{IoU}] \approx 0.09\)。
-
说明什么:展示了 LTT 在非单调风险下的必要性——RCPS 无法处理 IoU(因为 IoU 对 \(\lambda\) 不单调),LTT 是首个提供 IoU 有限样本保证的方法。
-
异常检测与覆盖率的联合控制(ImageNet + ODIN):
- 数据:ImageNet [9] 的 ResNet 分类器,用 ODIN [14] 作为异常检测分数。
- 方法:同时控制异常检测的误报率(T1E)\(\le \alpha_1\) 和分类预测集的覆盖率 \(\ge 1-\alpha_2\)。参数 \(\lambda = (\lambda_1, \lambda_2)\) 是二维阈值。LTT 对 \(\lambda_1 \times \lambda_2\) 的网格做 Bonferroni 检验。
- 结果:在 \(\alpha_1=0.1, \alpha_2=0.1\) 时,LTT 选出的 \((\lambda_1, \lambda_2)\) 组合在验证集上同时满足 T1E \(\approx 0.08\) 和覆盖率 \(\approx 0.91\)。
-
说明什么:展示了 LTT 处理多维参数的能力——RCPS 只能处理一维 \(\lambda\),LTT 通过多重检验自然扩展到多维。
-
表格医疗数据(MIMIC-III):
- 论文还展示了在 MIMIC-III 医疗数据上的应用,控制死亡率预测的覆盖率与 FDR,结果类似。
🔎 结论是否比证明窄 - FDR 控制的 PRDS 条件:定理 2 要求 p 值满足 PRDS,本文在损失函数对 \(\lambda\) 单调时证明了 PRDS。但在非单调损失(如 IoU)下,PRDS 可能不成立,此时 BH 的保证退化为 B-Y 调整(\(\delta \cdot \sum 1/i / m\)),这比 \(\delta\) 更保守。论文在实例分割例子中使用了 BH,但 IoU 对 \(\lambda\) 不单调,严格来说应使用 B-Y 调整——论文在正文中没有明确指出这一点,只在附录提及。这是一个"结论比证明窄"的地方:实际应用中用了 BH,但理论保证在非单调下可能不如陈述的那么紧。 - 连续参数空间的离散化:LTT 要求 \(\Lambda\) 有限,实际应用中通过网格离散化。论文声称"网格足够细即可",但未给出离散化误差的定量分析——这隐含了一个未证明的假设:离散化的 \(\Lambda\) 能足够好地逼近连续空间的最优 \(\lambda\)。
四、开放问题(点到为止,扎根具体语句)¶
-
FDR 控制在非单调损失下的依赖结构:定理 2 在非单调损失下 PRDS 可能不成立,BH 的保证退化为 B-Y 调整。能否构造更紧的 p 值或依赖调整,在非单调损失下仍实现 \(\delta\)-水平的 FDR 控制?(扎根:定理 2 的陈述与附录对 PRDS 的讨论,以及实例分割例子中 BH 的使用与理论保证之间的缝隙)
-
连续参数空间的离散化误差:LTT 要求 \(\Lambda\) 有限,实际通过网格离散化。能否给出离散化粒度与风险控制保守性之间的定量关系?即,网格多细时,离散化 \(\Lambda\) 的最优 \(\lambda\) 与连续 \(\Lambda\) 的最优 \(\lambda\) 之间的风险差 \(\le\) 某个 \(\epsilon\)?(扎根:第 3.1 节对 \(\Lambda\) 有限的假设,以及实际应用中的网格选择没有理论指导)
-
条件风险控制的近似保证:LTT 提供的是边际风险控制(对所有测试点平均),但实际需要条件风险控制(对特定 \(X=x\))。能否在 LTT 框架内引入条件风险控制的近似保证,类似 Romano et al. (2020) [18] 对分类的做法?(扎根:intro 对边际覆盖与条件覆盖的讨论,以及 [22] 的不可能结果留下的缝隙)
-
与保形预测的效率比较:在风险函数恰好单调且 \(\lambda\) 一维时,LTT(多重检验)与 RCPS(直接排序+单点检验)都能工作。LTT 在此设定下是否比 RCPS 更保守?能否给出两者保守性的定量比较?(扎根:intro 对 RCPS 的引用"all previous work... have required that \(\lambda\) is one-dimensional and that the risk function be monotonic",以及 LTT 在此特例下是否退化为 RCPS 的分析缺失)
提醒:要确认某条是不是真 gap,去读同子领域近期约 5 篇的 intro——都指向它 = 共识(真 gap),互相打架 = 机会。
Maintained by 陈星宇 · Homepage · Source on GitHub