Provable Uncertainty Decomposition via Higher-Order Calibration

We thank the reviewer for their time and appreciate that they agree on the importance of the problem. We provide responses to their individual questions below:

Re. background and explanation

We think good uncertainty estimation could directly guide practitioners as they seek to improve their classifiers.

Suppose we’ve trained a classifier on some dataset. Now suppose that the model is uncertain on a particular datapoint: it assigns high probability to more than one class—its predictive uncertainty is high. What do we do?

Without good uncertainty estimation, this is not obvious. The problem might just be that our data is ambiguous and that the model has accordingly learned to output ambiguous predictions. Alternatively, it might just be that we haven’t trained our model long enough, or that our model is too small. In the former case, the solution is simply to acquire better data; tinkering with our model or its training procedure will not help us at all here. In the latter, we can completely resolve the issue by just modifying our training procedure, without touching the data: we might just want to train longer, or use a larger/better tuned model.

A good uncertainty decomposition reveals precisely which of these two scenarios we’re in (or, if we have some mixture of both problems, it tells us what fraction of our predictive uncertainty is because of our data and what fraction is because of our model). Accordingly, it can tell practitioners precisely what they need to do to improve their classifiers.

In response to a request from reviewer y8E9, we have added a detailed walkthrough of our running X-ray example to the appendix (edits in orange), which we hope illustrates the value of high-quality uncertainty decomposition. We have also added a conclusion to the main paper, which likewise summarizes the main points. We hope these help communicate the importance of the problem, but we’d be happy to make further changes if necessary. Let us know what you think!

Re. Lee et al.

Thanks for bringing this to our attention! You’re right—like [1], this paper reinforces how two-label data can be used to make much stronger, conditional statements about the distribution of labels for a particular input. There are important differences between their work and ours—e.g. they treat specifically with hierarchical data, only indirectly touch on calibration, and rule out the practicality of even higher-order data (they speculate that this would produce unstable intervals, contrary to our work)—but it’s certainly relevant. We’ve added a citation in the most recent version of our manuscript.

Please let us know if we’ve addressed all of the reviewer’s concerns and whether they’d be willing to raise the score.

[1] Johnson, Daniel D., et al. "Experts Don't Cheat: Learning What You Don't Know By Predicting Pairs." arXiv preprint arXiv:2402.08733 (2024).

We’re glad the reviewer found our approach valuable and that they enjoyed the manuscript. We address their individual comments below:

Re. estimation of quantities of interest

We’ve reworded parts of the experimental section to make it clearer how entropy values were computed (highlighted in orange).

Re. the running example

Certainly. We’ve updated Section A of the appendix to include a fully elaborated walkthrough of the running example (also highlighted in orange).

We thank the reviewer for their time and hope we have addressed all of their concerns.

Thank you for your thorough review! We appreciate the feedback, and have included below answers to your questions as well as how we plan to make changes to address your comments.

Re. structure/text weaknesses

You make a great point that it would be useful to include a reference to Figure 1 in the text. We have added a reference in the intro near the location you recommended (all edits in orange). Regarding the "Summary of Main Results" section --- note that the section is intended to end with the paragraph after Theorem 1.2. However, we have broken up the section into “Main result” and “Techniques” to improve clarity. We have added a conclusion section to summarize the key theoretical results, discuss limitations, and suggest potential future work. We’ve ensured all appendices are properly referenced in the main text.

Re. missing related work

Thanks for bringing these to our attention. We’ve added citations to both works to the most recent version of the manuscript.

Re. experiment baselines

[3]’s “Cheat NN” coincides with the first strategy, as it trains a predictor to predict 2-snapshot outcomes (where the matrix corresponds to pairs of classes). Our suggested first strategy generalizes this approach to k > 2. See our response to Q2 for more details and experiment updates!

Re. Q1 (posterior predictive distribution)

The posterior predictive distribution can be seen as a mixture as follows: suppose $f$ is a Bayesian model and $f(x; \theta) \in \Delta Y$ is the output at $x$ with some fixed parameters $\theta$. When $\mathbf{\theta}$ is itself drawn from the posterior over parameters, $f(x; \mathbf{\theta})$ becomes a random distribution. The posterior predictive distribution at $x$ is thus a mixture whose mixture components are given by $f(x; \mathbf{\theta})$. Importantly, we do not average the mixture components --- we refer to that in our terminology as the mixture centroid or in this context the Bayesian Model Average (BMA).

Re. Q2 (higher-order calibration strategy)

The first strategy is that employed by [3] for the case k = 2, but it is both less practical than the second strategy (it requires modifying the weights of the predictor and greatly increasing the dimension of the output layer) and also not as strongly supported by our theory. Nevertheless, we’re currently running experiments using the first strategy on a new dataset with enough multi-label datapoints to train a model (CIFAR-10H is just a test/calibration set) and will include them with the final version of the manuscript.

Re. Q3 (epistemic uncertainty and variance)

We use ``variance’’ in quotes to refer to an intuitive notion of variation between values, rather than the actual variance of the Bayes mixture. We show in Theorem 1.2 and more generally in Lemma C.1 that this intuitive variance can be formalized as the divergence between the mixture components and the mixture centroid. We’ve edited the sentence to improve clarity.

Re. Q4 (HOC and OOD Detection)

While it is indeed common to use EU for OOD detection, our theoretical guarantees only provide formal guarantees with respect to in-distribution data. For this reason, we do not make the claim that HOC would improve hard-OOD detection, but this remains a direction for future study.

Re. Q5 (concave generalized entropy function)

Our results with respect to the consequences of higher-order calibration hold very generally for any (strict or non-strict) concave entropy function, and thus for any of the entropy functions associated with proper scoring rules that are discussed in the sources you reference. Our results on estimating uncertainty with kth-order calibration (Theorem 3.3) are more or less efficient depending on the smoothness (in terms of either their approximation by low-degree polynomials, or uniform continuity) of these entropy functions, i.e. less smooth concave entropy functions will require larger values of k to approximate well.

Please let us know if you have any other feedback or questions.

[3] Johnson, Daniel D., et al. "Experts Don't Cheat: Learning What You Don't Know By Predicting Pairs." arXiv preprint arXiv:2402.08733 (2024).

Dear Authors,

I deeply appreciate your engagement and the efforts you've made to address my concerns. From my perspective, the paper now appears more solid and comprehensive.

Given the changes and the new results you've added, I am now more confident that the paper should be accepted. Therefore, I have increased my evaluation score and the confidence level of my assessment.

We apologize for the oversight; you’re right that Kotelevskii et al. should be mentioned alongside Hofman et al. We’ve edited the manuscript to reflect this.

We've also added experiments with the first strategy, finding that it slightly underperforms the post-hoc calibration strategy, at least at the model scale we explore in the paper. See Appendix G3 for details.

Thanks again for your detailed reading of our manuscript! We feel it is much improved from its original version. Please let us know if there are any remaining issues with the paper and whether you’d be willing to raise your score.

We thank the reviewer for their positive and informed review and detailed reading. We address their specific questions and comments below:

Re. questions about notation

“In Definition 1.1, you write… w.r.t. x ~ [x]”

We use a convention of referring to random variables using boldface. x ∼ [x] refers to a draw from the marginal distribution D_X restricted to the equivalence class [x]. This notation was indeed not very clearly explained in the main text, only in Appendix A. In the most recent version of the manuscript, we clarify the notation earlier in the manuscript. (All changes in orange)

“Why in line 270… k in parentheses?”

Y^(k) specifically denotes the space of uniform distributions over snapshots. Specifically, an element of Y^(k) is not a tuple (y_1, …, y_k) but rather the distribution Unif{y_1, …, y_k} (equivalently, it is the space of symmetrized tuples where only relative frequency matters). This is an important point --- we currently define it right before Definition 2.3 in the manuscript and emphasize it more carefully in the revised version. This is exactly the way in which Y^(k) is directly a subset of \Delta Y and hence \Delta Y^(k) a subset of \Delta \Delta Y. We hope this also addresses the question about the conceptual simplification in Line 273.

“The 1-Wasserstein… should be mentioned”

Indeed; we do state that Y must be discrete when we introduce it. We have added a note emphasizing this fact to the paragraph where we introduce Wasserstein distance.

“Careful in using… (see e.g. eq (27) in [4]).”

In the context of the current paper, we feel that “G” does not risk much confusion. Please also note that the authors of [4] use “GH” to refer to the generalized Hartley measure, not “G”.

Re. the Fisher-Laplace paradox

This is indeed a common motivating problem in the literature—for example, [5], as well as various papers on Bayesian deep learning and credal sets make similar arguments. To be clear, we do not claim to have discovered this issue with single-distribution predictors. We simply propose 1) a new way to evaluate any solution to the problem and 2) rigorous and practical solutions of our own.

Re. pitfalls of higher-order distributions

We did make an effort to cite as many relevant papers as possible (including several works by Hüllermeier and Sale and another by Caprio), but we thank the reviewer for drawing attention to a few that we missed and the need for further discussion. We also note that there is additional discussion of related work in Appendix B, including on mixture-based uncertainty decompositions.

Regarding the pitfalls of higher-order distributions, Bengs et al. ([6], cited in [1, Section 5]) arguably captures the key concern: given only level-0 samples (i.e. ordinary labeled examples), it does not make sense to learn a level-2 predictor (i.e. a mixture predictor). This same concern also underlies the critique in [7] and [8] of one popular way of obtaining higher-order distributions, namely evidential deep learning.

We agree with this concern completely (it is also related to the Fisher-Laplace paradox just discussed). It is exactly why we instead learn a Level-2 predictor from k-snapshots, ie multilabeled examples (which are a kind of Level-1 sample) (see the last paragraph of Bengs et al, Section 2.3 for a similar point). Without k-snapshots, we fully agree that existing approaches to using higher-order distributions fall short in various ways. Moreover, our work identifies exactly how these approaches fall short, and proposes (a) learning from k-snapshots as a principled way of learning mixtures, and (b) higher-order calibration as a principled way of ensuring that these mixtures have clear frequentist semantics. In fact, higher-order calibration also yields an evaluation metric for all such methods producing higher-order distributions.

Other methods of representing higher-order uncertainty such as credal sets tackle these concerns in different ways. We view mixtures as especially expressive and natural, since they occur already in common methods such as Bayesian and ensemble methods. Note also that there is a considerable literature on mixture-based uncertainty decompositions (by Hüllermeier and Sale and others) that also takes mixtures as a starting point; see Appendix B for discussion. Ultimately, however, all such representations are formalisms for a subtle real-world concept, with various pros and cons. Our core reason for using mixtures is that we can prove a strong formal result such as Thm 1.2, which we do not see how to do for other representations. We have included some of this discussion in the extended related work (Appendix B, in orange) in the updated manuscript.

Re. type-2 validity

Thank you for bringing this to our attention. Type-2 validity [2] is a certain guarantee on the predicted probability distribution for a new unseen point drawn marginally from the underlying distribution. Importantly, it is not merely a coverage guarantee about the value of the new point, but rather a guarantee about its distribution. Higher-order calibration provides a guarantee that is similar in spirit but different in its particulars. A particular consequence is higher-order prediction sets with coverage guarantees for entire ground truth probability distributions --- please see Appendix F for details. Moreover, these guarantees hold conditionally over an equivalence class rather than merely marginally over the entire distribution.

For further discussion of the differences between conformal prediction and prediction intervals derived from second-order calibration (a special case of our notion of higher-order calibration), please see a nice section of the appendix of [5] titled “Comparison to other distribution-free statistical guarantees”.

Re. credal sets

Credal sets are not second-order probability distributions, and in particular allow expressing total ignorance via the empty credal set. However, for many purposes a nonempty credal set behaves similarly to the uniform mixture over that set, and in this sense mixtures are still a useful and general language with significant pros of their own. Ultimately we believe these are incomparable approaches. A key benefit of mixtures for us is that we can prove formal guarantees such as Thm 1.2 for mixtures. We are not aware of similar guarantees for credal sets --- note that we were not able to find a definition of credal set calibration in [3].

Re. conclusion

We have added a conclusion to the most recent draft of the manuscript.

Please let us know if we missed anything or if there are concerns that still remain. We would be happy to engage further.

[5] Johnson, Daniel D., et al. "Experts Don't Cheat: Learning What You Don't Know By Predicting Pairs." arXiv preprint arXiv:2402.08733 (2024).

[6] Bengs, Viktor, Eyke Hüllermeier, and Willem Waegeman. "Pitfalls of epistemic uncertainty quantification through loss minimisation." Advances in Neural Information Processing Systems 35 (2022): 29205-29216.

[7] Jürgens, Mira, et al. "Is Epistemic Uncertainty Faithfully Represented by Evidential Deep Learning Methods?." arXiv preprint arXiv:2402.09056 (2024).

[8] Pandey, Deep Shankar, and Qi Yu. "Learn to accumulate evidence from all training samples: theory and practice." International Conference on Machine Learning. PMLR, 2023.