Improving Multi-Class Calibration through Normalization-Aware Isotonic Techniques
Authors: Alon Arad
Saharon Rosset
Venue: ICML 2025 poster (2025)
Keywords: Machine Learning
Calibration
Multi-class
Isotonic Regression
Uncertainty Estimation
Primary area: general_machine_learning->supervised_learning
TL;DR: We propose novel isotonic normalization-aware post-hoc calibration techniques that inherently account for probability normalization, addressing a key limitation of prior approaches.

Abstract: Accurate and reliable probability predictions are essential for multi-class supervised learning tasks, where well-calibrated models enable rational decision-making. While isotonic regression has proven effective for binary calibration, its extension to multi-class problems via one-vs-rest calibration often produces suboptimal results, limiting its practical adoption. In this work, we propose novel isotonic normalization-aware techniques for multi-class calibration, grounded in natural and intuitive assumptions expected by practitioners. Unlike prior approaches, our methods inherently account for probability normalization by either incorporating normalization directly into the optimization process (**NA-FIR**) or modeling the problem as a cumulative bivariate isotonic regression (**SCIR**). Empirical evaluations on a variety of text and image classification datasets across different model architectures reveal that our approach consistently improves log loss and expected calibration error (ECE) metrics. These findings underscore the potential of our approach to enhance a-parametric multi-class calibration practices, offering an adaptable solution for real-world applications.

Improving Multi-Class Calibration through Normalization-Awar Isotonic Techniques
Alon Arad
Saharon Rosset
Abstract
their reliability and implications within the broader decision- making framework. For instance, in healthcare, overesti- mating the likelihood of disease may lead to unnecessary interventions, while underestimation risks delaying vital treatments.
Accurate and reliable probability predictions are essential for multi-clase supervised learning tasks, where well-calibrated models enable rational decision-making. While isotonic regression has proven effective for binary calibration, its exten- sion to multi-class problems via one-vs-rest cal- ibration produced suboptimal results when com- pared to parametric methods, limiting its practical adoption. In this work, we propose novel iso- tonic normalization-awar techniques for multi- class calibration, grounded in natural and intuitive assumptions expected by practitioners. Unlike prior approaches, our methods inherently account for probability normalization by either incorporat- ing normalization directly into the optimization process (NA-FIR) or modeling the problem as a cumulative bivariate isotonic regression (SCIR). Empirical evaluation variety of text and im- age classification datasets across different model architectures reveals that our approach consis- tently improves negative log-likelihood (NLL) and expected calibration error (ECE) metrics.
Calibration a term frequently used to describe this con- cept and serves a dual purpose in addressing these chal- lenges. It is both measure of the "reliability" of model outputs-evalluting the alignment between predicted prob- abilities and observed outcomes and method for re- fining these outputs to enhance their practical utility. The concept of calibration has long history, with foundational works (Murphy, 1973; Murphy & Winkler, 1977; DeG- root & Fienberg, 1981) emphasizing the relationship be- tween loss scores and calibration. Subsequent research (Platt, 1999; Zadrozny & Elkan, 2001; Niculescu-Mizil & Caruana, 2005) has examined the reliability of outputs from various machine learning algorithms and the application of post-hoc calibration methods, particularly focusing on methods designed for binary classification tasks. To address the challenges of multi-class calibration, it was suggested (Zadrozny & Elkan, 2002) to decompose the problem into multiple binary classification tasks learnt only with class respective model output and binary label. To ensure that the predictions sum to and form valid probability vector, the post-calibration predicted class values are normalized by dividing each by their sum.
1. Introduction
The rapid progress of artificial intelligence (AT) has greatly expanded both the trust in and the range of applications for Al models in real-world settings. These advancements have fundamentally reshaped fields requiring accurate predictions and informed decision-mann makiing,, including healthcare, agri- culture, finance, and retail. However, decisionnmaking in these contexts often transcends simple notions of correct- ness, requiring a nuanced understanding of the underlying probabilities generated by the models. For practitioners, this means engaging critically with model outputs, assessing
Recent advancements computational power and neu- network architectures have introduced new challenges around over-confident models (Guo al., 2017: Kull et al., 2019), particularly in quantifying and defining calibration in multi-class settings (Vaicenavicius et al., 2019). These works have highlighted the effectiveness of "simple" para- metric approaches, such as Temperature Scaling, which naturally extend to multi-class scenarios without requiring decomposition binary sub-problems or additional normal- ization considerations, leaving traditional non-parametric methods somewhat sidelined.
Equual contribution 'Department of Statistics, Tel Aviv Univer- sity. Correspondence to: Alon Arad <alonarad tau..tau. Saharon Rosset <saharon tlu...tuu.cc.l>..
However, later studies (Gupta & Ramdas, 2022; Patel et al., 2020) have underscored the untapped potential of traditional techniques when applied with well suited assumptions that have proven useful on empirical datasets evaluation. No-
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Isotonic Normalization-Aware Multi-Class Calibration 2025
tably, these works focus on histogram binning (HB), despite the historical prominence of isotonic regression (IR) in bi- nary classification tasks. Interestingly, both report state-of- the-art (SOTA) results for unnormalized predictions, mean- ing the predictions don't necessarily form a valid probability vector. This appears to paradoxically conflict with the fun- damental goal of calibration: fostering trust the reported probabilities.
Definition 2.2. A classifier p is class-wise calibrated if
E| DX, [[X);] - x());,
Vj E (l....,k}.
As demonstrated by Vaicenavicius et al. (2019) being class- wise calibrated does not necessarily imply that the classifier is indeed calibrated, making a weaker concept of cali- bration. Additionally, another weaker notion of calibration proposed by Guo et al. (2017) has gained attention and popularity due to its strong practical motivation for address- ing the question: "Can we trust the top predicted category score?" " It is defined as follows:
In this work, we emphasize the importance of being Normulization-Awarr in non-parametric multi-class settings. Sections 2 and 3 provide a concise overview of the subject and prior literature. In Section 4 we introduce two IR based approaches that incorporate normalization directly into the problem formulation and are motivated by simply stated assumptions. The first approach modifies the optimization function explicitly (hence the term Normalization-Awarr while the second redefines the problem by addressing cu- mulative sub-problems instead of treating each class as an independent binary task. As demonstrated in Section 5, our proposed methods consistently improve both negative log- nngllikeiihod (NLL.) and calibration error across diverse datasets, achieving SOTA results and reaffirming the ef- fectiveness of IR for calibration. We believe this provides practitioners with powerful non-parametric alternative in scenarios where parametric assumptions may be limiting.
Definition 2.3. a classifier f is confidence calibrated if
E Yrg max ((X) mmx p(X) = max ((X)
Offering a practical and interpretable metric for trust in classification outputs.
2.2. Error Measurement
A commonly used method for assessing the alignment of probabilistic binary forecasts with actual outcome probabili- ties is using a Reliability plot (see Murphy & Winkler 1977; DeGroot & Fienberg 1983; Niculescu-Mizil & Caruana 2005) This approach involves dividing predictions within [0, 1] range into equal-width bins and comparing the model's predicted probabilities against the actual outcome statisties within each bin. While Reliability plot offers valuable vi- sualization, single summary statistic is often preferred. In the binary case Nacini et al. (2015) define estimated cali- bration error (ECE) as the weighted sum of absolute differ- ences in these bins. However, generalizing this measure not straightforward, thus several definitions were offered. Nixon et al. (2019) suggested cw-ECE corresponding to the class-wise calibrated notion in Definition 2.2 and is esti- mated by averaging ECE computed independently for each class binary subproblem. Since this approach can overem- phasize observations in small bins, they also propose TECE, which applics thresholded equal-mass binning to each class before averaging the resulting estimates. For the confidence calibrated notion in Definition 2.3, the conf-ECE estimator (Guo et al., 2017: Kull et al., 2019) is computed by applying binning and binary labeling based on the maximum pre- dicted probability. The corresponding Reliability plot is known as Confidence Reliability plot. Alternative methods based on kernel density estimation (KDE) have been pro- posed (Zhang et al., 2020; Widmann et al., 2019; Marx et al., 2024) but are less frequently used in practice.
2. Problem Definition
2.1. Introduction to the Calibration Challenge
We address supervised multi-class classification where a classifier á learns to map inputs X E Rd finite of classes {1...., k} using training set T = {(I; } where each pair (I;, v1) represents realization of i.dd random variables YX, with Y one-hot encoded vec- tor. The classifier outputs predictions p(X) that lie within the probability simplex A A defined as R-1 {pe R 2 Vi, Ei =1). In essence, calibra- tion implies that if a set of samples is classified with an 80% probability of belonging to a certain class, we would expect that, indeed, 80% of those samples accurately fall into that class. This requirement formalized as follows:
Definition 2.1. A classifier P is called calibrated if for any E A k-1 it holds that
B(Y ((X) =) =q
While this definition effectively captures the theoretical essence of calibration, its measurement is often imprac- tical in multi-class scenarios (A: > 4) due to the extensive number of test points required for estimating it effectively. To address this complexity, a more attainable standard was proposed:
Proper Scoring Rules. Evaluation measures for proba- bilistic forecasts can be attributed back to Brier (1950) and Good (1952) where the main concern was creating a scoring rule to encourage the forecaster to be honest (see Gneiting & Raftery 2007 for full characterization of proper scoring rules).
2

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
Definition 2.4. A scoring rule S: A+-1x x {1, ,I, RU (+:00) is called proper if
3.2. Jon-Paramctric Methods
The two prevalent non-parametrie methods are HB and IR. HB introduced by Zadrozny (2001) for binary classification. It divides V2 into B pre-determined quantiles based on p(x;) values, the estimate for each bin is computed as the observed proportion in the calibration set. The method is considered non parameettii since it makes no distributional assumptions. Nacini et al. (2015) suggested a further improvement to HB by employing a Bayesian approach to aggregate multi- ple binning choices. IR, proposed by (Zadrozny & Elkan, 2002) fits calibration map 9 under the sole assumption of monotonicity. Formally, IR is characterized as
arg arg By (pp. Y)] q
P It is easy to verify that both NLL and Brier score are proper scoring rules. Interestingly, as shown by Bröcker (2009) any proper scoring rule can be decomposed into two compo- nents: The first, refinement, quantifies the variance within Y given a model's prediction, essentially capturing the model's precision. The second, calibration/reliabiiity, assesses how well the model's predictions align with the actual outcomes.
3. Post-Hoe Calibration Methods
g = arg min
Σ (olf(z;)) - wx) 1=1
Post-hoc calibration is typically performed using either a hold-out calibration set or the validation set. Let V = {(r,, yt) y:)] represent an independent calibration set (i.i.d) separate from the training set T. For clarity, let Ò de- note the fitted post-hoe model, trained calibration set
t t((((x)) S (((aa)) when 2, I 23
In the binary I-D case, the problem is solved by first or- dering the data and then applying PAVA (Pool Adjacentt Violators Algorithm Ayer et al. 1955) fitting a piecewise constant function to the calibration map with no further as- sumptions or parameters to specify. Moreover, it can be shown that the fitted 9 is the solution for any proper scoring rule, proof and further details supplied in Appendix D.
VB= ((((x)))))) M1) (44,M)) E V We will refer to ý as the calibration map.
3.1. Parametric Methods
Platt (1999) introduced a logistic-regression-bane calibra- tion for binary predictions, motivated by the empirical fit of a sigmoid to SVM outputs. Later, Kull et al. (2017) demonstrated that the logistic relation assumption holds in the binary case when the distributions of model outputs conditioned on the outcome are Gaussian. This insight led to their suggested binary calibrator extension named Beta calibration modeling conditional distribution using Beta dis- tribution. For multi-class neural network settings, Guo et al. (2017) proposed three natural extensions: Matrix Scaling (MS). Vector Scaling (VS) and Temperature Scaling (TS). MS essentially applies multinomial logistic regression to the logits 2x;;) input prior to the final softamx layer SsM while VS is the specific case where the transformation matrix is constrained to be diagonal. TS simplifies the calibration approach further by enforcing a uniform scaling factor T across all logits and is fitted by solving the following NLL minimization optimization problem:
3.3. Nar-Perae Multi-Class Extensions and Assumptions
OvR. Both HB and IR can be extended to multi-class set- tings by decomposing the problem into k one-vs-rest binary subproblems and normalizing the prediction scores by divid- ing them by their sum, we refer to these methods as IR-OvR and HB-OvR respectively. This induction is justified when one assumes Category Independence, formally expressed as P(Y| p(X)) = P(Y. p(X))).
sCW. To address inefficiencies arising from small class priors datasets, Patel et al. (2020) introduce Shared Class- Wise (sCW) training, which merges binary sub-problems for classes with similar priors. When all sub-problems are trained jointly we name the underlying assumption Per- mutation Invariance formally assuming P(Y; ((X)) = P(Yo()) (o(X)) where a is permutation defined such that that ((X))- Applying Permutation Invari- ance to calibration set in our settings involves flattening all the predictions, thus, we term Flattened Isotonic Regression (FIR) to be the result of applying sCW training to all classes together:
(1i) log(asM( 2(1z)) (1)
f arg min T
)
T
1=1
The corresponding calibration map is then given by ((=(x;)) aSM{ (لzz)). Despite its simplicity, TS has consistently demonstrated strong performance on conf-ECE and remains preferred method for post-hoc calibration. It has further inspired several variations, including Mozafari et al. 2018;J0 Ji et al. 2019; Ding et al. 2021. Kull et al. (2019) proposed Dirichlet calibration as a natural extension to Beta calibration, noting slight differences from MS.
ĪFIR arg min
Σ
(v:) log(9(((x:)))
(3)
+(1 (v.) log(1 - g((((:))))))
for monotonic function g. Patel et al. (2020) previously
3

---

Isotonic Normalization-Awer Multi-Class Calibration 2025
Unoal ConfECE 13.90% prolue 0.0
NA-FIR, Conf-EE 1.91% poalu
SCR, Conk-ECE 1.87% prialue 0.04
Joins sahring
Juaagee socn 30 sirving
soln Clink siheing
T8, Conf-ECE 5 2.20% p-value +.0
FIR, Conf-EEE 3.47% p-value # 0.0
IR. Conf-EE 2.2% p-valuo = 0.0
Figure 1. Confidence Reliability plots for NG20 BERT-Large-Uneased classifier, p-value calcluated as suggested by Vaicenavicius al. (2019) under the null of perfectly calibrated procedure. As can be seen the uncalibrated model is highly over-confident and both our suggested methods are the only ones where we get positive p-value.
reported FIR without normalization, whereas Zhang et al. (2020) has applied the straightforward correction for Cate- gory Independence assumption:
Table 1. Multi-Class extensions and their underlying assumptions
COMPARED METHODS
OuR METHODS
CALIBRATION METHOD
MS
OvR FIR
SCIR
NA-FIR
GFIN(D) ( 9FIR(PI)
(FIR(PK)
ORDER PRESERVING
X
v x
v
x
V
Ei= Et OFIR(P))
12-19FI(()))
PERMUTATION INVARIANT
X v
x
v
v
V
RELAXING CATEGORY INDE- PENDENCE
V
v
V
Notably, FIR is Order Preserving, meaning p; 2 Pj + ((p), 2 0(), for all p E A These types of structural assumptions have also been outlined in the context of para- metric models (Rahimi et al., 2020).
sumptions reveals the key weakness we want to address they all are trained without taking into consideration their actual normalized outcomes.
Alternatively Gupta & Ramdas (2022) proposed M2B framework, essentially suggesting to align calibration method with calibration error objection. For example, when confidence calibrated (Definition 2.3) is of interest, HB should be trained using a calibration set containing only the top predicted probability and {0, 1} encoding to indicate whether the top predicted class matches the actual class. No- tably, they report SOTA performance without normalizing the output predictions.
We believe that providing valid probability predictions is essential for building trust among practitioners, especially in decision-making frameworks. However, most existing non- parametric calibration methods for multi-class settings operate under the assumption of category independence, where each class is calibrated separately and if predictions are normalized it only done post calibration.
This modeling choice introduces key limitation as it is known that such marginal (classwise) calibration is strictly weaker than full (canonical) calibration (Vaicenavicius et al., 2019). For example both prediction vectors [0.8, 0.2,0] and [0.8, 0.1, 0.1] share the same top-1 prediction but their underlying uncertainty profiles can differ substantially.
3.4. Other Related Work
It is worth noting that various calibration approaches have been proposed, including post hoc methods (see Silva Filho et al. 2023 for a more comprehensive discussion), regu- larization techniques, implicit calibration strategies, and uncertainty estimation methods. For a comprehensive re- view of these methods in the context of deep learning, see Abdar al. (2021); Gawlikowski al. (2023).
While we aim to relax the Category Independence assump- tion, we justify Order Preserving assumption desirable property. As underlying models improve, it becomes in- creasingly reasonable for calibration method to preserve the ranking of predicted probabilities from the original model.
4. Normalization Aware IR Methods
Motivation. Examining the previously proposed non- parametric multi-class extensions and their respective as-
Furthermore, the traditional OvR approach suffers from high

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
Table Average ranking comparison between different calibration methods across different datasets and various metrics. Percentages indicating how often a method achieved the lowest score for a given metric across the tested models. The best- pest-performing calibrator is highlighted bold.
AVERAGE RANKING
METRIC
DATASET
NA-FIR
SCIR
FIR
IR OvR
TS
VS
MS
UNCALIBRATED
20NG
1.4 (70%)
6.0 (0%)
2.8 (10%)
7.3 (0%)
(10%)
(10%)
5.3 (0%)
6.7 (D%)
CIFARIO
1.2 (75%)
1.8 (25%)
4.0(0%)
7.0 (0%)
5.8 (0%)
4.8
3.5
8.0(0%)
CIFAR100
(62%)
4.4 (15%)
3.3 (.%)
7.6 (0%)
2.8 (88)
3.8 (8%)
6.7 (8%)
5.9 (0%)
NLL
FOOD101
2.5 (0%)
5.8 (0%)
(0%)
7.9 (0%)
1.6 (62%)
2.9 (38%)
7.0 (0%)
(0%)
IMAGENET
1.0 (100%)
4.9 (0%)
2.0 (0%)
8.0 (0%)
3.4 (0%)
5.1 (0%)
5.9 (0%)
5.8 (0%)
R52
1.7 (50%)
5.1 (0%)
3.2 (10%)
8.0 (0%)
2.1 (30%)
5.1 (10%)
6.7 (0%)
4.1 (0%)
YR
3.2 (14%)
5.3 (5%)
5.2 (0%)
5.2 (0%)
4.9 (0%)
3.2 (5%)
1.5 (77%)
7.6 (0%)
20NG
2.4
2.6 (60%)
3.1 (30%)
3.9 (0%
6.9 (0%)
4.4 (0%)
4.9 (0%)
7.8 (D%)
CIFARIO
4.8 (0%)
1.0 (100%)
5.8 (0%)
5.8 (0%)
2.8 (0%)
4.0 (0%)
4.0 (0%)
(.0
CIFAR100
2.5 (8%)
1.2 (85%)
4.7 (0%%
(0%)
3.1 (0%)
(8%)
7.4 (0%)
7.3 (0%)
CONF-ECE
FOOD101
2.5%
3.2 (25%)
(0%)
4.9 (12%)
2.8 (38%)
(0%)
7.6
(0%)
IMAGENET
1.4 (75%)
2.0 (25%)
(.0(0))
5.5 (0%)
4.0 (0%)
6.1 (0%)
7.4 (0%)
6.6 (0%)
R52
2.6 (20%)
2.9 (50%)
3.6 (10%)
6.3 (0%)
4.8 (0%)
3.8 (10%)
5.1 (10%)
6.9 (0%)
YR
3.0 (18%)
3.2 (41%)
4.1 (9%)
3.4 (14%)
6.0 (0%)
4.8 (5%)
3.7 (14%)
7.9 (0%)
20NG
2.1 (40%)
4.3 (0%)
2.8 (20%)
2.7 (30%)
4.9 (0%)
4.9 (10%)
7.0 (0%)
7.3 (0%)
CIFARI0
2.2 (0%)
1.0 (100%)
(0%)
3.5 (0%)
6.2 (0%)
5.5 (0%)
6.2
(.0%
CIFAR100
(31%)
2.5 (46%)
(0%)
(0%)
3.8 (8%)
(8%)
7.4
6.7 (0%)
BS
10OD101
(125)
(0%)
(.0)
5.6 (12%)
2.4 (38%)
3.6 (38%)
7.8 (0%)
(09)
IMAGENET
1.2 (75%)
3.4 (0%)
(0%)
6.5 (0%)
4.1 (12%)
5.8 (12%)
6.6 (0%)
(0%)
R52
(50%)
4.9 (10%)
(.9)
5.7 (0%)
3.9 (20%)
3.9 (20%)
6.8 (0%)
(0%)
YR
3.8 (9%)
6.0 (5%)
4.8 (0%)
3.0 (5%)
5.7 (0%)
(5%%
1.8 (77%)
7.8 (0%)
20NG
(0%)
3.8 (10%)
3.7 (10%)
1.6 (60%)
7.0 (0%)
(0%)
3.1 (20%)
7.8 (0%)
CIFAR10
4.2 (0%)
2.0 (50%)
5.5 (0%)
2.5 (25%)
7.0 (0%)
4.2 (0%)
2.5 (25%)
8.0 (0%)
CIFARI00
2.6 (23%)
2.4 (46%)
(80%
4.2 (8%)
3.7 (0%)
4.7 (15%)
7.3 (0%)
7.1 (0%)
CW-ECE
F0OD101
(0%)
3.2 (38%)
3.9 (0%)
(0%)
2.5 (25%)
3.8 (38%)
7.4 (0%)
(0%)
IMAGENET
(0%)
6.1 (0%)
3.1 (12%)
4.4 (0%)
2.0 (50%)
4.1 (25%)
5.4 (12%)
(0%) (0%)
R52
3.8 (0%)
(0%)
2.7 (40%)
4.5 (10%)
4.7 (10%)
2.8 (40%)
7.2 (0%)
YR
4.0 (18%)
4.7 (0%)
4.7 (0%)
2.3 (14%)
6.4 (0%)
4.1 (0%)
2.1 (68%)
70%)
20NG
3.4 (20%)
3.1 (10%)
4.5 (10%)
2.9 (30%) %))
5.6 (0%)
5.0 (20%)
3.7 (10%)
7.8 (0%)
CIFARIO
2.8 (25%%
1.8 (50%)
4.5 (0%)
2.5 (25%)
6.8 (0%
4.8 (0%)
(0%)
8.0 (0%)
CIFARIO0
2.2 (23%)
1.7 (62%)
(0%)
4.5 (0%)
4.5 (0%)
4.6 (8%)
7.6 (0%)
(8%)
TECE
F0OD101
(12%)
2.6 (25%)
3.0 (25%)
5.8 (12%)
4.0 (12%)
4.8 (12%)
7.6 (0%)
(0%)
IMAGENET
2.9 (12%))
2.1 (50%)
(0%)
8.0 (0%)
5.1 (0%)
6.4 (0%)
6.1 (0%)
2.9 (38%)
R52
6.1 (0%)
2.7 (30%)
5.3 (10%)
3.6 (10%)
5.1 (0%)
(10%)
3.2 (40%)
(0%)
YR
3.9 (18%)
(0%)
4.7 (5%%
2.7 (14%)
6.0 (0%)
(9%)
2.0 (55%)
7.7 (0%)
variance as data sparse in critical areas, particularly for overconfident models in scenarios with limited calibration data and many classes. We find it reasonable to assume that model's overconfidence or under under--onfidence exhibits similar characteristics across different classes effectively assuming Permutation Invariance.
the problem in a straightforward manner:
Denote the isotonic function class as g = (g : [0, 1] + R+ g(u) S g(v) if u S t} we define NA-FIR NLL minimization problem as follows:
Formulation.
4 Σ 1=1
m
g(((z,)1)
Thus, we suggest two alternatives that aim to leverage the empirical observations from sCW and M2B frameworks, yet are designed to incorporate normalization within the problem formulation.
IN arg min gEg
(vi) log
(4)
Σ ))11)((()3,))
and, accordingly:
4.1. Normalized Aware Flattened Isotonic Regression
INA.FIR (p1) 9NA.FIR(P) E (NN.)
FNA. > (IX))
(5)
NA-FIR is what we believe to be the most appropriate non- parametric analogue to TS. Since NLL is proper scoring rule, minimization incentivize calibration improvement (see stated decomposition in Section 2.2). Thus we formulate
Note that while TS is applied to the softmax function (Equa- tion (I)), the only difference in our normalized aware iso- tonic formulation lies in the use of derived probabilities
5

---

Isotonic Normalization-Awaal Multi-Class Calibration 2025
instead of direct logits, which is not fundamental change as the exponent is a monotonic function.
4.2. Sorted Cumulative Isotonic Regression
Motivated to develop a calibration method that aligns with the practitioner's 's decision decision-making -mkinng process, particularly mod- cling binary problems that correspond directly to the ECE evaluated metric (e.g conf-ECE)) we propose SCIR, which integrates ranking into the problem formulation.
Both FIR and NA-FIR assume Permutation Invariance and ensure Order Preservation for every prediction point. But while FIR optimization (Equation (3)) doesn't t account for the collateral effects of the fitted isotonic values, NA-FIR optimization (Equation (4)) incorporates the normalization term, thereby relaxing the limitations of the Category Inde- pendence assumption.
Formulation. Let (p, y) E Vp be a calibration point, and let a be the order permutation such that Po-1(1) 2 ... 2 P we define the sorted cumulative corresponding set for each prediction point
Fitting Process. It is important to highlight that this prob- lem is no longer convex, which means that PAVA cannot be directly applied as a solution. Consequently, we explored alternative methods for searching constrained local minima. Given that PAVA when applied to the non-nommn non-maaall iso- tonic problem, identifies the optimal bin boundaries for min- imizing the NLL in the flattened binary case, provides both reasonable initialization point and an opportunity to reduce the effective search space. Leveraging the isotonic block structure identified by PAVA allowed us to include more thorough search techniques, as outlined in our proposed algorithm Algorithm The algorithm employs Markov Chain Monte Carlo (MCMC) optimization, also known as simulated annealing, achieving stable convergence while still allowing the practitioner to specify both the minimal number of bins and the granularity of fitted values. Further details can be found in Appendix A.2.
{
)
Cloored y)
Pg.T),
E Vs ofiSSr
and for set of points we define the aggregated set Cld = Unnyjev, Clssoned y). This set contains tuples of cu- mulative top-r scores and their associated cumulative la- bel counts such that each ((g,r). CM belongs to [0, 1| x f1....,A} }} x 1).
Finally ŌSCIR defined as the solution to the following minimization problem:
arg min 9
Σ ÿ log (g(g,r))
Cldsss
(6)
+(1 1) log (1 g(g,r)
s. g r) S g(s if S
Algorithm 1 MCMC Blockwise Normalized Aware Flat- tened Isotonic Optimization
Thus imposing monotonicity both in prediction sum and ranking index. To make predictions for new input point the probabilities are first sorted, ĐCSIR is applied, difference is taken and then the results are transformed back into the original order. Formally the prediction is calculated as:
1: Input: Data Y,Y,
hyperparameters Cataage: 3, num iterations,
min_blocks, split.size thrresold
2: Flatten X and y: Ziaten X. flatten(), Vflatenn Y. flatten()
3: Initialize block structure and fits:
blocks. block_fits] + PAVA (Tameen: Vitane))
OSCIR (f(x:)) C
Σ
4: Refine block structure: [blocks, block fits] +
split blocks(blocks, min blocks, split size threshold)
a()So(()
5: for to num_iterations do
-ÿcsin(
Σ
p(z:), o(() -1)
Select a random block: block ~ (11, (enblocks))
7: Perturb block fit: ~ (d((111 1),, change + 6chunge
o())a(1)-1
8: Update suggested fit:
suggested miggested_block_fft block_fit fit + block_fits block] + change
where ÚCSIR( (- = 0
( k)) 0.
1 by definition.
9:
Validate isotonicity of btrggested_bbock....
10:
likelihood > current_likelihong then Update: hest likelihond 4- likelihood, best fit + suggested block fits end if
Illustrative Example. Let h: 4 and consider pair (p. v) = (0.2, 0.4, 0.3, 0.1], 00, 1]) The corresponding sorted cumulative set is:
11:
12:
13:
likelihood > current Likelihod or
rand() < exp(8- (likelihooooo current line___iikehhhod)) then Accept: block_fits + current likelihood likelihood
Cllsorted (p. v) ((0.4, 11,0), (10.7, 21. 1). (10.9,3) 3),
14:
To compute the calibrated probability for the first class (which appears at the third rank in the sorted order), we apply: ŌSCIR (p) = ISCIR (0.9,3) JJSCI (0.8, 2)
15: end if
16: end for
17: Return: best. block.
We note that this formulation assumes Permutation Invari- ance and encodes mutual learning effectively allowing to
6

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
10
Cumulefive Class
Normalized Aware vs. Normalized Probebilties Difference
06
3 Cumulative Class
2 Cumulative Class
0.10
Predictes Output
4 Cumulafive Claes
Diffrrncee
5 Cumulafive Class
0.00
-0.0
8 8066
0.10
Dount
00
50
02
0,4
08 0.8 1.0
0.1
02
03
04
0.5
06
0.7
0.8
1.0
Curullative Probabil by
Uncodiratter Protosiiity
(a) BERT- larT-llage-uncaset SCIR fit
(b) HERT-lage--unasse NA-FIR fits v.s FIR fits on test data
Figure 2. Both plots are based on the NG20 dataset with trained HEET--aage-unncssed classifer. The left plot illustrates fitted calibration curves for the first 5 ranks cumulative trained models, where the final prediction for each rank (cumulative class) is calculated as the difference between its cumulative value and the previous one. The right plot provides insights into the effect on test predicted probabilities comparing NA-FIR to FIR predictions function of Uncalibrated predictions that were thresholded to lie within the [0.01, 1] range and subsequently binned into 30 equal-width intervals. The lower chart depicts the corresponding bin sizes.
break Category Independence assumption, but does not guar- antee Order Preservation. We justify the coordinate- wise induced order which can expand the natural isotonic induced order as we find it is reasonable to assume super-additivity of the flattened isotonic calibration map and it ensures non- negative predicted values for every cumulative class any prediction point. Finally, in practice, we add small to all output probabilities and divide by the sum in order to prevent zero probabilities.
Algorithm 2 2-D Grid Sorted Cumulative Isotonic Maximal Upper Set Algorithm
1: Input: X = [((k,,),, [I,..., 2, w E ER"
2: Initialize M(N411XA, RNXA as zero matrices, and Avg(X)
3: for N to do
4:
for f to
5:
if S / then
6:
M = Mli + 1, + w. - R[i =j
7:
else if 1 and (y: b) 0 then
8:
M [i.j]] = Mli + L, R[i.]] =j
Fitting Process. In general, solving a multi-dimennsonal
9:
else
10:
Mi..j] = Mi + 1, wilsn - b); R(i.5l =
isotonic regression is computationally demanding, with a worst-case complexity of (mm*k4) as demonstrated by
11: end if
12: end for
Spouge et al. (2003) for the least square loss (Equation (2)) and by Luss& & Rosset (2014) for the generalized convex
13: end for
14: Initialize S = 0:: =c
case. However, we show that by utilizing one of the algo-
15: for i = 1 to N do
16: Set (k:,
rithms specified in Spouge et al. (2003) to suit this problem, the following result holds:
17:
if R(i,)) j) / then
18: Add i to
Proposition 4.1. The cumulative sorted problem defined
19: end if
in Equation (6) can be solved in Omm²kA) worst case time
20: Update j R(i,j)
21:
end for
using Algorithm 2.
22: Return: S
This solution is obtained by recursively splitting Clane using the surprisingly simple dynamic programming algorithm outlined in Algorithm 2. When the returned partition equals the input assigned value is the input corresponding mean. proof for Proposition 4.1 and further details are provided in Appendix A.
CI CIFAR-100 (Krizhevsky, 2009), Food-10 (Bossard et al., 2014) and ImageNet-1k 1 (Russakovsky et al., 2015) for image classification, and R52, NG20, and Yelp Review (Zhang et al., 2015) for text classification. These datasets include varying numbers of classes and valida- tion/test set sizes, allowing us to test calibration methods across diverse scenarios (see Table 3 for further specifica- tion). Experiments were conducted using various modern DNN architectures and a few classical machine learning models. To assess the practical usefulness of calibration functions, we compared several models with different archi-
5. Experiments
5.1. Experiment Design
We evaluate post-hoc calibration methods on seven bench- mark datasets spanning both image and text domains:
7

---

Isotonic Normallzation Multi-Clas Calibration 2025
NA-FIR-
40.0%
81.3%
0%
78.7%
76.0%
78.7%
96.7%
NA-FIR
90.7%
97. 33
90.7
70.7%
73.3%
76.0%
96.0%
SCIR
-6.00%
18.7%
62.7%
76.0%
98.7%
0.8
SCIR
6.7%
24.0%
85.3%
25.31
30.70
57. .7%%
66.7%
0.8
FIR
18.7%
64.0% 62.6%
53.3%
72.0%
98.7%
Proportion Wins (%)
FIR
2.7%
76.0%
86.7%
46.0%
53.3%
66.
68.0%
38.0%
89.3%
Proportion of Wins (%6)
0.6
OVR
3%
46.7% 38.7%
72.0
IR OVR
9.3%
14.7%
13.3%
13.3%
10.7
8.0%
84.7%
21.
17.3%
37.3%
52.0%
TS
26.7%
74.7%
50.7%
86.7%
49.3%
31..%000.09
24.0%
0%
46.7%
61. 3%
49.3%
60.0% 60.0%
93.3%
V5
-2..7
69.3%
46.7%
99.3%
49.3%
57.3% 80.0000000 00.0%
MS
21.3% 16.00 16.0%
28.0%
28. 0% 42.7% 40.0%
73.3%
0.2
MS
24.0%
42.7%
32.0%
92. 0%
38.7% 42.7%
53.3%
Uncal
1.3% 1.3%
1.3% 12. .% 8.0% 6.7% 26.7%
Uncal
4.0%
33.3%
10.7% 65.3% 0.0%
20.0%
46.7 7.7%
0.0
NA-FIR
SCIR
FiR
IR OvR
TS
MS
Uncal
NA-FIR SCIR
FIR
IR OUR
TS
MS
Uncal
(a) conf-ECE
(b) NIL
Figure 3. Comparison of conf- ECE and NLL between different calibration methods. Each cell in the heatmap represent the percentage of times the calibration method the row had achieved better score then the calibration method on the column.
tectures and training regimes so overall 75 baseline models being evaluated. For each dataset and model, we applied seven of the calibration methods outlined in Section 3 and Section 4, omitting other mentioned methods for simplic- ity. Detailed information on experimental setup is provided in Appendix B. The performance of these methods will be evaluated using the metrics accuracy, NLL, Brier score, conf-ECE, ew-ECE and TECE. To account for practical considerations, also report wall-clock time. TECE is evaluated with threshold of 1 //k and all calibration met- rics are computed using 15 bins and their respective binning schemes as defined.
demonstrates greater stability, consistently ranking among the top calibration methods even when is not the best performer. It also shows that our approach for constrained NLL optimization was indeed justified, as we can see that NA-FIR not only improves NLL but also conf-ECE when compared to FIR, see Figure for example. Moreover, the results clearly show that NA-FIR outperforms linear scal- ing methods for most datasets except for the FOOD101 dataset where TS excels and Yelp Review where there is abundance of examples in each class. In contrast, SCIR consistently produces lower scores for NLL unwanted surprising property, especially when considering the well performing ECE metrics. Interestingly, this holds even when Brier score is comparable, thus we attribute this unwanted behavior to near zero probabilities arising from overlaps in the cumulative class probabilities.
5.2. Results
Normalization Aware Effect. As shown in Figure 2, while normalization awareness, as defined in Section 4.1, might appear to be a minor adjustment, it has a significant impact on predicted probabilities. Lower FIR probabilities are often inflated by NA-IR and vice versa. This phenomena effec- tively demonstrate that awareness has resulted in increased uncertainty in final predictions which was not accounted when fitting FIR. Looking at cumulative fits of SCIR we can notice that the first rank fit which corresponds to the suggested M2B framework is relatively "constrained" free allowing to learn conf-ECE targeted calibration map, on the other hand many overlaps and order violations seems to occur which can be problematic.
A closer analysis into the gaps, shown in Figure 7 pro- vided in appendix C, reveals that dataset characteristics such as number of classes and data set type correlate with some of the calibration methods performance. TS performed better on image classification datasets, while both MS and IR OvR were greatly affected by the number of classes and samples provided.
With respect to wall-clock time measurements, both TS and VS are highly efficient, completing in matter of seconds across all datasets. In contrast, SCIR and NA-FIR exhibit less favorable scaling behavior. For NA-FIR, each iteration scales linearly with the number of samples (Appendix A.2). In practice, the method required approximately 15 min- utes to calibrate Yelp Review and ImageNet- Ik. SCIR, by contrast, is highly sensitive to the number of classes (Propo- sition 4.1), taking second on Yelp Review but approx-
Aggregated Comparative Results. Table 2 demonstrates that both our proposed methods, SCIR and NA-FIR, achieve state-of-the the- performance in terms of NLL loss and conf- ECE across all datasets. In terms of conf-ECE, SCIR of- ten achieves the best results (see Figure 3), while NA-FIR
8

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
imately 120 minutes on ImageNet-1k. All timing results were obtained on standard single-machine setup without GPU acceleration. Nevertheless, calibration sets are often substantially smaller than training sets and the calibration overhead remains minor relative to model training time.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Lastly, re-visiting our assumptions in this empirical evalua- tion provides a more concrete justification for our approach. First, the superior performance of both the cumulative ap- proach and flattening methods compared to IR OvR indi- cates that leveraging permutation invariance enhances the model's generalization capabilities. Second, the results high- light that order preservation is a reasonable assumption, ef- fectively acting as a classical "variance reduction" technique, as evidenced by the more stable results observed across and within each dataset for the respective methods. Finally, the rankings and performance differences once again empha- size the effectiveness of post-hoe calibration methods in improving model reliability and robustness.
References
Abdar, M., Pourpanah, F., Hussain, S., Rezazadegan, D., Liu, L., Ghavamzadeh, M., Fieguth, P., Cao, X., Khos- ravi, A., Acharya, U. R., et al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information fusion, 76:243-299 2974 2021. 2021.
Ayer, M., Brunk, H. D., Ewing, G. M., Reid, W. T., and Silverman, E. An empirical distribution function for sampling with incomplete information. The annals of mathematical statistics, pp. 641-647, 1955.
Per Model Comparison. We also examine how different network architectures influence post-hoc calibration. For in- stance, results (see Table 4 in Appendix C) for CIFAR- 100, show that highly overconfident architectures (DenseNet, ResNet) benefit substantially from SCIR in comparison to other methods, while ViT and Swin being less overconfident, gain modestly yet consistently. Similarly, conf-ECC ECE result for textual models across architectures show the same trend. Simpler models, such as Fas(Text, Swem-Concat along with classical ML algorithms (NB, SVC), exhibit greater cali- bration improvements (see Figure 11 in Appendix C). In contrast, more advanced models (e.g, BERT- tend to show less variation across calibration methods. We can see how better in advance calibrated models still gain from post-hoc calibration but can be much less sensitive to the underlying mechanism.
Barlow, R. E. and Brunk, H. D. The isotonic regression problem and its dual. Journal of the American Statistical Association, 67(337): (((337))14000 140-147, 1972.
Bossard, I.., Guillaumin, M., and Van Gool, L.. Food- 101 mining discriminative components with random forests. In European Conference on Computer Vision, 2014.
Brier, G. W. Verification of forecasts expressed in terms of probability. Monthly weather review, 78(1):1-3, 1950.
Bröcker, J. Reliability, sufficiency, and the decomposition of proper scores. Quarterly Journal of the Royal Meteo- rological Society: A journal of the atmospheric sciences, applied meteorology and physical oceanography, 135 1643):1512-1519, 2009.
Brummer, N. and Preez, J. d. The pav algorithm op- timizes binary proper scoring rules. arXiv preprint arXiv:1304.22 2013.
6. Conclusions
We have proposed two non-trivial extensions for non para- metric learning in post-hoc calibration that achieve state-of- the-art results. These extensions rely on simple yet effective explicit assumptions and directly incorporate them within the post-hoc optimization framework, rather than resorting to traditional k-one-vs-rest decomposition. By addressing the normalization problem, our approach demonstrates im- proved performance and adaptability to diverse scenarios, providing a more flexible approach for learning a calibration map. While the empirical results are encouraging, several avenues for discussion and further research remain. In par- ticular, the relationship between calibration and refinement when analyzed through user-specific metrics like conf-ECC -CEE, warrants deeper investigation. Our results highlight clear trade-off, emphasizing yet again the complex nature of defin- ing a "weel-calibrated" model.
DeGroot, M. H. and Fienberg, S. E. Assessing probability assessors: calibration and refinement. 1981.
DeGroot, M. H. and Fienberg, S. E. The comparison and
evaluation of forecasters. Journal of the Royal Statistical Society: Series D (The Statistician), 32(1-2):12222 1983.
Ding, Z., Han, X., Liu, P., and Niethammer, M. Local temperature scaling for probability calibration. In Pro- ceedings of the IEEF/CVF International Conference on Computer Vision, pp. 6889-6899, 2021.
Gawlikosski, J., Tassi, C. R. N., Ali, M., Lee, J., Humt, M., Feng, J., Kruspe, A., Triebel, R., Jung, P., Roscher, R., et al. A survey of uncertainty in deep neural networks. Artificial Intelligence Review, 56(Suppl 1):1513-1581 2023.
9

---

Isotonic Normallzation Multi-Class Calibration 2025
Gneiting, T. and Raftery, A. E. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-378 2007.
focal loss. Advances in Neural Information Processing Systems, 33:15288-15299 2020.
Murphy, H. new vector partition of the probability score. Journal of Applied Meteorology and Climatology, 12(4):595-600, 1973.
Good, J. Rational decisions. Journal of the Royal Statisti- cal Sociery: Series B (Methodological), 14(1):107-114, 1952.
Murphy, A. H. and Winkler, R. L.. Reliability of subjective probability forecasts of precipitation and temperature. Journal of the Royal Statistical Society Series C: Applied Statistics, 26(1):41-47, 1977.
Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Naeini, M. P., Cooper, G., and Hauskrecht, M. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the AAAI conference on artificial intelli- gence, volume 29, 2015.
Gupta, C. and Ramdas, A. Top-label calibration and multicllas-tt-binnd reductions. In International Con- ference on Learning Representations, 2022.
Ji, B., Jung, H., Yoon, J., Kim, K., al. Bin-wise tempera- ture scaling (bts): improvement in confidence calibration performance through simple scaling techniques. In 2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW), pp. 4190-4196. IEEE, 2019.
Niculescu- Mizil, A. and Caruana, R. Predicting good prob- abilities with supervised learning. In Proceedings of the 22nd international conference on Machine learning, pp. 625 632, 2005.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, 2009.
Nixon, J., Dusenberry, M. W., Zhang, L., Jerfel, G., and Tran, D. Measuring calibration in deep learning. CVPR workshops, volume 2, 2019.
Kull, M., Silva Filho, T., and Flach, P. Beta calibration: a well-founded and casily implemented improvement on logistic calibration for binary classifiers. In Artificial intelligence and statistics, pp. 623-631. PMLR, 2017.
Patel, K., Beluch, W., Yang, B., Pfeiffer, M., and Zhang, D. Multi-class uncertainty calibration via mutual in- formation maximization-based binning. arXiv preprint arXi::2006.13022 2020.
Kull, M., Perello Nieto, M., Kängsepp. M., Silva Filho, T., Song, H., and Flach, P. Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration. Advances in neural information processing systems, 32, 2019.
Platt, J. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Ad- vances in large margin classifiers, 10(3):61-74, 1999.
Rahimi, A., Shaban, A., Cheng, C.-A., Hartley, R., and Boots, B. Intra order-preserving functions for calibra- tion of multi-class neural networks. Advances Neural Information Processing Systems, 33:13456-13467 2020.
Li, Q. Peng, H. Li, J., Xia, C., Yang, R., Sun, L., Yu, S., and He, I.. survey on text classification: From tradi- tional to deep learning. ACM Transactions on Intelligent Systems and Technology (TIST), 13(2):1 2022.
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211-52, 2015. doi:
Luss, R. and Rosset, S. Generalized isotonic regression. Journal of Computational and Graphical Statistics, 23 10000, 2014.
Marx, C., Zalouk, S., and Ermon, S. Calibration by dis- tribution matching: trainable kernel calibration metrics. Advances in Neural Information Processing Systems. 36, 2024.
10. 10.1007/s11263-015-000
Schervish. M. J. A general method for comparing probabil- ity assessors. The annals of statistics, 17(4):1866-187 1989.
Mozafari, A. S., Gomes, H. S., Leão, W., Janny, S., and Gagné, C. Attended temperature scaling: a practical approach for calibrating deep neural networks. arXiv preprint arXiv: 1586, 2018.
Silva Filho, T., Song, H., Perello-Nieto, M., Santos- Rodriguez, R., Kull, M., and Flach, P. Classifier cal- ibration: a survey on how to assess and improve pre- dicted class probabilities. Machine Learning, 112(9): 3211-3260, 2023.
Mukhoti, J., Kulharia, V., Sanyal, A., Golodetz, S., Torr, P., and Dokania, P. Calibrating deep neural networks using
10

---

Isotonic Normalization-Awarl Multi-Class Calibration 2025
Spouge, J., Wan, H., and Wilbur, W. Least squares isotonic regression in two dimensions. Journal of Optimization Theory and Applications, 117:585-605, 2003.
Vaicenavicius, J., Widmann, D., Andersson, C., Lindsten, F., Roll, J., and Schön, T. Evaluating model calibration in classification. In The 22nd international conference artificial intelligence and statistics, pp. 3459-3467. PMLR. 2019.
Widmann, D., Lindsten, F., and Zachariah, D. Calibration tests in multi-class classification: A unifying framework. Advances in neural information processing systems, 32,
2019.
Wightman, Pytorch image models. attps:///ittti: wightaanpyyoorhhhhheeeceoeo htppppyyttchhhteeee iaae--iaageennn models,
com/ http/rwighhmann 2019.
Zadrozny, B. Reducing multiclass to binary by coupling probability estimates. Advances in neural information processing systems, 14, 2001.
Zadrozny, B. and Elkan, C. Obtaining calibrated proha- bility estimates from decision trees and naive bayesian classifiers. leml, volume 1, pp. 606,616,200 2001.
Zadrozny, B. and Elkan, C. Transforming classifier scores into accurate multiclass probability estimates. In Proceed- ings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 694 699, 2002.
Zhang. J., Kailkhura, B., and Han, T. Y.JJ Mix-n-match: Ensemble and compositional methods for uncertainty cal- ibration in deep learning. In International conference on machine learning, pp. 11117-11128 PMLR, 2020.
Zhang, X., Zhao, J., and LeCun, Y. Character-level convolu- tional networks for text classification. Advances in neural information processing systems, 28, 2015.

---

Isotonic Normalization-Awaal Multi-Class Calibration 2025
A. Normalized Aware Methods Algorithmic Details
A.I. SCIR
A.1.I. PRELIMINARIES
We begin by quoting several definitions and theorems from Spouge, Wan, and Wilbur (Spouge et al., 2003), which will later be utilized to prove the proposed algorithm:
Let X { transitive. Let 9" denote the result of isotonic regression, defined in Equation (2), for the corresponding weights wy E R and values Vi IR.
/ be partially ordered set, meaning there exists a relation 3 that is reflexive, antisymmetric, and
we denote (gls)* as the result of isotonic regression for S C X with the respective wi,
Definition A.1. A subset U S X called an upper set x E U and 3 = 2 E U. A lower set is defined dual manner.
We note that upper sets are closed under arbitrary intersections and unions of upper sets. Similarly, lower sets satisfy this property. Additionally, the empty set is both upper set and lower
Definition A.2. A pair (L, U), where U is upper set and L X U is lower set, is called projection pair if and only if there exists real number such that:
Yx E L, 2 EEU (z) s (glu)"
Theorem A.3. If (L, is a projection pair, then:
9 (z) (gl æEL. (glv)) aeU.
Proof. See Theorem 3.1 in (Spouge et al., 2003).
Using Theorem A.3, we observe that by finding projection pair, we can split the isotonic problem into sub- cub-problems that are easier to compute. Fortunately, we have a systematic way to find such pairs.
Definition A.4. For S C X and S = {i xs E S), define:
1. Avg(S)= = Eies, west
Lics, wa
2. =(5))=iEs)) Wi (ys Avg(X)),
3. Let Ux denote the set of all upper in X. A maximal upper set is an upper set that satisfies U arg max Hu')"), A minimal lower set defined dually.
Theorem A.5. Every non-empty pair (L, where U is maximal upper set, is projection pair. If the empty set is maximal upper set in X, then g" [x for all x, E X.
Proof. See Theorem 3.2, Corollary 3.1, and Corollary 3.2 in (Spouge et al., 2003).
The result above provides powerful framework for solving the isotonic regression problem. Specifically, the isotonic regression problem can be addressed iteratively by:
1. Identifying maximal upper set.
2. Splitting X into projection pairs.
3. Repeating the process until the maximal upper is empty.
4. Unifying the fitted results into an isotonic function on X.
12

---

Isotonic Normalization-AAarr Multi-Class Calibration 2025
A.1.2. 2-D GRID DYNAMIC PROGRAMMING
We focus on X' { (xi, 36) E Claag } and the coordinate-wise partial order relation (p, 3 (q.5) if S q and i j.
Each [0, X {1, {1,...,k k 1}. Since working with isotonic functions, w.l.o.g stable sort X by:
The first argument (cumulative probability),
Then the second argument (cumulative class count).
This sorting allows us treat X' as a grid:
[L...., x (1....,k 1}.
where all points have integer coordinates corresponding to their order index and the cumulative number of classes used. Note that m (k-1), 1), where m is the size of the calibration and is the number of classes.
Definitions and Recursive Setup
Definition A.6. For every grid point (i,j) E N x N, we define an upper set function u: N X + X' as:
((i.j) (k, E x (i,)) = (k,
Note that j(( is an upper set for any i.j.
Definition A.7. We also define set of upper sets for a given point on the grid as:
ū(i,j) = (U u(i,)) S VKk 1) E U k 2 U is an upper set).
Lemma A.8. Let Ux, be the set of all upper sets in X = { k 2 i}. Then:
ū(i, c) = Ux., and in particular, ū(1,)) Ux
Proof. Let U E Ux. We will show that U E ū(i, c): First, note that for every i, u(i, c) = 0, as the second coordinate c is, by construction, not smaller than any point in X. Thus, u(i, e) S U trivially. Second, for all (k:, 7) E X, 2 í by construction. This also applies to U C X. Lastly, U also an upper set in X. For any point x E X' - X, the first coordinate smaller than i, so U E ū(i,.)) implying Ux, S ū(i. c).
Equality holds since U E ā(t, c) implies U is an upper set with U C X.
Lemma A.9. Let 04 (i and m N. Then:
ū(i, + m) -((i 1, m) & u(i,
Proof. Define:
ū(i, + m) -= y Mnng
where:
u-z, = (U' E ū(i,+ $ U},
Ux. = = U E ū(i,++m) ,4 2 E U}.
u-s; u(i,I+ m): let E u- If v; & U, then I(k, U > as there is only one point in X' for each coordinate, u(i,l+ + m) uii + 1, thus U i(i+,,1++ m), leading u-z; ū(i o 1, 1 m). The reverse follows by the same arguments, implying u_x, ū(i + 1, m).
2. Ur. = ū(i. l): let U E uz. since x, E U and U is an upper set, then u(i, S U, meaning U E ū(i,t). Hence, Mz. = ūii. 1). the opposite direction follows as if U" E l(i,l) + o; E U" and the two other conditions are identical for ū(i, 1 + m) leading to ū(i,() C uz
Combining these results, we get:
iii, m) ū(( 1,7 m) w a(i,)).
13

---

Isotonic -ormalization-Aware Multi-Class Calibration 2025
Definition A.10. Define:
M(i.)) max vea(i.))
Hx(U),
where UU) evaluates the cumulative contribution of an upper set U.
Lemma A.11. M(i,j) can be computed recursively as:
M(i + 1,5)+ + max(M(i 1,J), M(i,1) otherwise,
1i 11
M(i,j)
where z; (i,1) and wilyi Avg(2)).
Proof. j S 1, then (i,j) 3 (i,1) = 24 j). Since there is only one point in X' for each coordinate, have
j( u(i, I), and:
= =(.))=((+
Thus:
ū(i,j) ((i,)) U (U u(i Mi++1, CU,(())))))) U: à 2 is an upper set}.
Since there is only one point in X' already included, this reduces
ū(t,j) (()
Therefore:
Miij))
max (x(U)= = wyyy - Avg(Z))) + M(i + -1,)). UER(1.))
j L 4, the result follows directly from Lemma 12:
M(i.j) = max max(M(i 1,5), M(1)),
Complexity Analysis
The algorithm iterates rows in decreasing order and columns in increasing order. For each cell (i.j), the computation involves constant time operations. This leads to complexity of O(N k) O(n k2) for building M and R. Since the algorithm recursively splits A' into two non-empty sets, the overall complexity is O(N2) O(n2k*) (see Lemma 4.1 in (Spouge et al., 2003) for details).
Prediction on the Grid
After computing g" using the outlined method, we extend the framework to include fast predictions for new points. A straightforward generalization from the univariate case is:
min(f" (q (q.1) x max (q.1) (q.1) X, (g. (p, otherwise.
if (p. = ((..))
g' (p, k)
To ensure efficiency on the grid, we define recursive function that pre-computes the maximal prediction for any grid point (i. Initialize:
5(0,-) min(g" (q.1) Cluge):
and for S(i,j) with v, (i, I), use the recursive formula:
S(i 1.j)
if < I if > I.
((i,))
max(g" S(i 1,5))
This computation requires O(N . k) time for pre-computing S(i.j) and (log( k)) for new prediction using binary search.
14

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
Algorithm 3 2-D Grid Sorted Cumulative Isotonic Maximal Upper Set Algorithm
Input: X' {(kk)) l ,.l...,,N] y, R"
2: Initialize M(N+1)xer Rxxe as zero matrices, and b Avg(2))
3: for N to 1 do
4: for j = 1 to do
5: if S. then
6:
j = Mii + 1, + wi(H: (yk b); R(i,J]
7:
else j and (yi - 6) then
8:
M [. = Mli + 1,5]; R(i,]= j
9:
else
10:
Ji = Mii 1,4 wilu b): Rli. =
11: end if
12: end for
13: end for
14: Initialize = [ =c
for
to N'
Set (k 2i
17:
if () < then
18:
Add to S
19: end if
20: Update j = R(),.))
21:
end for
Return: S
A.2. NA-FIR
We will note that the FIR as described cannot solved using previous publications on isotonic solutions, we thus considered alternatives for local minima searching:
1. MCMC optimization (also known as simulated annealing), that works by probabilistic search in the isotonic region.
@1 2. Simple implementation of GD that works by calculating in each step ag ((x)) and after the update projects the isotonic region by applying PAVA.
3. Quadratic programming based methods- SLQSP, trust-constr from scipy were considered.
4. Use penalty approach-code violation into objective function.
where we implemented split blocks be a partition of the current block structure equal mass points within each block such that they not less then Mock__ize_ssee split_fhreshold. since largest bins for small probabilities, complete the bin partition smaller bins used for the remainder. see illustrative example in Figure 4.
Scale. In order to compute Equation (4) we need to calculate the likelihood in each iteration which can result in complexity of Omm-A k num num ) This can lead to high number of operations for high dimensional datasets. given B blocks that partition the [o, 1] domain to non-overlapping bins Bin Bing define:
bj == ((i.)) 1) E [m] x [A] ((x:)) E Bin, A (va): = 1}1
for j in [B] and let e Nmx be a matrix where
C. = Kl E [k] p(z;): E Bin,
91
Let ø denote the value assigned for Bin, and define T C'
mR We can rewrite the log-likelihood from Equation (4)
9
15

---

Isotonic NormallzationnAAare Multi-Class Calibration 2025
Algorithm 4 MCMC Blockwise Normalized Aware Flattened Isotonic Optimization
1: Input: Data X, w; y,, hyperparameters Echange: 3, iterations, min blocks, block split size threshold
2: Flatten X and y: Fftattenn X .latten(,, Vflatinn fllatten()
3: Initialize block structure and fits: (block.structure, structure, block fits] <- PAVA(X, y, w)
4: Refine block structure: [block_structure sttrucuuee,, block_fits] < split_ wwwlooosstuuuuurrrr....... min blocks, www.spiisiiiteeeesssooooooo
5: for = 1 to num iterations do
6: Select random block: block ~ (etllckeetbokcckssssuueuui
7: Perturb block fit: 8 {-1,1}, change Cchange 8
8: Update suggested fit: suggested block fit block fits/block) change
9: Validate isotonicity suggested block fit
10: if likelihood > current_ likelihood then
11:
Update: best likelliid + likelihood, best_fit <- brrgested.bloc..fft end if
12:
13: if likelihood > current.likelhhood or randO) < exp(3 (likelihood - current.ikclihood)) then
Accept: block fits + suggested block fits 15: end if
16: end for
17: Return: best block fits
A OOOOOOOOOOO ........o
C
00o
A'
B
D
E'
F
o00
Figure simple example for block split with values block size saciee_sp____taae threshold 2, mire blocks original PAVA solution of block-structure.
as follows:
k
I(g)
(B:) log (g(p(x:)))
log
g (p(x)))))
1=1
3m
B
m
Σ by log(g,)
log (T₃)
Since each iteration our optimization changes only one block value 9j. we can exploit this sparsity to efficiently compute the updated objective. We incrementally update the relevant entries via Tnew T C, Echange 6, where C, the j tt column and Cchange, 5 are defined in Algorithm 1. This allows us calculate the likelihood in ((m) operations per iteration.
In our experiments, ran the MCMC algorithm with bela 200, maximum of number of 1 iterations, and early stopping criterion triggered if the best likelihood did not improve for 10 iterations. This configuration consistently yielded stable results and often outperformed alternatives, even when the number of bins matched the PAVA solution. For simplicity, we report results based on this setting.
16

---

Isotonic -ormalization-Aware Multi-Class Calibration 2025
B. Additional Experimental Details
B.1. Dataset Descriptions
1. CIFAR-10: Consists of 60,000 32x32 color images in 10 classes, with 6,000 images per class.
2. CIFAR-100: A refinement of CIFAR-10 with 100 classes, each containing 600 images per class.
3. Food-101: Comprises 101 food categories with a total of 101,000 images. Each class contains 250 manually reviewed test images and 750 training images.
4. ImageNet-1k: 1k: Contains 1.2 million training images and 50,000 validation images across 1,000 object categories. Drawn from the ImageNet Large Scale Visual Recognition Challenge (ILSVRC).
5. R52: Collected from the Reuters financial newswire service in 1987. Only label categories appearing in both train and test. datasets are retained.
6. NG20: Contains approximately 18,000 newsgroup posts on 20 topics.
7. Yelp Review: Comprises Yelp reviews and their respective star ratings. Extracted from the Yelp Dataset Challenge 2015 data.
Table 3. Comparison Study Dataset Descriptions
Dataset
Type
# Classes
# Models Used
Validation Set Size
Test Set Size
CIFAR-10
Image Classification
10
4
5k
10k
CIFAR-100
Image Classification
100
13
5k / 2.5k
10k / 7.5k
Food- 101
Image Classification
101
8
6.3k
18.6k 6k
Imagenet-Ik -k
Image Classification
1000
8
12.5k
37.5k
R52
Text Classification
52
10
0.6k
1.9k
NG20
Text Classification
20
10
1.7k
5.3k
Yelp Review
Text Classification
5
22
12.5k
37.5k
Text Classifiers
Since for text classification there not enough datasets with many classes and pre-trained classifiers, trained models based on (Li et al., 2022) text classification review for all datasets.
R52 and NG20: A total of 10 models were trained. All BERT-based models were trained with an evaluation set comprising 10% of the data for epochs, using a learning rate of 1.5e-05 and batch size of 16. The best model was selected based on evaluation set accuracy. For simpler neural network models (FastText, Kim-CNN, and SWEM-Concat), the best-performing model was chosen from the following parameter grid:
Batch size (bs): [16, 32]
Learning rate (Ir): [le-3, 5e-3, 1e-2]
These models used GloVe 6B with 300-dimensional embeddings. For Naive Bayes (NB) and SVM linear models 5-fold cross-validation was with Parameter grids of:
Naive Bayes (alpha): [0.01, 0.05, 0.1, 1.0, 10.0]
SVM (C): [0.1, 3, 10, 100]
Model architecture trained:
albert-base-v2 (link)
17

---

Isotonic Normalization-Awe Multi-Class Calibration 2025
bert-base-uncased (link)
bert-large-uncased (link)
distilbert-base-uneeee (link)
fast-text
kim-enn
nb (link)
SVC(kernet="linearr (link)
swem-concat
xlnet-base-cased (link)
Yelp Review (YR): A total of 22 models were trained. The same models as above were trained on this dataset, with the following adjustments:
Evaluation set size reduced to 1% the data.
Introduced checkpointing every 500 steps.
Added early stopping with minimum 0.5% improvement in evaluation accuracy.
Additionally, 12 pre-trained models from HuggingFace were used:
bert Dert-base-uncased-ht (link)
hert-base-cased-hf (link)
Bert-base-cased. (link)
hert-base-cased-hf-- (link)
bert- sattbase-casd----- (link)
bert-base-cased-hi--4 (link)
distilbert-bass--nccseehhf (link)
distilbert-bas--uncaeede (link)
gpt2-hf hf (link)
roberta-hf (link)
ZS-deberta-base (link)
7S-deberta-small (link)
C.2 Image Classifiers
CIFAR-10: A total of 4 models were used, all provided by the Focal Calibration Library (link):
Densenet121
Resnet 10
Resnet50
Wideresnet
18

---

Isotonic Normalization-Aware Multi-Class Calibration 2025
CIFAR-100:
A total of 4 models were used from the Focal Calibration Library (link), and additional 9 models from
HuggingFace:
DenseNet121 (link)
ResNet18 (link)
ResNet34 (link)
ResNet50 (link)
Swin (link)
Swin-1 (link)
16 (link)
VIT (link)
ViT-1 (link)
Food-101:
All models were sourced from HuggingFace:
Swin (link)
Swin-1 (link)
Swin-2 (link)
Swin-3 (link)
VIT (link)
VIT-1 (link)
VTT-2 (link)
VIT-3 (link)
Imagenet-1k:
All 8 models sourced from HuggingFace (Wightman, 2019):
Beit (link)
ConvNeXT (link)
Swin (link)
ResNerRS-B (link)
DenseNet-121 (link)
Eva (link)
MobileNetV3 (link)
ViT (link)
19

---

Isotonic Normalization-AAarr Multi-Class Calibration 2025
C. Extended Results
C.0.1. TRAINING OPTIMIZATION
SCIR Empirical run time estimations for NG20 dataset for both for min-cut graph partition (using Igraph package from python) and dynamic grid partition:
note that our proposed dynamic grid partition also replicated using much bigger dataset (cifar-100 100 with 10K test samples) and comparison to randomly generated data yielding the below results:
only much faster but gains seems to be linear. this phenomena
Allowing us to scale efficiently for all the datasets included.
Fit Time vs. n for Partitioning Methods
Min Cut Partition
Dynamic
2.84)
1.000
Time (seconds)
100
75
50
25
06.84)
4000
5000
6000
7000
8000
9000
10000
Figure 5. fit time in seconds for dynamic grid partition vs min cut partition
Fit Time of Dynamic Grid Partition for Cifar-100 and Random Data
Cifar-100
120
0ln81.78)
0.995
Time (seconds)
100
11.5)
250000
350000
Figure 6. fit time in seconds both for Cifar- 100 data each time binning few classes together to create less samples in the cumulative induce problem set and randomly generated data to account for inter-depensencies due to the structure of the problem.
20

---

Isotonic NormallzaaionnAAare Multi-Class Calibration 2025
C.0.2. COMPARISONS
Comparison of calibration methods for all metrics across datasets
324
322
326
calbritbe,, mothod
celbritton mrch od
3.6
3.5-
4.2
3.0
ada
towes Surene
calkto
Conkes
toulim
(a) -CEE
(b) NLL
Figure 7. Comparison of conf-ECE and NLL values across datasets. NLL values were normalized within each dataset by subtracting the mean and dividing by the standard deviation.
3319
3356
Na-ie
3300
3515
ocpa
20W5
ONWDD
C
152
Y8
Inigetet
399C
052
C CIMIOO
CINREEO
FeeeC::
Imagete:
(a) TECE
(b) Brier Score
Figure 8. Comparison of TECE and Brier score values across datascts. Brier score values were normalized within each dataset by subtracting the mean and dividing by the standard deviation.
21

---

Isotonic Normalization-ANe Multi-Class Calibration 2025
SC.
Bage
Beg8
2040
622
CPARID Sctime
crvizes
bectt1
Inagellet
23VC
CRARLEO
reeet::
durere
(a) CECE non normalized
(b) CECE normalized
Figure 9. Comparison of CECE across datasets, Both normalized and non normalized plots are presented as differences are small.
22

---

Isotonic -ormalization-Aware Multi-Class Calibration 2025
Win Ratios for all metrics Each cell in the heatmap represent the percentage of times the calibration method the row had achieved better score then the calibration method the column.
NA-FIR
NA-FIR
0.7
0.8
SCIR
74.7%
74.7%
54.7%
73.3%
68.0%
37.3%
74.7%
SCIR -5.33%
68.0%
60.0%
0%
80.0%
60.0%
FIR 20.0% 24.0%
46.7%
53.3%
56.0%
32.
52.0%
61.3%
Proportion of Wins (%)
FIR
32.0%
32.0%
44.0%
69.3%
52.0%
60.0%
84.0%
0.6
P 04000000 Wins
IR OVR -52.0%
41.3% 52.0%
54.7%
62.7%
36. 0%
56.0%
0.5
IR OvR
-4..7%
0%
56.0%
65.3% 57.3% 56.0%
77.3%
0.5
-36.0%
TS
0.4
-44.0%
29.3%
44.0%
36
0%
41.3%
30.7%
41.3%
VS
42.7% 37 37 48.0% 42.7% 60.0%
46.7%
30.0%
MS
65.3% 61.3%
65.
3% 4..%% 61.3% 69. 99.3%
62.7%
MS
33.33% 40. 0% 40.0% 44.0% 58.7% 53.3%
69.3%
0.2
Uncal
36.0% 24, 4.00
37.3% 44.0%
26,7 58.7% 37.3%
Uncal
16 16.0% 10. 7% 16. 16.0% 22, 7% 0% 20 0% 30.7%
0.2
NA-FIR
SCIR
FIR
IR OVR
TS
MS
Uncal
NA-FIR SCIR
FIR
IR OVR TS
VS
MS
Uncal
(a) Accuracy
(b) TECE
0.9
0.9
NA-FIR
80.0%
77.3%
66.7%
76.0%
55.3%
72.0%
90.7%
NA-FIR
61.3% 57.3%
46.7%
70.7%
54.7%
58.7%
88.0%
0.8
0.8
SCIR
20.09
32.0%
54.7%
37%
50.7%
65.3%
SCIR -3.7%
53.3%
38.7%
66.7%
3%
56.0%
69.3%
FIR
FIR 42.7%
Wins
IR OVR
33.3%
45.3%
40.0%
50.7%
46.7%
68.0%
73.3%
IR OvR 53.3%
61.3% 58.7%
64.0%
64.0%
72.0%
3%
TS-0
24.0%
42.7%
32.0%
49.3%
42.7%
62.7%
99.0%
TS 29.3%
19.3%
33.3%
33.3%
36.0%
33.3%
50.7%
86.7%
VS
34.7%
49.3%
41.3%
53.3%
57.3%
81.3%%
VS
45.3% 7%%
48.0%
36.0%
66.7%
49.3%
69.3%
MS
28.0% 0%%.34.7% 34.7% 29.3% 32.09 37.3% 36.0%
52.0%
MS
41.3% 44.0% 42.7% 26. 8.0%
49.3% 50.7%
69.3%
0.2
Uncal
Uncal
0.1
0.1
NA-FIR
SCIR
FIR
IR OVR
TS
MS
Uncal
NA-FIR
SCIR
FIR
IR OVR
TS
MS
Uncal
(c) BS
(d) CRCE
23

---

Isotonic -ormalization-Aware Multi-Class Calibration 2025
Model architectures results comparison A comparison between older and newer architectures across given relevant datasets. Note that number of samples per model architecture is low.
text models
0.200
0.150
0.125
Calibration Method NA-FIR
0.015
SCIR
0.025
IR OvR
0.000
TS
bert-large uncased
bert sas-base-uuee uncased
distibert Metibbertbaase-ee saatt-aaee---te uncased
fast-text
swem-concat
MultinomlalNB
SVCikemel= (Clkkeeet="lnnarr) llnner))
VS
MS
Uncalibrated
Model Architecture
Figure 11. conf-ECE plotted for same model architecture and aggregated across datasets
Rank
Calibration Method
NA-FIR
SCIR
IR OvR
bert- www-llaree-une uncased unnrasedg--uedeed
bert-based uncased
distibertt Sltthert-base-une base uncased
fast-text
swem-concat
MultinomialNB
SvCikemet= es lliear))
Uncalibrated
Model Architecture
Figure 12. conf-ECE rank mean plotted for same model architecture and aggregated across datasets
24

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
3.0
2.5
2.0
Calibration Method
15-
NA-FIR
1.-
IR OvR
bert- bert-large port-large-unee uncge-dd
bert bert-base-und bes-bass-uncedd
distilbert Betilbert-base-ur -ancr----a----e-ddd
uncased
fast-text
swem-concat
MultinomlalNB
SvCikemel = llinear))
vs
Uncalibrated
Model Architecture
Figure 13. NLL plotted for same model architecture and aggregated across datasets
2 Rank
Calibration Method
IR
bert-largen part-large-uncased
bert bert-base-une uentbbas--uncsed uncased
distilbert base uncased
fast-text
swern-concat
MultinomialNB
Svcikemel er 'linear')
VS
Uncalibrated
Model Architecture
Figure 14. NLL rank mean plotted for same model architecture and aggregated across datasets
25

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
Per Model tables
Table CIFAR 100 models comparison
MODEL ARCHETICTURE
DENSENETI21
RESNETi10
MODEL
TECE
NLL
CW-ECE
UNCALIBRATED
75.48%
20.98%
2.056
0.450%
0.00446
17.08%
77.27%
19.05%
1.792
0.41%
0.004071
16.61%
NA-FIR
75.51%
4.91%
1.112
0.229%
0.00359
4.12%
77.35%
5.38%
0.977
0.21%
0.003297
4.48%
SCIR
75.20%
1.57%
1.204
0.221
0.00353
3.62%
77.00%
1.27%
0.995
0.20%
0.003248
4.00%
75.51%
7.56%
0.238%
0.00370
7.06%
77.35%
7.08%
1.047
0.22%
0.003377
7.14%
75.28%
0.218
0.00370
5.27%
7.36%
1.539
0.21%
0.003394
5.87%
TS
75.48%
5.06%
1.190
0.236
0.00371
7.14%
77.27%
5.04%
1.045
0.21%
0.003383
7.17%
VS
75.84%
4.83%
1.169
0.219
0.00361
6.07%
77.28%
5.36%
1.048
0.22%
0. 0.003387
7.02%
MS
71.79%
13.87%
1.860
0.361
0.00433
8.09%
73.88%
12.91%
1.843
0.34%
0.004118
7.95%
Both models were used in (Mukhoti et al., 2020)
MODEL ARCHETICTURE
SWIN
VIT
CALIBRATION MODEL
ACCURACY
CONF-ECE
NLL
CW-ECE
TECE ACCURACY
CONF-ECE
NLL
CW-ECE
BS
TECE
UNCALIBRATED
87.19%
89.63%
0.160%
0.001679
7.14%
NA-FIR
87.19%
0.84%
0.4116
0.14%
0.00183
89.57%
1.68%
0.121%
0.001517
4.52%
SCIR
87.20%
0.88%
0.4698
0.13%
0.00185
4.91%
89.43%
1.09%
0.430
0.118%
0.001525
4.39%
FIR
87.19%
1.33%
0.4121
0.14%
0.00183
5.22%
89.56%
2.84%
0.379
0.119%
0.001538
4.80%
TR OVR
86.49%
3.30%
1.3629
0.16%
0.00197
6.54%
89.55%
3.86%
1.234
0.134%
0.001583
5.00%
TS
87.19%
1.08%
0.4112
0.14%
0.00183
4.71%
89.63%
2.96%
0,396
0.122%
0.001571
5.89%
VS
86.89%
1.75%
0.4347
0.16%
0.00190
5.59%
89.59%
3.67%
0.439
0.137%
0.001634
6.57%
MS
83.08%
7.10%
0.6514
0.22%
0.00252
7.86%
88.75%
5.36%
0.537
0.163%
0.001 790
6.62%
Both models are publicly available on HuggingFace.
Table 5. BERT and XLNet calibration comparison
Model Architecture
BERT-Base SeETT-Bsee-nnee Uncased
XLNet-Basec Base-BaaeCC
Calibration model
Accuracy
conf-ECE
ew-ECE
TECE
Accuracy
conf-ECE
cw-ECE
BS
TECE
Uncalibrated
95.90%
2.34%
0.1927
0.169
0.001341
13.75%
94.40%
2.38%
0.2626
0.200%
0.001654
13.40%
NA-FIR
95.80%
1.4%%
0.1873
0.163%
0.001272
14.54%
94.55%
1.77%
0.2513
0.206%
0.0016227
15.88%
SCIR
95.90%
1.34%
0.1992
0.162%
0.001324
10.90%
94.29%
241%
0.3746
0.198%
0.001785
13.28%
FIR
95.90%
0.163%
0.001279
14.20%
94.55%
0.2562
0.204%
0.001649
15.55%
IR OvR
94.61%
2.51%
1.2967
0.189%
0.001583
7.65 %
94.29%
2.65%
1.2616
0.210%
0.001782
10.82%
TS
95.90%
2.00%
0.1909
0.175%
0.001339
13.62%
94.40%
2.34%
0.2551
0.206%
0.001644
12.51%
VS
95.95%
1.59%
0.1995
0.160%
0.001304
12.56%
94.81%
2.12%
0.2588
0.197%
0.001634
13.58%
MS
94.71%
1.47%
0.5322
0.19%
0.001537
7.92%
93.41%
1.52%
0.5712
0.232%
0.001887
8.05 %
R52 models BERT base and XLNet base cased both models were trained for this thesis.
Model Archeticture
BERT-Base- Uncased
XLNet- Cased
Calibration model
Accuracy
conf-
cw-BCE
TECE
Accuracy
conF-ECE
cw-ECE
Uncalibrated
75.13%
12.01%
0.9437
1.309%
0.01 886
11.00%
75.36%
12.80%
0,9561
1.386%
0.01881
10.83%
NA-FIR
75.17%
2.02%
0.8583
0.720%
0.01733
4.87%
75.25%
1,89%
0.8468
0.687%
0.01716
4.99%
SCIR
75.11%
4.01%
0.9158
0.805%
0.01756
4.93%
74.81%
2.15%
0,9400
0.652 %
0.01748
4.96%
FIR
75.17%
1.76%
0.8743
0.712%
0.01731
4.88%
75.27%
3.47%
0.8914
0.680%
0.01731
5.56%
IR OvR
75.19%
1.86%
1.0050
0.695%
0.01751
5.46%
75.34%
4.19%
1.1708
0.692%
0.01745
5.59%
75.13%%
6.20%
4.69%
0.8467
6.50%
75.23%
2.43%
0.8847
0.814%
0.01775
6.80%
75.13%
3.35%
0,8536
0.731
0.01751
6.20%
MS
74.98
1,95%
0,9063
0.643%
0.01 808
5.55%
74.45%
4.88%
0.9021
0.802%
0.01807
6.44%
NG20 models
BERT base and XLNet base cased.. both models were trained for this thesis.
26

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
D. Isotonic Regression Properties
Theorem D.1. Let : [0, 1] x [0,1] + (-o0, be proper scoring rule and = {(11, (11,,9)),,, (En. The isotonic
optimization problem that induced by this scoring rule and total order S
min
S(g(z)) u.) we s.t. g(zi) S g(2)) when 24 S 2j
is solved by:
Σj=u Wyys
8/4 = min max
s.t. u usisi
j=
Before presenting the proof, it is worth noting that Barlow & Brunk (1972) had proved functional relationship of the isotonic squared етrоr minimization result to any other convex functions even for partial, demonstrating that the same solution holds for NLL and Brier score. In addition, the above stated theorem was previously established by Brummer and Perez (Brummer & Preez, 2013), a result that we were unaware of during the writing process. Nevertheless, we provide a much simpler and more accessible proof.
Notations.
Assume w.l.o.g. that x; S xy whenever i j. Define:
a(i) = (U E U}: the set of possible upper sets for i.
I(i) [L E L.j: the set of possible lower sets for i.
Avg(S)= Lees Malk
.SC (1. The weighted average of S.
Eres we
s = - (klis k j}: The set of indices from to j.
U(S) (U U SAUSAAU is upper set in S): The of all upper sets within subset S.
two key properties the described solution:
1. The solution is isotonic: Since for < j,, (.) c i(t) and ū(i) C ū(j), we have:
((x;) = min max Avg(((() ((() ī(t)) < min max Avg ((1) n ((1) S min max Avg(E())n(()) = 5(x;)) ((0) a(t)
(() a0)
Kg) a(y)
2. Fixed on Partition:
The described solution creates partition I of (1,2....,, such that for every A E I C (1.2..... n), , it holds that g(æx) ((x,) for all i,j E A. Let uf and I represent the respective maximizing upper and lower sets for the min-max solution, with A = uf n For any E A, if < i, we have ū(j) C ū(i). Thus, since E A, u}= = ur, leading to ((x:)) = j(x,). if j. we know that Avg( A) I Avg(S (mi))))();)) since we minimize over ((t). Thus, Avg(((max(vu)) < Avg(A), leading to Avg(S (m)m)();)))) Z Avg(S?) for all > i. Therefore, uz = ut, which leads to g(x.)= g(zz).
Lemma D.2. Convexity lemmu for binary proper scoring rules. For a binary proper scoring rule S* the minimizer over the interval [p.p] given by:
arg min PS45
S* max(p, min(p.p)).
Proof. By definition:
pS = =
(1- 0),
and using the properties proper scoring rules (see Schervish (1989)), we have:
S(g. 1) = e(g) + - D) (q), S(g. 0) e(g) - qe' (g):
27

---

Isotonic Normallzation-AAarr Multi-Class Calibration 2025
where is a concave function. Thus:
(g. c(q) (p (p-g)e'(at)) 2))
and the derivative of S* with respect to is:
05 (q. p) = (4 + (p q) c' (p- (q) dq
Since e is concave, e" is non- non-positive. Therefore, (g p) is monotonic decreasing for q S p and monotonic increasing for q > p. Thus, the minimum will be obtained at:
max(p,minp,.71 min(p. p)).
Lemma D.3. Let y1, "2,.... Un be a series where yı E {0, 1}. with respective weights W1, W2,...> Wn-
Wnn- Suppose the
following property holds:
arg max Aag(U = =1,,2 ..,,,,..,, n [[n]
Then bounded isotonic regression:
max
(l(())))))) s.t. s(i) S for) pSosP
solved by:
max(a, Avg((n)))
Proof. By induction. For 1, the solution follows directly from the properties of the scoring rule S, S( 1) is monotonic increasing and S(e, 0) is monotonic decreasing. Assume the result holds for any series of length S and prove for n + 1.
Let y1, $2. Un. Uh+1 be a series holding (+). We will assume 3n+1 = 0, as otherwise the series entirely composed of 1s, and the statement follows naturally. Let be the index of the maximal appearing sequence which holds (*), meaning:
k max i5n
(i) arg max Avg(U) -(i] UEU(Si)
We will show that both Ag {y1, 1/2
8k } and A (yk+1, 1n++1 hold (+). The set Ag holds (+) by its selection.
For A,, assume it does not hold. Then there exists & 1 1 < n such that:
arg max (E
Avg(U)= = S
yielding the following inequalities:
1. Avg(S 2 Avg(S
2. Avg(S 2 Avg(S!-1)
3. Avg(S!++) & Avg(Sp+1)
4. Avg(S(+() & 1tg(
28

---

Isotonic NormalliaatinnAAare Multi-Class Calibration 2025
Inequalities (3) and (4) hold because (v1.-.... such that:
Un+1) - satisfies (+). Now, since I - k, there exists index <1'<1-1
St arg
max Avg(U), UEU(S
and in particular, this implies:
(5) Avg(S S Avg(S)
If l' ki it would contradict the fact that sp+t1 is the maximal upper set for A1. From (4) and (5), have:
(6) Avg(S;*') AAvg(S); + ))) AAvg(S (1 2 Avg(S?+!),
thus 1' < k. This allows to rewrite (5) as:
(1 wi Av)gAv(S))) w Avg(S (1- ArggA) + Avg(
where:
W1 xi*++ Wi
k=k+11
W
W22
1=
si=1
W
Noting that 2 w2 and the fact that S 2 kt1 we obtain from (6):
(1- - w1))Av((S) + (w) Ay)Avg(S()) 2 wy)Avg(S(),
which implies Avg(S): 2 Avg(S*), contradicting the assumption that Ag holds (+). Therefore, both Ao and Ag hold (x), and we can apply our induction theorem to them.
marking Qı, Q2 for Ølst and ölstt,, respectively, we have:
Avg(S
(++1)
if I Avg(( $ p,
Q2
=
if Avg(Satt) < m) Sp.
if S P Avg(S*++) sn+1)
p
Using the convexity lemma for proper scoring rules, and since Avg(S*+1) that if q2 > 41, we can further decrease our score by increasing Qı, leading to the conclusion that in the optimal solution Q2 g² Now:
(+11) < Avg(S}) as (v...., Mo++ holds (+), we get
n+1
a+1 S(q. Di y:)w
I Wi Vi S(q. 1) + Σjel Wj (1 yi)
max
S(g. y.w, = max
max
S(g. 0).
9 im1 1=1
Σ j= Wj
j= Wi
> Wi Σy wy
Let p =
Then:
max pS + (11)))((10))))) Su
max(p, min(7.)))
9
leading to our desired claim.
29

---

Isotonic Normalization-Awar Multi-Class Calibration 2025
From the convexity lemma and induction base cases, and with our earlier observations, Theorem D.1 proof becomes straightforward
Proof. Let 7 be a partition of (1,2,...,,,) n) achieved by the described solution. We notice that every A E 7 holds the lemma property, as for every group, the maximization set for the given lower set is the same, including the last element in the group. Knowing that:
min
S(g(z)), vi)u; 2
Σ
min Σ
S(g(zz)) ve)ws
ACT
iEA
subject to:
g(x;) S g(zz) when H; S Zzj
and given the lemma, we know that the solution for the latter problem is:
AA E L,Vi A: Avg(A).
Given the isotonic nature of this solution, it is also feasible for the first minimization problem, proving our desired result.
30


Reviews:
[{"review_id": "UeOaZ1nHiz", "reviewer": "Reviewer_7kNs", "summary": "This paper proposes two isotonic regression based approaches that incorporate normalization into problem formulation of multiclass calibration:\n* Normalized Aware Flattened Isotonic Regression, which finds a mapping g such that g(p(x)) is normalized before computing the NLL objective.\n* Sorted Cumulative Isotonic Regression, which finds a g that minimizes binary cross entropy loss on some set.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. \n\nThe major concern is regarding statistical properties of the algorithms we propose, in particular NA-FIR. This is expressed in the review sections on Claims and Evidence, Theoretical Claims and the last point of Questions for Authors.\n\nRegarding the statistical properties, it is important to emphasize that the NA-FIR loss function in Eq. (4) is a standard multinomial NLL (with one expression for each observation), in contrast to the loss function for previous FIR variants (Eq. (3) in our paper) which is indeed “summing over the classes” as the reviewer notes. The first implication is that the reviewer’s last comment in Questions for Authors regarding Eq. (4) is incorrect since Eq. (4) is a standard multinomial NLL. It also means that NA-FIR indeed uses a proper scoring rule for calibration (it is well known since Good (1952) that multinomial NLL or “log score” is proper), which addresses the reviewer’s statistical consistency issue. NA-FIR is non-convex (as are other calibration methods), so does not guarantee algorithmic convergence, however, the loss function is proper and statistically consistent. We will make this point more explicit in the paper’s published version, if accepted. For our second algorithm SCIR in Eq. (5), indeed the loss function is similar to FIR and “sums over the classes”. We agree that this is not ideal in terms of statistical performance, but it is common practice, as the reviewer notes.\n\nAdditional issues: \n\n* Clarity of the SCIR (second) approach, referred in second comment under Methods and Evaluation Criteria. We emphasize that all terms in Eq. (5) are defined, although we acknowledge that the definitions can (and should) be made clearer, especially given the conceptual complexity of the SCIR approach. Specifically, $\\tilde{y}$ is the cumulative label, defined via the definition of $CU_{sorted}$ and explained right after Eq. (5). The function $g$ is the optimization objective (over 2d space of cumulative probability and rank), and is implicitly defined through that.\n \n* The first two Questions for Authors note clarity issues in the beginning of Section 4, when motivating the desired properties of multi-class calibration. We agree that the discussion in this part should be improved. Specifically to the reviewer’s comments, the word “thus” was intended to refer to other non-parametric approaches that assume category independence during calibration, and  normalize predictions in the actual prediction process. The example in l197 was indeed intended to demonstrate that marginal calibration is weaker than calibration in Def. 2.1 as the reviewer notes. This was intended for readers who may not be as familiar with these notions. We will make an effort to improve clarity of this part.\n\n* Missing reference to Rahimi et al. (2020) who define similar criteria to the ones we do in Sec. 3.3. Thank you for this reference, which is indeed relevant, and will be added to our paper and properly referenced. We note that our focus is on the algorithmic non-parametric contributions we propose, which are not related to their paper. \n\n* Typos noted under Comments and Suggestions. Thank you for these, we will address them.", "claims_and_evidence": "The paper proposes two calibration methods with builtin normalization. Those methods can ensure normalized output, but my major concern is the statistical consistency. That is, assuming the assumptions are correct for the underlying distribution, there is no guarantee that the proposed algorithms will achieve the meaningful optima as measured by some proper scoring rule (or even any weaker metrics such as different forms of calibration errors). For the first method, the authors point out that it may not recover global optima because of the nonconvexity. For the second method, the algorithmic convergence is given but the statistical convergence or consistency is missing.", "methods_and_evaluation_criteria": "The first approach: The intuition make sense. The assumptions are strong and needs more technical discussion. See my last point in the question section.\n\nThe second approach: I find it difficult to parse the equations. For example, in Equation (5), \\tilde{y} is not defined; function g is not defined (why does it take two arguments?). As such, I'm not sure if the intuition checks out for this approach.", "theoretical_claims": "The authors discussed the algorithmic convergence of the second algorithm. I did not check the correctness because my major concern is in statistical concistency/convergence.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "* Both major assumptions discussed in Section 3 have been studied before [1]. Using the concept introduced in [1], Category Independence means p \\mapsto P[Y|\\hat{p}(X)=p] is diagonal, and Order Preserving means \\hat{g} is intra-order preserving.\n* Moreover, I think Section 4 needs improvement in terms of conciseness, clarity, and organization. [1] did a better job in terms of being precise with the language.\n\n1. Rahimi et al., Intra Order-Preserving Functions for Calibration of Multi-Class Neural Networks, NeurIPS 2020", "other_strengths_and_weaknesses": "Strength: the experiments cover many datasets.", "other_comments_or_suggestions": "Typo:\n* There's an extra \"2025\" in the running title at the top of each page. \n* L037 right: \"have highlighted the effectiveness of ”simple” para-\nmetric approaches\": please fix the left quotation mark. \n- L268 left: Use macro \\log (so that it's not displayed in italics). Use \\left( and \\right) around the fraction as in L273.\n* L273 left: NA-FIR should be wrapped in \\text{} as in L268.", "questions_for_authors": "- L189 right: \"We believe valid probability predictions are essential for building trust among practitioners, especially in decision-making frameworks, thus the only alternative offered is assuming Category Independence.\"\n\t- Can you elaborate the logic implied by \"thus\"? I understand that ensuring valid probability predictions is equivalent to requiring the calibration function is a mapping from the simplex to itself; why does it necessarily require the Category Independence assumption to hold?\n\t- Also this paragraph seems out of place. The \"This\" at the beginning of the following paragraph refers to the weakness in the previous paragraph, and I'm not clear of the goal of this paragraph.\n- L197 right: \"...differences that cannot be solely attributed to observed miscalibration in the intervals around the marginal predictions of 0, 0.1, 0.2.\"\n\t- I don't understand what this means.\n\t- It is well known that marginal calibration (do you mean classwise-calibration in Def 2.2?) is strictly weaker than (canonical) calibration (Def 2.1). What is the point of using an example here to illustrate this?\n- L268 left: Equation (4) is a sample version of NLL. I am generally skeptical about breaking down the classes in the objective function which requires strong assumptions. Summing over the classes in Equation (4) essentially treats every class dimension of every sample is independent. This is in general not true. However, I am aware that many prior works (most notably, see Step 1 Data Ensemble of Zhang'20 mix-and-match) take this assumption. My main concern is why minimizing such a loss function will optimize the proper scoring rule, or even any weaker metrics like canonical or classwise calibration error?", "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": "", "extra_scores": {}}, {"review_id": "QB8juPIBT3", "reviewer": "Reviewer_mZju", "summary": "he paper discusses a tweak on a post-hoc recalibration method for the multi-class classification algorithm. One of the widely used methods for post-hoc recalibration in the binary setting is the isotonic regression: given already a classification algorithm, we can consider a new regression problem where the covariates $x_i$ are now the predictions $p_i$ of the previous algorithms, and the response variables $y_i \\in \\{0, 1\\}$ are associated with the actual distributions. The isotonic regression finds a recalibration function $g : [0, 1] \\to [0,1]$ minimizing a proper-scoring loss $\\mathbb{E}_i \\ell(g(p), y)$ among all non-decreasing functions $g: [0,1] \\to [0,1]$. As it turns out, given sample $(p_1, y_1), \\ldots (p_n, y_n)$, there exist an efficient algorithm solving this minimization problem exactly, and the solution is always a piecewise constant function.\n\nThe generalization of this recalibration method to multi-class classification setting is much more tricky; now, the algorithm outputs a probability vector $p \\in \\Delta^k$, and we would like to provide some re-parametrization of $p$ that improves the proper loss. A method proposed previously (Patel et al. 202, Zhang et al. 2020) is to just attempt to minimize over all univariate monotone functiosn $g$ the negative log likelihood loss\n$\\mathbb{E} \\sum_i - y_i \\log( g(p(x)\\_i))$, and then report the normalized $g(p\\_i)/\\sum\\_{j} g(p\\_j)$ as the final probability vector.\n\nThe authos observe that in the objective function here, the log-likelihood is calculated with respect to a vector $g(p_i)$ over $i \\in [k]$ which is not necessairly contained in the probability simplex. They suggest directly minimize over monotone $g$ the desired log-likelihood \n$\\mathbb{E} \\sum_i - y_i \\log(g(p(x)_i) / \\sum_j g(p(x))_j)$.\n\n\nThis is relatively simple and natural tweak to the idea of Patel et al and Zhang et al.  Since the empirical minimization problem is not convex anymore, in contrast with the simple one-dimensional situation where the global minimum could be obtained explicitly, here it is not clear how to actually find a reasonable function $g$.\n\nThe authors tried several optimization heuristics to solve the computational problem at hand, and report the best of the attempted solutions. They ended up starting with a piecewise-constant function provided by a standard one-dimensional isotonic regression for the unnormalized problem, splitting the regions on which the function is constant into shorter sub-intervals, and applying a simulated annealing to adjust the values in each interval.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and positive review. \nThe reviewer rightfully mentions that only final results for the best heuristic are being presented,  but we refer to our Appendix C and comments to Reviewer 4 where we provide more details on computational considerations for adopting our suggested methods that will be added to our final version if accepted.", "claims_and_evidence": "The authors claim that their modification of the known recalibration method FIR, despite looking relatively innocent, provides a significant adventage and results in noticably better calibration than state of the art alternatives. They compared several post-hoc calibration methods on six benchmarks, with varying number of classes. For each pair of recalibration methods they showed on a heat-map percentage of the times one method achieved a better score than the other. The newly proposed NA-FIR and SCIR seems to consistently outperform other six calibration methods.", "methods_and_evaluation_criteria": "The author has used quite a wide set of benchmark datasets, and compared a wide range of different recalibration algorithms. They also attempted to use various heuristic to solve the specific non-convex optimization problem they used in the definition of NA-FIR~---they only present the final results for the best heuristic, but it is valuable that they mention other attempts they tried.", "theoretical_claims": "There are no theoretical claims in this paper~---they provide experimental evidence for the validity of their approach.", "experimental_designs_or_analyses": "Experimental design seems sound, and --- importantly, it is using a wide range of datasets coming from different sources. Specific details of all experiments, and additional metrics of calibration errors can be found in the extensive supplementary material. I did not attempt to replicate their experiments.", "relation_to_broader_scientific_literature": "The problems of multi-class recalibration, and in general of understanding various aspects multi-class calibration are important areas with still a large room for further discoveries. The authors propose an improvement over known methods for recalibration, while applying the isotonic regression --- preserving the monotonicity of the post-processing function $g$.", "essential_references_not_discussed": "I am not aware of the essential references that are missing.", "other_strengths_and_weaknesses": "The experimental setup in this paper is very well prepared, with a wide range of data sets, wide range of other recalibration algorithms used as comparisons, and few calibration metrics to compare those algorithms. Moreover, the supplementary material providing very specific details of how the experiments were preformed, making it quite easy to attempt potential replication.", "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": "", "extra_scores": {}}, {"review_id": "C7VY6NU5MB", "reviewer": "Reviewer_6BKQ", "summary": "The paper addresses the critical challenge of multi-class calibration in supervised learning.  \nWhile isotonic regression has proven effective for binary calibration problems, its extension to multi-class settings through one-vs-rest (OvR) calibration has historically underperformed compared to parametric methods like Temperature Scaling.   \nThe authors identify a key limitation: traditional approaches do not inherently account for probability normalization during optimization.\n\nThe primary contributions are two novel isotonic regression techniques for multi-class calibration:\n1.    Normalization-Aware Flattened Isotonic Regression (NA-FIR): This method explicitly incorporates normalization into the optimization process, modifying the standard isotonic regression approach.\n 2.   Cumulative Bivariate Isotonic Regression (SCIR): Rather than treating each class as an independent binary task, this approach redefines the problem by addressing cumulative sub-problems.\n\nThe authors demonstrate that these normalization-aware techniques consistently improve calibration performance across diverse datasets and model architectures, asserting that their approach represents a state-of-the-art non-parametric alternative in scenarios where parametric assumptions may be limiting.   \nThe paper presents empirical evaluations on text and image classification datasets, demonstrating that the proposed approach improves negative log-likelihood (NLL) and expected calibration error (ECE) metrics.\n\n## update after rebuttal\nI keep my score - the empirical results are enough IMHO, even though *some* of them are on rather small datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and positive review. \nAs far as theoretical claims we would like to also refer the reviewer to Appendix 4 where we provide a theoretically valid motivation for our isotonic approach.", "claims_and_evidence": "The main claim of the paper is that:   \n>  NA-FIR and SCIR (the proposed methods) improve multi-class calibration by inherently accounting for probability normalization.  \n\nTo which the autors provide the following empirical evidence\n* Figure 1 visually supports this claim by showing improved calibration with NA-FIR and SCIR. \n* Section 5 that show improvements in NLL and ECE, which are standard metrics for evaluating calibration. \n* The results are presented in Table 2, where the proposed methods generally achieve better average rankings compared to other calibration techniques. \n\nThe evidence provided includes empirical results from experiments on six benchmark datasets (CIFAR-10, CIFAR-100, Food-101, R52, NG20, and Yelp Review) using various modern deep neural network architectures and classical machine learning models.", "methods_and_evaluation_criteria": "NLL and ECE are two of the most accepted ways to measure calibration in machine learning.   \nThe authors also employ variations of ECE, such as class-wise ECE (cw-ECE), thresholded equal-mass binning ECE (TECE), and confidence-calibrated ECE (conf-ECE).    \nThe authors use traditional benchmark datasets from both image and text domains, and compare methods against several existing calibration techniques (TS, MS, VS, IR-OvR, FIR).", "theoretical_claims": "The paper includes a theoretical claim in *Proposition 4.1*, which states that the cumulative sorted problem defined in Eq. (5) can be solved in $O(m^2k^4)$ using *Algorithm 2*.  \n\nThe proof for the proposition, which I could not follow, is provided in Appendix A.", "experimental_designs_or_analyses": "The experimental section is following the accepted practice in the field, as I mention above.\n\nI would commend the authors for using cross-validation (line 867) which is sadly not a common practice (IMHO)", "relation_to_broader_scientific_literature": "The paper effectively situates itself within the broader calibration literature. \nThe authors acknowledge foundational works on calibration by Murphy (1973), Murphy & Winkler (1977), and DeGroot & Fienberg (1981), establishing historical context.\n\nMore recent developments are referenced, including Platt's (1999) logistic regression-based calibration for binary predictions and subsequent extensions by Kull et al. (2017). \nFor neural networks specifically, the authors discuss Guo et al.'s (2017) parametric methods: Matrix Scaling, Vector Scaling, and Temperature Scaling.\n\nIn the non-parametric domain, the paper builds upon Zadrozny & Elkan's (2002) work on decomposing multi-class problems into binary subproblems and more recent contributions by Patel et al. (2020) and Zhang et al. (2020) on Flattened Isotonic Regression.\n\nThe authors identify a gap in the literature where prior work reported state-of-the-art results for unnormalized predictions, which they argue conflicts with the fundamental goal of calibration: fostering trust in reported probabilities.", "essential_references_not_discussed": "I could not think of a major missing reference.", "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": "", "extra_scores": {}}, {"review_id": "CcIHbDq218", "reviewer": "Reviewer_Rvdp", "summary": "This paper addresses  extending isotonic regression from binary calibration to multi-class calibration. It proposes isotonic normalization-aware techniques for multi-class calibration. In particular, it introduces two techniques to account for probability normalization: (1) NA-FIR that incorporates normalization directly into the optimization process and (2) SCIR that models the problem as a cumulative bivariate isotonic regression. Experiments  are conducted on several text and image classification datasets across different model architectures, showing the proposed method can improve  log-likelihood (NLL) and expected calibration error (ECE) metrics.\n\n\n\n## update after rebuttal:\nThe experiments on ImageNet-1k During rebuttal indeed drive me towards positive, but not upon an accept. Even though my concerns on time cost still holds, the explanation (in particular the second round) indeed drive me to positive. I decide to raise my score from 2 (weak reject) to 3 (weak accept).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. \n\nAs you rightfully pointed out, validating our methods on larger datasets such as ImageNet-1K is important for demonstrating scalability and generality. In the last few days we have made a concentrated effort and conducted additional experiments on ImageNet-1K using [eight pre-trained models](https://github.com/huggingface/pytorch-image-models/blob/main/results/results-imagenet.csv), using the 50k validation for both calibration (25%) and test (75%).\n\nWe show here preliminary results for the calibration measures used in the paper. The results are in the same format as Table 2 in the paper, and show average rank and % best. As can be seen, for all measures except cw-ECE one of our methods NA-FIR and SCIR is best, in most cases by far. cw-ECE is not really a relevant measure with 1000 classes (see paper for definition of cw-ECE), as a vector of all zeros is likely to be best.\n\n| Metric            | NA-FIR      | SCIR        | FIR         | IR OvR      | TS          | VS          | MS          | Uncalibrated |\n|------------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|---------------|\n| **Cross Entropy (NLL)** | **1.0 (100%)**  | 4.9 (0%)    | 2.0 (0%)    | 8.0 (0%)    | 3.4 (0%)    | 5.1 (0%)    | 5.9 (0%)    | 5.8 (0%)      |\n| **Brier Score (BS)**   | **1.2 (75%)**   | 3.4 (0%)    | 2.4 (0%)    | 6.5 (0%)    | 4.1 (12%)   | 5.8 (12%)   | 6.6 (0%)    | 6.0 (0%)      |\n| **conf-ECE**| **1.4 (75%)**   | 2.0 (25%)   | 3.0 (0%)    | 5.5 (0%)    | 4.0 (0%)    | 6.1 (0%)    | 7.4 (0%)    | 6.6 (0%)      |\n| **cw-ECE**          | 3.6 (0%)    | 6.1 (0%)    | 3.1 (12%)   | 4.4 (0%)    | **2.0 (50%)**   | 4.1 (25%)   | 5.4 (12%)   | 7.2 (0%)      |\n| **TECE**          | 2.9 (12%)   | **2.1 (50%)**   | 2.5 (0%)    | 8.0 (0%)    | 5.1 (0%)    | 6.4 (0%)    | 6.1 (0%)    | 2.9 (38%)     |\n\n\nRegarding runtime, we acknowledge that our methods are **less efficient** than TS or FIR on large datasets as you justly were concerned. \nWhile both TS and FIR run in a few seconds, for the algorithms presented in the paper it takes a mean time of 120 minutes for SCIR and 16 minutes for NA-FIR with the suggested algorithm. \n\nWe would like to add additional context regarding these results:\n* SCIR has a theoretical worst case time complexity of $O(m^2k^4)$ (Appendix A), and though it scales better in practice, it remains resource-intensive for 𝑘=1000 classes. For example, fitting takes around 2 minutes for cifar100 (100 classes, 5k calibration samples - see Appendix C) and for imagenet-1k it takes around 120 minutes with 30 minutes std.\n* NA-FIR scales more efficiently even as k grows, since it fits a PAVA step first, significantly reducing the number of effective parameters. After applying memorization to only update bins deltas in NLL calculation, NA-FIR  for imagenet-1k (1000 classes) takes ~15 minute, in comparison to 5 minutes for food101 dataset (101 classes, 6.3k calibration samples). We also discuss several ways to optimize NA-FIR in the supplemental material which can result in significant time difference (using this approach results in about a minute fitting time, but results were less stable).\n\nWhile we recognize that TS remains the most efficient method and is a strong baseline, our approach offers stronger calibration under normalization constraints not addressed by previous nonparametric methods. We provide both theoretical grounding (see Section D and our response to Reviewer 1) and empirical evidence including on large scale dataset as Imagent-1k to support this claim.\n\nFinally, in many applications, calibration sets are limited (see for example [1]), and compute overhead from calibration is minor compared to model training costs. If accepted we will include wall-clock details in the final version for transparency, thus by offering complexity analysis and strong empirical gains, we allow practitioners to weigh the pros and cons depending on their application and compute resources. We believe our methods have a place in the literature, as they offer flexible and effective alternative where calibration quality is prioritized.\n\nWe also appreciate the note on typos and will revise accordingly.  Regarding the use of $\\preceq$, we follow convention where it denotes partial ordering.\n\n[1] Patel et al, Multi-class uncertainty calibration via mutual information maximization-based binning, ICLR 2021", "claims_and_evidence": "The main claim of this paper is from the empirical perspective tha \"our proposed methods consistently improve both negative log-likelihood (NLL) and calibration error across diverse datasets, achieving SOTA results and reaffirming the effectiveness of IR for calibration\". While this claim is indeed supported by the experiments of the paper, I have concerns on the experiments, relating to the scalability, see the details of the comments on experimental designs.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria is overall make sense. But it misses the experiments in comparing the efficiency of the proposed methods and the benchmark is overall small-scale (see comments on experimental designs)", "theoretical_claims": "I do not think this paper provides theoretical contributions. The method is based on previous work with some intuition, and the main technical contributions are the proposed algorithms.", "experimental_designs_or_analyses": "Even thought the experiments support the claims, I still have concerns on the significance. My concerns are follows:\n\n(1) The datasets used in this paper is almost small-scale, I think this paper should conduct experiments on more larger datasets, e.g., at least conduct experiments on ImageNet-1000 datasets (there are many pre-trained models for Imagenet-1000, I do not think the computing power is the problem).  \n\n(2) This paper should conduct experiments to compare the computation cost, e.g., wall clock time, especially on the Imagenet-1000 datasets. It is important show its scalability in practice. I think TS is a very simple (efficient) and effective method for calibration (even though I am not an experts in calibration),  How does the proposed method compared to TS in efficiency?", "relation_to_broader_scientific_literature": "This paper provides clear routing how this paper builds on. I acknowledge it. However, it seems incremental overall, from the perspective of methods.", "essential_references_not_discussed": "I believe this paper provides essential references, even though I am not familiar to the references about calibration.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "(1) Line 124, missing \".\"\n\n(2) eqn 2, what is the meaning of \"$\\preceq$\" ?\n\n(3) Line 205 (right) , missing \",\" before \"we justify....\"", "questions_for_authors": "How does the proposed method compared to TS in efficiency? especially with the increase on the size of classes and data samples? (better provide the results on ImageNet-1000)", "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": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: The paper proposes two normalization‑aware isotonic calibration methods for the multi‑class setting and supplies broad empirical evidence (since rebuttal including also ImageNet‑1K), that these techniques improve negative log‑likelihood and several calibration metrics over existing post‑hoc approaches. Two reviewers find the contribution sufficient for ICML and a third moved from weak reject to weak accept after seeing the large‑scale results, so the overall tilt of the reviews is positive. The fourth reviewer kept the score as weak reject but is now more neutral to its acceptance. 

I highlight three key points in the discussions. First, one reviewer still reports difficulty following the notation and the rationale for sharing a single isotonic function across classes, so the exposition must be tightened and definitions made explicit. Second, the authors provided wall‑clock times that confirm NA‑FIR and especially SCIR are much slower than Temperature Scaling, and one reviewer continues to question whether the accuracy gains justify this computational cost; thus, the final version should present these timings and discuss use‑case trade‑offs. Third, the motivation and statistical justification for the shared isotonic assumption need clearer explanation to remove the remaining doubts about consistency. The new ImageNet‑1K experiments addressed the dataset‑scale concern, and no reviewer raised further objections. Provided the authors commit to clarifying the presentation and to documenting runtime, I recommend acceptance.
Decision: Accept (poster)