Fundamental bounds on efficiency-confidence trade-off for transductive conformal prediction
Arash Behboodi, Alvaro H. C. Correia, Fabio Valerio Massoli, Christos Louizos
cs.LG, cs.IT, stat.ML
2025-09-05
Qualcomm 证明直推 conformal 只要联合置信不塌到零，预测集期望大小就按 n·H(Y|X) 指数膨胀；TSCP 在 MNIST、n=3 上效率指数 0.33，Bonferroni 版 SCP 是 0.93。
标准 conformal prediction 给单条预测做边缘覆盖：每个输入单独出一个集合，真实标签以至少 1−α 的概率落在里面。质检一批零件、筛一批样本、批准一组代码改动时，错一条就整批作废，需要的是联合覆盖：n 个测试点的标签向量同时落在一个联合预测集里。
直推 conformal prediction（TCP）就是做这件事。Vovk 给过 Bonferroni 拼法：每条用 α/n 做普通 conformal，再取笛卡尔积。覆盖能保住，集合随 n 涨得很快。Qualcomm AI Research 这篇要回答的是更硬的问题：联合集合平均能有多小，同时还能保住给定置信。
效率用联合预测集的期望基数衡量，增长率写成 γ{n,m} = (1/n) log E|Γ|。主定理把标签固有不确定性和集合大小连起来：对任意 β∈(0,1)，P(P(Y|X)≤β) ≤ α + β E|Γ|。条件分布越散，左边对小 β 越大，集合下界就越松不得。
渐近上有相变。只要 lim inf (1−αn)>0，就有 γ ≥ H(Y|X)；反过来，若增长率严格低于条件熵，置信会塌到零。有限样本用 Berry–Esseen 把 n 项 log P(Yi|Xi) 的和展开，多出一项 dispersion σ，即 log P(Y|X) 的标准差，外加三阶矩 ρ。近似界是 nγ ≥ n H(Y|X) + √n σ Q^{−1}(α) − (log n)/2 + O(1)。Q 是高斯尾函数。这套写法直接借自有限码长 Shannon 容量分析。
界是可及的。若预言机给出真 P(Y|X)，把所有乘积概率超过阈值 β 的标签向量收进集合，一、二阶项与下界对齐。用近似分布 Q 时，额外惩罚是 E[D(P(·|X)∥Q(·|X))]。
据此给出 Transductive Split Conformal Prediction（TSCP）：把模型分数 f(x)[y] 当成近似条件概率，校准集上用 1−∏ f(xj)[yj] 做非一致性分数，取有限样本校正分位数，测试时收进乘积分数过阈的标签组。朴素搜索是 O(|Y|^n)，可按乘积结构动态规划剪枝。
实验在 MNIST / FashionMNIST / CIFAR-10 / CIFAR-100 上用对称标签噪声控制不确定性（保留概率 1−ε=0.98），LeNet-5 和 ResNet-20，校准集约 180 条，α=0.1。对数用 base 2。效率指数的理论上界是 log₂(类别数)，10 类是 3.32，100 类是 6.64。
MNIST、n=3：TSCP 的 γ 是 0.333，Bonferroni 版 split CP 是 0.926，APS 是 1.068。n=9：TSCP 0.813，SCP 2.895，APS 2.919。FashionMNIST、n=3：0.787 对 SCP 的 1.404。CIFAR-10、n=3：0.995 对 1.679。CIFAR-100 上优势缩小：n=3 时 3.418 对 4.900，n=9 时 TSCP 6.608、SCP 6.539，两边都顶到类别数上界附近，TSCP 的经验联合覆盖还略低（0.88 对 0.92）。
Bonferroni 在 n 变大时崩得很快：α=0.1、n=20 意味着每条置信 0.005，校准集一有限，集合就接近全标签。TSCP 在 n<10 时贴着理论界走；n 再大，校准集约 180 条要按 n 分组，有效校准只剩 180/n，覆盖和效率一起受影响。用真条件分布能打到界上；把分布扰动到 KL 约 0.12 和 0.26 时，效率按定理里的 KL 项变差。
这是给联合不确定量化画的 Shannon 式定额：合成数据上 H(Y|X) 和 σ 可算时，新方法该拿这张图当靶，而不是只跟 Bonferroni 比谁不那么差。实践上，需要整批零错误的系统不该默认 α/n 笛卡尔积。TSCP 把模型概率直接当成一致性分数，是对「最优集合由条件分布的水平集给出」这条理论的工程翻译。
它是渐进改进加一块硬下界，不是新的覆盖理论。覆盖仍然只依赖可交换性。
有限样本界假定测试点 i.i.d.，作者把推广到非 i.i.d. 列为未来工作。H(Y|X) 和 σ 在真实数据上未知；若用同一个 Q 既估这些量又建集合，上下界会贴在一起，给不出新信息。TSCP 的有效校准随 n 变小，表里 CIFAR-100、n=9 已经贴上界，谈不上赢。实验全是带人造标签噪声的视觉分类，没有语言或结构化输出。联合集合的枚举对大 |Y| 或大 n 仍贵，动态规划只是缓解。定理对任何一致性分数成立，因此不依赖训练样本量 m，也解释不了「更多校准能换更小集合」这件事。