Conformal prediction (CP) is a wrapper around traditional machine learning models, giving coverage guarantees under the sole assumption of exchangeability; in classification problems, for a chosen significance level $\varepsilon$, CP guarantees that the error rate is at most $\varepsilon$, irrespective of whether the underlying model is misspecified. However, the prohibitive computational costs of "full" CP led researchers to design scalable alternatives, which alas do not attain the same guarantees or statistical power of full CP. In this paper, we use influence functions to efficiently approximate full CP. We prove that our method is a consistent approximation of full CP, and empirically show that the approximation error becomes smaller as the training set increases; e.g., for $10^{3}$ training points the two methods output p-values that are $<10^{-3}$ apart: a negligible error for any practical application. Our methods enable scaling full CP to large real-world datasets. We compare our full CP approximation (ACP) to mainstream CP alternatives, and observe that our method is computationally competitive whilst enjoying the statistical predictive power of full CP.
翻译:共变预测(CP)是围绕传统机器学习模式的包装(CP),在唯一假设的互换性假设下提供覆盖保障;在分类问题中,对于所选定的重要水平,美元和瓦列普西隆值,CP保证误差率最高为$和瓦列普西隆值,而不论基本模型的描述是否错误。然而, " 全面 " CP的令人望而却步的计算成本导致研究人员设计了可缩放的替代方法,这些替代方法不能达到完全CP的保障或统计能力。在本文中,我们使用影响功能来有效地接近全部CP。我们证明我们的方法是完全CP的近似近似值,并且从经验上表明,随着培训设置的增加,近似误差率会越来越小;例如,10 ⁇ 3美元的培训发现,两种方法的p价值是 < {%-3}美元,而两者相分离:对于任何实际应用来说,一个微不足道的错误。我们的方法能够将整个CP缩成大型真实世界数据集。我们把我们的完全CP接近值与CP替代方法进行比较,我们发现我们的方法在计算上具有竞争力,同时具有计算上具有竞争力。