Assuming Locally Equal Calibration Errors for Non-Parametric Multiclass Calibration
Authors: Kaspar Valk
Meelis Kull
Venue: Accepted by TMLR ()

Abstract: A probabilistic classifier is considered calibrated if it outputs probabilities equal to the expected class distribution given the classifier's output. Calibration is essential in safety-critical tasks where small deviations between the predicted probabilities and the actually observed class proportions can incur high costs. A common approach to improve the calibration of a classifier is to use a hold-out data set and a post-hoc calibration method to learn a correcting transformation for the classifier's output. This work explores the field of post-hoc calibration methods for multi-class classifiers and formulates two assumptions about the probability simplex which have been used by many existing non-parametric calibration methods, but despite this, have never been explicitly stated: assuming locally equal label distributions or assuming locally equal calibration errors. Based on the latter assumption, an intuitive non-parametric post-hoc calibration method is proposed, which is shown to offer improvements to the state-of-the-art according to the expected calibration error metric on CIFAR-10 and CIFAR-100 data sets.


Published in Transactions on Machine Learning Research (06/2023)
Assuming Locally Equal Calibration Errors for Non-Parametric Multiclass Calibration
Kaspar Valk
volk. kalk.kaspor
@gmail kalkkkasppr@maal.. com
Meelis Kull University of Tartu
meelis. frelis.kulluud.cco
Reviewed on OpenReview: https: / openreview. net/ formm? nd=n55s
Abstract
A probabílistic classifier is considered calibrated if it outputs probabilities equal to the expected class distribution given the classifier's output. Calibration is essential in safety- critical tasks where small deviations between the predicted probabilities and the actually observed class proportions can incur high costs. A common approach to improve the cali- bration of a classifier is to use a hold-out dataset and a post-hoc calibration method to learn a correcting transformation for the classifier's output. This work explores the field of post- hoc calibration methods for multi-class classifiers and formulates two assumptions about the probability simplex which have been used by many existing non-parametric calibration methods, but despite this, have never been explicitly stated: assuming locally equal label distributions assuming locally equal calibration errors. Based on the latter assumption an intuitive non- non- con-parmetrric post-hoc calibration method is proposed, which is shown to offer improvements to the statc-of-thee according to the expected calibration crror metric on CIFAR-10 and CIFAR-100 datasets.
1 Introduction
Probabilistic classifiers take some data as input and produce probability distributions over classes as output. For example, a classifier could be tasked to lake as inpul an X-ray image person's 's chest and produce as output a vector of three probabilities for whether the image depicts a healthy lung, lung cancer or some other lung disease. A classifier is considered to be calibrated if its predieted probabilitics with the true class distribution. It is possible that probabilistic classifier is not well-calibrated and produces distorted probabilities. For example, predicting an X-ray image to show a healthy lung with probability of 0.9 is calibrated if, among a large sample of images with similar predictions, 0.9 of them truly depict a healthy lung. in reality only 0.7 of the images depict a healthy lung, then the prediction of 0.9 is over- confident. The problem of over-confident. predictions especially common for modern deep neural networks Guo al. 2017 Lakshminarayanan et al., 2017). Distorted output probabilitics are also characteristic of many classical machine learning methods such as naive Bayes, decision trees NiculescuuMMiil & Caruanal
in correspondence
2005
Domingos & Pazzani 1996) high-dimensional logistic regression (Bai et al.) 2021 Clarté et al.
2022a
Well-calibrated classifiers are essential in safely-critical applications (e.g. medical diagnosis, autonomous driving) where small deviations of predicted probabilities from being calibrated can cause costly mistakes [Leibig et al., 2017]. For example, in a self-driving car that uses a classifier to detect the road clear of obstructions, coeficontd predictions can lead to accidents, and under-confident predictions can prevent the vehicle from driving.

---

Published in Transactions on Machine Learning Research (06/2023)
The machine learning literature has two fundamentally different approaches to achieve better-calibrated classifiers. The first approach, with focus on neural networks, is to modify the classifier's training algorithm or use Bayesian approaches to model uncertainties. For example, Mukhoti / et al. (2020) studied the use of
focal loss [Lin ct al.) 2017) instead of log-loss for training better calibrated classifier; Müller et al. (2019)
investigated the use of label smoothing (Szegedy et al.) (0166) during training for better calibration; Kumar
et al. 2018)) and Popordanoska et al. (2021) proposed additional terms to be added to the training time loss
function that penalize miscalibration; Maddox al. (2019) proposed Bayesian model averaging for achieving
calibration in deep learning.
The second approach to achieve better-calibrated classifiers is to apply a post-hoc calibration method on an already trained classifier. Post-hoc calibration methods receive as input a classifier and a hold-out validation dataset and learn a transformation from the classifier's predictions to better-caliie calibrated predictions. Many methods have been proposed for binary probabilistic classifiers, where the output has only two classes and only onc degree of freedom. For example, there exists logistic calibration (Platt) 1999); isotonic calibration (Zadrozny & Elkan 2002); histogram binning (Zadrozny & Elkan] 2001); beta calibration (Kull et al., 2017). For multi-class classifiers with more than two output classes, common approach has been to apply binary methods in a one-versus-rest manner: binary post-hoc calibration method is applicd separately on the probabilities of each class (Zadrozny & Elkan 2002). In recent years, several inherently multi cillti-caas post-hoc calibration methods have been proposed as well, even though some of them are applicable only for neural networks. For example, Guo et al. (2017) proposed temperature scaling, vector scaling, and matrix scaling; Kull et al. (2019) introduced Dirichlet calibration: Zhao et al. (2021) proposed a method specifically intended for decision making scenarios; Rahimi et al. (2020p suggested intra-order preserving functions; Wenger et al.
2020 proposed non-parametric method based on latent Gaussian process.
This work takes a look at the post-hoc calibration method approach for achieving better calibrated multi- class classifiers. While there already exist many strong multi-class methods, several of them are limited to symmetrical transformations for all the classes; for example, temperature scaling, Gaussian process calibra- tion, diagonal and order-invariant subfamilies of the intra-order preserving functions are all symmetrical. As shown in the experiments section, symmetrical transformations are usually not problem but can be severely limiting in some cases. The asymmetrical existing methods are limited in their expressivity; for example, matrix scaling and vector scaling are limited to only linear transformations in the logit space. This work proposes an intuitive and simple non-parametric post-hoc calibration method that is not limited by a symmetrical transformation or the expressivity of parametric function families. The basis of the proposed method is assuming that similar predictions on the probability simplex have similar calibration errors. The method shown to outperform competing methods, offering improvements in expected calibration error and avoiding the failures of symmetric methods.
In Section notation is introduced and an overview of background information connected to multi-class calibration is given. The concepts of calibration, calibration error, calibration error estimation, and existing post-hoc calibration methods for multi-class calibration are explained. In Scction 3 the contributions of this work are described and a post-hoc calibration method is proposed. In Section 4 experiments are carried out to compare the proposed method to its competitors. The source code of the experiments available at https: This paper builds upon preliminary research conducted for
//github. wwt.///asaaar//eeeecaaaaaaoaaaaa the author's master's 's thesis (Valk 2022).
2
Background and related work
The following sections introduce the concepts of calibration, calibration error, calibration error estimation and explain the existing post-hoc calibration methods for multi-class calibration.
2.1 Notation
This work focuses on m-class classification problems with feature space X' and onc-hot encoded label space y (1..,....
........ 0), (0, 1,...,,)........................ .)...., (0,0, ..... 1)}. where m 2 3. A probabilistic multi-class classifier for such classification problem is function f X - A that takes input features x X' and outputs
2

---

Published in Transactions on Machine Learning Research (06/2023)
probability vector f(x) (f1.....,P.. Pm)) A", where Am f(g...... 9m) [0, 1 E == 1}
is the (m - 1ddimenssinn probability simplex. In addition, let X E X, Y = (Y,,... Ym) E y and
f(x) = P label, and P the classifier's prediction.
P..) n be random variables, where X denotes the imput features, Y denotes the
2.2 Calibration
There exist several definitions for calibration in the context of probabilistic multi-class classifiers.
Multi-class calibration A classifier is considered to be multi-class-calibratee (or just calibrated) et al. 2019) if for any prediction vector A m it holds that
Kull
Ey YIP D =
Classwise calibration A weaker notion classwise calibration conditions the expectation on each class separately (Zadrozny & Elkan 2002). A classifier is considered to be classwise calibrated if for any class E (1, m and any real value E [0, 1] holds that
Ey; [rlp = =c]= =c.
Note that for binary classification, classwise calibration is the same multi-class calibration Vaiccnavvvcuus
et al. 2019
Confidence calibration Another weaker notion, confidence calibration used by Guo et al. (011 requires calibration only for the predictions of the class with the highest probability in each output. classifier is considered to be confidence calibrated for any real value e [0, 1] it holds that
Ey Y Yargmas e max P =.
An illustrative example of the different calibration definitions is presented in Appendix A.1
2.3 Calibration error
Calibration error describes the difference between the predicted probabilities of the classifier and the corre- sponding perfectly calibrated class probabilities. Kumar et al. (2019 defined calibrat ion error for confidence and classwise calibration for classifier f. In a slightly more generalized form, confidence calibration error is defined as
Ce Ep [mmas P Ey Yorgmaz |maa A p]101// 1/a
and classwise calibration error is defined
CE = Σ Ep P. - Ey [x11 1 1/1/
The calibration errors are parameterized by a, where a = results in meanrabbsolute-erroo, and a 2 mean-squared-erro:
Calibration error could not only be defined for the whole classifier f but also for just prediction value the difference between the right-hand side and the left-hand side of the corresponding calibration definition. For this work, calibration error for multi-class calibration for prediction vector value P is defined as
CE = P---EE r =
Note that for multi-class calibration, the error defined in such way is vector of real values.
3

---

Published in Transactions on Machine Learning Research (06/2023)
2.4 Calibration evaluation
In any real-world setting, true calibration error not be directly found, it can only be estimated. Common metrics to evaluate calibration are expected calibration error (ECE) and proper scoring rules.
The ECE metric groups similar predictions into bins and uses bin averages to estimate the calibration error. For confidence calibration, ECE is calculated using Y Yargmaz and max P and it is defined as
B: 1 Usl.
confidence ECE
Σ i=1
where b the number of bins, [Ba] the number of data points in bin Bi, n the number of data points, P; the average prediction value in the i-th bin and V. the average label value in the i-th bin (Naeini et al.) 2015
For classwise calibration, ECE is defined
classwise ECE class-j-ECE,
where class-j-ECE is calculated with the same formula as Equation 11) but with values Y; and P3 used instead of Y arrmez f and max P when calculating D, and P. (Kull et al. 2019 Commonly bins are chosen with cither equal size so that they contain an equal amount of data points, or with equal width so that the probability interval from 0 to uniformly partitioned between them. Equal-sized bins are also called equal-mass bins or data dependent bins in some works.
While ECE is an important measure for calibration evaluation, it should not be the only metric to be evaluated. Very low calibration error can be achieved if the classifier makes very uninformative predictions; e.g. predicts the overall class distribution of the training dataset for any given input. Good metrics to consider in addition to ECE are proper scoring rules (Brier score or log-loss) as they are shown to decompose into calibration loss and refinement loss (DeGroot & Fienberg 1983). While the calibration loss measures miscalibration, the refinement loss measures the extent to which instances different classes are getting the same prodiction. The key property of proper scoring rules have the Baycs-optimal model as the unique loss minimizer, achieving zero calibration loss and the minimal possible refinement loss, which can be non-zero due to aleatoric uncertainty (Kull & Flach 2015
2.5 Post-hoc calibration methods
Calibration of an alrcady trained classifier can be improved by post-hoc calibration methods. Given a classifier and a hold-out validation dataset different from the original training dataset, the goal of a post-hoc calibration method is to learn a map è n - A from the uncalibrated output P of the classifier to a better-calibrated output a()). The ideal result would be the calibration method learns the true calibration map c(p) Ey 2 = D.. The transformation is typically learned by optimizing a proper scoring rule (Brier score log-loss) (Rahimi et al.) 2020 A possible motivation behind this can be that unless the refinement loss is decreasing, any reduction of proper loss is due to the reduction of the calibration loss.
One-versus-rest methods A common approach to multi-class calibration has been to apply binary post- hoc calibration methods in a nee-erssu--rest manner (Zadrozny & Elkan 2002). For every class in class classification task, one can define binary one-vs-rest classification problem: the currently viewed class is the positive class, rest of the classes grouped together are the negative class. In one-versus-rest approach to multi-class calibration, a binary classification method is trained on m such one-vs-rest. tasks separalely. For example, some binary calibration methods that have been applied in the versuursus- approach are Platt scaling (Platt 1999), isotonic regression calibration (Zadrozny (Zadrozny Elkan 2001), and beta calibration (Kull et al. (017). Platt scaling and beta calibration are both parametric methods fitting specific family for calibration, isotonic regression calibration uses isotonic
Elkan| (002), histogram binning
4

---

Published in Transactions on Machine Learning Research (06/2023)
regression to learn calibrating transformation, histogram binning divides the probability space into equal- sized bins and in each bin sets the calibrated value of predictions belonging to that bin equal to the empirical class distribution value in the bin.
There are two considerable flaws to the one-versus-rest approach. First, it is not able to learn any depen- dencies between classes. Second, when the output of m binary methods put back together, the prediction vector will likely no longer sum to and needs to be normalized. It has been shown that normalization can make the probabilities less calibrated depending on the metric used (Gupta & Ramdas 2022). Therefore, some works propose to ignore the final step of normalization and treat vne-vs- calibration as truly separate binary calibration problems (Patel et al. 2021 Gupta & Ramdas 2022).
Temperature scaling Temperature scaling is logit scaling method designed for neural networks in- troduced by Guo et al. (2017). The method is defined as a(z) = (=/lt) where z is the logit vector and E (0, oo) is the learned temperature parameter shared across all classes. If > 1, then the method makes the predictions less confieent by pulling the probability distribution towards the uniform distribution; if < 1, then the method makes the predictions more confident, making the largest probability in the output even larger.
Matrix and vector scaling Matrix and vector scaling are both logit transformation techniques proposed by Guo et al. (2017) similar to lemperature scaling. The calibrated output of these techniques is obtained by 0(z) = (W + b), where W E gexk is a matrix of learned weights (restricted to the diagonal matrix for vector scaling, unrestricted for matrix scaling) and b E &R is a vector of learned biases. Vector scaling is similar to temperature scaling, but instead of a single scaling parameter, a scaling parameter is learned separately for each class and an additional bias also learned. For matrix scaling, each logit becomes a linear combination of other logits. Matrix scaling gives better results if it is trained with off-diagonal and intercept regularization (ODIR) (Kull et al. 2019:: the term X( mI
E, b3) is added to 1) Σips wfy) pl( 1 m
the training loss, where À and μ are the regularization hyperparamcters.
Dirichlet calibration Dirichlet calibration is a method proposed by Kull et al. (2019) that is quite similar to matrix scaling, except. it does not work on the logits of a neural net but rather on the actual predicted probabilities p of a classifier. With Dirichlet calibration, the calibrated probabilities are obtained by a(p) = (WWngp + b), where In is vectorized natural-logarithm function. Similar to matrix scaling, Dirichlet calibration is also trained with ODIR to prevent overfitting.
Intra order-preserving functions Rahimi et al. (020)) proposed to use the family of intra order- preserving (IOP) functions to learn a calibration map on the logits of a noural network. An IOP function é : - m is veclor-valued function where the order of the sorted output components is the same as the order of sorted input components, that is argsort 6(z) = argsort z. The use of 1OP functions was motivated by their property of preserving classifier accuracy, and having larger expressive power than the scaling methods proposed by Guo et al. (2017) Dirichlet calibration. The IOP function family preserves classifier accuracy after calibration, as the largest probability in the classifier output still remains the largest probability after calibration, thanks to the order-preserving property. The IOP function family is more ex- pressive than matrix scaling or Dirichlet calibration, as IOP functions can learn non-linear transformations while matrix scaling and Dirichlet calibration are limited to linear transformations.
In addition, Rahimi et al. (2020) showed in their experiments that in practice, it is better to use diagonal subfamily of IOP functions they can be expressed with fewer parameters and are therefore less prone to overfitting, An IOP function è is diagonal function if ē(x) = (é(z)..... (c(z))...,&
where è I - IR is a continuous and incrcasing function. A diagonal IOP function is symmetrical for all classes and produces oulput where the different class logits do not. interact with each other in é. It can be noted that temperature scaling uses a subfamily of diagonal IOP functions: it uses linear diagonal IOP functions where the bias term equals Rahimi et al.) (2020) implemented the IOP post-hoc calibration method as a neural network with two fully connected hidden layers with preserrres constraints. Their implementation has two hyperparameters: the number of neurons in the first and second hidden layers.
5

---

Published in Transactions on Machine Learning Research (06/2023)
Decision calibration Zhao et al. [2021 proposed non-parametric calibration method for the context of decision making settings. The method works iteratively by partitioning the probability simplex and applying an adjustment on each partition. The partition and adjustment are both determined by the average difference between the label and prodiction values.
Gaussian process calibration Wenger et al. 2020) proposed a natively multi-class non-parametric cal- ibration method that uses a latent Gaussian process to learn the calibrating transformation. The method applies the same transformation for all the classes.
3 Contributions
The contributions of this work to the field of multi-class calibration can be split into two:
1. The work formulates two assumptions about the true calibration map that have been previously used but not clearly stated in the calibration literature.
By explicitly acknowledging the assumptions, we propose an intuitive and simple non-parametric post-hoc calibration method.
3.1 Proposed assumptions
Before introducing the proposed assumptions, small introduction is needed. According to the defi- nition of multi-class calibration given in Section 2.2 a prediction vector P is considered calibrated if p Ey Y D) Therefore, a calibrating transformation of prediction ş could be found we had a good estimate its true conditional class distribution Ey Y|P= = - we could simply set the pre- diction value P equal to the estimate. Similarly, if were approach calibration from the definition of calibration error CE(() = - y = =p) given in Section 2.3 it would suffice for calibration if we had a good calibration error estimate we could subtract the estimate from the prediction and our output would be calibrated.
One obvious weak estimator for the true class distribution could be the (single) label value Y corresponding to p. The estimator would clcarly be unbiased as for each p, the average value of Y is equal Ey f p). and hence, Ey EY P = p) Ey E = P] = O. However, this estimator Y would have very high variance as it is based on sample with just one element. Likewise, an unbiased high variance estimator CE could be constructed for the calibration error as the difference between the prediction and its label CE(p) = Y. Unfortunately, both of these simple estimators have too high variance to be used for calibration. However, if we made some assumptions about the calibration map of our classifier, we could construct good estimators that make use of these weaker estimators.
Assumption of locally equal calibration errors (LECE) We propose to assume that the calibration error is approximately equal in a close neighborhood on the probability simplex. Formally, for some fixed c, > 0 and some neighborhood function d: A x A R, we assume that
d(p.p') <
|(FF()) CFFD Se
where 11-112 denotes the squared Euclidean norm. Note that the term 'locally is often used to refer to neighborhoods in the original feature space, whereas consider neighborhoods in the simpler.
Given a validation dataset, the LECE assumption allows us to construct a considerably better estimator Ceeeigh for the calibration error of prediction p than the previously introduced weak estimator CE( = P- Y. First, we need to find the close neighborhood of P, meaning the validation predictions P....., Ps with labels Y, i,.... Ya for which (f. for in 1,...,k. k. A stronger est estimator can then be constructed

---

Published in Transactions on Machine Learning Research (06/2023)
if we average across the weak calibration error estimator values belonging to that close neighborhood
Eeniggh (p) (CC()) L.. -Y). Y.).
The stronger estimalor has upper bound on its squared bias
Bias (nneigh())
= By Yx [Enesgh(B) C
By, 1(f: -Y.)] - CF(())
(B. Ey, (Y.)) - CF((P)
( -
(CE(P)) -C
c=
The variance of the estimator decreases approximately linearly as the number of neighbors increases
Var (Fnnighh Var
Σ
CFLD
k Disn
Var(CE((,)
Var (cE(C
1.2
Given the estimate neeggg (f), calibrated prediction can finally be constructed by subtracting it from the original prediction: a()) P - C (neigh(P):
Assumption of locally equal class distributions (LECD) A similar derivation for constructing cal- ibrated predictions is possible if one would instead assume that the true label distribution Ey Y is approximately equal in a close neighborhood. Formally, for some fixed e, 8 > and some neighborhood function d: Am x m R, we assume that
d(p. 28 = EY Y Ey Y P
2 SE
With this assumption, the method would arrive at calibrated prediction by using the average one-hot label vector in close neighborhood a(ÿ) Σ Y.. Similarly to the previous LECE assumption, the estimator used with the LECD assumption would also have an upper bound of e on its squared bias, and its variance would decrease approximately linearly as the number of neighbors increases.
Visualisation of the assumptions To better understand the difference between the two assumptions,
consider Figure [ It depicts the calibration maps learned by two calibration methods on a synthetic calibration task. The exact details about the synthetic dataset are given in Section 4.1 but in short, 5000 prediction and label pairs were generated from Dirichlet distribution with parameters [0.5, 0.5, 0.5], and the goal of the calibration methods in Figures La and Ib was to learn to imitate the true calibration map depicted in Figure Ic from the generated data. Note that the true calibration map depicted in Figure Ic is something we never know in practice and here it has been manually created merely for this synthelic calibration task to allow for visual comparison between the two assumptions. Both the background colors and black arrows depict the learned transformation. The same information that is represented by the arrow is also represented by the RGB color value which is in linear relation with the calibration error vector that point: red for class 1, green for class 2, and blue for class

---

Published in Transactions on Machine Learning Research (06/2023)
(a) Histogram binning one-vs-rest with LECD assumption (classical)
(b) Histogram binning one-vs-rest with LECE assumption (new)
(c) True calibration map
1.0
0.8
0.6
53
0.4
0.2
0.0
0.0
0.2
0.2
0.4
0.4
0.6
0.6
P2
0.8
0.8
P1
1.0
1.0
Figure 1: Illusraaivve example of the differences between the LECD and the LECE assumption synthetic calibration lask. Two versions of histogram binning applied in one-vs-rest style with equal-width bins (a, b) aim to learn the true calibration map (c). The classical histogram binning uses the LECD assumption (a); the novel version uses the LECE assumption (b). Note the difference between the two methods: (a) for LECD the black calibration arrows point to the same location in one bin; (b) for LECE the arrows are the same one bin. Histogram binning applied with the LECE assumption (b) imitates the true calibration
map (c) more closely than the one applied with the LECD assumption (a). For details about the synthetic data calibration task, see Section 4.1
Both of the methods depicted in Figure la and Figure 1b depict the result of histogram bimning method applied in one-vs-resl style with 5 equal-width bins. Note that the classical histogram binning uses equal-size bins, but here equal-width width bins are used for clearer visualization. The only difference between the methods is the underlying assumption used: Figure la the LECD assumption used as classical histogram binning; the novel alternative Figure Db uses the LECE assumption. Note that the visualization in Figure La is very similar to the visualization of the higher-dimensional reliability diagrams used by Vaicenavicius al.
8

---

Published in Transactions on Machine Learning Research (06/2023)
2019 and even though they are technically the same, here Figure la does not depict reliability diagram, but rather the transformation of calibration method.
In both cases, the binning scheme defines the close neighborhoods, where we assume the corresponding assumptions to hold. With the classical LECD assumption, the end point of every calibrating arrow is the same one bin; with the novel assumption, the calibrating arrow itself the same in one bin. When comparing Figure Ia] and Figure Ib to Figure [c histogram binming applied with the LECE assumption provides closer imitation of the true calibration map than histogram binning applied with the LECD assumption. The visual intuition is also confirmed by the several mumeric metrics in provided in Table | in Section 4.1 showing that the histogram binning based on the LECE assumption is indeed closer to the true calibration map. The LECE assumption outperformed the LECD assumption on the real experiments as well (as shown in Section 4.2.4 and therefore preferred in this work.
Relation to prior work Neither the two assumptions are completely novel as estimators based on them have been used in previous work. However, the assumptions themselves have never been explicitly stated, An estimator based on the assumption of equal calibration errors has been used in at least two algorithms that use the average difference between the label and prediction in a close neighborhood. First, the widely used ECE calculation algorithm (Nacini et al. 2015) defines the close neighborhood with bins and in each bin uses the difference between the average label and average prediction value to estimate the calibration -
error - this is similar to the proposed assumption as k.
P. 1E
E Yz = E v.)) Socond,
the recently proposed decision calibration algorithum (Zhao et. al., 2021 also uses the average difference between the predictions and labels in a close neighborhood. In the decision calibration algorithm, the close neighborhoods are defined in each iteration by the partition.
An estimator based on the assumption of equal class distributions has also been previously used. It is the basis of the histogram binning method Zadrozny & Elkan 2001) where the close neighborhood is defined by the binning scheme; in each bin, the average one-hot label vector is used to calibrate the predictions. The weighted average one-hot label vector is also used in recent work by Popordanoska et al. (2021) for a training time calibration method, not a post-hoc calibration method. In their work, all the neighbors of a prediction are assigned weight with a kernel function; the weighted average of label vectors is then used to estimate the calibrated prediction.
Defining the close neighborhood For both assumptions, two open questions remain:
1. How many instances should the close neighborhood cover?
2. How should the close neighborhood be defined?
To answer the first question: the more neighbors taken, the less varying the estimators; however, the further away the neighbors are, the bolder the assumptions and the larger the bias from the assumption. Therefore, a sweet spot for the bias-variance tradeoff has to be found. This can be achieved if the used neighborhood scheme offers hyperparameter defining the neighborhood size. The hyperparameter could then be optimized with vross-validation with Brier score or log-loss.
There is no simple answer to the second question. Histogram binning and the ECE algorithun define the close neighborhood with binning scheme. However, the binning schemes are only defined for the binary case. The decision calibration algorithm (Zhao et al. 2021) defines the close neighborhoods by a linear partition that splits the probability simplex such that the calibration error estimates would be maximized. Popordanoska et al. (2021) define the neighborhood through assigning weights with kernel function.
3.2 LECE calibration
One intuitive approach would be to define the close neighborhood separately for every data point: for some prediction p, the close neighborhood could be defined by the closest instances on the validation dataset. Defining the neighborhood this way results basically in a modified k-nearest-neigee neighboos algorithm that we call LECE calibration. For any uncalibrated prediction p, LECE calibration would:
9

---

Published in Transactions on Machine Learning Research (06/2023)
1. Find the i closest predictions on the validation dataset PI. Pi..... P5 according to some neighborhood function d.
2. Estimate the calibration error of p by finding the average difference between its neighbors' prediction and label
k E y.)
1 k
neiigh (p)
(p.
CE(P)).
3. Subtract the calibration error estimate CE neigihh (f) from the uncalibrated prediction P to calibrate:
a(p) p C'Enihh
Similary to the LECE calibration algorithm, a LECD calibration algorithm could be defined as well, with the only difference being in the underlying assumption used instead of steps and 3 of the algorithm, the method would instead set the calibrated prediction equal to the average label value of the neighbors a(0) - E
For the neighborhood function d, we considered Kullback-Leibler divergence and Euclidean distance. As shown in the real data experiments in Section 4.2.4. Kullback-Leibler divergence performed slightly bet- ter. To find the neighbors of p, Kullback-Leibler divergence is applied as dKL( where dKL (f. f') = E Pi log ( and the term in the sum is considered equal to 0 if p. = 0 and oqual to 0o if f. + 0 and F. = 0. The number of classes is denoted by m.
Thresholding tiny probabilities A problem inherent to the non-parametric LECE (and LECD) calibra- tion method is its inability to work well for tiny probabilities. This is because the method uses an estimator, which has some built in errors coming from its bias and/or variance. For class probabilities that are very near to 0, these errors of the estimator become very large proportionally to the probability. To see this, consider a true class probability p; estimated based on & neighbours. In the ideal case where all the neighbours have the same true label distribution, the variance of this estimator is P=(--p.) Hence the estimator's relative
k
Vk /p. A-P. which becomes increasingly Vp..k large when pi gets small. This could even lead to situations, where the LECE method produces output that is smaller than 0 for some classes and could no longer be interpreted as probabilities. For example, consider f. = 0.01 and suppose the average prediction of its k neighbors is p = 0.03 and the average label ÿ = 0.01. In that case, the calibration error estimate is C'Eeeigh (fx) = 0.03 - 0.01 = 0.02 and the calibrat- ing transformation would be a(p.) = é. neigigh (p.) = 0.01 0.02 = -0.01, which is no longer the probability simplex. Therefore, to overcome this problem with small proba bilitie,,,, we opted to introduce one more parameter to the calibration method: a threshold value t E R which sets a lower limit when to apply the method. For any class probability smaller than 4, we do not apply the method. As the true class probability P. is unknown, then instead we apply this threshold on both the uncalibrated prediction Pa and the corresponding buuld-be-calibrated prediction a(p:). More precisely, given the prediction vector p, and the would-be-calibrated prediction vector a()) = f CFFneighh if for the i-th class A. S t or (,( S t, then we set (p) = Prs where 2(-) = (2)(),.... (.). Thresholding can cause the final output to no longer sum to 1, so to solve this, as a final step we divide the output vector by its sum. As shown by optimal threshold values chosen by hyperparameter tuning in the real experiments in Table II the LECE method chooses small threshold values ranging from t = 0 to = 0.02.
error (standard deviation divided by the true value) is VPP(L-pu))
Composition with parametric methods The authors of the decision calibration algorithm noticed that their proposed non-paraectric post-hoc calibration method works better if it is applied in composition with temperature scaling (Zhao el al., 2021). First, temperature scaling learns the calibration map on the validation dataset and then their method fine-tunes the result of temperature scaling using the temperature- scaled validation data. The benefit of composing parametric and non-parametric calibration mothods was also shown by Zhang et al. (2020) who noted that isotonic regression applied in a one-versus-rest manner works better if it is applied on top of temperature scaling. A similar observation is true for the proposed
10

---

Published in Transactions on Machine Learning Research (06/2023)
non-parametric LECE calibration method in this work well. The experiments on real data in Section 4.2 show that the proposed method loses to existing parametric post-hoc calibration methods when applied directly, but wins when applied on top of temperature scaling. From the experiments it can be concluded that on datasets with few samples per class, LECE alone is not strong cnough to compete with methods with parametric assumptions. However, LECE has ils merits being less constrained than its competitors, and therefore it can offer improvements on top of parametric methods, wherever they are limited by their parametric family. Additionally, the violations of the LECE asumptiin are likely diminish when the calibration errors become smaller, e.g. top of temperature scaling.
Algorithm 1: LECE calibration method
Input predictions on the validation set , Pn validation set labels Vi.....B0 Un
prediction to calibrate f
neighborhood size k
distance function d threshold
number of classes m
Output: calibrated prediction a(p)
D < distances d(ş: P.) for i in 1,...
+ indices of k smallest values from D
pp- : Lier
// average prediction
y <- & EiEID) y;
// average label
CE
calibration error estimate
a(p) + --CE
// //iiitial calibrated prediction
for i in 1....,m. m do
if P. St or E(p); then
a(p); + P.
//
thresholding
10
end
11 end
m 12 a(p) c(p) -/- a(p);
// ensure sums to
return e(f)
The complete pseudocode of LECE calibration with thresholding presented in Algorithm Note that if LECE calibration were be applied in composition with temperature scaling, then the only difference in Algorithm 1 would be that the input ......, P., and P would be the output of temperature scaling. A discussion the computational and memory complexity of Algorithm [ is given in Appendix A.2
To summarize, the LECE calibration method is essentially a k-nearest neighbors algorithm using the neigh- bors prodiction and label difference; the method involves thresholding of tiny probabilitics; and it works best when composed with a parametric method.
4 Experiments
The experiments' section consists two parts:
A small experiment on synthetically generated data. The goal of this experiment is to illustrate and give visual intuition about the different post-hoc calibration methods.
Larger experiments on two real datasets and three convolutional neural network classifiers. The goal of these experiments compare the proposed post-hoc calibration method with its competitors and see if it offer improvement the state-of-the-art.
11

---

Published in Transactions on Machine Learning Research (06/2023)
4.1 Synthetic data experiment
To illustrate the differences wetween the assumplion of locally equal calibration errors (LECE) and the as- sumption of locally equal class distributions (LECD), and the limitations of the existing post-hoc calibration methods, a synthetic dataset was created. A synthetic approach allows to define the true calibration function c(p) = EY|YYP P pp. which is not available in any real-world dataset.
4.1.1
Data generation
For the experiment, 3-class validation dataset consisting of 5000 prediction and label pairs, and test dataset consisting of 100000 prediction and label pairs were generated. Note that calibration applies on the predictions and does not depend on the original feature space, we are directly generating predictions without considering the features nor the classification model at all. Classifier predictions á were sampled from a 3- class Dirichlet distribution with parameters [0.5, 0.5, 0.5]; the label distributions were calculated by applying the chosen true calibration function c(p) = EY P) on the predictions; the labels were sampled from c(f). The chosen true calibration function is defined as c(f) (Øf + f f + f1-
3 . + fy where is the renormalizing term to sum to 1. The chosen function is depicted in Figure Ic and repeated again in Figure 2d for convenience. Note that the results of the synthetic experiment should be considered purely illustrative as the function e(-) was chosen rather arbitrarily and with different function the results could be different.
5
4.1.2 Compared post-hoc calibration methods
On the synthetic task several post-hoc calibration methods were evaluated:
Two different histogram binnings with equal-width bins: classical version with the LECD as- sumption (H-LECD) and novel version with the LECE assumption (H-LECE). The histogram binning methods were chosen to visualise the difference between the two assumptions formalized in Section
The visualization between the two assumptions is provided in Figure
Temperature scaling (TS) to illustrate the limitations of symmetric calibration methods which can only learn transformations that act the same way for all the classes. Temperature scaling was applied to log(f) no logits were available for the task.
Dirichlet calibration (DIR) to show the limited expressivity of the otherwise powerful parametric methods. Dirichlet calibration was fit without rogularization as the number of paramcters is low with 3 classes.
Our proposed LECE calibration method (LECE) to illustrate its merits. The method was applied with à = 500 neighbors and threshold value (thus applying thresholding only ensure that outputs are non-negative). Note that this synthetic calibration task is meant to be purely illustrative of different calibration methods, and therefore the hyperparameters of LECE were manually chosen to show that the method can work well given good hyperparameters. The experiments on real data where hyperparameters are tuned with cross-validation show that good hyperparameter values can be found in practice as well.
4.1.3 Results
The learned calibration maps of H-LECD and H-LECE are depicted in Figure [ the maps of all other methods are shown in Figure 2 Both the background colors and black arrows in both Figure I and Figure 2 depict the learned transformation. The same information that is represented by the arrow is also represented by the RGB color value which is in a linear relation with the calibration error vector at that point: red for class 1, green for class 2, and blue for class 3. Table [ contains the results of the synthetic experiment according to several different mumeric metrics; it shows the mean of 100 data generation seeds with the standard deviation. For synthetic experiments, the ECE measures replaced with the true calibration
12

---

Published in Transactions on Machine Learning Research (06/2023)
Table 1: Results the illustrative synthetic experiment: the mean and standard deviation over 100 data seeds is reported. For details of the applied mothods, see Section 4.1.2 H-LECD (in Figure lab is outperformed by H-LECE (in Figure lbp. TS (in Figure 2a) is limited by symmetry and loses DIR (in Figure 2bp. DIR is limited by its parametric family and loses to LECE (in Figure 2ch. The final column (truc) depicts the theoretical best result which is obtained by applying the true calibration map (in Figure 2d
oulrs
II-LECD
H-LECE
TS
DIR
LECE
confidence CE
0.056
0.001
0.019
0.002
0.030 + 0.002
0.022 0.004
0.018 + 0.003
0.000 0.000
classwise CE
0.049 + 0.001
0.016 0.001
0.027 0.000
0.018 1.00020002
0.015 0.002
0.000 + 0.000
Brier score
0.448 + 0.001
0.438 = 0.001
0.440 0.001
0,438 0.001
0.438 0.001
0.436 + 0.001
log-loss
0.772 0.002
0.749
0.010
0.751 0.002
0.747
0.002
0.742 + 0.002
0.738 0.002
accuracy
0.668 + 0.002
0.671 + 0.002
0.669 + 0.001
0.671 0.001
0.670 + 0.001
0.671 + 0.001
(a) Temperature scaling
(b) Dirichlet calibration
7
(c) LECE calibration (new)
(d) True calibration map
1.0
0.8
0.6
0.4
0.2
0.4
0.4
0.6
0.6
Pz
0.8
0.8
P
Figure 2: Illustrative example of calibration maps produced by different post-hoc calibration methods on a synthetic calibration task (a, b, c). The goal of the methods is to learn the true calibration map (d). Temperature scaling (a) limited by its symmetric calibration map. Dirichlet calibration (b) performs well, but is held back by its parametric family: fails to imitate the calibration arrows of the true calibration map (d) for small values of pr. LECE calibration (c) manages learn a transformation very similar to the true calibration map (d).
13

---

Published in Transactions on Machine Learning Research (06/2023)
errors (CE) as the true calibration function is known (sce Section 2.3 for details): CE is measured with =1 and the expectation is replaced with empirical test set average. The last column in Table | depicts the results when applying the true calibration map the theoretical best result the methods could achieve.
First, when comparing the two histogram binnings, it can be seen that the evaluation metrics in Table [ confirm the visual intuition available from Figure Ta and Figure Tbj the new proposed LECE assumption significantly outperforms the classical LECD assumption. Second, as seen in Figure 2a temperature scaling is clearly not sufficient for the task it is limited to symmetrical transformation. Third, Dirichlet calibration, one of the strongest existing competitors learns result close to the true calibration map, but is held back by its parametric family: note its bad performance for values close to 0 for P as the learned calibration arrows there are not similar to the arrows of the true calibration map. Overall, the proposed LECE calibration method depicted in Figure 2c learns the most similar transformation to the true calibration map.
4.2 Real data experiments
The goal of the real data experiments is to see if the proposed method can improve state-oftthe-art in practical settings.
4.2.1 Datasets and models
CIFAR-10 and CIFAR-100 datasets Krizhevsky 2009 are used for the experiments. On both of the datasets,
the predictions of convolutional neural networks ResNet-110 (He et al. 2016), ResNet Wide 32 (Zagorukoo & Komodakis 2016), Net4eNet-40 (Huang et al. 2017 are used. The precomputed logits of these three
CNN-s were provided by Kull et al. (2019), and the same validation and test split of the logits was used
as in the experiments of Kull et al. (2019 and Rahimi al. (2020). An overview of the used datasets,
classifiers, and dataset sizes is given in Table 2
4.2.2 Compared post-hoc calibration methods
On the real datasets the following methods are compared:
Uncalibrated predictions (uncal) to have baseline.
Matrix scaling with ODIR (MS); best hyperparameters for the dataset and classifier combinations were provided by the authors of ODIR for matrix scaling (Kull al. 2019
Diagonal subfamily of intra-order preserving functions (IOP); best hyperparameters for the dataset and classifier combinations were obtained from the original article (Rahimi el al. 2020
Gaussian process calibration (GP) applied on logits (Wenger et al.
2020
Temperature scaling (TS) Guo et al. 2017
Datasets and model details for the real experiments. The precomputed logits were provided by Kull et al. (2019) and the validation and test split of the logits was used in the experiments of
Table 2:
Kull et al. 2019 and Rahimi et al. (2020)
Dataset size
Dataset
Models
Classes
Training
Validation
Test
CIFAR-10
DenseNett40
10
45000
5000
10000
ResNet-110
ResNet Wide 32
CIFAR-100
DenseNett40
100
45000
5000
10000
ResNet-1100
ResNet Wide 32
14

---

Published in Transactions on Machine Learning Research (06/2023)
Decision calibration (hao et al. 2021 trained to achieve decision calibration with respect to all loss functions with 2 decisions; number of trained iterations was determined by looking at the test set (!) Brier score to save computational resources, thus giving a slight unfair advantage to this method; the final output was normalised to sum to 1 which was not done in the original implementation but inevitable for log-loss evaluation; applied composition with temperature scaling (TS+DEC) as recommended by the original paper.
Isotonic regression calibration (Zadrozny Elkan 2002) appliod a one-vs-rest approach (IR) and the same method in composition with temperature scaling (TS+IR) proposed by Zhang el al.) (2020). In both cases, the final output is normalized by dividing the output vector with its sum.
Our proposed method; optimal hyperparameters were found with 10-fold cross-validation grid search optimized by log-loss from neighborhood size proportions q of the training dataset {0.01, 0.02, 0-03, 0.04, 0.05, 0.06, 0.07, 0.2, 1.0), and threshold values I e {0, 0.00125, 0.0025, 0.005, 0.01, 0.02, 0.04, 0.05, 0.10, 1.0]. Note that including t = 1 as possible value allows the calibration mothod to learn the identity map. Neighborhood size proportion 0.01 stands for 0.01 5000 = neighbors in the validation set and 0.01 4500 45 neighbors one fold of the 10-fold gross-validation as there are 5000 total data points in the validation set. The reason for using fixed proportion q instead of fixed number of neighbors borhood would cover approximately the same subregion of the probability simplex data folds of different sizes. LFCE calibration is applied in composition with temperature scaling (TS+LECE) and without temperature scaling (LECE).
g k/n
to ensure that the neigh-
For methods applied in composition with temperature scaling, temperature scaling is always applied first.
4.2.3 Results
In the following paragraphs the results for confidence ECE, classwise ECE, log-loss, and accuracy are pre- sented.
Confidence ECE Table presents the results for confidence ECE. Both confidence and classwise ECE are measured with 15 equal-sized bins also known data dependent bins according to the formulas described in Section 2.4 According to confidence ECE, the best performing methods are GP and our proposed method TS+LECE. Without TS, LECE performs poorly on the real datasets: it is heavily outperformed by every other method. However, when applied in composition with TS, the result of TS is improved for 5 out of 6 cases.
Table 3: Confidence ECE (x 10 applied with 15 equal-sized bins according to the formula described in Section 2.4 For details of the applied methods see Section 4.2.2 In every row, the methods are ranked and the rank is displayed as a subindex, the best performing method is also highlighted in bold. On average, the best performing methods are Gaussian process calibration (GP) and our proposed method TS LECE.
ours
ours
uncal
IR
LECE
MS
IOP
GP
TS
DSC
TS
TS LECE
C-10
DenseNet-40
5.4910
1.67g
3.72g
0.91,
0.80g
0.863
0.92,
1.13g
1.39,
0.691
ResNet-110
4.7510
1.44g
3.31g
0.99;
0.91g
0.882
0.94,
1.01g
1.027
0.65,
ResNet Wide 32
4.4810
1.07s
2.05g
0.75g
0.69,
0.39,
0.69a
0.767
0.69g
0.60z
average rank
10.0
8.0
9.0
5.0
2.7
2.0
4.0
6.3
5.7
1.3
C-100
DenseNet-40
21.16T0
4.86g
10.49g
1.22,
3.45,
0.89
0.79,
3.85;
2.12;
1.183
ResNet-1100
18.48
5.80g
6.36g
2.31,
2.80,
1.89,
2.133
3.40,
3.176
1.99,
ResNet Wide 32
18.7810
5.74g
15.53g
1.85g
1.043
0.872
1.41,
3.347
2.95g
0.851
average rank
10.0
8.0
9.0
4.3
1.7
2.7
7.0
5.7
2.0
15

---

Published in Transactions on Machine Learning Research (06/2023)
Table 4: Classwise ECE (x10²) applied with 15 equal-sized bins according to the formula described in Section 2.4 For details of the applied methods see Section 4.2.2 In every row, the methods are ranked and the rank is displayed as a subindex, the best performing method is also highlighted in bold, On average, the best performing methods
matrix scaling (MS) and our proposed method TS+LECE. Row CIFAR-10 ResNet Wide 32 illustraires the limitations of symmetrical methods, where all symmetrical methods (IOP, GP, TS) offer minimal improvements over uncalibrated predictions.
ours
ours
uncal
IR
LECE
MS
IOP
GP
TS
TS+DEC
TS+IR
TS+LECE
C-10
DenseNet-10
0.44510
0.280;
0,411p
0.2144
0.2513
0.259;
0.255,
0.291s
0.2644
0.2342
ResNet-110
0.
0.260s
0.297g
0.180,
0.212;
0.215g
0.216,
0.2487
0.2346
0.216;
ResNet Wide 32
0.49610
0.319
0.292,
0.1811
0.452,
0.440,
0.446a
0.282;
0.2462
0.2462
average rank
10.0
7.0
7.7
1.0
4.7
5.0
5.3
6.3
4.7
2.7
C-100
DenseNet-40
0,130g
0.1177
0.20610
0.0952
0.110s
0.102,
0.102,
0.139g
0.095²
0.0941
ResNet- 110
0.132,
0.1197
0.15910
0.110;
0.0964
0.0921
0.0943
0.135g
0.1146
0.092:
ResNet Wide 32
0.124g
0.122,
0.13610
0.094z
0.105,
0.105;
0.103,
0.121g
0.096g
0.089,
average rank
8.0
7.0
10.0
3.0
5.0
3.3
3.7
8.7
3.7
1.0
Classwise ECE Table ! presents the results for classwise ECE. Note that classwise ECE values tend to be a lot smaller than confidence ECE: this is due to the fact that most predictions coming from the softmax function are tiny and wash out the ECE score (Nixon et al.) 2019). On CIFAR-10, matrix scaling clearly the best performing method. On CIFAR-100 our proposed LS+LECE performs best but only marginally: many other hoth offer similar scores. The results CIFAR-10 ResNel Wide 32 expose the limitations of symmetrical methods that perform the same transformation for all the classes. For that case, TOP, GP, and TS all fail and produce bad classwise ECE scores around 0.440 which is only slightly lower than the uncalibrated result 0.496. Methods not limited by symmetry offer substantially better results, all producing scores less than 0.320 with matrix scaling even reaching as low as 0.181. Without TS, LECE performs again poorly: for CIFAR-100 even worsens the result uncalibrated predictions. However, similarly to confidence ECE, when applied in composition with TS, it offers consistent improvements over TS.
Log-loss Table 5 displays the results for log-loss. The best method according log-loss is clearly matrix scaling, being ranked first every time. The second best method is our proposed TS+LECE. The limitations of symmetrical methods can be seen according to log-loss well: CIFAR-10 ResNet Wide 32, IOP, GP, and TS perform worse than MS and TS+LECE. Without TS, LECE again performs poorly, but in composition with TS, it consistently offers improvements over TS.
Table 5: Log-loss. For details of the applied methods see Section 4.2.2 every row, the methods are ranked and the rank is displayed as a subindex, the best performing method also highlighted in bold. On average, the best performing method is matrix scaling (MS) followed by our proposed TS+LECE.
uncal
TR
LECE
MS
TOP
GP
TS
TS+DEC
TS+IR TS+LECE
C-10
DeuseNet-40
0.4281o
0,268
0.310,
0.222,
0.225g
0.226;
0.225g
0,266,
0,261g
0.223
ResNet-110
0.35810
0.250,
0,267,
0.204,
0.208,
0.206,
0.209;
0.232,
0.254g
0.206g
ResNet Wide 32
0.38210
0.214g
0.264g
0.182,
0.192;
0.191s
0.191s
0.234s
0.219;
0,1852
average rank
10.0
7.0
9.0
1.0
4.0
3.3
3.7
7.0
7.0
2.0
C-100
DenseNet-40
2.01710
1,367,
1.739,
1.047,
1.066;
1.056;
1.057,
1.338
1.442a
1.054g
ResNet-110
1.6941
1.619g
1.4987
1.073;
1.105s
1.082,
1.092.
1.453s
1.591s
1.085g
ResNet Wide 32
1.80210
1.3657
1.576,
0.931,
0.9454
0.939g
0.9454
1.284s
1.4019
0.9372
average rank
10.0
7.7
8.3
1.0
4.7
2.7
4.0
6.0
8.0
2.3
16

---

Published in Transactions on Machine Learning Research (06/2023)
Table 6: Classifier accuracy. For details the applied methods see Section 4.2.2 In every row, the methods are ranked and the rank is displayed a subindex, the best performing method is also highlighted in bold. There are no large differences between the methods. Only notable value is isotonic regression combined with temperature scaling (TS+IR) on CIFAR-100 ResNet-110, where it reduces accuracy from 0.715 to 0.710.
OUTS
uncal
IR
LECE
MS
IOP
GP
TS
TS+DEC
TS++R
TS+LECE
C-10
DenseNet-40
0.924g
0.924g
0.924g
0.925,
0.9243
0.924g
0.924g
0.924g
0.924g
0.9251
ResNet-110
0.936,
0.936,
0.936,
0.936,
0.936,
0.935g
0.936,
0.936,
0.935g
0.936,
ResNet Wide 32
0.9397
0.940s
0.940s
0.9421
0.9397
0.9397
0.939,
0.9413
0.9413
0.9421
average rank
3.0
3.0
1.0
3.7
6.3
3.7
2.3
5.0
1.0
C-100
DenseNet-40
0.700,
0.7004
0.700,
0.704,
0.7004
0.7004
0.700,
0.702g
0.69710
0.704,
ResNet-110
0.715g
0.712g
0.715g
0.715g
0.715g
0.715g
0.715g
0.7161
0.71010
0.7161
ResNet Wide 32
0.738
0.738
0.7384
0.7401
0.7384
0.738
0.738
0.7401
0.73610
0.740,
average rank
3.7
5.7
3.7
1.7
3.7
3.7
3.7
1.7
10.0
1.0
Accuracy Table presents accuracies of the methods on the test set. None of the methods offer substantial improvements in accuracy, nor do any of the methods have considcrable detrimental effects. In general, the methods perform very similarly. The only notable value is TS+IR on CIFAR-100 ResNet-110, where it reduces accuracy of the uncalibrated classifier from 0.715 to 0.710.
4.2.4 Ablation study
To understand the importance of the neighborhood function used in the LECE calibration algorithm, and compare LECE calibration with LECD calibration, we repeat. the real data experiments for the following methods
LECE calibration with Fuclidean distance instead of Kullback-Leible divergence (LECE and TS+LECEeuc>;
otherwise the same method as LECE calibration but using the LECD assumption instcad of the LECE assumption (LECD and TS+LEC
LECD calibration as described in Section 3.2
The method parameters were choson with 10-fold cross-validation from the same parameter sets as for LECE calibration described in Section 4.2.2 Table presents the results for confidence ECE, Table S the results for
Table 7: Ablation study, confidence ECE (x10²) applied with 15 equal-sized bins according to the formula described in Section 2.4. For details of the applicd methods see Scction 4.2.4 every row, the methods are ranked and the rank displayed as subindex, the best performing method also highlighted in bold. On average, the best performing method is TS+LECE.
LECE
LECE
LECD
LS+LECE
+
LSCD
C-10
DenseNet-40
3.72s
3.304
3.43;
0.691
0.762
1.193
ResNet-111
3.31
3.20s
2.694
0.65,
0.662
0.94g
ResNet Wide 32
2.05g
2.936
1.934
0.60g
0.532
0.50,
average rank
5.7
5.0
4.3
1.7
2.0
2.3
C-100
DenseNet-40
10.49;
11.16g
5.974
1.182
1.213
0.791
ResNet-110
6.36;
12.026
3.534
1.992
2.033
1.711
ResNet Wide 32
15.53g
14.21;
5.764
0.851
1.162
1.413
average rank
5.3
5.7
4.0
1.7
2.7
1.7
17

---

Published in Transactions on Machine Learning Research (06/2023)
Table 8: Ablation study, classwise ECE (x (x10") applied with equal-sized bins according to the formula described in Section 2.4 For details of the applied methods see Soction 4.2.4 every row, the methods are ranked and the rank displayed as subindex, the best performing method is also highlighted in bold. On average, the best performing method is TS+LECE.
LECE
LECE LECD)
TS+LECE TS+LECEeus
TS+LECD
C-10
DenseNet-440
0.4114
0.670,
0.453;
0.2341
0.238
0.2673
ResNet- 110
0.2974
0.5576
0.335;
0.216,
0.2021
0.2162
ResNet Wide 32
0.292;
0.7326
0.2854
0.2461
0.2742
0.2773
average rank
4.3
6.0
4.7
1.3
1.7
2.7
C-100
DenseNet-40
0.251;
0.3366
0.1724
0.0941
0.0962
0.1023
ResNet-110
0.159,
0.269,
0.1234
0.0921
0.0953
0.0921
ResNet Wide 32
0.137;
0.332
0.1264
0.089,
0.0952
0.1033
average rank
5.0
6.0
4.0
1.0
2.3
2.3
Table 9: Ablation study, log-loss. For details of the applied methods see Section 4.2.4 In every row, the methods are ranked and the rank displayed subindex, the best performing method is also highlighted in bold. The best performing method is TS+LECE.
LECE
LECEcue
LECD
TS+LECE
+S+LECEeus
TS+LECD
C-10
DenseNeet-40
0.310;
0.3054
0.3196
0.2231
0.2242
0.2263
ResNet- 110
0.267;
0.2654
0.2796
0.206,
0.2061
0.209g
ResNet Wide 32
0.264;
0.2604
0.272
0.185,
0.1872
0.1883
average rank
5.0
4.0
6.0
1.0
1.7
3.0
C-100
DenseNet-40
1.739g
1.681s
1.4374
1.0541
1.0541
1.0573
ResNet-110
1.498;
1.5166
1.3064
1.085,
1.087₂
1.0923
ResNet Wide 32
1.5766
1.544,
1.2724
0.9371
0.9412
0.9453
average rank
5.7
5.3
4.0
1.0
1.7
3.0
classwise ECE, and Table 1 the results for log-loss. The three tables are discussed unison, as the methods are ranked similarly across the tables, and the key conclusions to be made from the tables are the same.
The best method on average in all the tables is TS+LECE. TS+LECE outperforms its derivative with Euclidean distance TS+LECFFew in almost all cases with a few exceptions: it loses once in confidence ECE, once in classwise ECE, and is tied twice in log-loss. TS+LECE outperforms TS+LECD as well: it performs better in 13 cases, is tied in 2, and loses in 3 out of the 18 total rows in the three tables.
When comparing the methods with and without TS, it can be seen that TS crucial for all of them. Adding the composition with TS improves the result in all cases and by a very large margin. For cases without TS, LECE and LECE perform otherwise similarly but for classwise ECE the method LECE.se fails. Therefore, similary to the LECE methods applied in composition with TS, Kullback-Leiba be concluded to perform better than Euclidean distance for the non-compositional case as well. Comparing LECE with LECD, LECE seems to perform better for CIFAR-10 but LECD for CIFAR-100. Yet, as the compositional TS+LECE methods heavily outperformed the non-compositonal LECE methods, the final conclusion would still be that LECE assumption is better than the LECD assumption.
divergence
Table I0 shows the optimal neighborhood proportion parameter q chosen by the 10-fold cross-valie cross-validation for the methods. Many different values represented, starting from 0.01 corresponding to 0.01 5000 50
18

---

Published in Transactions on Machine Learning Research (06/2023)
Table 10: Optimal neighborhood proportion & chosen by cross-validation. Commonly chosen values are between 0.01 and 0.1 (corresponding respectively to 50 and 500 neighbors). In some cascs the value 1.0 is also chosen corresponding to the whole 5000 validation data points. For TS+LECE, the neighborhood proportion remains in range between 0.01 to 0.04 corresponding to 50 to 200 neighbors.
LECE
LECE
LECD
TS+LECE
TS+LECEeue
TS+LECD
C-10
DenseNet-40
0.04
0.1
0.04
0.04
0.03
0.07
ResNet-1110
0.06
0.1
1.0
0.03
0.02
0.01
ResNet Wide 32
0.02
0.1
0.02
0.01
0.01
0.01
C-100
DenseNet-40
0.05
0.03
1.0
0.01
0.02
0.01
ResNet- 110
0.01
0.05
1.0
0.04
0.03
0.01
ResNet Wide 32
1.0
0.03
1.0
0.04
0.05
0.01
Table 11: Optimal threshold chosen by cross-validation, For methods applied without TS, values close are chosen, corresponding to thresholding. For methods applied in composition with TS, the chosen threshold values are usually small: between 0.0025 and 0.02. In three cases, TS-LECD has chosen t 1.0 meaning it has learned the identity transformation.
LECE
LECE
LECD
LS+
TS+LECE
TS+LECD
C-10
DenseNet-40
0
0
0
0.0025
0.0025
0.1
ResNet-110
0
0
0.05
0.01
0.01
1.0
ResNet Wide 32
0
0
0
0.01
0.02
0.05
C-100
DenseNet-40
0
0
0.005
0.02
0.02
1.0
ResNet-110 110
0
0
0.005
0.01
0.02
0.1
ResNet Wide 32
0
0
0.005
0.005
0.005
1.0
neighbors, up 1.0, corresponding to the whole validation dataset of 5000 neighbors. For TS+LECF the neighborhood proportion remains in range between 0.01 to 0.04 corresponding to 50 to 200 neighbors.
Table 11 shows the optimal threshold parameter chosen by the 10-fold cross-validation. For methods applied without TS, 0 seems to be a good value as it was chosen by LECE and LECE in all cases. For methods applicd in composition with TS, the chosen threshold values remain usually small: between 0.0025 and 0.02. TS+LECD an exception as uses larger threshold values. three cases out of six even picked / 1.0, meaning it learned the identity map and kept the result of TS.
The rumning times of LECE and LECD calibration are discussed in Appendix A.3
4.2.5 Discussion
Overall, from the experiments it can be concluded that while many strong methods exist, our proposed TS+LECE can still offer improvements. Symmetrical methods IOP, GP, and TS perform generally well, but can fail for problems where asymmetrical transformations are needed as shown by classwise ECE and log-loss on CIFAR-10 ResNet Wide 32. Matrix scaling could be considered the best method according classwise ECE and log-loss, but according to confidence ECE it is clearly outperformed by other methods. TS+LECE avoids the problems of symmetrical methods and offers the best confidence ECE, being second best in classwise ECE and log-loss.
Another aspect to notice from the experiments, is the behaviour of LECE with the number of classes. On the illustrational synthetic task with classes the method performs very well without TS. However, on the real tasks with 10 and 100 classes, the method fails unless it used on top of TS. This is due problems arising from the curse of dimensionality inherent to the proposed parameeriii approach. In higher dimensions, the probability space is more sparsely populated every data point starts to become approximately equally
19

---

Published in Transactions on Machine Learning Research (06/2023)
distant from every other data point. Because of this, the neighborhood sizes grow and the applied assumption of locally equal calibration errors becomes very bold, lowering the effectiveness iveness of the method. However, applying LECE on top of TS makes the assumption to be more realistic, as the calibration errors are smaller after TS and hence the errors of neighbors are more similar, as required by the LECE assumption.
5 Conclusion
This work explored the field of post-hoc calibration methods for multi-class classifiers. Two assumptions about the true calibration map were formalized that have been previously used for creating estimators, but despite this have never been clearly stated: assuming locally equal calibration errors (LECE) and assuming locally equal class distributions (LECCD). Based on the more reasonable of the assumptions, a non-parametric calibration method was proposed - LECE calibration. The used assumption states that the calibration error of a data point can be modeled by the calibration errors of its neighbors. This results in using the average difference of predictions and labels in a close neighborhood to estimate the calibration error of a prediction. Based the definition of calibration, the found calibration error estimate is then subtracted from the prediction to reach calibrated prediction.
Experiments were carried out on three convolutional neural networks trained on CIFAR-10 and CIFAR-100 to compare the proposed method with its competitors. The experimental results on real data showed that the proposed method alone is clearly not competitive for cases with many classes and a limited validation dataset due to problems arising from the curse of dimensionality. However, when applying the proposed method in composition with temperature scaling, it tops the state-of-the-art in confidence ECE and is close to the best according to classwise ECE and log-loss.
For future work, the limitations of the proposed approach could be studied more thoroughly. How does improvement in calibration depend on the number of classes in the dataset; on the validation dataset size; or on the distribution of the predictions? In addition, the composition of different calibration methods could studied further as this work and several previous [Zhang et al. 2020 Zhao et al. 2021 have shown the possible benefits.
Acknowledgments
This work was supported by the European Social Fund via IT Academy programme, Estonian Research Council grant PRG1604, and by the Estonian Centre of Excellence in IT (EXCITE), funded by the European Regional Development Fund.
References
Yu Bai, Song Mei, Huan Wang, and Caiming Xiong. Don't just blame over-parametrriation for over- confidence: Theoretical analysis of calibration in binary classification. In International Conference on Machine Learning, pp. 566-576. PMLR, 2021.
Lucas Clarté, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. A study of uncertainty quantification in overparametrized high-dimensional models. arXiv preprint arXiv:2210.12700 2022a.
Lucas Clarté, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Theoretical characterization of uncertainty in high-dimensional linear classification. arXiv preprint arXiv:2202.03295 2022b.
Morris H DeGroot and Stephen E Fienberg. The comparison and evaluation of forecasters. Journal of the
Royal Statistical Society: Series D (The Statistician), 32(1-2):12 22, 1983.
Pedro M. Domingos and Michael J. Pazzani. Beyond Independence: Conditions for the Optimality of the Simple Bayesian Classificr. In ICML, 1996.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On Calibration of Modern Neural Networks. In International Conference Machine Learning, pp. 1321-1330, 2017.
20

---

Published in Transactions on Machine Learning Research (06/2023)
Chirag Gupta and Aaditya Ramdas. Top-label calibration and multiclass-to-bnnary reductions. In
International Conference on Learning Representations, 2022. URL. htttps://ppenreviex wttpe/eewwiieeeeeffuuuue..
id=WqoBaaPHS-
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Doep Residual Learning for Image Rocognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770 778, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely Connected Convolu- tional Networks. Tn Proceedings of the TEEE conference on computer vision and pattern recognition, pp. 4700 4708, 2017.
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. 2009. URL https: www.ss. toronto.. wow.nto..du/-kriiz///. fwwearrrnnnn--aaaae--------- 2009-02- pdf
Meelis Kull and Peter Flach. Novel Decompositions of Proper Scoring Rules for Classification: Score Ad- justment as Precursor to Calibration. Machine Learning and Knowledge Discovery in Databases, pp. 68-85, 2013.
Meelis Kull, Telmo Silva Filho, and Peter Flach. Beta calibration: well-founded and easily implemented im- provement on logistic calibration for binary classifiers. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 623-631, 2017.
Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach. Be- yond temperature scaling: Obtaining well-calibrated multi-class probabilities with Dirichlet calibration. Advances neural information processing systems, 32, 2019.
Ananya Kumar, Percy Liang, and Tengyu Ma. Verified Uncertainty Calibration. Advances in Neural Information Processing Systems, 32, 2019.
Aviral Kumar, Sunita Sarawagi, and Uiiwal Jain. Trainable Calibration Measures for Neural Networks from Kernel Mean Embeddings. In International Conference Machine Learning, pp.
2018.
Balaji Takshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and Scalable Predictive Uncer- tainty Estimation using Deep Ensembles. Advances in neural information processing systems, 30, 2017.
Christian Leibig, Vaneeda Allken, Murat Seçkin Ayhan, Philipp Berens, and Siegfried Wahl. Leveraging uncertainty information from deep neural networks for discase detection. Scientific reports, 7(1):1-14, 2017.
Tsung- Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal Loss for Dense Object Detection. In Proceedings of the IEEE international conference on computer vision, pp. 2980-2988, 2017.
Wesley J Maddox, Pavel Iamailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson. A Simple Baseline for Bayesian Uncertainty in Deep Learning. Advances in Neural Information Processing Systems, 32, 2019.
Jishmu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip Torr, and Puneet Dokania. Calibrating Deep Neural Networks using Focal Loss. Advances in Neural Information Processing Systems, 11115288-12299 2020.
Rafael Müller, Simon Kornblith, and Geoffrey E Hinton. When Does Label Smoothing Help? Advances in neural information processing systems, 32, 2019.
Mahdi Pakdaman Nacini, Gregory Cooper, and Milos Hanskrecht. Obtaining Woll Calibrated Probabilities Using Bayesian Binning, In AAAI Conference on Artificial Intelligence, 2015.
Alexandru Niculescu- and Rich Caruana. Predicting good probabilities with supervised learning. In Proceedings of the 22nd international conference Machine learning, pp. 625 632, 2005.
21

---

Published in Transactions on Machine Learning Research (06/2023)
Jeremy Nixon, Michael W Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Calibration in Deep Learning. In CVPR Workshops. volume 2, 2019.
Measuring
Kanil Patel, William H. Beluch, Bin Yang, Michael Pfeiffer, and Dan Zhang. Multi-class uncertainty cal- ibration via mutual information maximization-basel binning. In International Conference Learning Representations, 2021. URL
John C. Platt. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likeli- hood Methods. In Advances in large margin classifiers, pp. 61-74, 1999.
Teodora Popordanoska, Raphael Sayer, and Matthew B Blaschko. Calibration Regularized Training of Deep Neural Networks using Kernel Density Estimation. 2021. URL https://openreviee..eee wwt.forrummuueeem
1-1FH8oYTI
Amir Rahimi, Amirreza Shaban, Ching-An Cheng, Richard Hartley, and Byron Boots. Intra Order- Preserving Functions for Calibration of Multi-Class Neural Networks. Advances in Neural Information Procossing Systems, 33: 11111331116666 2020.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the Inception Architecture for Computer Vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and Thomas Schön. Evaluating model calibration in classification. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 3459-3467, 2019.
Kaspar Valk. Calibration of Multi Probabilistic Classifiers. Master's thesis, University of Tartu, 2022.
URL https://comserv.cc cs
www.c......e...ee wt. www.w.......e..ticoooo.e.. phaasss//ataaahett.ppp/77///9992
Jonathan Wenger, Hedvig Kjellström, and Rudolph Tricbel. Non-Parametric Calibration for Classification.
In International Conference on Artificial Intelligence and Statistics, pp. 178 190, 2020.
Bianca Zadrozny and Charles Elkan. Obtaining Calibrated Probability Estimates from Decision Trees and Naive Bayesian Classifiers. ICML, 1, 2001.
Bianca Zadrozny and Charles Elkan. Transforming Classifier Scores into Accurate Multiclass Probability Estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 694-699, 2002.
Sergey Zagoruyko and Nikos Komodakis. Wide Residual Networks. In Proceedings of the British Machine Vision Conference (BMVC), pp. 87.1-87.12, 2016.
Jize Zhang, Bhavya Kailkhura, and T Yong-Jin Han. Mix-n-Match: Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning. In International Conference on Machine Learning, pp. 11117-11128, 2020.
Shengjia Zhao, Michael P Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon. Calibrating Predictions to Decisions: Novel Approach to Multi-Class Calibration. In Thirty-Fifte Conference on Neural Information Processing Systems, 2021.
A Appendix
A.1 Example of different calibration definitions
As toy example illustrate the different definitions of calibration, consider 3-class classifier for which P can take two equally likely values
p= 0..30.)3))) or p (0.6, 0.2.0..200.2)
22

---

Published in Transactions on Machine Learning Research (06/2023)
Now suppose that the corresponding expected label values for these predictions are Such classifier would not be multi-class calibrated as
Ey Y = (0.6, 0.3, 0.1 = (0.5, 0.3, 0.2) and
Ey Y|P (0.6, (0.6.0.2.0.))
(0.7,0.2,0.1)
Ey Y P = (0.6, 0.10 *
0.1), and also
Ey Y p (0.6,0.2.0.2)
* (0.6,0.2.0.2).
The classifier would also not be classwise calibrated as
By
Y3| 0.1 * 0.1, and also
Ey Ys|P3 0.2
0.2.
However, the classifier would be confidence calibrated as
Ey Y Yargmaz P mar P = 0.6 = 0.5 0.7 0.6.
A.2 Computational and memory complexity of LECE calibration
The complete pscudocode LECE calibration with thresholding was presented in Algorithm The LECE calibration method is essentially a variation of the i-nearest-ncighhors algorithm and its exact memory and computational complexity depends on the implementation. The LECE calibration method does not need any training, but has heavy computational and memory complexity during inference time. On a validation set with size a test set with size y, m classes, and h neighbors, the total computational complexity of our implementation is O(m - x y) and it is caused by line of Algorithm [ which needs O(m x) calculations for a single test set data point. The memory complexity of our implementation is O(x m b + -), where S y is a batch size parameter. The memory complexity O(x m - b) is caused by line 1 of the algorithm, where the distances are calculated with matrix operations applied on test set batches of size The Oy m) is also needed as the test dataset has to be kept in memory during inference time.
A.3 Running times of LECE calibration
The LECE method requires no time for training but considerable time for inference as discussed in Ap- pendix A.2 The real data experiments were implemented in Python and run on a machine with 16 GBs of RAM and CPU with clock speed 3.7 GHz. For CIFAR-10 DenseNet-40, LECE calibration with the best hyperparameters reported in Table TO and Table 11 took 4.7s to calibrate the 10000 test set data points given the 5000 validation set data points (average running time over 10 runs). For CIFAR-100 DenscNet-40, the average running time over 10 runs was 34.2s.
By far the most computationally expensive part of the LECE calibration method is the calculation of distances in line 1 of Algorithm | For CIFAR-10, line 1 accounted for 85% of the running time (4.0s of 4.7s), and for CIFAR-100 it was even 97% (33.2s of 34.2s). The second most computationally expensive part of the algorithm is finding the & closest neighbors in line 2 of Algorithm D For CIFAR-10, line 2 accounted for 13% of total running time, and for CIFAR-100 it was 2%.
The running times for the LECD calibration method were very similar to LECE; as were the running times for TS+LECE and TS+LECD as temperature scaling requires only a fraction of a second for training and evaluation. For example, TS+LECE took 4.9s to train the calibration method and evaluate the 10000 test set points on CIFAR-10 10 DenseNet-40: and for CIFAR-100 DenseNet-40 it was 34.8s (average of 10 runs). The running times for ResNet- and ResNet Wide-32 were similar to DenseNet-40.
23


Reviews:
[{"review_id": "OygrB9tZlp", "reviewer": "Reviewer_xZn1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength:\n\nI liked the proposed LECE principle. It is simple, makes complete sense, and as far as I know has not been studied before. Figure 1 is quite useful and the paper is easy to read until the end of Section 3. Experiments suggest the method works well. The authors go beyond only comparing to other calibration methods, also studying the following aspects:\n\n- the effect of scaling before applying LECE,\n- two notions of distance and their parameters, \n- dealing with near-zero probabilities by thresholding,\n- behavior with respect to multiple calibration notions as well as proper scoring rules.\n\nOnce revised and published, I think the LECE method/principle will be a valuable addition to the calibration community. \n\n### Weaknesses: \n\n- No 1-v-rest baselines are reported in the empirical comparisons. While some reasons are briefly indicated on page 4 for ignoring 1-v-rest methods (\"There are two ... deforms the calibrated probabilities\"), no citations or experiments are included. I am aware of at least a couple of papers (https://arxiv.org/pdf/2107.08353.pdf, https://arxiv.org/pdf/2006.13092.pdf) where it was shown that 1-v-rest methods can outperform some full-vector scaling methods that you considered. \n\n- Some presentation aspects need to be strengthened, as elaborated in the \"requested changes\" segment. Particularly, the experiments and tables can be improved significantly. Other issues were the misnomer of \"histogram binning\" for fixed-width binning, lack of good motivation for thresholding small probabilities, and not reporting standard deviations (or other measures of statistical uncertainty) in the empirical findings. \n\n- The technical discussion around LECE on page 6 is limited and informal. I think it is better to be informal and brief than to have meaningless theory, so I have not requested a revision on this front. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The LECD principle is inherent in many post-hoc calibration methods such as temperature scaling, histogram binning, isotonic regression, fixed-width binning, Dirichlet calibration, etc. The LECD principle being: locally (with respect to the pre-hoc classifier), the true label distribution is approximately equal. \n\nThe authors propose an alternative LECE principle: locally (with respect to the pre-hoc classifier), calibration errors are approximately equal. New calibration methods can be derived based on the LECE principle, and these seem to outperform existing methods that are based on the LECD principle. This is demonstrated through an illustration on synthetic data, and standard baselining on CIFAR-10 and CIFAR-100 (with deepnets).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Major:\n\n- Please add one or two 1-v-rest baselines in the empirical comparison (perhaps based on histogram binning/Platt scaling/isotonic regression/ Bayesian binning in quantiles, etc). \n- Histogram binning has bins with equal mass, whereas the method you have used in experiments is equal-width binning. Please refer to the method you are using as equal-width binning to avoid confusion. \n- Supplement all tables with meaningful captions following standard scientific conventions. In general, the experiments section is currently not well-organized: float placement is not standard (middle of pages instead of top), and the lists of methods split across pages too many times. Not everything needs to be standard but too many deviations are not ideal. \n- For instance, Table 1 appears suddenly in the middle of Sec 4.1 without a caption and without introducing the acronymized methods. The table should perhaps be on top of the following page, and a caption should be included summarizing the takeaway message, describing what the subindices are, what \"true\" means in the last column, etc (I mention the things that were unclear to me, but other things could be unclear to other readers, so please include a comprehensive caption).\n- Sec 4.1: you mention averaging over 10 seeds, but no standard deviation is reported. Thus, I am not sure of the significance of the results in Table 1. Since it is a synthetic experiment, I suggest derandomizing with 1000 simulations and reporting the (very small) standard deviation to make the results almost 100% conclusive. \n- What splits were used for the CIFAR post-hoc experiments? If splits were standard, refer to where these were obtained from. If splits were random, report standard deviations in the results. \n\n### Minor but strongly recommended\n\n- The fixed-width binning in 3-dimensions that you used was initially suggested in the paper by Vaicenavicius et al. (2019), so do cite this contribution. \n- The title is not very informative since \"nonparametric multiclass calibration\" is quite broad and the qualification \"simple\" is subjective. Please provide a more informative title without the subjective qualifier.\n- Page 5: the description of intra order-preserving functions can be improved.\n- The motivation/background for \"thresholding tiny probabilities\" could be made clearer. The description makes a number of statements without theoretical/empirical justification or referencing other work: \"these build-in errors become very large proportional to the probability\", \"LECE method produces output smaller than 0\". The method of correction is also not well-unmotivated; why retain the original probability and not just set c-hat(p-hat) = 0? (In contrast, the paragraph immediately after, \"Composition with parametric methods\" is very clear! Citations and independent justifications are provided, and an experiments section is also referenced.) \n\n### Minor and up to the authors\n\n- I believe when you say 'locally' in the paper, you mean with respect to the pre-hoc classifier. This may be useful to qualify explicitly.\n- If the authors can show on an illustrative synthetic example that LECE provably does better than LECD, that would be a very useful addition to the paper. ", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lo1QaY1HXp", "reviewer": "Reviewer_Fi18", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Pros**\n---------\n+ The paper is easy to read.\n\n+ The proposed method is relatively simple, technically sound, and has strong results.\n\n+ Relation to previous works and discussing the drawbacks and fair comparison to previous methods are valuable.\n\n**Cons**\n---------\n- The motivation for the proposed method needs to be improved in the abstract.\n\n- The proposed method has the main drawbacks of non-parametric: mainly sensitivity to noise and being computationally expensive. These may also need to be discussed in the main text.\n- The accuracies of the models after calibration are not present in the experiments.\n\n- Some drawbacks limit the applicability of the proposed method. As the number of classes increases, the method becomes computationally expensive and less reliable due to high dimensionality. Similarly, the number of validation samples, whether small or large, affects the results. Although these issues are discussed to some extent in the paper, conducting experiments by varying the number of validation samples or using a greater number of classes (such as ImageNet) and reporting the computation times would further strengthen the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper uses the assumption that nearby points on the probability simplex have similar calibration mappings to propose a post-hoc calibration method based on the nearest neighbor algorithm. They present two assumptions on the local neighborhood of a point on a probability simplex: 1) LECE assumes nearby points have equal calibration errors, and 2)  LECD assumes nearby points have the same class distribution. The authors show that their LECE assumption leads to an unbiased estimation of calibration error. Then the authors discuss the Relation of their work to previous works and provide some practical considerations to enhance the results. The results show that the proposed method is comparable to other state-of-the-art methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the Strengths And Weaknesses section.", "broader_impact_concerns": "I see no concern about broader impact of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rdVUjEUVyx", "reviewer": "Reviewer_QVr6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* 1. The paper overall is easy to read. The connections between the paper and existing results are well illustrated.\n\n* 2. The \"formally\" summarized two assumptions are beneficial for the literature.\n\n* 3. The introduced non-parametric calibration works well in synthetic data. When the number of classes is relatively large, combining with temperature scaling can generate promising results.\n\n**Weaknesses**\n\n* 1. **The formulated assumptions are kind of informal** \n\nThe two assumptions are not rigorously formulated. A formal illustration could be much better, i.e., instead of mentioning $\\hat{p}_1\\approx \\hat{p}_2\\$, a more rigorous saying could be better since these two assumptions are highlighted as contributions. For example, for some distance measure $D$, if $D(\\hat{p}_1, \\hat{p}_2)<\\delta$ for any $\\delta\\to 0$, ......\n\n* 2. **Experiment results are not fully convincing**\n\n* * 2.1 In the experiments of synthetic datasets, the improvements of LECE (Table 1) are marginal in many settings, i.e., under \"accuracy\", and \"Brier score\", the differences between LECE and DIR are negligible. In such cases, is it necessary to give them different ranks? Besides, can authors try 2 other true calibration functions to see if the performance of LECE is still consistently better than DIR? What is more, why do authors choose $k=500, t=0$ in this synthetic dataset, and what are the candidate values of $k, t$ in this synthetic experiment?\n\n* * 2.2 In the experiments of CIFAR datasets, LECE performs too badly without using TS. And it is hard to attribute the nice performance of TS+LECE to LECE. Since in certain cases, TS could achieve fairly well. Adding LECE has no further improvements. A couple of questions are listed in the section **Requested changes**. \n\n* * 2.3 More detailed explanations on why adding LECE requires TS might be needed, for the experiments on CIFAR datasets.\n\n* * 2.4 When looking into the ablation study (Table 7), please correct me if my understanding is incorrect: personally, it seems that the reason why the authors report the performance of TS+LECE rather than others, i.e., $LECE_{\\text{euc}}$ or $TS+LECE_{\\text{euc}}$ is because of the performance on the dataset for evaluation? For me, I feel like this is kind of cherry-picking. In practice, why do the authors decide on reporting $TS+LECE$ instead of $TS+LECE_{\\text{euc}}$ for comparing with other methods?\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work focuses on the **post-hoc calibration of the multi-class probabilistic classifier**. The contributions could be summarized below:\n\n* **1. Formulation of two assumptions** (Section 3.1)\n\nThe authors propose two assumptions about the true calibration map: \n\n  (a) Assumption of locally equal calibration errors (LECE)\n\n  (b) Assumption of locally equal class distributions (LECD)\n\nSimilar assumptions are implicitly made in existing literature [1, 2, 3, etc] but have never been explicitly stated. \n\n* **2. A detailed visualization comparison of different post-hoc calibration methods**\n\nThe authors adopt a well-designed synthetic dataset to compare the performance of a list of post-hoc calibration methods using the calibration map. (Not 100$\\%$ sure if this is a novel contribution or not.)\n\n* **3. A non-parametric post-hoc calibration method** (Section 3.2 and Section 4)\n\nThe authors proposed LECE calibration, which estimates the calibration error via the averaged difference between the prediction and label, w.r.t. its $k$ nearest neighbors. The synthetic (3-classes) dataset illustrates the effectiveness of the LECE in calibration. On real-world CIFAR datasets, LECE is able to achieve promising results when completed with the temperature scaling method.\n\n**References:**\n\n[1] Obtaining Well Calibrated Probabilities Using Bayesian Binning, AAAI'15.\n\n[2] Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration, NeurIPS'21.\n\n[3] Obtaining Calibrated Probability Estimates from Decision Trees and Naive Bayesian Classifiers, ICML'01.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I summarize my concerns, suggestions, and observed typos below, with the order of their appearances in the paper.\n\n* 1. **Suggestion 1:** \"Probabilistic classifiers take as input some data and produce as output probability distributions over classes.\" --> It might be better to say \"Probabilistic classifiers take some data as input and produce probability distributions over classes as output.\"\n\n* 2. **Suggestion 2:** \"It is possible that a probabilistic classifier is not well-calibrated and produces distorted probabilities. A classifier is considered to be calibrated if its predicted probabilities are in correspondence with the true class distribution.\" --> It might be better to switch the order of these two sentences.\n\n* 3. **Suggestion 3:** A toy example for the illustration of three definitions in Section 2.2 could be much better. \n\n* 4. **Suggestion 4:** In Section 2.4, more introduction about proper scoring rules might be better.\n\n* 5. **Notation 1 (Expectation):** on page 6, when talking about expectations, it could be better to what the expectation is with respect to, making the presentation more clear, i.e., $\\mathbb{E}_{?} \\[\\hat{CE}_\\{neigh} (\\hat{p}) ]$.\n\n* 6. **Suggestion 5:** a brief introduction of the synthetic dataset at the end of page 6 could be much better. Or put the visualization of the assumptions in the experiment section? \n\n* 7. **Question 1:** is the visualization (calibration map) a novel visualization tool for comparisons between post-hoc calibrations?\n\n* 8. **Question 2:** Figure 1 is kind of hard for me to follow. The differences among certain figures (except for (a)) are not quite straightforward to catch. Can authors adopt two sub-figures and explain their differences in more detail (i.e., (d), (e), (f))? Besides, more explanations on settings of the sub-figure are appreciated, i.e., what information is the color conveying. As for the differences between calibration maps, can they be quantified in numeric values?\n\n* 9. **Typo 1:** on page 8, \"The LECE assumption outperformed the LECD assumption on the real experiments also\". \"Also\" --> as well.\n\n* 10. **Suggestion 6:** the first sentence of section 3.2 reads weird.\n\n* 11. **Notation 2 ($\\hat{p}_{1i}$):** some notations are not well defined/introduced, i.e., in the introduction of KL-divergence on page 9, $\\hat{p}_{1i}$ is not well-defined.\n\n* 12. **Notation 3 ($\\hat{c}(\\hat{p})$):** at the end of paragraph \"Thresholding tiny probabilities\", the notation is not consistent, i.e., $\\hat{\\mathbf{c}}(\\hat{\\mathbf{p}})$ and $\\hat{c}(\\hat{\\mathbf{p}})$.\n\n* 13. **Typo 2:** in the last sentence of the paragraph \"Composition with parametric methods\", white space is needed in the front.\n\n* 14. **Exp 1:**  can authors try 2 other true calibration functions to see if the performance of LECE is still consistently better than DIR, in the synthetic experiments?\n\n* 15. **Exp 2:** why do authors choose $k=500, t=0$ in the synthetic dataset, and what are the candidate values of $k, t$ in this synthetic experiment?\n\n* 16. **Exp 3:** at the end of section 4.1.3, can the authors explain how the conclusion \"the proposed LECE calibration method depicted in Figure 1e learns the most similar transformation to the true calibration map\" is made? Is it numerically tested? \n\n* 17. **Exp 4:** in experiments of CIFAR datasets, for TS+LECE, what temperature scaling parameter is adopted? And how is it selected?\n\n* 18. **Exp 5:** for the comparison between TS, and TS+LECE, is TS+LECE always better than TS?\n\n* 19. **Exp 6:** in experiments of CIFAR datasets, while searching for optimal parameters, do the authors have any observations on the pattern of good parameters?\n\n* 20. **Exp 7:** More detailed explanations on why adding LECE requires TS might be needed, for the experiments on CIFAR datasets.\n\n* 21. **Exp 8:** experiment details on how the statistics are calculated (i.e., the evaluation dataset, etc), are needed, for CIFAR experiments.\n\n* 22. **Exp 9:** When looking into the ablation study (Table 7), please correct me if my understanding is incorrect: personally, it seems that the reason why the authors report the performance of TS+LECE rather than others, i.e., $LECE_{\\text{euc}}$ or $TS+LECE_{\\text{euc}}$ is because of the performance on the dataset for evaluation? For me, I feel like this is kind of cherry-picking. In practice, why do the authors decide on reporting $TS+LECE$ instead of $TS+LECE_{\\text{euc}}$ for comparing with other methods?\n\n\n\n\n", "broader_impact_concerns": "There seem to be no ethical concerns about the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "q8HDZc4Cw2", "reviewer": "Reviewer_eGb8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- **[C1]**:\n> *A probabilistic classifier is considered calibrated if it outputs probabilities that are in correspondence\nwith empirical class proportions.*\n\nBeing pedantic, this sentence in the abstract is at odds with the definition of calibration given in Section 2.2, where the calibration is defined as an expectation over the population. I agree that in practice this is approximated by an empirical average over the validation set, but technically these two are different.\n\n- **[C2]**:\n> *The problem of over-confident predictions is especially common for modern deep neural networks (Guo et al., 2017; Lakshminarayanan et al., 2017). Distorted output probabilities are also characteristic of many classical machine learning methods such as naive Bayes or decision trees (Niculescu-Mizil & Caruana, 2005; Domingos & Pazzani, 1996).*\n\nRecent theoretical progress (Bai et al. 2021; Clarté et al. 2022a,b) have shown that over-confidence is widespread in models as simple as high-dimensional logistic regression. I think it is important to mention this since there is a widespread belief in the literature that overconfidence is a specific problem to deep neural networks.\n\n- **[C3]**: Assumptions LECD and LECE in Page 6 translate to assumptions on the underlying data distribution / target classifier. More precisely, if data is generated from a target classifier $f_{\\star}(x) = \\mathbb{P}(Y=1|X=x)$ what do these assumptions intuitively imply on the functional form of $f_{\\star}$? For instance, would they be satisfied by a logit or probit model?\n\n- **[C4]**: Why don't the authors report the standard deviation over the independent runs in Table 1-4? This is not a good practice, specially when the difference between the comparison is (for certain methods) on the third digit.\n\n- **[C5]**: Since this is a numerical paper based on comparing very different algorithms, I miss a discussion on running times and sample complexity. Are (at least the order of) the running times similar? Both the proposed method and TS require cross-validation. Does this requires two validation sets (one for TS, one for the hyperparameter) or both are done together? More generally, does all methods use the same quantity of validation data?   \n\n- **[C6]**: It would be nice to have a pseudo-code for LECE and LECE+TS. This is sort of done in the list in Page 9, but a pseudo-code with input, steps and output clearly stated could help better the implementation and understanding the points above. \n\n- **[C7]**: I find curious that comparing LECE to TS and to TS+LECE, in most cases the highest decrease in the overconfidence often comes from TS itself, which remains a simple and easy to implement metho. What are your thoughts on that?\n\n**References**\n\n[[Bai et al. 2021]](https://proceedings.mlr.press/v139/bai21c.html) Yu Bai, Song Mei, Huan Wang, Caiming Xiong. *Don’t Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification*. Proceedings of the 38th International Conference on Machine Learning, PMLR 139:566-576, 2021.\n\n[[Clarte 2022a]](https://arxiv.org/abs/2202.03295) Lucas Clarté, Bruno Loureiro, Florent Krzakala, Lenka Zdeborová. *Theoretical characterization of uncertainty in high-dimensional linear classification*. arXiv: 2202.03295\n\n[[Clarte 2022b]](https://arxiv.org/abs/2210.12760) Lucas Clarté, Bruno Loureiro, Florent Krzakala, Lenka Zdeborová. *A study of uncertainty quantification in overparametrized high-dimensional models*. arXiv: 2210.12760", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new multi-class post-hoc non-parametric calibration method. The method is based on the idea that the calibration error is approximately equal in a small neighbourhood of the simplex (\"LECE assumption\"), and consists of subtracting the uncalibrated classifier by the averaged calibration error in a neighbourhood on the classifier. The algorithm therefore depends on a choice of distance on the simplex, and has one hyperparameter that is chosen by cross-validation: the size of the neighbourhood.\n\nMost of the results consist of benchmarking the algorithm against popular calibration methods (TS, MS, IOP, etc.) and across different architectures (DenseNet-40, ResNet-110, etc.) and datasets, both synthetic and real (CIFAR10, CIFAR100). By itself, the proposed method is outperformed in most of the experiments. However, when combined with temperature scaling, it consistently outperforms all the other benchmarks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Major**:\n- Include error bars / standard deviation in every experiment.\n- Add a discussion on running time and how much validation data is used for cross-validation / TS.\n\n**Minor**:\n- Add a pseudo-code for the proposed algorithm and the coupled TS version.", "broader_impact_concerns": "In my reading there are no broader impact concerns for this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of calibrating multi-class classifiers, a fundamental problem of broad interest to the community. It explicates conditions underpinning the success of calibration that have hitherto not been discussed directly. These are used to devise a new calibration scheme with strong empirical performance. Reviewers unanimously agreed that the paper makes an interesting contribution that would be valuable for the TMLR audience. From our reading, we concur with this view. We are thus pleased to recommend the paper for acceptance.

For the final version, we do agree with one reviewer's suggestion that the authors consider reducing the length of the the main body.
Decision: Accept (poster)