Year: 2021

Abstract:
Calibrating neural networks is of utmost importance when employing them in safety-critical applications where the downstream decision making depends on the predicted probabilities. Measuring calibration error amounts to comparing two empirical distributions. In this work, we introduce a binning-free calibration measure inspired by the classical Kolmogorov-Smirnov (KS) statistical test in which the main idea is to compare the respective cumulative probability distributions. From this, by approximating the empirical cumulative distribution using a differentiable function via splines, we obtain a recalibration function, which maps the network outputs to actual (calibrated) class assignment probabilities. The spline-fitting is performed using a held-out calibration set and the obtained recalibration function is evaluated on an unseen test set. We tested our method against existing calibration approaches on various image classification datasets and our spline-based recalibration approach consistently outperforms existing methods on KS error as well as other commonly used calibration measures.

heading: 1 INTRODUCTION
text: Despite the success of modern neural networks they are shown to be poorly calibrated (Guo et al. (2017)), which has led to a growing interest in the calibration of neural networks over the past few years (Kull et al. (2019); Kumar et al. (2019; 2018); Müller et al. (2019)). Considering classification problems, a classifier is said to be calibrated if the probability values it associates with the class labels match the true probabilities of correct class assignments. For instance, if an image classifier outputs 0.2 probability for the “horse” label for 100 test images, then out of those 100 images approximately 20 images should be classified as horse. It is important to ensure calibration when using classifiers for safety-critical applications such as medical image analysis and autonomous driving where the downstream decision making depends on the predicted probabilities.
One of the important aspects of machine learning research is the measure used to evaluate the performance of a model and in the context of calibration, this amounts to measuring the difference between two empirical probability distributions. To this end, the popular metric, Expected Calibration Error (ECE) (Naeini et al. (2015)), approximates the classwise probability distributions using histograms and takes an expected difference. This histogram approximation has a weakness that the resulting calibration error depends on the binning scheme (number of bins and bin divisions). Even though the drawbacks of ECE have been pointed out and some improvements have been proposed (Kumar et al. (2019); Nixon et al. (2019)), the histogram approximation has not been eliminated.1
In this paper, we first introduce a simple, binning-free calibration measure inspired by the classical Kolmogorov-Smirnov (KS) statistical test (Kolmogorov (1933); Smirnov (1939)), which also provides an effective visualization of the degree of miscalibration similar to the reliability diagram (NiculescuMizil & Caruana (2005)). To this end, the main idea of the KS-test is to compare the respective classwise cumulative (empirical) distributions. Furthermore, by approximating the empirical cumulative distribution using a differentiable function via splines (McKinley & Levine (1998)), we
1We consider metrics that measure classwise (top-r) calibration error (Kull et al. (2019)). Refer to section 2 for details.
obtain an analytical recalibration function2 which maps the given network outputs to the actual class assignment probabilities. Such a direct mapping was previously unavailable and the problem has been approached indirectly via learning, for example, by optimizing the (modified) cross-entropy loss (Guo et al. (2017); Mukhoti et al. (2020); Müller et al. (2019)). Similar to the existing methods (Guo et al. (2017); Kull et al. (2019)) the spline-fitting is performed using a held-out calibration set and the obtained recalibration function is evaluated on an unseen test set.
We evaluated our method against existing calibration approaches on various image classification datasets and our spline-based recalibration approach consistently outperforms existing methods on KS error, ECE as well as other commonly used calibration measures. Our approach to calibration does not update the model parameters, which allows it to be applied on any trained network and it retains the original classification accuracy in all the tested cases.

heading: 2 NOTATION AND PRELIMINARIES
text: We abstract the network as a function fθ : D → [0, 1]K , where D ⊂ IRd, and write fθ(x) = z. Here, x may be an image, or other input datum, and z is a vector, sometimes known as the vector of logits. In this paper, the parameters θ will not be considered, and we write simply f to represent the network function. We often refer to this function as a classifier, and in theory this could be of some other type than a neural network.
In a classification problem, K is the number of classes to be distinguished, and we call the value zk (the k-th component of vector z) the score for the class k. If the final layer of a network is a softmax layer, then the values zk satisfy ∑K k=1 zk = 1, and zk ≥ 0. Hence, the zk are pseudoprobabilities, though they do not necessarily have anything to do with real probabilities of correct class assignments. Typically, the value y∗ = argmaxk zk is taken as the (top-1) prediction of the network, and the corresponding score, maxk zk is called the confidence of the prediction. However, the term confidence does not have any mathematical meaning in this context and we deprecate its use.
We assume we are given a set of training data (xi, yi)ni=1, where xi ∈ D is an input data element, which for simplicity we call an image, and yi ∈ K = {1, . . . ,K} is the so-called ground-truth label. Our method also uses two other sets of data, called calibration data and test data.
It would be desirable if the numbers zk output by a network represented true probabilities. For this to make sense, we posit the existence of joint random variables (X,Y ), where X takes values in a domain D ⊂ IRd, and Y takes values in K. Further, let Z = f(X), another random variable, and Zk = fk(X) be its k-th component. Note that in this formulation X and Y are joint random variables, and the probability P (Y | X) is not assumed to be 1 for single class, and 0 for the others. A network is said to be calibrated if for every class k,
P (Y = k | Z = z) = zk . (1)
This can be written briefly as P (k | f(x)) = fk(x) = zk. Thus, if the network takes input x and outputs z = f(x), then zk represents the probability (given f(x)) that image x belongs to class k.
The probability P (k | z) is difficult to evaluate, even empirically, and most metrics (such as ECE) use or measure a different notion called classwise calibration (Kull et al. (2019); Zadrozny & Elkan (2002)), defined as,
P (Y = k | Zk = zk) = zk . (2)
This paper uses this definition (2) of calibration in the proposed KS metric.
Calibration and accuracy of a network are different concepts. For instance, one may consider a classifier that simply outputs the class probabilities for the data, ignoring the input x. Thus, if fk(x) = zk = P (Y = k), this classifier f is calibrated but the accuracy is no better than the random predictor. Therefore, in calibration of a classifier, it is important that this is not done while sacrificing classification (for instance top-1) accuracy.
2Open-source implementation available at https://github.com/kartikgupta-at-anu/ spline-calibration
The top-r prediction. The classifier f being calibrated means that fk(x) is calibrated for each class k, not only for the top class. This means that scores zk for all classes k give a meaningful estimate of the probability of the sample belonging to class k. This is particularly important in medical diagnosis where one may wish to have a reliable estimate of the probability of certain unlikely diagnoses.
Frequently, however, one is most interested in the probability of the top scoring class, the top-1 prediction, or in general the top-r prediction. Suppose a classifier f is given with values in [0, 1]K and let y be the ground truth label. Let us use f (−r) to denote the r-th top score (so f (−1) would denote the top score; the notation follows python semantics in which A[−1] represents the last element in array A). Similarly we define max(−r) for the r-th largest value. Let f (−r) : D → [0, 1] be defined as
f (−r)(x) = max(−r)k fk(x) , and y (−r) = { 1 if y = argmax(−r)k fk(x) 0 otherwise .
(3)
In words, y(−r) is 1 if the r-th top predicted class is the correct (ground-truth) choice. The network is calibrated for the top-r predictor if for all scores σ,
P (y(−r) = 1 | f (−r)(x) = σ) = σ . (4)
In words, the conditional probability that the top-r-th choice of the network is the correct choice, is equal to the r-th top score.
Similarly, one may consider probabilities that a datum belongs to one of the top-r scoring classes. The classifier is calibrated for being within-the-top-r classes if
P (∑r
s=1 y (−s) = 1 ∣∣ ∑r s=1 f (−s)(x) = σ ) = σ . (5)
Here, the sum on the left is 1 if the ground-truth label is among the top r choices, 0 otherwise, and the sum on the right is the sum of the top r scores.

heading: 3 KOLMOGOROV-SMIRNOV CALIBRATION ERROR
text: We now consider a way to measure if a classifier is classwise calibrated, including top-r and withintop-r calibration. This test is closely related to the Kolmogorov-Smirnov test (Kolmogorov (1933); Smirnov (1939)) for the equality of two probability distributions. This may be applied when the probability distributions are represented by samples.
We start with the definition of classwise calibration:
P (Y = k | fk(X) = zk) = zk . (6) P (Y = k, fk(X) = zk) = zk P (fk(X) = zk) , Bayes’ rule .
This may be written more simply but with a less precise notation as
P (zk, k) = zk P (zk) .
Motivation of the KS test. One is motivated to test the equality (or difference between) two distributions, defined on the interval [0, 1]. However, instead of having a functional form of these distributions, one has only samples from them. Given samples (xi, yi), it is not straight-forward to estimate P (zk) or P (zk | k), since a given value zk is likely to occur only once, or not at all, since the sample set is finite. One possibility is to use histograms of these distributions. However, this requires selection of the bin size and the division between bins, and the result depends on these parameters. For this reason, we believe this is an inadequate solution.
The approach suggested by the Kolmogorov-Smirnov test is to compare the cumulative distributions. Thus, with k given, one tests the equality∫ σ
0
P (zk, k) dzk = ∫ σ 0 zk P (zk) dzk . (7)
Writing φ1(σ) and φ2(σ) to be the two sides of this equation, the KS-distance between these two distributions is defined as KS = maxσ |φ1(σ)− φ2(σ)|. The fact that simply the maximum is used
here may suggest a lack of robustness, but this is a maximum difference between two integrals, so it reflects an accumulated difference between the two distributions.
To provide more insights into the KS-distance, let us a consider a case where zk consistently over or under-estimates P (k | zk) (which is usually the case, at least for top-1 classification (Guo et al. (2017))), then P (k | zk)−zk has constant sign for all values of zk. It follows that P (zk, k)−zkP (zk) has constant sign and so the maximum value in the KS-distance is achieved when σ = 1. In this case,
KS = ∫ 1 0 ∣∣P (zk, k)− zkP (zk)∣∣ dzk = ∫ 1 0 ∣∣P (k | zk)− zk∣∣P (zk) dzk , (8) which is the expected difference between zk and P (k | zk). This can be equivalently referred to as the expected calibration error for the class k.
Sampled distributions. Given samples (xi, yi)Ni=1, and a fixed k, one can estimate these cumulative distributions by ∫ σ
0
P (zk, k) dzk ≈ 1
N N∑ i=1 1(fk(xi) ≤ σ)× 1(yi = k) , (9)
where 1 : B → {0, 1} is the function that returns 1 if the Boolean expression is true and otherwise 0. Thus, the sum is simply a count of the number of samples for which yi = k and fk(xi) ≤ σ, and so the integral represents the proportion of the data satisfying this condition. Similarly,∫ σ
0
zk P (zk) dzk ≈ 1
N N∑ i=1 1(fk(xi) ≤ σ)fk(xi) . (10)
These sums can be computed quickly by sorting the data according to the values fk(xi), then defining two sequences as follows.
h̃0 = h0 = 0 ,
hi = hi−1 + 1(yi = k)/N ,
h̃i = h̃i−1 + fk(xi)/N .
(11)
The two sequences should be the same, and the metric
KS(fk) = max i |hi − h̃i| , (12)
gives a numerical estimate of the similarity, and hence a measure of the degree of calibration of fk. This is essentially a version of the Kolmogorov-Smirnov test for equality of two distributions.
Remark. All this discussion holds also when k < 0, for top-r and within-top-r predictions as discussed in section 2. In (11), for instance, f−1(xi) means the top score, f−1(xi) = maxk(fk(xi)), or more generally, f−r(xi) means the r-th top score. Similarly, the expression yi = −r means that yi is the class that has the r-th top score. Note when calibrating the top-1 score, our method is applied after identifying the top-1 score, hence, it does not alter the classification accuracy.

heading: 4 RECALIBRATION USING SPLINES
text: The function hi defined in (11) computes an empirical approximation
hi ≈ P (Y = k, fk(X) ≤ fk(xi)) . (13)
For convenience, the value of fk will be referred to as the score. We now define a continuous function h(t) for t ∈ [0, 1] by h(t) = P (Y = k, fk(X) ≤ s(t)) , (14) where s(t) is the t-th fractile score, namely the value that a proportion t of the scores fk(X) lie below. For instance s(0.5) is the median score. So, hi is an empirical approximation to h(t) where t = i/N . We now provide the basic observation that allows us to compute probabilities given the scores.

heading: Test Class[-1] | Uncalibrated
text: KS-error = 5.493%, Probability=92.420%
Proposition 4.1. If h(t) = P (Y = k, fk(X) ≤ s(t)) as in (14) where s(t) is the t-th fractile score, then h′(t) = P (Y = k | fk(X) = s(t)), where h′(t) = dh/dt.
Proof. The proof relies on the equality P (fk(X) ≤ s(t)) = t. In words, since s(t) is the value that a fraction t of the scores are less than or equal, the probability that a score is less than or equal to s(t), is (obviously) equal to t. See the supplementary material for a detailed proof.
Notice h′(t) allows direct conversion from score to probability. Therefore, our idea is to approximate hi using a differentiable function and take the derivative which would be our recalibration function.

heading: 4.1 SPLINE FITTING
text: The function hi (shown in fig 1a) is obtained through sampling only. Nevertheless, the sampled graph is smooth and increasing. There are various ways to fit a smooth curve to it, so as to take derivatives. We choose to fit the sampled points hi to a cubic spline and take its derivative.
Given sample points (ui, vi)Ni=1 in IR× IR, easily available references show how to fit a smooth spline curve that passes directly through the points (ui, vi). A very clear description is given in McKinley & Levine (1998), for the case where the points ui are equally spaced. We wish, however, to fit a spline curve with a small number of knot points to do a least-squares fit to the points. For convenience, this is briefly described here.
A cubic spline v(u) is defined by its values at certain knot points (ûk, v̂k)Kk=1. In fact, the value of the curve at any point u can be written as a linear function v(u) = ∑K k=1 ak(u)v̂k = a
>(u) v̂, where the coefficients ak depend on u.3 Therefore, given a set of further points (ui, vi)Ni=1, which may be different from the knot points, and typically more in number, least-squares spline fitting of the points (ui, vi) can be written as a least-squares problem minv̂ ‖A(u)v̂ − v‖2, which is solved by standard linear least-squares techniques. Here, the matrix A has dimension N ×K with N > K. Once v̂ is found, the value of the spline at any further points u is equal to v(u) = a(u)>v̂, a linear combination of the knot-point values v̂k.
Since the function is piecewise cubic, with continuous second derivatives, the first derivative of the spline is computed analytically. Furthermore, the derivative v′(u) can also be written as a linear combination v′(u) = a′(u)>v̂, where the coefficients a′(u) can be written explicitly.
Our goal is to fit a spline to a set of data points (ui, vi) = (i/N, hi) defined in (11), in other words, the values hi plotted against fractile score. Then according to Proposition 4.1, the derivative of the spline is equal to P (k | fk(X) = s(t)). This allows a direct computation of the conditional probability that the sample belongs to class k.
3Here and elsewhere, notation such as v and a denotes the vector of values vi or ak, as appropriate.
0 20 40 60 80 100
Percentile
0.0
0.2
0.4
0.6 0.8 C um ul at iv e S co re / P ro ba bi li
ty
(a)
Cumulative Score Cumulative Probability
0.0 0.2 0.4 0.6 0.8
Cumulative Score
0.0
0.2
0.4
0.6
0.8
(b)
Cumulative Score Cumulative Probability
0 20 40 60 80 100
Percentile
0.2
0.4
0.6
0.8
1.0
S co
re /
P ro
ba bi
li ty
(c)
Score Probability
0.2 0.4 0.6 0.8 1.0
Score
0.2
0.4
0.6
0.8
1.0
(d)
Score Probability

heading: Calib Class[-1] | Calibrated
text: KS-error = 0.371%, Probability=93.820%

heading: Test Class[-1] | Calibrated
text: KS-error = 0.716%, Probability=92.420%
Since the derivative of hi is a probability, one might constrain the derivative to be in the range [0, 1] while fitting splines. This can be easily incorporated because the derivative of the spline is a linear expression in v̂i. The spline fitting problem thereby becomes a linearly-constrained quadratic program (QP). However, although we tested this, in all the reported experiments, a simple least-squares solver is used without the constraints.

heading: 4.2 RECALIBRATION
text: We suppose that the classifier f = fθ is fixed, through training on the training set. Typically, if the classifier is tested on the training set, it is very close to being calibrated. However, if a classifier f is then tested on a different set of data, it may be substantially mis-calibrated. See fig 1.
Our method of calibration is to find a further mapping γ : [0, 1]→ [0, 1], such that γ ◦fk is calibrated. This is easily obtained from the direct mapping from score fk(x) to P (k | fk(x)) (refer to fig 1d). In equations, γ(σ) = h′(s−1(σ)). The function h′ is known analytically, from fitting a spline to h(t) and taking its derivative. The function s−1 is a mapping from the given score σ to its fractile s−1(σ). Note that, a held out calibration set is used to fit the splines and the obtained recalibration function γ is evaluated on an unseen test set.
To this end, given a sample x from the test set with fk(x) = σ, one can compute h′(s−1(σ)) directly in one step by interpolating its value between the values of h′(fk(xi)) and h′(fk(xi+1)) where xi and xi+1 are two samples from the calibration set, with closest scores on either side of σ. Assuming the samples in the calibration set are ordered, the samples xi and xi+1 can be quickly located using binary search. Given a reasonable number of samples in the calibration set, (usually in the order of thousands), this can be very accurate. In our experiments, improvement in calibration is observed in the test set with no difference to the accuracy of the network (refer to fig 2d). In practice, spline fitting is much faster than one forward pass through the network and it is highly scalable compared to learning based calibration methods.

heading: 5 RELATED WORK
text: Modern calibration methods. In recent years, neural networks are shown to overfit to the Negative Log-Likelihood (NLL) loss and in turn produce overconfident predictions which is cited as the main reason for miscalibration (Guo et al. (2017)). To this end, modern calibration methods can be broadly categorized into 1) methods that adapt the training procedure of the classifier, and 2) methods that learn a recalibration function post training. Among the former, the main idea is to increase the entropy of the classifier to avoid overconfident predictions, which is accomplished via modifying the training loss (Kumar et al. (2018); Mukhoti et al. (2020); Seo et al. (2019)), label smoothing (Müller et al. (2019); Pereyra et al. (2017)), and data augmentation techniques (Thulasidasan et al. (2019); Yun et al. (2019); Zhang et al. (2018)).
On the other hand, we are interested in calibrating an already trained classifier that eliminates the need for training from scratch. In this regard, a popular approach is Platt scaling (Platt et al. (1999)) which transforms the outputs of a binary classifier into probabilities by fitting a scaled logistic function on a held out calibration set. Similar approaches on binary classifiers include Isotonic Regression (Zadrozny & Elkan (2001)), histogram and Bayesian binning (Naeini et al. (2015); Zadrozny & Elkan (2001)), and Beta calibration (Kull et al. (2017)), which are later extended to the multiclass setting (Guo et al. (2017); Kull et al. (2019); Zadrozny & Elkan (2002)). Among these, the most popular method is temperature scaling (Guo et al. (2017)), which learns a single scalar on a held out set to calibrate the network predictions. Despite being simple and one of the early works, temperature scaling is the method to beat in calibrating modern networks. Our approach falls into this category, however, as opposed to minimizing a loss function, we obtain a recalibration function via spline-fitting, which directly maps the classifier outputs to the calibrated probabilities.
Calibration measures. Expected Calibration Error (ECE) (Naeini et al. (2015)) is the most popular measure in the literature, however, it has a weakness that the resulting calibration error depends on the histogram binning scheme such as the bin endpoints and the number of bins. Even though, some improvements have been proposed (Nixon et al. (2019); Vaicenavicius et al. (2019)), the binning scheme has not been eliminated and it is recently shown that any binning scheme leads to underestimated calibration errors (Kumar et al. (2019); Widmann et al. (2019)). Note that, there are binning-free metrics exist such as Brier score (Brier (1950)), NLL, and kernel based metrics for the multiclass setting (Kumar et al. (2018); Widmann et al. (2019)). Nevertheless, the Brier score and NLL measure a combination of calibration error and classification error (not just the calibration which is the focus). Whereas kernel based metrics, besides being computationally expensive, measure the calibration of the predicted probability vector rather than the classwise calibration error (Kull et al. (2019)) (or top-r prediction) which is typically the quantity of interest. To this end, we introduce a binning-free calibration measure based on the classical KS-test, which has the same benefits as ECE and provides effective visualizations similar to reliability diagrams. Furthermore, KS error can be shown to be a special case of kernel based measures (Gretton et al. (2012)).

heading: 6 EXPERIMENTS
text: Experimental setup. We evaluate our proposed calibration method on four different imageclassification datasets namely CIFAR-10/100 (Krizhevsky et al. (2009)), SVHN (Netzer et al. (2011)) and ImageNet (Deng et al. (2009)) using LeNet (LeCun et al. (1998)), ResNet (He et al. (2016)), ResNet with stochastic depth (Huang et al. (2017)), Wide ResNet (Zagoruyko & Komodakis (2016)) and DenseNet (Huang et al. (2017)) network architectures against state-of-the-art methods that calibrate post training. We use the pretrained network logits4 for spline fitting where we choose validation set as the calibration set, similar to the standard practice. Our final results for calibration are then reported on the test set of all datasets. Since ImageNet does not comprise the validation set, test set is divided into two halves: calibration set and test set. We use the natural cubic spline fitting method (that is, cubic splines with linear run-out) with 6 knots for all our experiments. Further experimental details are provided in the supplementary. For baseline methods namely: Temperature scaling, Vector scaling, Matrix scaling with ODIR (Off-diagonal and Intercept Regularisation), and Dirichlet calibration, we use the implementation of Kull et al. (Kull et al. (2019)).
4Pre-trained network logits are obtained from https://github.com/markus93/NN_ calibration.
Results. We provide comparisons of our method using proposed KS error for the top most prediction against state-of-the-art calibration methods namely temperature scaling (Guo et al. (2017)), vector scaling, MS-ODIR, and Dirichlet Calibration (Dir-ODIR) (Kull et al. (2019)) in Table 1. Our method reduces calibration error to 1% in almost all experiments performed on different datasets without any loss in accuracy. It clearly reflects the efficacy of our method irrespective of the scale of the dataset as well as the depth of the network architecture. It consistently performs better than the recently introduced Dirichlet calibration and Matrix scaling with ODIR (Kull et al. (2019)) in all the experiments. Note this is consistent with the top-1 calibration results reported in Table 15 of (Kull et al. (2019)). The closest competitor to our method is temperature scaling, against which our method performs better in 9 out of 13 experiments. Note, in the cases where temperature scaling outperforms our method, the gap in KS error between the two methods is marginal (< 0.3%) and our method is the second best. We provide comparisons using other calibration metrics in the supplementary.
From the practical point of view, it is also important for a network to be calibrated for top second/third predictions and so on. We thus show comparisons for top-2 prediction KS error in Table 2. An observation similar to the one noted in Table 1 can be made for the top-2 predictions as well. Our method achieves< 1% calibration error in all the experiments. It consistently performs well especially for experiments performed on large scale ImageNet dataset where it sets new state-of-the-art for calibration. We would like to emphasize here, though for some cases Kull et al. (Kull et al. (2019)) and Vector Scaling perform better than our method in terms of top-2 KS calibration error, overall (considering both top-1 and top-2 predictions) our method performs better.

heading: 7 CONCLUSION
text: In this work, we have introduced a binning-free calibration metric based on the Kolmogorov-Smirnov test to measure classwise or (within)-top-r calibration errors. Our KS error eliminates the shortcomings of the popular ECE measure and its variants while accurately measuring the expected calibration error and provides effective visualizations similar to reliability diagrams. Furthermore, we introduced a simple and effective calibration method based on spline-fitting which does not involve any learning and yet consistently yields the lowest calibration error in the majority of our experiments. We believe, the KS metric would be of wide-spread use to measure classwise calibration and our spline method would inspire learning-free approaches to neural network calibration. We intend to focus on calibration beyond classification problems as future work.

heading: 8 ACKNOWLEDGEMENTS
text: The work is supported by the Australian Research Council Centre of Excellence for Robotic Vision (project number CE140100016). We would also like to thank Google Research and Data61, CSIRO for their support.

heading: Appendices
text: Here, we first provide the proof of our main result, discuss more about top-r calibration and splinefitting, and then turn to additional experiments.

heading: A PROOF OF PROPOSITION 4.1
text: We first restate our proposition below.
Proposition A.2. If h(t) = P (Y = k, fk(X) ≤ s(t)) as in (14) of the main paper where s(t) is the t-th fractile score. Then h′(t) = P (Y = k | fk(X) = s(t)), where h′(t) = dh/dt.
Proof. The proof is using the fundamental relationship between the Probability Distribution Function (PDF) and the Cumulative Distribution Function (CDF) and it is provided here for completeness. Taking derivatives, we see (writing P (k) instead of P (Y = k)):
h′(t) = P (k, fk(X) = s(t)) . s ′(t)
= P (k | fk(X) = s(t)) . P (fk(X) = s(t)) . s′(t)
= P (k | fk(X) = s(t)) . d
dt
( P (fk(X) ≤ s(t)) ) = P (k | fk(X) = s(t)) . d
dt (t)
= P (k | fk(X) = s(t)) .
(15)
The proof relies on the equality P (fk(X) ≤ s(t)) = t. In words: s(t) is the value that a fraction t of the scores are less than or equal. This equality then says: the probability that a score is less than or equal to the value that a fraction t of the scores lie below, is (obviously) equal to t.
B MORE ON TOP-r AND WITHIN-TOP-r CALIBRATION
In the main paper, definitions of top-r and within-top-r calibration are given in equations (4) and (5). Here, a few more details are given of how to calibrate the classifier f for top-r and within-top-r calibration.
The method of calibration using splines described in this paper consists of fitting a spline to the cumulative accuracy, defined as hi in equation (11) in the main paper. For top-r classification, the method is much the same as for the classification for class k. Equation (11) is replaced by sorting the data according to the r-th top score, then defining
h̃0 = h0 = 0 ,
hi = hi−1 + 1(y (−r) = 1)/N ,
h̃i = h̃i−1 + f (−r)(xi)/N ,
(16)
where y(−r) and f (−r)(xi) are defined in the main paper, equation (3). These sequences may then be used both as a metric for the correct top-r calibration and for calibration using spline-fitting as described.
For within-top-r calibration, one sorts the data according to the sum of the top r scores, namely∑r s=1 f (−s)(xi), then computes
h̃0 = h0 = 0 , hi = hi−1 + 1 ( r∑ s=1 y(−s) = 1 )/ N ,
h̃i = h̃i−1 + r∑ s=1 f (−s)(xi)/N ,
(17)
As before, this can be used as a metric, or as the starting point for within-top-r calibration by our method. Examples of this type of calibration (graphs for uncalibrated networks in fig 7 and fig 9) is given in the graphs provided in fig 8 and fig 10 for within-top-2 predictions and within-top-3 predictions respectively.
It is notable that if a classifier is calibrated in the sense of equation (1) in the main paper (also called multi-class-calibrated), then it is also calibrated for top-r and within-top-r classification.

heading: C LEAST SQUARE SPLINE FITTING
text: Least-square fitting using cubic splines is a known technique. However, details are given here for the convenience of the reader. Our primary reference is (McKinley & Levine (1998)), which we adapt to least-squares fitting. We consider the case where the knot-points are evenly spaced.
We change notation from that used in the main paper by denoting points by (x, y) instead of (u, v). Thus, given knot points (x̂i, ŷi)Kk=1 one is required to fit some points (xi, yi) N i=1. Given a point x, the corresponding spline value is given by y = a(x)>Mŷ, where ŷ is the vector of values ŷi. The form of the vector a(x) and the matrix M are given in the following.
The form of the matrix M is derived from equation (25) in McKinley & Levine (1998). Define the matrices
A =  4 1 1 4 1 1 4 1 . . .
1 4 1 1 4
 ; B = 6 h2  1 −2 1 1 −2 1 . . .
1 −2 1  , where h is the distance between the knot points. These matrices are of dimensions K − 2×K − 2 and K − 2×K respectively. Finally, let M be the matrix
M =  0K >
A−1B 0K >
IK×K  . Here, 0K is a vector of zeros of length K, and IK×K is the identity matrix. The matrix M has dimension 2K ×K. Next, let the point x lie between the knots j and j + 1 and let u = x− x̂j . Then define the vector v = a(x) by values
vj = −u3/(6h) + u2/2− hu/3 , vj+1 = u
3/(6h)− hu/6 , vj+K = −u/h+ 1 ,
vj+1+K = u/h ,
with other entries equal to 0.
Then the value of the spline is given by
y = a(x)>Mŷ ,
as required. This allows us to fit the spline (varying the values of ŷ) to points (xi, yi) by least-squares fit, as described in the main paper.
The above description is for so-called natural (linear-runout) splines. For quadratic-runout or cubicrunout splines the only difference is that the first and last rows of matrix A are changed – see McKinley & Levine (1998) for details.
As described in the main paper, it is also possible to add linear constraints to this least-squares problem, such as constraints on derivatives of the spline. This results in a linearly-constrained quadratic programming problem.

heading: D ADDITIONAL EXPERIMENTS
text: We first provide the experimental setup for different datasets in Table 3. Note, the calibration set is used for spline fitting in our method and then final evaluation is based on an unseen test set.
We also provide comparisons of our method against baseline methods for within-top-2 predictions (equation 5 of the main paper) in Table 4 using KS error. Our method achieves comparable or better results for within-top-2 predictions. It should be noted that the scores for top-3 (f (−3)(x)) or even top-4, top-5, etc., are very close to zero for majority of the samples (due to overconfidence of top-1 predictions). Therefore the calibration error for top-r with r > 2 predictions is very close to zero and comparing different methods with respect to it is of little value. Furthermore, for visual illustration, we provide calibration graphs of top-2 predictions in fig 3 and fig 4 for uncalibrated and calibrated network respectively. Similar graphs for top-3, within-top-2, and within-top-3 predictions are presented in figures 5 – 10.
We also provide classification accuracy comparisons for different post-hoc calibration methods against our method if we apply calibration for all top-1, 2, 3, . . . ,K predictions for K-class classification problem in Table 5. We would like to point out that there is negligible change in accuracy between the calibrated networks (using our method) and the uncalibrated ones.

heading: Test Class[-2] | Uncalibrated
text: KS-error = 2.256%, Probability=97.500%
0 20 40 60 80 100
Percentile
0.0
0.2
0.4
0.6
0.8
1.0
C um
ul at
iv e
S co
re /
P ro
ba bi
li ty
(a)
Cumulative Score Cumulative Probability
0.0 0.2 0.4 0.6 0.8 1.0
Cumulative Score
0.0
0.2
0.4
0.6
0.8
1.0
(b)
Cumulative Score Cumulative Probability
0 20 40 60 80 100
Percentile
0.6
0.7
0.8
0.9
1.0
S co
re /
P ro
ba bi
li ty
(c)
Score Probability
0.6 0.7 0.8 0.9 1.0
Score
0.6
0.7
0.8
0.9
1.0
(d)
Score Probability

heading: Calib Class[-2] | Calibrated
text: KS-error = 0.144%, Probability=98.040%

heading: Test Class[-2] | Calibrated
text: KS-error = 0.571%, Probability=97.500%

heading: Test Class[-3] | Uncalibrated
text: KS-error = 0.983%, Probability=98.970%
0 20 40 60 80 100
Percentile
0.0
0.2
0.4
0.6
0.8
1.0
C um
ul at
iv e
S co
re /
P ro
ba bi
li ty
(a)
Cumulative Score Cumulative Probability
0.0 0.2 0.4 0.6 0.8 1.0
Cumulative Score
0.0
0.2
0.4
0.6
0.8
1.0
(b)
Cumulative Score Cumulative Probability
0 20 40 60 80 100
Percentile
0.825
0.850
0.875
0.900
0.925
0.950
0.975
1.000
S co
re /
P ro
ba bi
li ty
(c)
Score Probability
0.85 0.90 0.95 1.00
Score
0.825
0.850
0.875
0.900
0.925
0.950
0.975
1.000
(d)
Score Probability

heading: Calib Class[-3] | Calibrated
text: KS-error = 0.176%, Probability=99.280%

heading: Test Class[-3] | Calibrated
text: KS-error = 0.368%, Probability=98.970%
For the sake of completeness, we present calibration results using the existing calibration metric, Expected Calibration Error (ECE) (Naeini et al. (2015)) in Table 6. We would like to reiterate the fact that ECE metric is highly dependent on the chosen number of bins and thus does not really reflect true calibration performance. To reflect the efficacy of our proposed calibration method, we also present calibration results using other calibration metrics such as recently proposed binning free measure KDE-ECE (Zhang et al. (2020)), MCE (Maximum Calibration Error) (Guo et al. (2017)) and Brier Scores for top-1 predictions on ImageNet dataset in Table 7. Since, the original formulation of Brier Score for multi-class predictions is highly biased on the accuracy and is approximately similar for all calibration methods, we hereby use top-1 Brier Score which is the mean squared error between top-1 scores and ground truths for the top-1 predictions (1 if the prediction is correct and 0 otherwise). It can be clearly observed that our approach consistently outperforms all the baselines on different calibration measures.

Review summaries:
The paper presents a post-hoc calibration method for deep neural net classification. The method proposes to first reduces the well-known ECE score to a special case of the Kolmogorov-Smirnov (KS) test, and this way solves the dependency of ECE on the limiting binning assumption. The method proposes next to recalibrate the classification probabilities by fitting a cubic spline to the KS test score.