Conformal Prediction for Deep Classifier via Label Ranking

Thank you for the recognition. We address specific concerns below.

1. Choice of $\lambda$. [Q1]

For SAPS and RAPS, we utilize a validation set to tune hyperparameters and the remaining dataset to calibrate the $\tau$. For APS, we calibrate the threshold $\tau$ on the whole calibration set.

Thanks for your recognition and the valuable suggestions. We give a detailed response to your questions and comments in the following.

1. Adaption of sets.[W1]

In the literature of conformal prediction, the size of prediction sets is expected to represent the inherent uncertainty of the classifier's predictions. With a comparable set size, methods with high adaption can reflect instance-wise uncertainty precisely [R1]. Specifically, prediction sets should be larger for hard examples than for easy ones. Adaption is particularly significant in high-stakes scenarios where assessing the model's reliability is necessary. In Figure 3b, we show SAPS preserves more distinguishable information than RAPS, while achieving a smaller average set size and desired coverage rate. This advantage further strengthens the value of the proposed method.

2. Gap between SAPS and ground truth [W2]

We guess that the "ground truth" is the sets produced by APS with the oracle model (correct us if we are mistaken). In Proposition 2, we provide a theoretical result, suggesting that SAPS is capable of producing smaller sets than APS, with the oracle model.

3. The desired coverage [W3]

Thank you for the great suggestion. We have included pseudo-code algorithms in Appendix H of the revised manuscript.

For the validation set, we would like to clarify that various score functions caused by different values of $\lambda$ always satisfy the desired coverage. In other words, the value of $\lambda$ does not affect the coverage guarantee, which is theoretically proved by Proposition 1. This is also supported by the empirical results in Sec 4.2.

4. Minor issues [W4,W5,Q3,Q4]

We thanks for pointing out the typos. We have fixed them in the updated version.

• $\mathcal{C}\left(\boldsymbol{x}\_{i},y_i,u_i\right)$ is a typo. In Section 4.1, we revised $\mathcal{C}\left(\boldsymbol{x}\_{i},y_i,u_i\right)$ to $\mathcal{C}\left(\boldsymbol{x}\_{i}\right)$ representing the prediction set for $\boldsymbol{x}\_{i}$.
• In the proof of Lemma 1, we assume that $p_{(k)}>\frac{1}{k}$ for any $k\geq 2$. Thus, for any $\tilde{k}< k$, it holds that $p_{(\tilde{k})}>\frac{1}{k}$.
• In Proposition 1, the subscript of symbol $\mathcal{C}\_{1-\alpha}(\boldsymbol{x}\_{n+1},u\_{n+1})$ hase been completed.
• In proof of Proposition 2, the inequality is the $\frac{1}{\lambda} \leq \frac{1}{1-\frac{1}{K}}$.

5. Definition of prediction set in Proposition 1 [Q2]

Thank you for pointing out the ambiguous notation. The prediction set in Proposition 1 is defined as $\mathcal{C}_{1-\alpha}(\boldsymbol{x},u) =\lbrace y\in\mathcal{Y} : S(\boldsymbol{x},y,u;\hat{\pi})\leq \tau \rbrace.$ Thus, it is mathematically equivalent to Eq. 3. To mitigate this confusion, we added a detailed description in Proposition 1.

6. The nest property [Q1]

The nesting property defined by Eq.2 is a common property holding on all prediction sets for any conformal predictor [R2]. Specifically, if a lower error rate is expected, the set will have a larger size for higher coverage. In this work, since the calibrated threshold $\tau$ is the $1-\alpha$ quantile of scores, the nesting property of $\alpha$ is equivalent to a nesting property for $\tau$, i.e., $\alpha_1>\alpha_2 \rightarrow \tau_1\leq\tau_2 \rightarrow \lbrace y\in\mathcal{Y}: S(\boldsymbol{x},y,u;\hat{\pi})\leq \tau_1 \rbrace \subseteq \lbrace y\in\mathcal{Y}: S(\boldsymbol{x},y,u;\hat{\pi})\leq \tau_2\rbrace,$ for a test point $\boldsymbol{x}$ and a random variable $u$. Therefore, we get the nesting property of $\mathcal{C}_{1-\alpha}(\boldsymbol{x},u)$.

7. Difference between proposition 1 and Theorem 2 [Q3]

Proposition 1 is a corollary of Theorem 2. Specifically, Theorem 2 gives a coverage guarantee for CP methods whose prediction set has a general formulation $\mathcal{C}(\boldsymbol{x},u,\tau)$. The prediction set of SAPS defined as $\lbrace y\in\mathcal{Y}:S(\boldsymbol{x},y,u;\hat{\pi})\leq \tau \rbrace$ is a specific instance of $\mathcal{C}(\boldsymbol{x},u,\tau)$. Therefore, Proposition 1 offers a coverage guarantee for SAPS. We apologize for this misunderstanding and have revised Appendix B to make this clearer.

[R1] Anastasios Nikolas Angelopoulos, Stephen Bates, Michael I. Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In 9th International Conference on Learning Representations

[R2] Balasubramanian, V., Ho, S.-S., and Vovk, V. (2014). Conformal prediction for reliable machine learning: theory, adaptations and applications.

Dear reviewer poFK,

Sorry to disturb you. We sincerely appreciate your valuable comments. We would like to further provide brief answers here to the issues that might be your primary concerns.

We really appreciate your efforts in identifying the typos and ambiguous descriptions, as well as providing valuable suggestions for method descriptions. In response to your feedback, we have carefully revised the typos and enhanced the clarity of our descriptions. We have provided a specific description of the technique details of our proposed method in Appendix H.

We guess that you may have concerns about adaption. With a comparable set size, methods with high adaption can discriminately reflect instance-wise uncertainty. In particular, the results show that our method preserves more distinguishable information than RAPS, while achieving a smaller average set size and desired coverage rate.

In addition, we would like to clarify that various score functions caused by different values of $\lambda$ always satisfy the desired coverage. This concern can be resolved by Proposition 1 and verified by empirical results.

We sincerely hope that the above answers can address your concerns. We look forward to your response and are willing to answer any questions.

Thank you

5. Theoretical comparison with RAPS [W3]

In this work, we aim to provide an in-depth understanding of SAPS through the comparison of APS and RAPS. While there might be some new insights in the comparison between SAPS and RAPS, it is challenging to analyze these two methods in a unified framework, as RAPS introduces two hyper-parameters. Instead, we empirically show the superiority of SAPS over RAPS in set size, conditional coverage violation, and adaptation. Furthermore, we compare SAPS with RAPS($k_r=1$) in Sec 5 to further demonstrate the negative effect of probability values. We believe the thorough analysis of RAPS is sufficient to support our conclusion.

Thank you for the valuable comments and detailed feedback on our manuscript. Please find our response below.

1. Proposition 1 represents a common property [W1]

Yes, many existing works have shown their methods possess the property [R1, R2] while some works do not provide theoretical proofs [R3, R4]. In this work, we present the proposition to show that the proposed method also satisfies the finite-sample coverage guarantee from a theoretical perspective. Without the proposition, it becomes ambiguous if our method can obtain the theoretical property. In other words, Proposition 1 enhances the completeness of our work.

2. Calibrated condition of Proposition 2

In the literature of conformal prediction, it is a common assumption that the given model is well-calibrated in theoretical analysis [R5, R6, R7]. Based on the assumption, we can then provide the subsequent analysis to show the inherent advantages of SAPS compared to APS. On the contrary, it would be non-trivial to give an in-depth understanding of the proposed method, without the condition. Thus, the theoretical explanation is still valuable to the community. In addition, the empirical results in Section 4 demonstrate the effectiveness of our method with imperfect models.

3. The range of $\lambda$ in Proposition 2

We would like to clarify that the range of 0.001 to 0.5 is for the hyperparameter of RAPS, instead of our method. We tune the $\lambda$ of SAPS in the range of 0.02 to 0.6. Moreover, the threshold of $\lambda$ in Proposition 2 is a sufficient condition to show the advantage of SAPS, but it does not reflect that the optimal value of $\lambda$ must exist in the interval $[1-\frac{1}{K},\infty)$ in the experiments.

Here, we conduct an experiment to validate the effectiveness of SAPS with a $\lambda$ in the interval $[1-\frac{1}{K},\infty)$. In particular, we set $\lambda = 1$. The results on three datasets are shown in the table below. We show that SAPS with $\lambda=1$ still outperforms APS, which validates the proposition.

Finally, we would like to clarify that the set size of SAPS would not maintain the upward trend with the increase of $\lambda$. Instead, the set size will converge to a specific value, and SAPS is equivalent to the APS without probability value when $\lambda \to \infty$. To demonstrate this, we update Figure 4a in the revised version by extending the value of $\lambda$ and the updated figure validates the above statement.

4. Clarification of proposed score function [W2]

The constant $2$ in Eq. (8) is not a user-guided value. The term $(o(y,\hat{\pi}(\boldsymbol{x}))-2+u)$ contains ranking scores from rank $2$ to rank $(o(y,\hat{\pi}(\boldsymbol{x}))-1)$, and a random ranking score at the rank $o(y,\hat{\pi}(\boldsymbol{x}))$. As the ranking score is defined as a constant $\lambda$, the sum of ranking scores from rank $2$ to rank $(o(y,\hat{\pi}(\boldsymbol{x}))-1)$ is $(o(y,\hat{\pi}(\boldsymbol{x}))-2) \cdot \lambda$. Thus, the formulation of the proposed score function is defined as $\hat{\pi}_{max} (\boldsymbol{x}) + (o(y,\hat{\pi}(\boldsymbol{x}))-2) \cdot \lambda$+ $u\cdot \lambda$.

[R1] Anastasios Nikolas Angelopoulos, et al. Uncertainty sets for image classifiers using conformal prediction. In 9th International Conference on Learning Representations, ICLR 2021

[R2] Charles Lu, et al. Federated conformal predictors for distributed uncertainty quantification. International Conference on Machine Learning, ICML 2023

[R3] Subhankar Ghosh, et al. Improving uncertainty quantification of deep classifiers via neighborhood conformal prediction: Novel algorithm and theoretical analysis. AAAI 2023

[R4] Henrik Linusson, et al. Classification with reject option using conformal prediction. PAKDD 2018

[R5] Bat-Sheva Einbinder, et al. Training uncertainty-aware classifiers with conformalized deep learning. Advances in Neural Information Processing Systems, 2022b

[R6] Aleksandr Podkopaev, et al. Distribution-free uncertainty quantification for classification under label shift. In Uncertainty in Artificial Intelligence

[R7] Bat-Sheva Einbinder, et al. Conformal prediction is robust to label noise. arXiv preprint arXiv:2209.14295, 2022a

Dear Reviewer xE2a,

Sorry to disturb you. We appreciate that you have pointed out some concerns. We believe that we have addressed all your concerns and clarified the misunderstanding part. Would you please kindly check that and consider re-evaluating our work? Please let us know if you have any further concerns and we are open to all possible discussions.

Thank you

Thank you for the recognition and valuable comments. Please find our response below.

1. Correction of citation [Q1]

Thank you for the correction. We have fixed the citation in the revised version.

2. Clarification of the calibrated threshold [Q2]

Thank you for pointing out the unclear part. Here, we provide a detailed explanation of $\tau$. The score function is defined as $S(\boldsymbol{x},y,u;\hat{\pi}) = r -u$ where $r$ is the rank of $\hat{\pi}\_y(\boldsymbol{x})$ in the sorted vector of $\hat{\pi}(\boldsymbol{x})$. We use $A_{r}$ to denote the proportion of examples in the calibration set that have scores less than $r$. If $k$ satisfies $A_{k}\geq 1-\alpha >A_{k-1}$, the $1-\alpha$ quantile of scores for the calibration set, i.e., the calibrated threshold $\tau$, falls within the interval $[k-1,k]$. As the scores in the interval $[k-1,k]$ are uniformly distributed, and the proportion of examples with scores in $[k-1,k]$ is $a_k$, $\tau$ is chosen as the $\frac{1-\alpha- A_{k-1}}{a_{k}}$ quantile of $[k-1,k]$. In the revised manuscript, we provide a detailed supplement for the proof in Appendix A. The asterisk (*) is a typo, which is fixed in the revised version.