The Price of Choice in Selective Prediction
作者: Daniel Cieślak, Andrzej Czyżewski
分类: cs.LG
发布日期: 2026-10-21
备注: 43 pages, including appendices
💡 一句话要点
提出选择性预测中的成本分析以优化分类器性能
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 选择性分类器 风险覆盖 样本成本 交集-并集测试 机器学习 决策支持 多重性校正
📋 核心要点
- 现有选择性分类器在满足风险覆盖合同时，面临样本成本随菜单复杂度增加而上升的挑战。
- 本文提出了一种交集-并集测试（IUT）方法，能够在不进行多重性校正的情况下有效评估分类器的风险和覆盖率。
- 实验结果表明，在不同的覆盖率条件下，样本成本变化显著，且IUT方法在多种情况下表现出强大的性能和稳定性。
📝 摘要（中文）
选择性分类器可以通过预先声明的规则菜单（如阈值或K个得分区间的并集）来满足风险覆盖合同，要求覆盖率至少为κ且错误率不超过α。为了反驳这一存在性声明，需要排除所有允许的规则。交集-并集测试（IUT）在不进行多重性校正的情况下实现有效性，但其样本成本可能随着菜单丰富度的增加而增加。本文对这一成本进行了表征，并与最优审计进行了比较。在固定的内部风险目标α和间隙γ下，K区间菜单在覆盖率底线κ下的最小样本量为K(1-κ)/(κγ²)，在小间隙、大菜单的情况下，精确的IUT达到了这一速率。即使在已知得分分布的情况下，下界仍然成立，而上界扩展到VC维数为d的菜单。拒绝任何规则在审计样本上可行的程序可能会支付线性K成本，即使平方根速率是可能的。
🔬 方法详解
问题定义：本文解决选择性分类器在满足风险覆盖合同时的样本成本问题，现有方法在菜单复杂度增加时样本成本显著上升。
核心思路：提出交集-并集测试（IUT），通过有效的规则评估机制，避免多重性校正带来的额外成本，优化样本使用效率。
技术框架：整体流程包括定义风险覆盖合同、构建得分区间菜单、实施IUT方法进行规则验证，并通过样本审计评估分类器性能。
关键创新：IUT方法在不需要多重性校正的情况下，能够有效降低样本成本，并在小间隙、大菜单的情况下达到最优样本量。
关键设计：设定固定的内部风险目标α和间隙γ，利用K区间菜单的结构，确保在覆盖率底线κ下实现最小样本量，同时考虑VC维数对样本需求的影响。
📊 实验亮点
实验结果显示，在K=4的情况下，样本成本在覆盖率κ从0.5变化到0.95时，变化幅度达到7.7倍。经过理论驱动的归一化处理后，最终值差异约为5%。在60个特定信心门限的实验中，28/30个合同在未触及的审计中保持隐蔽，显示出IUT方法的强大性能。
🎯 应用场景
该研究的潜在应用领域包括机器学习中的选择性预测、风险管理和决策支持系统。通过优化样本成本，能够提高分类器的效率和准确性，进而在金融、医疗和自动驾驶等领域产生实际价值。未来，随着数据量的增加和模型复杂性的提升，本文的方法有望在更广泛的应用场景中发挥重要作用。
📄 摘要（原文）
A selective classifier may be claimed to satisfy a risk-coverage contract if some rule from a predeclared menu (a threshold or a union of $K$ score intervals) attains coverage at least $κ$ and error at most $α$. Refuting this existential claim requires ruling out every permitted rule. The intersection-union test (IUT) achieves validity without a multiplicity correction, but its sample cost can increase with menu richness. We characterize this cost and compare it with the optimal audit. For a fixed interior risk target $α$ and gap $γ$, the minimax sample size for K-interval menus at coverage floor $κ$ is $K(1-κ)/(κγ^2)$, up to logarithmic factors, in the stated small-gap, large-menu regime; exact IUT attains this rate. The lower bound holds even with a known score distribution, while the upper bound extends to menus of VC dimension $d$. Procedures that refuse to reject whenever any rule appears feasible on the audit sample can pay a linear $K$ cost even when a square-root rate is possible. Reference-free testing reaches a smaller scale under constant-risk alternatives, whereas unknown heterogeneous risks can make the linear cost unavoidable. In simulations with $K=4$, the raw menu cost varies 7.7-fold between $κ=.5$ and $κ=.95$; after theorem-motivated normalization the endpoint values differ by approximately 5%. Held-out experiments with three VLM judges show positive exact-hiding windows in all 60 split-specific confidence-gate families, with 28/30 contracts chosen on audit-A remaining hidden on untouched audit-B. On a cleaner multi-annotator target, hiding is weaker and transfers in 3/10 resplits. Frozen image and multimodal classifiers show boundary behavior consistent with the IUT guarantee and strong power relative to practical certificates.