Year: 2021

Abstract:
We investigate the relationship between commonly considered notions of multiclass calibration and the calibration algorithms used to achieve these notions, leading to two broad contributions. First, we propose a new and arguably natural notion of top-label calibration, which requires the reported probability of the most likely label to be calibrated. Along the way, we highlight certain philosophical issues with the closely related and popular notion of confidence calibration. Second, we outline general ‘wrapper’ multiclass-to-binary (M2B) algorithms that can be used to achieve confidence, top-label, and class-wise calibration, using underlying binary calibration routines. Our wrappers can also be generalized to other notions of calibration, if required for certain practical applications. We instantiate these wrappers with the binary histogram binning (HB) algorithm, and show that the overall procedure has distribution-free calibration guarantees. In an empirical evaluation, we find that with the right M2B wrapper, HB performs significantly better than other calibration approaches.

heading: 1 INTRODUCTION
text: Machine learning models often make probabilistic predictions over the output value, with the ideal goal being to learn the true probability distribution of the output given the input. However, nature never reveals true probability distributions, making it infeasible to achieve this ideal goal in most practical situations. Instead, there is significant interest in the ML community on designing models that achieve the simpler goal of being calibrated. Consider the problem of predicting the probability of rain. When a meteorologist claims that the probability of rain on a particular day is 0.7, we cannot actually test if 0.7 was the ‘true probability of rain’ without making unverifiable assumptions (Dawid, 1982). However, we can test if the meteorologist is calibrated by requiring that on the D days when 0.7 is predicted, it indeed rained on roughly 0.7D of those days (and the same is true for other probabilities). Arguably, a calibrated meteorologist is more interpretable than an uncalibrated one — in the same sense, an ML classification model is arguably more interpretable if the probabilistic predictions it makes for the classes are calibrated (Platt, 1999; Zadrozny and Elkan, 2001; Niculescu-Mizil and Caruana, 2005).
The rain-prediction example is readily converted into a formal notion of calibration for binary classification. Denote a random (feature, label)-pair as pX,Y q P X ˆt0, 1u. A predictor h : X Ñ r0, 1s is said to be calibrated if PrpY “ 1 | hpXq “ qq “ q for every q P r0, 1s (almost surely). If the output is multiclass, Y P rLs :“ t1, 2, . . . , L ě 3u, we consider the calibration of a multi-dimensional predictor h that makes predictions in the pL´1q-dimensional probability simplex: h : X Ñ ∆L´1. The natural extension of binary calibration yields that h is calibrated if PrpY “ l | hpXq “ qq “ ql for every l P rLs, where ql denotes the l’th component of q. However, this notion of calibration becomes infeasible to achieve or verify once L is even 4 or 5 (Vaicenavicius et al., 2019). Thus a number of relaxations of this notion have become popular in the ML literature: confidence calibration (Guo et al., 2017), class-wise calibration (Kull et al., 2017), and extensions of these such as thresholded-class-wise calibration (Nixon et al., 2020) and top-K confidence calibration (Gupta et al., 2021). Each of these relaxations assess predictors by focusing on one or more binary calibration claims. In our work, we dig deeper into what these notions of multiclass calibration mean in terms of the associated probabilistic claim they are verifying. Our study leads us to a new notion of calibration — top-label calibration — and novel calibration algorithms (henceforth called ‘calibrators’) for achieving multiclass calibration. A summary of our contributions is below:
(a) In Section 2, we demonstrate that while confidence calibration is a simple and popular onedimensional view of calibration, it does not lead to a practically meaningful claim. Our proposed notion of top-label calibration corresponds to a subtle but critical change to confidence calibration that rectifies this issue. In contrast to all previous works that have proposed to fix confidence calibration by optimizing the full calibration vector (Kull et al., 2019; Nixon et al., 2020; Kumar et al., 2019; Zadrozny and Elkan, 2002; Vaicenavicius et al., 2019; Widmann et al., 2019), our work continues to advocate for calibrating probabilities only for the top predicted class.
(b) In Section 3, we show that most popular notions of multiclass calibration internally verify binary calibration claims. We characterize these as ‘multiclass-to-binary’ or ‘M2B’ notions. The benefit of this characterization is that for any M2B notion of calibration, a unique customized M2B calibrator can be designed that is specifically tuned to the given notion.
(c) In Section 4, we instantiate the M2B approach using the binary calibration algorithm of histogram binning (Zadrozny and Elkan, 2001; Gupta and Ramdas, 2021). We show that histogram binning, when used with the right M2B wrapper, (i) allows for strong theoretical guarantees without distributional assumptions, and (ii) achieves state-of-the-art results with respect to certain standard notions of calibration error.
We briefly note that identifying the right notion of calibration (i.e. practically useful, philosophically meaningful, and statistically tractable) is also an important problem for structured output spaces (Kuleshov et al., 2018; Gneiting et al., 2007). While this paper is entirely in the multiclass setting, our ideas have implications for identifying the right notion of calibration for other output spaces.

heading: 2 MODIFYING CONFIDENCE CALIBRATION TO TOP-LABEL CALIBRATION
text: A commonly used notion of calibration in multiclass classification settings is confidence calibration, a simple ‘one-dimensional’ reduction to binary calibration proposed by Guo et al. (2017). For the rest of this paper, we use P for the data-generating distribution over X ˆ rLs, and we denote a random point from this distribution as pX,Y q „ P . Let c : X Ñ rLs denote a classifier or ‘toplabel predictor’ and h : X Ñ r0, 1s a function that provides a confidence or probability score for the top-label cpXq. The predictor pc, hq is said to be confidence calibrated (for P ) if (confidence calibration) P pY “ cpXq | hpXqq “ hpXq. (1) In other words, when the reported confidence hpXq equals p P r0, 1s, then the fraction of instances where the predicted label is correct also approximately equals p. Note that for an L-dimensional predictor h : X Ñ ∆L´1, one would use cp¨q “ arg maxlPrLs hlp¨q and hp¨q “ hcp¨qp¨q; ties are broken arbitrarily. Then h is confidence calibrated if the corresponding pc, hq satisfies (1). Confidence calibration is most applicable in high-accuracy settings where we trust the label prediction cpxq. For instance, if a high-accuracy cancer-grade-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 intrusive treatment. However, we may want to know (and control) the number of non-grade-III patients that were given this suggestion incorrectly. In other words, is Prpcancer is not grade III | cancer is predicted to be of grade III with confidence 95%q equal to 5%? Confidence calibration attempts to capture this intuition by focusing on the the probability of the predicted label.
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 (1) into words, we ascertain that confidence calibration leads to guarantees of the form: “if the confidence hpXq in the top-label is 0.6, then the accuracy (frequency with which Y equals cpXq) is 0.6”. How useful is such a guarantee?
Not very useful. Suppose a patient P is informed (based on their symptoms X), they are most likely to have a certain disease D with probability 0.6. Further patient P is told that this score is confidence calibrated. Based on the previous paragraph, 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, P 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 D 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.
Example 1. Suppose the instance space is pX,Y q P ta, bu ˆ t1, 2, . . .u. (X can be seen as the random patient, and Y as the disease they are suffering from.) Consider a predictor pc, hq and let the values taken by pX,Y, c, hq be as follows:
Feature x P pX “ xq Class prediction cpxq Confidence hpxq P pY “ cpXq | X “ xq a 0.5 1 0.6 0.2 b 0.5 2 0.6 1.0
The table specifies only the probabilities P pY “ cpXq | X “ xq; the probabilities P pY “ l | X “ xq for l ‰ cpxq can be set arbitrarily. We verify that pc, hq is perfectly confidence calibrated: P pY “ cpXq | hpXq “ 0.6q “ 0.5pP pY “ 1 | X “ aq ` P pY “ 2 | X “ bqq “ 0.5p0.2` 1q “ 0.6. However, whether the actual practical instance is X “ a or X “ b, the probabilistic claim of 0.6 bears no correspondence with reality. If X “ a, hpXq “ 0.6 is extremely overconfident since P pY “ 1 | X “ aq “ 0.2. On the other hand, if X “ b, hpXq “ 0.6 is extremely underconfident since P pY “ 1 | X “ bq “ 1.0. The reason for the strange behavior above is that the probability P pY “ cpXq | hpXqq is not interpretable from a decision-making perspective. In practice, we never report just the confidence hpXq, but also the class prediction cpXq (obviously!). Thus it is more reasonable to talk about the conditional probability of Y “ cpXq, given what we know, that is both cpXq and hpXq. Thus, we make a small but critical change to (1); we say that pc, hq is top-label calibrated if
(top-label calibration) P pY “ cpXq | hpXq, cpXqq “ hpXq. (2) (See the disambiguating Remark 2 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) are predicted to have disease D with probability 0.6, the fraction who actually have disease D is also 0.6.” Philosophically, it makes perfect sense to condition on what is reported — both the top label and its confidence — because that is what is known to 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 a model is the expected-calibrationerror (ECE) metric. The ECE associated with confidence calibration is defined as
conf-ECEpc, hq :“ EX |P pY “ cpXq | hpXqq ´ hpXq| . (3) We define top-label-ECE (TL-ECE) in an analogous fashion, but also condition on cpXq:
TL-ECEpc, hq :“ EX |P pY “ cpXq | cpXq, hpXqq ´ hpXq| . (4) Higher values of ECE indicate worse calibration performance. The predictor in Example 1 has conf-ECEpc, hq “ 0. However, it has TL-ECEpc, hq “ 0.4, revealing its miscalibration. More generally, it can be deduced as a straightforward consequence of Jensen’s inequality that conf-ECEpc, hq is always smaller than the TL-ECEpc, hq (see Proposition 4 in Appendix G). As illustrated by Example 1, the difference can be significant. In the following subsection we illustrate that the difference can be significant on a real dataset as well. First, we make a couple of remarks. Remark 1 (ECE estimation using binning). Estimating the ECE requires estimating probabilities conditional on some prediction such as hpxq. A common strategy to do this is to ‘bin’ together nearby values of hpxq using binning schemes (Nixon et al., 2020, Section 2.1), and compute a single estimate for the predicted and true probability using all the points in a bin. The calibration method we espouse in this work is histogram binning (HB), a method whose output is already discrete and does not require 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). It is commonly understood that binning leads to underestimation of the effective ECE (Vaicenavicius et al., 2019; Kumar et al., 2019). Thus, using unbinned ECE estimates for HB gives HB a disadvantage compared to the binned ECE estimates we use for other methods. (This further strengthens our positive results for HB.) The binning scheme we use is equal-width binning, where the interval r0, 1s is divided into B equal-width intervals. Equal-width binning typically leads to lower ECE estimates compared to adaptive-width binning (Nixon et al., 2020). Remark 2 (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 ‘top-label-ECE’ (Kumar et 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.
(a) Confidence reliability diagram (points marked ‹) and top-label reliability diagram (points marked `) for a 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 1a for bin 6 (top) and bin 10 (bottom); see further details in point (c) below. The ‹ markers are in the same position as Figure 1a, and denote the average predicted and true probabilities. The colored points denote the predicted and true probabilities when seen class-wise. The histograms on the right show the number of test points per class within bins 6 and 10.
Figure 1: Confidence reliability diagrams misrepresent the effective miscalibration.

heading: 2.1 AN ILLUSTRATIVE EXPERIMENT WITH RESNET-50 ON CIFAR-10
text: We now compare confidence and top-label calibration using ECE estimates and reliability diagrams (Niculescu-Mizil and Caruana, 2005). This experiment can be seen as a less malignant version of Example 1, where confidence calibration is not completely meaningless, but can nevertheless be misleading. Figure 1 illustrates the (test-time) calibration performance of a ResNet-50 model (He et al., 2016) on the CIFAR-10 dataset (Krizhevsky, 2009). In the following summarizing points, the pc, hq correspond to the ResNet-50 model. (a) The ‹ markers in Figure 1a form the confidence reliability diagram (Guo et al., 2017), con-
structed as follows. First, the hpxq values on the test set are ‘binned’ into one of B “ 10 bins, r0, 0.1q, r0.1, 0.2q, . . . , r0.9, 1s, depending on the interval to which hpxq belongs. The gray bars in Figure 1a indicate the fraction of hpxq values in each bin — nearly 92% points belong to bin r0.9, 1s and no points belong to bin r0, 0.1q. Next, for every bin b, we plot ‹ “ pconfb, accbq, which are the plugin estimates of E rhpXq | hpXq P Bin bs and P pY “ cpXq | hpXq P Bin bq respectively. The dashed X “ Y line indicates perfect confidence calibration.
(b) The ` markers in Figure 1a 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 l and bin b, define
∆b,l :“ | pP pY “ cpXq | cpXq “ l, hpXq P Bin bq ´ pE rhpXq | cpXq “ l, hpXq P Bin bs |,
where pP , pE denote empirical estimates based on the test data. The overall miscalibration is then
∆b :“ Weighted-averagep∆b,lq “ ř lPrLs pP pcpXq “ l | hpXq P Bin bq ∆b,l.
Note that ∆b is always non-negative and does not indicate whether the overall miscalibration occurs due to under- or over-confidence; also, if the absolute-values were dropped from ∆b,l, then ∆b would simply equal accb´ confb. In order to plot ∆b in a reliability diagram, we obtain the direction for the corresponding point from the confidence reliability diagram. Thus for every ‹ “ pconfb, accbq, we plot` “ pconfb, confb`∆bq if accb ą confb and` “ pconfb, confb´∆bq otherwise, for every b. This scatter plot of the `’s gives us the top-label reliability diagram. Figure 1a 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 1b zooms into the sixth bin (hpXq P r0.5, 0.6q) and bin 10 (hpXq P r0.9, 1.0s), as described next.
(c) Figure 1b displays the class-wise top-label reliability diagrams for bins 6 and 10. Note that for bin 6, the ‹ marker is nearly on theX “ Y line, indicating that the overall accuracy matches the
0.005
0.010
0.015
0.020
0.025
Es tim
at ed
E CE
Base model top-label-ECE Base model conf-ECE

heading: Temperature scaling top-label-ECE
text: Temperature scaling conf-ECE
Histogram binning top-label-ECE Histogram binning conf-ECE
5 10 15 20 25 Number of bins
0.0075
0.0100
0.0125
0.0150
0.0175
0.0200
0.0225
0.0250
0.0275
Es tim
at ed
E CE
ResNet-50
5 10 15 20 25 Number of bins
0.005
0.010
0.015
0.020
0.025
0.030
Es tim
at ed
E CE
ResNet-110
5 10 15 20 25 Number of bins
0.005
0.010
0.015
0.020
0.025
Es tim
at ed
E CE
Wide-ResNet-26-10
5 10 15 20 25 Number of bins
0.005
0.010
0.015
0.020
0.025
0.030
Es tim
at ed
E CE
DenseNet-121
Figure 2 displays the aggregate effect of the above phenomenon (across bins and classes) through estimates of the conf-ECE and TL-ECE. The precise experimental setup is described in Section 4. These plots display the ECE estimates of the base model, as well as the base model when recalibrated using temperature scaling (Guo et al., 2017) 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 valueB P r5, 25s in order to 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 are 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 it is common to compare predictors based on the conf-ECE, the TL-ECE comparison is more meaningful, and can potentially be different.

heading: 3 CALIBRATION ALGORITHMS FROM CALIBRATION METRICS
text: In this section, we characterize a number of notions of multiclass calibration as ‘Multiclass-tobinary’ (or M2B) notions, and propose a general-purpose calibration algorithm that achieves the corresponding M2B notion of calibration. Thus the M2B framework yields multiple novel post-hoc calibration algorithms, each of which is tuned to a specific M2B notion of calibration.

heading: 3.1 MULTICLASS-TO-BINARY (M2B) NOTIONS OF CALIBRATION
text: In Section 2, we defined confidence calibration (1) and top-label calibration (2). 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 h “ ph1, h2, . . . , hLq is said to be class-wise calibrated (Kull et al., 2017) if
(class-wise calibration) @l P rLs, P pY “ l | hlpXqq “ hlpXq. (5)
Another recently proposed notion is top-K confidence calibration (Gupta et al., 2021). For some l P rLs, let cplq : X Ñ rLs denote the l-th highest class prediction, and let hplq : X Ñ rLs denote the confidence associated with it (c “ cp1q and h “ hp1q are special cases). For a given K ď L,
(top-K-confidence calibration) @k P rKs, P pY “ cpkqpXq | hpkqpXqq “ hpkqpXq. (6)
As we did in Section 2 for confidenceÑtop-label, top-K-confidence calibration can be modified to the more interpretable top-K-label calibration by further conditioning on the predicted labels:
(top-K-label calibration) @k P rKs, P pY “ cpkqpXq | hpkqpXq, cpkqpXqq “ hpkqpXq. (7)
We call each of these notions ‘multiclass-to-binary’ or ‘M2B’ notions, since at their core, each of them reduce multiclass calibration to one or more binary calibration requirements. Each binary calibration requirement corresponds to verifying if the distribution of Y , conditioned on some prediction predpXq, satisfies a single binary calibration claim associated with predpXq. Table 1 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 l P rLs, the conditioning is on predpXq “ hlpXq, and a single binary calibration statement is verified: P pY “ l | predpXqq “ hlpXq. The notion of canonical calibration mentioned in the introduction is not an M2B notion. Canonical calibration is discussed in detail in Appendix F. Due to the conditioning on a multi-dimensional 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.

heading: 3.2 ACHIEVING M2B NOTIONS OF CALIBRATION USING M2B CALIBRATORS
text: The M2B framework illustrates how multiclass calibration can typically be viewed via a 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 a fixed ‘pre-learnt’ base model g : X Ñ ∆L´1. The base model g can correspond to a deep-net, a random forest, or any 1-v-all (one-versus-all) binary classification model such as 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 “ pX1, Y1q, pX2, Y2q, . . . , pXn, Ynq P pX ˆ rLsqn, 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 a 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 a signal for improving calibration.
M2B calibrators take the form of ‘wrapper’ methods that work on top of a given binary calibrator. Denote an arbitrary black-box binary calibrator as At0,1u : r0, 1sXˆpXˆt0, 1uq‹ Ñ r0, 1sX , where the first argument is a mapping X Ñ r0, 1s that denotes a (miscalibrated) binary predicor, and the second argument is a calibration data sequence of arbitrary length. The output is a (better calibrated) binary predictor. Examples of At0,1u 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 1 ta “ bu P t0, 1u which takes the value 1 if a “ b, and 0 if a ‰ b. The general formulation of our M2B calibrator is delayed to Appendix A since the description is a 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 1– 3). Each of these calibrators are different from the ‘classical’ M2B calibrator (Algorithm 4) that has been used by Zadrozny and Elkan (2002), Guo et al. (2017), Kull et al. (2019), and most other papers
M2B calibrators: Post-hoc multiclass calibration using binary calibrators
Input in each case: Binary calibrator At0,1u : r0, 1sX ˆ pX ˆ t0, 1uq‹ Ñ r0, 1sX , base multiclass predictor g : X Ñ ∆L´1, calibration data D “ pX1, Y1q, . . . , pXn, Ynq.
Algorithm 1: Top-label calibrator 1 cÐ classifier or top-class based on g; 2 g Ð top-class-probability based on g; 3 for lÐ 1 to L do 4 Dl Ð tpXi,1 tYi “ luq : cpXiq “ lqu; 5 hl Ð At0,1upg,Dlq; 6 end 7 hp¨q Ð hcp¨qp¨q (predict hlpxq if cpxq “ l); 8 return pc, hq;
Algorithm 2: Class-wise calibrator 1 Write g “ pg1, g2, . . . , gLq; 2 for lÐ 1 to L do 3 Dl Ð tpXi,1 tYi “ luq : i P rnsu; 4 hl Ð At0,1upgl,Dlq; 5 end 6 return ph1, h2, . . . , hLq;
Algorithm 3: Confidence calibrator 1 cÐ classifier or top-class based on g; 2 g Ð top-class-probability based on g; 3 D1 Ð tpXi,1 tYi “ cpXiquq : i P rnsu; 4 hÐ At0,1upg,D1q; 5 return pc, hq;
Algorithm 4: Normalized calibrator 1 Write g “ pg1, g2, . . . , gLq; 2 for lÐ 1 to L do 3 Dl Ð tpXi,1 tYi “ luq : i P rnsu; 4 rhl Ð At0,1upgl,Dlq; 5 end 6 Normalize: for every l P rLs, hlp¨q :“ rhlp¨q{ řL k“1
rhkp¨q; 7 return ph1, h2, . . . , hLq;
we are aware of, with the most similar one being Algorithm 2. Top-K-label and top-K-confidence calibrators are also explicitly described in Appendix A (Algorithms 6 and 7).
Top-label calibration requires that for every class l P rLs, P pY “ l | cpXq “ l, hpXqq “ hpXq. Thus, to achieve top-label calibration, we must solve L calibration problems. Algorithm 1 constructs L datasets tDl : l P rLsu (line 4). The features in Dl are the Xi’s for which cpXiq “ l, and the labels are 1 tYi “ lu. Now for every l P rLs, we calibrate g to hl : X Ñ r0, 1s using Dl and any binary calibrator. The final probabilistic predictor is hp¨q “ hcp¨qp¨q (that is, it predicts hlpxq if cpxq “ l). The top-label predictor c does not change in this process. Thus the accuracy of pc, hq is the same as the accuracy of g irrespective of which At0,1u is used. Unlike the top-label calibrator, the confidence calibrator merges all classes together into a single dataset D1 “ Ť
lPrLsDl.
To achieve class-wise calibration, Algorithm 2 also solves L calibration problems, but these correspond to satisfying P pY “ l | hlpXqq “ hlpXq. Unlike top-label calibration, the dataset Dl for class-wise calibration contains all the Xi’s (even if cpXiq ‰ l), and hl is passed to At0,1u instead of h. Also, unlike confidence calibration, Yi is replaced with 1 tYi “ lu instead of 1 tYi “ cpXiqu. The overall process is 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 2, except that there is an additional normalization step (line 6 of Algorithm 4). This normalization was first proposed by Zadrozny and Elkan (2002, Section 5.2), and has been used unaltered by most other works1 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 to 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 class-wise-HB, that achieve strong empirical results and satisfy distribution-free calibration guarantees.
1the 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 a common ‘I-Max’ binning scheme across classes, whereas in Algorithm 2 the predictor hl for each class is learnt completely independently of other classes

heading: 4 EXPERIMENTS: M2B CALIBRATION WITH HISTOGRAM BINNING
text: Histogram binning or HB was proposed by Zadrozny and Elkan (2001) with strong empirical results for binary calibration. The basic idea in the binary version is that the base model g : X Ñ r0, 1s is used to partition the calibration data into a number of ‘bins’ so that each bin has roughly the same number of calibration 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 (2021) showed that HB satisfies strong distribution-free calibration guarantees, which are otherwise impossible for scaling methods (Gupta et al., 2020).
Despite these guarantees and the strong binary calibration performance, studies for multiclass calibration have reported that HB typically performs worse than scaling methods such as temperature scaling (TS), vector scaling (VS), and Dirichlet scaling (DS) (Kull et al., 2019; Roelofs et al., 2020; Guo et al., 2017). TS, VS, and DS are not designed for a specific notion of calibration or ECE. On the other hand HB can be adapted to a given M2B notion using the M2B framework. In this section, we report that with the right M2B wrapper, HB in fact performs better than each of these scaling methods. A few interesting calibrators have been proposed recently (Zhang et al., 2020; Rahimi et 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 even in these papers. We do not compare to these calibrators since our focus is on the M2B reduction. One of the key messages is that the HB baselines reported by most of these papers can be significantly improved with the right M2B reduction.
We use three metrics for comparison: the first is top-label-ECE or TL-ECE (defined in (4)), which we argued leads to a more meaningful comparison compared to conf-ECE. Second, we consider the more stringent maximum-calibration-error (MCE) metric (Guo et al., 2017) that assesses the worst
calibration across predictions (see more details in Appendix D.3). The top-label-MCE is defined: TL-MCEpc, hq :“ max
lPrLs sup rPRangephq |P pY “ l | cpXq “ l, hpXq “ rq ´ r| . (8)
To assess class-wise calibration, we use class-wise-ECE (CW-ECE), defined as, CW-ECEpc,hq :“ L´1
řL l“1 EX |P pY “ l | hlpXqq ´ hlpXq| . (9)
All ECE/MCE estimation is performed as described in Remark 1; see more details in Appendix D.2.
Formal algorithm and theoretical guarantees. Top-label-HB (TL-HB) and class-wise-HB (CWHB) are explicitly stated in Appendices B and C respectively; 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 (2021) to TL-HB (Theorem 1 in App. B) and CW-HB (Theorem 2 in App. C). We informally summarize one of the guarantees shown: if the number of bins are chosen so that there are at least k calibration points-per-bin, then the expected-ECE is bounded as: E r(TL-) or (CW-) ECEs ď a
1{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 and identically distributed test-point pX,Y q. Experimental details. We experimented on the CIFAR-10 and CIFAR-100 datasets, which have 10 and 100 classes each. The base models are deep-nets with the following architectures: ResNet-50, Resnet-110 (He et al., 2016), Wide-ResNet-26-10 (WRN) (Zagoruyko and Komodakis, 2016), 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/validation/test sets. The validation set was used for posthoc calibration 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?” Mukhoti et al. (2020) report that the best performing loss functions while training deep-net are the Brier score and focal loss. We thus used their Brier score and focal loss models in our experiments — all results in the main paper are with Brier score, and results with focal loss are in Appendix D.4. As a sanity check, we verified that our experiments reproduced the exact CW-ECE numbers reported in Table F.2 of their paper (corresponding to columns ‘Brier Loss’ and ‘FLSD-53’). We did not perform any additional tuning, and we have reported more or less all results obtained during our investigations. Implementation details for TS, VS, and DS are in Appendix D. In Appendix B.2, we consider top-label calibration for the class imbalanced COVTYPE-7 dataset, and show that TL-HB adapts to tail/infrequent classes.
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 1) splits datasets across the predicted classes, and some classes in CIFAR-100 occur very rarely. This is further discussed in Appendix D.6.
(b) For TL-MCE, CW-HB is the best performing method on CIFAR-10, by a huge margin. For CIFAR-100, TS or VS perform better than TL-HB, but not by a huge margin. Since HB ensures that each bin gets roughly the same number of points, this ensures that the predictions are somewhat equally calibrated across bins. This is one of the main advantage of using HB, as also discussed by Gupta and Ramdas (2021).
(c) For CW-ECE, CW-HB is the best performing method across the two datasets and all four architectures. The N-HB method which has been used in many CW-ECE baseline experiments performs terribly. In other words, skipping the normalization step leads to a large improvement in CW-ECE. This observation is one of our most striking findings. To shed some light on this, we note that the distribution-free calibration guarantees for CW-HB shown in Appendix C no longer hold post-normalization. Thus, both our theory and experiments indicate that skipping normalization improves CW-ECE performance.
In Appendix D.5, we report each of the results in Tables 2 and 3 with the number of bins taking every value in the range r5, 25s. Most observations remain the same under this expanded study, which further strengthens our conclusions.

heading: 5 REPRODUCIBILITY STATEMENT
text: Some reproducibility desiderata, such as external code and libraries that were used are summarized in Appendix D.1. All code to generate results with the CIFAR datasets is attached in the supplementary material. Our base models were pre-trained deep-net models generated by Mukhoti et al. (2020), obtained from www.robots.ox.ac.uk/„viveka/focal calibration/ (corresponding 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.com/torrvision/focal calibration. To aid reproducibility, we have submitted supplementary material packaged with the prediction matrices (in a ‘data’ folder). However, since the maximum size of the supplementary material was 100MB, we have removed some DenseNet-121 models from the data, and also the corresponding code from the jupyter-notebook for reproducing results. Since the DenseNet-121 numbers are similar to other architectures, this should not affect reproducibility. Upon publication, all code will be publicly released as a github repository.

heading: 6 ETHICS STATEMENT
text: Post-hoc calibration is a 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 limitations. Post-hoc calibration requires keeping aside a fresh, representative dataset, that was not used for training. If this dataset is 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, 2021). A well calibrated classifier is not necessarily an accurate or a fair one, and vice versa (Kleinberg et al., 2017). Deploying calibrated models in critical applications like medicine, criminal law, banking, etc. does not preclude the possibility of the model being frequently wrong or unfair.

heading: A ADDENDUM TO SECTION 3 “CALIBRATION ALGORITHMS FROM CALIBRATION METRICS”
text: In Section 3, we introduced the concept of M2B calibration, and showed that popular calibration notions are in fact M2B notions (Table 1). 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 1. In Appendix A.2, we illustrate the philosophy of M2B calibration using a simple example with a dataset that contains 6 points. This example also illustrates the top-label-calibrator, the classwise-calibrator, and the confidence-calibrator.

heading: A.1 GENERAL-PURPOSE M2B CALIBRATOR
text: Denote some M2B notion of calibration as C. Suppose C corresponds toK binary calibration claims. The outer for-loop in Algorithm 5, runs over each such claim in C. For example, for class-wise calibration, K “ L and for confidence and top-label calibration, K “ 1. Corresponding to each claim, there is a probability-predictor that the conditioning is to be done on, such as g or gl or gpkq. Additionally, there may be conditioning on the label predictor such as c or cpkq. These are denoted as prc, rgq in Algorithm 5. For confidence and top-label calibration, rc “ c, the top-label-confidence. For class-wise calibration, when rg “ gl, we have rcp¨q “ l. If there is no label conditioning in the calibration notion, such as in confidence, top-K-confidence, and class-wise calibration, then we enter the if-condition inside the for-loop. Here hk is learnt using a single calibration dataset and a single call to At0,1u. Otherwise, if there is label conditioning, such as in top-label and top-K-label calibration, we enter the else-condition, where we learn a separate hk,l for every l P rLs, using a different part of the dataset Dl in each case. Then hkpxq equals hk,lpxq if rcpxq “ l. Finally, since C is verifying a sequence of claims, the output of Algorithm 5 is a sequence of predictors. Each original prediction prc, rgq corresponding to the C is replaced with prc, hkq. This is the output of the M2B calibrator. Note that the rc values are not changed. This output appears abstract, but normally, it can be represented in an interpretable way. For example, for class-wise calibration, the output is just a sequence of predictors, one for each class: ph1, h2, . . . , hLq. This general-purpose M2B calibrators can be used to achieve any M2B calibration notion: toplabel calibration (Algorithm 1), class-wise calibration (Algorithm 2), confidence calibration (Algorithm 3), top-K-label calibration (Algorithm 6), and top-K-confidence calibration (Algorithm 7).

heading: A.2 AN EXAMPLE TO ILLUSTRATE THE PHILOSOPHY OF M2B CALIBRATION
text: Figure 3a shows the predictions of a given base model g on a given dataset D. Suppose D is a test set, and we are testing confidence calibration. Then the only predictions that matter are the top-predictions corresponding to the shaded values. These are stripped out and shown in Figure 3b, in the gp¨q row. Note that the indicator 1 tY “ cp¨qu is sufficient to test confidence calibration and given this, the cpXq are not needed. Thus the second row in Figure 3b only shows these indicators.
Algorithm 8: Top-label histogram binning Input: Base multiclass predictor g, calibration data D “ pX1, Y1q, . . . , pXn, Ynq Hyperparameter: # points per bin k P N (say 50), tie-breaking parameter δ ą 0 (say 10´10) Output: Top-label calibrated predictor pc, hq
1 cÐ classifier or top-class based on g; 2 g Ð top-class-probability based on g; 3 for lÐ 1 to L do 4 Dl Ð tpXi,1 tYi “ luq : cpXiq “ lqu and nl Ð |Dl|; 5 hl Ð Binary-histogram-binningpg,Dl, tnl{ku , δq; 6 end 7 hp¨q Ð hcp¨qp¨q; 8 return pc, hq;
Verifying top-label calibration is similar (Figure 3c), but in addition to the predictions gp¨q, we also retain the values of cp¨q. Thus the gp¨q and 1 tY “ cp¨qu are shown, but split across the 4 classes. Class-wise calibration requires access to all the predictions, however, each class is considered separately as indicated by Figure 3d. Canonical calibration looks at the full prediction vector in each case. However, in doing so, it becomes unlikely that gpxq “ gpyq 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 a 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 on the pg,1 tY “ cp¨quq corresponding to g. If top-label calibration is to be achieved, we should use the pc, gq values. If class-wise calibration is to be achieved, we should look at each gl separately and solve L different problems. Finally, for canonical calibration, we must look at the entire g vector as a single unit. This is the core philosophy behind M2B calibrators: if binary claims are being verified, solve binary calibration problems.

heading: B DISTRIBUTION-FREE TOP-LABEL CALIBRATION USING HISTOGRAM BINNING
text: In this section, we formally describe histogram binning (HB) with the top-label-calibrator (Algorithm 1) and provide methodological insights through theory and experiments.

heading: B.1 FORMAL ALGORITHM AND THEORETICAL GUARANTEES
text: Algorithm 8 describes the top-label calibrator formally using HB as the binary calibration algorithm. The function called in line 5 is Algorithm 2 of Gupta and Ramdas (2021). 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 a 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 a more principled way of choosing the number of bins is to fix the number of points per bin. This is parameter k of Algorithm 8. Given k, the number of bins is decided separately for every class as tnl{ku where nl is the number of points predicted as class l. This choice is particularly relevant for top-label calibration since nl can be highly non-uniform (we illustrate this empirically in Section B.2). The tie-breaking parameter δ can be arbitrarily small (like 10´10), and its significance is mostly theoretical—it 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 on a bin; this leads to a cleaner theoretical guarantee.
HB recalibrates g to a piecewise constant function h that takes one value per bin. Consider a specific bin b; the h value for this bin is computed as the average of the indicators t1 tYi “ cpXiqu : Xi P Bin bu. This is an estimate of the ‘bias’ of the bin P pY “ cpXq | X P Bin bq. A concentration inequality can then be used to bound the deviation between the estimate and the true bias to prove distribution-free calibration guarantees. In the forthcoming Theorem 1, we show high-probability and in-expectation bounds on the the TL-ECE of HB. Additionally, we show marginal and condi-
tional top-label calibration bounds, defined next. These notions were proposed in the binary calibration setting by Gupta et al. (2020) and Gupta and Ramdas (2021). In the definition below, A refers to any algorithm that takes as input calibration data D and an initial classifier g to produce a top-label predictor c and an associated probability map h. Algorithm 8 is an example of A. Definition 1 (Marginal and conditional top-label calibration). Let ε, α P p0, 1q be some given levels of approximation and failure respectively. An algorithm A : pg,Dq ÞÑ pc, hq is
(a) pε, αq-marginally top-label calibrated if for every distribution P over X ˆ rLs,
P ´ |P pY “ cpXq | cpXq, hpXqq ´ hpXq| ď ε ¯ ě 1´ α. (10)
(b) pε, αq-conditionally top-label calibrated if for every distribution P over X ˆ rLs,
P ´ @ l P rLs, r P Rangephq, |P pY “ cpXq | cpXq “ l, hpXq “ rq ´ r| ď ε ¯
ě 1´ α. (11)
To clarify, all probabilities are taken over the test point pX,Y q „ P , the calibration data D „ Pn, and any other inherent algorithmic randomness in A; these are all implicit in pc, hq “ ApD,gq. Marginal calibration asserts that with high probability, on average over the distribution of D, X , P pY “ cpXq | cpXq, hpXqq is at most ε away from hpXq. In comparison, TL-ECE is the average of these deviations over X . Marginal calibration may be a 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 is a strictly stronger definition that requires the deviation to be at most ε for every possible prediction pl, rq, 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. Theorem 1. Fix hyperparameters δ ą 0 (arbitrarily small) and points per bin k ě 2, and assume nl ě k for every l P rLs. Then, for any α P p0, 1q, Algorithm 8 is pε1, αq-marginally and pε2, αqconditionally top-label calibrated for
ε1 “
d
logp2{αq 2pk ´ 1q ` δ, and ε2 “
d
logp2n{kαq 2pk ´ 1q ` δ. (12)
Further, for any distribution P over X ˆ rLs, we have P pTL-ECEpc, hq ď ε2q ě 1 ´ α, and E rTL-ECEpc, hqs ď a 1{2k ` δ.
The proof in Appendix G is a multiclass top-label adaption of the guarantee in the binary setting by Gupta and Ramdas (2021). The rOp1{ ? kq dependence of the bound relies on Algorithm 8 delegating at least k points to every bin. Since δ can be chosen to be arbitrarily small, setting k “ 50 gives roughly ED rTL-ECEphqs ď 0.1. Base on this, we suggest setting k P r50, 150s in practice.

heading: B.2 TOP-LABEL HISTOGRAM BINNING ADAPTS TO CLASS IMBALANCED DATASETS
text: The principled methodology of fixing the number of points per bin reaps practical benefits. Figure 4 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 1 and 49% for class 2. The entire dataset has 581012 points which is divided into train-test in the ratio 70:30. Then, 10% of the training points are held out for calibration (n “ |D| “ 40671). 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 top-label 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 E 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, 2021) estimate how the LHS of condition (10), denoted as V pεq, varies with ε. We observe that for all ε, V pεq 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
1 2 3 4 5 6 70.000
0.025
0.050
0.075
0.100
0.125
0.150
0.175
0.200
EC E
Random forest Histogram binning
0.0
0.1
0.2
0.3
0.4
0.5
Cl as
s r at
io
Class ratio
1 2 3 4 5 6 70.000
0.025
0.050
0.075
0.100
0.125
0.150
0.175
0.200
EC E
Random forest Histogram b nning
0.0
0.1
0.2
0.3
0.4
0.5
Cl as
s r at
io
Class ratio
0.00 0.25 0.50 0.75 1.0 Predicted probability
0.0
0.2
0.4
0.6
0.8 1.0 Tr ue p ro ba bi lit y
Class 2 reliability diagram
0.00 0.05 0.10 0.15 0.0
0.2
0.4
0.6
0.8
1.0
V( )
Class 2 validity plot
0.00 0.25 0.50 0.75 1.00 Predicted probability
0.0
0.2
0.4
0.6
0.8
1.0
Tr ue
p ro
ba bi
lit y
Class 4 reliability diagram
0.00 0.05 0.10 0.15 0.0
0.2
0.4
0.6
0.8
1.0
V( )
Class 4 validity plot
1 2 3 4 5 6 7 Class 0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200 To pla be l E CE 0.0 0.1 0.2 0.3 0.4 0.5 Cl as s r at io
(a) Top-label histogram binning (Algorithm 8) with k “ 100 points per bin. Class 4 has only 183 calibration points. Algorithm 8 adapts and uses only a single bin to ensure that the TL-ECE on 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-calibration TL-ECE using binning is quite uniform.
0.00 0.25 0.50 0.75 1.00 Predicted probability
0.0
0.2
0.4
0.6
0.8
1.0
Tr ue
p ro
ba bi
lit y
Class 2 reliability diagram
0.00 0.05 0.10 0.15 0.0
0.2
0.4
0.6
0.8
1.0
V( )
Class 2 validity plot
0.00 0.25 0.50 0.75 1.00 Predicted probability
0.0
0.2
0.4
0.6
0.8
1.0
Tr ue
p ro
ba bi
lit y
Class 4 reliability diagram
0.00 0.05 0.10 0.15 0.0
0.2
0.4
0.6
0.8
1.0
V( )
Class 4 validity plot
1 2 3 4 5 6 7 Class 0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200 To pla be l E CE 0.0 0.1 0.2 0.3 0.4 0.5 Cl as s r at io
(b) Histogram binning with B “ 50 bins for every class. Compared to Figure 4a, the post-calibration 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 a fixed number of calibration points per bin, Algorithm 8 obtains relatively uniform top-label calibration across classes (Figure 4a). In comparison, if a fixed number of bins are chosen for all classes, the performance deteriorates for the least likely classes (Figure 4b).
the less likely classes, HB has a more uniform miscalibration across classes. Figure 4b considers a 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 tnl{ku in line 5 of Algorithm 8 with a fixed B P N). While even in this setting there is a drop in the TL-ECE compared to the RF model, the final profile is less uniform compared to fixing the number of points per bin.
The validity plots and top-label reliability diagrams for all the 7 classes are reported in Figure 9 in Appendix E, along with some additional observations.

heading: C DISTRIBUTION-FREE CLASS-WISE CALIBRATION USING HISTOGRAM BINNING
text: In this section, we formally describe histogram binning (HB) with the class-wise-calibrator (Algorithm 2) and provide theoretical guarantees for it.

heading: C.1 FORMAL ALGORITHM
text: To achieve class-wise calibration using binary routines, we learn each component function hl in a 1- v-all fashion as described in Algorithm 2. Algorithm 9 contains the pseudocode with the underlying routine as binary HB. To learn hl, we use a dataset Dl, which unlike top-label HB (Algorithm 8), contains Xi even if cpXiq ‰ l. However the Yi is replaced with 1 tYi “ lu. The number of points per bin kl can be different for different classes, but generally one would set k1 “ . . . “ kL “ k P N. Larger values of kl will lead to smaller εl and δl in the guarantees, at loss of sharpness since the number of bins tn{klu would be smaller.
Algorithm 9: Class-wise histogram binning Input: Base multiclass predictor g : X Ñ ∆L´1, calibration data D “ pX1, Y1q, . . . , pXn, Ynq Hyperparameter: # points per bin k1, k2, . . . , kl P NL (say each kl “ 50), tie-breaking parameter δ ą 0 (say 10´10) Output: L class-wise calibrated predictors h1, h2, . . . , hL
1 for lÐ 1 to L do 2 Dl Ð tpXi,1 tYi “ luq : i P rnsqu; 3 hl Ð Binary-histogram-binningpgl,Dl, tn{klu , δq; 4 end 5 return ph1, h2, . . . , hLq;

heading: C.2 CALIBRATION GUARANTEES
text: A general algorithm A for class-wise calibration takes as input calibration data D and an initial classifier g to produce an approximately class-wise calibrated predictor h : X Ñ r0, 1sL. Define the notation ε “ pε1, ε2, . . . , εLq P p0, 1qL and α “ pα1, α2, . . . , αLq P p0, 1qL. Definition 2 (Marginal and conditional class-wise calibration). Let ε,α P p0, 1qL be some given levels of approximation and failure respectively. An algorithm A : pg,Dq ÞÑ h is (a) pε,αq-marginally class-wise calibrated if for every distribution P over X ˆ rLs and for every
l P rLs P ´ |P pY “ l | hlpXqq ´ hlpXq| ď εl ¯ ě 1´ αl. (13)
(b) pε,αq-conditionally class-wise calibrated if for every distribution P over X ˆ rLs and for every l P rLs,
P ´ @r P Rangephlq, |P pY “ l | hlpXq “ rq ´ r| ď εl ¯ ě 1´ αl. (14)
Definition 2 requires that each hl is pεl, αlq calibrated in the binary senses defined by Gupta et al. (2021, Definitions 1 and 2). From Definition 2, we can also uniform bounds that hold simultaneously over every l P rLs. Let α “
řL l“1 αl and ε “ maxlPrLs εl. Then (13) implies
P ´ @l P rLs, |P pY “ l | hlpXqq ´ hlpXq| ď ε ¯ ě 1´ α, (15)
and (14) implies
P ´ @l P rLs, r P Rangephlq, |P pY “ l | hlpXq “ rq ´ r| ď ε ¯ ě 1´ α. (16)
The choice of not including the uniformity over L in Definition 2 reveals the nature of our class-wise HB algorithm and the upcoming theoretical guarantees: (a) we learn the hl’s separately for each l and do not combine the learnt functions in any way (such as normalization), (b) we do not combine the calibration inequalities for different rLs in any other way other than a union bound. Thus the only way we can show (15) (or (16)) is by using a union bound over (13) (or (14)).
We now state the distribution-free calibration guarantees satisfied by Algorithm 9. Theorem 2. Fix hyperparameters δ ą 0 (arbitrarily small) and points per bin k1, k2, . . . , kl ě 2, and assume nl ě kl for every l P rLs. Then, for every l P rLs, for any αl P p0, 1q, Algorithm 9 is pεp1q,αq-marginally and pεp2q,αq-conditionally class-wise calibrated with
ε p1q l “
d
logp2{αlq 2pkl ´ 1q ` δ, and εp2ql “
d
logp2n{klαlq 2pkl ´ 1q ` δ. (17)
Further, for any distribution P over X ˆ rLs,
(a) P pCW-ECEpc, hq ď maxlPrLs ε p2q l q ě 1´ ř lPrLs αl, and
(b) E rCW-ECEpc, hqs ď maxlPrLs a 1{2kl ` δ.
Theorem 2 is proved in Appendix G. The proof follows by using the result of Gupta and Ramdas (2021, Theorem 2), derived in the binary calibration setting, for each hl separately.
As discussed in Section 3.2, unlike previous works (Zadrozny and Elkan, 2002; Guo et al., 2017; Kull et al., 2019), Algorithm 9 does not normalize the hl’s. We do not know how to derive Theorem 2 style results for a normalized version of Algorithm 9.

heading: D ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS FOR CIFAR-10 AND
text: CIFAR-100
We present additional details and results to supplement the experiments with CIFAR-10 and CIFAR100 in Sections 2 and 4 of the main paper.

heading: D.1 EXTERNAL LIBRARIES USED
text: All our base models were pre-trained deep-net models generated by Mukhoti et al. (2020), obtained from www.robots.ox.ac.uk/„viveka/focal calibration/ and used along with the code at https://github.com/torrvision/focal calibration to obtain base predictions. 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 D.4, we report corresponding results with focal loss.
We also used the code at https://github.com/torrvision/focal calibration for temperature scaling (TS). For vector scaling (VS) and Dirichlet scaling (DS), we used the code of Kull et al. (2019), hosted at https://github.com/dirichletcal/dirichlet python. For VS, we used the file dirichletcal/calib/vectorscaling.py, and for DS, we used the file dirichletcal/calib/fulldirichlet.py. No hyperparameter tuning was performed in any of our histogram binning experiments or baseline experiments; default settings were used in 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 to test-data peeking across multiple settings.

heading: D.2 FURTHER COMMENTS ON BINNING FOR ECE ESTIMATION
text: As mentioned in Remark 1, ECE estimates for all methods except TL-HB and CW-HB was done using fixed-width bins r0, 1{Bq, r1{B, 2{Bq, . . . r1´ 1{B, 1s for various values of B P r5, 25s. For TL-HB and CW-HB, B is the number of bins used for each call to binary HB. For TL-HB, note that we 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 tnl{ku with B. For CW-HB, we described Algorithm 9 with different values of kl corresponding to the number of bins per class. For the CIFAR-10 and CIFAR-100 comparisons, we set each k1 “ k2 “ . . . “ kL “ k, where k P N satisfies tn{ku “ B. Tables 2,3, 4, and 5 report estimates withB “ 15, which is the ‘standard’ value in many works (Guo et al., 2017; Kull et al., 2019; Mukhoti et al., 2020). Corresponding to each table, we have a figure where ECE estimates with varyingB are reported to strengthen conclusions: these are Figure 5,7, 6, and 8 respectively. Plugin estimates of the ECE were used, same as Guo et al. (2017). Further binning was not done for TL-HB and CW-HB since the output is already discrete and sufficiently many points take each of the predicted values. Note that due to Jensen’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 a disadvantage.

heading: D.3 SOME REMARKS ON MAXIMUM-CALIBRATION-ERROR (MCE)
text: Guo et al. (2017) defined MCE with respect to confidence calibration, as follows:
conf-MCEpc, hq :“ sup rPRangephq |P pY “ cpXq | hpXq “ rq ´ r| . (18)
Conf-MCE suffers from the same issue illustrated in Figure 2 for conf-ECE. In Figure 1b, we looked at the reliability diagram within two bins. These indicate two of the values over which the supremum is taken in equation (18): these are the Y-axis distances between the ‹ markers and the X “ Y 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 to these values across all bins. To remedy the underestimation of the effective MCE, we can consider the top-label-MCE, which was defined in (8) as follows
TL-MCEpc, hq :“ max lPrLs sup rPRangephq |P pY “ l | cpXq “ l, hpXq “ rq ´ r| . (19)
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 as in the proof of Proposition 4, it can be shown that for any c, h, conf-MCEpc, hq ď TL-MCEpc, hq. The TL-MCE is closely related to conditional top-label calibration (Definition 1b). Clearly, an algorithm is pε, αqconditionally top-label calibrated if and only if for every distribution P , P pTL-MCEpc, hq ď εq ě 1´ α. Thus the conditional top-label calibration guarantee of Theorem 1 implies a high probability bound on the TL-MCE as well.

heading: D.4 TABLE 2 AND 3 STYLE RESULTS WITH FOCAL LOSS
text: Results for top-label-ECE and top-label-MCE with the base deep net model being trained using focal loss are reported in Table 4. Corresponding results for class-wise-ECE are reported in Table 5. The observations are similar to the ones reported for Brier score:
1. For TL-ECE, TL-HB is either the best or close to the best performing method on CIFAR10, but suffers on CIFAR-100. This phenomenon is discussed further in Appendix D.6. N-HB is the best or close to the best for both CIFAR-10 and CIFAR-100.
2. For TL-MCE, TL-HB is the best performing method on CIFAR-10, by a 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.

heading: D.5 ECE AND MCE ESTIMATES WITH VARYING NUMBER OF BINS
text: Corresponding to each entry in Tables 2 and 4, we perform an ablation study with the number of bins varying as B P r5, 25s. This is in keeping with the findings of Roelofs et al. (2020) that the
ECE/MCE estimate can vary with different numbers of bins, along with the relative performance of the various models.
The results are reported in Figure 5 (ablation of Table 2) and Figure 7 (ablation of Table 3). The captions of these figures contain further details on the findings. Most findings are similar to those in the main paper, but the findings in the tables are strengthened through this ablation. The same ablations are performed for focal loss as well. The results are reported in Figure 6 (ablation of Table 4) and Figure 8 (ablation of Table 5). The captions of these figures contain further details on the findings. The ablation results in the figures support those in the tables.

heading: D.6 ANALYZING THE POOR PERFORMANCE OF TL-HB ON CIFAR-100
text: CIFAR-100 is an imbalanced dataset with 100 classes and 5000 points for validation/calibration (as per the default splits). Due to random subsampling, the validation split we used had one of the classes predicted as the top-label only 31 times. Thus, based on Theorem 1, we do not expect HB to have small TL-ECE. This is confirmed by the empirical results presented in Tables 2/4, 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 5d/6d). In comparison, for CWECE, CW-HB is 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 in performance of HB when few calibration points are available was also observed in the binary setting by Gupta and Ramdas (2021, Appendix C). Niculescu-Mizil and Caruana (2005) noted in the conclusion of 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 k ě 20.

heading: E ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS FOR COVTYPE-7
text: 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 RandomForestClassifier 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 a fair comparison, instead of having a fixed binning scheme
to assess the base model, the binning scheme was decided based on the unique predictions of toplabel HB. Thus for every l, and r P Rangephlq, the bins are defined as tx : cpxq “ l, hlpxq “ ru. 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 k “ 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 was made on this basis.
Figure 9 supplements Figure 4 in the main paper by presenting reliability diagrams and validity plots of top-label HB for all classes. Figure 9a presents the plots with adaptive number of bins per class (Algorithm 8), and Figure 9b presents these for fixed number of bins per class. We make the following observations.
(a) For every class l P rLs, the RF is overconfident. This may seem surprising at first since we 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 1 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 of 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 8.

heading: F BINNING-BASED CALIBRATORS FOR CANONICAL MULTICLASS CALIBRATION
text: Canonical calibration is a notion of calibration that does not fall in the M2B category. To define canonical calibration, we use Y to denote the output as a 1-hot vector. That is, Yi “ eYi P
∆L´1, where el corresponds to the l-th canonical basis vector in Rd. Recall that a predictor h “ ph1, h2, . . . , hLq is said to be canonically calibrated if P pY “ l | hpXqq “ hlpXq for every l P rLs. Equivalently, this can be stated as E rY | hpXqs “ hpXq. Canonical calibration implies class-wise calibration:
Proposition 1. If E rY | hpXqs “ hpXq, then for every l P rLs, P pY “ l | hlpXqq “ hlpXq.
The proof in Appendix G is straightforward, but the statement above is 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 predpXq “ hpXq, and after this conditioning, each of the L statements P pY “ l | predpXqq “ hlpXq 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 a calibrator for canonical calibration. In this section, we discuss alternative binning-based approaches to achieving canonical calibration.
For binary calibration, there is a complete ordering on the interval r0, 1s, and this ordering is leveraged by binning based calibration algorithms. However, ∆L´1, 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-based calibrators for canonical calibration. Our descriptions are for general L ě 3, but we anticipate these algorithms to work reasonably only for small L, say if L ď 5. As usual, denote g : X Ñ ∆L´1 as the base model and h : X Ñ ∆L´1 as the model learnt using some post-hoc canonical calibrator. For canonical calibration, we can surmise binning schemes that directly learn h by partitioning the prediction space ∆L´1 into bins and estimating the distribution of Y in each bin. A canonical calibration guarantee can be showed for such a binning scheme using multinomial concentration (Podkopaev and Ramdas, 2021, Section 3.1). However, since Volp∆L´1q “ 2ΘpLq, there will either be a bin whose volume is 2ΩpLq (meaning that h would not be sharp), or the number of bins will be 2ΩpLq, entailing 2ΩpLq requirements on 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 ∆L´1 into B ě 1 bins. We denote this binning scheme as B : ∆L´1 Ñ rBs, where Bpsq corresponds to the bin to which s P ∆L´1 belongs. To learn h, the calibration data is binned to get sets of data-point indices that belong to each bin, depending on the gpXiq values:
for every b P rBs, Tb :“ ti : BpgpXiqq “ bu, nb “ |Tb| . We then compute the following estimates for the label probabilities in each bin:
for every pl, bq P rLs ˆ rBs, pΠl,b :“ ř iPTb 1 tYi “ lu nb if nb ą 0 else pΠl,b “ 1{B.
The binning predictor h : X Ñ ∆L´1 is now defined component-wise as follows:
for every l P rLs, hlpxq “ pΠl,Bpxq.
In words, for every bin b P rBs, h predicts the empirical distribution of the Y 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 a result using the Bretagnolle-Huber-Carol inequality. All of these concentration inequality give bounds that depend inversely on nb or ? nb.
In the following subsections, we describe some binning schemes which can be used for canonical calibration based on the setup illustrated above. First we describe fixed schemes that are not adaptive to the distribution of the data: Sierpinski binning (Appendix F.1) and grid-style binning (Appendix F.2). These are analogous to fixed-width binning for L “ 2. Fixed binning schemes are not adapted to the calibration data and may have highly imbalanced bins leading to poor estimation of the distribution of Y in bins with small nb. In the binary case, this issue is remedied using histogram binning to 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 gpXiq values, there is no obvious ordering for the multi-dimensional gpXiq values. In Appendix F.3 we describe a projection based histogram binning scheme that circumvents this issue and ensures that each nb is reasonably large. In Appendix F.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 Nobel, 1996; Gordon and Olshen, 1984; Breiman et al., 2017; Devroye, 1988); further extensive references 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 essentially interested in binning ∆L´1. In terms of theory, the results these works target are asymptotic consistency for the (Bayes) optimal classification and regression functions, instead of canonical calibration. 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.

heading: F.1 SIERPINSKI BINNING
text: First, we describe Sierpinski binning for L “ 3. The probability simplex for L “ 3, ∆2, is a triangle with vertices e1 “ p1, 0, 0q, e2 “ p0, 1, 0q, and e3 “ p0, 0, 1q. Sierpinski binning is a recursive partitioning of this triangle based on the fractal popularly known as the Sierpinski triangles. Some Sierpinski bins forL “ 3 are shown in Figure 10. Formally, we define Sierpinski binning recursively based on a depth parameter q P N. Given an x P X , let s “ gpxq. For q “ 1, the number of bins is B “ 4, and the binning scheme B is defined as:
Bpsq “
$
’ &
’ % 1 if s1 ą 0.5 2 if s2 ą 0.5 3 if s3 ą 0.5 4 otherwise.
(20)
Note that since s1 ` s2 ` s3 “ 1, only one of the above conditions can be true. It can be verified that each of the bins have volume equal to p1{4q-th the volume of the probability simplex ∆2. If a finer resolution of ∆2 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 ∆2 to recursively define the sub-partitioning. For i P r4s, define the bins bi “ ts : Bpsq “ iu. Consider the bin b1. Let us ‘reparameterize’ it as pt1, t2, t3q “ p2s1 ´ 1, 2s2, 2s3q. It can be verified that b1 “ tpt1, t2, t3q : s1 ą 0.5u “ tpt1, t2, t3q : t1 ` t2 ` t3 “ 1, t1 P p0, 1s, t2 P r0, 1q, t3 P r0, 1qu.
Based on this reparameterization, we can recursively sub-partition b1 as per the scheme (20), replacing s with t. Such reparameterizations can be defined for each of the bins defined in (20):
b2 “ tps1, s2, s3q : s2 ą 0.5u : pt1, t2, t3q “ p2s1, 2s2 ´ 1, 2s3q, b3 “ tps1, s2, s3q : s3 ą 0.5u : pt1, t2, t3q “ p2s1, 2s2, 2s3 ´ 1q,
b4 “ tps1, s2, s3q : si ď 0.5 for all iu : pt1, t2, t3q “ p1´ 2s1, 1´ 2s2, 1´ 2s3q, and thus every bin can be recursively sub-partitioned as per (20). As illustrated in Figure 10, for Sierpinski binning, we sub-partition only the bins b1, b2, b3 since the bin b4 corresponds to low confidence for all labels, where finer calibration may not be needed. (Also, in the L ą 3 case described shortly, the corresponding version of b4 is geometrically different from ∆L´1, and the recursive partitioning cannot be defined for it.) If at every depth, we sub-partition all bins except the corresponding b4 bins, then it can be shown using simple algebra that the total number of bins is p3q`1 ´ 1q{2. For example, in Figure 10, when q “ 2, the number of bins is B “ 14, and when q “ 3, the number of bins is B “ 40. As in the case of L “ 3, Sierpinski binning for general L is defined through a partitioning function of ∆L´1 into L ` 1 bins, and a reparameterization of the partitions so that they can be further sub-partitioned. The L` 1 bins at depth q “ 1 are defined as
Bpsq “ " l if sl ą 0.5, L` 1 otherwise. (21)
While this looks similar to the partitioning (20), the main difference is that the bin bL`1 has a larger volume than other bins. Indeed for l P rLs, volpblq “ volp∆L´1q{2L´1, while volpbL`1q “ volp∆L´1qp1 ´ L{2L´1q ě volp∆L´1q{2L´1, with equality only occuring for L “ 3. Thus the bin bL`1 is larger than the other bins. If gpxq P bL`1, then the prediction for x may be not be very sharp, compared to if gpxq were in any of the other bins. On the other hand, if gpxq P bL`1, 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, we only reparameterize the bins b1, b2, . . . , bL so that they can be further divided:
bl “ tps1, s2, . . . , sLq : sl ą 0.5u : pt1, t2, . . . , tLq “ p2s1, . . . , 2sl ´ 1, . . . , 2sLq. For every l P rLs, under the reparameterization above, it is straightforward to verify that
tpt1, t2, . . . , tLq : sl ą 0.5u “ tpt1, t2, . . . , tLq : ÿ
uPrLs tu “ 1, tl P p0, 1s, tu P r0, 1q @u ‰ lu.
Thus every bin can be recursively sub-partitioned following (21). For Sierpinski binning with L labels, the number of bins at depth q is given by pLq`1 ´ 1q{pL´ 1q.

heading: F.2 GRID-STYLE BINNING
text: Grid-style binning is motivated from the 2D reliability diagrams of Widmann et al. (2019, Figure 1), where they partitioned ∆2 into multiple equi-volume bins in order to assess canonical calibration on a 3-class version of CIFAR-10. For L “ 3, ∆2 can be divided as shown in Figure 11. This corresponds to ‘gridding’ the space ∆2, 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 11. We describe grid-style binning formally for general L ě 3. Consider some τ ą 0 such that K :“ 1{τ P N. For every tuple k “ pk1, k2, . . . , kLq in the set
I “ tk P NL : maxpL,K ` 1q ď ÿ
lPrLs kl ď K ` pL´ 1qu, (22)
define the bins bk :“ ts P ∆L´1 : for every l P rLs, slK P rkl ´ 1, kls. (23)
These bins are not mutually disjoint, but intersections can only occur at the ‘edges’. That is, for every s that belongs to more than one bin, at least one component sl satisies slK P N. In order to identify a single bin s, ties can be broken arbitrarily. One strategy is to use some ordering on NL; say for k1 ‰ k2 P N, k1 ă k2 if and only if for the first element of k1 that is unequal to the corresponding element of k2 the one corresponding to k1 is smaller. Then define the binning function B : ∆L´1 Ñ |I| as Bpsq “ mintk : s P bku. 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 ∆L´1).
Proposition 2. The bins tbk : k P Iu defined by (23) mutually exhaust ∆L´1.
Proof. Consider any s P ∆L´1. For slK R N “ t1, 2, . . .u, set kl “ maxp1, rslKsq ą slK. Consider the condition C : for all l such that slK R N, slK “ 0. IfC is true, then for l such that slK P N, set kl “ slK. If C is not true, then for l such that slK P N, set exactly one kl “ slK ` 1, and for the rest set kl “ slK. Based on this setting of k, it can be verified that s P bk. Further, note that for every l, kl ě slK, and there exists at least one l such that kl ą slK. Thus we have:
L ÿ l“1 kl ą L ÿ l“1 slK
“ K.
Since řL l“1 kl P N, we must have řL l“1 kl ě K ` 1. Further since each kl P N, řL l“1 kl ě L. Next, note that for every l, kl ď slK ` 1. If C is true, then there is at least one l such that slK P N, and for this l, we have set kl “ slK ă slK ` 1. If C is not true, then either there exists at least one l such that slK R N Y t0u for which kl “ rslKs ă slK ` 1, or every slK P N, in which case we
have set kl “ slK for one of them. In all cases, note that there exists an l such that kl ă slK ` 1. Thus,
L ÿ l“1 kl ă L ÿ l“1 pslK ` 1q
“ K ` L.
Since řL l“1 kl P N, we must have řL l“1 kl ď K ` L´ 1.
Next, we show that each bin indexed by k P I contains a non-zero volume subset of ∆L´1, where volume is defined with respect to the Lebesgue measure in RL´1. This can be shown by arguing that bk contains a scaled and translated version of ∆L“1. Proposition 3. For every k P I , there exists some u P RL and v ą 0 such that u` v∆L´1 Ď bk.
Proof. Fix some k P I . By condition (22), řL l“1 kl P rmaxpL,K ` 1q,K ` L´ 1s. Based on this, we claim that there exists a τ P r0, 1q such that
L ÿ l“1 pkl ´ 1q ` τL` p1´ τq “ K. (24)
Indeed, note that for τ “ 0, řL l“1pkl ´ 1q ` τL ` p1 ´ τq ď pK ´ 1q ` 1 “ K and for τ “ 1, řL
l“1pkl ´ 1q ` τL ` p1 ´ τq “ řL l“1 kl ą K. Thus, there exists a τ that satisfies (24) by the intermediate value theorem.
Next, define u “ K´1pk ` pτ ´ 1q1Lq and v “ K´1p1 ´ τq ą 0, where 1L denotes the vector in RL with each component equal to 1. Consider any s P u ` v∆L´1. Note that for every l P rLs, slK P rkl ´ 1, kls and by property (24),
L ÿ l“1 slK “
˜
L ÿ l“1 pkl ` pτ ´ 1qq
¸
` v “ L ÿ
l“1 pkl ´ 1q ` τL` p1´ τq “ K.
Thus, s P ∆L´1 and by the definition of bk, s P bk. This completes the proof.
The previous two propositions imply that B satisfies the property we require of a reasonable binning scheme. For L “ 3, grid-style binning gives equi-volume bins as illustrated in Figure 11; however this is not true for L ą 3. We now describe a histogram binning based partitioning scheme.

heading: F.3 PROJECTION BASED HISTOGRAM BINNING FOR CANONICAL CALIBRATION
text: Some of the bins defined by Sierpinski binning and grid-style binning may have very few calibration points nb, leading to poor estimation of pΠ. In the binary calibration case, this can be remedied using histogram binning which strongly relies on the scoring function g taking values in a fully ordered space r0, 1s. To ensure that each bin contains Ωpn{Bq points, we estimate the quantiles of gpXq and created the bins as per these quantiles. However, there are no natural quantiles for unordered prediction spaces such as ∆L´1 (L ě 3). In this section, we develop a histogram binning scheme for ∆L´1 that is semantically interpretable and has desirable statistical properties.
Our algorithm takes as input a prescribed number of bins B and an arbitrary sequence of vectors q1, q2, . . . , qB´1 P RL with unit `2-norm: }qi}2 “ 1. Each of these vectors represents a direction on which we will project ∆L´1 in order to induce a full order on ∆L´1. Then, for each direction, we will use an order statistics on the induced full order to identify a bin with exactly tpn` 1q{Bu´ 1 calibration points (except the last bin, which may have more points). The formal algorithm is described in Algorithm 10. It uses the following new notation: givenm vectors v1, v2, . . . , vm P RL, a unit vector u, and an index j P rms, let order-statisticsptv1, v2, . . . , vmu, u, jq denote the j-th order-statistics of tvT1 u, vT2 u, . . . , vTmuu.
Algorithm 10: Projection histogram binning for canonical calibration Input: Base multiclass predictor g : X Ñ ∆L´1, calibration data D “ tpX1, Y1q, pX2, Y2q, . . . , pXn, Ynqu Hyperparameter: number of bins B, unit vectors q1, q2, . . . , qB P RL, Output: Approximately calibrated scoring function h
1 S Ð tgpX1q,gpX2q, . . . ,gpXnqu; 2 T Ð empty array of size B; 3 cÐ tn`1B u; 4 for bÐ 1 to B ´ 1 do 5 Tb Ð order-statisticspS, qb, cq; 6 S Ð Sztv P S : vT qb ď Tbu; 7 end 8 TB Ð 1.01; 9 Bpgp¨qq Ð mintb P rBs : gp¨qT qb ă Tbu;
10 pΠ Ð empty matrix of size B ˆ L; 11 for bÐ 1 to B do 12 for lÐ 1 to L do 13 pΠb,l ÐMeant1 tYi “ lu : BpgpXiqq “ b and @s P rBs, gpXiqT qs ‰ Tsu; 14 end 15 end 16 for lÐ 1 to L do 17 hlp¨q Ð pΠBpgp¨qq,l; 18 end 19 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 the directions given by q. Each pqb, Tbq pair corresponds to a hyperplane that ‘cuts’ ∆L´1 into two subsets given by tx P ∆L´1 : xT qb ă Tbu and tx P ∆L´1 : xT qb ě Tbu. The overall partitioning of ∆L´1 is created by merging these cuts sequentially. This defines the binning function B. By construction, the binning function is such that each bin contains at least tn`1B u´ 1 many points in its interior. As suggested by Gupta and Ramdas (2021), we do not include the points that lie on the boundary, that is, points Xi that satisfy gpXiqT qs “ Ts for some s P rBs. The interior points bins are then used to estimate the bin biases pΠ.
No matter how the q-vectors are chosen, the bins created by Algorithm 10 have at least X n B \ ´1 points for bias estimation. However, we discuss some simple heuristics for setting q 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 10 if L “ 2 by setting each qb as e2 (the vector r0, 1s). Equivalently, we can set each qb to ´e1 since both are equivalent for creating a projection-based order on ∆2. Thus for L ě 3, a natural strategy for the q-vectors is to rotate between the canonical basis vectors: q1 “ ´e1, q2 “ ´e2, . . . , qL “ ´eL, qL`1 “ ´e1, . . . , and so on. Projecting with respect to ´el focuses on the class l by forming a bin corresponding to the largest values of glpXiq among the remaining Xi’s which have not yet been binned. (On the other hand, projecting with respect to el will correspond to forming a bin with the smallest values of glpXiq.) The q-vectors can also be set adaptively based on the training data (without seeing the calibration data). For instance, if most points belong to a specific class l P rLs, we may want more sharpness for this particular class. In that case, we can choose a higher ratio of the q-vectors to be ´el.

heading: F.4 EXPERIMENTS WITH THE COVTYPE DATASET
text: In Figure 12 we illustrate the binning schemes proposed in this section on a 3-class version of the COVTYPE-7 dataset considered in Section B.2. As noted before, this is an imbalanced dataset where classes 1 and 2 dominate. We created a 3 class problem with the classes 1, 2, and other (as
class 3). The entire dataset has 581012 points and the ratio of the classes is approximately 36%, 49%, 15% respectively. The dataset was split into train-test in the ratio 70:30. The training data was further split into modeling-calibration in the ratio 90:10. A logistic regression model g using sklearn.linear model.LogisticRegression was learnt on the modeling data, and g was recalibrated on the calibration data.
The plots on the right in Figure 12 are recalibration diagrams. The base predictions gpXq on the test-data are displayed as a scatter plot on ∆2. Points in different bins are colored using one of 10
different colors (since the number of bins is larger than 10, some colors correspond to more than one bin). For each bin, an arrow is drawn, where the tail of the arrow corresponds to the average gpXq predictions in the bin and the head of the arrow corresponds to the recalibrated hpXq prediction for the bin. For bins that contained very few points, the arrows are suppressed for visual clarity.
The plots on the left in Figure 12 are validity plots (Gupta and Ramdas, 2021). Validity plots display estimates of V pεq “ Ptest-data p}E rY | gpXqs ´ gpXq}1 ď εq , as ε varies (g corresponds to the validity plot for logistic regression; replacing g with h 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 pεq. Overall, Figure 12 shows that all of the binning approaches improve the calibration of the original logistic regression model across different ε. However, the recalibration does not change the original model significantly. Comparing the different binning methods to 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.

heading: G PROOFS
text: Proofs appear in separate subsections, in the same order as the corresponding results appear in the paper and Appendix. Proposition 4 was stated informally, so we state it formally as well.

heading: G.1 STATEMENT AND PROOF OF PROPOSITION 4
text: Proposition 4. For any predictor pc, hq, conf-ECEpc, hq ď TL-ECEpc, hq.
Proof. To avoid confusion between the the conditioning operator and the absolute value operator |¨|, we use abs p¨q to denote absolute values below. Note that, abs pP pY “ cpXq | hpXqq ´ hpXqq “ abs pE r1 tY “ cpXqu | hpXqs ´ hpXqq
“ abs pE r1 tY “ cpXqu ´ hpXq | hpXqsq “ abs pE rE r1 tY “ cpXqu ´ hpXq | hpXq, cpXqs | hpXqsq ď E rabs pE r1 tY “ cpXqu ´ hpXq | hpXq, cpXqsq | hpXqs
(by Jensen’s inequality) “ E rabs pP pY “ cpXq | hpXq, cpXqq ´ hpXqq | hpXqs .
Thus,
conf-ECEpc, hq “ E rabs pP pY “ cpXq | hpXqq ´ hpXqqs ď E rE rabs pP pY “ cpXq | hpXq, cpXqq ´ hpXqq | hpXqss “ E rabs pP pY “ cpXq | hpXq, cpXqq ´ hpXqqs “ TL-ECEpc, hq.

heading: G.2 PROOF OF THEOREM 1
text: The proof strategy is as 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 hl. Then, we show that the binary guarantees for the individual hl’s leads to a top-label guarantee for the overall predictor pc, hq. Consider any l P rLs. Let Pl denote the conditional distribution of pX,1 tY “ luq given cpXq “ l. Clearly, Dl is a set of nl i.i.d. samples from Pl, and hl is learning a binary calibrator with respect to Pl using binary histogram binning. The number of data-points is nl and the number of bins is Bl “ tnl{ku bins. We now apply the GR21 bounds on hl. First, we verify that the condition they require is satisfied:
nl ě k tnl{ku ě 2Bl.
Thus their marginal calibration bound for hl gives,
P
˜
|P pY “ l | cpXq “ l, hlpXqq ´ hlpXq| ď δ `
d
logp2{αq 2ptnl{Blu´ 1q
| cpXq “ l ¸ ě 1´ α.
Note that since tnl{Blu “ tnl{ tnl{kuu ě k,
ε1 “ δ `
d
logp2{αq 2pk ´ 1q ě δ `
d
logp2{αq 2ptnl{Blu´ 1q .
Thus we have
P p|P pY “ l | cpXq “ l, hlpXqq ´ hlpXq| ď ε1 | cpXq “ lq ě 1´ α. This is satisfied for every l. Using the law of total probability gives us the top-label marginal calibration guarantee for pc, hq:
P p|P pY “ cpXq | cpXq, hpXqq ´ hpXq| ď ε1q
“ L ÿ
l“1 P pcpXq “ lqP p|P pY “ cpXq | cpXq, hpXqq ´ hpXq| ď ε1 | cpXq “ lq
(law of total probability)
“ L ÿ
l“1 P pcpXq “ lqP p|P pY “ l | cpXq “ l, hlpXqq ´ hlpXq| ď ε1 | cpXq “ lq
(by construction, if cpxq “ l, hpxq “ hlpxq)
ě L ÿ
l“1 P pcpXq “ lqp1´ αq
“ 1´ α.
Similarly, the in-expectation ECE bound of GR21, for p “ 1, gives for every l,
E |P pY “ l | cpXq “ l, hlpXqq ´ hlpXq | cpXq “ l| ď a
Bl{2nl ` δ “ a
tnl{ku {2nl ` δ ď a
1{2k ` δ. Thus,
E|P pY “ cpXq | cpXq, hlpXqq ´ hpXq|
“ L ÿ
l“1 P pcpXq “ lqE|P pY “ l | cpXq “ l, hlpXqq ´ hlpXq| | cpXq “ l
ď L ÿ
l“1 P pcpXq “ lqp
a
1{2k ` δq
“ a 1{2k ` δ.
Next, we show the top-label conditional calibration bound. Let B “ řL l“1Bl and αl “ αBl{B. Note that B ď
řL l“1 nl{k “ n{k. The binary conditional calibration bound of GR21 gives
P
˜
@r P Rangephlq, |P pY “ l | cpXq “ l, hlpXq “ rq ´ r| ď δ `
d
logp2Bl{αlq 2ptnl{Blu´ 1q
| cpXq “ l ¸
ě 1´ αl. Note that
d
logp2Bl{αlq 2ptnl{Blu´ 1q “
d
logp2B{αq 2ptnl{Blu´ 1q
ď
d
logp2n{kαq 2ptnl{Blu´ 1q
(since B ď n{k)
ď
d
logp2n{kαq 2pk ´ 1q (since k ď tnl{Blu).
Thus for every l P rLs,
P p@r P Rangephlq, |P pY “ l | cpXq “ l, hlpXq “ rq ´ r| ď ε2q ě 1´ αl.
By construction of h, conditioning on cpXq “ l and hlpXq “ r is the same as conditioning on cpXq “ l and hpXq “ r. Taking a union bound over all L gives
P p@l P rLs, r P Rangephq, |P pY “ cpXq | cpXq “ l, hpXq “ rq ´ r|q ď ε2q
ě 1´ L ÿ
l“1 αl “ 1´ α,
proving the conditional calibration result. Finally, note that if for every l P rLs, r P Rangephq,
|P pY “ cpXq | cpXq “ l, hpXq “ rq ´ r| ď ε2,
then also TL-ECEpc, hq “ E|P pY “ cpXq | hpXq, cpXqq ´ hpXq| ď ε2.
This proves the high-probability bound for the TL-ECE. Remark 3. Gupta and Ramdas (2021) proved a more general result for general `p-ECE bounds. Similar results can also be derived for the suitably defined `p-TL-ECE. Additionally, it can be shown that with probability 1 ´ α, the TL-MCE of pc, hq is bounded by ε2. (TL-MCE is defined in Appendix D, equation (8).)

heading: G.3 PROOF OF PROPOSITION 1
text: Consider a specific l P rLs. We use hl to denote the l’th component function of h and Yl “ 1 tY “ lu. Canonical calibration implies
P pY “ l | hpXqq “ E rYl | hpXqs “ hlpXq. (25)
We can then use the law of iterated expectations (or tower rule) to get the final result:
E rYl | hlpXqs “ E rE rYl | hpXqs | hlpXqs “ E rhlpXq | hlpXqs (by the canonical calibration property (25)) “ hlpXq.

heading: G.4 PROOF OF THEOREM 2
text: 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 hl. This leads to the class-wise results as well.
Consider any l P rLs. Let Pl denote the distribution of pX,1 tY “ luq. Clearly, Dl is a set of n i.i.d. samples from Pl, and hl is learning a binary calibrator with respect to Pl using binary histogram binning. The number of data-points is n and the number of bins is Bl “ tn{klu bins. We now apply the GR21 bounds on hl. First, we verify that the condition they require is satisfied:
n ě kl tn{klu ě 2Bl.
Thus the GR21 marginal calibration bound gives that for every l P rLs, hl satisfies
P
˜
|P pY “ l | hlpXqq ´ hlpXq| ď δ `
d
logp2{αlq 2ptn{Blu´ 1q
¸
ě 1´ αl.
The class-wise marginal calibration bound of Theorem 2 follows since tn{Blu “ tn{ tn{kluu ě kl, and so
ε p1q l ě δ `
d
logp2{αlq 2ptn{Blu´ 1q .
Next, the GR21 conditional calibration bound gives for every l P rLs, hl satisfies
P
˜
@r P Rangephlq, |P pY “ l | hlpXq “ rq ´ r| ď δ `
d
logp2Bl{αlq 2ptn{Blu´ 1q
¸
ě 1´ αl.
The class-wise marginal calibration bound of Theorem 2 follows since Bl “ tn{klu ď n{kl and tn{Blu “ tn{ tn{kluu ě kl, and so
ε p2q l ě δ `
d
logp2Bl{αlq 2ptn{Blu´ 1q .
Let k “ minlPrLs kl. The in-expectation ECE bound of GR21, for p “ 1, gives for every l,
E rbinary-ECE-for-class-l phlqs ď a
Bl{2nl ` δ “ a
tn{klu {2n` δ ď a
1{2kl ` δ ď a 1{2k ` δ.
Thus,
E rCW-ECEpc, hqs “ E « L´1 L ÿ
l“1 binary-ECE-for-class-l phlq
ff
ď L´1 L ÿ
l“1 p a 1{2k ` δq
“ a 1{2k ` δ,
as required for the in-expectation CW-ECE bound of Theorem 2. Finally, for the high probability CW-ECE bound, let ε “ maxlPrLs ε p2q l and α “ řL l“1 αl. By taking a union bound over the the conditional calibration bounds for each hl, we have, with probability 1 ´ α, for every l P rLs and r P Rangephq, |P pY “ l | cpXq “ l, hpXq “ rq ´ r| ď εp2ql ď ε. Thus, with probability 1´ α,
CW-ECEpc, hq “ L´1 L ÿ
l“1 E|P pY “ l | hlpXqq ´ hlpXq| ď ε.
This proves the high-probability bound for the CW-ECE.

Review summaries:
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.

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.  The 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.

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.   In 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.