Conformalized Credal Set Predictors

Thank you for your kind words about the paper and for your valuable feedback. We hope our response addresses your comments and questions.

• W1. The main similarity between our work and [1] lies in the data assumption we make. However, while the authors in [1] focus on obtaining prediction sets (i.e., sets of labels), our work is centered on the development of credal sets (i.e., sets of probability distributions). The distinction is important because credal sets allow for the disentangling of total uncertainty into aleatoric and epistemic components, something that prediction sets in [1] do not achieve.

  In the context of credal sets, our proposed conformalized credal sets are designed to be valid in the sense that they cover the ground-truth first-order distribution with high probability—a property that, to the best of our knowledge, is unique to our approach.

  Moreover, for model training, we do not limit ourselves to first-order probability predictors. We thoroughly discuss both first-order and second-order probability predictors, providing a family of nonconformity scores tailored to each type of predictor to enhance the flexibility of our proposed methods. We also address the challenge of obtaining a valid credal set when only imprecise first-order data is available. Additionally, we empirically demonstrate the effectiveness of our proposed methods for uncertainty quantification with such datasets.

• W2. It is worth noting that our approach to model training and calibration does not introduce any additional complexity compared to existing models. Our credal sets can always be precisely described by equation (10) in the paper for any arbitrary K. This equation also enables efficient membership checking, allowing us to determine whether a distribution belongs to a set. The only limitation arises when seeking an exact closed-form representation of the credal set or a compact form, such as in the 1-dimensional regression problem where we represent the set with an interval. However, this challenge is essentially unavoidable for Conformal Prediction in complex (infinite) output spaces, such as multi-output regression or structured output prediction. We have also clarified the details of our experiment in Appendix F, as mentioned in our response to W2 from reviewer gqZt.

• W3. We would like to highlight that datasets where multiple human experts annotate each data instance x are indeed becoming increasingly common in practical tasks, including widely used benchmarks like ImageNet [2] and CIFAR-10 [3], and in some cases, have even been shown to be necessary [4]. This is especially crucial in the context of natural language processing, where a long history of research emphasizes its importance [5,6] (Please refer to our extended related work in Appendix A for many more references). Aggregating annotator disagreements regarding the label of an instance x into a distribution over labels can be seen as an effective way to represent aleatoric uncertainty. We believe and demonstrate in this paper that this information can also contribute to advancements in uncertainty representation and quantification research.

• W4. Guarantees rely on assumptions, and we believe that our assumption is not stronger than assumptions made for comparable results in the literature. Intuitively, the assumption seems to be not only sufficient but even necessary: If noise is unbounded, the estimations can deviate arbitrarily from the ground-truth distribution, thereby making any guarantee impossible. Moreover, it's important to highlight that in real-world applications, quantifying noise, if present, may not always be feasible. Instead, we are often limited in the observations that are available to us. For instance, in our case, we rely on distributions obtained from aggregating human annotations. It's also worth noting that the guarantee of the proposed method remains always consistent with respect to these observations.

• Q1. If the reviewer is referring to model calibration with zero-order data, to the best of our knowledge, none of the existing calibration methods are instance-wise, i.e., they do not aim to calibrate the predicted probability for each specific input x but rather provide calibration in expectation. It is certainly interesting to explore various calibration methods to see if they can achieve this.

• Q2. We are not entirely certain that we fully understand the method the reviewer is referring to. We believe we could provide a more comprehensive answer with additional context. However, as a general remark, if we aim to remove the bounded noise assumption, we would either need to introduce an alternative assumption (which may come naturally with a certain approach) or reconsider our theorem or guarantee entirely.

[1] D. Stutz et al., "Conformal prediction under ambiguous ground truth."

[2] L. Beyer et al., "Are we done with imagenet?"

[3] J. C. Peterson et al., "Human uncertainty makes classification more robust"

[4] L. Schmarje, et al. "Is one annotation enough? a data-centric image classification benchmark for noisy and ambiguous label estimation"

[5] Y. Nie et al., "What can we learn from collective human opinions on natural language inference data?"

[6] D. Stutz et al., "Evaluating AI systems under uncertain ground truth: a case study in dermatology"

We would like to thank the reviewer for engaging with our work. We tried to clarify two of the mentioned weaknesses/concerns, elaborate on one another, and address their questions.

• W1. In our implementations, we ensure that each parameter of the Dirichlet distribution is at least one. We define the Dirichlet parameter as 1+NN(x), where NN(x) represents the non-negative output of the neural network. The intuition behind this is that, in the worst-case scenario where the output of the neural network is zero, we encounter a complete lack of knowledge, and this can be represented by setting the Dirichlet parameter vector to 1, which defines a uniform second-order distribution over all first-order distributions. We'll ensure to clarify this point in the paper.
• W2. We stated the bounded noise assumption at the nonconformity score level to have a universal applicability for all nonconformity functions. For instance, when the Total Variation (TV) distance is used as the nonconformity function, the left-hand side of equation (11) in the paper can be rewritten as:

$

 \mathbb{P}\left(|f(x, {\lambda}^{x})-f({x}, \tilde{\lambda}^{x} ) | < \epsilon \right) &= 
 \mathbb{P}\left(|d_{TV}(\hat{\lambda}^{x}, {\lambda}^{{x}})-d_{TV}(\hat{{\lambda}}^{{x}}, \tilde{{\lambda}}^{{x}} ) | < \epsilon \right) \geq \mathbb{P}\left(d_{TV}(\tilde{{\lambda}}^{{x}}, {\lambda}^{{x}}) < \epsilon \right)
 

$

 where the inequality holds according to reverse triangle inequality and $\hat{{\lambda}}^{{x}}$ denotes the prediction of the model. We can then use the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality  to bound the total variation distance between the true categorical distribution and its empirical estimate from $m$ independent samples:

$

\mathbb{P}\left( d_{TV}(\tilde{{\lambda}}^{{x}}, {{\lambda}}^{{x}}) \leq \epsilon \right) \geq 1 - 2K \exp\left(-2m\epsilon^2\right).

$

Hence, when using TV as the nonconformity score for first-order approaches, the bounded noise in the nonconformity score reflects the noise arising from estimating the ground truth first-order distributions with only samples from that distribution. It is not clear how to provide such a bound for arbitrary nonconformity functions, which is why we presented the theoretical results under the assumption of bounded noise on the nonconformity level.

• W3. Please refer to our global response, in which we explained why we see such dependency and how we handled it.
• Q1. As discussed in the response to W2, the DKW inequality can be used to bound the total variation distance between the true categorical distribution and its empirical estimate based on m independent samples, however, in the special case where m=1, this bound can be quite loose and, therefore, less useful. Interestingly, in Appendix E.2, we conduct experiments with synthetic data where we use the estimation of the ground-truth first-order distribution with varying values of m, including m=1. As illustrated in Figures 13 and 15, coverage is generally achieved in almost all cases. However, for lower values of m, this coverage comes with reduced efficiency, resulting in larger sets.
• Q2. Please refer to the response provided for W1.
• Q3. Please refer to our global response.
• Q4. For the uncertainty interval figures, our goal was to present the information similarly to our credal sets, as shown in Figure 2, where we visualize the location of the ground truth distribution, the predicted distribution (either first-order or second-order, depending on the model), and the credal set. Analogously, we display the uncertainty interval together with the entropy of the ground truth distribution and the entropy of the predicted first-order distribution or the entropy of the mean of the Dirichlet distribution for the second-order predictor. However, the entropy function is non-injective, meaning that two different distributions can have the same entropy. Therefore, the fact that the entropy of the ground truth is within the uncertainty interval does not necessarily imply that the credal set covers the distribution itself.
• Q5. It is certainly desirable to achieve the coverage guarantee with the smallest possible set sizes. However, with a credal set, uncertainty depends on both the size and the location of the set. Broadly speaking, set size influences epistemic uncertainty, while location affects aleatoric uncertainty. The least uncertain scenario would be a singleton located at a corner of the simplex.
• Q6. Investigating conditional coverage is definitely an interesting and important direction for future work in our paper. We anticipate this to be an even more challenging problem, as conditional coverage in standard conformal prediction (CP) pertains to the coverage given x or y (the label). In our case, however, it involves coverage given x or the first-order distribution.
• Limitations. We hope our response to W2 has helped clarify the limitation.

Thank you for your kind words and feedback. We found your questions very interesting and did our best to elaborate on them.

• Q1. Thank you for the reference; it is definitely an interesting and relevant work. To the best of our understanding, the main difference between the two papers is that [1] assumes additive noise on the level of labels while we are dealing with noise on the level of first-order distributions. It is not immediately clear to us how to incorporate the results from [1] into our context.
• Q2. and Q3. Regarding an algorithm that generates prediction sets from credal sets, as noted in our response to W3 for reviewer gqZt, this topic has been explored in the field of imprecise probability. For instance, one approach involves excluding a label from the prediction set if its probability is dominated by other classes across all distributions within the credal set or the approach mentioned by reviewer gqZt [2]. However, extracting a conformal prediction set (with guarantees) from a conformal credal set is indeed an interesting follow-up research question stemming from our paper, and it is not an easy one to address immediately. More importantly, we believe that such an approach could greatly enrich the prediction sets by providing valuable insights into the uncertainty components (AU and EU).
• Q4. The reason that some predictions do not cover the ground truth within the credal set is due to the specified error rate of Conformal Prediction (CP). While using conformal risk control will change the guarantee from coverage to risk, it's not immediately clear how and in what sense this can improve the results. However, it can definitely be considered an interesting future work.
• Q5. This phenomenon occurs with credal sets constructed by the first-order predictor because, once the quantile is determined during the calibration step, all distributions within a certain distance are included in the set for any given point during test time. This is similar to the issue found in standard Conformal Prediction (CP) for regression when using absolute error as the nonconformity score, which is often criticized for its lack of adaptivity. In the CP for regression literature, one way to address this issue is through normalized nonconformity measures, where the score for each point is divided by a measure of its dispersion at that point [3]. In Appendix D of the paper, we introduced a normalized nonconformity score that divides the distance function by the entropy of the predicted distribution. Figure 10 demonstrates the successful improvement in the adaptivity of our proposed approach.

[1] Guille-Escuret, Charles, and Eugene Ndiaye. "From Conformal Predictions to Confidence Regions."

[2] M. Caprio et al., "Credal Bayesian Deep Learning."

[3] H. Papadopoulos et al., "Normalized nonconformity measures for regression conformal prediction".

We would like to thank the reviewer for their insightful comments and suggestions. We have made every effort to address and clarify their concerns in the following response.

• W1. The comparison with other methods was not feasible primarily due to differences in data assumptions. While the methods mentioned in the review rely on zero-order data, our approach requires first-order data. Additionally, methods such as Bayesian Neural Networks (BNNs) or ensembles represent uncertainty using second-order probability distributions, whereas our approach utilizes credal sets. This fundamental difference in representation makes a direct comparison impossible. It's also worth noting that our approach is indeed a variant of conformal prediction specifically adapted to handle first-order data. The key advantage of our proposed conformalized credal sets is that they are designed to be valid in the sense that they cover the ground truth first-order distribution with high probability—a property that, to the best of our knowledge, is unique to our approach. Interestingly, when first-order calibration data is available, our approach can be applied to BNNs or ensembles to construct valid credal sets based on their predicted second-order probability distributions.
• W2. We believe it's important to clarify the details in Appendix F. For CIFAR10-H, we discretized the simplex into 100,000 distributions. For each test data point in CIFAR10-H, creating credal sets—determining whether each of those 100,000 distributions belongs to the credal set across all four methods (TV, KL, WS, and Inner)—takes only 11 seconds. The majority of this time ($\sim$10.4 seconds) is attributed to the WS method, where we were unable to implement parallelization and had to iterate through all simplex distributions using a for loop. As a result, constructing all credal sets for the entire test set of 1,000 instances can take up to 3 hours. For this dataset, the calibration step and uncertainty quantification were completed in less than a second. We will ensure to clarify this in the paper to avoid any confusion.
• W3. We fully agree with the reviewer that deriving a set of labels from a credal set is indeed a very interesting question, even though it is not the intention of our paper. This topic has been explored in various studies within the field of imprecise probability, such as the very interesting approach mentioned by the reviewer, or even simpler ones, such as the one where a label is excluded from the prediction set if its probability is dominated by other classes across all distributions within the credal set. In addition to these approaches, one could also apply the calibration step of the Monte Carlo Conformal Prediction method proposed by [1] in parallel, allowing for the construction of a prediction set alongside the credal sets.
• W4. Please refer to our global response, specifically the Evaluation of uncertainty quantification paragraph.
• Q1. This is indeed the desired property we're aiming for, and the same question applies to standard Conformal Prediction (CP). While CP naturally prevents prediction sets from becoming arbitrarily large by providing an upper bound on coverage probability under reasonable assumptions, the set size also depends on the chosen nonconformity score. In our work, we've explored and compared several scores, as shown in Figure 3 for the ChaosNLI dataset.
• Q2. For second-order predictors, we need to assume a parametric distribution and estimate its parameters from the data. The Dirichlet distribution is a common choice, as it has been used in other second-order predictors like evidential deep networks [2]. Regarding the second question, if the reviewer is referring to cases where the imprecise first-order distributions are biased estimates of the ground truth and we lack the bounded assumption of Theorem 3.2, our approach would be limited to the observations provided by these imprecise first-order distributions. Consequently, our uncertainty representation would be valid relative to these biased data, which ultimately reflect a bias toward the ground truth.
• Q3. For the reasons why direct comparisons are not feasible, please refer to the response provided for W1. Note that learning models, such as first-order or second-order predictors, can be trained using zero-order data but not the credal predictor. The proposed credal predictor requires at least first-order data for calibration. For example, in our experiments with CIFAR-10H, we conformalize a probabilistic classifier trained on CIFAR-10 (zero-order) training data with CIFAR-10H (first-order) calibration data.
• Q4. Our proposed method enables classifiers to represent uncertainty in a reliable manner through the use of a credal set. With this credal set, we can quantify both aleatoric and epistemic uncertainty, which can then inform decisions on the appropriate course of action. For instance, when epistemic uncertainty is high, it may be addressed by gathering more data. Conversely, if total uncertainty is primarily driven by high aleatoric uncertainty, additional data collection (e.g., consulting more experts) may not be beneficial and could be considered a waste of resources. We also demonstrated this with an illustrative experiment using synthetic data in Appendix E.1.

[1] D. Stutz et al., "Conformal prediction under ambiguous ground truth."

[2] M. Sensoy et al., "Evidential deep learning to quantify classification uncertainty."