跳转至

Sequential Conformal Calibration under Recursive Selection

作者: Yuning Yang, Zexuan Liu, Tianci Wang, Danlin Li
主题: 因果推断
相关性: 6/10
链接: https://arxiv.org/abs/2610.12937


一、领域脉络与小综述

这个方向是什么:本文属于"分布自由、有限样本的推断保证"这一谱系,具体研究多阶段决策问题中的序贯共形校准。根本问题是:当一个决策链条中,早期决策(如库存阈值)决定了哪些样本"存活"到后续阶段,而后续阶段的评分函数又可能基于早期校准结果重新拟合时,如何对整个决策序列的每个前缀提供覆盖保证。这是一个将共形预测从"单次预测区间"推广到"嵌套约束序列"的问题,其数学核心是在递归选择(recursive selection)造成的依赖结构下维持重排不变性(exchangeability)。

发展脉络: - 奠基工作:共形预测的基本框架由 Vovk 等人建立,其核心思想是利用样本间的交换性,通过排名构造分布自由的预测集。本文引用的 Vovk (2012) 给出了单次覆盖的精确二项分布刻画(Proposition 2b),这是本文二项稀释 Beta 链的直接前身。 - 主要进展:Cao (2024) 将共形预测用于新闻供应商(newsvendor)问题,在模型误设定下校准订货量,这是"共形+运营决策"的代表作。Li et al. (2026) 的 COINS 方法提出了任意阶段有效的序贯共形预测,但其构造是"校准-only"的,不涉及评分函数的重新拟合。Jin & Ren (2025) 和 Wang et al. (2024) 分别处理选择后覆盖和共形多重检验,与本文共享"选择改变总体"这一核心困难。 - 当前 frontier:本文声称的缺口是:当评分函数本身依赖早期校准结果(即"可预测重排")时,重排不变性可能失效。COINS 的累积计数构造在固定评分下有效,但无法覆盖"评分被重新拟合"的情形。本文的 fresh-fold 构造正是为了填补这一缺口。

子线索聚类: 1. 共形预测的扩展(Vovk 2012; Romano et al. 2021; Chernozhukov et al. 2021; Gibbs et al. 2025; Jung et al. 2023):从边际覆盖走向条件覆盖、分组覆盖、非交换性修正。 2. 序贯与在线推断(Li et al. 2026; Jin & Ren 2025; Wang et al. 2024):覆盖保证随时间/选择阶段累积,强调"任意停止时间"或"任意前缀"的有效性。 3. 运营管理与库存理论(Clark & Scarf 1960; van Houtum 2006; Levi et al. 2007, 2015; Ban & Rudin 2019; Oroojlooyjadid et al. 2020; Besbes et al. 2026):多级库存系统的服务约束与成本优化,本文的序列条件分位数公式直接嵌入这一传统。

这个方向在追问的核心问题: 1. 选择偏差下的有效性:当校准总体由先前决策决定时,如何保证覆盖?本文的答案是 fresh fold + 条件交换性(Lemma 1)。 2. 数据重用与新鲜度的权衡:重用幸存者可以节省数据,但可能破坏交换性;fresh fold 恢复有效性但消耗数据。本文 Proposition 8 和 10 给出了精确的权衡刻画。 3. 校准目标与成本目标的耦合:库存成本不仅取决于覆盖,还取决于阈值的位置。本文 Theorem 4 给出了超额成本的上界,但只在特定条件下成立。

⚠️ 作者的 framing(这是作者的说法):作者将缺口定义为"递归选择下的重排失效",并声称 fresh-fold 构造是"显然的下一步"。具体语句:"If those earlier calibration cases are reused for later ranking, the fitted score can depend on them in a way that does not treat a surviving test case symmetrically. This asymmetry can invalidate the exchangeability underlying the usual conformal rank argument." 作者淡化了两个竞争路线:(i) 加权共形(如 Barber et al. 2023 的非交换性修正)——作者只在 Proposition 8 中讨论了固定评分下的严格幸存者重用,未将其与加权方案系统比较;(ii) 在线学习/ regret 框架——作者没有讨论 regret 界限,而是直接给出有限样本覆盖。什么明显该被引 / 该存在、却没出现在 intro 里:作者没有引用 Barber et al. (2023) 关于非交换性的一般性理论(虽然引用了其 2021 年的条件覆盖不可能性结果),也没有引用最近关于"共形+分布偏移"的加权方法(如 Tibshirani et al. 2019 的 weighted conformal)。这些是值得研究者去查的潜在对比点。

张力:未见明显对立引用。但存在一个内部张力:Proposition 8(b) 说固定评分下严格幸存者重用"完全有效"(exactly valid),而 Proposition 8(a) 说弱幸存者重用可能失败——两者之间的边界(什么构成"弱"选择)在正文中只通过反例刻画,没有一般性条件。另一个张力是 Theorem 4 Part I 与 Part II 的适用条件不同:Part I 需要全局振荡条件(oscillation),Part II 需要局部密度条件,二者覆盖的场景几乎不重叠。


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

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

记号清单(按出现顺序):

记号 含义 类型
\(Z = (X, Y)\) 一个统计单元,\(X\) 是决策前已知的上下文,\(Y = (Y_1, \ldots, Y_K)\) 是 \(K\) 个阶段的评估结果 随机变量
\(K\) 决策阶段总数 常数
\(R_k(z)\) 第 \(k\) 阶段的评分函数,\(R_k: \mathcal{Z} \to \mathbb{R}\) 固定或可重拟合的函数
\(\hat{t}_k\) 第 \(k\) 阶段的校准阈值 由数据决定的随机变量
\(\hat{q}_k(x)\) 第 \(k\) 阶段预测的分位数函数(如 \(\beta_k\) 分位数) 拟合的预测器
\(\hat{s}_k(x)\) 最终决策阈值,\(\hat{s}_k(x) = \hat{q}_k(x) + \hat{t}_k\) 随机函数
\(E_k\) 通过前 \(k\) 个约束的集合:\(E_k = \{z : R_j(z) \le \hat{t}_j, \forall j \le k\}\) 随机集合
\(E_k(Z)\) 测试单元通过前 \(k\) 个约束的事件 事件
\(a_k\) 目标前缀覆盖概率,\(a_k = \prod_{j=1}^k \beta_j\) 常数(设计参数)
\(\beta_k\) 第 \(k\) 阶段的条件目标覆盖:\(P(E_k \mid E_{k-1}) \ge \beta_k\) 常数
\(N_k\) 第 \(k\) 折(fresh fold)的校准样本量 常数
\(M_k\) 第 \(k\) 阶段幸存的校准样本数 随机变量
\(r_k\) 选择的排名:\(r_k = \lceil (M_k + 1)\beta_k \rceil\) 随机变量
\(F_k\) 到第 \(k\) 阶段为止的信息 \(\sigma\)-域 filtration
\(p_k\) 第 \(k\) 阶段的条件覆盖概率(随机变量) 随机变量
\(\theta_k(m)\) 排名取整松弛:\(\theta_k(m) = r_k(m)/(m+1) - \beta_k \in [0, 1/(m+1))\) 确定性函数

数据生成机制与可观测数据:

  • 训练数据:独立样本 \(Z_1, \ldots, Z_N \sim P\)(未知分布),用于拟合预测器 \(\hat{q}_k\)。
  • 校准数据:独立于训练数据的 \(N\) 个样本,被随机分成 \(K\) 个不相交的折(fold)\(I_1, \ldots, I_K\),大小分别为 \(N_1, \ldots, N_K\)。第 \(k\) 折只用于第 \(k\) 阶段的阈值校准。
  • 测试单元:一个新的独立样本 \(Z = (X, Y)\),与所有校准数据独立。
  • 可观测量:对每个校准样本 \(Z_i\),可以观测其上下文 \(X_i\) 和所有结果 \(Y_i\)(因为 \(Y\) 是事后评估的,不涉及实时决策)。对测试单元,决策前只观测 \(X\),\(Y\) 在决策后观测。

关键假设(在最小内核中):

  1. 可预测性(Predictability):第 \(k\) 阶段的评分函数 \(R_k\) 只依赖于 \(F_{k-1}\)(即训练数据、前 \(k-1\) 折的校准数据、以及前 \(k-1\) 个阈值),不依赖于第 \(k\) 折或测试单元。这是 Lemma 1 的核心条件。
  2. 原子性(Atomlessness):给定 \(F_{k-1}\) 和 \(E_{k-1}(Z)\),评分 \(R_k(Z)\) 的条件分布无原子。这保证排名均匀性。
  3. 正存活概率:\(P(E_{k-1}(Z) \mid F_{k-1}) > 0\),否则条件概率无定义。

第二步:最小内核

最简例子:\(K = 2\) 阶段,\(Z = (X, Y_1, Y_2)\),\(X\) 是标量上下文,\(Y_1, Y_2\) 是两个结果。目标是保证 \(P(Y_1 \le \hat{s}_1(X),\; Y_2 \le \hat{s}_2(X)) \ge a_2 = \beta_1 \beta_2\)。

朴素方法(失败):用同一组校准样本先校准 \(\hat{t}_1\),然后在幸存者 \(\{i : Y_{1i} \le \hat{s}_1(X_i)\}\) 中校准 \(\hat{t}_2\)。问题在于:幸存者集合是由 \(\hat{t}_1\) 选择的,而 \(\hat{t}_1\) 本身依赖于这些样本的值。测试单元 \(Z\) 的 \(Y_1\) 与幸存者的 \(Y_1\) 分布不同(幸存者的 \(Y_1\) 被截断了),因此 \(Y_2\) 的条件分布也不同——重排不变性失效。

本文方法(fresh fold):

  • 第 1 阶段:用折 \(I_1\) 的 \(N_1\) 个样本,计算 $\hat{t}_1 = $ 第 \(r_1\) 个顺序统计量,其中 \(r_1 = \lceil (N_1 + 1)\beta_1 \rceil\)。
  • 第 2 阶段:不使用 \(I_1\) 的幸存者,而是用折 \(I_2\) 的 \(N_2\) 个样本,但只保留其中满足 \(Y_{1i} \le \hat{s}_1(X_i)\) 的样本(即"存活"到第 2 阶段的样本)。设 \(M_2\) 为幸存者数,\(r_2 = \lceil (M_2 + 1)\beta_2 \rceil\),$\hat{t}_2 = $ 幸存者评分的第 \(r_2\) 个顺序统计量。

为什么有效:关键在 Lemma 1。固定 \(F_1\)(包括 \(\hat{t}_1\)),折 \(I_2\) 的样本与测试单元 \(Z\) 独立。条件于 \(E_1(Z)\)(测试单元通过第 1 阶段),\(Z\) 的评分 \(R_2(Z)\) 与 \(I_2\) 中幸存者的评分是 i.i.d. 的——因为 \(I_2\) 的样本没有参与 \(\hat{t}_1\) 的校准,所以"幸存"这一事件对 \(I_2\) 样本和测试单元是对称的。这就是"fresh"的含义:每一折只使用一次,避免了选择偏差。

核心数学命题(退化形式):

命题(单阶段覆盖):设 \(Y_1, \ldots, Y_m, Y\) 是 i.i.d. 连续随机变量,\(r = \lceil (m+1)\beta \rceil\),$\hat{t} = $ 第 \(r\) 个顺序统计量。则 \(P(Y \le \hat{t}) \ge \beta\),且若 \(r \le m\),\(P(Y \le \hat{t}) = r/(m+1) \in [\beta, \beta + 1/(m+1))\)。

多阶段推广(Theorem 1 的直觉):对每个 \(k\),条件于 \(F_{k-1}\) 和 \(E_{k-1}(Z)\),第 \(k\) 折幸存者的评分与测试单元的评分是 i.i.d. 的。因此单阶段命题给出条件覆盖 \(\ge \beta_k\)。然后取期望:

\[P(E_k(Z)) = E[P(E_k(Z) \mid F_{k-1})] \ge E[\beta_k \cdot \mathbf{1}_{E_{k-1}(Z)}] = \beta_k P(E_{k-1}(Z)),\]
递推得 \(P(E_k(Z)) \ge \prod_{j=1}^k \beta_j = a_k\)。

为什么这是"最小内核":整个论文的数学结构——Lemma 1(交换性)、Theorem 1(前缀覆盖)、Theorem 2(覆盖过程的 Beta 链刻画)、Proposition 1(有限样本松弛上界)——都是这个两阶段例子的严格化与推广。读者掌握这个例子后,读 Theorem 2 的证明只需补充"条件期望递推"和"Beta 分布与均匀顺序统计量的关系"两个工具。

可观测与不可观测的区分:研究者能观测到的是校准样本的完整结果 \((X_i, Y_i)\) 和测试单元的上下文 \(X\);不可观测的是测试单元的 \(Y\)(决策前)。所有覆盖保证都是关于"测试单元的 \(Y\)"的边际或条件概率,积分掉训练数据和校准数据的随机性。


三、这篇论文做了什么

三句话

  1. 研究问题:在多阶段决策中,当早期决策决定后续校准总体、且评分函数可能基于早期校准结果重新拟合时,如何为决策序列的每个前缀提供有限样本、分布自由的覆盖保证。
  2. 核心方法:提出"每阶段使用新折(fresh fold)"的校准方案,证明在可预测重排(predictable refitting)下,条件于早期折,所选折的幸存者评分与测试评分保持交换性,从而覆盖保证对每个前缀成立。
  3. 主要结论:推导出覆盖过程的通用"二项稀释 Beta 链"(Binomial-thinned Beta chain),其分布仅依赖于折大小和目标水平;给出精确的覆盖松弛、弃权概率和校准预算的有限样本刻画;并证明固定评分下严格幸存者重用完全有效,自适应评分下重用可能造成最坏情况秩损失。

设定与假设(完整版)

  • 数据:训练样本、\(K\) 个不相交的校准折 \(I_1, \ldots, I_K\)(大小 \(N_1, \ldots, N_K\))、一个独立测试单元 \(Z\)。
  • 信息结构:\(F_0\) 包含训练数据和折分配;\(F_k = \sigma(F_0, Z_i : i \in \cup_{j \le k} I_j)\)。
  • 可预测性:评分函数 \(R_k\) 是 \(F_{k-1} \otimes \mathcal{B}(\mathcal{Z})\) 可测的(即只依赖过去的信息)。
  • 原子性:给定 \(F_{k-1}\) 和 \(E_{k-1}(Z)\),\(R_k(Z)\) 的条件分布无原子。
  • 目标:\(P(E_k(Z)) \ge a_k = \prod_{j=1}^k \beta_j\),其中 \(E_k = \{z : R_j(z) \le \hat{t}_j, \forall j \le k\}\)。

主要结果

Theorem 1(序贯覆盖):在可预测性和原子性下,fresh-fold 方案满足 \(P(E_k(Z)) \ge a_k\) 对所有 \(k\) 成立。证明路线:Lemma 1 给出条件交换性,然后用条件期望递推(见第二节)。

Theorem 2(覆盖过程的普适律):设 \(p_k = P(E_k(Z) \mid F_k)\) 为 realized 覆盖概率。在原子性下,\((M_k, p_k)\) 构成马尔可夫链,其转移核仅依赖于 \((N_k, \beta_k)\):\(M_k \sim \text{Binomial}(N_k, p_{k-1})\),且给定 \(M_k = m\),\(p_k = p_{k-1} V_k\),其中 \(V_k \sim \text{Beta}(r_k(m), m+1-r_k(m))\)(若 \(r_k(m) \le m\)),否则 \(V_k = 1\)。这个结果的深刻之处在于普适性:无论数据分布、评分函数、预测器如何,只要可预测性和原子性成立,覆盖过程的分布就完全由折大小和目标水平决定。证明路线:先用 Lemma 1 将条件分布转化为 i.i.d. 均匀顺序统计量,再用 Beta 分布与均匀顺序统计量的经典关系。

Proposition 1(有限样本松弛):\(0 \le P(E_k(Z)) - a_k \le \sum_{j=1}^k (a_k/a_j)/(N_j + 1)\)。证明:从 Theorem 2 的 Beta 链出发,利用 \(\theta_j(m) \le 1/(m+1)\) 和条件期望递推。

Proposition 8(重用边界): - (a) 弱幸存者重用(评分 \(\le\) 阈值)可能失败,给出精确反例:\(Z \sim U(0,1)\),\(R_1(z) = z\),\(R_2(z) = -z\),\(N=40\),\(\beta_1 = \beta_2 = 1/2\),实际覆盖 \(= 10/41 < 1/4\)。 - (b) 严格幸存者重用(评分 \(<\) 阈值)在固定评分下完全有效:\(P(E_k(Z)) = S_k/(N+1)\),其中 \(S_k = \lceil (N+1)a_k \rceil\)。证明用排列对称性。 - (c) 自适应评分下,每个重用样本可造成最多 1 的秩损失,因此需要 \(u + f\) 的修正。

Proposition 9(校准预算):必要条件是 \(N_k \ge m_k^* = \lceil \beta_k/(1-\beta_k) \rceil\)(否则必然弃权);充分条件是 \(N \ge (1-\eta) \sum_k m_k^*/\bar{a}_{k-1}\)(其中 \(\bar{a}_{k-1}\) 是 Proposition 1 的上界),此时所有阈值以概率 \(\ge 1-\eta\) 有限。

Proposition 10(分块重用):将阶段分组,每组共享一个 fresh fold,组内用累积计数(COINS 风格)。覆盖松弛为 \(\sum_{\text{blocks}} (a_K/a_{e_l})/(N_l+1)\)。

Proposition 11(分组条件覆盖):若评分函数在预定义的上下文组内分别校准(Mondrian 风格),则组条件覆盖保证成立,松弛项与组大小成反比。

Theorem 4(超额成本):Part I(全局过程,允许重拟合)在振荡条件(oscillation)下给出 \(\|\hat{s}_k - s^*_k\|_\infty\) 的界,进而给出超额成本 \(O(\sum_k (\omega_k + \gamma_k/\phi_k)^2)\)。Part II(固定评分)给出加权 \(L^2\) 界,常数是 \(\bar{\Lambda}/2\) 乘以方差项 \(V_\Lambda(q)\) 和失配项 \(M(q)\) 之和。

证明路线与技术技巧

  • 整体路线:从"条件交换性"(Lemma 1)出发,建立"覆盖概率递推"(Theorem 1),然后将递推嵌入马尔可夫链框架(Theorem 2),从而把多阶段问题转化为单阶段 Beta 链的分析。这种"先交换性、后马尔可夫链"的两步走是本文证明的骨架。
  • 关键技巧 1:fresh fold 的构造。将校准数据分成 \(K\) 折,每折只用于一个阶段。这避免了"同一批样本既参与选择又参与校准"的循环依赖。代价是校准效率降低(每阶段只用 \(N_k\) 个样本),但换来的是普适的覆盖保证。
  • 关键技巧 2:条件期望递推。Theorem 1 的证明不使用任何分布假设,只依赖条件期望的塔性质。这体现了"分布自由"的本质。
  • 关键技巧 3:Beta 链的普适性。Theorem 2 的关键洞察是:给定 \(F_{k-1}\) 和 \(M_k = m\),\(V_k\) 的条件分布是 Beta\((r_k(m), m+1-r_k(m))\),与 \(P\) 无关。这来自均匀顺序统计量的经典性质。这个"普适性"使得模拟链成为可能,无需知道数据分布。
  • 关键技巧 4:反例构造。Proposition 8(a) 的反例(\(R_1 = z\), \(R_2 = -z\))极其简洁,直接暴露了弱幸存者重用的本质问题:幸存者的 \(R_2\) 分布与测试单元的 \(R_2\) 分布相反。
  • 关键技巧 5:分块与分组。Proposition 10 和 11 展示了如何将 fresh fold 的思想与已有的 COINS 和 Mondrian 方法结合,在数据效率与有效性之间取折中。

真实例子与应用

  1. 三梯队库存模拟(Section 6.1):\(K=3\) 阶段,Gamma 需求,误设定的线性-高斯预测器。结果:fresh-fold 重拟合达到 81.98% 最终前缀覆盖率(目标 81.82%),平均成本比 Bonferroni 基线低 5.5%。这个例子验证了 Theorem 1 的预测,并展示了重拟合(refitting)的实际收益。
  2. 深度敏感性实验(Section 6.1):固定总校准预算,变化阶段数 \(K \in \{2,3,5,7,10\}\)。结果:fresh fold 在深度增加时弃权概率上升(如 \(N=300, K=10\) 时 64% 弃权率),与 Proposition 9 的预测一致;Bonferroni 从不弃权但覆盖过度。
  3. 自行车共享数据(Section 6.2):4260 个非重叠四小时周期,时间序列切分。结果:fresh fold 在 \(N=1000\) 时达到 81.43%(LQR)和 80.54%(GB)的最终覆盖率,接近目标 81.82%;Bonferroni 覆盖 89-91%,成本更高。这个例子展示了方法在真实数据上的可行性,但作者明确说明这是"压力测试"而非部署评估。

🔎 结论是否比证明窄

  • Theorem 2 的普适性被过度声称:Theorem 2 的"普适"依赖于原子性假设。作者在正文中承认"ties occur with probability zero"(Appendix G.6),但在摘要和引言中未提及这一限制。对于离散数据(如计数需求),原子性不成立,覆盖保证需要修正(Proposition 8 的排列论证部分处理了 ties,但 Theorem 2 的 Beta 链不适用)。
  • Theorem 4 Part I 的振荡条件在实际中不可验证:\(\omega_k\)(振荡界)是预测器误差的全局上确界,对于非线性预测器(如梯度提升)通常无法计算。作者在 Appendix C 中承认这一点,但正文的表述("bounded by the variation of the learner's bias")可能让读者误以为这是一个可操作的界。
  • Proposition 8(c) 的"秩损失"界是保守的:作者证明每个重用样本最多造成 1 的秩损失,但未给出达到该界的条件。实际损失可能远小于此,但论文没有提供更紧的界。
  • 实验部分的成本比较不完整:Table 6 中 fresh fold 的成本优势是在特定需求分布和预测器下得到的,作者没有提供不同误设定程度下的敏感性分析。Appendix F.5 的"learner robustness"只改变了预测器族,没有改变需求分布族。

四、开放问题

  1. 离散数据的序贯校准:Theorem 2 的 Beta 链依赖原子性。对于离散分布(如 Poisson 需求),如何刻画覆盖过程的分布?是否需要新的链结构?(扎根于 Theorem 2 的假设和 Appendix G.6 的 ties 讨论。)
  2. 自适应重拟合的紧界:Proposition 8(c) 给出每个重用样本 1 的秩损失,但实际损失可能更小。能否给出依赖数据分布的更紧界?是否存在"温和自适应"(如仅更新截距)下秩损失更小的方案?(扎根于 Proposition 8(c) 的保守性。)
  3. 弃权与执行的权衡:Proposition 9 给出了弃权概率的精确公式,但论文没有讨论"弃权后怎么办"(如回退到 Bonferroni 或使用默认阈值)。弃权-回退策略的联合覆盖保证是什么?(扎根于 Proposition 9 和 Appendix F.1 的弃权数据。)
  4. 分组条件覆盖的粒度选择:Proposition 11 的组划分是预定义的。如何数据自适应地选择分组?分组过细导致样本不足,过粗则条件保证退化。是否存在最优分组策略?(扎根于 Proposition 11 和 Remark 10 的 cell budget 讨论。)
  5. 时间依赖与状态转移:自行车数据实验暴露了时间序列中的分布漂移,但理论框架假设独立周期。若周期之间存在状态依赖(如库存结转),fresh fold 的交换性论证是否仍然成立?(扎根于 Section 6.2 的"chronological split"和作者关于"independent planning cycles"的假设。)

提醒:要确认上述某条是否是真 gap,建议去读"conformal prediction under distribution shift"(如 Barber et al. 2023)、"weighted conformal"(Tibshirani et al. 2019)以及"online conformal prediction"(如 Gibbs & Candès 2021)近 5 篇的 intro——如果它们都指向同一个未解决问题,那就是共识性 gap;如果它们互相打架,那可能是更值得挖掘的机会。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论