揭示了预测置信度与效率的固有权衡，指出高置信度必导致预测集指数级膨胀。
Fundamental bounds on efficiency-confidence trade-off for transductive conformal prediction
- 提出有限样本下置信度与预测集大小的严格边界
- 预测集大小随样本数线性增长，且与数据条件熵成正比
- 新算法优于传统Bonferroni方法，适用于需高效置信预测场景
横贯式共形预测同时处理多个数据点的预测。给定目标置信水平，目标是构造一个包含真实结果的概率不低于指定值的预测集。本文揭示了横贯式方法中置信度与效率之间的根本权衡，其中效率以预测集大小衡量。具体地，我们推导出一个严格的有限样本界，表明任何非平凡置信水平均会导致具有内在不确定性的数据上预测集大小呈指数增长。该指数随样本数量线性增长，且与数据的条件熵成正比。此外，该界包含一个二阶项——称为离散度，定义为对数条件概率分布的方差。我们证明基于近似条件分布的横贯式方法可逼近此界。受此启发，我们提出一种实用的横贯式预测算法，其性能优于传统的Bonferroni方法。
原文摘要 · Abstract (English)
Transductive conformal prediction addresses the simultaneous prediction for multiple data points. Given a desired confidence level, the objective is to construct a prediction set that includes the true outcomes with the prescribed confidence. We demonstrate a fundamental trade-off between confidence and efficiency in transductive methods, where efficiency is measured by the size of the prediction sets. Specifically, we derive a strict finite-sample bound showing that any non-trivial confidence level leads to exponential growth in prediction set size for data with inherent uncertainty. The exponent scales linearly with the number of samples and is proportional to the conditional entropy of the data. Additionally, the bound includes a second-order term, dispersion, defined as the variance of the log conditional probability distribution. We show that the transductive methods based on the approximate conditional distribution can approach this bound. Inspired by this setup, we introduce a practical transductive prediction algorithm that surpasses Bonferroni methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。