# TOP-LABEL CALIBRATION
## AND MULTICLASS-TO-BINARY REDUCTIONS

**Chirag Gupta & Aaditya Ramdas**
Carnegie Mellon University
_{chiragg,aramdas}@cmu.edu_

ABSTRACT

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

1 INTRODUCTION

Machine learning models often make probabilistic predictions. The ideal prediction is the true conditional distribution of the output given the input. However, nature never reveals true probability
distributions, making it infeasible to achieve this ideal in most situations. Instead, there is significant interest towards designing models that are calibrated, which is often feasible. We motivate the
definition of calibration using a standard example of predicting the probability of rain. Suppose a
meteorologist claims that the probability of rain on a particular day is 0.7. Regardless of whether it
rains on that day or not, we cannot know if 0.7 was the underlying probability of rain. However, we
can test if the meteorologist is calibrated in the long run, by checking if on the D days when 0.7 was
predicted, it indeed rained on around 0.7D days (and the same is true for other probabilities).

This example is readily converted to a formal binary calibration setting. Denote a random (feature,
label)-pair as pX, Y q P X ˆ t0, 1u, where X is the feature space. A probabilistic predictor h : X Ñ
r0, 1s is said to be calibrated if for every prediction q P r0, 1s, PrpY “ 1 | hpXq “ qq “ q (almost
surely). Arguably, if an ML classification model produces such calibrated scores for the classes,
downstream users of the model can reliably use its predictions for a broader set of tasks.

Our focus in this paper is calibration for multiclass classification, with L ě 3 classes and Y P
rLs :“ t1, 2, . . ., L ě 3u. We assume all (training and test) data is drawn i.i.d. from a fixed
distribution P, and denote a general point from this distribution as pX, Y q „ P . Consider a typical
multiclass predictor, h : X Ñ ∆[L][´][1], whose range ∆[L][´][1] is the probability simplex in R[L]. A
natural notion of calibration for h, called canonical calibration is the following: for every l P rLs,
_P_ pY “ l | hpXq “ qq “ ql (ql denotes the l-th component of q). However, canonical calibration
becomes infeasible to achieve or verify once L is even 4 or 5 (Vaicenavicius et al., 2019). Thus,
there is interest in studying statistically feasible relaxations of canonical notion, such as confidence
calibration (Guo et al., 2017) and class-wise calibration (Kull et al., 2017).


-----

In particular, the notion of confidence calibration (Guo et al., 2017) has been popular recently.
A model is confidence calibrated if the following is true: “when the reported confidence for the
predicted class is q P r0, 1s, the accuracy is also q”. In any practical setting, the confidence q is
never reported alone; it is always reported along with the actual class prediction l P rLs. One
may expect that if a model is confidence calibrated, the following also holds: “when the class l is
predicted with confidence q, the probability of the actual class being l is also q”? Unfortunately, this
expectation is rarely met—there exist confidence calibrated classifier for whom the latter statement
is grossly violated for all classes (Example 1). On the other hand, our proposed notion of top-label
calibration enforces the latter statement. It is philosophically more coherent, because it requires
conditioning on all relevant reported quantities (both the predicted top label and our confidence in
it). In Section 2, we argue further that top-label calibration is a simple and practically meaningful
replacement of confidence calibration.

In Section 3, we unify top-label, confidence, and a number of other popular notions of multiclass
calibration into the framework of multiclass-to-binary (M2B) reductions. The M2B framework relies on the simple observation that each of these notions internally verifies binary calibration claims.
As a consequence, each M2B notion of calibration can be achieved by solving a number of binary
calibration problems. With the M2B framework at our disposal, all of the rich literature on binary
calibration can now be used for multiclass calibration. We illustrate this by instantiating the M2B
framework with the binary calibration algorithm of histogram binning or HB (Zadrozny and Elkan,
2001; Gupta and Ramdas, 2021). The M2B + HB procedure achieves state-of-the-art results with
respect to standard notions of calibration error (Section 4). Further, we show that our procedure is
provably calibrated for arbitrary data-generating distributions. The formal theorems are delayed to
Appendices B, C (due to space limitations), but an informal result is presented in Section 4.

2 MODIFYING CONFIDENCE CALIBRATION TO TOP-LABEL CALIBRATION

Let c : X Ñ rLs denote a classifier or top-label 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 the data-generating distribution P ) if

_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 invasive 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%? It would appear that by
focusing on the the probability of the predicted label, confidence calibration enforces such control.

However, as we illustrate next, confidence calibration fails at this goal by providing a guarantee that
is neither practically interpretable, nor actionable. Translating the probabilistic statement (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”. Such_
a guarantee is not very useful. Suppose a patient P is informed (based on their symptoms X), that
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. 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:

|0.5|1|0.6|
|---|---|---|


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, l ‰ cpxq, can be set arbitrarily. We verify that pc, hq is 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 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. Contrarily, if X “ b, hpXq “ 0.6 is extremely underconfident.

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 is reported, that is both cpXq and hpXq. We make
a small but critical change to (1); we say that pc, hq is top-label calibrated if
_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 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 H). 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 probabilities using all the points in a bin. The calibration method
we espouse in this work, histogram binning (HB), produces discrete predictions whose ECE can
be estimated without further binning. Based on this, we use the following experimental protocol:
we report unbinned ECE estimates while assessing HB, and binned ECE estimates for all other
compared methods, which are continuous output methods (deep-nets, temperature scaling, etc). 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.

2.1 AN ILLUSTRATIVE EXPERIMENT WITH RESNET-50 ON CIFAR-10

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. Here, 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), constructed 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 :“ |P pY “ cpXq | cpXq “ l, hpXq P Bin bq ´ E rhpXq | cpXq “ l, hpXq P Bin bs |,

where _P,_ E denote empirical estimates based on the test data. The overall miscalibration is then

[p] [p]

[p] ∆[p] _b :“ Weighted-averagep∆b,lq “_ _lPrLs_ _P_ 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[ř] [p] ∆b,l,
thenthe direction for the corresponding point from the confidence reliability diagram. Thus for every ∆b would simply equal accb ´ confb. In order to plot ∆b in a reliability diagram, we obtain
‹otherwise, for every “ pconfb, accbq, we plot b. This scatter plot of the ` “ pconfb, confb` `∆’s gives us the top-label reliability diagram.bq if accb ą confb and ` “ pconfb, confb´∆bq
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 the X “ Y line, indicating that the overall accuracy matches the


-----

Base model top-label-ECE Temperature scaling top-label-ECE Histogram binning top-label-ECE
Base model conf-ECE Temperature scaling conf-ECE Histogram binning conf-ECE

ResNet-50


Temperature scaling top-label-ECE
Temperature scaling conf-ECE


Histogram binning top-label-ECE
Histogram binning conf-ECE


ResNet-110


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins




0.030

0.025

0.020

0.015

0.010

0.005


0.025

0.020

0.015

0.010

0.005


0.025

0.020


0.015


CIFAR-10, as well as with recalibration using histogram binning and temperature scaling. The TL
the architecture. Top-label histogram binning typically performs better than temperature scaling.

5 10 15 20 25

|0.0275|Col2|Col3|Col4|Col5|Col6|Col7|Col8|Col9|Col10|Col11|Col12|Col13|Col14|Col15|Col16|Col17|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|0.0275||||||||0.030|||||||||
|0.0 0.0|250 225||||||||0.025 ECE||||||||
||||||||||||||||||
||||||||||||||||||
|0.0 0.0 0.0|200 175 150||||||||0.020 Estimated 0.015||||||||
||||||||||||||||||
|0.0 0.0|125 100||||||||0.010 0.005||||||||
||||||||||||||||||
|0.0|075 5 10|||15 Number of bins||20 25|||5|||1|0 15 20 25 Number of bins s) and TL-E ation using h CE, dependin m binning ty||||
|ig I C|ure 2: FAR-10 E is oft|||Conf-E, as wel en 2-3||CE (da l as wit times th|||shed li h recali e conf-|||ne br E|||||
|e|archite|||cture. T||op-labe|||l histog|||ra|||||


overall confidence of 0.545. However, the true accuracy when class 1 was predicted is 0.2 and

Number of bins

«
the true accuracy when class 8 was predicted is « 0.9 (a very similar scenario to Example 1). For
bin 10, the ‹ marker indicates a miscalibration of « 0.01; however, when class 4 was predicted
(roughly 8% of all test-points) the miscalibration is « 0.05.

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 value B 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.


3 CALIBRATION ALGORITHMS FROM CALIBRATION METRICS

In this section, we unify a number of notions of multiclass calibration as multiclass-to-binary (or
M2B) notions, and propose a general-purpose calibration algorithm that achieves the corresponding
M2B notion of calibration. The M2B framework yields multiple novel post-hoc calibration algorithms, each of which is tuned to a specific M2B notion of calibration.


3.1 MULTICLASS-TO-BINARY (M2B) NOTIONS OF CALIBRATION

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** _h1, h2, . . ., hL_ is said to be class-wise calibrated (Kull et al., 2017) if
“ p q

(class-wise calibration) _l_ _L_, P _Y_ _l_ _hl_ _X_ _hl_ _X_ _._ (5)
@ P r s p “ | p qq “ p q

Another recently proposed notion is top-K confidence calibration (Gupta et al., 2021). For some
_l P rLs, let c[p][l][q]_ : X Ñ rLs denote the l-th highest class prediction, and let h[p][l][q] : X Ñ rLs denote
the confidence associated with it (c “ c[p][1][q] and h “ h[p][1][q] are special cases). For a given K ď L,


(top-K-confidence calibration) @k P rKs, P pY “ c[p][k][q]pXq | h[p][k][q]pXqq “ h[p][k][q]pXq. (6)


-----

|Calibration notion|Quantifier|Prediction (predpXq)|Binary calibration statement|
|---|---|---|---|
|Confidence|-|hpXq|PpY “ cpXq | predpXqq “ hpXq|
|Top-label|-|cpXq, hpXq|PpY “ cpXq | predpXqq “ hpXq|
|Class-wise|@l P rLs|h lpXq|PpY “ l | predpXqq “ h lpXq|
|Top-K-confidence|@k P rKs|hpkqpXq|PpY “ cpkqpXq | predpXqq “ hpkqpXq|
|Top-K-label|@k P rKs|cpkqpXq, hpkqpXq|PpY “ cpkqpXq | predpXqq “ hpkqpXq|


Table 1: Multiclass-to-binary (M2B) notions internally verify one or more binary calibration statements/claims. The statements in the rightmost column are required to hold almost surely.

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 “ c[p][k][q]pXq | h[p][k][q]pXq, c[p][k][q]pXqq “ h[p][k][q]pXq. (7)

Each of these notions reduce multiclass calibration to one or more binary calibration requirements,
where each binary calibration requirement corresponds to verifying if the distribution of Y, condi**tioned on some prediction 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 _L_, the conditioning is on pred _X_ _hl_ _X_, and a single binary calibration statement
P r s p q “ p q
is verified: P _Y_ _l_ pred _X_ _hl_ _X_ . Based on this property, we call each of these notions
p “ | p qq “ p q
multiclass-to-binary or M2B notions.

The notion of canonical calibration mentioned in the introduction is not an M2B notion. Canonical
calibration is discussed in detail in Appendix G. 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.

3.2 ACHIEVING M2B NOTIONS OF CALIBRATION USING M2B CALIBRATORS

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
_X1, Y1_ _,_ _X2, Y2_ _, . . .,_ _Xn, Yn_ _L_, typically data on which g was not learnt, to
_D “ p_ q p q p q P pX ˆ r sq[n]
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, 1s[X] ˆpX ˆt0, 1uq[‹] Ñ r0, 1s[X], 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 0,1 are histogram binning (Zadrozny and Elkan, 2001), isotonic
_At_ u
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, 1s[X]** ˆ pX ˆ t0, 1uq[‹] Ñ r0, 1s[X], base multiclass
predictor g : ∆[L][´][1], calibration data _X1, Y1_ _, . . .,_ _Xn, Yn_ .
_X Ñ_ _D “ p_ q p q


**Algorithm 3: Class-wise calibrator**


**Algorithm 1: Confidence calibrator**

**1 c Ð classifier or top-class based on g;**

**23 g Ð top-class-probability based onXi, 1** _Yi_ _c_ _Xi_ : i **gn;** ;

**4 h D Ð[1]** Ð tp At0,1upg, t D[1] “q; p quq P r su

**5 return pc, hq;**


**1 Write g** _g1, g2, . . ., gL_ ;
“ p q

**23 for l Ðl** 1 to LX doi, 1 _Yi_ _l_ : i _n_ ;

**4** _Dhl Ð Ð tp At0,1upg tl, D “lq;_ uq P r su

**5 end**

**6 return ph1, h2, . . ., hLq;**

**Algorithm 4: Normalized calibrator**


**Algorithm 2: Top-label calibrator**


_c_ classifier or top-class based on g; **1 Write g “ pg1, g2, . . ., gLq;**
Ð **2 for l** 1 to L do

_g for Ð lDh top-class-probability based on Ðll Ð tp 1 to LX0,1 doi, 1g, tYi “l_ ; _luq : cpXiq “ g;_ _lqu;_ **534 endDh Ðll Ð Ð tp AtX0,1iu, 1pg tl,Y Di “lq; luq : i P rnsu;**

**end** Ð At up _D_ q **6 Normalize: for everyr** _l P rLs,_

_h returnp¨q Ð p hc, hcp¨qqp¨q;_ (predict hlpxq if cpxq “ l); **7 returnhlp¨q : p“h1h, hlp¨q{2, . . ., hk“1Lhq;kp¨q;**

[r] [ř][L] [r]

we are aware of, with the most similar one being Algorithm 3. 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 2 constructs
binary calibrator. The final probabilistic predictor isLlabels are datasets 1 t tDYli : “ l l P ru. Now for everyLsu (line 4). The features in l P rLs, we calibrate D hl are thep¨q “ g to h X hcp¨qil :’s for whichp¨q X (that is, it predicts Ñ r0, 1 csp usingXiq “ D ll, and the h and anylpxq 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 0,1 is used. Unlike the top-label calibrator,
_At_ u
the confidence calibrator merges all classes together into a single dataset _l_ _L_
_D[1]_ “ Pr s _[D][l][.]_

To achieve class-wise calibration, Algorithm 3 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 c _Xi_ _l), and hl is passed to_ 0,1 instead
The overall process is similar to reducing multiclass classification toof h. Also, unlike confidence calibration, Yi is replaced withp q ‰ 1 tYi “ L lu 1-v-all binary classification instead of 1 A tYti “u cpXiqu.
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 3, 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
works[1] 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 3 the predictor hl for each class is learnt completely independently of other classes


**1 c Ð classifier or top-class based on g;**

**2 g Ð top-class-probability based on g;**

**34 for l Ðl** 1 to LX doi, 1 _Yi_ _l_ : c _Xi_ _l_ ;

**5** _Dhl Ð Ð tp At0,1upg, t D “lq;_ uq p q “ qu

**6 end**

**7 hp¨q Ð hcp¨qp¨q (predict hlpxq if cpxq “ l);**

**8 return pc, hq;**


-----

|Metric|Dataset|Architecture|Base|TS|VS|DS|N-HB|TL-HB|
|---|---|---|---|---|---|---|---|---|
|Top- label- ECE|CIFAR-10|ResNet-50|0.025|0.022|0.020|0.019|0.018|0.020|
|||ResNet-110|0.029|0.022|0.021|0.021|0.020|0.021|
|||WRN-26-10|0.023|0.023|0.019|0.021|0.012|0.018|
|||DenseNet-121|0.027|0.027|0.020|0.020|0.019|0.021|
||CIFAR-100|ResNet-50|0.118|0.114|0.113|0.322|0.081|0.143|
|||ResNet-110|0.127|0.121|0.115|0.353|0.093|0.145|
|||WRN-26-10|0.103|0.103|0.100|0.304|0.070|0.129|
|||DenseNet-121|0.110|0.110|0.109|0.322|0.086|0.139|
|Top- label- MCE|CIFAR-10|ResNet-50|0.315|0.305|0.773|0.282|0.411|0.107|
|||ResNet-110|0.275|0.227|0.264|0.392|0.195|0.077|
|||WRN-26-10|0.771|0.771|0.498|0.325|0.140|0.071|
|||DenseNet-121|0.289|0.289|0.734|0.294|0.345|0.087|
||CIFAR-100|ResNet-50|0.436|0.300|0.251|0.619|0.397|0.291|
|||ResNet-110|0.313|0.255|0.277|0.557|0.266|0.257|
|||WRN-26-10|0.273|0.255|0.256|0.625|0.287|0.280|
|||DenseNet-121|0.279|0.231|0.235|0.600|0.320|0.289|


Table 2: Top-label-ECE and top-label-MCE for deep-net models (above: ‘Base’) and various posthoc calibrators: temperature-scaling (TS), vector-scaling (VS), Dirichlet-scaling (DS), top-label-HB
(TL-HB), and normalized-HB (N-HB). Best performing method in each row is in bold.

|Metric|Dataset|Architecture|Base|TS|VS|DS|N-HB|CW-HB|
|---|---|---|---|---|---|---|---|---|
|Class- wise- ECE ˆ102|CIFAR-10|ResNet-50|0.46|0.42|0.35|0.35|0.50|0.28|
|||ResNet-110|0.59|0.50|0.42|0.38|0.53|0.27|
|||WRN-26-10|0.44|0.44|0.35|0.39|0.39|0.28|
|||DenseNet-121|0.46|0.46|0.36|0.36|0.48|0.36|
||CIFAR-100|ResNet-50|0.22|0.20|0.20|0.66|0.23|0.16|
|||ResNet-110|0.24|0.23|0.21|0.72|0.24|0.16|
|||WRN-26-10|0.19|0.19|0.18|0.61|0.20|0.14|
|||DenseNet-121|0.20|0.21|0.19|0.66|0.24|0.16|



Table 3: Class-wise-ECE for deep-net models and various post-hoc calibrators. All methods are
same as Table 2, except TL-HB is replaced with class-wise-HB (CW-HB).

4 EXPERIMENTS: M2B CALIBRATION WITH HISTOGRAM BINNING

Histogram binning or HB was proposed by Zadrozny and Elkan (2001) with strong empirical results
for binary calibration. In HB, a base binary calibration 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 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 results for binary calibration, 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). In our
experiments, we find that the issue is not HB but the M2B wrapper used to produce the HB baseline.
With the right M2B wrapper, HB beats TS, VS, and DS. A number of calibrators have been proposed
recently (Zhang et al., 2020; Rahimi 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 in these papers. We do not
compare to each of these calibrators; our focus is on the M2B reduction and the message that the
baselines dramatically improve with the right M2B wrapper.

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 that assesses the worst calibration
across predictions (see more details in Appendix E.3). For top-label calibration MCE is given by
wise calibration, we use class-wise-ECE defined as the average calibration error across classes:TL-MCEpc, hq :“ maxlPrLs suprPRangephq |P pY “ l | cpXq “ l, hpXq “ rq ´ r|. To assess class

-----

CW-ECEpc, hq :“ L[´][1][ ř][L]l“1 [E][X][ |][P] [p][Y][ “][ l][ |][ h][l][p][X][qq ´][ h][l][p][X][q][|][. All ECE/MCE estimation is per-]
formed as described in Remark 1. For further details, see Appendix E.2.

**Formal algorithm and theoretical guarantees. Top-label-HB (TL-HB) and class-wise-HB (CW-**
HB) 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 and CW-HB
(Theorems 1 and 2). We informally summarize one of the results here: if there are at least k calibration points-per-bin, then the expected-ECE is bounded as: E r(TL-) or (CW-) ECEs ď 1{2k,

for TL-HB and CW-HB respectively. The outer E above is an expectation over the calibration data,

a

and corresponds to the randomness in the predictor learnt on the calibration data. Note that the ECE
itself is an expected error over an unseen i.i.d. test-point pX, Y q „ P .

**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: ResNet50, Resnet-110, Wide-ResNet-26-10 (WRN) (Zagoruyko and Komodakis, 2016), and DenseNet121 (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 post-hoc 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?” We used their Brier score and focal loss models in_
our experiments (Mukhoti et al. (2020) report that these are the empirically best performing loss
functions). All results in the main paper are with Brier score, and results with focal loss are in
_Appendix E.4. Implementation details for TS, VS, and DS are in Appendix E._

**Findings. In Table 2, we report the binned ECE and MCE estimates when B “ 15 bins are used by**
HB, and for ECE estimation. We make the following observations:

(a) For TL-ECE, N-HB is the best performing method for both CIFAR-10 and CIFAR-100. While
most methods perform similarly across architectures for CIFAR-10, there is high variation in
CIFAR-100. DS is the worst performing method on CIFAR-100, but TL-HB also performs
poorly. We believe that this could be because the data splitting scheme of the TL-calibrator (line
4 of Algorithm 2) splits datasets across the predicted classes, and some classes in CIFAR-100
occur very rarely. This is further discussed in Appendix E.6.

(b) For TL-MCE, TL-HB is the best performing method on CIFAR-10, by a huge margin. For
CIFAR-100, TS or VS perform slightly better than TL-HB. Since HB ensures that each bin gets
roughly the same number of points, the predictions are well calibrated across bins, leading to
smaller TL-MCE. A similar observation was also made by 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 further 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.

**Additional experiments in the Appendix. In Appendix E.5, we report each of the results in Ta-**
bles 2 and 3 with the number of bins taking every value in the range r5, 25s. Most observations
remain the same under this expanded study. In Appendix B.2, we consider top-label calibration for
the class imbalanced COVTYPE-7 dataset, and show that TL-HB adapts to tail/infrequent classes.

5 CONCLUSION

We make two contributions to the study of multiclass calibration: (i) defining the new notion of
top-label calibration which enforces a natural minimal requirement on a multiclass predictor—the
probability score for the top class prediction should be calibrated; (ii) developing a multiclass-tobinary (M2B) framework which posits that various notions of multiclass calibration can be achieved
via reduction to binary calibration, balancing practical utility with statistically tractability. Since it
is important to identify appropriate notions of calibration in any structured output space (Kuleshov
et al., 2018; Gneiting et al., 2007), we anticipate that the philosophy behind the M2B framework
could find applications in other structured spaces.


-----

6 REPRODUCIBILITY STATEMENT

Some reproducibility desiderata, such as external code and libraries that were used are summarized
in Appendix E.1. All code to generate results with the CIFAR datasets 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.

7 ETHICS STATEMENT

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.

ACKNOWLEDGEMENTS

This work used the Extreme Science and Engineering Discovery Environment (XSEDE), which is
supported by National Science Foundation grant number ACI-1548562 (Towns et al., 2014). Specifically, it used the Bridges-2 system, which is supported by NSF award number ACI-1928147, at the
Pittsburgh Supercomputing Center (PSC). CG’s research was supported by the generous Bloomberg
Data Science Ph.D. Fellowship. CG would like to thank Saurabh Garg and Youngseog Chung for
interesting discussions, and Viveka Kulharia for help with the focal calibration repository. Finally,
we thank Zack Lipton, the ICLR reviewers, and the ICLR area chair, for excellent feedback that
helped improve the writing of the paper.

REFERENCES

Jock A Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and
_electronics in agriculture, 24(3):131–151, 1999._

Leo Breiman, Jerome H Friedman, Richard A Olshen, and Charles J Stone. Classification and
_regression trees. Routledge, 2017._

Luc Devroye. The equivalence of weak, strong and complete convergence in L1 for kernel density
estimates. The Annals of Statistics, 11(3):896–904, 1983.

Luc Devroye. Automatic pattern recognition: A study of the probability of error. IEEE Transactions
_on pattern analysis and machine intelligence, 10(4):530–543, 1988._

Tilmann Gneiting, Fadoua Balabdaoui, and Adrian E Raftery. Probabilistic forecasts, calibration
and sharpness. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 69(2):
243–268, 2007.

Louis Gordon and Richard A Olshen. Almost surely consistent nonparametric regression from
recursive partitioning schemes. Journal of Multivariate Analysis, 15(2):147–163, 1984.

Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural
networks. In International Conference on Machine Learning, 2017.


-----

Chirag Gupta and Aaditya Ramdas. Distribution-free calibration guarantees for histogram binning
without sample splitting. In International Conference on Machine Learning, 2021.

Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution-free binary classification:
prediction sets, confidence intervals and calibration. In Advances in Neural Information Process_ing Systems, 2020._

Kartik Gupta, Amir Rahimi, Thalaiyasingam Ajanthan, Thomas Mensink, Cristian Sminchisescu,
and Richard Hartley. Calibration of neural networks using splines. In International Conference
_on Learning Representations, 2021._

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
2016.

Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected
convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern
_Recognition, 2017._

Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In Innovations in Theoretical Computer Science, 2017.

Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical Report, Univer_sity of Toronto, 2009._

Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning
using calibrated regression. In International Conference on Machine Learning, 2018.

Meelis Kull, Telmo M. Silva Filho, and Peter Flach. Beyond sigmoids: How to obtain wellcalibrated probabilities from binary classifiers with beta calibration. Electronic Journal of Statis_tics, 11(2):5052–5080, 2017._

Meelis Kull, Miquel Perello-Nieto, Markus K¨angsepp, Hao Song, and Peter Flach. Beyond temperature scaling: Obtaining well-calibrated multiclass probabilities with Dirichlet calibration. In
_Advances in Neural Information Processing Systems, 2019._

Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in
_Neural Information Processing Systems, 2019._

Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain. Trainable calibration measures for neural networks
from kernel mean embeddings. In International Conference on Machine Learning, 2018.

G´abor Lugosi and Andrew Nobel. Consistency of data-driven histogram methods for density estimation and classification. Annals of Statistics, 24(2):687–706, 1996.

Jishnu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip HS Torr, and Puneet K
Dokania. Calibrating deep neural networks using focal loss. In Advances in Neural Information
_Processing Systems, 2020._

Alexandru Niculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised learning. In International Conference on Machine Learning, 2005.

Jeremy Nixon, Michael W Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measuring calibration in deep learning. arXiv preprint arXiv:1904.01685, 2020.

Andrew Nobel. Histogram regression estimation using data-dependent partitions. The Annals of
_Statistics, 24(3):1084–1105, 1996._

Kanil Patel, William Beluch, Bin Yang, Michael Pfeiffer, and Dan Zhang. Multi-class uncertainty
calibration via mutual information maximization-based binning. In International Conference on
_Learning Representations, 2021._

John C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized
likelihood methods. In Advances in Large Margin Classifiers, pages 61–74. MIT Press, 1999.


-----

Aleksandr Podkopaev and Aaditya Ramdas. Distribution-free uncertainty quantification for classification under label shift. In Uncertainty in Artificial Intelligence, 2021.

Jian Qian, Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Concentration inequalities for
multinoulli random variables. arXiv preprint arXiv:2001.11595, 2020.

Amir Rahimi, Amirreza Shaban, Ching-An Cheng, Richard Hartley, and Byron Boots. Intra orderpreserving functions for calibration of multi-class neural networks. In Advances in Neural Infor_mation Processing Systems, 2020._

Rebecca Roelofs, Nicholas Cain, Jonathon Shlens, and Michael C Mozer. Mitigating bias in calibration error estimation. arXiv preprint arXiv:2012.08668, 2020.

J. Towns, T. Cockerill, M. Dahan, I. Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop,
D. Lifka, G. D. Peterson, R. Roskies, J. Scott, and N. Wilkins-Diehr. XSEDE: Accelerating
Scientific Discovery. Computing in Science & Engineering, 16(5):62–74, 2014.

Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and
Thomas B Sch¨on. Evaluating model calibration in classification. In International Conference
_on Artificial Intelligence and Statistics, 2019._

Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the L1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep,
2003.

David Widmann, Fredrik Lindsten, and Dave Zachariah. Calibration tests in multi-class classification: a unifying framework. In Advances in Neural Information Processing Systems, 2019.

Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees
and naive Bayesian classifiers. In International Conference on Machine Learning, 2001.

Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass probability estimates. In International Conference on Knowledge Discovery and Data Mining, 2002.

Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision
_Conference, 2016._

Jize Zhang, Bhavya Kailkhura, and T Han. Mix-n-match: Ensemble and compositional methods for
uncertainty calibration in deep learning. In International Conference on Machine Learning, 2020.


-----

**Algorithm 5: Post-hoc calibrator for a given M2B calibration notion C**
**Input: Base (uncalibrated) multiclass predictor g, calibration data**
_X1, Y1_ _, . . .,_ _Xn, Yn_, binary calibrator
_D “ p_ q p q
_At0,1u : r0, 1s[X]_ ˆ pX ˆ t0, 1uq[‹] Ñ r0, 1s[X]

**1 K Ð number of distinct calibration claims that C verifies;**

**2 for each claim k P rKs do**

**34** Fromk **g, inferXi, Z pic,** _g, whereq Ð plabel-predictor Zi_ 1 _Yi_ _, probability-predictorc_ _Xi_ ; q corresponding to claim k;

**5** _Dif conditioning does not include class prediction Ð tp_ qu Ð t “ p qu _c then_

r r

**6** — (confidence, top-K-confidence, and class-wise calibration) —

r

**7** _hk_ 0,1 _g,_ _k_ ;
Ð At up _D_ q r

**8** **end**

**9** **else** r

**10** — (top-label and top-K-label calibration) —

**11** **for l P rLs do**

**1213** _Dhk,lk,l Ð Ð tp AtX0,1iu, Zpg,iq P Dk,l Dqk; :_ _cpXiq “ lqu;_

**14** **end** r

**15** _hkp¨q Ð hk,cp¨q[p¨q][ (]r[h]k_ [predicts][ h]k,l[p][x][q][ if][ r]cpxq “ l);

**16** **end**

r

**17 end**

**18 — (the new predictor replaces each** _g with the corresponding hk) —_

**19 return plabel-predictor, hkq corresponding to each claim k P rKs;**

r

**Input for Algorithms 6 and 7: base multiclass predictor g : X Ñ ∆[L][´][1], calibration data D “**
pX1, Y1q, . . ., pXn, Ynq, binary calibrator At0,1u : r0, 1s[X] ˆ pX ˆ t0, 1uq[‹] Ñ r0, 1s[X] .

**Algorithm 6: Top-K-label calibrator**


**1 For every k P rKs, infer from g the k-th**
largest class predictor c[p][k][q] and the
associated probability g[p][k][q];

**2 for k Ð 1 to K do**

**34** **for l Ðk,l 1 to LX doi, 1** _Yi_ _l_ :

_D_ Ð tp t “ uq
_c[p][k][q]_ _Xi_ _l_ ;
p q “ u

**5** _h[p][k,l][q]_ Ð At0,1upg[p][k][q], Dk,lq;

**6** **end**

**7** _h[p][k][q]_ Ð h[p][k,c][p][k][q][p¨qq]p¨q;

**8 end**

**9 return ph[p][1][q], h[p][2][q], . . ., h[p][K][q]q;**


**Algorithm 7: Top-K-confidence calibrator**

**1 For every k P rKs, infer from g the k-th**
largest class predictor c[p][k][q] and the
associated probability g[p][k][q];

**23 for k Ðk** 1 to KXi do, 1 _Yi_ _l_ : i _n_ ;

_D_ Ð tp t “ uq P r su

**4** _h[p][k][q]_ Ð At0,1upg[p][k][q], Dkq;

**5 end**

**6 return ph[p][1][q], h[p][2][q], . . ., h[p][K][q]q;**


A ADDENDUM TO SECTION 3 “CALIBRATION ALGORITHMS FROM
CALIBRATION METRICS”

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.


-----

(a) Predictions of a fixed base model
**g : X Ñ ∆[3]** on calibration/test data
_D “ tpa, 3q, pb, 4q, . . ., pf, 1qu._

(b) Confidence calibration


(d) Class-wise calibration

(c) Top-label calibration


(e) Canonical calibration


Figure 3: Illustrative example for Section A.2. The numbers in plot (a) correspond to the predictions
made by g on a dataset D. If D were a test set, plots (b–e) show how it should be used to verify if g
satisfies the corresponding notion of calibration. Consequently, we argue that if D were a calibration
set, and we want to achieve one of the notions (b–e), then the data shown in the corresponding plots
should be the data used to calibrate g as well.

A.1 GENERAL-PURPOSE M2B CALIBRATOR

Denote some M2B notion of calibration as C. Suppose C corresponds to K 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 g _k_ .
p q
Additionally, there may be conditioning on the label predictor such as c or cpkq. These are denoted
as pc, _gq in Algorithm 5. For confidence and top-label calibration,_ _c “ c, the top-label-confidence._
For class-wise calibration, when _g_ _gl, we have_ _c_ _l._
“ p¨q “

If there is no label conditioning in the calibration notion, such as in confidence, top-r r r _K-confidence,_
and class-wise calibration, then we enter the if-condition inside the for-loop. Here r r _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,l_ _x_ if _c_ _x_ _l._
p q p q “

Finally, since C is verifying a sequence of claims, the output of Algorithm 5 is a sequence of predictors. Each original prediction r _c,_ _g_ corresponding to the is replaced with _c, hk_ . This is the
p q _C_ p q
output of the M2B calibrator. Note that the _c values are not changed. This output appears abstract,_
but normally, it can be represented in an interpretable way. For example, for class-wise calibration,
r r r
the output is just a sequence of predictors, one for each class: _h1, h2, . . ., hL_ .
r p q

This general-purpose M2B calibrators can be used to achieve any M2B calibration notion: toplabel calibration (Algorithm 2), class-wise calibration (Algorithm 3), confidence calibration (Algorithm 1), top-K-label calibration (Algorithm 6), and top-K-confidence calibration (Algorithm 7).

A.2 AN EXAMPLE TO ILLUSTRATE THE PHILOSOPHY OF M2B CALIBRATION

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;**

**34 for l Ðl** 1 to LX doi, 1 _Yi_ _l_ : c _Xi_ _l_ and nl _l_ ;

**65 endDhl Ð Ð tp Binary-histogram-binning t** “ uq p q “pg, Dqul, tnl{ku, δ Ðq; |D _|_

**7 hp¨q Ð hcp¨qp¨q;**

**8 return pc, hq;**

Verifying top-label calibration is similar (Figure 3c), but in addition to the predictionsretain the values of cp¨q. Thus the gp¨q and 1 tY “ cp¨qu are shown, but split across the 4 classes. gp¨q, we also
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.

B DISTRIBUTION-FREE TOP-LABEL CALIBRATION USING HISTOGRAM
BINNING

In this section, we formally describe histogram binning (HB) with the top-label-calibrator (Algorithm 2) and provide methodological insights through theory and experiments.

B.1 FORMAL ALGORITHM AND THEORETICAL GUARANTEES

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 1 _Yi_ _c_ _Xi_ : Xi
Bin bu. This is an estimate of the bias of the bin P pY “ cpXq | X P Bin t t bq. A concentration “ p qu P
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 ´ α. (8)
´ ¯

(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 ´ α.
´ ¯ (9)

To clarify, all probabilities are taken over the test point pX, Y q „ P, the calibration data D „ P _[n],_
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_ _L_ _. Then, for any α_ 0, 1 _, Algorithm 8 is_ _ε1, α_ _-marginally and_ _ε2, α_ _-_
_conditionally top-label calibrated for ě_ P r s P p q p q p q


log 2 _α_
p { q _and_ _ε2_
2 _k_ 1 “
p ´ q [`][ δ,]


log 2n _kα_
p { q _δ._ (10)

2 _k_ 1 `
p ´ q


_ε1_
“


_Further, for any distribution P over_ _L_ _, we have P_ _TL-ECE_ _c, h_ _ε2_ 1 _α, and_
_X ˆ r_ s p p q ď q ě ´
E rTL-ECEpc, hqs ď 1{2k ` δ.

The proof in Appendix H is a multiclass top-label adaption of the guarantee in the binary setting bya
Gupta and Ramdas (2021). The _Op1{?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 E TL-ECE _h_ 0.1. Base on this, we suggest setting k 50, 150 in practice.
_D r_ p qs ď [r] P r s

B.2 TOP-LABEL HISTOGRAM BINNING ADAPTS TO CLASS IMBALANCED DATASETS

The principled methodology of fixing the number of points per bin reaps practical benefits. 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 F show that the RF is always underconfident no matter which class is predicted as the
top-label. HB (in green) recalibrates the RF effectively across all classes. Validity plots (Gupta and
Ramdas, 2021) estimate how the LHS of condition (8), 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


-----

|Class|ratio|Class ratio|
|---|---|---|


3Class4 5 6


Class ratio

0.5

0.4

0.3

0.2Class ratio

0.1

0.0

|Ran|dom foRraenstdom foresHtistogram Hbiinsntoinggra|m binning|
|---|---|---|



Class 2 validity plot


Class 4 reliability diagram


Class 4 validity plot


0.200

0.175

0.150

0.125

0.100

0.075

0.050

0.025

0.000



1.0

0.8

0.6

0.4

0.2

0.0


0.200 0.200 1.0 1.0 0.5

0.175 0.175 0.8 0.8

0.6 0.6

0.150 0.150( )V 0.4 0.4 0.4 ( )V

0.125 0.125 0.2 True probability0.2

0.3

ECE0.100 0.0 0.0

Class ratio



|Col1|Col2|Col3|Col4|Col5|1.0|Col7|Col8|Col9|Col10|Col11|Col12|Col13|Col14|1.0|Col16|Col17|Col18|Col19|0|.5|Col22|1|.00 .8 .6|.5|Col26|Col27|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
||0.1|75|0.1|75|0.8 0.6||||||||ability|0.8 0.6||||||||0 0|||||
||0.1|50|0.1|50 V( ) 25|0.4 0.2||||||||True prob|0.4 0.2|||||0|.4||) V( 0 0|0 .4 .2|.4|||
||0.1|25|0.1||||||||||||||||||io|||o|||
||E||E||0.0|||||||||0.0|||||0|.3|rat|0|0.3 rati .0 0.00 0.05 0.10 0. Class i0n.2ts per bin. Cl at the TL-ECE g0n.i1ficantly high ing is quite unif|.3 rati|||
|0.100 EC .00 0.25 0.50 0 Predicted proba 0.075 op-label h ts. Al0g.0o5r0it CE o0.n0 2c5la es (4, 5, a 0.000|||.750.11.0 EC bility|000|0.0|0|0.05||0.10||0|.15||0|.00 P|0. re|25 0. dicted|50 prob|0.75 ability 0.2||1.00 Class||||||
||||ist0o.0g|7r5a|m|binn|in|g|(A||lgo|ri|thm|8|) w|i|th k||“ 1||00 po||||||
||||hm0. 08|5 a0d|||||||||||||||||||||||
||||||ap|ts a|nd|u|ses||o|nl|y a|sin|gle|b|in|to|ens 0.1 er h||ure th as si||||||
||||ss 2 0.0 nd 6)|. O 25, b|ve|rall|,|the|ra||nd|o|m f|ore|st|cl|ass|ifi|||||||||
||||||ut|the|po|st|-ca||lib|ra|tio|n T|L-|E|CE|u|sing 0.0||binn||||||


2 3 4 5 6 7


Class 2 reliability diagram

0.00 0.25 0.50 0.75 1.00

Predicted probability


Class 2 validity plot


Class 4 reliability diagram

0.00 0.25 0.50 0.75 1.00

Predicted probability


Class 4 validity plot


0.200

0.175

0.150

0.125

0.100

0.075

0.050

0.025

0.000


1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


0.5

0.4

0.3

0.2

0.1

0.0


0.0

0.00 0.05 0.10 0.15


0.0

0.00 0.05 0.10 0.15


Class4


(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 F, along with some additional observations.


C DISTRIBUTION-FREE CLASS-WISE CALIBRATION USING HISTOGRAM
BINNING

In this section, we formally describe histogram binning (HB) with the class-wise-calibrator (Algorithm 3) and provide theoretical guarantees for it. The overall procedure is called class-wise-HB.
Further details and background on HB are contained in Appendix B, where top-label-HB is described.


C.1 FORMAL ALGORITHM

To achieve class-wise calibration using binary routines, we learn each component function hl in a 1v-all fashion as described in Algorithm 3. Algorithm 9 contains the pseudocode with the underlying
routine as binary HB. To learn hl, we use a dataset _l, which unlike top-label HB (Algorithm 8),_
containsper binLarger values of k Xl can be different for different classes, but generally one would seti even if kl will lead to smaller cpXiq ‰ l. However the εl and Yi δ is replaced withl in the guarantees, at loss of sharpness since the D 1 tYi “ l ku. The number of points1 “ . . . “ kL “ k P N.
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 binparameter δ ą 0 k (say1, k2 10, . . ., k[´][10])** _l P N[L]_ (say each kl “ 50), tie-breaking

**Output: L class-wise calibrated predictors h1, h2, . . ., hL**

**12 for l Ðl** 1 to LX doi, 1 _Yi_ _l_ : i _n_ ;

**43 endhDl Ð Ð tp Binary-histogram-binning t** “ uq P r psqugl, Dl, tn{klu, δq;

**5 return ph1, h2, . . ., hLq;**

C.2 CALIBRATION GUARANTEES


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, 1s[L]. Define
the notation ε _ε1, ε2, . . ., εL_ 0, 1 and α _α1, α2, . . ., αL_ 0, 1 .
“ p q P p q[L] “ p q P p q[L]
**Definition 2 (Marginal and conditional class-wise calibration). Let ε, α P p0, 1q[L]** 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_ _Y_ _l_ _hl_ _X_ _hl_ _X_ _εl_ 1 _αl._ (11)
_|_ p “ | p qq ´ p q| ď ě ´
´ ¯

(b) pε, αq-conditionally class-wise calibrated if for every distribution P over X ˆ rLs and for every
_l P rLs,_

_P_ _r_ Range _hl_ _,_ _P_ _Y_ _l_ _hl_ _X_ _r_ _r_ _εl_ 1 _αl._ (12)
@ P p q _|_ p “ | p q “ q ´ _| ď_ ě ´
´ ¯

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 _L_ . Let α _l_ 1 _[α][l][ and][ ε][ “][ max][l][Pr][L][s][ ε][l][. Then (11) implies]_
P r s “ “

_P_ _l_ _L_ _,_ _P_ _Y_ _l_ _hl_ _X_ _hl_ _X_ _ε_ 1 _α,_ (13)
@ P r[ř][L]s _|_ p “ | p qq ´ p q| ď ě ´
´ ¯

and (12) implies

_P_ _l_ _L_ _, r_ Range _hl_ _,_ _P_ _Y_ _l_ _hl_ _X_ _r_ _r_ _ε_ 1 _α._ (14)
@ P r s P p q _|_ p “ | p q “ q ´ _| ď_ ě ´
´ ¯

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 (13) (or (14)) is by using a union bound over (11) (or (12)).

We now state the distribution-free calibration guarantees satisfied by Algorithm 9.
_and assumeTheorem 2. n Fix hyperparametersl ě kl for every l P r δL ąs. Then, for every 0 (arbitrarily small) and points per bin l P rLs, for any αl P p0 k, 11q, k, Algorithm 9 is2, . . ., kl ě 2,_
pε[p][1][q], αq-marginally and pε[p][2][q], αq-conditionally class-wise calibrated with

log 2 _αl_ log 2n _klαl_

_ε[p]l[1][q]_ “ d 2 _kpl_ { 1q _and_ _ε[p]l[2][q]_ “ d 2pkl { 1 q ` δ. (15)

p ´ q [`][ δ,] p ´ q

_Further, for any distribution P over X ˆ rLs,_

_(a) P_ _CW-ECE_ _c, h_ maxl _L_ _ε[p]l[2][q]_ 1 _l_ _L_ _[α][l][, and]_
p p q ď Pr s q ě ´ Pr s

_(b) E_ _CW-ECE_ _c, h_ maxl _L_ 1 2kl _δ._
r p qs ď Pr s { ` [ř]
a


-----

Theorem 2 is proved in Appendix H. The proof follows by using the result of Gupta and Ramdas
(2021, Theorem 2), derived in the binary calibration setting, for each hl separately. 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-CW-ECE.

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.

D FIGURES FOR APPENDIX E

Appendix E begins on page 23. The relevant figures for Appendix E are displayed on the following
pages.


-----

ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.0275

0.0250

0.0225

0.0200

0.0175

0.0150

0.0125

0.0100


0.026

0.024

0.022

0.020

0.018

0.016

0.014


0.0300

0.0275

0.0250

0.0225

0.0200

0.0175

0.0150


0.0300

0.0275

0.0250

0.0225

0.0200

0.0175

0.0150

0.0125


(a) TL-ECE estimates on CIFAR-10 with Brier score. TL-HB is close to the best in each case. While CW-HB
performs the best atResNet-50 _B “ 15, the ECE estimate may not be reliable since it is highly variable across bins.ResNet-110_ Wide-ResNet-26-10 DenseNet-121


0.35

0.30

0.25

0.20

0.15

0.10


0.30

0.25

0.20

0.15

0.10


0.30

0.25

0.20

0.15

0.10


0.30

0.25

0.20

0.15

0.10


10 15 20 25

Number of bins


10 15 20 25

Number of bins


10 15 20 25

Number of bins


10 15 20 25

Number of bins


(b) TL-ECE estimates on CIFAR-100 with Brier score. N-HB is the best performing method, while DS is the
worst performing method, across different numbers of bins. TL-HB performs worse than TS and VS.


ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.0


0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1


0.5

0.4

0.3

0.2

0.1


0.7

0.6

0.5

0.4

0.3

0.2

0.1


(c) TL-MCE estimates on CIFAR-10 with Brier score. The only reliably and consistently well-performing
method is TL-HB.


ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1


0.6

0.5

0.4

0.3

0.2


0.6

0.5

0.4

0.3

0.2


0.6

0.5

0.4

0.3

0.2


(d) TL-MCE estimates on CIFAR-100 with Brier score. DS is the worst performing method. Other methods
perform across different values of B.

Figure 5: Table 2 style results with the number of bins varied as B P r5, 25s. See Appendix E.5 for
further details. The captions summarize the findings in each case. In most cases, the findings are
similar to those with B “ 15. The notable exception is that performance of N-HB on CIFAR-10 for
TL-ECE while very good at B “ 15, is quite inconsistent when seen across different bins. In some
cases, the blue base model line and the orange temperature scaling line coincide. This occurs since
the optimal temperature on the calibration data was learnt to be T “ 1, which corresponds to not
changing the base model at all.


-----

ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.055

0.050

0.045

0.040

0.035

0.030

0.025

0.020

0.015


0.050

0.045

0.040

0.035

0.030

0.025

0.020

0.015


0.045

0.040

0.035

0.030

0.025

0.020

0.015

0.010


0.040

0.035

0.030

0.025

0.020

0.015


(a) TL-ECE estimates on CIFAR-10 with focal loss. TL-HB is close to the best in each case. While CW-HB
performs the best atResNet-50 _B “ 15, the ECE estimate may not be reliable since it is highly variable across bins.ResNet-110_ Wide-ResNet-26-10 DenseNet-121

0.30

0.30 0.30

0.30

0.25

0.25 0.25

0.25


0.20

0.15

0.10


0.20

0.15

0.10

0.05


0.20

0.15

0.10

0.05


0.20

0.15

0.10

0.05


10 15 20 25

Number of bins


10 15 20 25

Number of bins


10 15 20 25

Number of bins


10 15 20 25

Number of bins


(b) TL-ECE estimates on CIFAR-100 with focal loss. N-HB is the best performing method, while DS is the
worst performing method, across different numbers of bins. TL-HB performs worse than TS and VS.


ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.0


0.7

0.6

0.5

0.4

0.3

0.2

0.1


0.8

0.6

0.4

0.2

0.0


0.5

0.4

0.3

0.2

0.1


(c) TL-MCE estimates on CIFAR-10 with focal loss. The only reliably and consistently well-performing
method is TL-HB.


ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.7

0.6

0.5

0.4

0.3

0.2


0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2


0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2


0.6

0.5

0.4

0.3

0.2


(d) TL-MCE estimates on CIFAR-100 with focal loss. DS is the worst performing method. Other methods
perform across different values of B.

Figure 6: Table 4 style results with the number of bins varied as B P r5, 25s. See Appendix E.5 for
further details. The captions summarize the findings in each case. In most cases, the findings are
similar to those with B “ 15. In some cases, the blue base model line and the orange temperature
scaling line coincide. This occurs since the optimal temperature on the calibration data was learnt
to be T “ 1, which corresponds to not changing the base model at all.


-----

ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


Wide-ResNet-26-10

|Col1|Col2|Col3|Col4|
|---|---|---|---|
|||||
|||||
|||||
|||||
|||||
|||||



10 15 20 25

Number of bins


0.007

0.006

0.005

0.004

0.003


0.008

0.007

0.006

0.005

0.004

0.003

0.002


0.007

0.006

0.005

0.004

0.003

0.002


0.0055

0.0050

0.0045

0.0040

0.0035

0.0030

0.0025


(a) CW-ECE estimates on CIFAR-10 with Brier score. CW-HB is the best performing method across bins, and
N-HB is quite unreliable.


ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.006

0.005

0.004

0.003

0.002

0.001


0.007

0.006

0.005

0.004

0.003

0.002

0.001


0.006

0.005

0.004

0.003

0.002

0.001


0.006

0.005

0.004

0.003

0.002

0.001


(b) CW-ECE estimates on CIFAR-100 with Brier score. CW-HB is the best performing method. DS and N-HB
are the worst performing methods.

Figure 7: Table 3 style results with the number of bins varied as B P r5, 25s. The captions summarize
the findings in each case, which are consistent with those in the table. See Appendix E.5 for further
details.


ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.010

0.009

0.008

0.007

0.006

0.005

0.004

0.003

0.002


0.009

0.008

0.007

0.006

0.005

0.004

0.003

0.002


0.010

0.008

0.006

0.004

0.002


0.010

0.008

0.006

0.004


(a) CW-ECE estimates on CIFAR-10 with focal loss. CW-HB is the best performing method across bins, and
N-HB is quite unreliable.


ResNet-50

10 15 20 25

Number of bins


ResNet-110

10 15 20 25

Number of bins


Wide-ResNet-26-10

10 15 20 25

Number of bins


DenseNet-121

10 15 20 25

Number of bins


0.006

0.005

0.004

0.003

0.002

0.001


0.006

0.005

0.004

0.003

0.002

0.001


0.006

0.005

0.004

0.003

0.002

0.001


0.006

0.005

0.004

0.003

0.002

0.001


(b) CW-ECE estimates on CIFAR-100 with focal loss. CW-HB is the best performing method. DS and N-HB
are the worst performing methods.

Figure 8: Table 5 style results with the number of bins varied as B P r5, 25s. The captions summarize
the findings in each case, which are consistent with those in the table. See Appendix E.5 for further
details.


-----

E ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS FOR CIFAR-10 AND
CIFAR-100

We present additional details and results to supplement the experiments with CIFAR-10 and CIFAR100 in Sections 2 and 4 of the main paper.

E.1 EXTERNAL LIBRARIES USED

All our base models were pre-trained deep-net models generated by Mukhoti et al. (2020), obtained
from www.robots.ox.ac.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 E.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.

E.2 FURTHER COMMENTS ON BINNING FOR ECE ESTIMATION

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 with B “ 15, which has been commonly used 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 varying B 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.

E.3 SOME REMARKS ON MAXIMUM-CALIBRATION-ERROR (MCE)

Guo et al. (2017) defined MCE with respect to confidence calibration, as follows:

conf-MCEpc, hq :“ _rPRangesupphq_ _|P_ pY “ cpXq | hpXq “ rq ´ r| . (16)

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 (16): 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


-----

|Metric|Dataset|Architecture|Base|TS|VS|DS|N-HB|TL-HB|
|---|---|---|---|---|---|---|---|---|
|Top- label- ECE|CIFAR-10|ResNet-50|0.022|0.023|0.018|0.019|0.023|0.019|
|||ResNet-110|0.025|0.024|0.022|0.021|0.020|0.020|
|||WRN-26-10|0.024|0.019|0.016|0.017|0.019|0.018|
|||DenseNet-121|0.023|0.023|0.021|0.021|0.025|0.021|
||CIFAR-100|ResNet-50|0.109|0.107|0.107|0.332|0.086|0.148|
|||ResNet-110|0.124|0.117|0.105|0.316|0.115|0.153|
|||WRN-26-10|0.100|0.100|0.101|0.293|0.074|0.135|
|||DenseNet-121|0.106|0.108|0.105|0.312|0.091|0.147|
|Top- label- MCE|CIFAR-10|ResNet-50|0.298|0.443|0.368|0.472|0.325|0.082|
|||ResNet-110|0.378|0.293|0.750|0.736|0.535|0.089|
|||WRN-26-10|0.741|0.582|0.311|0.363|0.344|0.075|
|||DenseNet-121|0.411|0.411|0.243|0.391|0.301|0.099|
||CIFAR-100|ResNet-50|0.289|0.355|0.234|0.640|0.322|0.273|
|||ResNet-110|0.293|0.265|0.274|0.633|0.366|0.272|
|||WRN-26-10|0.251|0.227|0.256|0.663|0.229|0.270|
|||DenseNet-121|0.237|0.225|0.239|0.597|0.327|0.248|


Table 4: Top-label-ECE and top-label-MCE for deep-net models and various post-hoc calibrators.
All methods are same as Table 2. Best performing method in each row is in bold.

MCE, we can consider the top-label-MCE, defined as

TL-MCE _c, h_ : max sup _P_ _Y_ _l_ _c_ _X_ _l, h_ _X_ _r_ _r_ _._ (17)
p q “ _lPrLs_ _rPRangephq_ _|_ p “ | p q “ p q “ q ´ _|_

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.

E.4 TABLE 2 AND 3 STYLE RESULTS WITH FOCAL LOSS

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

E.5 ECE AND MCE ESTIMATES WITH VARYING NUMBER OF BINS

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


-----

|Metric|Dataset|Architecture|Base|TS|VS|DS|N-HB|CW-HB|
|---|---|---|---|---|---|---|---|---|
|Class- wise- ECE ˆ102|CIFAR-10|ResNet-50|0.42|0.42|0.35|0.37|0.52|0.35|
|||ResNet-110|0.48|0.44|0.36|0.35|0.51|0.29|
|||WRN-26-10|0.41|0.31|0.31|0.35|0.49|0.27|
|||DenseNet-121|0.41|0.41|0.40|0.39|0.63|0.30|
||CIFAR-100|ResNet-50|0.22|0.20|0.20|0.66|0.23|0.16|
|||ResNet-110|0.24|0.23|0.21|0.72|0.24|0.16|
|||WRN-26-10|0.19|0.19|0.18|0.61|0.20|0.14|
|||DenseNet-121|0.20|0.21|0.19|0.66|0.24|0.16|


Table 5: Class-wise-ECE for deep-net models and various post-hoc calibrators. All methods are
same as Table 2, except top-label-HB is replaced with class-wise-HB or Algorithm 3 (CW-HB).
Best performing method in each row is in bold.

Table 4) and Figure 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.

E.6 ANALYZING THE POOR PERFORMANCE OF TL-HB ON CIFAR-100

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.

F ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS FOR COVTYPE-7

We present additional details and results for the top-label HB experiment of Section B.2. The base
classifier is an RF learnt using sklearn.ensemble import 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 Range _hl_, the bins are defined as _x : c_ _x_ _l, hl_ _x_ _r_ .
P p q t p q “ p q “ u
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.


-----

Class 1 reliability diagram


Class 1 validity plot


Class 1 reliability diagram


Class 1 validity plot


1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


0.0

0.00 0.05 0.10 0.15


0.0

0.00 0.05 0.10 0.15


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 2 reliability diagram


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 2 reliability diagram


Class 2 validity plot


Class 2 validity plot


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2


0.0

0.00 0.05 0.10 0.15


0.0

0.00 0.05 0.10 0.15


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 3 reliability diagram


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 3 reliability diagram


Class 3 validity plot


Class 3 validity plot


1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


0.0

0.00 0.05 0.10 0.15


0.0

0.00 0.05 0.10 0.15


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 4 reliability diagram


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 4 reliability diagram


Class 4 validity plot


Class 4 validity plot


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2


0.0

0.00 0.05 0.10 0.15


0.0

0.00 0.05 0.10 0.15


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 5 reliability diagram


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 5 reliability diagram


Class 5 validity plot


Class 5 validity plot


1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2

0.0

1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


0.0

0.00 0.05 0.10 0.15


0.0

0.00 0.05 0.10 0.15


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 6 reliability diagram


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 6 reliability diagram


Class 6 validity plot


Class 6 validity plot


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2


0.0

0.00 0.05 0.10 0.15


0.0

0.00 0.05 0.10 0.15


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 7 reliability diagram


0.00 0.25 0.50 0.75 1.00

Predicted probability

Class 7 reliability diagram


Class 7 validity plot


Class 7 validity plot


1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2

0.0


1.0

0.8

0.6

0.4

0.2


0.0

0.00 0.05 0.10 0.15


0.0

0.00 0.05 0.10 0.15


0.00 0.25 0.50 0.75 1.00

Predicted probability


0.00 0.25 0.50 0.75 1.00

Predicted probability


(a) Top-label HB with k “ 100 points per bin.


(b) Top-label HB with B “ 50 bins per class.


Figure 9: Top-label histogram binning (HB) calibrates a miscalibrated random-forest on the class
imbalanced COVTYPE-7 dataset. For the less likely classes (4, 5, and 6), the left column is better calibrated than the right column. Similar observations are made on other datasets, and so we
recommend adaptively choosing a different number of bins per class, as Algorithm 8 does.


-----

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.

G BINNING-BASED CALIBRATORS FOR CANONICAL MULTICLASS
CALIBRATION

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**
∆[L][´][1], where el corresponds to the l-th canonical basis vector in R[d]. Recall that a predictor “ **h P “**
_h1, h2, . . ., hL_ is said to be canonically calibrated if P _Y_ _l_ **h** _X_ _hl_ _X_ for every l _L_ .
p q p “ | p qq “ p q P r s
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 H 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_ pred _X_ _hl_ _X_ should simultaneously be true. On the other hand, M2B notions verify only
| p qq “ p q
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][´][1]q “ 2[Θ][p][L][q], there will either be a bin whose volume is 2[Ω][p][L][q] (meaning that h would


-----

not be sharp), or the number of bins will be 2[Ω][p][L][q], entailing 2[Ω][p][L][q] 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 g _Xi_ values:
p q
for every b P rBs, Tb :“ ti : BpgpXiqq “ bu, nb “ |Tb| .
We then compute the following estimates for the label probabilities in each bin:

_i_ _Tb_ [1][ t][Y][i][ “][ l][u]

for every _l, b_ _L_ _B_ _,_ Πl,b : P if nb 0 else Πl,b 1 _B._
p q P r s ˆ r s “ _nb_ ą “ {

ř

The binning predictor h : ∆[L][´][1] is now defined component-wise as follows:
_X Ñ_ [p] [p]

for every l P rLs, hlpxq “ Πl,Bpxq.

In words, for every bin b P rBs, h predicts the empirical distribution of the Y values in bin b.

[p]

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 G.1) and grid-style binning
(Appendix G.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 g _Xi_ values,
p q
there is no obvious ordering for the multi-dimensional g _Xi_ values. In Appendix G.3 we describe
p q
a projection based histogram binning scheme that circumvents this issue and ensures that each nb
is reasonably large. In Appendix G.4, we present some preliminary experimental results using our
proposed binning schemes.

Certain asymptotic consistency results different from calibration have been established for histogram
regression and classification in the nonparametric statistics literature (Nobel, 1996; Lugosi and 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.

G.1 SIERPINSKI BINNING

First, we describe Sierpinski binning for L “ 3. The probability simplex for L “ 3, ∆[2], is a triangle
with vertices e1 1, 0, 0, e2 0, 1, 0, and e3 0, 0, 1 . Sierpinski binning is a recursive
partitioning of this triangle based on the fractal popularly known as the Sierpinski triangles. Some “ p q “ p q “ p q
Sierpinski bins for L “ 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:_

1 if s1 0.5

_Bpsq “_ $ 23 ifif s s23 ą ą 0 0..55 (18)

’& 4 otherwise. ą

’


-----

∆[2] _q “ 1_ _q “ 2_ _q “ 3_

Figure 10: Sierpinski binning for L “ 3. The leftmost triangle represents the probability simplex
∆[2]. Sierpinski binning divides ∆[2] recursively based on a depth parameter q P N.

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 4, define the bins bi **s :** **s** _i_ . Consider the bin b1. Let us
_reparameterize it as_ _t1, t2 P r, t3_ s 2s1 1, 2s2, 2s3 “ t. It can be verified that Bp q “ u
p q “ p ´ q

_b1_ _t1, t2, t3_ : s1 0.5 _t1, t2, t3_ : t1 _t2_ _t3_ 1, t1 0, 1 _, t2_ 0, 1 _, t3_ 0, 1 _._
“ tp q ą u “ tp q ` ` “ P p s P r q P r qu

Based on this reparameterization, we can recursively sub-partition b1 as per the scheme (18), replacing s with t. Such reparameterizations can be defined for each of the bins defined in (18):

_b2_ _s1, s2, s3_ : s2 0.5 : _t1, t2, t3_ 2s1, 2s2 1, 2s3 _,_
“ tp q ą u p q “ p ´ q
_b3_ _s1, s2, s3_ : s3 0.5 : _t1, t2, t3_ 2s1, 2s2, 2s3 1 _,_
“ tp q ą u p q “ p ´ q
_b4_ _s1, s2, s3_ : si 0.5 for all i : _t1, t2, t3_ 1 2s1, 1 2s2, 1 2s3 _,_
“ tp q ď u p q “ p ´ ´ ´ q

and thus every bin can be recursively sub-partitioned as per (18). As illustrated in Figure 10, for
Sierpinski binning, we sub-partition only the bins 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 p3[q][`][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 “_ _lL_ 1 ifotherwise. sl ą 0.5, (19)
" `

While this looks similar to the partitioning (18), the main difference is that the bin bL 1 has a
`
larger volume than other bins. Indeed for l P rLs, volpblq “ volp∆[L][´][1]q{2[L][´][1], while volpbL`1q “
volp∆[L][´][1]qp1 ´ L{2[L][´][1]q ě volp∆[L][´][1]q{2[L][´][1], with equality only occuring for L “ 3. Thus the
bin bL 1 is larger than the other bins. If g _x_ _bL_ 1, then the prediction for x may be not be
` p q P `
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_ _s1, s2, . . ., sL_ : sl 0.5 : _t1, t2, . . ., tL_ 2s1, . . ., 2sl 1, . . ., 2sL _._
“ tp q ą u p q “ p ´ q

For every l P rLs, under the reparameterization above, it is straightforward to verify that

_t1, t2, . . ., tL_ : sl 0.5 _t1, t2, . . ., tL_ : _tu_ 1, tl 0, 1 _, tu_ 0, 1 _u_ _l_ _._
tp q ą u “ tp q _uÿPrLs_ “ P p s P r q @ ‰ u

Thus every bin can be recursively sub-partitioned following (19). For Sierpinski binning with L
labels, the number of bins at depth q is given by pL[q][`][1] ´ 1q{pL ´ 1q.


-----

0.75


0.25


0.8

0.2 0.8

0.4 0.6

0.6 0.4


0 0.2 0.4 0.6 0.8


0.2


0.25 0.75

0.5 0.5


0.25 0.5


0.75


Class 2

_K “ 4, τ “ 0.25_


Class 2

_K “ 5, τ “ 0.2_


Figure 11: Grid-style binning for L “ 3.

G.2 GRID-STYLE BINNING


Grid-style binning is motivated from the 2D reliability diagrams of Widmann et al. (2019, Figure 1),
where they partitioned ∆[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 N[L]_ : maxpL, K ` 1q ď _lPrÿLs_ _kl ď K ` pL ´ 1qu,_ (20)

define the bins
_bk :“ ts P ∆[L][´][1]_ : for every l P rLs, slK P rkl ´ 1, kls. (21)

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
Nthe corresponding element of[L]; say for k1 ‰ k2 P N, k k1 ă2 the one corresponding to k2 if and only if for the first element of k1 is smaller. Then define the binning k1 that is unequal to
function : ∆[L][´][1] _I_ as **s** min **k : s** _bk_ . The following propositions prove that a)
_B_ Ñ | _|_ _Bp_ q “ t P u
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 (21) mutually exhaust ∆[L][´][1].**


_Proof.Consider the condition Consider any s P ∆[L][´][1]. For slK R N “ t1, 2, . . .u, set kl “ maxp1, rslKsq ą slK._
_C : for all l such that slK R N, slK “ 0._

Ifset exactly one C is true, then for kl _l s such thatlK_ 1, and for the rest set slK P N, set kl “ s klKl . If s ClK is not true, then for. Based on this setting of l such that k, it can be slK P N,
verified that s _bk “._ ` “
P

Further, note that for every l, kl _slK, and there exists at least one l such that kl_ _slK. Thus we_
have: ě ą

_L_ _L_

_kl_ _slK_
_lÿ“1_ ą _lÿ“1_

“ K.

Since _l_ 1 _[k][l][ P][ N][, we must have][ ř]l[L]_ 1 _[k][l][ ě][ K][ `][ 1][. Further since each][ k][l][ P][ N][,][ ř]l[L]_ 1 _[k][l][ ě][ L][.]_
“ “ “

Next, note that for everyand for this[ř][L] _l, we have set l k, kll ď s slKlK ` s 1l. IfK_ _C 1 is true, then there is at least one. If C is not true, then either there exists at least one l such that slK P N,_
_l such that slK R N Y t0u for which “_ ă kl “ r `slKs ă 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_

_kl_ _slK_ 1
_lÿ“1_ ă _lÿ“1p_ ` q

“ K ` L.

Since _l_ 1 _[k][l][ P][ N][, we must have][ ř]l[L]_ 1 _[k][l][ ď][ K][ `][ L][ ´][ 1][.]_
“ “

[ř][L]


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 R[L][´][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 R[L]** _and v ą 0 such that u ` v∆[L][´][1]_ Ď bk.

_Proof. Fix some k_ _I. By condition (20),_ _l_ 1 _[k][l][ P r][max][p][L, K][ `][ 1][q][, K][ `][ L][ ´][ 1][s][. Based on this,]_
P “
we claim that there exists a τ P r0, 1q such that

_L_ [ř][L]

_kl_ 1 _τL_ 1 _τ_ _K._ (22)
_lÿ“1p_ ´ q ` ` p ´ q “

Indeed, note that for τ 0, _l_ 1[p][k][l][ ´][ 1][q `][ τL][ ` p][1][ ´][ τ] [q ď p][K][ ´][ 1][q `][ 1][ “][ K][ and for][ τ][ “][ 1][,]
_L_ “ “
_l_ 1[p][k][l][ ´][ 1][q `][ τL][ ` p][1][ ´][ τ] [q “][ ř][L]l 1 _[k][l][ ą][ K][. Thus, there exists a][ τ][ that satisfies (22) by the]_
“ “
intermediate value theorem. [ř][L]
ř

Next, define u “ K [´][1]pk ` pτ ´ 1q1Lq and v “ K [´][1]p1 ´ τ q ą 0, where 1L denotes the vector
in R[L] with each component equal to 1. Consider any s P u ` v∆[L][´][1]. Note that for every l P rLs,
_slK_ _kl_ 1, kl and by property (22),
P r ´ s

_L_ _L_ _L_

_slK_ _kl_ _τ_ 1 _v_ _kl_ 1 _τL_ 1 _τ_ _K._
_lÿ“1_ “ ˜lÿ“1p ` p ´ qq¸ ` “ _lÿ“1p_ ´ q ` ` p ´ q “

Thus, s ∆[L][´][1] and by the definition of bk, s _bk. This completes the proof._
P P

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.

G.3 PROJECTION BASED HISTOGRAM BINNING FOR CANONICAL CALIBRATION

Some of the bins defined by Sierpinski binning and grid-style binning may have very few calibration
points nb, leading to poor estimation of Π. 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 0, 1 . To ensure that each bin contains Ω _n_ _B_ points, we estimate the quantiles of g _X_
r s [p] p { q p q
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 R[L] with unit ℓ2-norm: _qi_ 2 1. Each of these vectors represents a direction
on which we will project´ P ∆[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
a unit vectordescribed in Algorithm 10. It uses the following new notation: given u, and an index j _m_, let order-statistics _v1, v2, . . ., v m vectorsm_ _, u, j v1, v2 denote the, . . ., vm P j R-th[L],_
P r s pt u q
order-statistics of tv1[T] _[u, v]2[T]_ _[u, . . ., v]m[T]_ _[u][u][.]_


-----

**Algorithm 10: Projection histogram binning for canonical calibration**


**Input: Base multiclass predictor g : X Ñ ∆[L][´][1], calibration data**
_X1, Y1_ _,_ _X2, Y2_ _, . . .,_ _Xn, Yn_
_D “ tp_ q p q p qu

**Output:Hyperparameter: Approximately calibrated scoring function number of bins B, unit vectors q h1, q2, . . ., qB P R[L],**

**1 S** **g** _X1_ _, g_ _X2_ _, . . ., g_ _Xn_ ;
Ð t p q p q p qu

**2 T Ð empty array of size B;**

**3 c Ð t** _[n]B[`][1]_ [u][;]

**4 for b Ð 1 to B ´ 1 do**

**5** _Tb_ order-statistics _S, qb, c_ ;
Ð p q

**6** _S_ _S_ _v_ _S : v[T]_ _qb_ _Tb_ ;

**7 end** Ð zt P ď u

**8 TB** 1.01;
Ð

**9** **g** min _b_ _B_ : g _qb_ _Tb_ ;
_Bp_ p¨qq Ð t P r s p¨q[T] ă u

**10** Π Ð empty matrix of size B ˆ L;

**11 for b Ð 1 to B do**

**12** **for l** 1 to L do

[p] Ð

**13** Πb,l Mean 1 _Yi_ _l_ : **g** _Xi_ _b and_ _s_ _B_ _, g_ _Xi_ _qs_ _Ts_ ;

**14** **end** Ð t t “ u _Bp_ p qq “ @ P r s p q[T] ‰ u

**15 end** p

**16 for l Ð 1 to L do**

**17** _hlp¨q Ð_ ΠBpgp¨qq,l;

**18 end**

**19 return h;** [p]

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 _qb, Tb_ pair corresponds to a hyperplane that cuts ∆[L][´][1] into two subsets given by
p q
_x_ ∆[L][´][1] : x[T] _qb_ _Tb_ and _x_ ∆[L][´][1] : x[T] _qb_ _Tb_ . The overall partitioning of ∆[L][´][1] is
tcreated by merging these cuts sequentially. This defines the binning function P ă u t P ě u _B. By construction,_
the binning function is such that each bin contains at least t _[n]B[`][1]_ [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 gpXiq[T] _qs “ Ts for some s P rBs. The interior points bins are then used to_
estimate the bin biases Π.

_n_
No matter how the q-vectors are chosen, the bins created by Algorithm 10 have at least _B_ 1 points

´
for bias estimation. However, we discuss some simple heuristics for setting[p] _q that are semantically_

X \

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:and so on. Projecting with respect to ´ qe1 “ ´l focuses on the classe1, q2 “ ´e2, . . ., q l by forming a bin corresponding toL “ ´eL, qL`1 “ ´e1, . . .,
the largest values of gl _Xi_ among the remaining Xi’s which have not yet been binned. (On the
p q
other hand, projecting with respect to el will correspond to forming a bin with the smallest values
of gl _Xi_ .)
p q

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.**
´

G.4 EXPERIMENTS WITH THE COVTYPE DATASET

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


-----

(a) Calibration using Sierpinski binning at depth q “ 2.

(b) Calibration using grid-style binning with K “ 5, τ “ 0.2.

(c) Projection-based HB with B “ 27 projections: q1 “ ´e1, q2 “ ´e2, . . ., q4, ´e1, . . ., and so on.

(d) Projection-based HB with B “ 27 random projections (qi drawn uniformly from the ℓ2-unit-ball in R[3]).

Figure 12: Canonical calibration using fixed and histogram binning on a 3-class version of the
COVTYPE-7 dataset. The reliability diagrams (left) indicate that all forms of binning improve the
calibration of the base logistic regression model. The recalibration diagrams (right) are a scatter plot
of the predictions gpXq on the test data with the points colored in 10 different colors depending on
their bin. For every bin, the arrow-tail indicates the mean probability predicted by the base model g
whereas the arrow-head indicates the probability predicted by the updated model h.

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.

H PROOFS

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.

H.1 STATEMENT AND PROOF OF PROPOSITION 4

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

H.2 PROOF OF THEOREM 1


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 _c, h_ .
p q

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
_Brequire is satisfied:l “ tnl{ku bins. We now apply the GR21 bounds on hl. First, we verify that the condition they_
_nl ě k tnl{ku ě 2Bl._


-----

Thus their marginal calibration bound for hl gives,

_P_ _P_ _Y_ _l_ _c_ _X_ _l, hl_ _X_ _hl_ _X_ _δ_

˜| p “ | p q “ p qq ´ p q| ď `

Note that since tnl{Blu “ tnl{ tnl{kuu ě k,


logp2{αq

2ptnl{Blu ´ 1q [|][ c][p][X][q “][ l]

logp2{αq

2ptnl{Blu ´ 1q _[.]_


ě 1 ´ α.


logp2{αq
2pk ´ 1q [ě][ δ][ `]


_ε1_ _δ_
“ `


Thus we have


_P_ _P_ _Y_ _l_ _c_ _X_ _l, hl_ _X_ _hl_ _X_ _ε1_ _c_ _X_ _l_ 1 _α._
p| p “ | p q “ p qq ´ p q| ď | p q “ q ě ´

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_ _Y_ _c_ _X_ _c_ _X_ _, h_ _X_ _h_ _X_ _ε1_
p| p “ p q | p q p qq ´ p q| ď q

_L_

_P_ _c_ _X_ _l_ _P_ _P_ _Y_ _c_ _X_ _c_ _X_ _, h_ _X_ _h_ _X_ _ε1_ _c_ _X_ _l_

“ _lÿ“1_ p p q “ q p| p “ p q | p q p qq ´ p q| ď | p q “ q

(law of total probability)


_P_ _c_ _X_ _l_ _P_ _P_ _Y_ _l_ _c_ _X_ _l, hl_ _X_ _hl_ _X_ _ε1_ _c_ _X_ _l_

“ _lÿ“1_ p p q “ q p| p “ | p q “ p qq ´ p q| ď | p q “ q

(by construction, if c _x_ _l, h_ _x_ _hl_ _x_ )
p q “ p q “ p q

_L_

ě _P_ pcpXq “ lqp1 ´ αq

_lÿ“1_

“ 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| ď _Bl{2nl ` δ_

“ atnl{ku {2nl ` δ
a1 2k _δ._

ď { `

Thus, a

E|P pY “ cpXq | cpXq, hlpXqq ´ hpXq|

_L_

“ _P_ pcpXq “ lqE|P pY “ l | cpXq “ l, hlpXqq ´ hlpXq| | cpXq “ l

_lÿ“1_


ď _P_ pcpXq “ lqp 1{2k ` δq

_lÿ“1_ a

“ 1{2k ` δ.
a

Next, we show the top-label conditional calibration bound. Let B _l_ 1 _[B][l][ and][ α][l][ “][ αB][l][{][B][.]_
“ “
Note that B _l_ 1 _[n][l][{][k][ “][ n][{][k][. The binary conditional calibration bound of GR21 gives]_
ď “

[ř][L]

[ř][L] log 2Bl _αl_

_P_ _r_ Range _hl_ _,_ _P_ _Y_ _l_ _c_ _X_ _l, hl_ _X_ _r_ _r_ _δ_ p { q

˜@ P p q _|_ p “ | p q “ p q “ q ´ _| ď_ ` d 2 tnl _Blu_ 1

p { ´ q [|][ c][p][X][q “][ l]

1 _αl._
ě ´

Note that


log 2Bl _αl_
p { q

2ptnl{Blu ´ 1q [“]


logp2B{αq

2ptnl{Blu ´ 1q


-----

log 2n _kα_
p { q (since B _n_ _k)_

ď d 2 tnl _Blu_ 1 ď {

p { ´ q

log 2n _kα_
p { q (since k tnl _Blu)._

ď d 2 _k_ 1 ď {

p ´ q

Thus for every l P rLs,

_P_ _r_ Range _hl_ _,_ _P_ _Y_ _l_ _c_ _X_ _l, hl_ _X_ _r_ _r_ _ε2_ 1 _αl._
p@ P p q _|_ p “ | p q “ p q “ q ´ _| ď_ q ě ´

By construction of h, conditioning on c _X_ _l and hl_ _X_ _r is the same as conditioning on_
p q “ p q “
_cpXq “ l and hpXq “ r. Taking a union bound over all L gives_

_P_ _l_ _L_ _, r_ Range _h_ _,_ _P_ _Y_ _c_ _X_ _c_ _X_ _l, h_ _X_ _r_ _r_ _ε2_
p@ P r s P p q _|_ p “ p q | p q “ p q “ q ´ _|q ď_ q

_L_

1 _αl_ 1 _α,_
ě ´ _lÿ“1_ “ ´

proving the conditional calibration result. Finally, note that if for every l P rLs, r P Rangephq,

_P_ _Y_ _c_ _X_ _c_ _X_ _l, h_ _X_ _r_ _r_ _ε2,_
_|_ p “ p q | p q “ p q “ q ´ _| ď_

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_ _c, h_ is bounded by ε2. (TL-MCE is defined in Ap´ p q
pendix E, equation (17).)


H.3 PROOF OF PROPOSITION 1

1Consider a specific tY “ lu. Canonical calibration implies l P rLs. We use hl to denote the l-th component function of h and Yl “

_P_ pY “ l | hpXqq “ E rYl | hpXqs “ hlpXq. (23)

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 (23))
_hl_ _X_ _._
“ p q

H.4 PROOF OF THEOREM 2

We use the bounds of Gupta and Ramdas (2021, Theorem 4) (henceforth called the GR21 bounds),
derived in the binary calibration setting, to conclude marginal, conditional, and ECE guarantees for
each 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 isthe GR21 bounds on hl. First, we verify that the condition they require is satisfied: n and the number of bins is Bl “ tn{klu bins. We now apply

_n ě kl tn{klu ě 2Bl._

Thus the GR21 marginal calibration bound gives that for every l P rLs, hl satisfies


log 2 _αl_
p { q

2ptn{Blu ´ 1q


_P_ _Y_ _l_ _hl_ _X_ _hl_ _X_ _δ_
_|_ p “ | p qq ´ p q| ď `


1 _αl._
ě ´


-----

The class-wise marginal calibration bound of Theorem 2 follows since tn{Blu “ tn{ tn{kluu ě kl,
and so


log 2 _αl_
p { q

2ptn{Blu ´ 1q _[.]_


_ε[p]l[1][q]_ _δ_
ě `


Next, the GR21 conditional calibration bound gives for every l P rLs, hl satisfies


log 2Bl _αl_
p { q

2ptn{Blu ´ 1q


_r_ Range _hl_ _,_ _P_ _Y_ _l_ _hl_ _X_ _r_ _r_ _δ_
@ P p q _|_ p “ | p q “ q ´ _| ď_ `


1 _αl._
ě ´


The class-wise marginal calibration bound of Theorem 2 follows sincetn{Blu “ tn{ tn{kluu ě kl, and so _Bl “ tn{klu ď n{kl and_


log 2Bl _αl_
p { q

2ptn{Blu ´ 1q _[.]_


_εl[p][2][q]_ _δ_
ě `


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 ď


_Bl_ 2nl _δ_
{ `

tn{klu {2n ` δ

1 2kl _δ_
{ `

1{2k ` δ.


Thus,


_L_

binary-ECE-for-class-l _hl_
_lÿ“1_ p qff

p 1{2k ` δq
a


_L[´][1]_


E rCW-ECEpc, hqs “ E


ď L[´][1]


_l“1_

“ 1{2k ` δ,

as required for the in-expectation CW-ECE bound of Theorem 2. Finally, for the high probabilitya
CW-ECE bound, let ε maxl _L_ _ε[p]l[2][q]_ and α _l_ 1 _[α][l][. By taking a union bound over the the]_
“ Pr s “ “
conditional calibration bounds for each hl, we have, with probability 1 _α, for every l_ _L_ and
´ P r s
_r_ Range _h_,

[ř][L]
P p q
_P_ _Y_ _l_ _c_ _X_ _l, h_ _X_ _r_ _r_ _ε[p]l[2][q]_ _ε._
_|_ p “ | p q “ p q “ q ´ _| ď_ ď

Thus, with probability 1 ´ α,


CW-ECEpc, hq “ L[´][1] E|P pY “ l | hlpXqq ´ hlpXq| ď ε.

_lÿ“1_

This proves the high-probability bound for the CW-ECE.


-----

