Conformal Prediction for Class-wise Coverage via Augmented Label Rank Calibration
2406.06818
0
0
🔮
Abstract
Conformal prediction (CP) is an emerging uncertainty quantification framework that allows us to construct a prediction set to cover the true label with a pre-specified marginal or conditional probability. Although the valid coverage guarantee has been extensively studied for classification problems, CP often produces large prediction sets which may not be practically useful. This issue is exacerbated for the setting of class-conditional coverage on imbalanced classification tasks. This paper proposes the Rank Calibrated Class-conditional CP (RC3P) algorithm to reduce the prediction set sizes to achieve class-conditional coverage, where the valid coverage holds for each class. In contrast to the standard class-conditional CP (CCP) method that uniformly thresholds the class-wise conformity score for each class, the augmented label rank calibration step allows RC3P to selectively iterate this class-wise thresholding subroutine only for a subset of classes whose class-wise top-k error is small. We prove that agnostic to the classifier and data distribution, RC3P achieves class-wise coverage. We also show that RC3P reduces the size of prediction sets compared to the CCP method. Comprehensive experiments on multiple real-world datasets demonstrate that RC3P achieves class-wise coverage and 26.25% reduction in prediction set sizes on average.
Create account to get full access
Overview
- Conformal prediction (CP) is a framework for constructing prediction sets that cover the true label with a pre-specified probability.
- While CP has been extensively studied for classification problems, the resulting prediction sets can be large and impractical.
- This is especially true for class-conditional coverage on imbalanced classification tasks, where the valid coverage guarantee may not hold for all classes.
Plain English Explanation
Conformal prediction is a way to create prediction sets that are guaranteed to contain the true label a certain percentage of the time. For example, you could create a prediction set that contains the true label 95% of the time. [Link to https://aimodels.fyi/papers/arxiv/verifiably-robust-conformal-prediction]
However, these prediction sets can often be quite large, making them less useful in practice. This is particularly problematic for imbalanced classification tasks, where the classes are not evenly distributed. [Link to https://aimodels.fyi/papers/arxiv/conformal-prediction-score-that-is-robust-to]
Imagine you're trying to classify images as either "dog" or "cat". If there are many more dog images than cat images in your training data, the conformal prediction method may struggle to achieve good coverage for the cat class. This means that the prediction set for a cat image could be very large, covering most or all of the possible classes.
Technical Explanation
The paper proposes a new algorithm called Rank Calibrated Class-conditional CP (RC3P) to address this issue. RC3P modifies the standard class-conditional CP (CCP) method in two key ways:
-
It uses a label rank calibration step to selectively apply the class-wise thresholding subroutine only to classes with small top-k error. This helps reduce the size of the prediction sets.
-
It can provably achieve class-wise coverage, meaning the valid coverage guarantee holds for each individual class, even on imbalanced datasets. [Link to https://aimodels.fyi/papers/arxiv/conformal-prediction-deep-classifier-via-label-ranking]
The authors show that RC3P outperforms the standard CCP method, reducing prediction set sizes by an average of 26.25% across multiple real-world datasets. [Link to https://aimodels.fyi/papers/arxiv/provably-robust-conformal-prediction-improved-efficiency]
Critical Analysis
The paper presents a solid technical contribution, with a well-designed algorithm and thorough theoretical and experimental analysis. However, some potential limitations and areas for further research are:
- The performance of RC3P may still degrade on highly imbalanced datasets, where the top-k error for some classes remains high. [Link to https://aimodels.fyi/papers/arxiv/conformal-prediction-learned-features]
- The computational overhead of the label rank calibration step may be significant, especially for large datasets or models with many classes.
- It would be interesting to see how RC3P compares to other approaches for improving conformal prediction, such as using learned features or calibrating the conformity scores.
Conclusion
Overall, the Rank Calibrated Class-conditional CP (RC3P) algorithm is a promising step towards making conformal prediction more practical and useful, particularly for imbalanced classification tasks. By selectively applying class-wise thresholding and achieving provable class-wise coverage, RC3P can significantly reduce the size of prediction sets while maintaining the desirable statistical guarantees of conformal prediction.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
Verifiably Robust Conformal Prediction
Linus Jeary, Tom Kuipers, Mehran Hosseini, Nicola Paoletti
0
0
Conformal Prediction (CP) is a popular uncertainty quantification method that provides distribution-free, statistically valid prediction sets, assuming that training and test data are exchangeable. In such a case, CP's prediction sets are guaranteed to cover the (unknown) true test output with a user-specified probability. Nevertheless, this guarantee is violated when the data is subjected to adversarial attacks, which often result in a significant loss of coverage. Recently, several approaches have been put forward to recover CP guarantees in this setting. These approaches leverage variations of randomised smoothing to produce conservative sets which account for the effect of the adversarial perturbations. They are, however, limited in that they only support $ell^2$-bounded perturbations and classification tasks. This paper introduces VRCP (Verifiably Robust Conformal Prediction), a new framework that leverages recent neural network verification methods to recover coverage guarantees under adversarial attacks. Our VRCP method is the first to support perturbations bounded by arbitrary norms including $ell^1$, $ell^2$, and $ell^infty$, as well as regression tasks. We evaluate and compare our approach on image classification tasks (CIFAR10, CIFAR100, and TinyImageNet) and regression tasks for deep reinforcement learning environments. In every case, VRCP achieves above nominal coverage and yields significantly more efficient and informative prediction regions than the SotA.
6/7/2024
A Conformal Prediction Score that is Robust to Label Noise
Coby Penso, Jacob Goldberger
0
0
Conformal Prediction (CP) quantifies network uncertainty by building a small prediction set with a pre-defined probability that the correct class is within this set. In this study we tackle the problem of CP calibration based on a validation set with noisy labels. We introduce a conformal score that is robust to label noise. The noise-free conformal score is estimated using the noisy labeled data and the noise level. In the test phase the noise-free score is used to form the prediction set. We applied the proposed algorithm to several standard medical imaging classification datasets. We show that our method outperforms current methods by a large margin, in terms of the average size of the prediction set, while maintaining the required coverage.
5/22/2024
🔮
Provably Robust Conformal Prediction with Improved Efficiency
Ge Yan, Yaniv Romano, Tsui-Wei Weng
0
0
Conformal prediction is a powerful tool to generate uncertainty sets with guaranteed coverage using any predictive model, under the assumption that the training and test data are i.i.d.. Recently, it has been shown that adversarial examples are able to manipulate conformal methods to construct prediction sets with invalid coverage rates, as the i.i.d. assumption is violated. To address this issue, a recent work, Randomized Smoothed Conformal Prediction (RSCP), was first proposed to certify the robustness of conformal prediction methods to adversarial noise. However, RSCP has two major limitations: (i) its robustness guarantee is flawed when used in practice and (ii) it tends to produce large uncertainty sets. To address these limitations, we first propose a novel framework called RSCP+ to provide provable robustness guarantee in evaluation, which fixes the issues in the original RSCP method. Next, we propose two novel methods, Post-Training Transformation (PTT) and Robust Conformal Training (RCT), to effectively reduce prediction set size with little computation overhead. Experimental results in CIFAR10, CIFAR100, and ImageNet suggest the baseline method only yields trivial predictions including full label set, while our methods could boost the efficiency by up to $4.36times$, $5.46times$, and $16.9times$ respectively and provide practical robustness guarantee. Our codes are available at https://github.com/Trustworthy-ML-Lab/Provably-Robust-Conformal-Prediction.
5/1/2024
Conformal Prediction for Deep Classifier via Label Ranking
Jianguo Huang, Huajun Xi, Linjun Zhang, Huaxiu Yao, Yue Qiu, Hongxin Wei
0
0
Conformal prediction is a statistical framework that generates prediction sets containing ground-truth labels with a desired coverage guarantee. The predicted probabilities produced by machine learning models are generally miscalibrated, leading to large prediction sets in conformal prediction. To address this issue, we propose a novel algorithm named $textit{Sorted Adaptive Prediction Sets}$ (SAPS), which discards all the probability values except for the maximum softmax probability. The key idea behind SAPS is to minimize the dependence of the non-conformity score on the probability values while retaining the uncertainty information. In this manner, SAPS can produce compact prediction sets and communicate instance-wise uncertainty. Extensive experiments validate that SAPS not only lessens the prediction sets but also broadly enhances the conditional coverage rate of prediction sets.
6/7/2024