Top-label calibration and multiclass-to-binary reductions
Authors: Chirag Gupta
Aaditya Ramdas
Venue: ICLR 2022 Poster (2022)
Keywords: calibration
multiclass
uncertainty quantification
distribution-free
histogram binning

Abstract: We propose a new notion of multiclass calibration called top-label calibration. A classifier is said to be top-label calibrated if the reported probability for the predicted class label---the top-label---is calibrated, conditioned on the top-label. This conditioning is essential for practical utility of the calibration property, since the top-label is always reported and we must condition on what is reported. However, the popular notion of confidence calibration erroneously skips this conditioning. Furthermore, we outline a multiclass-to-binary (M2B) reduction framework that unifies confidence, top-label, and class-wise calibration, among others. As its name suggests, M2B works by reducing multiclass calibration to different binary calibration problems; various types of multiclass calibration can then be achieved using simple binary calibration routines. We instantiate the M2B framework with the well-studied histogram binning (HB) binary calibrator, and prove that the overall procedure is multiclass calibrated without making any assumptions on the underlying data distribution. In an empirical evaluation with four deep net architectures on CIFAR-10 and CIFAR-100, we find that the M2B + HB procedure achieves lower top-label and class-wise calibration error than other approaches such as temperature scaling. Code for this work is available at https://github.com/aigen/df-posthoc-calibration.

We propose a new notion of multiclass calibration called top-label calibration. classifier is said to be top-label calibrated if the reported probability for the pre- dicted class lahel-the top-lahel-is calibrated, conditioned on the top-label. This conditioning is essential for practical utility of the calibration property, since the top-label always reported and we must condition on what is reported. How- ever, the popular notion of confidence calibration erroneously skips this condi- tioning. Furthermore, we outline a multiclass-to-iinal (M2B) reduction frame- work that unifies confidence, top-label, and class-wise calibration, among others. As its name suggests, M2B works by reducing multiclass calibration to differ- ent binary calibration problems; various types of multiclass calibration can then be achieved using simple binary calibration routines. We instantiate the M2B framework with the well-studied histogram binning (HB) binary calibrator, and prove that the overall procedure is multiclass calibrated without making any as- sumptions on the underlying data distribution. In an empirical evaluation with four deep net architectures on CIFAR-10 10 and CIFAR-100, we find that the M2B Published as a conference paper at ICLR 2022
TOP-LABEL CALIBRATION AND SATTICLASS-TO-IINNE REDUCTIONS
Chirag Gupta & Aaditya Ramdas
Carnegie Mellon University
{chiragg, aramdas ) cmu edu
ABSTRACT
+ HB procedure achieves lower top-label and class-wise calibration error than other approaches such as temperature scaling. Code for this work is available at https://githun: com/ afgen/df www.ppootoooooooo mallibatiion
INTRODUCTION
Machine learning models often make probabilistic predictions. The ideal prediction is the true con- ditional distribution of the output given the input. However, nature never reveals true probability distributions, making it infeasible to achieve this ideal most situations. Instead, there is signifi- cant interest towards designing models that are calibrated, which is often feasible. We motivate the definition of calibration using a standard example of predicting the probability of rain. Suppose a meteorologist claims that the probability of rain
a particular day is 0.7. Regardless of whether it rains on that day or not, we cannot know if 0.7 was the underlying probability of rain. However, we test if the meteorologist is calibrated in the long run, by checking if on the D) days when 0.7 was predicted, it indeed rained on around 0.7D days (and the same is true for other probabilities).
This example is readily converted a formal binary calibration setting. Denote random (Feature, label)-pair as (X, Y) E X' x 1J, where X' is the feature space. A probabilistic predictor h : - [0, is said be calibrated if for every prediction q E [0. 1J. Pr(Y = h(X) q) = q (almost surely). Arguably. if an ML classification model produces such calibrated scores for the classes, downstream users of the model can reliably use its predictions for broader set of tasks.
Our focus in this paper is calibration for multiclass classification, with L > 3 classes and Y [z] = (1,2...., I. > 3). We assume all (training and test) data is drawn i.i.d. from a fixed distribution P, and denote a general point from this distribution as (X.Y) ~ P. Consider a typical multiclass predictor, h X - A-1, whose range 4-1 is the probability simplex R. A natural notion of calibration for h. called canonical calibration is the following: for every / E [4]. P(Y = h(X)= = q) = qi (qi denotes the I-th component of q). However, canonical calibration becomes infeasible
achieve or verify once L is even or 5 (Vaicenavicius et al. 2019). Thus, there is interest in studying statistically feasible relaxations of canonical notion, such as confidence
calibration (Guo al. 2017) and class-wise calibration (Kull al. 2017)

---

Published as a conference paper at ICLR 2022
In particular, the notion of confidence calibration (Guo et al. 2017) has been popular recently. A model is confidence calibrated if the following is true: "when the reported confidence for the predicted class is q e [o, 1]. the accuracy is also q". In any practical setting, the confidence q is never reported alone; it is always reported along with the actual class prediction 1 E [Z]. One may expect that if model is confidence calibrated, the following also holds: "when the class I is predicted with confidence the probability of the actual class being / is also q"? Unfortunately, this expectation is rarely met-there exist confidence calibrated classifier for whom the latter statement is grossly violated for all classes (Example Tt. On the other hand, our proposed notion of top-label calibration enforces the latter statement. conditioning on all relevant reported quantities (both the predicted top label and our confidence in it). In Section 2 we argue further that top-label calibration simple and practically meaningful replacement of confidence calibration.
philosophically more coherent, because it requires
In Section we unify top-label, confidence, and number of other popular notions of multiclass calibration into the framework of multiclass-to-binaryy (M2B) reductions. The M2B framework re- lies on the simple observation that each of these notions internally verifies binary calibration claims. As consequence, each M2B notion of calibration can be achieved by solving number of binary calibration problems. With the M2B framework at our disposal, all of the rich literature on binary calibration can now be used for multiclass calibration. We illustrate this by instantiating the M2B framework with the binary calibration algorithm of histogram binning or HB (Zadrozny and Eikan 2001 Gupta and Ramdas 2021). The M2B + HB procedure achieves state-of-the-ar results with respect to standard notions of calibration error (Section 4.. Further, we show that our procedure is provably calibrated for arbitrary data-generating distributions. The formal theorems are delayed to Appendices B. C (due to space limitations), but an informal result is presented in Section 4
2 MODIFYING CONFIDENCE CALIBRATION TO TOP-LABEL CALIBRATION
Let c : X' [1] denote classifier or top-label predictor and h : X' [0, 1J a function that provides a confidence or probability score for the top-label c(X). The predictor (c, h) is said to be
confidence calibrated (for the data- settagenerating distribution P) if
P(Y = c(X) ((X))= = A(X).
(I)
In other words, when the reported confidence l(()) equals p [o, 1]. then the fraction of instances
where the predicted label is correct also approximately equals p. Note that for an L-dimensional
predictor h X' A f-11 one would use c(-) arg max h4(-) and h(-)) = h-)) ties are
broken arbitrarily. Then h is confidence calibrated if the corresponding (c, h) satisfies 1
Confidence calibration is most applicable in high-accuracy settings where we trust the label pre- diction c(z). For instance, if high-accuracy suncer-grade-preddee prediction model predicts a patient as having "95% grade III. 3% grade II, and 2% grade I", we would suggest the patient to undergo an invasive treatment. However, we may want to know (and control) the number of non-grade-Ill patients that were given this suggestion incorrectly. In other words, is Pr(cancer is not grade III cancer is predicted to be of grade III with confidence 95%) equal to 5%? It would appear that by focusing on the the probability of the predicted label, confidence calibration enforces such control.
However, as we illustrate next, confidence calibration fails at this goal by providing a guarantee that is neither practically interpretable, nor actionable. Translating the probabilistic statement (I) into words, we ascertain that confidence calibration leads to guarantees of the form: "if the confidence h(X) in the top-label is 0.6, then the accuracy (frequency with which Y equals c(X)) is 0.6". Such a guarantee is not very useful. Suppose a patient P is informed (based on their symptoms X), that they are most likely have certain discase D with probability 0.6. Further patient this score is confidence calibrated. P can now infer the following: "among all patients who have probability 0.6 of having some unspecified disease, the fraction who have that unspecified disease is also 0.6." However, P is concerned only about disease D, and not about other diseases. That is, wants to know the probability of having D among patients who were predicted to have disease D with confidence 0.6, not among patients who were predicted to have some disease with confidence 0.6. In other words, P cares about the occurrence of among patients who were told the same thing that P has been told. It is tempting to wish that the confidence calibrated probability 0.6 has any bearing on what P cares about. However, this faith is misguided, as the above reasoning suggests, and further illustrated through the following example.
told that
2

---

Published as a conference paper at ICLR 2022
(1, (X can be as the random patient, and Y as the disease they are suffering from.) Consider predictor (c, h) and let the values taken by (X, Y, c, h) be as follows:
Example 1. Suppose the instance space is (X (a, b)
Feature
P(X x)
Class prediction c(x)
Confidence h(x))
P(Y c(X) X x)
0.5
0.6
0.2
0.5
2
0.6
1.0
The table specifies only the probabilities P(Y dX) X z); the probabilities
P(Y = X r). c(z), can be set arbitrarily. We verify that (c. h) is confidence calibrated:
P(Y = c(X) h(() = 0.6) P.Y = = = a) + P(Y
X x b)) 0.5 + 1) 0.6.
However, whether the actual instance is X = a or X = b. the probabilistie claim of 0.6 bears no correspondence with reality. If X a, h(X)= = 0.6 is extremely overconfident since
P(Y - a) 0.2. Contrarily, if X b, (X) 0.6 is extremely underconfident.
M
The reason for the strange behavior above is that the probability P(Y c(X) I(X)) is not interpretable from decision-making perspective. In practice, we never report just the confidence h(X), but also the class prediction e(X) (obviously!). Thus it is more reasonable to talk about the conditional probability of Y = c(X), given what is reported, that is both c( c(X) X) and h(X). We make
a small but critical change to [ we say that (c, h) is top-label calibrated
P(Y c(X) h(X), = (()).
(See the disambiguating Remark on terminology.) Going back to the patient-disease example, top-label calibration would tell patient P the following: "among all patients, who (just like you) predicted to have disease D with probability 0.6, the fraction who actually have disease D is also 0.6." Philosophically, it makes sense to condition on what is reported- both the top label and its confidence-becaneee that is what is known the recipient of the information; and there is no apparent justification for not conditioning on both.
A commonly used metric for quantifying the miscalibration of model is the expected-caliivratinn error (ECE) metric. The ECE associated with confidence calibration is defined as
conf-ECB(cc, h) :- Ex P c(X) M(X)) ((X))
We define top-label-ECE (TL-ECEE) in analogous fashion, but also condition on c(X): TL-ECB(c, h) := Ex PP c(X) c(X), ((X)) -(())-(--
(4)
Higher values of ECE indicate worse calibration performance. The predictor in Example I has conf-ECE((, h) 0. However, it has TL-ECE(c, h) 0.4, revealing its miscalibration. More gen- erally, it can be deduced as a straightforward consequence of Jensen's 's inequality that conf-ECE( h) always smaller than the TL-ECE((,, h)) (see Proposition Appendix [H. As illustrated by Exam- [T the difference can be significant. In the following subsection we illustrate that the difference can be significant on real dataset as well. First, we make a couple of remarks.
Remark (ECE estimation using binning). Estimating the ECE requires estimating probabilities conditional on some prediction such as h (z). A common strategy to do this bin together nearby values of h(x) using binning schemes (Nixon et al., 2020 Section 2.1), and compute a single esti- mate for the predicted and true probabilities using all the points in bin. The calibration method we espouse in this work, histogram binning (HB), produces discrete predictions whose ECE can be estimated without further binning. Based on this, we use the following experimental protocol: we report unbinned ECE estimates while assessing HB, and binned ECE estimates for all other compared methods, which are continuous output methods (deep-nets, temperature scaling, etc). is commonly understood that binning leads to underestimation of the effective ECE (Vaicenavicius ct al. 2019 Kumar et al., 2019). Thus, using unbinned ECE estimates for HB gives HB disadvan- tage compared to the binned ECE estimates we use for other methods. (This further strengthens our positive results for HB.) y The binning scheme we use is equal-width binning, where the interval [o, 1] divided into B equal-width intervals. Equal-width binning typically leads lower ECE estimates compared to adaptive-width binning (Nixon et al., 2020).
Remark (Terminology). The term conf-ECE was introduced by Kull et al. (2019). Most works
refer to conf-ECE as just ECE (Guo et al. 2017 Nixon et al. 2020; Mukhoti et al. 2020 Kumar et al. 2018). However, some papers refer to conf- ECE as lap-label-ECE (Kumar al.
2019 Zhang et al. 2020), resulting in two different terms for the same concept. We call the older notion as conf-ECE, and our definition of top-label calibration/ECE (4) is different from previous ones.
3

---

Published as a conference paper at ICLR 2022
U355
True probarility accurac)
033
Casa
X T=Y
933
054
635
D5Y
0.4
ResNitt5 confidence
100
Closs
1312
Restiet50 top-label
0.32
Fraction of predictions
Dhas
2.. Predicted prabability or confidence
04 0.6
0.28
Ebans
Actrage
(a) Confidence reliability diagram (points marked *) and top-label reliability diagram
0.34
0560
0550
Pradicte probuteky
(points marked +) for ResNet-50 model on the CIFAR-10 dataset; see further details in points (a) and (b) below. The gray bars denote the fraction of predictions in each bin. The confidence reliability diagram (mistakenly) suggests better calibration than the top-label reliability diagram.
(b) Class-wise and zoomed-in version of Figure Ta for bin
6 (top) and bin 10 (hottom); further details in point (c) below. The * markers are in the same position as Figure Ia and denote the average predicted and true probabilities. The colored points denote the predicted and true probabilities when seen class-wise. The histograms the right show the
number of test points per class within bins 6 and 10.
Figure 1: Confidence reliability diagrams misrepresent the effective miscalibration.
2.1
AN ILLUSTRATIVE EXPERIMENT WITH RESNET-50 50 ON CIFAR-10
We now compare confidence and top-label calibration using ECE estimates and reliability diagrams (Niculescu-Mizl and Caruana 2005). This experiment can be as a less malignant version of
Example 1 Here, confidence calibration is not completely meaningless, but can nevertheless be
misleading. Figure illustrates Jiguutenillustrattes the (test-time) calibration performance of a ResNet-50 model (He) ct al. 2016) on the CIFAR-I0 dataset (Krizhevsky) (2009). In the following summarizing points, the (c, h) correspond to the ResNet-50 model.
(a) The * markers in Figure Ta form the confidence reliability diagram (Guo et al. 2017). con- structed follows. First, the h(xz) values on the test set are binned into one of B 10 bins, [0, 0.1), [0.1, 0.2), ..................... [0.9, 1]. depending on the interval to which (xx) belongs. The gray bars in Figure la indicate the fraction of h(x) values in each bin- nearly 92% points belong to bin [0.9, and no points belong to bin [0, 0.1). Next, for every bin b, we plot * = (conff, acc;), which are the plugin estimates of E. [X(X) M(X) E Bin b) and P(Y c(X) h(X) Bin b) respectively. The dashed X Y line indicates perfect confidence calibration.
(b) The + markers in Figure La form the top-label reliability diagram. Unlike the confidence reliability diagram, the top-label reliability diagram shows the average miscalibration across classes in a given bin. For a given class 7 and bin b, define
Do.1 IP(Y c(X) c(X) 1,K(X) Bin b) Σ[Λ(X) | c(X) 1,h(X) Bin b] I,
where P, P. denote empirical estimates based on the test data. The overall miscalibration is then
As :
average
EVELLy P(c(X)
h(X) e Bin b) As,1-
Note that As is always non-negative and does not indicate whether the overall miscalibration occurs due under- or over-confidence; also, if the absolute-values were dropped from As. then A, would simply equal acc,, conf,- In order to plot A, in a reliability diagram, we obtain the direction for the corresponding point from the confidence reliability diagram. Thus for every * (conf,, ac we plot + (conf,, conf, + As)) if acc, > conf, and + - (conf,- conf, A,) otherwise, for every b. This scatter plot of the +'s gives us the labelabel reliability diagram. Figure T shows that there is a visible increase in miscalibration when going from confidence calibration to top-label calibration. To understand why this change occurs, Figure Tb zooms into the sixth bin (h(X)= [0.5, 0.6)) and bin 10 (h(X) E [0.9, 1.0]). as described next.
(c) Figure displass the class-wise top-label reliability diagrams for bins 6 and 10. Note that for bin 6, the * marker is nearly on the X Y line, indicating that the overall accuracy matches the
4

---

Published as a conference paper at ICLR 2022
model tap-label-ECE Base model conf-ECE
Temperature scaling top-label-ECE Temperature scaling conf-ECE
Histogram binning top-label-ECE Histogram binning conf-ECE
Recket 110
Wide RecWet 26
Penseler 12)
0.030
0.022
60256
50025
0.520
0.122
0.015
00150
60122
0.823
Mambardd
Number of 101
Number of t99
Numbero tins
Figure 2: Conf-ECE (dashed lines) and TL-ECE (solid lines) of four deep-net architectures on CIFAR-10, as well as with recalibration using histogram binning and temperature scaling. The TL- ECE is often 2-3 times the conf-ECE, depending the number of bins used to estimate ECE, and the architecture. Top-label histogram binning typically performs better than temperature scaling.
overall confidence of 0.545. However, the true accuracy when class I was predicted is 0.2 and the true accuracy when class 8 was predicted is = 0.9 (a very similar scenario to Example For bin 10, the * marker indicates miscalibration of 0.01; however, when class 4 was predicted (roughly 8% of all test-points) the miscalibration is s 0.05.
Figure 2 displays the aggregate effect of the above phenomenon (across bins and classes) through estimates of the conf-ECK and TL-ECE. The precise experimental setup described in Section 4 These plots display the ECE estimates of the base model, well as the base model when recalibrated
using temperature scaling (Guo et al.) (017) and our upcoming formulation of top-label histogram binning (Section 3). Since ECE estimates depend on the number of bins B used (see Roelofs et al. (2020) for empirical work around this), we plot the ECE estimate for every value [5, 25| in order obtain clear and unambiguous results. We find that the TL-ECE is significantly higher than the conf-ECE for most values of B, the architectures, and the pre- and post- recalibration models. This figure also previews the performance of our forthcoming top-label histogram binning algorithm. Top-label HB has smaller estimated TL-ECE than temperature scaling for most values of B and the architectures. Except for ResNet-50, the conf-ECE estimates also better.
To summarize, top-label calibration captures the intuition of confidence calibration by focusing on the predicted class. However, top-label calibration also conditions on the predicted class, which is always part of the prediction in any practical setting. Further, TL-ECE estimates can be substantially different from conf-ECE estimates. Thus, while is common to compare predictors based on the conf-ECE, the TL-ECE comparison is more meaningful, and can potentially be different.
CALIBRATION ALGORITHMS FROM CALIBRATION METRICS
In this section, we unify number of notions of multiclass calibration as multiclass-to-binan (or M2B) notions, and propose a general-purpose calibration algorithm that achieves the corresponding M2B notion of calibration. The M2B framework yields multiple novel post-hoc calibration algo- rithms, each which is tuned to a specific M2B notion of calibration.
3.1 MUL.TICLASS-
(M2B) NOTIONS OF CALIBRATION
In Section 2 we defined confidence calibration I and top-label calibration These notions verify calibration claims for the highest predicted probability. Other popular notions of calibration verify calibration claims for other entries in the full L-dimensional prediction vector. A predictor h2) is said be class-wiss calibrated (Kull al. 2017)
(h1, hg....,hhy
(class-wise calibration) VI E [4], P(Y = (x) = (X).
(5) 2021). For some
Another recently proposed notion top-K confidence calibration (Gupta et al. I E [4], let (1) [L] denote the 1-th highest class prediction, and let 1
X
[L] denote
the confidence associated with it (c c()) and h = (1) are special cases). For a given K & L,
(top-K-confidence calibration)
Vk [K]. P(Y (x) (x)) (x)
(6)
5

---

Published as a conference paper at ICLR 2022
Calibration notion
Quantifier
Prediction (xr)d(X))
Binary calibration statement
Confidence
h(X)
P(Y c(X) pred X)) h(x)
Top-label
(X),h(x)
P(Y c(x) pred X)) h(x)
Class-wise
W [L]
(x(X)
P(Y (red(X)) =4((X)
Top-K -confidnnee
4k E [K]
(X)
P(Y (X) pred(X)) h (X)
Top-K-label
Wk [K]
(X),
P(Y (X) pred (X)) = (x)
Table I: Multiclass-to-iiaan (M2B) notions internally verify more binary calibration state-
ments/claims. The statements in the rightmost column are required to hold almost surely.
As we did in Section 2 for confidence--tope tto--labll, top- -confideneee calibration be modified to the more interpretable -l-bbel calibration by further conditioning on the predicted labels:
(top-K Ktop-Kllabe K-label calibration)
Ak E [K]. P(Y ((h) (x) h (1) (X), c( (X)) = (x))))) (X).
(7)
Each of these notions reduce multiclass calibration to one or more binary calibration requirements, where each binary calibration requirement corresponds to verifying if the distribution of Y, condi- tioned on some prediction pred(X), satisfies a single binary calibration claim associated with pred (X). Table illustrates how the calibration notions discussed so far internally verify a number of binary calibration claims, making them M2B notions. For example, for class-wise calibration, for every / E [L]. the conditioning is on (.)d(X) (X) = (x(),, and single binary calibration statement is verified: P(Y = pr) = hy (X). Based on this property, we call each of these notions multcclass-t--binaryyy or M2B notions.
The notion of canonical calibration mentioned in the introduction is not an M2B notion. Canonical calibration discussed in detail in Appendix G Due to the conditioning on a multi-dimennional prediction, non-M2B notions of calibration are harder to achieve or verify. For the same reason, it is possibly easier for humans to interpret binary calibration claims when taking decisions/actions.
3.2 ACHIEVING M2B NOTIONS OF CALIBRATION USING M2B CALIBRATORS
The M2B framework illustrates how multiclass calibration can typically be viewed via reduction to binary calibration. The immediate consequence of this reduction is that one can now solve multiclass calibration problems by leveraging the well-developed methodology for binary calibration.
The upcoming M2B calibrators belong to the standard recalibration or post-hoc calibration setting. In this setting. one starts with fixed pre-learnt base model g X' - A The base model can correspond to a deep-net, a random forest, or any 1-v-all (one-versus-all) binary classification model such logistic regression. The base model is typically optimized for classification accuracy and may not be calibrated. The goal of post-hoc calibration is to use some given calibration data D (X1, Yi), (X2, Y2),.. ..... (X,,, Y,) E (X' [L])", typically data on which g was not learnt, to recalibrate g. In practice, the calibration data is usually the same as the validation data.
To motivate M2B calibrators, suppose we want to verify if g is calibrated on certain test set, based on a given M2B notion of calibration. Then, the verifying process will split the test data into a number of sub-datasets, each of which will verify one of the binary calibration claims. In Appendix A.2 we argue that the calibration data can also be viewed as a test set, and every step in the verification process can be used to provide signal for improving calibration.
M2B calibrators take the form of wrapper methods that work on top of given binary calibrator. Denote an arbitrary black-box binary calibrator as Açu.1; [0, 1 x (X'x (0, 1)) - [0. 1 where the first argument a mapping X' [0. 1] that denotes (miscalibrated) binary predicor, and the second argument is calibration data sequence of arbitrary length. The output is a (better calibrated) binary predictor: Examples of 1.. are histogram binning (Zadrozny and Elkan 2001), isotonic regression (Zadrozny and Elkan 2002). and Platt scaling (Platt 1999).. In the upcoming descriptions, we use the indicator function {a = b) E {0, which takes the value if a b, and 0 if a *
The general formulation of our M2B calibrator is delayed to Appendix A since the description is bit involved. To ease readability and adhere to the space restrictions, in the main paper we describe the calibrators corresponding to top-label, class-wise and confidence calibration (Algorithms [ Each of these calibrators are different from the classical M2B calibrator (Algorithm that has been used by Zadrozny and Elkan (2002). Guo al. 2017 Kull al. (2019), and most other papers

---

Published as a conference paper at ICLR 2022
M2B calibrators: Post-hoc multiclass calibration using binary calibrators
Input in each case: Binary calibrator A(o.1) : [0,1]* x (X x {0, 1))" - [0, 10,1]*, base multiclass predictor g X' - A 4-1, calibration data D = (X1, YI). (Xns Yn).
Algorithm 1: Confidence calibrator
Algorithm Class-wise calibrator
classifier top-class based on g; < top-class-pree op-claas-probability based on g:
Write g (g). 92. ................................ :b);
2 for + 1 to L do
D' [(,, 1 (Y, c(X;))) : [n]]:
D: [(X, (., 4): :de [n]]:
h < Ag..)((.DD) D');
hy - ((o,)) Di);
return (c, h);
s end
return (h1, h2,........ hL);
Algorithm Normalized calibrator
Algorithm 2: Top-label calibrator
Write g (01. 901-9:--0 -...--..... -L);;
c classifier or top-class based on g:
2 for - 1 to do
g pa-class-probabilie based g:
D: {(X,, (Y; 13: : [n]]:
for / < to L do
Di ((,,, 1 (Y; 11) c({,, = 1);;
hy - (1, Di);
Di)):
h4 - (g, Di):
s end
&end
Normalize: for every le [4].
h(.) (+))()) (predict hx( if c(x) I);
hi(+) := h/(-)/ Σk he(:); 7 return (h1, he.............................. hL);
return (c,h):
we are aware of, with the most similar one being Algorithm 3 Top- Sop-KKlabee label and top-K -ooffideee calibrators are also explicitly described in Appendix A (Algorithms and 7
Top-label calibration requires that for every class 1 [Z], P(Y
c(X) - (x) h(X).
Thus, to achieve top-label calibration, we must solve L calibration problems. A constructs datasets (D: labels are 1 (Y; zj. Now for every / E [L]. we calibrate g to hy binary calibrator. The final probabilistic predictor is h(-) = (.) (that is, it predicts hy(x)) e(x) I). The top-label predictor e does not change in this process. Thus the accuracy of (c, h) the same as the accuracy of g irrespective of which Alo,1) used. Unlike the top-label calibrator, the confidence calibrator merges all classes together into a single dataset D' Ute[r]] Di.
[L]] (line 4. The features in D, are the X;'s for which c(X,) 4, and the
X [0, 1J using Dj and any
To achieve class-wise calibration, Algorithm also solves L calibration problems, but these corre- spond to satisfying P(Y =1 1 hx))) (x).. Unlike top-label calibration, the dataset D; for class-wise calibration contains all the X,' K'ss (even if c(X,) * 1), and h is passed to Aqu,1) instead of h. Also, unlike confidence calibration, Y; is replaced with (Y 2} instead of 1 (Y, = c(X,)). The overall process similar to reducing multiclass classification to L 1-v-all binary classification problem, but our motivation is intricately tied to the notion of class-wise calibration.
Most popular empirical works that have discussed binary calibrators for multiclass calibration have done so using the normalized calibrator, Algorithm 4 This is almost identical to Algorithm except that there is an additional normalization step (line of Algorithm 4). This normalization was first proposed by Zadrozny and Elkan (2002) Section 5.2), and has been used unaltered by most other work where the goal has been to simply compare direct multiclass calibrators such as temperature scaling, Dirichlet scaling, etc., to a calibrator based on binary methods (for instance, see Section 4.2 of Guo et al. (2017). In contrast to these papers, we investigate multiple M2B reductions in an effort identify the right reduction of multiclass calibration to binary calibration.
To summarize, the M2B characterization immediately yields a novel and different calibrator for every M2B notion. In the following section, we instantiate M2B calibrators on the binary calibrator of histogram binning (HB), leading to two new algorithms: top-label-HB and wises-wise-HB, that achieve strong empirical results and satisfy distribution- free calibration guarantees.
'the only exception we are aware of is the recent work of Patel et al. (2021) who also suggest skipping normalization (see their Appendix A1); however they use common I-Max binning scheme across classes, whereas in Algorithm the the predictor h; for each class is learnt completely independently of other classes

---

Published as a conference paper at ICLR 2022
Metric
Dataset
Architecture
Base
TS
VS
DS
N-HB
TL-HB
ResNet-50
0.025
0.022
0.020
0,010
0.010
0.020
ResNet- 110
0.029
0.022
0.021
0.021
0.020
0.021
CIFAR-IO
WRN-26-10
0.023
0.023
0.019
0.021
0.012
0.018
Top- label-
DenseNet- 121
0.027
0.027
0.020
0.020
0.019
0.021
ResNet-50
0.118
0.114
0.113
0.322
0.081
0. 1.143
ECE
ResNet-110
0.127
0.121
0.115
0.353
0.093
O. 145
CIFAR-100
WRN-26-10
0.103
0.103
0.100
0.304
0.070
0.
DenseNet-121
0.110
0.110
0.109
0.322
0.086
O. 139
ResNet-50
0.315
0.305
0.773
0.282
0.411
0.107
ResNet-110
0.275
0.227
0.264
0.392
0.195
0.077
CIFAR-10
WRN-26-10
0.771
0.771
0.498
0.325
0.140
0.071
Top- label- MCE
DenseNet- I21
0.289
0.289
0.734
0.294
0.345
0.087
ResNet-50
0.436
0.300
0.251
0.619
0.397
0.291
ResNet-110
0.313
0.255
0.277
0.557
0.266
0.257
CIFAR-100
WRN-26-10
0.273
0.255
0.256
0.625
0.287
0,280
DenseNet-121
0.279
0.231
0.235
0.600
0.320
0.289
Table 2: Top-label-ECE and top-label-MCE for deep-net models (above: 'Base') and various post- hoc calibrators: temperature-scain scaling (TS), vector-scaling (VS), Dirichlet-scaling (DS), top-label-HB (TI.-HB), and normalized-HB (N-HB). Best performing method in each row is in bold.
Metric
Dataset
Architecture
Base
TS
VS
DS
N-HB
CW-HB
ResNet-50
0.46
0.42
0.35
0.35
0.50
0.28
ResNet-
0.59
0.50
0.42
0.38
0.53
0.27
CIFAR-10
Class-
WRN-26-10
0.44
0.44
0.35
0.39
0.39
0.28
wise- ECE
DenseNet-121
0.46
0.46
0.36
0.36
0.48
0.36
ResNet-50
0.22
0.20
0.20
0.66
0.23
0.16
10
ResNet-T10
0.24
0.23
0.21
0.72
0.24
0.16
CIFAR-100
WRN-26-10
0.19
0.19
0.18
0.61
0.20
0.14
DenseNet-121
0.20
0.21
0.19
0.66
0.24
0.16
Table 3: Class-wise-ECE for deep-net models and various post-hoc calibrators. All methods are same as Table except TL-HB is replaced with class-wise-HB (CW-HB).
4 EXPERIMENTS: M2B CALIBRATION WITH HISTOGRAM BINNING
Histogram binning or HB was proposed by Zadrozny and Elkan (2001) with strong empirical results for binary calibration. In HB, base binary calibration model g X [0, 1] is used to partition the calibration data into a number of bins so that each bin has roughly the same number of points. Then, for each bin, the probability of Y 1 is estimated using the empirical distribution on the calibration data. This estimate forms the new calibrated prediction for that bin. Recently, Gupta and Ramdas (202T) showed that HB satisfies strong distribution- free calibration guarantees, which are otherwise impossible for scaling methods (Gupta et al. 2020
Despite these results for binary calibration, studies for multiclass calibration have reported that HB typically performs worse than scaling methods such temperature scaling (TS), vector scaling (VS), and Dirichlet scaling (DS) (Kull et al., 2019 Roelofs al. 2020 Guo al.) 2017). In our experiments, find that the issue is not HB but the M2B wrapper used to produce the HB baseline. With the right M2B wrapper, HB beats TS, VS, and DS. A number of calibrators have been proposed
recently (Zhang et al. 2020 Rahimi al. 2020 Patel et al. 2021 Gupta et al. 2021). but VS and DS continue to remain strong baselines which are often close to the best in these papers. We do not compare to each of these calibrators; our focus is the M2B reduction and the message that the baselines dramatically improve with the right M2B wrapper.
We three metrics for comparison: the first is top-label-ECE TL-ECE (defined in 4)) which we argued leads to a more meaningful comparison compared to conf-ECE. Second, we consider the more stringent
(MCE) metric that assesses the worst calibration
across predictions (see more details in Appendix E.3 For top-label calibration MCE is given by
TL-MCE(c, fi) max SuppeRango(k) PP(Y =I I c(X) = 1, h(X) r) rl. To assess class- wise calibration, class-wise-ECCF defined the average calibration error across classes:
8

---

Published as a conference paper at ICLR 2022
CW-ECE( h) := E Ex IP(Y = (x)) (x)) All ECE/MCE estimation is per- formed as described in Remark [
For further details, see Appendix E.2
Formal algorithm and theoretical guarantees. Top-label-HB (TL-HB) and HB) are explicitly stated in Appendices B BanddC rrsppectivvy: these are instantiations of the top-label calibrator and class-wise calibrator with HB. N-HB is the the normalized calibrator (Algorithm 4 with HB, which is the same as CW-HB, but with an added normalization step. In the Appendix, we extend the binary calibration guarantees of Gupta and Ramdas (202T) TL-HB and CW-HB (Theorems D and 2). We informally summarize one of the results here: if there are at least & cali- bration points-per-bing then the expected-ECE is bounded as: E [(TI.-) or (CW-) ECE] & 11/2k, for TL-HB and CW-HB respectively. The outer E' above is an expectation over the calibration data, and corresponds to the randomness in the predictor learnt on the calibration data. Note that the ECE itself is an expected error over an unseen i.idd. test-point (X,Y) P.
(CW-
Experimental details. We experimented on the 10 and CIFAR-100 100 datasets, which have 10 and 100 classes each. The base models are deep-nets with the following architectures: ResNet- 50, Resnet- 10, Wide-ResNee-26-11
(WRN) (Zagoruyko and Komodakis (016). and DenseNet- 121 (Huang et al., 2017). Both CIFAR datasets consist of 60K (60,000) points, which are split as 45K/5K/10K to form the train/validattonn/tes sets. The validation set was used for post-hoc calibra- tion and the test set was used for evaluation through ECE/MCE estimates. Instead of training new models, we used the pre-trained models of Mukhoti et al. 2020). We then ask: "which post-hoc calibrator improves the calibration the most?" We used their Brier score and focal loss models in experiments (Mukhoti et al.] (2020) report that these are the empirically best performing loss functions). All results in the main paper are with Brier score, and results with focal loss are in Appendix E.4 Implementation details for TS, VS, and DS are in Appendix E
Findings. In Table 2 we report the binned ECE and MCE estimates when B = 15 bins are used by HB, and for ECE estimation. We make the following observations:
(a) For TL-ECE, N-HB is the best performing method for both CIFAR-10 and CIFAR-100. While most methods perform similarly across architectures for CIFAR-10, there is high variation in CIFAR-100. DS is the worst performing method on CIFAR-100, but TL-HB also performs poorly. We believe that this could be because the data splitting scheme of the TL-calibrator (line 4 of Algorithm 2 splits datasets across the predicted classes, and some classes in CIFAR-100 occur very rarely. This is further discussed in Appendix [E6]]
(b) For TL-MCE, TL-HB is the best performing method on 100 by huge margin. For CIFAR-100, TS or VS perform slightly better than TL-HB. Since HB ensures that each bin gets roughly the same number of points, the predictions are well calibrated across bins, leading to smaller TL-MCE, A similar observation was also made by GGupt and Ramdas (2021).
(c) For CW-ECE, CW-HB is the best performing method across the two datasets and all four ar- chitectures. The N-HB method which has been used in many CW-ECE baseline experiments performs terribly. In other words, skipping the normalization step leads large improvement in CW-ECE. This observation is one of our most striking findings. To shed further light on this, we note that the distribution-free calibration guarantees for CW-HB shown Appendix C no longer hold post-normalization. Thus, both our theory and experiments indicate that skipping normalization improves CW-ECE performance.
Additional experiments in the Appendix. In Appendix E.5 we report each of the results in Ta- bles 2 and 3 with the number of bins taking every value the range [5, 25]. Most observations remain the same under this expanded study. In Appendix B.2 we consider top-label calibration for the class imbalanced COVTYPE-7 dataset, and show that TI. HB adapts to tail/infrequent classes.
5 CONCLUSION
We make two contributions to the study of multiclass calibration: (i) defining the new notion of top-label calibration which enforces a natural minimal requirement on a multiclass tre probability score for the top class prediction should be calibrated; (ii) developing a multiclass-to- binary (M2B) framework which posits that various notions of multiclass calibration can be achieved via reduction to binary calibration, balancing practical utility with statistically tractability. Since is important to identify appropriate notions of calibration in any structured output space (Kuleshov) et al. 2018 Gneiting et al., (007), we anticipate that the philosophy behind the M2B framework could find applications in other structured spaces.

---

Published as a conference paper at ICLR 2022
6 REPRODUCIBILITY STATEMENT
Some reproducibility desiderata, such as external code and libraries that were used are summarized in Appendix E.1 All code to generate results with the CIFAR datasets attached in the supple- mentary material. Our base models were pre-trained deep-net models generated by Mukhoti et al. 2220), obtained from www.robol robots. ox ac wwt..uu//vvveiiieeeeee htt///vvveaa/aaeee http://laaaaaaaaaaaaaaaaaaaaaaaa wal.ccabibriiioooo (corre- sponding to "brier score' and 'focal loss adaptive 53' at the above link). By avoiding training of new deep-net models with multiple hyperparameters, we also consequently avoided selection biases that inevitably creep in due to test-data-peeking. The predictions of the pre-trained models were obtained using the code at https: /github......gggg www/torrvisiiaiiocooooooci.oiiee focal calibratiion ion.
ETHICS STATEMENT
Post-hoe calibration post-processing step that can be applied on top of miscalibrated machine learning models to increase their reliability. As such, we believe our work should improve the transparency and explainability of machine learning models. However, we outline a few limita- tions. Post-hoc calibration requires keeping aside fresh, representative dataset, that was not used for training. If this dataset too small, the resulting calibration guarantee can be too weak to be meaningful in practice. Further, if the test data distribution shifts in significant ways, additional corrections may be needed to recalibrate (Gupta et al.] 2020; Podkopaev and Ramdas (021). A well calibrated classifier not necessarily accurate 2017). Deploying calibrated models critical applications like medicine, criminal law, banking, etc. does not preclude the possibility of the model being frequently wrong or unfair.
fair one, and vice versa (Kleinberg al.)
ACKNOWLEDGEMENT
This work used the Extreme Science and Engineering Discovery Environment (XSEDE), which is supported by National Science Foundation grant number ACI-1548562 (Towns et al. 2014). Specif- ically, it used the Bridges-2 system, which is supported by NSF award number ACI- 1978147, the Pittsburgh Supercomputing Center (PSC). CG's research was supported by the generous Bloomberg Data Science Ph.D. Fellowship. CG would like to thank Saurabh Garg and Youngseog Chung for interesting discussions, and Viveka Kulharia for help with the focal calibration repository. Finally, we thank Zack Lipton, the ICLR reviewers, and the ICLR area chair, for excellent feedback that helped improve the writing of the paper.
REFERENCES
Jock Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and dis- criminant analysis in predicting forest cover types from cartographic variables. Computers and electronics in agriculture, 24(3):131-11,, 1999.
Leo Breiman, Jerome Friedman, Richard A Olshen, and Charles Stone. Classification and regression trees. Routledge, 2017.
Luc Devroye. The equivalence of weak, strong and complete convergence in L₁ for kernel density estimates. The Annals of Statistics, 11(3):896 9044,99999999999999 1983.
Lue Devroye. Automatic pattern recognition: A study of the probability of error. IEEE Transactions on pattern analysis and machine intelligence, 10(4):530-543, 1988.
Tilmann Gneiting, Fadoua Balabdaoui, and Adrian Raftery. Probabilistic forecasts, calibration and sharpness. Journal of the Royal Statistical Suciety: Series B (Statistical Methodology), 69(2): 243-268, 2007.
Louis Gordon and Richard A Olshen. Almost surely consistent nonparametric regression from recursive partitioning schemes. Journal of Multivariate Analysis, 15(2):147-163, 1984.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In International Conference Machine Learning, 2017.
10

---

Published as a conference paper at ICLR 2022
Chirag Gupta and Aaditya Ramdas. Distribution-fiee calibration guarantees for histogram binning without sample splitting. In International Conference on Machine Learning, 2021.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas, Distribution-free binary classification: prediction sets, confidence intervals and calibration. In Advances in Neural Information Process- ing Systems, 2020.
Kartik Gupta, Amir Rahimi, Thalaiyasingam Ajanthan, Thomas Mensink, Cristian Sminchisescu, and Richard Hartley. Calibration of neural networks using splines. International Conference on Learning Representations, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinherger. Densely connected convolutional networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2017.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determi- nation of risk scores. In Innovations in Theoretical Computer Science, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical Report, Univer- sity of Toronto, 2009.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. International Conference on Muchine Learning, 2018.
Meelis Kull, Telmo M. Silva Filho, and Peter Flach. Beyond sigmoids: How to obtain well- calibrated probabilities from binary classifiers with beta calibration. Electronic Journal of Statis- tics, 1 11(2):0522-5000, 2017.
Meelis Kull, Miquel Perello-Nieto, Markus Kängsepp. Hao Song, and Peter Flach. Beyond tem- perature scaling: Obtaining well-calibrated multiclass probabilities with Dirichlet calibration. In Advances in Neural Information Processing Systems, 2019.
Ananya Kumar, Percy $ Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems, 2019.
Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain. Trainable calibration measures for neural networks from kernel mean embeddings. In International Conference on Machine Learning. 2018.
Gábor Lugosi and Andrew Nobel. Consistency of data-driven histogram methods for density esti- mation and classification. Annals of Statistics, 24(2):687-706, 1996.
Jishnu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip HS Torr, and Puneet K Dokania. Calibrating deep neural networks using focal loss. In Advances in Neural Information Processing Systems, 2020.
Alexandru Niculescu-Minn and Rich Caruana. Predicting good probabilities with supervised learn- ing. In International Conference on Machine Learning, 2005.
Jeremy Nixon, Michael W Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measur- ing calibration in deep learning. arXiv preprint arXiv:1904.01685, 2020.
Andrew Nobel. Histogram regression estimation using data-dependent partitions. The Annals of Statistics, 2483)10844 1996.
Kanil Patel, William Beluch, Bin Yang, Michael Pfeiffer, and Dan Zhang. Multi-class uncertainty calibration via mutual information maximization-base binning. In International Conference on Learning Representations, 2021.
John C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In Advances in Large Margin Classifiers, pages 61-74. MIT Press, 1999.
11

---

Published as a conference paper at ICLR 2022
Aleksandr Podkopaev and Aaditya Ramdas. Distribution-fre free uncertainty quantification for classi- fication under label shift. In Uncertainty in Artificial Intelligence, 2021.
Jian Qian, Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric, Concentration inequalities for multinoulli random variables. arXiv preprint arXiv:2001.11595 2020.
Amir Rahimi, Amirreza Shaban, Ching-An Cheng, Richard Hartley, and Byron Boots. Intra order- preserving functions for calibration of multi-class neural networks. In Advances in Neural Infor- mation Processing Systems, 2020.
Rebecca Roclofs, Nicholas Cain, Jonathon Shlens, and Michael C Mozer. Mitigating bias in cali- bration error estimation. arXiv preprint arXiv:20/2.08663. 2020.
Towns, T. Cockerill, M. Dahan, I. Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop, D. Lifka, G. D. Peterson, R. Roskies, J. Scott, and N. Wilkins-Dichr, XSEDE: Accelerating Scientific Discovery. Computing in Science & Engineering, 16(5):62-74, 2014.
Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and Thomas B Schön. Evaluating model calibration in classification. In International Conference on Artificial Intelligence and Statisties, 2019.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. In- equalities for the L1 deviation of the empirical distribution. Hewlett Paackrrd Labs, Tech. Rep, 2003.
David Widmann, Fredrik Lindsten, and Dave Zachariah. Calibration tests in multi-class classifica- tion: unifying framework. In Advances Neural Information Processing Systems, 2019.
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers. In International Conference Machine Learning, 2001.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass proba- bility estimates. International Conference on Knowledge Discovery and Data Mining, 2002.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference, 2016.
Jize Zhang, Bhavya Kailkhura, and Han. Mix-n-match: Ensemble and compositional methods for uncertainty calibration in deep learning. In International Conference Machine Learning, 2020.
12

---

Published as a conference paper at ICLR 2022
Algorithm 5: Post-hoc calibrator for given M2B calibration notion C
Input: Base (uncalibrated) multiclass predictor g, calibration data
D (X1, Y1), (Xn, Yn), binary calibrator
10o [o, 1] (X' 1)) - [o. 1]
K number of distinct calibration claims that C verifies;
for each claim & [K] do
From g, infer (c, - (label-predictor, probability-predictr)) corresponding to claim k; Dr= - {(x,, Z,) where Z; - (Y, ((X,)); conditioning does not include class prediction è then
(confidence, top-K-co ne----oonideece, and class-wise calibration)
hx - A (o, end else
10
(top-label and
calibration)
for 1 E [1]] do
DA.I {X,, Z,) E Dx a(x)) = 1)};
13
hx. A (g. Pa.)::
14
end
hx(-) - (+) (h+ predicts (z) if f(x) l);
15
16
end
17
end
(the new predictor replaces each with the corresponding hy.) return (label-predictor, h4)) corresponding to each claim k E [K]]
19
Input for Algorithms and 7 base multiclass predictor g : X - A 1--1, calibration data D (X1, Y1), (X,,, Y.). binary calibrator A(o,1) [0. 1]x x (X' (0, 1})* [0,
Algorithm 6: Top-K -labell calibrator For every E [K]. infer from g the k-th largest class predictor ((+) and the associated probability g(#);
Algorithm 7: Tfop-K-confinn calibrator
For every k [K]. infer from g the k-th largest class predictor c(()) and the associated probability ((();;
for 1: - 1 to K do
for 1 - 1 to L do
DE,1 {(X,, 1 (Y: = =)):
2 for k K do
(X,) = l);
D {X,, 1 (Y, = 1}) :ie [m]];
(K.0 - A ( Dk.)):
(k) A(o.1) Dx)::
end
end
(*) ((te)
return
(h (2)) (k)):
end
return
(2)),, (K)3
A ADDENDUM TO SECTION CALIBRATION METRICS"
"CALIBRATION ALGORITHMS FROM
In Section we introduced the concept of M2B calibration, and showed that popular calibration
notions are in fact M2B notions (Table [] We showed how the calibration notions of top-label, class-wise, and confidence calibration can be achieved using a corresponding M2B calibrator. In the following subsection, we present the general-purpose wrapper Algorithm 5 that can be used to derive an M2B calibrator from any given M2B calibration notion that follows the rubric specified by Table I In Appendix A.2, illustrate the philosophy of M2B calibration using simple example with a dataset that contains 6 points. This example also illustrates the calibrator, the class- wise-calibrator, and the confidence--alibratto:
13

---

Published as a conference paper at ICLR 2022
an
0.6
0.0
0.0
((bb
((())
(())
==1
0
9:()
0.9
0.6
0.9
0.0
0.0
0.7
0.1
0.1
0.1
92()
0.1
0.1
<(-)
Y=
-
8:()
0.6
0.0
0.1
0.8
0.0
8x())
#4()
0.3
0.3
0.1
0.8
0.1
0.0
a(>>
0
0
8()
0.6
0.6
0.7
0.8
0.8
0.9
Y c()
ef-)
3
2
4
3
1
6.()
0.3
0.3
0.1
0.8
0.1
0.0
Y
2
0.6
0.8
c(1) =
fixed base model g - A 8 on calibration/test data D = {(a, 3), (b, 4), .),...,
(a) Predictions
Y c()
1
(d) Class-wise calibration
[(0)
g(b)
((A)
e(
, (f, 1)).
a( c()
0.8
6 4
0.1
3.0
02
0.0
0.9
0.0
3.0
0.7
0.0
0.1
0.0
0.6
0.6
0.7
0.8
0.8
0.9
(c) Top-label calibration
Y = c(-
0
1
0
0
0.3
3.0
0.1
1.0
0.0
(b) Confidence calibration
(e) Canonical calibration
Figure 3: Illustrative example for Section A.2 The numbers in plot (a) correspond to the predictions
made by g on dataset D. If D were a test set, plots (b-e) show how should be used to verify if g satisfies the corresponding notion of calibration. Consequently, set, and we want to achieve one of the notions (b-e), then the data shown in the corresponding plots should be the data used calibrate well.
argue that if D were calibration
A.1 GENERAL GENERAL-PURPOSE M2B CALIBRATOR
Denote some M2B notion of calibration as C. Suppose C corresponds K binary calibration claims. The outer for-loop in Algorithm []] runs over each such claim in For example, for class-wiss wiie calibration, K L and for confidence and top-label calibration, K 1. Corresponding to each claim, there a Additionally, there may be conditioning the label predictor such as (2, in Algorithm 5 For confidence and top-label calibration, č c, the top-Label-confidence. For class-wing wise calibration, when ğ = 9t. we have 2(-) =
that the conditioning is to be done on, such as g or gi or 9ik)-
C(R)- These denoted
If there is no label conditioning in the calibration notion, such in confidence, top-K -onffidence, and class-wise calibration, then we enter the if-condition inside the for-loop. Here h2 is learnt using single calibration dataset and single call to Aqo, Otherwise, if there is label conditioning, such as in top-label and top-K KClabel calibration, we enter the else-condition, where we learn a separate ha. for every 1 e [L], using different part of the dataset D; in each case. Then ha (x: equals (x)) if ((x) =
Finally, since C is verifying sequence of claims, the output of Algorithm 5 is sequence of pre- dictors. Each original prediction (7, Ø) corresponding to the C. is replaced with (7, hg). This is the changed. This output appears abstract,
output of the M2B calibrator. Note that the è values but normally, it can be represented in an interpretable way. For example, for class-wise calibration, the output is just sequence of predictors, one for each class: (h1, h2....,
This purpose M2B calibrators can be used to achieve any M2B calibration notion: top- label calibration (Algorithm D class-wise calibration (Algorithm 3). confidence calibration (Algo- rithm [}. top- K-labll calibration (Algorithm 6). and -oo-f-confieence calibration (Algorithm) 7).
A.2 AN EXAMPLE TO ILLUSTRATE THE PHILOSOPHY OF M2B CALIBRATION
Figure 3a shows the predictions of given base model on given dataset D. Suppose D is test set, and we are testing confidence calibration. Then the only predictions that matter are the prepriidittios corresponding to the shaded values. These stripped out and shown in Figure in the g(-) row. Note that the indicator (Y = c(-)) sufficient to test confidence calibration and given this, the e(X) are not needed. Thus the second row in Figure 3b only shows these indicators.
14

---

Published as a conference paper at ICLR 2022
Algorithm 8: Top-label histogram binning
Input: Base multiclass predictor g, calibration data D = Yi)...... (Xn, Yn) Hyperparameterr # points per bin & E N (say 50), tie-breaking parameter 8 > 0 (say 10 10-10) Output: Top-label calibrated predictor (c, h) classifier top-class based g:
top-clas--robbbiiliy based on gi
for 1 to L do
Di - {(,,, 1 (Y, = 13) c(X,) = 1)} and nt < [Prl: h4 Binary- suarry--sttgram-biniee binning(g. D;, |n/kk] .);;
end
h(-) - h-())-);;
return (c, h):
Verifying top-label calibration is similar (Figure 3cp. but in addition to the predictions g(-), we also retain the values of c(-). Thus the g(t) and (Y c(:)3 are shown, but split across the 4 classes. Class-wise wise calibration requires access to all the predictions, however, each class is considered sep- arately as indicated by Figure 3d Canonical calibration looks at the full prediction vector in each case. However, in doing so, it becomes unlikely that g(x) g(y) for any x, y since the number of values that g can take is now exponential.
Let us turn this around and suppose that D were calibration set instead of a test set. We argue that D should be used in the same way, whether testing or calibrating. Thus, if confidence calibration is to be achieved, we should focus the (g. (Y c(-)) corresponding to g. If top-label calibration is to be achieved, we should use the (c.g) values. class-wise calibration is to be achieved, we should look at each gr separately and solve L different problems. Finally, for canonical calibration, must look at the entire vector as a single unit. This is the core philosophy behind M2B calibrators: binary claims are being verified, solve binary calibration problems.
B DISTRIBUTION-FREE TOP-LABEL CALIBRATION USING HISTOGRAM BINNING
In this section, we formally describe histogram binning (HB) with the top-label-callbratto (Algo- rithm 2 and provide methodological insights through theory and experiments.
B. FORMAL ALGORITIM AND THEORETICAL GUARANTEES
Algorithm describes the top-label calibrator formally using HB as the binary calibration algorithm. The function called in line S is Algorithm 2 of Gupta and Ramdas (021). The first argument in the call is the top-label confidence predictor, the second argument is the dataset to be used, the third argument is the number of bins to be used, and the fourth argument is tie-breaking parameter (described shortly). While previous empirical works on HB fixed the number of bins per class, the analysis of Gupta and Ramdas (2021) suggests that more principled way of choosing the number of bins is to fix the number of points per bin. This is parameter k of Algorithm g Given k, the number of bins is decided separately for every class as [m// /kj where ny the number of points predicted as class I. This choice is particularly relevant for top-label calibration since ni can be highly non-uniform (we illustrate this empirically in Section B.2). The tie-breaking parameter 8 can be arbitrarily small (like 10-19), and its significance is mostly theoretical is used to ensure that outputs of different bins are not exactly identical by chance, so that conditioning on a calibrated probability output is equivalent to conditioning
bin; this leads to cleaner theoretical guarantec.
HB recalibrates g to piecewise constant function & that takes one value per bin. Consider a specific bin 6; the l value for this bin is computed as the average of the indicators 11 (Y, c(X.)) X, Bin 6). This is an estimate of the bias of the bin P(Y = c(X) X E Bin b). A concentration inequality then be used to bound the deviation between the estimate and the true bias to prove distribution-free calibration guarantees. In the forthcoming Theorem [ we show high-probabiiltyy and in-expectation bounds on the the TL-ECE of HB. Additionally, we show marginal and condi-
15

---

Published as a conference paper at ICLR 2022
tional top-label calibration bounds, defined next. These notions were proposed in the binary cal- ibration setting by Gupta et al. (2020) and Gupta and Ramdas (022)) In the definition below, A refers to any algorithm that takes imput calibration data D and mitial classifier g to produce top-label predictor e and an associated probability map h. Algorithm g is an example of AA.
Definition (Marginal and conditional top-label calibration), Let a E (0. 1) be some given levels of approximation and failure respectively. An algorithm A (g. D) - {c, h)) is
(a) (e, marrgnnlyyy top-label calibrated if for every distribution P over X' x [4].
P(IP(Y e(X) | cx)), (x)) h(xx < <)) 2 -a a.
(8)
(b) (e, a)-oodittionnll top-label calibrated if for every distribution P over X x [b].
P(VIE [L]r Range(M)) = c(X) 11 =)) -1) 3 a.
(9)
To clarify, all probabilities taken over the test point (X,Y) ~ P. the calibration data D P" and any other inherent algorithmic randomness in A: these are all implicit in (c, A(D, g). Marginal calibration asserts that with high probability, on average over the distribution of D,X, P(Y'c(X)) c(X) c(X), h(X)) is at most away from h(X). In comparison, TL-ECE is the average of these deviations over X. Marginal calibration may be more appropriate metric for calibration than TL-ECE if we are somewhat agnostic to probabilistic errors less than some fixed threshold (like 0.05). Conditional calibration a strictly stronger definition that requires the deviation to be at most e for every possible prediction (1, r), including rare ones, not just on average over predictions. This may be relevant in medical settings where we want the prediction on every patient to be reasonably calibrated. Algorithm 8 satisfies the following calibration guarantees.
P(Y
Theorem 1. Fix hyperparameters 8 > 0 (arbitrarily small) and points per bin k > 2, and assume n, > k for every I E [L]. Then, for any a (0, 1), Algorithm 8 is (E1, a) -mrrgnallyy and (E2, a)) conditionally top-label calibruted for
log (2/a) S1 =
log [og(2n/ka)) + 6.
2(k: - + 8,,
and
82 =
(10)
2(k: - 1)
Further, for any distribution P over X' x [L]. we huve P(TL-ECE(C,h) h) & 82) > 1 and E [TL-ECE(c, hi] & /1/2k 8
The proof in Appendix H is multiclass top-label adaption of the guarantee in the binary setting by Gupta and Ramdas (2021) 1. The Ō(1/VK) dependence of the bound relies Algorithm delegating at least & points to every bin. Since can be chosen to be arbitrarily small, setting = 50 gives
roughly ED [TL-ECE(h)] < 0.1. Base this, suggest setting k E [50, 150] in practice.
B.2 TOP-LABEL HISTOGRAM BINNING ADAPTS TO CLASS IMBALANCED DATASETS
The principled methodology of fixing the number of points per bin reaps practical benefits. Fig- ure nee4illan illustrates this through the performance of HB for the class imbalanced COVTYPE-7 dataset Blackard and Dean 1999) with class ratio approximately 36% for class and 49% for class 2. The entire dataset has 581012 points which is divided into train-test the ratio 70:30. Then, 10% of the training points are held out for calibration (n (DI 4067 1). The base classifier is a random forest (RF) trained on the remaining training points (it achieves around 95% % test accuracy). The RF is then recalibrated using HB. The tapelabel reliability diagrams in Figure 4a illustrate that the original RF (in orange) is underconfident on both the most likely and least likely classes. Additional figures in Appendix F show that the RF is always underconfident no matter which class is predicted as the top-label. HB (in green) recalibrates the RF effectively across all classes. Validity plots (Gupta and Ramdas 2 estimate how the LHS of condition (8), denoted V(E), varies with e. We observe That for all E, (E) is higher for HB. The rightmost barplot compares the estimated TL-ECE for all classes, and also shows the class proportions. While the original RF is significantly miscalibrated for
16

---

Published as a conference paper at ICLR 2022
Ra ndom forest
Histogram binring
Class ratio
Chere valisty
billlty
Cascd biyy
0375
0110
012
100 0.2e 010
3.55
6.32
5.35
4.5
1.20
(a) Top-label histogram binning (Algorithm 8 with l: 100 points per bin. Class 4 has only 183 calibration points. Algorithm addapss and uses only a single bin ensure that the TI.-ECE class 4 is comparable to the TL-ECE on class 2. Overall, the random forest classifier has significantly higher TL-ECE for the least likely classes (4, 5, and 6). but the post-calibratio TL-ECE using binning is quite uniform.
Cleer reduciltt Bagran
Clecc valld pirr
Clas An budd doggnn
Casce va bay
crod prosaiity
Pndiited bybubilty
(b) Histogram binning with B 50 bins for every class. Compared to Figure 4a the post- calibraatt TL-ECE for the most likely classes decreases while the TL-ECE for the least likely classes increases.
Figure 4: Recalibration of a random forest using histogram binning on the class imbalanced COVTYPE-7 dataset (class 2 is roughly 100 times likelier than class 4). By ensuring fixed num- ber of calibration points per bin, AlgorithmB obtains relatively uniform top-label calibration across classes (Figure 4a). In comparison, if a fixed number of bins chosen for all classes, the perfor- mance deteriorates for the least likely classes (Figure 4b).
less likely classes, HB has a more uniform miscalibration across classes Figure 4b considers slightly different HB algorithm where the number of points per class is not adapted to the number of times the class is predicted, but is fixed beforehand (this corresponds to replacing |n/// in 5 Algorithm with fixed B E N). While even in this setting there is drop the TL-ECE compared to the RF model, the final profile less uniform compared to fixing the number of points per bin.
The validity plots and top-label reliability diagrams for all the classes reported in Figure 9 in Appendix along with some additional observations.
C DISTRIBUTION-FRE CLASS-WISH CALIBRATION USING HISTOGRAM BINNING
In this section, we formally describe histogram binning (HB) with the class-wise-calibaue (Algo- rithm 3) and provide theoretical guarantees for it. The overall procedure is called class-wise-HB. Further details and background on HB are contained in Appendix where top-label-HB is de- scribed.
C.1 FORMAL ALGORITHM
To achieve class-wise calibration using binary routines, we learn each component function h; in a 1- v-all fashion as described in Algorithm 3 Algorithm Icontains the pseudocode with the underlying routine as binary HB. To learn lu, we use dataset 2,, which unlike top-label HB (Algorithm contains X, even if c(X;) * I. However the Y, is replaced with 1 1}. The number of points per bin k can be different for different classes, but generally would set kı Larger values k will lead to smaller E and 8, in the guarantees, at loss of sharpness since the number of bins [n/kz] would be smaller.
ky k N.
17

---

Published as a conference paper at ICLR 2022
Algorithm 9: Class-wise histogram binning
Input: Base multiclass predictor X' - A L-1 calibration data D = (X1, ..., (Xn, Yn) Hyperparameter: points per bin kı, ku.................. k No (say each ky 50), tie-breaking parameter 8 > 0 (say 10 10-10)
Output: L class-wise calibrated predictors h1, hr,
for < 1 to L do
D. - {(X,, 1 (Y, = 13) i [n]]]:
h4 Binary- histogram binning(gi, Dı, In/ka) :);;
end
return (h1, he......................... ................................ hL):
C.2 CALIBRATION GUARANTEES
general algorithm for
calibration takes as input calibration data and an initial
classifier to produce an approximately class-wise calibrated predictor h X' - [o, 1l.. Define the notation (#1, , r.) E (0, 1)4 and a 02, ... ..r.) E (0, 1)4.
Definition 2 (Marginal and conditional class wise calibration). Let E, (0,1)* be some given levels of approximation and failure respectively. An algorithm A: (g, D) - i
(a) (e, a)) marginally class-wise calibrated if for every distribution P over X [L] and for every E [T.]
P( P(Y 1 (x)) - hx( & E1 an.
(11)
(b) (e, conndiiiion class-wise calibrated for every distribution over X' [L] and for every e [L].
P P(rr Range(hi), JP(Y (x( =)) - E 1 ay.
(12)
Definition 2 requires that each h is (Ez, oz) calibrated in the binary senses defined by Gupta et al. 2021 Definitions and 2). From Definition we can also uniform bounds that hold simultancously
over every I E [Z]. Let Σt 0g and maXte[L] Then 11 implies
P(VlE [2] P(Y = P(y=1]
(PY==|((())) hx) & <e)
(13)
and implies
P P( [T.),r Range(h)),IP(> = -1 (x( - & 3 1 -
(14)
The choice of not including the uniformity over T. in Definition reveals the nature of our class-wise HB algorithm and the upcoming theoretical guarantees: (a) we learn the hy separately for each / and do not combine the learnt functions in any way (such as normalization), the calibration inequalities for different [L] in any other way other than union bound. Thus the only way we can show 13 (or (4) is by using a union bound over (IT) (or (12).
(b) we do not combine
We now state the distribution-free calibration guarantees satisfied by Algorithm 9
Theorem 2. Fix hyperparameters
0 (arbitrarily small) and points per bin ky k2..... ......., ky > 2, and assume n4 2 for every I E [L]. Then, for every I [L]. for any on (0, 1), Algorithm (e(1), oz) -marginally and (e(2) ,,)) -xo-ciniiii class-wise calibrated with
logg(2 (2/c)) 5, and
Log 2n 2n/k)au) 5.
E (1)
E7 (2)
(15)
2(kg -1] 1)
2(kr
1)
Further, for any distribution P over X x [L].
(a) P(CW-ECE(<,)) & maxie[]] e (2)) 2 E1ELL an and
(b) E [CW-ECE((,))) maxie[L) V 11/2kz 6.
18

---

Published as a conference paper at ICLR 2022
Theorem is proved in Appendix H The proof follows by using the result of Gupta and Ramdas 2202 Theorem 2), derived in the binary calibration setting, for each h4 separately. |uupta and Ramdas (2021) proved more general result for general l, ECE bounds. Similar results can also be derived for the suitably defined C,-CW-FCF.
As discussed in Section 3.2, unlike previous works (Zadrozny and Elkan
2002
Guo et al. 2017
Kull et al. 2019). Algorithm does not normalize the h s. We do not know how to derive Theorem
9
style results for normalized version of Algorithm
D FIGURES FOR APPENDIX
E
Appendix E begins on page The relevant figures for Appendix E displayed on the following
pages.
19

---

Published as a conference paper at ICLR 2022
Base model
Top-label-HB Normalized-HB
Vector scaling
Temperature scaling
Dirichlet scaling
Heptect 50
Ronket
600.75
6.300
0.230
0.02.0
60225
6oz0e
0.0000
6:218
60375
6:11
0,030
Number sins
Kumbbr
Numbbree
hurbbrr 1015
(a) TL-ECE estimates on CIFAR-I0 with Brier score. TL-HB is close to the best each case. While CW-HB performs the best at B = 15, the ECE estimate may not be reliable since it is highly variable across bins.
Rc
Wide: Nade-Bellee 26:15
Dcrochet
0.30
0.25
0.20
2.2
9.20-
0.55
0.30
3.10
0.30
0.30
10
22
15
25
Number sins
Number of
Rumber 2015
Bumber of
(b) TL-ECE estimates CIFAR-100 with Brier score. N-HB the best performing method, while DS is the worst performing method, across different numbers of bins. TL-HB performs worse than TS
5o
Rechiee 110
Wide Ruchle 26.11
DenseNec1221
0.-
2.5
6.7
2.8
0.7-
2A-
cammated
2.3
2a
Numberd
Number
Number
Number
(c) TL-MCE estimates on CIFAR-10 with Brier score. method is TL-HB.
The only reliably and consistently well-performing
NesNutso
Bushie:
2.8
9.55
2.5
2.5
3.A
0.--
33
6.3
02
25
Buumeer
Rumber
Bumber
Number
(d) TL-MCE estimates CIFAR-100 with Brier DS is the performing method. Other methods perform across different values B.
Figure 5: Table 2 style results with the number of bins varied B [5, 25]. See Appendix E.5 for further details. The captions summarize the findings in each case. In most cases, the findings are similar those with B 15. The notable exception is that performance of N-HB on CIFAR-10 for TL-ECE while very good at B 15, is quite inconsistent when seen across different bins. some cases, the blue base model line and the orange temperature scaling line coincide. This occurs since the optimal temperature on the calibration data was learnt to be T 1, which corresponds to not changing the base model all.
20

---

Published as a conference paper at ICLR 2022
Base model
Top-label-HB Normalized HB
Vector scaling
Temperature scaling
Dirichlet scaling
Restee: 53
Restle:: 310
WV do Realiet--6-10
Denos 123
0.053
0.345
0.241
0.033
0.235
0.540
2 0.040
0.332
0.55
0.22
6:22%
0.030
0.02
6.222
0.22
6:11
6.115
0.0
6:015
Mamber of bina
Mamberr 201
Namber 2h1
Numbo of tina
(a) TL-ECE estimates on CIFAR-I0 with loss. TL-HB is close to best in case. While CW-HB performs the best 15, the ECE estimate may not be reliable since is highly variable across bins.
Rambae-53
Redieb333
Wide Sww.-eeeeeneenn 26-10
Deneetat-127
0.25
0.70
220
0.25
335
0:10
3.08
10
15
24
10 15
25
sira
(b) TL-ECE estimates CIFAR-100 with focal loss. N-HB is the best performing method, while DS is the worst performing method, across different numbers of bins. TL.HBB performs worse than TS and VS.
BesNets3
Ranhwe-320
M
0.-
Extmeret ECE FA
0.2
0.t
0.-
2.
Number Dis
Rumber bin
Numbel Mis
Number of bin
(c) TL-MCE estimates on CIFAR-10 10 with focal loss. method is TL-HB.
The only reliably and consistently well well-performing
ResNetSo
Rushee 110
Wide Rechic::6 10
Duno
2.0
3.55
0.8-
6.6
2.7
Cemmtec ICC
0.2
15
20
10
75
15
20
10
25
(d) TL-MCE estimates CIFAR- 100 with focal loss. DS is the worst performing method. Other methods perform across different values of B.
Figure 6: Table 4 style results with the number of bins varied as B [5, 25]. See Appendix F.5 for further details. The captions summarize the findings in each case. In most cases, the findings are similar to those with B = 15. In some cases, the blue base model line and the orange temperature scaling line coincide. This occurs since the optimal temperature on the calibration data was learnt to be T = 1, which corresponds to not changing the base model at all.
21

---

Published as a conference paper at ICLR 2022
Base model
Class-wise-HB Normalized-HB
Vector scaling Dirichlet scaling
Temperature scaling
0.207
Rechee::
Benseler:12)
0.037
0.636
00040
231
5 0.003
0.004
0:33
00030
0.922
0.012
Mumber
Kumberef
Numberal
(a) CW-FCE estimates on CTEAR-10 with Brier score. CW-HB the best performing method bins, and N-HB quite unreliable.
Ra
de 2d0--eallet-2---100
Ner:
0.220
0.206
0.006
0.338
0.205
000015
0.234
0.004
0.033
0.033
0.003
0.912
6.911
0.033
25
2010
(b) CW-ECE estimates CIFAR-100 with Brier CW-HIB is the best performing method. DS and N-IIB are worst performing methods.
Figure 7: Table style results with the number of bins varied as B E [5, 25J. The captions summarize the findings in each case, which are consistent with those in the table. See Appendix E.5 for further details.
Rosteed 50
McsMcc--10
Penscce::122
0.303
0.302
0.000
Edimuted SE2
0.20
0.335
0.054
0.03
0:333
6.002
Mumber ains
Number
Number Lin
Numberor Line
(a) CW-ECE estimates on CIFAR- 10 with focal loss. CW-HB is the best performing method across bins, and N-HB is quite unreliable.
Rcslac:
ReaMect-10
de Re--lNett--2-1
6.331
0.935
0.303
0.333
0.523
0.322
0.032
0.302
6.03
0.033
0.643
pita
Number
Numbor Line
Numboro Line
(b) CW-ECE estimates on CIFAR- 100 with focal loss. CW-HB is the best performing method. DS and N-HB are the worst performing methods.
Figure 8: Table style results with the number of bins varied as [5, 25]. The captions summarize the findings in each case, which are consistent with those in the table. See Appendix E.5 for further details.
22

---

Published as a conference paper at ICLR 2022
E ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS FOR CIFAR- 10 AND CIFAR-100
We present additional details and results to supplement the experiments with CIFAR-10 and CIFAR- 100 in Sections 2 and of the main paper.
E. EXTERNAL LIBRARIES USED
All our base models were pre-trained deep-net models generated by Mukhoti et al. (2020), obtained from www. robots......... ox ac wwt..uuk//vvvvviie focal locallcall iib ibbrati oontiinn/// and used along with the code at https: : / /gi thub.. com/torrv ierorrvvsiii s sion/ focal 1 ca 1 bibratiion on to obtain base predic- tions. We focused on the models trained with Brier score and focal loss, since it was found to perform the best for calibration. All reports in the main paper are with the Brier score; in Appendix E.4 we report corresponding results with focal loss.
We also used the code at https: /ttttbb......t temperature scaling (TS). For vector scaling (VS) and Dirichlet scaling (DS), we used the code of http//ddirccehteeeiiiii...
www.iiaaiibiiiiinoom for
Kull et (2019), hosted at https: For VS, we used the file ctt.cccceettcllccccaa///ccccacte the file di ciichee cwwehccaaaaccccccccc ctccccalbffllldd richlet py. No hyperparameter tuning was per- formed in any of our histogram binning experiments or baseline experiments; default settings were used every case. The random seed was fixed so that every run of the experiment gives the same result. In particular, by relying on pre-trained models, we avoid training new deep-net models with multiple hyperparameters, thus avoiding any selection biases that may arise due test-data peeking across multiple settings.
python. lin.eeainngp... py, and for DS, we used
E.2 FURTHER COMMENTS ON BINNING FOR ECE ESTIMATION
As mentioned in Remark I ECE estimates for all methods except TL-HB and CW-HB was done using fixed-widhs width bins [0. T/ B), [1/ B, ... - 1/B, 1] for various values of B E [5, 25]. For TI.HB and CW-HB,
the number of bins used for each call to binary HB. For TL.HH,, note that actually proposed that the number of bins-per-class should be fixed; see Section B.2 However, for ease of comparison to other methods, we simply set the number of bins to B for each call to binary HB. That is, in line 5 we replace |n//|| with B. For CW-HB, we described Algorithm with different values of k corresponding to the number of bins per class. For the CIFAR-10 and CIFAR-100 comparisons, we set each kn h2
kj. k, where k N satisfies [n/k] B.
Tables 23 and 5 report estimates with B = 15, which has been commonly used in many works (uoo al. 2017 Kull et al., 2019 Mukhoti al. 2020). Corresponding each table, have figure where ECE estimates with varying B are reported to strengthen conclusions: these are Fig- respectively. Plugin estimates the ECE were used, same Guo al. (2017). Further binning was not done for TL-HB and CW-HB since the output is already discrete and sui- ficiently many points take each of the predicted values. Note that due to Jensen's 's inequality, any further binning will only decrease the ECE estimate (Kumar et al.] 2019). Thus, using unbinned estimates may give TL-HB and CW-HB disadvantage.
ure 7 and g
E.3
SOME REMARKS ON MAXIMUM-CALIBRATUI
(MCE)
Guo et al. (017)) defined MCE with respect to confidence calibration, as follows:
conf-MCE(c. := sup
IP(Y c(X) h(X) = rl.
(16)
reRange(h)
Conf-MCE suffers from the same issue illustrated in Figure for Conf-ECE. In Figure lb we looked at the reliability diagram within two bins. These indicate two of the values over which the supremum is taken in equation (16): these are the Y-axis distances between the * markers and the = line for bins 6 and 10 (both are less than 0.02). On the other hand, the effective maximum miscalibration for bin 6 is roughly 0.15 (for class 1), and roughly 0.045 (for class 4), and the maximum should be taken with respect these values across all bins. To remedy the underestimation of the effective
23

---

Published as a conference paper at ICLR 2022
Metric
Dataset
Architecture
Base
TS
VS
DS
N-HB
TL-HB
ResNet-50
0.022
0.023
0.018
0.019
0.023
0.019
ResNet- 10
0.025
0.024
0.022
0.021
0.020
0.020
CIFAR-10
WRN-26- 10
0.024
0.019
0.016
0.017
0.019
0.018
Top- label-
DenseNet- 121
0.023
0.023
0.021
0.021
0.025
0.021
ResNet-50
0.109
0.
0.107
0.332
0.086
0.148
ECE
ResNet- 110
0.124
0.117
0.105
0.316
0.115
0.153
CIFAR-100
WRN-26-10
0.100
0.100
0.101
0.293
0.074
0.135
DenseNet-121
0.106
0.108
0.105
0.312
0.091
0.147
ResNet-50
0.298
0.443
0.368
0.472
0.325
0.082
ResNet-110
0.378
0.293
0.750
0.736
0.535
0.089
CIFAR-10
WRN-26-10
0.741
0.582
0.31
0.363
0.344
0.075
Top- label-
DenseNet-121
0.411
0.411
0.243
0.391
0.301
0.099
ResNet-50
0.289
0.355
0.234
0.640
0.322
0.273
MCE
ResNet-
0.293
0.265
0.274
0.633
0.366
0.272
CIFAR-100
WRN-266-10
0.251
0.227
0.256
0.663
0.229
0.270
DenseNet-121
0.237
0.225
0.239
0.597
0.327
0.248
Table 4: Top-label-ECE and top-label-MCE for deep-net models and various post-hoc calibrators. All methods are same as Table Best performing method each row is in bold.
MCE, we can consider the top-label-MCE, defined as
TL-MCB(c, h) == max sup IP(Y - c( -))
(17)
[E[L] (ERange(h))
Interpreted in words, the TL-MCE assesses the maximum deviation between the predicted and true probabilities across all predictions and all classes. Following the same argument in the proof of Proposition 4 it can be shown that for any c, h, conf-MCE(c, h) TL-MCE(c, h). The TL-MCE
closely related to conditional top-label calibration (Definition [b). Clearly, an algorithm is (s, conditionally top-label calibrated if and only if for every distribution P, P(TL-MCE(c, h) & E) > 1- a. Thus the conditional top-label calibration guarantee of Theorem iimplies high probability bound on the TL-MCE as well.
E.4 TABLE AND 3 STYLE RESULTS WITH FOCAL LOSS
Results for top-labeI-ECE and top-label-MCE. with the base deep net model being trained using focal loss are reported in Table 4 Corresponding results for Maas-wiss--EC are reported in Table The observations are similar to the ones reported for Brier score:
1. For TL-ECE, TL-HB is either the best close to the best performing method CIFAR- 10, but suffers on CIFAR- 100. This phenomenon is discussed further in Appendix E.6 N-HB is the best close the best for both CIFAR-10 and CIFAR-100.
2. For TL-MCE, TL-HB is the best performing method on CIFAR-10, 10, by huge margin. For CIFAR-100, TS or VS perform better than TL-HB, but not by a huge margin.
3. For CW-ECE, CW-HB is the best performing method across the two datasets and all four architectures.
E.5 ECE AND MCE ESTIMATES WITH VARYING NUMBER OF BINS
Corresponding to each entry in Tables and we perform an ablation study with the number of bins varying as B E [5, 25). This is in keeping with the findings of Roclofs et al. (2020) that the ECE/MCE estimate can vary with different numbers of bins, along with the relative performance of the various models.
(ablation of Table 2) and Figure (ablation of Table B The captions of these figures contain further details the findings. Most findings similar those in the main paper, but the findings in the tables are strengthened through this ablation. The same ablations performed for focal loss well. The results reported in Figure 6 (ablation of
The results are reported in Figure 5
24

---

Published as a conference paper at ICLR 2022
Metric
Dataset
Architecture
Base
TS
VS
DS
N-HB
CW-HB
ResNet-550
0.42
0,42
0.35
0.37
0.52
0.35
ResNet- 10
0.48
0.44
0.36
0.35
0.51
0.29
CIFAR-10
Class- wise-
WRN-266-00
0.41
0.31
0.31
0.35
0.49
0.27
DenseNet-121
0.41
0.41
0.40
0.39
0.63
0.30
ECE
ResNet-50
0.22
0.20
0.20
0.66
0.23
0.16
x x102
ResNet-110
0.24
0.23
0.21
0.72
0.24
0.16
CIFAR-100
WRN-26-10
0.19
0.19
0.18
0.61
0.20
0.14
DenseNet-121
0.20
0.21
0.19
0.66
0.24
0.16
Table 5: Class-wise-ECE for deep-net models and various post-hoc calibrators. All methods are same Table 2 except top-label-HB is replaced with class-wise-HB or Algorithm 3 (CW-HB). Best performing method in each row is in bold.
Table 4 and Figure (ablation of Table 5). The captions of these figures contain further details on the findings. The ablation results in the figures support those the tables.
E.6 ANALYZING THE POOR PERFORMANCE OF TL-HB ON CIFAR-100
CIFAR- 100 is imbalanced dataset with 100 classes and 5000 points for validation/calliration (as per the default splits). Due to random subsampling, the validation split we used had one of the classes predicted the top-label only 31 times. Thus, based Theorem [ we do not expect HB to have small TL-ECE. This is confirmed by the empirical results presented in Tables 24 and Figures 5b.6b We observe that HB has higher estimated TL-ECE than all methods except DS, for most values of the number of bins. The performance of TL-HB for TL-MCE however is much much closer to the other methods since HB uses the same number of points per bin, ensuring that the predictions are somewhat equally calibrated across bins (Figures 6d). In comparison. for CW- ECE, CW-HB the best performing method. This is because in the class-wise setting, 5000 points are available for recalibration irrespective of the class, which is sufficient for HB.
The deterioration performance of HB when few calibration points are available was also observed in the binary setting by Gupta and Ramdas (202T] Appendix C). Miculescu-Mizi and Caruana (2005) noted in the conclusion their paper that Platt scaling (Platt 1999). which is closely related to TS, performs well when the data is small, but another nonparametric binning method, isotonic regression
Zadrozny and Elkan 2002) performs better when enough data is available. Kull et al. (2019) Section 4.1) compared HB to other calibration techniques for class- wise calibration on 21 UCI datasets, and found that HB performs the worst. On inspecting the UCI repository, we found that most of the datasets they used had fewer than 5000 (total) data points, and many contain fewer than 500.
Overall, comparing our results to previous empirical studies, we believe that if sufficiently many points are available for recalibration, or the number of classes is small, then HB performs quite well. To be more precise, we expect HB to be competitive if at least 200 points per class can be held out for recalibration, and the number of points per bin is at least > 20.
F ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS FOR COVTYPE-7
We present additional details and results for the top-label HB experiment of Section B.2 The base classifier is an RF learnt using sklearn. ensemble import RandomFos wwwammoorrstteee cesttllasee sisssiiiesss fier with default parameters. The base RF is a nearly continuous base model since most predictions are unique. Thus, we need to use binning to make reliability diagrams, validity plots, and perform ECE estimation, for the base model. To have fair comparison, instead of having fixed binning scheme to assess the base model, the binning scheme was decided based on the unique predictions of top- label HB. Thus for every I, and r E Range( fz), the bins are defined as (æ : c(z) = L, h1(2) = r). Due to this, while the base model in Figures 4a and 4b are the same, the reliability diagrams and validity plots in orange are different. As can be seen in the bar plots in Figure 4 the ECE estimation is not affected significantly.
When lo 100, the total number of bins chosen by Algorithm 8 was 403, which is roughly 57.6 bins per class. The choice of B 50 for the fixed bins per class experiment made this basis.
25

---

Published as a conference paper at ICLR 2022
Ly dupgnn
Claa vol d2y pic.
Cater spom
0.3
0.2
431 075
Findited pribstt
Fredcted proburilty
Cito 2rehace duggam
Class vol stc.
Case 2-cckde boyd
Class 2 2eliiiy sM
0.4
0.5
0.5
$10
150
0.22
515
0.15
0.75
1:00
635
6.10
0.3
Trodited
probucilty
1.0
100
325
150
5.5
100
0.00
0.33
3.0
0.55
350
0.15
130
385
030
0.3
noliie dbub
probuciity
ryliniiiyy 10yran
Clyse 4 vol ihyy plit
Clans comii Elydaamm aayan
Clecs vabiity 19
Frodited grobsti
Tredicted probaciltt
Clocr and
Csec
1.2
1.3
2.00
0.2
0.2
32
02-
0.2
2.8
60
03
8.60
3.55
850
375
160
0.58
6.55
6.1
335
330
0.35
336
0.15
1.0
0.30
885
630
035
rollettly duggum
Clas vulilyy plc.
Oato Bty sgga
2.4
044
0.2
mndited arittt by
mrddcted proburiity
Card 7 miliciiityy 5hgram
Clore val piz
Oser T Et samm
Clore Tiaaddyy obe
2.8
0.00
0.3
0.5
Trodkted bo
550
0.22
0.55
353
0.75
probuiliy
1:00
0.10
(a) Top-label HB with A 100 points per bin.
(b) Top-label HB with B 50 bins per class.
Figure 9: Top-label histogram binning (HB) calibrates a miscalibrated random-foree on the class imbalanced COVTYPE-7 dataset. For the less likely classes (4, and 6), the left column is bet- ter calibrated than the right column. Similar observations are made on other datasets, and so we recommend adaptively choosing different number of bins per class, Algorithm does.
26

---

Published as a conference paper at ICLR 2022
Figure 9 supplements Figure in the main paper by presenting reliability diagrams and validity plots of top-label HB for all classes. Figure Pa presents the plots with adaptive number of bins per class (Algorithm B). and Figure 9b presents these for fixed number of bins per class. We make the following observations.
(a)
For every class / [T., the RF is overconfident. This may seem surprising first since generally expect that models may be overconfident for certain classes and underconfident for others. However, note that all our plots assess top-label calibration, that is, we are assessing the predicted and true probabilities of only the predicted class. It is possible that a model is overconfident for every class whenever that class is predicted to be the top-label.
(b) For the most likely classes, namely classes and 2, the number of bins in the adaptive case is higher than 50. Fewer bins leads to better calibration (at the cost of sharpness). This can be verified through the validity plots for classes 1 and 2 the validity plots in the fixed bins case is slightly above the validity plot in the adaptive bin case. However both validity plots are quite similar.
(c) The opposite is true for the least likely classes, namely classes 4, 5, 6. The validity plot in the fixed bins case is below the validity plot in the adaptive bins case, indicating higher TL-ECE in the fixed bins case. The difference between the validity plots is high. Thus if a fixed number bins per class is pre-decided, the performance for the least likely classes significantly suffers.
Based on these observations, we recommend adaptively choosing the number of bins per class, as done by Algorithm
G BINNING-BASED CALIBRATORS FOR CANONICAL MULTICLASS CALIBRATION
Canonical calibration notion of calibration that does not fall the M2B category. To define canonical calibration, we use Y to denote the output a 1-hot vector. That is. Y, ey, A where E corresponds to the I-th canonical basis vector in Idd, Recall that a predictor = h21, ... h2) is said to be canonically calibrated if P(Y = / h(X)) hx(X) for every e [L]. Equivalently, this can be stated as E [Y h(X)] = h(X). Canonical calibration implies class-wise calibration:
Proposition 1. F [Y] h(x)] = h(X), then for every e [Z]. P(Y = 1 (1,(()) (x(
The proof in Appendix H straightforward, but the statement above illuminating, because there exist predictors that are class-wise calibrated but not canonically calibrated (Vaicenavicius et al.
2019 Example 1).
Canonical calibration is not an M2B notion since the conditioning occurs on the L-dimensional prediction vector pred(X)= = h(X), and after this conditioning, each of the L statements P(Y 1 XX) = (x) should simultaneously be true. On the other hand, M2B notions verify only individual binary calibration claims for every such conditioning. Since canonical calibration does not fall in the M2B category, Algorithm 5 does not lead to calibrator for canonical calibration. In this section, we discuss alternative binning-bast based approaches to achieving canonical calibration.
For binary calibration, there is complete ordering on the interval [0. 1]. and this ordering is lever- aged by binning based calibration algorithms. However, A for L > 3 does not have such a natural ordering. Hence, binning algorithms do not obviously extend for multiclass classification. In this section, we briefly discuss some binning-bart based calibrators for canonical calibration. Our descriptions are for general L > 3, but anticipate these algorithms work reasonably only for small L., say if I. & 5.
As usual, denote g X L-1 as the base model and h X 4-1 the model learnt ing some post-hoe canonical calibrator. For canonical calibration, we can surmise binning schemes that directly learn h by partitioning the prediction space A L-1 into bins and estimating the dis- tribution of Y in each bin. A canonical calibration guarantee can be showed for such a binning scheme using multinomial concentration (Podkopaev and Ramdas 202T, Section 3.1). However, since Vol( A 1 28(L), there will either be bin whose volume is 20L) (meaning that h would
27

---

Published as a conference paper at ICLR 2022
not be sharp), the number of bins will be 20(1)) entailing 20(1) requirements the sample complexity a curse of dimensionality. Nevertheless, let us consider some binning schemes that could work if L is small.
Formally, a binning scheme corresponds to a partitioning of A into B e bins. We denote this binning scheme as B : A [B], where (ss) corresponds the bin to which A belongs. To learn h, the calibration data is binned to get sets of data-point indices that belong to each bin, depending on the g(X,) values:
for every b E [B], :=
= {i
B(g()))) 6). n., |Tbl-
We then compute the following estimates for the label probabilities in each bin:
for every (l, [4] x [B], Nr. Eien, 1 (Y: 1)
if n, > 0 else f1 1/B.
Thb
The binning predictor h : - A--1 is now defined component-wise follows:
for every E [L], (z()) [1,,8())
In words, for every bin E [B]. h predicts the empirical distribution of the values in bin b.
Using a multinomial concentration inequality (Devroye 1983 Qian et al. 2020, Weissman et al.) 2003), calibration guarantees can be shown for the learnt h. Podkopaev and Ramdas (2021 Theorem 3) show such result using the HaaegnnolleHube--CCee inequality give bounds that depend inversely on n. or /Tu.
inequality. All of these concentration
In the following subsections, we describe some binning schemes which can be used for canoni- cal calibration based on the setup illustrated above. First we describe fixed schemes that are not adaptive the distribution of the data: Sierpinski binning (Appendix G.I) and grid-style binning (Appendix G.2). These are analogous to fixed-width binning for L = 2. Fixed binning schemes not adapted to the calibration data and may have highly imbalanced bins leading to poor esti- mation of the distribution of Y in bins with small T4. In the binary case, this issue is remedied using histogram binning ensure that each bin has nearly the same number of calibration points Gupta and Ramdas 2021). While histogram binning uses the order of the scalar g(X,) values, there is no obvious ordering for the cilti-dimensional gXX,) values. In Appendix G.3 we describe projection based histogram binning scheme that circumvents this issue and ensures that each na reasonably large. In Appendix G.4
we present some preliminary experimental results using our
proposed binning schemes.
Certain asymptotic consistency results different from calibration have been established for histogram regression and classification in the nonparametric statistics literature (Nobel) 1996; Lugosi and No- bel] 1996 Gordon and Olshen 1984, Breiman et al., 2017 Devroye 1988;; further extensive refer- ences can be found within these works. The methodology of histogram regression and classification relies on binning and is very similar to the one we propose here. The main difference is that these works consider binning the feature space X' directly, unlike the post-hoc setting where we are essen- tially interested in binning AL- In terms of theory, the results these works target are asymptotic consistency for the (Bayes) optimal classification and regression functions, instead of canonical cal- ibration. It would be interesting to consider the (finite-sample) canonical calibration properties of the various algorithms proposed in the context of histogram classification. However, such a study is beyond the scope of this paper.
G.1 STERPINSKI BINNING
First, we describe Sierpinski binning for L -= 3. The probability simplex for L 3, A is a triangle with vertices e = (1, 0, 0), e2 (0, 1), and e3 (0, 0, 1). Sierpinski binning is a recursive partitioning of this triangle based on the fractal popularly known as the Sierpinski triangles. Some Sierpinski bins for L 3 are shown in Figure I0 Formally, we define Sierpinski binning recursively based on depth parameter E N. Given an E X, let s = g(x). For = 1, the number of bins is B 4, and the binning scheme B is defined as:
1 if $1 > 0.5
2
if 82 > 0.5
B(s)= =
(18)
3 if 83 > 0.5
4 otherwise.
28

---

Published as a conference paper at ICLR 2022
A²
4 -
=
4
Figure 10: Sierpinski binning for I. 3. The leftmost triangle represents the probability simplex
A Sierpinski binning divides A recursively based on depth parameter E N.
Note that since + + 1, only one of the above conditions can be true. It can be verified that each of the bins have volume equal to (1/4)-th the volume the probability simplex A². If finer resolution of A is desired, B can be increased by further dividing the partitions above. Note that each partition is itself a triangle; thus each triangle can be mapped to A to recursively define the sub- sartpaatitionnng. For i [4], define the bins b, {s ((s) = =]. Consider the bin bj Let us reparameterize as (f), f2, tq) = (2s) - 1, 2s,, 2s²). can be verified that
bj = [(41, 12, 13) 81 > 0.5) = ((11, (2,1, (3) 4 + l2 + L3 = 1,4 E (0, 11,12 E [0, [0, 1))-
Based on this reparameterizaation, we can recursively sub-partition b per the scheme (18). replac- ing 8 with t. Such reparameterizations can defined for each of the bins defined in 18):
b2 = {(51, 52, 53)
0.5) (f1, ta) = (2s1, 252 - 1, 253);
by $2, s3) 53 0.5) (t1, ta) (231, 28, 283 1),
4 = ((11 52, s3) : 8, & 0.5 for all i} (2,,42, tx) = =(1 -11-281. 1-28,,
28y),
and thus every bin can be recursively sub-partitioned as per (18). As illustrated in Figure 10 for Sierpinski binning, we sub-partition only the bins b,, b2; by since the bin ba corresponds to low confidence for all labels, where finer calibration may not be needed. (Also, in the described shortly, the corresponding version of 61 geometrically different from A A and the recursive partitioning cannot be defined for it.) If at every depth, we sub-partition all bins except the corresponding by bins, then it can be shown using simple algebra that the total number of bins is (3a+1 - 1)/2. For example, in Figure 10 when 9 = 2, the number of bins is B = 14, and when q = 3, the number of bins B 40.
3 case
As in the case of L 3, Sierpinski binning for general L is defined through partitioning function of A L-1 into L + bins, and a reparameterization of the partitions so that they can be further sub-partitioned. The T. + bins at depth g = 1 are defined as
B(s)= { +++1
if > 0.5, otherwise.
(19)
While this looks similar to the partitioning (8). the main difference is that the bin by.-1 has larger volume than other bins. Indeed for e [.]. vol(hr vol(A4-1)/244 while vol(br+1) vol( (11--))11 - T./2L-1) > vol( (0((A-))/22-)) with equality only occuring for T. 3. Thus the bin bL+1 is larger than the other bins. If g(x) b1+1. then the prediction for may be not be very sharp, compared to if g(x) were in any of the other bins, On the other hand, if g(x) E bb+t1 the score for every class is smaller than 0.5, and sharp calibration may often not be desired in this region.
In keeping with this understanding, only reparameterize the bins b,, by ... by that they can be further divided:
bi $2.... 81) 31 > 0.5) (t1, t2, .t......tt)) tt) = (2.1..... 2s - 1,... ,2t). For every 1 E [7.]. under the reparameterization above, it is straightforward to verify that
((1 l2 ( : 81 > 0.5} ((4,44....,,44))
Σ l 1, e (0, 11,4 (0, Vu # 1}. ME[A]
Thus every bin can recursively sub partitioned following labels, the number of bins at depth y is given by (I,9+1 1)/( 1).
19
For Sierpinski binning with L
29

---

Published as a conference paper at ICLR 2022
0.25
0.75
0.2
0.8
Class 1
0.5
0.5
Cass
Class
0.4
0.6
Caty
0.6
0.4
0.75
0.25
0.8
0.2
1
0
0.75
K
4,
T
0.25
K 5, T 0.2
Figure 11: Grid-style binning for L = 3.
G.2 GRID-STYLE BINNING
Grid-style binning is motivated from the 2D reliability diagrams of Widmann et al. (2019) Figure 1), where they partitioned A into multiple equi-volune bins in order to assess canonical ca calibration
a 3-class version of CIFAR-10. For L 3, A can be divided as shown in Figure This corre-
sponds gridding the space A just the way we think of gridding the real hyperplane. However, the mathematical description of this grid for general L is not apparent from Figure
We describe
grid-style binning formally for general L >> 3.
kL) in the set Consider some > 0 such that K == 1LTT E N. For every tuple k = (21, ...
(KENN max K + 1) &
Σ
ha & K + (L-1)} 1)},
(20)
[E[L]
define the bins
bk (s A for every / sK E [kr
1, ki].
(21)
These bins are not mutually disjoint, but intersections can only occur the edges. That is, for every that belongs to more than one bin, at least one component satisies s,K E N. In order to identify a single bin s, ties can broken arbitrarily. One strategy is to use some ordering on N4; say for kj * K2 N, ki < k2 if and only if for the first element of ki that is unequal to the corresponding element of k2 the one corresponding to kj is smaller. Then define the binning function B A
bx). The following propositions prove that a) each s belongs to at least one bin, and b) that every bin is an L 1 dimensional object (and thus a meaningful partition of A (1-1).
|/| as B(s)
min(k
Proposition 2. The bins (bk ke 1} defined by 21 mutually exhaust A L-11
Proof. Consider any s Consider the condition
A 4-11 For s $ N = (1, set ky = max(1, > s,K.
C: for all I such that K N, 8:K = 0.
If true, then for 1 such that 8t K N, set ka K. If C is not true, then for I such that st K N, set exactly one Kj = 8j + 1, and for the rest set k K. Based on this setting of k, it can be
verified that bk-
Further, note that for every 1, ln 22 K, and there exists at least one such that by > s,K Thus we have:
K
K.
Since Σl= ky e N, we must have ELe by 3 K + 1. Further since each k E N, ELe ky
Next, note that for every I, k & s 1. If C is true, then there is at least one I such that K N, and for this I, we have set k; = K < s + 1. If is not true, then either there exists at least one I such that st K & N. u (0) for which ky K K K + 1, every K N. in which case
30

---

Published as a conference paper at ICLR 2022
have set ku s K for one of them. In all cases, note that there exists such that k s,K + 1. Thus,
ka
(s +1
1-1
K + L.
Since 2/_1 & N, we must have Σ h & K + L 1.
Next, we show that each bin indexed by k E contains a non-zero volume subset of A where volume is defined with respect to the Lebesgue measure in I L-11, This can be shown by arguing that by contains a scaled and translated version of A L-1
Proposition 3. For every k I, there exists some
TR& and such that VAL-1 L-111 = bu-
Proof. Fix some E By condition 20 El=1 ha E [max L, + 1), + I 1]. Based on this, claim that there exists T 1) such that
Σ 1-1
(ki - 1) + -1-T) K.
(22)
Indeed, note that for 0, Σ (k)
+ rI. (1- & (K 1) + K and for 1,
(k -
1) + rL + (1 - 7) = Σ kj > K. Thus, there exists a T that satisfies (2) by the
intermediate value theorem.
Next, define u = K (k + (7 - 1)1r) and v = K x-1((1-))) (1 > 0, where 1, denotes the vector
in RL with each component equal 1. Consider any s U L-1, Note that for every 1 E [Z],
K [k- - 1, ]ig and by property (22).
L
L 10h
Σ
+ (5- 1)) (T-1))
+ 00= Σ (1- + FL (1 (1- K.
Thus, s A and by the definition of bk. e bx. This completes the proof.
The previous two propositions imply that B satisfies the property we require of reasonable binning scheme. For L = 3, grid-style binning gives equi- bins illustrated in Figure [T] however this is not true for 3. We now describe a histogram binning based partitioning scheme.
G.3 PROJECTION BASED HISTOGRAM BINNING FOR CANONICAL CALIBRATION
Some of the bins defined by Sierpinski binning and grid-style binning may have very few calibration points ni. leading poor estimation îl. In the binary calibration case, this can be remedied using histogram binning which strongly relies on the scoring function taking values in a fully ordered space [0, 1J. To ensure that each bin contains Q(n/B) points, we estimate the quantiles of g(X) and created the bins as per these quantiles. However, there are no natural quantiles for unordered prediction spaces such as A r- (L 3). In this section, we develop histogram binning scheme for 4-1 that is semantically interpretable and has desirable statistical properties.
Our algorithm takes as input a prescribed number of bins and an arbitrary sequence of vectors ς1 ................................ 9--1 1 IR with unit f--nor:: |/qill2 1. Each of these vectors represents direction on which we will project L-1 in order to induce full order on 4-1 Then, for each direction, we will use order statistics
the induced full order to identify bin with exactly [[n + 1)/BJ- 1 calibration points (except the last bin, which may have more points). The formal algorithm is described in Algorithm 10 It uses the following
notation: given vectors U1, U2 ... Un RR. a unit vector u, and an index j E [m]. let order-statistics( (U, U2 ... em u, j) denote the j-th order-statistics of {uf u, v/ M,.....0 " u..)).
31

---

Published as a conference paper at ICLR 2022
Algorithm 10: Projection histogram binning for canonical calibration
Input: Base multiclass predictor X' A calibration data ((X1, Yi), (X2, Y2)...., (X,,, Yn)
Hyperparameter: number of bins B, unit vectors 91, 92. . E R,,, Output: Approximately calibrated scoring function h S - (g(Xi), g(X)),.. .(X.).
- -empy array of size B:
c |=
for b - to B 1 do
Т3 order-statisties(S. e); f S: v qo & To);
end
TB < 1.01;
B(g(-)) - min(be E []] g(-)² qb < To);
10 π - e-mptyy matrix of size L;
11 for b - to B do
12
for 1 to L do
fi. - Mean (Y, = 1) B(g((.)) = and V [B], g(X.)* 9o * To):
13
end
15 end
16 for 1 to do
hx(-) - (18(())).
17
18 end
return h;
We now briefly describe some values computed by Algorithm 10 in words to build intuition. The array T. which is learnt on the data, represents the identified thresholds for directions given by g. Each (4b,Th TT) pair corresponds to hyperplane that cuts A into two subsets given by {ar E A x" qb < T3} and (ar A =x"xx" qb > To}. The overall partitioning of A is created by merging these cuts sequentially. This defines the binning function B. By construction, the binning function such that each bin contains at least | many points in its interior. As suggested by Gupta and Ramdas (2021), do not include the points that lie the boundary, that is, points X; that satisfy g(X;)² 9s T, for some s e [B]. The interior points bins are then used to estimate the bin biases TT.
No matter how the vevtoss are chosen, the bins created by Algorithm h0 at least ; - points for bias estimation. However, we discuss some simple heuristics for setting 9 that are semantically meaningful. For some intuition, note that the binary version of histogram binning Gupta and Ramdas 2021 Algorithm 1) is essentially recovered by Algorithm [0 if L by setting each y e2 (the vector [o, 1)). Equivalently. we can set each q6 to -e since both are equivalent for creating a projection- based order Az. Thus for L > 3, natural strategy for the q-vectors is rotate between the canonical basis vectors: and Projecting with respect to -e; focuses the class by forming a bin corresponding to the largest values of (x(X,) among the remaining X,'s which have not yet been binned. (On the
= e1,
-e2..... Qt.
-z,, (L++1 = - -e.....
other hand, projecting with respect to e will correspond forming bin with the smallest values of (X.).)
The vevectoss also be set adaptively based the training data (without seeing the calibration data). For instance, if most points belong to specific class E [L]. we may want more sharpness for this particular class. In that case, we can choose higher ratio of the q-vectors be ej,
G.4 EXPERIMENTS WITH THE COVTYPE DATASET
In Figure illustrate the binning schemes proposed in this section 3-class version of the COVTYPE dataset considered Section B.2 As noted before, this is an imbalanced dataset where classes 1 and 2 dominate. We created a class problem with the classes 1, 2, and other (as
32

---

Published as a conference paper at ICLR 2022
0.0
0.6
0.2
Brrning
(3...)
0.00
0.06
030
015
(a) Calibration using Sierpinski binning at depth 2.
1.5
666
0.2
Logedic
0.00
0.05
0.30
035
(b) Calibration using grid-style binning with K 5, - 0.2.
1.5
0.6
Logtdic rogressir
00
Bening
0.00
(c) Projection-basse with 27 projections: @1
e1, Q2
e2.
24: -1,
and so on.
4.5
V12
0.4
Logidic regrmakor
60
Brriin
232
(d) Projection-basse based HB with B 27 random projections (g, drawn uniformly from the En-unit-ball in R²),
Canonical calibration using fixed and histogram binning COVTYPE-7 dataset. The reliability diagrams (left) indicate that all forms of binning improve the calibration of the base logistic regression model. The recalibration diagrams (right) of the predictions g(X) on the test data with the points colored in 10 different colors depending on their bin. For every bin, the arrow-tail indicates the mean probability predicted by the base model g whereas the arrow-head indicates the probability predicted by the updated model h.
Figure 12:
3-class version of the
scatter plot
class 3). The entire dataset has 58 581012 points and the ratio of the classes is approximately 36%, 49%, 15% respectively. The dataset was split into train-test the ratio 70:30. The training data was further split into modeling-callibatiio in the ratio 90:10. A logistic regression model using sklearn. warrn.iine Winear was recalibrated on the calibration data.
1tt.11i.nnommeeell morermmoeel...mm www.istiieegeeeseeee.....o cRegression was leamt on the modeling data, and g
The plots on the right in Figure 12 are recalibration diagrams. The base predictions g(X) on the test-data displayed scatter plot 2 Points in different bins colored using of 10
33

---

Published as a conference paper at ICLR 2022
different colors (since the number of bins is larger than 10, some colors correspond to than one bin). For each bin, an arrow is drawn, where the tail of the arrow corresponds to the average g(X) predictions in the bin and the head of the arrow corresponds to the recalibrated h(X) prediction for the bin. For bins that contained very few points, the arrows are suppressed for visual clarity.
The plots the left in Figure 12 are validity plots (Gupta and Ramdas 2021). Validity plots display estimates of
V(e) dast--data (J |
gg - <
as varies (g corresponds to the validity plot for logistic regression: replacing g with above gives plots for the binning based classifier h). For logistic regression, the same binning scheme as the one provided by h is used to estimate V(e).
Overall, Figure 12 shows that all of the binning approaches improve the calibration of the original logistic regression model across different e. However, the recalibration does not change the original model significantly. Comparing the different binning methods each other, we find that they all perform quite similarly. It would be interesting to further study these and other binning methods for post-hoc canonical calibration.
H PROOFS
Proofs appear in separate subsections, in the same order the corresponding results appear in the paper and Appendix. Proposition was stated informally, so we state formally as well.
H.1 STATEMENT AND PROOF OF PROPOSITION
Proposition 4. For any predictor (c, h), conf-ECE(e,.) & TL-ECE(c,
Proof. To avoid confusion between the the conditioning operator and the absolute value operator |-|, use abs (-) denote absolute values below. Note that,
abs (P(Y c(X) h(X)) h(X)) abs E
[ Y
c(X)) k(X]] h(X))
abs E
{Y = ((X))-(XX) h(x)])
abs (E
E [1 (Y =(()) - ((X)), [XX))
Jabs
[E [1 c(X)) - -(x) ch(X),((X))) 1(X)
(by Jensen's inequality)
[abs (P(Y - x(x) ((x)) - ((x)) [(X)]
Thus,
conf-ECE(e, h)
E [abs (P(Y = c(X) ((X))((()))))))))())) - h(x))]
E E Jabs (P(Y c(X) ((X), h(X)) A(X)Il
E Jabs (P(Y=) = c(x) ((x),(x) -x())]
TL-ECE(C,h) h).
H.2 PROOF OF THEOREM I
The proof strategy is follows. First, we use the bound of Gupta and Ramdas 2021 Theorem 4) (henceforth called the GR21 bound), derived in the binary calibration setting, to conclude marginal, conditional, and ECE guarantees for each hr. Then, we show that the binary guarantees for the individual hy's 's leads to top-label guarantee for the overall predictor (c, h).
Consider any E [L]. Let Pt denote the conditional distribution of (X, [ = 1J) given c(X) = Clearly, Dj is set of nu i.idd. samples from Pt, and fy is learning binary calibrator with respect to Pt using binary histogram binning. The number of data mata-points n, and the number bins is B, |ng/ /] bins. We now apply the GR21 bounds h. First, verify that the condition they require is satisfied:
n k[m/k] 2Br.
34

---

Published as a conference paper at ICLR 2022
Thus their marginal calibration bound for hy gives,
12g(2/a)
x - h2( & 6 |
2( Bi] - 1 (x = >1-a.
Note that since |nz/ hhn/Bil= - |nt/k: > k.
log(2/a)
log (2g(2/))
E1 =1=0+ 6+ 1/ 2(k: - 1)
3 8 + \
2[[mz/ Bi] - 1)
Thus we have
P(IP( = 1 -x,x - (x)1 & E1 |x() = 1) > 1-aa a.
This is satisfied for every 1. Using the law of total probability gives us the top-label marginal cali-
bration guarantee for (c, h):
P([P(Y c(X) c(X)) h(X)) E1)
Σ - (x),, M(X) < ((l() 1)
(law of total probability)
11 e((( = =1:==1,,0 (()x(X)) - hx(x EEl ((x) I)
(by construction, if c(r) = L, h(z) = hı(z))
1(( =1aa.
Similarly, the in-expectation ECE bound of GR21, for 1, gives for every 1
E P| = c(X) = Ix)) - Ix(X) c(X) = || & v Bi B1/2mq +
= v |n/ /k) 22 + 5
& 1/2k + 6.
Thus,
EIP(Y = [xx) - M(X)
P(((X) = () = =1 ((()) = 1, 1,,(()) - hx(x)) c(X)= =
P(c(X)= = 111k 6))
/ 1/2k 6.
Next, show the top-label conditional calibration bound. Let B = Σ Bi and a; aBi/ B. Note that < Dا_ ni/k k = n/k. The binary conditional calibration bound of GR21 gives
log(2B:/au))
p Vr Range(hu), IP(Y (P / ((x) (,14(x) - 6
2([n Bi] -1) [(() =
- aq.
Note that
log(2Bi/ou) 2([ng/ Bi] 11
log(2B/a)
2([n// Br] 1)
35

---

Published as a conference paper at ICLR 2022
log(2n/ ko)) 2([m Bi]
(since B & n/k)
log( 2m/kaa)
(since Ao < B.n/B.I).
2(k
Thus for every I [T].
on. By construction of h, conditioning on c(X) = and (x) = r is the same as conditioning on
P(vr Range(hi), = (XX
= -|
c(X) I and h(X) Taking union bound over all L gives
P(vl E [L]] r E Range(h), IP(Y = c() ((X) = 1, = r) -r) x E2)
1 Σ = 11-a
proving the conditional calibration result. Finally, note that if for every 1 e [L], re Range(h),
IP(Y c(X) c(X) ((X r) - rl & 62,
then also
TL-ECE(c, h) P(Y c(X) ((X), h(X)l < E2.
This proves the high- high-probability bound for the TL-ECE.
Remark 3. Gupta and Ramdas (2021) I proved more general result for general ED-ECE bounds.
Similar results can also derived for the suitably defined E Tp-TL-ECE. Additionally, can be shown that with probability 1 - a. the TL-MCE of (c, h) is bounded by 52. (TL-MCE is defined in Ap-
pendix E. equation 17
H.3 PROOF OF PROPOSITION
Consider a specific E [L]. We use hy to denote the 1-th component function of h and Y =
1(Y = 1). Canonical calibration implies
P(Y / h(X)) E [Y h(X)] lx(X).
(23)
We can then use the law of iterated expectations (or tower rule) to get the final result:
E [ hx(X)]
E [ [Y h(X)] (X)]
E [lr(X) {x())
(by the canonical calibration property 23
hx(X).
H.4 PROOF OF THEBREM 2
We use the bounds of Gupta and Ramdas 2021 Theorem 4) (henceforth called the GR21 bounds), derived in the binary calibration setting, to conclude marginal, conditional, and ECE guarantees for each h4. This leads to the class-wise results as well.
Consider any E [L]. Let P: denote the distribution of (X, 1 (Y 1}). Clearly, D; is a set of n i.i.d samples from Pt, and by is learning a binary calibrator with respect to Pt using binary histogram binning. The number of data-points is n and the number of bins is B₁ [n/k]] bins. We now apply the GR21 1 bounds on h4. First, we verify that the condition they require satisfied:
ky In/k| 2 2B,
Thus the GR21 marginal calibration bound gives that for every E [L]. by satisfies
P (IPCY = (x())) -x( <
(gg(2/a))
> 1 on.
2(nn/ Bi] -1)
36

---

Published as a conference paper at ICLR 2022
The class wise marginal calibration bound of Theorem 2 follows since |n/Bi] |n/ In/kall ki and so
log(2/ar) 2([n// Bi] - 1)
8 +
Next, the GR21 conditional calibration bound gives for every [L]. hy satisfies
(2g(2 2([n/ [:] 1)
p Vr E Range(hi), P(Y (x) =)) - 6
3 1 at.
The Blasswwise marginal calibration bound of Theorem follows since Bi [n/ki] & n/k and nn/ Bi| /n/ |n/kal > k, and so
log( log(2B//ar) 2([n/ Bi| 1)
8+
Let m hy. The in-expectation ECE bound of GR21, for = 1, gives for every I
E [bbinay-EEE--or--caee (hi) v B1/2n4 + 5
VIn/kul //l /2n + 5
V 1/2kg +
V 1/2k + 6.
Thus,
(CW-ECE(ch)) = L
Dinary-ECE-for-classs (hi)
(V 1/2k + 8)
11/2k + 8,
as required for the in-expectation CW-ECE bound of Theorem 2 Finally, for the high probability CW-ECE bound, let max (2) and ΣL ar. By taking union bound over the the conditional calibration bounds for each h,, we have, with probability 1 - a. for every / E [4] and r e Rhnge(h),
|P(Y - = r) - rl <
c
E..
Thus, with probability 1 1 o,
CW-ECE(C, h) L-1 Σ P(Y = hx()) - 1x(x)1 & E.
This proves the high-probability bound for the CW-ECE.
37


Reviews:
[{"review_id": "ZtKECqIuld", "reviewer": "Reviewer_NPUy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a pretty dense paper that contains a lot of material, but it is very well written. I do not consider myself an expert on the topic, but I could follow the flow of the paper quite well. \n\nThe authors have been able to convince me of the disadvantages of confidence calibration, and the advantages of the method they introduce. To this end, Example 1 and the case study in Figure 1 really helped. The experimental results also seem to support the claims of the authors. From a more conceptual perspective, the proposed algorithms are also appealing. \n\nHowever, I do see potential problems with the approach of the authors for classification problems with infrequent classes, like in extreme multi-class classification, where long-tail classes have very few observations. In such situations, confidence calibration will probably work much better, as one doesn't have to condition for rare classes. Conversely, for the approach of the authors, one needs much more observations per class. So, in this regard, the experiments are currently somewhat limited, and probably telling a too optimistic story. I would have liked to see some experiments with extreme classification datasets that have long-tail class distributions. ", "summary_of_the_paper": "This paper discusses the topic of classifier calibration in multi-class classification. The focus is on obtaining well-calibrated probabilities for the top-predicted classes. The authors give arguments, examples and experimental results to show that the commonly-used confidence calibration method suffers a number of shortcomings that makes it less useful in practice. As an alternative, top-label calibration is proposed, where calibration is analyzed on a per-class basis, when a specific class is the top class. \n\nIn addition, the authors discuss shortcomings of confidence reliability diagrams, and they propose multi-class to binary reductions for achieving top-label calibration. In the experiments several methods are compared on two classical image classification benchmarks.  ", "summary_of_the_review": "Interesting and well-motivated idea. Datasets in the experiments are quite simple. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "T5yH4xKy-lo", "reviewer": "Reviewer_8zku", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The paper makes a convincing argument that on an individual level, confidence calibration may be misguided while their definition makes more sense. It is also true that a natural algorithm to achieve many notions of multi-label calibration is to reduce it to the binary case, as the paper suggests.\nWeaknesses: I think the definition also has obvious drawbacks that the authors do not discuss. In particular I am not convinced that calibrating only the top label makes sense. In practice it just means that you partition the data by the top label and then calibrate each partition separately (as the algorithm they suggest effectively does). The predictions outside the top label make no difference. It should be noted that satisfying this requirement is very easy. Pick the most common label and assign to all points the expectation of that label. Thus, the point of calibration is to do it to an existing classifier *with out* sacrificing other good properties such as loss minimization. Since the top label doesn't change by the calibrator the accuracy is unchanged, but the typical loss function for multi-class is cross entropy. \n\nDetailed comments:\n- Please explain better why calibrating only the top label is sufficient. Typically we assume that c(x) returns a vector of probabilities of dimension L, not just the top label out of the L.\n- At the beginning of section 2, please define confidence better. The arg max of the expression is a class (a number in [L]), not a pair (c,h), so the definition is confusing. \n- I am not very familiar with confidence calibration as is defined here, but it must have some good properties no? Please discuss them and contrast with your definition as well.\n- I'm not sure I fully understand the contribution of Section 3. Sure, some notions are reductions from binary classifiers, so lend themselves to be computed via binary calibrators. Is there anything more you can say? (for instance, is error being compounded?, is loss minimization being affected? are there computational tradeoffs?).\n- In table 2 and 3 it is worth noting that scaling algorithms are not designed to bring down ECE or TL ECE.", "summary_of_the_paper": "The paper suggests a definition for calibration in the multi-class setting named 'top label calibration'. The idea is to have only the most likely class calibrated. The small difference with previous definitions is that instead of conditioning only only the confidence value, the conditioning here is also on the identity of the class. The authors argue convincingly that this conditioning renders the definition more meaningful. \nThe authors then observe that many definitions for multi-class calibration could be reduced to multiple instances of binary calibration and suggest an algorithmic framework where a binary calibrator is used as a black box to achieve the multi class calibrator. They then test this by instantiating it with histogram binning and measuring the corresponding notion of expected calibration error.", "summary_of_the_review": "The provides a variation over  confidence calibration that takes into account the identity of the top label. This variation makes sense under some scenarios, but is still a quite a weak notion on its own. While it's an interesting notion to discuss, I think the contributions of the paper are too thin to justify publications.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "T4kKfFIfCLd", "reviewer": "Reviewer_xjQt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The first seven pages of the paper are very nice, and I very much enjoyed reading this material. The problems start with the experiments:\n\n1) Reading through the appendix, the authors are obviously aware that a calibration set is normally used to calibrate a model, before it is evaluated on the test set to compute ECE. However, there is no reference to how this is done for the experiments in the paper, which are based on pre-trained models. It seems that the validation set was perhaps used for both building the discretization-based calibration models and their evaluation, which seems highly problematic.\n\n2) One of the three empirical observations on Page 9 states that the new TL-HB is the best performing method for 1-vs-rest ECE. In fact, it is the un-normalized variant of 1-vs-rest calibration that is shown in Table 3 and that performs best! Assuming this is just a typo and \"TL-HB\" in Observation (c) was meant to be \"CW-HB\", this is the most surprising and potentially most impactful finding in the paper. (The other two observations are about the behaviour wrt TL-ECE/MCE, which are the new, less obvious ECE metrics, and the results are also more mixed wrt these metrics.) However, there is no analysis at all in the paper why leaving out normalization in the 1-vs rest method (CW-HB) is so much better than using it (N-EB)!\n\n3) There is no comparison to isotonic regression, which is trivially applied using the 1-vs-rest method, and like binning, is also a non-parameteric method. The scaling-based methods are all parameteric.\n\n4) The number of datasets is very limited (CIFAR-10 and CIFAR-100).\n\n5) The actual 1-vs-rest discretization-based calibration algorithm used in the paper (CW-HB) seems non-standard because a separate binning is applied for each class (see Algorithm 9 in Appendix C.1, assuming that Binary-histogram-binning performs equal-frequency binning as indicated elsewhere in the paper). My understanding is that normally, the same bin boundaries are used for all classes when this method is applied. The effect of this is unclear. Could it explain why normalization performs so poorly in Table 3?\n\nThe submission describes the discretization-based algorithms being evaluated as special instances of a general M2B \"notion\" for calibration of multi-class problems, and there is a corresponding \"general-purpose\" calibration algorithm that includes the evaluated algorithms as special cases. It is unclear how helpful this algorithm and the M2B \"notion\" are. This aspect of the paper seems somewhat trivial. There are no results or proofs regarding this general-purpose formulation of the algorithm.\n\nLonger and longer appendices seem to be becoming the norm, but this submission is quite extreme in this regard, particularly because only some appendices are referred to in the main text (G, A, D.3, D.2, D.4, D.5, B, D.1) while others aren't: E (random forest experiments, extend Appendix B.2), C (CW-HB), F (canonical multi-class calibration, 8 pages). The role of appendix F in particular is mysterious: it is only tangentially related to what is presented in the main text. \n\nOther questions and comments: \n\n- Do the calibrated probabilities obtained using top-label calibration sum to 1?\n\n- \"However, the distribution of $g$ can be different for different labels, thus they should be treated differently\" -- I don't understand the reason for having this sentence here. Is this to reinforce that point? I would delete it.\n\n- Renumber the algorithms to follow the order in which they are discussed.\n\n- \"the expectation is over the calibration data\" - isn't it trivial to fit the calibration data arbitrarily well? Why is this bound useful then?\n\n- Is N-HB defined in the text or just in the caption?\n\n- Why is CW-HB not included in Table 2? Is it obvious that it performs worse than TL-HB for these metrics? Conversely, doesn't it make sense to include TL-HB in Table 3?", "summary_of_the_paper": "The paper proposes a new method to fix confidence calibration by conditioning on the predicted label when formulating the calibration task (as well as on the class probability estimate for that label, as done in confidence calibration). This new approach is called \"top-label\" calibration. The paper shows how to modify the calibration process to achieve this by building a separate calibration model for each predicted class value. Experiments compare this approach, using binning as the calibration method, to confidence calibration as well as standard 1-vs-rest calibration (both with and without normalization in the latter method) based on calibration of pre-trained CIFAR-10/100 CNNs. Temperature scaling, vector scaling, and Dirichlet scaling are also included. Evaluation is performed using 1-vs-rest ECE, a new top-label ECE, and a maximum calibration error (MCE) variant of the latter. Surprisingly, the proposed approach does not perform as well as 1-vs-rest calibration when using the top-label variant of ECE; it does perform a lot better wrt the MCE variant on the CIFAR-10 data though. When considering 1-vs-rest ECE, the paper reports that 1-vs-rest *without* normalization performs better than the same approach with normalization, and also better than all scaling-based methods. The paper also explains how to adapt top-K-confidence calibration to obtain top-K-label calibration, but this is not evaluated.", "summary_of_the_review": "There are several problems with the empirical evaluation and the analysis. The submission (including the many appendices) also seems heavily overloaded, to the point that the main message becomes quite unclear.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6FIiJXDbmYX", "reviewer": "Reviewer_ZncC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is very well written, tackles an interesting area, proposes a novel calibration, and demonstrates the utility in empirical experiments.\n\nStrengths:\n\n- The proposed calibration results in a more intuitive interpretation than previous approaches and the authors argue so convincingly.\n- Matching calibration algorithms and metrics places everything into a nice framework, and the experiments demonstrate clearly the value of matching the algrithm and metric.\n- Histogram binning, within the appropriate algorithm, is shown to be a competitive post-hoc calibration technique.\n\nWeaknesses:\n\n- Only histogram binning is considered, though there are other post-hoc calibration methods that clearly fit in the algorithms described. It would have been good to see some results, or at least a discussion.", "summary_of_the_paper": "The authors consider the problem of calibrated probabilistic outputs for multiclass classifiers. They consider the various types of calibrations previously studied, such as confidence calibration and class-wise calibration, and then propose a novel notion of calibration based on the choice of top-labels.", "summary_of_the_review": "Excellent paper with good results and clear practical applications. The work is also well placed within existing literature.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of multi-class calibration, proposing new notion of "top-label calibration", and presenting and comparing new algorithms for multi-class calibration. Reviewers generally found the paper to be well-written, and tackling a foundational problem. There were some questions regarding the experiments:

(1) _Lack of explanation of why unnormalised beats normalised._ One of the paper's main empirical findings is that using an unnormalised predictor with histogram binning (CW-HB) can significantly outperform a normalised one (N-HB). There is however limited discussion prior to this of why such behaviour is expected.

(2) _Lack of comparison to isotonic regression._ One can apply isotonic regression in conjunction with one of the M2B algorithms in Sec 3. It is of interest whether isotonic regression + a suitable M2B wrapper compares to HB + an M2B wrapper.

(3) _Comparison to OVA calibration_. One reviewer raised the concern that the new algorithms proposed in this work are not too surprising; e.g., using a binary calibrator of one label vs everyone else appears natural.

(4) _Overloaded appendices_. One reviewer pointed out that some material in the Appendix is not referenced in the body, thus making the work not self-contained.

For point (1), the response indicates that the unnormalised model can obtain distribution-free guarantees. The lack of such a guarantee for the normalised model does not suggest that such a guarantee is impossible, however. Certainly the present work need not solve this issue in entirety, but if this is intended to be a main takeaway of the experiments, a little more discussion in the body seems advisable. 

On this note, from my reading, the experiments seek to demonstrate that suitable M2B reductions can dramatically improve the performance of HB. However, with the use of multiple evaluation metrics (Top-ECE, Top-MCE, Classwise-ECE) it is not clear if the authors intend to promote one specific M2B reduction as generally favourable; further, the text in Sec 3.2 suggests that N-HB is the method considered in prior works, which then seems to do better on top-label ECE than prior works. Which suggests that for this particular metric, one does not gain much from other M2B reductions?

For point (2), the response argued that "the main message of the paper is not about HB vs other binary calibrators, but proposing a single agnostic framework for achieving multiple notions of multiclass calibration using any binary calibrator". From my reading of the paper, I think this claim is accurate, and agree that the conceptual advance is the generic M2B framework itself

For point (3), the authors responded to suggest that while Algorithm 2 performs a natural one-versus-all calibration, this is different from Algorithm 1. Further, the latter is shown to be useful in Table 2 (bottom panel).

For point (4), the revision involved referencing relevant material in the Appendix. These seem better, though I would prefer if theorem statements (e.g., Theorem 1) appear in full or as sketches in the body.

Further to the above, I have a couple of minor suggestions:
- consider removing most hline's from Tables 1 -- 3

- keep the ordering of Algorithms 1 -- 4 the same as that in which methods are presented in Table 1.

**Summary**. The paper considers a foundational problem. It makes one simple yet interesting contribution in its definition of top-label calibration. Detailing the various multi-class calibrators in Section 3 is another contribution: albeit simple, it does illuminate the subtle issue of the role of normalisation in post-hoc calibration, which empirically is shown to have non-trivial impact. There are certainly avenues where the paper could be further strengthened, but overall I do see it as potentially being of broad interest to the community, and inspiring future work. My recommendation is thus for the authors to further incorporate the reviewers' detailed suggestions and the comments above, which can broaden the clarity, scope and impact of the work.
Decision: Accept (Poster)