# Taking a Step Back with KCal: Multi-Class Kernel-Based Calibration for Deep
Neural Networks

Zhen Lin
University of Illinois at Urbana-Champaign
Urbana, IL 61801
<EMAIL_ADDRESS>
Shubhendu Trivedi
<EMAIL_ADDRESS>
Jimeng Sun
University of Illinois at Urbana-Champaign
Urbana, IL 61801
<EMAIL_ADDRESS>

###### Abstract

Deep neural network (DNN) classifiers are often overconfident, producing
miscalibrated class probabilities. In high-risk applications like healthcare,
practitioners require fully calibrated probability predictions for decision-
making. That is, conditioned on the prediction vector, every class’
probability should be close to the predicted value. Most existing calibration
methods either lack theoretical guarantees for producing calibrated outputs,
reduce classification accuracy in the process, or only calibrate the predicted
class. This paper proposes a new Kernel-based calibration method called KCal.
Unlike existing calibration procedures, KCal does not operate directly on the
logits or softmax outputs of the DNN. Instead, KCal learns a metric space on
the penultimate-layer latent embedding and generates predictions using kernel
density estimates on a calibration set. We first analyze KCal theoretically,
showing that it enjoys a provable full calibration guarantee. Then, through
extensive experiments across a variety of datasets, we show that KCal
consistently outperforms baselines as measured by the calibration error and by
proper scoring rules like the Brier Score.

##  1 Introduction

The notable successes of Deep Neural Networks (DNNs) in complex classification
tasks, such as object detection (Ouyang & Wang, 2013), speech recognition
(Deng et al., 2013), and medical diagnosis (Qiao et al., 2020; Biswal et al.,
2017), have made them essential ingredients within various critical decision-
making pipelines. In addition to the classification accuracy, a classifier
should ideally also generate reliable uncertainty estimates represented in the
predicted probability vector. An influential study (Guo et al., 2017) reported
that modern DNNs are often overconfident or _miscalibrated_ , which could lead
to severe consequences in high-stakes applications such as healthcare (Jiang
et al., 2012).

Calibration is the process of closing the gap between the prediction and the
ground truth distribution given this prediction. For a $K$-class
classification problem, with covariates $X\in\mathcal{X}$ and the label
$Y\in\mathcal{Y}=[K]$, denote our classifier $\mathcal{X}\mapsto\Delta^{K-1}$
as $\hat{\mathbf{p}}=[\hat{p}_{1},\ldots,\hat{p}_{K}]$, where $\Delta^{K-1}$
is the ($K-1$)-simplex. Then,

######  Definition 1.

(Full Calibration (Kull et al., 2019; Vaicenavicius et al., 2019))
$\hat{\mathbf{p}}$ is fully-calibrated if $\forall k\in[K]$:

$\displaystyle\forall\mathbf{q}=[q_{1},\ldots,q_{K}]\in\Delta^{K-1},\mathbb{P}\\{Y=k|\hat{\mathbf{p}}(X)=\mathbf{q}\\}=q_{k}.$
(1)

It is worth noting that Def. (1) implies nothing about accuracy. In fact,
ignoring $X$ and simply predicting $\pi$, the class frequency vector, results
in a fully calibrated but inaccurate classifier. As a result, our goal is
always to improve calibration while maintaining accuracy. Another important
requirement is that $\hat{\mathbf{p}}\in\Delta^{K-1}$. Many binary calibration
methods such as Zadrozny & Elkan (2001; 2002) result in vectors that are not
interpretable as probabilities, and have to be normalized.

Many existing works only consider confidence calibration (Guo et al., 2017;
Zhang et al., 2020; Wenger et al., 2020; Ma & Blaschko, 2021), a much weaker
notion than that encapsulated by Def. (1) and only calibrates the predicted
class (Kull et al., 2019; Vaicenavicius et al., 2019).

######  Definition 2.

(Confidence Calibration) $\hat{\mathbf{p}}$ is confidence-calibrated if:

$\displaystyle\forall
q\in[0,1],\mathbb{P}\\{Y=\operatorname*{arg\,max}_{k}\hat{p}_{k}(X)|\max_{k}\hat{p}_{k}(X)=q\\}=q.$
(2)

Figure 1:  Reliability diagrams for confidence calibration (top) and Seizure
(bottom). The popular temperature scaling (right) only calibrates the
confidence, leaving Seizure poorly calibrated. See Figure 2 and the Appendix
for complete reliability diagrams.

However, confidence calibration is far from sufficient. Doctors need to
perform differential diagnoses on a patient, where multiple possible diseases
should be considered with proper probabilities for all of them, not only the
most likely diagnosis. Figure 1 shows an example where the confidence is
calibrated, but prediction for important classes like Seizure is poorly
calibrated. A classifier can be confidence-calibrated but not useful for
differential diagnoses if the probability assignments for most diseases are
inaccurate.

Recent research effort has started to focus on full calibration, for example,
in Vaicenavicius et al. (2019); Kull et al. (2019); Widmann et al. (2019);
Karandikar et al. (2021); Mukhoti et al. (2020); Patel et al. (2021). We
approach this problem by leveraging the latent neural network embedding in a
nonparametric manner. Nonparametric methods such as histogram binning (HB)
(Zadrozny & Elkan, 2001) and isotonic regression (IR) (Zadrozny & Elkan,
2002), are natural for calibration and have become popular. Gupta & Ramdas
(2021) recently showed a calibration guarantee for HB. However, HB usually
leads to noticeable drops in accuracy (Patel et al., 2021), and IR is prone to
overfitting (Niculescu-Mizil & Caruana, 2005). Unlike existing methods, we
take one step back and train a new low-dimensional metric space on the
penultimate-layer embeddings of DNNs. Then, we use a kernel density
estimation-based classifier to predict the class probabilities directly. We
refer to our Kernel-based Calibration method as KCal. Unlike most calibration
methods, KCal provides high probability error bounds for full calibration
under standard assumptions. Empirically, we show that with little overhead,
KCal outperforms all existing calibration methods in terms of calibration
quality, across multiple tasks and DNN architectures, while maintaining and
sometimes improving the classification accuracy.

Summary of Contributions:

  * •

We propose KCal, a principled method that calibrates DNNs using kernel density
estimation on the latent embeddings.

  * •

We present an efficient pipeline to train KCal, including a dimension-reducing
projection and a stratified sampling method to facilitate efficient training.

  * •

We provide finite sample bounds for the calibration error of KCal-calibrated
output under standard assumptions. To the best of our knowledge, this is the
first method with a full calibration guarantee.

  * •

In extensive experiments on multiple datasets and state-of-the-art models, we
found that KCal outperforms existing calibration methods in commonly used
evaluation metrics. We also show that KCal provides more reliable predictions
for important classes in the healthcare datasets.

The code to replicate all our experimental results is submitted along with
supplementary materials.

##  2 Related Work

Research on calibration originated in the context of meteorology and weather
forecasting (see Murphy & Winkler (1984) for an overview) and has a long
history, much older than the field of machine learning (Brier, 1950; Murphy &
Winkler, 1977; Degroot & Fienberg, 1983). We refer to Filho et al. (2021) for
a holistic overview and focus below on methods proposed in the context of
modern neural networks. Based on underlying methodological similarities, we
cluster them into distinct categories.

Scaling: A popular family of calibration methods is based on scaling, in which
a mapping is learned from the predicted logits to probability vectors.
Confidence calibration scaling methods include temperature scaling (TS) (Guo
et al., 2017) and its antecedent Platt scaling (Platt, 1999), an ensemble of
TS (Zhang et al., 2020), Gaussian-Process scaling (Wenger et al., 2020),
combining a base calibrator (TS) with a rejection option (Ma & Blaschko,
2021). Matrix scaling with regularization was also used to perform full
calibration (Kull et al., 2019). While some scaling-based methods can be data-
efficient, there are no known theoretical guarantees for them to the best of
our knowledge.

Binning: Another cluster of solutions relies on binning and its variants, and
includes uniform-mass binning (Zadrozny & Elkan, 2001), scaling before binning
(Kumar et al., 2019), and mutual-information-maximization-based binning (Patel
et al., 2021). Isotonic regression (Zadrozny & Elkan, 2002) is also often
interpreted as binning. Uniform-mass binning (Zadrozny & Elkan, 2001) has a
distribution-free finite sample calibration guarantee (Gupta & Ramdas, 2021)
and asymptotic convergent ECE estimation (Vaicenavicius et al., 2019).
However, in practice, binning tends to decrease accuracy (Patel et al., 2021;
Guo et al., 2017). Binning can also be considered a member of the broader
nonparametric calibration family of methods. Such methods also include
Gaussian Process Calibration (Wenger et al., 2020), which however also only
considers confidence calibration.

Loss regularization: There are also attempts to train a calibrated DNN to
begin with. Such methods typically add a suitable regularizer to the loss
function (Karandikar et al., 2021; Mukhoti et al., 2020; Kumar et al., 2018),
which can sometimes result in expensive optimization and reduction in
accuracy.

Use of Kernels: Although not directly used for calibration, kernels have also
been used for uncertainty quantification for deep learning classification. In
classification with rejection, the k-nearest-neighbors algorithm (kNN),
closely related to kernel-based methods, has been used to provide a
“confidence measure” which is used to make a binary decision (i.e., whether to
reject or to predict) (Papernot & McDaniel, 2018; Jiang et al., 2018).
Recently, continuous kernels have also been used to measure calibration
quality or used as regularization during training (Widmann et al., 2019; Kumar
et al., 2018). Zhang et al. (2020) introduced a kernel density estimation
(KDE) proxy estimator for estimating ECE. However, it uses a un-optimized
kernel over $\Delta^{K-1}$, and shows the KDE-ECE estimator (but not the
calibration map) is consistent. To the best of our knowledge, use of trained
KDE to calibrate predictions hasn’t been proposed before. Further, we also
provide a bound on the calibration error.

##  3 KCal: Kernel-based Calibration

In this section, we formally introduce KCal, study its calibration properties
theoretically, and present crucial implementation details and comparisons with
other methods. Specifically, in Section 3.1, we discuss how to construct
(automatically) calibrated predictions for test data using a calibration set
$\mathcal{S}_{\text{cal}}$. Doing so requires a well-trained kernel and metric
space, and we describe a procedure to train such a kernel in Section 3.2. In
Section 3.3, we show that an appropriate shrinkage rate of the bandwidth
ensures that the KCal prediction is automatically calibrated. Sections 3.4
provides implementation details. Finally, in Section 3.5, we compare and
contrast KCal with existing methods.

###  3.1 Classification with Kernel Density Estimation

Following the calibration literature, we first require a holdout calibration
set $\mathcal{S}_{\text{cal}}=\\{X_{i},Y_{i}\\}_{i=1}^{N}$. In KCal, we fix a
kernel function $\hat{\phi}$ which is learned (the learning procedure is
described in Section 3.2). For a new datum $X_{N+1}$, the class probability
$\hat{\mathbf{p}}_{k}(X_{N+1})$ takes the following form:

$\displaystyle\hat{\mathbf{p}}_{k}(X_{N+1};\hat{\phi},\mathcal{S}_{\text{cal}})=\frac{\sum_{(x,y)\in\mathcal{S}_{\text{cal}}^{k}}\hat{\phi}(x,X_{N+1})}{\sum_{(x,y)\in\mathcal{S}_{\text{cal}}}\hat{\phi}(x,X_{N+1})},$
(3)

where
$\mathcal{S}_{\text{cal}}^{k}\vcentcolon=\\{(x,y)\in\mathcal{S}_{\text{cal}}|y=k\\}$.
The notation
$\hat{\mathbf{p}}_{k}(X_{N+1};\hat{\phi},\mathcal{S}_{\text{cal}})$ emphasizes
the dependence on $\hat{\phi}$ and $\mathcal{S}_{\text{cal}}$. However, we
will use $\hat{\mathbf{p}}_{k}(X_{N+1})$ when the dependence is clear from
context.

Remarks: What we have described is essentially the classical nonparametric
procedure of applying kernel density estimation for classification. For a
moment, suppose we know the true density function $f_{k}$ of $\mathcal{P}_{k}$
(the distribution of all the data in class $k$), and the proportion of class
$k$, denoted $\pi_{k}$ (such that $\sum_{k\in[K]}\pi_{k}=1$). Then, for any
particular $x_{0}$, using the Bayes rule we get:

$\displaystyle\mathbb{P}\\{Y=k|X=x_{0}\\}$
$\displaystyle=\frac{f_{k}(x_{0})\pi_{k}}{\sum_{{k^{\prime}}\in[K]}f_{k^{\prime}}(x_{0})\pi_{k^{\prime}}}.$
(4)

Now, replacing $f_{k}$ with the kernel density estimate
$\hat{f}_{k}(x_{0})\vcentcolon=(\sum_{(x,y)\in\mathcal{S}_{\text{cal}}^{k}}\hat{\phi}_{b}(x,x_{0}))/|\mathcal{S}_{\text{cal}}^{k}|$,
and the class proportion $\pi_{k}$ with
$\displaystyle\hat{\pi}_{k}\vcentcolon=|\mathcal{S}_{\text{cal}}^{k}|/|\mathcal{S}_{\text{cal}}|$
we get back Eq. (3).

###  3.2 Training

Employing an appropriate kernel function $\hat{\phi}$ is crucial for good
performance under the kernel density framework. The kernel in turn has a
critical reliance on the choice of the underlying metric. To obtain good
performance using deep learning learning models, we train a metric space on
top of the penultimate layer embeddings.

To begin, we assume a deep neural network is already trained on
$\mathcal{S}_{\text{train}}=\\{X^{train}_{i},Y^{train}_{i}\\}_{i=1}^{M}$. We
place no limitations on the form of loss function, optimizer, or the model
architecture. However, we do require the neural net to compute an embedding
before a final prediction layer, which is always the case in modern
classification models. We denote the embedding function from
$\mathcal{X}\mapsto\mathbb{R}^{h}$ as $\mathbf{f}$.

Given a base “mother kernel” function $\phi$, such as the Radial Basis
Function (RBF) kernel, we denote the kernel with bandwidth $b$ as
$\phi_{b}\vcentcolon=\frac{1}{b}\phi(\frac{\cdot}{b})$. We parameterize the
learnable kernel as:

$\displaystyle\hat{\phi}(x,x^{\prime})\vcentcolon=\hat{\phi}_{\mathbf{\Pi},\mathbf{f},b}(x,x^{\prime})\vcentcolon=\phi_{b}(\mathbf{\Pi}(\mathbf{f}(x))-\mathbf{\Pi}(\mathbf{f}(x^{\prime}))).$
(5)

where $\mathbf{\Pi}:\mathbb{R}^{h}\mapsto\mathbb{R}^{d}$ is a dimension-
reducing projection parameterized by a shallow MLP (Section 3.4). Since the
inference time is linear in $d$, letting $d<h$ also affords computational
benefits.

Given that the embedding function $\mathbf{f}(x)$ from the neural network is
fixed, the only learnable entities are $b$ and $\mathbf{\Pi}$. In the training
phase, we fix $b=1$, and train $\mathbf{\Pi}$ using (stochastic) gradient
descent and log-loss. The specific value of $b$ does not matter since it can
be folded into $\mathbf{\Pi}$. Let us denote
$\mathcal{S}_{\text{train}}^{k}=\\{(x,y)\in\mathcal{S}_{\text{train}}:y=k\\}$.
In each iteration, we randomly sample two batches of data from
$\mathcal{S}_{\text{train}}$ \- the prediction data, denoted as
$\mathcal{S}_{\text{train}}^{B}$, to evaluate $\mathbf{\Pi}$, and “background”
data for each $k$, denoted as $\mathcal{B}^{k}$, from
$\mathcal{S}_{\text{train}}^{k}\setminus\mathcal{S}_{\text{train}}^{B}$ to
construct the KDE classifier. Then, the prediction for any $x_{j}$ is given by

$\displaystyle\hat{\mathbf{p}}_{k}(x_{j};\hat{\phi},\mathcal{S}_{\text{train}}\setminus\mathcal{S}_{\text{train}}^{B})\vcentcolon=\frac{\sum_{(x,y)\in\mathcal{B}^{k}}\frac{|\mathcal{S}_{\text{train}}^{k}\setminus\mathcal{S}_{\text{train}}^{B}|}{|\mathcal{B}^{k}|}\hat{\phi}(x,x_{j})}{\sum_{k^{\prime},(x,y)\in\mathcal{B}^{k^{\prime}}}\frac{|\mathcal{S}_{\text{train}}^{k^{\prime}}\setminus\mathcal{S}_{\text{train}}^{B}|}{|\mathcal{B}^{k^{\prime}}|}\hat{\phi}(x,x_{j})}\vspace{-1mm}$
(6)

where $\hat{\phi}$ is shorthand for $\hat{\phi}_{\mathbf{\Pi},\mathbf{f},b=1}$
defined in Eq. (5). The log-loss is given formally by

$\displaystyle L$
$\displaystyle=-\frac{1}{B}\sum_{(x,y)\in\mathcal{S}_{\text{train}}^{B}}\log\hat{\mathbf{p}}_{y}(x;\hat{\phi}_{\mathbf{\Pi},\mathbf{f},1},\mathcal{S}_{\text{train}}\setminus\mathcal{S}_{\text{train}}^{B}).$
(7)

Finally, we pick a $b=b^{*}$ on the calibration set $\mathcal{S}_{\text{cal}}$
using cross-validation. This is because $b$ should be chosen contingent on the
sample size (Section 3.3). Choosing $b$ can be done efficiently (Section 3.4).
Algorithm 1 summarizes the steps we explicated upon so far.

###  3.3 Theoretical Analysis: Calibration Comes Free

In the previous section, we have only described a procedure to improve the
prediction accuracy for $\hat{\mathbf{p}}$ on $\mathcal{S}_{\text{train}}$.
This section will show that calibration comes free with the $\hat{\mathbf{p}}$
obtained using Algorithm 1. In particular, we show that as the sample-size for
each class in $\mathcal{S}_{\text{cal}}$ increases, $\hat{\mathbf{p}}$
converges to the true frequency vector of $Y$ given the input. In interest of
smoother presentation, we only state the relevant claims in what follows.
Detailed proofs are presented in the Appendix.

To begin, we make a few standard assumptions, such as in Chacón & Duong
(2018), including:

  * •

($\forall k$) The density on the embedded space,
$\mathbf{\Pi}(\mathbf{f}(\mathcal{X}|Y=k))$, denoted as
$f_{\mathbf{\Pi}\circ\mathbf{f},k}$, is square integrable and twice
differentiable, with all second order partials bounded, continuous, and square
integrable.

  * •

$\phi$ is spherically symmetric, with a finite second moment.

Lemma 3.1 and 3.2 focus on an arbitrary class $k$ and ignore the subscript $k$
to the density $f$ for readability. We denote the size
$|\mathcal{S}_{\text{cal}}^{k}|=m$. Intuitively, due to the bias-variance
trade-off, a suitable bandwidth $b$ will depend on $m$: A small $b$ reduces
bias, but with the finite $m$, a smaller $b$ also leads to increased variance.
Thus, $b$ should go to 0 “slowly”, which is formally stated below:

######  Lemma 3.1.

For almost all $x$, if $b^{d}m\to\infty$ and $b\to 0$ as $m\to\infty$, then we
have

$\displaystyle\|\hat{f}_{\mathbf{\Pi}\circ\mathbf{f},k}(x)-f_{\mathbf{\Pi}\circ\mathbf{f},k}(x)\|_{2}\overset{P}{\to}0\text{
as }m\to\infty.$ (8)

Here $\hat{f}_{\mathbf{\Pi}\circ\mathbf{f},k}$ is the estimated
$f_{\mathbf{\Pi}\circ\mathbf{f},k}$ using $\mathcal{S}_{\text{cal}}$. Recall
that $d$ is the dimension of $\mathbf{\Pi}(\mathbf{f}(\mathcal{X}))$. We will
call such a bandwidth $b$ admissible, and we sometimes write $b(m)$ to
emphasize the dependence on $m$. The following lemma gives the optimal
admissible bandwidth:

######  Lemma 3.2.

The optimal bandwidth is $b=\Theta(m^{-\frac{1}{d+4}})$, which leads to the
fastest decreasing MSE (i.e.
$\mathbb{E}[\|\hat{f}_{\mathbf{\Pi}\circ\mathbf{f},k}(x)-f_{\mathbf{\Pi}\circ\mathbf{f},k}(x)\|_{2}]$)
of $O(m^{-\frac{4}{d+4}})$.

Now we are in a position to present the main theoretical results. In the
following, $m$ denotes the rarest class’s count
($m\vcentcolon=\min_{k}\\{|\mathcal{S}_{\text{cal}}^{k}|\\}$. Theorem 3.3
provides a bound between $\hat{\mathbf{p}}$ and the true conditional
probability vector on the embedded space
$\mathbf{p}(\mathbf{\Pi}(\mathbf{f}(X)))$:

######  Theorem 3.3.

Fixing $x$ such that the density of $\mathbf{\Pi}(\mathbf{f}(x))$ is positive,
with $b(m)=\Theta(m^{-\frac{1}{d+4}})$, for any $\lambda\in(0,2)$:

$\displaystyle\mathbb{P}\\{|\hat{\mathbf{p}}_{k}(x)-\mathbf{p}_{k}(\mathbf{\Pi}(\mathbf{f}(x)))|$
$\displaystyle>(3K+1)Cm^{\frac{-\lambda}{d+4}}\\}\leq
Ke^{-Bm^{\frac{4-2\lambda}{d+4}}}$ (9) $\displaystyle\text{ where
}\mathbf{p}_{k}(\mathbf{\Pi}(\mathbf{f}(x)))$
$\displaystyle\vcentcolon=\mathbb{P}\\{Y=k|\mathbf{\Pi}(\mathbf{f}(X))=\mathbf{\Pi}(\mathbf{f}(x))\\}$
(10)

for some constant $B$ and $C$. As a corollary,
$\hat{\mathbf{p}}(x)\overset{\text{almost
surely}}{\to}\mathbf{p}(\mathbf{\Pi}(\mathbf{f}(x)))\text{ as }m\to\infty$.

Next, we bound the full calibration error with additional standard
assumptions. More specifically, we use and build upon the main uniform
convergence result for classical KDE presented in Jiang (2017), to obtain
Theorem 3.4:

######  Theorem 3.4.

Assume $f_{\mathbf{\Pi}\circ\mathbf{f},k}$ is $\alpha$-Hölder continuous and
bounded away from $0$ for any $k$. For an admissible $b(m)$ with shrinkage
rate $\Theta((\frac{\log{m}}{m})^{\frac{1}{d+2\alpha}})$, for some constants
$B$ and $C$ we have:

$\displaystyle\mathbb{P}\\{\sup_{X,k}|\hat{\mathbf{p}}_{k}(X)-\mathbb{P}\\{Y=k|\hat{\mathbf{p}}(X)\\}|>(3K+1)C(\frac{\log{m}}{m})^{\frac{\alpha}{d+2\alpha}}\\}\leq
K(m^{-1}+m^{-B\frac{2\alpha}{d+2\alpha}m^{\frac{d}{d+2\alpha}}}).$ (11)

Algorithm 1 Overview of KCal

Input:
$\mathcal{S}_{\text{train}}$: $\\{(X^{train}_{i},Y^{train}_{i})\\}_{i=1}^{M}$
used to train the NN
$\mathcal{S}_{\text{cal}}$: $\\{(X_{i},Y_{i})\\}_{i=1}^{N}$ calibration set
$\mathbf{f}:$ Embedding function $\mathcal{X}\to\mathbb{R}^{h}$ (trained NN)
$X_{N+1}$: Unseen datum for prediction
Training (of the projection $\mathbf{\Pi}$):

Denote
$\mathcal{S}_{\text{train}}^{k}\vcentcolon=\\{(x,y)\in\mathcal{S}_{\text{train}}|y=k\\}$.

Denote $\phi_{b}$ as a base kernel function (e.g. RBF) with bandwidth $b$.

repeat

Sample $\mathcal{S}_{\text{train}}^{B}=\\{(x_{j},y_{j})\\}_{j=1}^{B}$ from
$\mathcal{S}_{\text{train}}$.

Compute $\hat{\mathbf{p}}(x_{j})$ via Eq. (6).

Loss
$l\leftarrow\frac{1}{B}\sum_{j=1}^{B}LogLoss(\hat{\mathbf{p}}(x_{j}),y_{j})$.

Update $\mathbf{\Pi}$ with (stochastic) gradient descent.

until the loss $l$ does not improve.

Set $\hat{\phi}_{b}\leftarrow\hat{\phi}_{\mathbf{\Pi},\mathbf{f},b}$ for
inference.

Inference:

Denote
$\mathcal{S}_{\text{cal}}^{k}\vcentcolon=\\{(x,y)\in\mathcal{S}_{\text{cal}}|y=k\\}$.

Tune $b^{*}$ on $\mathcal{S}_{\text{cal}}$ by minimizing log loss.

$\hat{\mathbf{p}}_{k}(X_{N+1})\leftarrow\frac{\sum_{(x,y)\in\mathcal{S}_{\text{cal}}^{k}}\hat{\phi}_{b^{*}}(x,X_{N+1})}{\sum_{(x,y)\in\mathcal{S}_{\text{cal}}}\hat{\phi}_{b^{*}}(x,X_{N+1})}$.

We now proceed to present details pertaining to the efficient implementation
of KCal.

###  3.4 Implementation Techniques

Efficient Training: As might be immediately apparent, utilizing algorithm 1
for prediction using full
$\mathcal{S}_{\text{train}}\setminus\mathcal{S}_{\text{train}}^{B}$ can be an
expensive exercise. In order to afford a training speedup, we consider a
random subset from
$\mathcal{S}_{\text{train}}\setminus\mathcal{S}_{\text{train}}^{B}$ using a
modified stratified sampling. Specifically, we take $m$ random samples from
each $\mathcal{S}_{\text{train}}^{k}$, denoted as
$\mathcal{S}_{\text{train}}^{k,m}$, and replace the right-hand side of Eq. 6
with:

$\displaystyle\vspace{-5mm}\frac{\sum_{(x,y)\in\mathcal{S}_{\text{train}}^{k,m}}\frac{|\mathcal{S}_{\text{train}}^{k}|}{m}\hat{\phi}(x,x_{0})}{\sum_{k^{\prime}\in[K],(x,y)\in\mathcal{S}_{\text{train}}^{k^{\prime},m}}\frac{|\mathcal{S}_{\text{train}}^{k^{\prime}}|}{m}\hat{\phi}(x,x_{0})}.$
(12)

The re-scaling term $\frac{|\mathcal{S}_{\text{train}}^{k}|}{m}$ is crucial to
get an unbiased estimate of $\hat{f}_{k}\hat{\pi}_{k}$. The stratification
employed makes the training more stable, while also reducing the estimation
variance for rarer classes (more details in Appendix B). The overall
complexity is now $O(KmdhB)$ per batch. In all experiments, we used $m=20$ and
$B=64$.

Form of $\mathbf{\Pi}$: While there is considerable freedom in choosing a
suitable form for $\mathbf{\Pi}$, we parameterize $\mathbf{\Pi}$ with a two
layer MLP with a skip connection. Consequently, $\mathbf{\Pi}$ can reduce to
linear projection when sufficient, and be more expressive when necessary. We
also experimented with using only a linear projection, the results for which
are included in the appendix. We fix the output dimension to
$d=\min\\{dim(\mathbf{f}),32\\}$, except for ImageNet ($d=128$).

Bandwidth Selection: Finally, to find the optimal bandwidth using
$\mathcal{S}_{\text{cal}}$, we use Golden-Section search (Kiefer, 1953) to
find the log-loss-minimizing $b^{*}$. This takes $O(\log{\frac{ub-lb}{tol}})$
steps where $[lb,ub]$ is the search space, and $tol$ is the tolerance.
Essentially, we assume that the loss is a convex function with respect to $b$,
permitting an efficient search (see Appendix H, which presents empirical
evidence that the convexity assumption is valid across datasets).

###  3.5 Comparisons with Existing Calibration Methods

Most existing calibration methods discussed in Section 2 and KCal all utilize
a holdout calibration set. However, unlike KCal, existing works usually fix
the last neural network layer. KCal, on the other hand, “takes a step back”,
and replaces the last prediction layer with a kernel density estimation based
classifier. Since the DNN $\mathbf{f}$ is fixed regardless of whether we use
the original last layer or not, we are really comparing a KDE classifier
(KCal) with linear models trained in various ways, after mapping all the data
with $\mathbf{f}$. Note that this characterization is true for most existing
methods, with a few exceptions (e.g., those summarized under “loss
regularization” in Section 2).

Employing a KDE classifier affords some clear advantages such as a
straightforward convergence guarantee and some interpretability111That is, one
could understand how the prediction is made by examining similar samples..
Furthermore, KCal can also be improved in an online fashion, a benefit
especially desirable in certain high-stakes applications such as in
healthcare. For example, a hospital can calibrate a trained model prior to
deployment using its own patient data (which is usually not available to train
the original model) as it becomes available.

Another important advantage of KCal is concerning normalization. In fact,
simultaneously calibrating all classes while satisfying the constraint that
$\hat{\mathbf{p}}\in\Delta^{K-1}$ is a distinguishing challenge for multi-
class calibration. Many calibration methods perform one-vs-rest calibration
for each class, and require a separate normalization step at test time
(Zadrozny & Elkan, 2001; 2002; Patel et al., 2021; Gupta et al., 2021). This
creates a gap between training and testing and could lead to drastic drop in
performance (Section 4). On the other hand, KCal automatically satisfies
$\hat{\mathbf{p}}\in\Delta^{K-1}$, and the normalization is consistent during
training and testing.

A disadvantage of KCal is the need to remember the
$\mathbf{\Pi}(\mathbf{f}(\mathcal{S}_{\text{cal}}))$ used to generate the KDE
prediction. This is however mitigated to a large extent by the dimension
reduction step, which already reduces the computational overhead
significantly222Experiments about the effect of $d$ on performance and
overhead are provided in the Appendix.. For example, in one of our experiments
on CIFAR-100, there are 160K (5K images, $d=32$) scalars to remember, which is
only 0.2% of the parameters (85M+) of the original DNN (ViT-base-patch16).
Moreover, KDE inference is trivial to parallelize on GPUs. There is also a
rich, under-explored, literature to further speed up the inference. Examples
include, KDE merging (Sodkomkham et al., 2016), Dual-Tree (Gray & Moore,
2003), and Kernel Herding (Chen et al., 2010). These methods can easily be
used in conjunction with KCal.

##  4 Experiments

###  4.1 Data and Neural Networks

We utilize two sets of data: computer vision benchmarks on which previous
calibration methods were tested, and health monitoring datasets where full
calibration is crucial for diagnostic applications. Table 1 summarizes the
datasets and their splits.

Table 1:  Dataset summary: Splits and number of classes ($K$).

Dataset | IIIC | IIIC(pat) | ISRUC | ISRUC(pat) | PN2017 | C10 | C100 | SVHN | ImageNet
---|---|---|---|---|---|---|---|---|---
Train | 103,818 | 1,936 | 61,841 | 69 | 15,087 | 45,000, | 45,000 | 65,931 | 1,281,167
Calibration | 1,787 | 77 | 1,372 | 6 | 253 | 5,000 | 5,000 | 7,326 | 25,000
Test | 33,953 | 684 | 26,070 | 24 | 4,813 | 10,000 | 10,000 | 26,032 | 25,000
$K$ | 6 | 6 | 5 | 5 | 4 | 10 | 100 | 10 | 1,000

Benchmark data Following Kull et al. (2019), we use multiple image benchmark
datasets, including CIFAR-10, CIFAR-100, and SVHN (Krizhevsky, 2009; Netzer et
al., 2011). We reserve 10% of the training data as the calibration set. We
fine-tune pretrained ViT (Dosovitskiy et al., 2021) and MLP-Mixer (Mixer)
(Tolstikhin et al., 2021) from the timm library (Wightman, 2019). We chose ViT
and Mixer because they are the state-of-the-art neural architectures in
computer vision, and accuracy should come before calibration quality. We also
included the ImageNet dataset (Deng et al., 2009) and use the pretrained
Inception ResNet V2 (Szegedy et al., 2017) following Patel et al. (2021).

Health monitoring data We also use three health monitoring datasets for
diagnostic tasks: IIIC (Jing et al., 2021), an ictal-interictal-injury-
continuum (IIIC) patterns classification dataset; ISRUC (Khalighi et al.,
2016), a sleep staging (classification) dataset using polysomnographic (PSG)
recordings; PN2017 (2017 PhysioNet Challenge) (Clifford et al., 2017;
Goldberger et al., 2000), a public electrocardiogram (ECG) dataset for rhythm
(particularly Atrial Fibrillation) classification. For the training set, we
follow Hong et al. (2019); Jing et al. (2021) for PN2017 and IIIC, and used 69
patients’ data for ISRUC. For the remaining data, 5% is used as the
calibration set and 95% for testing. We perform additional experiments after
splitting into training/calibration/test sets by patients for IIIC and
ISRUC333PN2017 did not provide patient IDs, so we cannot split by patient.,
marked as the “pat” version in tables. The calibration/test split is 20/80 in
“IIIC (pat)” and “ISRUC (pat)” because the number of patients is small. For
IIIC and ISRUC, we follow the standard practice and train a CNN (ResNet) on
the spectrogram (Biswal et al., 2017; Ruffini et al., 2019; Yuan et al.,
2019). For PN2017, we used a top-performing model from the 2017 PhysioNet
Challenge, MINA (Hong et al., 2019).

Table 2: Accuracy in % ($\uparrow$ means higher=better). Accuracy numbers
lower than the uncalibrated predictions are in dark red and the best are in
bold (both at p=0.01). KCal typically improves or maintains the accuracy.

Accuracy $\uparrow$ | UnCal | TS | DirCal | I-Max | Focal | Spline | IOP | GP | MMCE | KCal
---|---|---|---|---|---|---|---|---|---|---
IIIC (pat) | 58.68$\pm$1.42 | 58.68$\pm$1.42 | 63.17$\pm$1.42 | 57.20$\pm$1.32 | 54.35$\pm$1.64 | 58.51$\pm$1.32 | 58.68$\pm$1.42 | 58.68$\pm$1.42 | 58.05$\pm$1.37 | 61.67$\pm$2.22
IIIC | 58.53$\pm$0.06 | 58.53$\pm$0.06 | 63.80$\pm$0.10 | 56.96$\pm$0.14 | 54.41$\pm$0.05 | 58.36$\pm$0.20 | 58.53$\pm$0.06 | 58.52$\pm$0.06 | 58.06$\pm$0.04 | 66.32$\pm$0.21
ISRUC (pat) | 75.11$\pm$0.77 | 75.11$\pm$0.77 | 75.57$\pm$0.91 | 75.54$\pm$0.68 | 73.79$\pm$0.72 | 75.11$\pm$0.79 | 75.11$\pm$0.77 | 75.11$\pm$0.76 | 76.26$\pm$0.59 | 76.13$\pm$0.89
ISRUC | 74.66$\pm$0.08 | 74.66$\pm$0.08 | 76.08$\pm$0.16 | 75.15$\pm$0.07 | 73.34$\pm$0.09 | 74.69$\pm$0.09 | 74.66$\pm$0.08 | 74.66$\pm$0.09 | 75.95$\pm$0.07 | 77.45$\pm$0.16
PN2017 | 54.67$\pm$0.14 | 54.67$\pm$0.14 | 60.00$\pm$0.22 | 57.55$\pm$0.39 | 13.78$\pm$0.13 | 55.11$\pm$0.84 | 55.15$\pm$1.48 | 54.69$\pm$0.15 | 51.90$\pm$0.07 | 60.36$\pm$0.61
C10 (ViT) | 98.94$\pm$0.05 | 98.94$\pm$0.05 | 98.94$\pm$0.05 | 98.94$\pm$0.05 | 98.76$\pm$0.06 | 98.94$\pm$0.05 | 98.94$\pm$0.05 | 98.94$\pm$0.06 | 98.93$\pm$0.07 | 98.98$\pm$0.09
C10 (Mixer) | 98.17$\pm$0.08 | 98.17$\pm$0.08 | 98.03$\pm$0.09 | 98.13$\pm$0.08 | 96.98$\pm$0.08 | 98.17$\pm$0.08 | 98.17$\pm$0.08 | 98.16$\pm$0.08 | 98.15$\pm$0.06 | 98.14$\pm$0.06
C100 (ViT) | 92.09$\pm$0.16 | 92.09$\pm$0.16 | 92.08$\pm$0.14 | 91.95$\pm$0.17 | 91.21$\pm$0.12 | 92.09$\pm$0.16 | 92.09$\pm$0.16 | 92.09$\pm$0.16 | 92.41$\pm$0.17 | 92.37$\pm$0.15
C100 (Mixer) | 87.53$\pm$0.20 | 87.53$\pm$0.20 | 87.24$\pm$0.22 | 87.10$\pm$0.21 | 86.49$\pm$0.23 | 87.53$\pm$0.20 | 87.53$\pm$0.20 | 87.51$\pm$0.20 | 88.13$\pm$0.25 | 87.55$\pm$0.16
SVHN (ViT) | 95.93$\pm$0.05 | 95.93$\pm$0.05 | 95.93$\pm$0.05 | 95.85$\pm$0.06 | 95.70$\pm$0.08 | 95.93$\pm$0.05 | 95.93$\pm$0.05 | 95.93$\pm$0.05 | 96.48$\pm$0.04 | 96.42$\pm$0.05
SVHN (Mixer) | 95.85$\pm$0.04 | 95.85$\pm$0.04 | 95.98$\pm$0.04 | 95.85$\pm$0.05 | 95.24$\pm$0.04 | 95.85$\pm$0.04 | 95.85$\pm$0.04 | 95.85$\pm$0.05 | 95.58$\pm$0.05 | 96.10$\pm$0.04
ImageNet | 80.44$\pm$0.24 | 80.44$\pm$0.24 | 79.55$\pm$0.24 | 80.34$\pm$0.28 | – | 80.22$\pm$0.27 | 80.44$\pm$0.24 | 80.44$\pm$0.24 | – | 79.64$\pm$0.24

Table 3: Class-wise ECE in $10^{-2}$ ($\downarrow$ means lower=better). The
best accuracy-preserving method is in bold (p=0.01). The lowest but not
accuracy-preserving number is underscored. KCal almost always achieves the
lowest class-wise ECE, while maintaining accuracy.

CECE $\downarrow$ |  UnCal |  TS |  DirCal |  I-Max |  Focal |  Spline |  IOP |  GP |  MMCE |  KCal
---|---|---|---|---|---|---|---|---|---|---
IIIC (pat) |  8.07$\pm$0.27 |  8.97$\pm$0.85 |  5.13$\pm$1.48 |  9.23$\pm$0.98 |  8.99$\pm$0.53 |  8.56$\pm$0.62 |  8.33$\pm$0.50 |  7.95$\pm$0.64 |  7.12$\pm$0.43 |  4.68$\pm$1.27
IIIC |  7.96$\pm$0.02 |  8.96$\pm$0.52 |  2.24$\pm$0.13 |  8.76$\pm$0.26 |  8.78$\pm$0.02 |  8.43$\pm$0.21 |  8.01$\pm$0.25 |  7.52$\pm$0.23 |  6.70$\pm$0.25 |  2.03$\pm$0.26
ISRUC (pat) |  4.48$\pm$0.24 |  4.69$\pm$0.76 |  4.18$\pm$0.90 |  8.56$\pm$1.00 |  9.23$\pm$0.21 |  4.68$\pm$0.46 |  4.60$\pm$0.60 |  4.64$\pm$0.43 |  4.08$\pm$0.36 |  3.82$\pm$1.24
ISRUC |  4.49$\pm$0.02 |  5.17$\pm$0.77 |  2.71$\pm$0.40 |  9.22$\pm$0.85 |  9.05$\pm$0.03 |  4.73$\pm$0.15 |  4.67$\pm$0.36 |  4.67$\pm$0.27 |  4.10$\pm$0.22 |  1.90$\pm$0.28
PN2017 |  12.17$\pm$0.07 |  12.31$\pm$0.23 |  4.30$\pm$0.47 |  9.92$\pm$1.16 |  17.31$\pm$0.09 |  8.61$\pm$0.73 |  12.09$\pm$0.34 |  12.17$\pm$0.07 |  12.35$\pm$0.39 |  4.25$\pm$1.26
C10 (ViT) |  3.19$\pm$0.01 |  0.76$\pm$0.04 |  0.83$\pm$0.06 |  0.68$\pm$0.05 |  4.82$\pm$0.07 |  0.90$\pm$0.04 |  0.81$\pm$0.06 |  0.74$\pm$0.06 |  1.11$\pm$0.27 |  0.74$\pm$0.07
C10 (Mixer) |  3.11$\pm$0.02 |  1.45$\pm$0.12 |  1.23$\pm$0.10 |  1.24$\pm$0.17 |  6.70$\pm$0.03 |  1.28$\pm$0.09 |  1.30$\pm$0.07 |  1.21$\pm$0.07 |  1.43$\pm$0.19 |  1.17$\pm$0.10
C100 (ViT) |  5.90$\pm$0.05 |  5.27$\pm$0.20 |  4.64$\pm$0.13 |  4.96$\pm$0.17 |  5.53$\pm$0.06 |  4.41$\pm$0.14 |  4.72$\pm$0.12 |  4.65$\pm$0.16 |  4.27$\pm$0.23 |  4.32$\pm$0.10
C100 (Mixer) |  5.39$\pm$0.04 |  5.82$\pm$0.17 |  5.25$\pm$0.14 |  5.79$\pm$0.24 |  5.72$\pm$0.05 |  4.92$\pm$0.18 |  5.34$\pm$0.23 |  5.09$\pm$0.15 |  5.26$\pm$0.19 |  4.62$\pm$0.10
SVHN (ViT) |  3.37$\pm$0.01 |  2.31$\pm$0.56 |  1.22$\pm$0.06 |  2.64$\pm$0.20 |  5.89$\pm$0.03 |  1.34$\pm$0.05 |  1.39$\pm$0.06 |  1.40$\pm$0.05 |  1.47$\pm$0.11 |  1.23$\pm$0.10
SVHN (Mixer) |  3.20$\pm$0.01 |  3.06$\pm$0.61 |  1.21$\pm$0.12 |  2.64$\pm$0.17 |  5.59$\pm$0.02 |  1.45$\pm$0.09 |  1.44$\pm$0.06 |  1.46$\pm$0.06 |  1.64$\pm$0.13 |  1.40$\pm$0.08
ImageNet |  2.96$\pm$0.02 |  3.25$\pm$0.07 |  5.60$\pm$0.23 |  2.82$\pm$0.19 |  – |  2.17$\pm$0.06 |  2.30$\pm$0.14 |  2.42$\pm$0.06 |  – |  1.94$\pm$0.04

Table 4: ECE in $10^{-2}$ ($\downarrow$ means lower=better). The best
accuracy-preserving method is in bold (p=0.01). The lowest but not accuracy-
preserving number is underscored. KCal is usually on par or better than the
best baseline.

ECE $\downarrow$ | UnCal | TS | DirCal | I-Max | Focal | Spline | IOP | GP | MMCE | KCal
---|---|---|---|---|---|---|---|---|---|---
IIIC (pat) | 9.32$\pm$1.01 | 5.00$\pm$2.75 | 2.92$\pm$1.59 | 10.52$\pm$4.05 | 7.53$\pm$0.55 | 4.58$\pm$2.04 | 4.57$\pm$2.14 | 3.86$\pm$1.63 | 6.33$\pm$3.28 | 4.34$\pm$1.35
IIIC | 9.28$\pm$0.03 | 4.45$\pm$1.52 | 1.39$\pm$0.19 | 10.16$\pm$0.81 | 7.25$\pm$0.05 | 3.20$\pm$0.64 | 3.50$\pm$0.41 | 1.80$\pm$0.49 | 4.78$\pm$2.24 | 2.62$\pm$0.59
ISRUC (pat) | 3.59$\pm$0.32 | 2.73$\pm$1.53 | 2.97$\pm$0.97 | 8.86$\pm$1.39 | 14.88$\pm$0.43 | 1.98$\pm$0.35 | 2.45$\pm$1.36 | 2.00$\pm$0.53 | 2.12$\pm$0.93 | 2.78$\pm$1.25
ISRUC | 3.46$\pm$0.06 | 3.82$\pm$1.69 | 2.27$\pm$0.69 | 9.58$\pm$1.23 | 14.70$\pm$0.06 | 1.50$\pm$0.53 | 2.71$\pm$0.96 | 2.09$\pm$0.74 | 2.12$\pm$1.03 | 1.36$\pm$0.41
PN2017 | 16.70$\pm$0.22 | 16.99$\pm$0.73 | 5.64$\pm$0.75 | 10.40$\pm$1.35 | 24.63$\pm$0.13 | 6.84$\pm$2.09 | 16.07$\pm$2.03 | 16.66$\pm$0.21 | 13.49$\pm$1.07 | 4.78$\pm$1.48
C10 (ViT) | 9.15$\pm$0.05 | 0.75$\pm$0.11 | 0.40$\pm$0.04 | 0.51$\pm$0.07 | 7.17$\pm$0.07 | 0.39$\pm$0.08 | 0.39$\pm$0.04 | 0.21$\pm$0.06 | 0.42$\pm$0.29 | 0.40$\pm$0.05
C10 (Mixer) | 9.04$\pm$0.06 | 1.06$\pm$0.12 | 0.61$\pm$0.07 | 0.91$\pm$0.14 | 12.53$\pm$0.06 | 0.36$\pm$0.06 | 0.66$\pm$0.09 | 0.34$\pm$0.10 | 0.91$\pm$0.44 | 0.59$\pm$0.09
C100 (ViT) | 11.64$\pm$0.14 | 2.77$\pm$0.46 | 0.74$\pm$0.16 | 3.28$\pm$0.22 | 9.97$\pm$0.09 | 1.08$\pm$0.18 | 1.07$\pm$0.19 | 0.88$\pm$0.11 | 1.05$\pm$0.30 | 1.50$\pm$0.32
C100 (Mixer) | 13.71$\pm$0.15 | 3.03$\pm$0.34 | 1.06$\pm$0.28 | 4.75$\pm$0.27 | 14.35$\pm$0.21 | 1.25$\pm$0.29 | 1.70$\pm$0.66 | 1.08$\pm$0.26 | 1.93$\pm$0.49 | 3.07$\pm$0.49
SVHN (ViT) | 10.10$\pm$0.05 | 2.43$\pm$2.72 | 0.60$\pm$0.07 | 2.05$\pm$0.18 | 12.17$\pm$0.08 | 0.74$\pm$0.10 | 0.62$\pm$0.08 | 0.64$\pm$0.07 | 0.72$\pm$0.21 | 0.64$\pm$0.12
SVHN (Mixer) | 10.29$\pm$0.04 | 3.19$\pm$2.55 | 0.66$\pm$0.05 | 2.13$\pm$0.10 | 11.09$\pm$0.06 | 0.78$\pm$0.11 | 0.60$\pm$0.08 | 0.72$\pm$0.06 | 0.72$\pm$0.28 | 0.73$\pm$0.10
ImageNet | 3.21$\pm$0.15 | 3.52$\pm$0.13 | 4.30$\pm$0.68 | 7.97$\pm$0.35 | – | 1.10$\pm$0.20 | 1.31$\pm$0.47 | 0.87$\pm$0.12 | – | 1.43$\pm$0.34

Table 5:  Brier Score in $10^{-2}$ ($\downarrow$ means lower=better). The best
accuracy-preserving methods are in bold (p=0.01). The lowest but not accuracy-
preserving number is underscored.

Brier $\downarrow$ |  UnCal |  TS |  DirCal |  I-Max |  Focal |  Spline |  IOP |  GP |  MMCE |  KCal
---|---|---|---|---|---|---|---|---|---|---
IIIC (pat) |  21.30$\pm$0.25 |  20.70$\pm$0.69 |  18.94$\pm$0.55 |  21.09$\pm$1.29 |  21.48$\pm$0.19 |  20.43$\pm$0.50 |  20.52$\pm$0.58 |  20.33$\pm$0.42 |  21.11$\pm$0.71 |  19.33$\pm$0.78
IIIC |  21.35$\pm$0.01 |  20.62$\pm$0.27 |  18.33$\pm$0.04 |  20.83$\pm$0.19 |  21.46$\pm$0.01 |  20.21$\pm$0.09 |  20.39$\pm$0.09 |  20.05$\pm$0.08 |  20.86$\pm$0.26 |  17.54$\pm$0.10
ISRUC (pat) |  15.26$\pm$0.25 |  15.20$\pm$0.31 |  15.37$\pm$0.38 |  16.25$\pm$0.49 |  18.55$\pm$0.18 |  15.11$\pm$0.26 |  15.16$\pm$0.31 |  15.16$\pm$0.29 |  14.69$\pm$0.22 |  14.97$\pm$0.29
ISRUC |  15.46$\pm$0.03 |  15.50$\pm$0.19 |  15.07$\pm$0.09 |  16.62$\pm$0.33 |  18.77$\pm$0.01 |  15.31$\pm$0.05 |  15.39$\pm$0.10 |  15.35$\pm$0.06 |  14.91$\pm$0.08 |  14.28$\pm$0.08
PN2017 |  26.61$\pm$0.05 |  26.74$\pm$0.27 |  22.44$\pm$0.15 |  24.58$\pm$0.59 |  17.79$\pm$0.03 |  23.28$\pm$0.37 |  26.39$\pm$0.69 |  26.61$\pm$0.05 |  26.41$\pm$0.44 |  22.56$\pm$0.28
C10 (ViT) |  1.76$\pm$0.03 |  0.89$\pm$0.06 |  0.78$\pm$0.04 |  0.84$\pm$0.04 |  1.75$\pm$0.03 |  0.79$\pm$0.04 |  0.79$\pm$0.04 |  0.78$\pm$0.04 |  0.85$\pm$0.10 |  0.75$\pm$0.05
C10 (Mixer) |  2.29$\pm$0.03 |  1.48$\pm$0.07 |  1.42$\pm$0.05 |  1.46$\pm$0.08 |  4.16$\pm$0.04 |  1.39$\pm$0.04 |  1.40$\pm$0.05 |  1.37$\pm$0.04 |  1.45$\pm$0.16 |  1.34$\pm$0.04
C100 (ViT) |  6.94$\pm$0.08 |  5.35$\pm$0.15 |  5.17$\pm$0.10 |  5.48$\pm$0.14 |  6.93$\pm$0.07 |  5.19$\pm$0.09 |  5.18$\pm$0.10 |  5.14$\pm$0.09 |  4.81$\pm$0.10 |  5.01$\pm$0.08
C100 (Mixer) |  10.15$\pm$0.11 |  7.94$\pm$0.17 |  7.82$\pm$0.12 |  8.23$\pm$0.17 |  10.91$\pm$0.08 |  7.76$\pm$0.12 |  7.82$\pm$0.15 |  7.72$\pm$0.13 |  7.38$\pm$0.16 |  7.61$\pm$0.09
SVHN (ViT) |  3.99$\pm$0.03 |  3.03$\pm$0.34 |  2.78$\pm$0.04 |  2.99$\pm$0.07 |  5.03$\pm$0.03 |  2.80$\pm$0.03 |  2.79$\pm$0.04 |  2.79$\pm$0.04 |  2.43$\pm$0.02 |  2.49$\pm$0.03
SVHN (Mixer) |  4.03$\pm$0.03 |  3.21$\pm$0.36 |  2.77$\pm$0.03 |  3.04$\pm$0.04 |  5.06$\pm$0.04 |  2.84$\pm$0.03 |  2.81$\pm$0.04 |  2.81$\pm$0.04 |  3.03$\pm$0.02 |  2.68$\pm$0.03
ImageNet |  11.15$\pm$0.14 |  11.20$\pm$0.15 |  12.03$\pm$0.21 |  11.93$\pm$0.18 |  – |  10.68$\pm$0.13 |  10.69$\pm$0.13 |  10.67$\pm$0.12 |  – |  11.14$\pm$0.10

Table 6:  Ranks for different evaluation metrics. The best rank is
underscored. In general, KCal consistently outperforms baselines on Accuracy,
CECE and Brier, and the difference between most methods on ECE is small.

Ranking | UnCal | TS | DirCal | I-Max | Focal | Spline | IOP | GP | MMCE | KCal
---|---|---|---|---|---|---|---|---|---|---
ECE | 8.42$\pm$1.43 | 6.68$\pm$1.11 | 3.33$\pm$1.80 | 7.73$\pm$1.55 | 9.39$\pm$0.95 | 3.51$\pm$1.06 | 4.25$\pm$1.35 | 2.91$\pm$1.66 | 4.52$\pm$0.98 | 3.84$\pm$1.35
Accuracy | 5.03$\pm$1.30 | 5.03$\pm$1.30 | 4.53$\pm$2.69 | 6.41$\pm$2.36 | 9.99$\pm$0.03 | 5.56$\pm$0.93 | 5.01$\pm$1.27 | 5.64$\pm$1.16 | 4.74$\pm$3.30 | 2.70$\pm$2.01
CECE | 6.99$\pm$1.95 | 7.41$\pm$1.60 | 3.31$\pm$2.08 | 6.82$\pm$2.67 | 9.46$\pm$0.61 | 4.59$\pm$2.06 | 5.12$\pm$1.13 | 4.37$\pm$1.27 | 4.69$\pm$1.99 | 1.83$\pm$0.76
Brier | 8.18$\pm$1.52 | 6.91$\pm$0.85 | 3.86$\pm$2.08 | 7.42$\pm$1.06 | 8.98$\pm$2.67 | 4.23$\pm$1.05 | 4.88$\pm$1.24 | 3.89$\pm$1.83 | 4.11$\pm$2.89 | 2.05$\pm$1.17
Average | 7.16 | 6.51 | 3.76 | 7.09 | 9.46 | 4.47 | 4.81 | 4.20 | 4.51 | 2.61

###  4.2 Baselines Methods

We compare KCal with the multiple state-of-the-art calibration methods,
including Temperature Scaling (TS) (Guo et al., 2017), Dirichlet Calibration
(DirCal) (Kull et al., 2019), Mutual-information-maximization-based Binning
(I-Max) (Patel et al., 2021), Gaussian Process Calibration (GP) (Wenger et
al., 2020), Intra Order-preserving Calibration (IOP) (Rahimi et al., 2020),
Splines-based Calibration (Spline) (Gupta et al., 2021), Focal-loss-based
calibration (Focal) (Mukhoti et al., 2020), MMCE-based calibration (MMCE)
(Kumar et al., 2018).

###  4.3 Evaluation Metrics

We report standard evaluation metrics: Accuracy, class-wise expected
calibration error (CECE) (Kull et al., 2019; Patel et al., 2021; Nixon et al.,
2019), expected calibration error (ECE) (Guo et al., 2017), and Brier score
(Brier, 1950). CECE is typically used as a proxy to evaluate full calibration
quality, because directly binning basing on the entire vector
$\hat{\mathbf{p}}$ requires exponentially (in $K$) many bins. Similar to Patel
et al. (2021); Nixon et al. (2019), we ignore all predictions with very small
probabilities (less than $\max\\{0.01,\frac{1}{K}\\}$). ECE, on the other
hand, only measures confidence calibration (Def 2). For both ECE and CECE, we
use the “adaptive” version with equal number of samples in each bin (with 20
bins), because this is shown to measure the calibration quality better than
the equal-width version (Nixon et al., 2019). Brier score can be viewed as the
sum of a “calibration” term, and a “refinement” term measuring how
discriminative a model is (Kull & Flach, 2015). Here we focus on the brier
score of the top class. We refer to (Guo et al., 2017; Kull et al., 2019;
Nixon et al., 2019) for further discussion on these metrics.

###  4.4 Results

The results are presented in Tables 2, 3, 4 and 5. All experiments are
repeated 10 times by reshuffling calibration and test sets, and the standard
deviations are reported. For ImageNet, we skipped Focal and MMCE because the
base NN is given and these methods require training from scratch. Due to space
constraints, we include ablation studies in the Appendix.

In general, KCal has the best CECE, accuracy and Brier score, and is highly
competitive in terms of ECE as well. Note that KCal is also the only method
with provable calibration guarantee. TS is effective in controlling overall
ECE but shows little improvement on CECE over UnCal. DirCal often ranks high
for the calibration quality but tends to decrease accuracy as $K$ increases.
DirCal’s performance also has a higher cost: Every experiment requires
training over hundreds of models with SGD and taking the best ensemble,
accounting for most of the experiment computation cost in this paper. The
amount of tuning suggested for good performance indicates sensitivity to the
choice of hyper-parameters, which we have indeed observed to be the case.
Spline, IOP and GP are similar to DirCal on vision datasets, but generally
perform worse on the healthcare datasets. In Patel et al. (2021), I-Max lowers
ECE and CECE significantly. However, it has a critical issue - it does not
produce a valid probability vector444It generates a vector whose sum ranges
from 0.4 to 2.0 in our experiments. The range is wider for a larger $K$. .
Once normalized, as reported in our experiments, the performance worsens.
Since calibrating all the classes simultaneously is the distinguishing
challenge in multiclass classification, we interpret the observation as: If
this normalization constraint is removed, the “optimization problem” (to lower
calibration error) is much simpler, but the results are invalid hence unusable
probability vectors. Spline also requires a re-normalization step, but its
performance stays consistent. Focal is worse than the UnCal in many
experiments. While calibration performance may improve by combing Focal with
other methods, the drop in accuracy is harder to overcome555In PN2017, rare
classes are oversampled during training (Hong et al., 2019). While this did
not cause issues for other calibration methods, the distributional shift at
test time seems catastrophic for Focal. . We also observed that for healthcare
datasets, being able to tune on a different set of patients boosts the
performance significantly. This is reflected in the accuracy gain for DirCal
and KCal, and suggests that the embeddings/logits are quite transferable, but
the prediction criteria itself can vary from patient to patient.

Finally, we summarize the rankings of all datasets in Table 6. It is clear
that KCal consistently improves calibration quality for all classes and
maintains or improves accuracy. And if we look at only the confidence
prediction (Brier or ECE), KCal is still highly competitive.

Figure 2:  Reliability diagrams for the predicted class (top) and Seizure
(bottom) in IIIC. All methods calibrate confidence well, but only KCal
achieves reasonable calibration quality for Seizure.

###  4.5 Case Study for Seizure Prediction

We show the reliability diagrams (Kull et al., 2019; Guo et al., 2017) on the
IIIC dataset to illustrate the importance of full calibration in Figure 2. We
include both the the predicted class (confidence calibration) and Seizure.
More reliability diagrams can be found in the Appendix, and the results are
consistent for all classes. The un-calibrated predictions have large gaps for
both confidence and Seizure. Most baselines provide calibrated confidence
calibration, but fail to calibrated the output for the rare class Seizure.
KCal, on the other hand, achieves the most consistent results. We note again
that since all competing classes must be considered together for any clinical
decision, full calibration is indispensable in medical applications.

##  5 Conclusion

This paper proposed KCal, a learned-kernel-based calibration method for deep
learning models. KCal consists of a supervised dimensionality reduction step
on the penultimate layer neural network embedding to improve efficiency. A KDE
classifier using the calibration set is employed in this new metric space. As
a natural consequence of the construction, KCal provides a calibrated
probability vector prediction for all classes. Unlike most existing
calibration methods, KCal is also provably asymptotically fully calibrated
with finite sample error bounds. We also showed that empirically, it
outperforms existing state-of-the-art calibration methods in terms of accuracy
and calibration quality. Moreover, KCal is more robust to distributional
shift, which is common in high-risk applications such as healthcare, where
calibration is far more crucial. The major limitation of KCal is the need to
store the entire calibration set, which is a small overhead with the dimension
reduction step and potential improvements.

## References

  * Biswal et al. (2017) Siddharth Biswal, Joshua A. Kulas, Haoqi Sun, Balaji Goparaju, Michael Brandon Westover, Matt T. Bianchi, and Jimeng Sun.  Sleepnet: Automated sleep staging system via deep learning.  _ArXiv_ , abs/1707.08262, 2017.
  * Brier (1950) Glenn W. Brier.  Verification of Forecasts Expressed in Terms of Probability.  _Monthly Weather Review_ , 78(1):1, January 1950\.  doi: 10.1175/1520-0493(1950)078<0001:VOFEIT>2.0.CO;2.
  * Chacón & Duong (2018) José E. Chacón and Tarn Duong.  _Multivariate Kernel Smoothing and its Applications_.  Chapman and Hall, 2018.
  * Chen et al. (2010) Yutian Chen, Max Welling, and Alex Smola.  Super-samples from kernel herding.  In _Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence_ , UAI’10, pp. 109–116, Arlington, Virginia, USA, 2010\. AUAI Press.  ISBN 9780974903965.
  * Clifford et al. (2017) Gari D. Clifford, Chengyu Liu, Benjamin Moody, Liwei H. Lehman, Ikaro Silva, Qiao Li, A. E. Johnson, and Roger G. Mark.  AF classification from a short single lead ECG recording: The PhysioNet/computing in cardiology challenge 2017.  In _Computing in Cardiology_ , 2017.  doi: 10.22489/CinC.2017.065-469.
  * Degroot & Fienberg (1983) Morris H. Degroot and Stephen E. Fienberg.  The comparison and evaluation of forecasters.  _The Statistician_ , 32:12–22, 1983.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 248–255, 2009.  doi: 10.1109/CVPR.2009.5206848.
  * Deng et al. (2013) Li Deng, Geoffrey Hinton, and Brian Kingsbury.  New types of deep neural network learning for speech recognition and related applications: an overview.  In _2013 IEEE International Conference on Acoustics, Speech and Signal Processing_ , pp. 8599–8603, 2013.  doi: 10.1109/ICASSP.2013.6639344.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=YicbFdNTTy.
  * Filho et al. (2021) ATelmo Silva Filho, Hao Song, Miquel Perello-Nieto, Raul Santos-Rodriguez, Meelis Kull, and Peter Flach.  Classifier calibration: How to assess and improve predicted class probabilities: a survey.  _CoRR_ , abs/2112.10327, 2021.  URL https://arxiv.org/abs/2112.10327.
  * Gadat et al. (2016) Sébastien Gadat, Thierry Klein, and Clément Marteau.  Classification in general finite dimensional spaces with the k-nearest neighbor rule.  _The Annals of Statistics_ , 44(3):982–1009, 2016\.  ISSN 00905364.  URL http://www.jstor.org/stable/43818918.
  * Ge et al. (2021) Wendong Ge, Jin Jing, Sungtae An, Aline Herlopian, Marcus Ng, Aaron F. Struck, Brian Appavu, Emily L. Johnson, Gamaleldin Osman, Hiba A. Haider, Ioannis Karakis, Jennifer A. Kim, Jonathan J. Halford, Monica B. Dhakar, Rani A. Sarkis, Christa B. Swisher, Sarah Schmitt, Jong Woo Lee, Mohammad Tabaeizadeh, Andres Rodriguez, Nicolas Gaspard, Emily Gilmore, Susan T. Herman, Peter W. Kaplan, Jay Pathmanathan, Shenda Hong, Eric S. Rosenthal, Sahar Zafar, Jimeng Sun, and M. Brandon Westover.  Deep active learning for interictal ictal injury continuum EEG patterns.  _Journal of Neuroscience Methods_ , 351:108966, mar 2021\.  doi: 10.1016/j.jneumeth.2020.108966.  URL https://doi.org/10.1016%2Fj.jneumeth.2020.108966.
  * Goldberger et al. (2000) A. L. Goldberger, L. A. Amaral, L. Glass, J. M. Hausdorff, P. C. Ivanov, R. G. Mark, J. E. Mietus, G. B. Moody, C. K. Peng, and H. E. Stanley.  PhysioBank, PhysioToolkit, and PhysioNet: components of a new research resource for complex physiologic signals.  _Circulation_ , 2000.  ISSN 15244539.  doi: 10.1161/01.cir.101.23.e215.
  * Gray & Moore (2003) Alexander G. Gray and Andrew W. Moore.  Nonparametric density estimation: Toward computational tractability.  In _SDM_ , 2003.
  * Guo et al. (2017) Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger.  On calibration of modern neural networks.  In Doina Precup and Yee Whye Teh (eds.), _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pp. 1321–1330. PMLR, 06–11 Aug 2017.  URL https://proceedings.mlr.press/v70/guo17a.html.
  * Gupta & Ramdas (2021) Chirag Gupta and Aaditya Ramdas.  Distribution-free calibration guarantees for histogram binning without sample splitting.  In Marina Meila and Tong Zhang (eds.), _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 3942–3952. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/gupta21b.html.
  * Gupta et al. (2021) Kartik Gupta, Amir Rahimi, Thalaiyasingam Ajanthan, Thomas Mensink, Cristian Sminchisescu, and Richard Hartley.  Calibration of neural networks using splines.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=eQe8DEWNN2W.
  * Hong et al. (2019) Shenda Hong, Cao Xiao, Tengfei Ma, Hongyan Li, and Jimeng Sun.  Mina: Multilevel knowledge-guided attention for modeling electrocardiography signals.  In _IJCAI International Joint Conference on Artificial Intelligence_ , 2019.  ISBN 9780999241141.  doi: 10.24963/ijcai.2019/816.
  * Jiang (2017) Heinrich Jiang.  Uniform convergence rates for kernel density estimation.  In Doina Precup and Yee Whye Teh (eds.), _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pp. 1694–1703. PMLR, 06–11 Aug 2017.  URL https://proceedings.mlr.press/v70/jiang17b.html.
  * Jiang et al. (2018) Heinrich Jiang, Been Kim, Melody Guan, and Maya Gupta.  To trust or not to trust a classifier.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/7180cffd6a8e829dacfc2a31b3f72ece-Paper.pdf.
  * Jiang et al. (2012) Xiaoqian Jiang, Melanie Osl, Jihoon Kim, and Lucila Ohno-Machado.  Calibrating predictive model estimates to support personalized medicine.  _J. Am. Medical Informatics Assoc._ , 19(2):263–274, 2012.  doi: 10.1136/amiajnl-2011-000291.  URL https://doi.org/10.1136/amiajnl-2011-000291.
  * Jing et al. (2021) Jin Jing, Emile d’Angremont, Senan Ebrahim, Mohammad Tabaeizadeh, Marcus Ng, Aline Herlopian, Justin Dauwels, and M. Brandon Westover.  Rapid annotation of seizures and interictal-ictal-injury continuum eeg patterns.  _Journal of Neuroscience Methods_ , 347:108956, 2021.  ISSN 0165-0270.  doi: https://doi.org/10.1016/j.jneumeth.2020.108956.  URL https://www.sciencedirect.com/science/article/pii/S0165027020303794.
  * Karandikar et al. (2021) Archit Karandikar, Nicholas Cain, Dustin Tran, Balaji Lakshminarayanan, Jonathon Shlens, Michael C. Mozer, and Becca Roelofs.  Soft calibration objectives for neural networks.  _CoRR_ , abs/2108.00106, 2021.  URL https://arxiv.org/abs/2108.00106.
  * Khalighi et al. (2016) Sirvan Khalighi, Teresa Sousa, José Moutinho Santos, and Urbano Nunes.  ISRUC-Sleep: A comprehensive public dataset for sleep researchers.  _Computer Methods and Programs in Biomedicine_ , 2016.  ISSN 18727565.  doi: 10.1016/j.cmpb.2015.10.013.
  * Kiefer (1953) J. Kiefer.  Sequential minimax search for a maximum.  _Proceedings of the American Mathematical Society_ , 4(3):502–506, 1953.  ISSN 00029939, 10886826.  URL http://www.jstor.org/stable/2032161.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images, 2009.
  * Kull & Flach (2015) Meelis Kull and Peter Flach.  Novel decompositions of proper scoring rules for classification: Score adjustment as precursor to calibration.  In Annalisa Appice, Pedro Pereira Rodrigues, Vítor Santos Costa, Carlos Soares, João Gama, and Alípio Jorge (eds.), _Machine Learning and Knowledge Discovery in Databases_ , pp. 68–85, Cham, 2015. Springer International Publishing.  ISBN 978-3-319-23528-8.
  * Kull et al. (2019) Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach.  Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration.  In _Advances in Neural Information Processing Systems_ , pp. 12295–12305, 2019.
  * Kumar et al. (2019) Ananya Kumar, Percy S Liang, and Tengyu Ma.  Verified uncertainty calibration.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/f8c0c968632845cd133308b1a494967f-Paper.pdf.
  * Kumar et al. (2018) Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain.  Trainable calibration measures for neural networks from kernel mean embeddings.  In Jennifer Dy and Andreas Krause (eds.), _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pp. 2805–2814. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/kumar18a.html.
  * Ma & Blaschko (2021) Xingchen Ma and Matthew B. Blaschko.  Meta-cal: Well-controlled post-hoc calibration by ranking.  In Marina Meila and Tong Zhang (eds.), _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 7235–7245. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/ma21a.html.
  * Mukhoti et al. (2020) Jishnu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip Torr, and Puneet Dokania.  Calibrating deep neural networks using focal loss.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 15288–15299. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/aeb7b30ef1d024a76f21a1d40e30c302-Paper.pdf.
  * Murphy & Winkler (1977) Allan H. Murphy and Robert L. Winkler.  Reliability of subjective probability forecasts of precipitation and temperature.  _Journal of The Royal Statistical Society Series C-applied Statistics_ , 26:41–47, 1977.
  * Murphy & Winkler (1984) Allan H. Murphy and Robert L. Winkler.  Probability forecasting in meteorology.  _Journal of the American Statistical Association_ , 79:489–500, 1984.
  * Netzer et al. (2011) Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng.  Reading digits in natural images with unsupervised feature learning.  In _NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011_ , 2011.  URL http://ufldl.stanford.edu/housenumbers/nips2011_housenumbers.pdf.
  * Niculescu-Mizil & Caruana (2005) Alexandru Niculescu-Mizil and Rich Caruana.  Predicting good probabilities with supervised learning.  In _Proceedings of the 22nd International Conference on Machine Learning_ , ICML ’05, pp. 625–632, New York, NY, USA, 2005. Association for Computing Machinery.  ISBN 1595931805.  doi: 10.1145/1102351.1102430.  URL https://doi.org/10.1145/1102351.1102430.
  * Nixon et al. (2019) Jeremy Nixon, Michael W. Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran.  Measuring calibration in deep learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2019.
  * Ouyang & Wang (2013) Wanli Ouyang and Xiaogang Wang.  Joint deep learning for pedestrian detection.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , December 2013.
  * Papernot & McDaniel (2018) Nicolas Papernot and Patrick D. McDaniel.  Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning.  _CoRR_ , abs/1803.04765, 2018.  URL http://arxiv.org/abs/1803.04765.
  * Patel et al. (2021) Kanil Patel, William H. Beluch, Bin Yang, Michael Pfeiffer, and Dan Zhang.  Multi-class uncertainty calibration via mutual information maximization-based binning.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=AICNpd8ke-m.
  * Platt (1999) John C. Platt.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  In _ADVANCES IN LARGE MARGIN CLASSIFIERS_ , pp. 61–74. MIT Press, 1999.
  * Qiao et al. (2020) Zhi Qiao, Austin Bae, Lucas M Glass, Cao Xiao, and Jimeng Sun.  FLANNEL (Focal Loss bAsed Neural Network EnsembLe) for COVID-19 detection.  _Journal of the American Medical Informatics Association_ , 28(3):444–452, 10 2020.  ISSN 1527-974X.  doi: 10.1093/jamia/ocaa280.  URL https://doi.org/10.1093/jamia/ocaa280.
  * Rahimi et al. (2020) Amir Rahimi, Amirreza Shaban, Ching-An Cheng, Richard Hartley, and Byron Boots.  Intra order-preserving functions for calibration of multi-class neural networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 13456–13467. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/9bc99c590be3511b8d53741684ef574c-Paper.pdf.
  * Ruffini et al. (2019) Giulio Ruffini, David Ibañez, Marta Castellano, Laura Dubreuil-Vall, Aureli Soria-Frisch, Ron Postuma, Jean-François Gagnon, and Jacques Montplaisir.  Deep learning with eeg spectrograms in rapid eye movement behavior disorder.  _Frontiers in Neurology_ , 10, 2019.  ISSN 1664-2295.  doi: 10.3389/fneur.2019.00806.  URL https://www.frontiersin.org/article/10.3389/fneur.2019.00806.
  * Sodkomkham et al. (2016) Danaipat Sodkomkham, Davide Ciliberti, Matthew A. Wilson, Ken ichi Fukui, Koichi Moriyama, Masayuki Numao, and Fabian Kloosterman.  Kernel density compression for real-time bayesian encoding/decoding of unsorted hippocampal spikes.  _Knowledge-Based Systems_ , 94:1–12, 2016.  ISSN 0950-7051.  doi: https://doi.org/10.1016/j.knosys.2015.09.013.  URL https://www.sciencedirect.com/science/article/pii/S0950705115003524.
  * Szegedy et al. (2017) Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, and Alexander A. Alemi.  Inception-v4, inception-resnet and the impact of residual connections on learning.  In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence_ , AAAI’17, pp. 4278–4284. AAAI Press, 2017.
  * Tolstikhin et al. (2021) Ilya O. Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy.  Mlp-mixer: An all-mlp architecture for vision.  _CoRR_ , abs/2105.01601, 2021.  URL https://arxiv.org/abs/2105.01601.
  * Vaicenavicius et al. (2019) Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and Thomas Schön.  Evaluating model calibration in classification.  In Kamalika Chaudhuri and Masashi Sugiyama (eds.), _Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics_ , volume 89 of _Proceedings of Machine Learning Research_ , pp. 3459–3467. PMLR, 16–18 Apr 2019.  URL https://proceedings.mlr.press/v89/vaicenavicius19a.html.
  * Wenger et al. (2020) Jonathan Wenger, Hedvig Kjellström, and Rudolph Triebel).  Non-parametric calibration for classification.  In Silvia Chiappa and Roberto Calandra (eds.), _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pp. 178–190. PMLR, 26–28 Aug 2020.  URL https://proceedings.mlr.press/v108/wenger20a.html.
  * Widmann et al. (2019) David Widmann, Fredrik Lindsten, and Dave Zachariah.  Calibration tests in multi-class classification: A unifying framework.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/1c336b8080f82bcc2cd2499b4c57261d-Paper.pdf.
  * Wightman (2019) Ross Wightman.  Pytorch image models.  https://github.com/rwightman/pytorch-image-models, 2019.
  * Yuan et al. (2019) Ye Yuan, Guangxu Xun, Kebin Jia, and Aidong Zhang.  A multi-view deep learning framework for eeg seizure detection.  _IEEE Journal of Biomedical and Health Informatics_ , 23(1):83–94, 2019.  doi: 10.1109/JBHI.2018.2871678.
  * Zadrozny & Elkan (2001) Bianca Zadrozny and Charles Elkan.  Learning and making decisions when costs and probabilities are both unknown.  In _Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’01, pp. 204–213, New York, NY, USA, 2001. Association for Computing Machinery.  ISBN 158113391X.  doi: 10.1145/502512.502540.  URL https://doi.org/10.1145/502512.502540.
  * Zadrozny & Elkan (2002) Bianca Zadrozny and Charles Elkan.  Transforming classifier scores into accurate multiclass probability estimates.  In _Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’02, pp. 694–699, New York, NY, USA, 2002. Association for Computing Machinery.  ISBN 158113567X.  doi: 10.1145/775047.775151.  URL https://doi.org/10.1145/775047.775151.
  * Zhang et al. (2020) Jize Zhang, Bhavya Kailkhura, and T. Yong-Jin Han.  Mix-n-match : Ensemble and compositional methods for uncertainty calibration in deep learning.  In Hal Daumé III and Aarti Singh (eds.), _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 11117–11128. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/zhang20k.html.

Appendix

Overview of Appendices: Appendix A contains proofs for the lemmata and
theorems that appear in Section 3.3. Appendix B clarifies the benefits of the
sampling method (equal-size stratified sampling) described in Section 3.4.
Appendix C contains more details on the experiments in this paper. Appendix D
compares KCal with a simpler variant, namely KCal-Linear, which uses a linear
layer as the $\mathbf{\Pi}$. Appendix F explores the effect of $d$, the
projected dimension, on the performance and computational overhead. Finally,
Appendix G compares the cross-validation-selected bandwidth vs the
analytically computed bandwidth, which shows that it is possible to avoid most
of the bandwidth selection steps if we use KCal in an online manner.

##  Appendix A Detailed Assumptions and Proofs

###  A.1 Assumptions and Definitions

Denote $Z_{i}\vcentcolon=\mathbf{\Pi}(\mathbf{f}(X_{i}))$ for $i\in[N+1]$. We
assume $\\{Z_{i}\\}_{i=1}^{N+1}$ are i.i.d. Since fixing $\mathbf{\Pi}$ and
$\mathbf{f}$ using $\mathcal{S}_{\text{train}}$, all data will now live in
$\mathcal{Z}\vcentcolon=\mathbf{\Pi}(\mathbf{f}(\mathcal{X}))$. We are just
performing a standard (multivariate) kernel density estimation with only one
parameter $b$ on the calibration set. We will use $\hat{g}$ and $g$ to denote
the estimation and density in $\mathcal{Z}$, instead of the more cumbersome
$\hat{f}_{\mathbf{\Pi}\circ\mathbf{f},k}$ and
$f_{\mathbf{\Pi}\circ\mathbf{f},k}$.

Like in Chacón & Duong (2018), we make the following standard assumptions for
$g_{k}(\mathcal{Z})$:

  * •

(For any $k$) $g_{k}$ is square integrable and twice differentiable, with all
second order partials bounded, continuous and square integrable.

The base “mother kernel” function should satisfy the following (true for the
RBF kernel):

  * •

$\phi$ is spherical symmetric and has a finite second moment. Formally, this
means $\int_{\mathbb{R}^{d}}x\phi(x)dx=\mathbf{0}$ and $\forall
i\in[d],\int_{\mathbb{R}^{d}}x_{i}x_{j}\phi(x)dx=\mu_{2,\phi}\mathbf{1}\\{i=j\\}$
where $\mu_{2,\phi}$ is a fixed finite constant.

In the proof for Lemma 3.1 and Lemma 3.2, for simplicity, we ignore the
subscript k and write $g$ instead of $g_{k}$ where there is no confusion.

###  A.2 Proof of Lemma 3.1

Rewriting Eq. (8), we want to show $\|\hat{g}(\mathbf{z})-g(\mathbf{z})\|_{2}$
converges to $0$ in probability with an admissible $b(m)$, as $m\to\infty$. We
first derive the expression of the bias and variance of $\hat{g}$. For the
bias, we have:

$\displaystyle\mathbb{E}[\hat{g}(\mathbf{z})]-g(\mathbf{z})$
$\displaystyle=\frac{1}{b^{d}}\mathbb{E}\Bigg{[}\phi\Bigg{(}\frac{\mathbf{z}-Z}{b}\Bigg{)}\Bigg{]}-g(\mathbf{z})$
(13)
$\displaystyle=\frac{1}{b^{d}}\int\phi\Bigg{(}\frac{\mathbf{z}^{\prime}-\mathbf{z}}{b}\Bigg{)}g(\mathbf{z}^{\prime})d\mathbf{z}^{\prime}-g(\mathbf{z})$
(14)
$\displaystyle=\int\phi(\mathbf{u})g(\mathbf{z}+b\mathbf{u})d\mathbf{u}-g(\mathbf{z})$
(15)
$\displaystyle=\int\phi(\mathbf{u})\Big{(}g(\mathbf{z})+b(D_{g}(\mathbf{z}))^{\top}\mathbf{u}+\frac{1}{2}b^{2}\mathbf{u}^{\top}H_{g}(\mathbf{z})\mathbf{u}+o(\|b\mathbf{u}\|^{2})\Big{)}d\mathbf{u}-g(\mathbf{z})$
(16)
$\displaystyle=\int\phi(\mathbf{u})\frac{1}{2}b^{2}\mathbf{u}^{\top}H_{g}(\mathbf{z})\mathbf{u}d\mathbf{u}+o(\|b\mathbf{u}\|^{2})$
(17)
$\displaystyle=\int\phi(\mathbf{u})\frac{1}{2}b^{2}\sum_{i,j}u_{i}u_{j}H_{g,i,j}(\mathbf{z})d\mathbf{u}+o(b^{2})$
(18)
$\displaystyle=\sum_{i}H_{g,i,i}(\mathbf{z})\mu_{2,\phi}\frac{b^{2}}{2}+o(b^{2})$
(19) $\displaystyle=\frac{b^{2}}{2}\mu_{2,\phi}tr(H_{g}(\mathbf{z}))+o(b^{2})$
(20) $\displaystyle\implies|\mathbb{E}[\hat{g}(\mathbf{z})]-g(\mathbf{z})|$
$\displaystyle\leq C_{\phi,b}b^{2}$ (21)

for some constant $C_{\phi,b}$.

For the variance,

$\displaystyle Var(\hat{g}(z))$
$\displaystyle=Var\Bigg{(}\frac{1}{mb^{d}}\sum_{i=1}^{m}\phi\Bigg{(}\frac{\mathbf{z}-Z_{i}}{b}\Bigg{)}\Bigg{)}=\frac{1}{mb^{2d}}Var\Bigg{(}\phi\Bigg{(}\frac{\mathbf{z}-Z}{b}\Bigg{)}\Bigg{)}$
(22)
$\displaystyle\leq\frac{1}{mb^{2d}}\mathbb{E}\Bigg{[}\phi^{2}\Bigg{(}\frac{\mathbf{z}-Z}{b}\Bigg{)}\Bigg{]}=\frac{1}{mb^{2d}}\int\phi^{2}\Bigg{(}\frac{\mathbf{z}-\mathbf{z}^{\prime}}{b}\Bigg{)}g(\mathbf{z}^{\prime})d\mathbf{z}^{\prime}$
(23)
$\displaystyle=\frac{1}{mb^{d}}\int\phi^{2}(\mathbf{u})g(\mathbf{z}+b\mathbf{u})d\mathbf{u}$
(24)
$\displaystyle=\frac{1}{mb^{d}}\int\phi^{2}(\mathbf{u})\Big{(}g(\mathbf{z})+b(D_{g}(\mathbf{z}))^{\top}\mathbf{u}+o(\|b\mathbf{u}\|^{1})\Big{)}d\mathbf{u}$
(25)
$\displaystyle=\frac{1}{mb^{d}}\int\phi^{2}(\mathbf{u})g(\mathbf{z})d\mathbf{u}+o(\frac{1}{mb^{d}})$
(26)
$\displaystyle=\frac{1}{mb^{d}}g(\mathbf{z})\int\phi^{2}(\mathbf{u})d\mathbf{u}+o(\frac{1}{mb^{d}})\leq
C_{\phi,v}\frac{1}{mb^{d}}.$ (27)

for some constant $C_{\phi,v}$.

As a result, for any $\mathbf{z}\in\mathcal{Z}$, we have the MSE as:

$\displaystyle\mathbb{E}[\|\hat{g}(\mathbf{z})-g(\mathbf{z})\|^{2}]$
$\displaystyle=\mathbb{E}[\|\hat{g}(\mathbf{z})-\mathbb{E}[\hat{g}(\mathbf{z})]+\mathbb{E}[\hat{g}(\mathbf{z})]-g(\mathbf{z})\|^{2}]$
(28)
$\displaystyle=\mathbb{E}[\|\hat{g}(\mathbf{z})-\mathbb{E}[\hat{g}(\mathbf{z})]\|^{2}]+\mathbb{E}[\|\mathbb{E}[\hat{g}(\mathbf{z})]-g(\mathbf{z})\|^{2}]$
(29)
$\displaystyle=\underbrace{Var(\hat{g}(\mathbf{z}))}_{variance}+\underbrace{(\mathbb{E}[\hat{g}(\mathbf{z})]-g(\mathbf{z}))^{2}}_{bias^{2}}$
(30) $\displaystyle\leq C_{\phi,v}\frac{1}{mb^{d}}+C_{\phi,b}b^{4}.$ (31)

This means the MSE goes to $0$ as long as $b^{d}m\to\infty$ and $b\to 0$. As
$m\to\infty$, we have
$\lim_{m\to\infty}\mathbb{E}[\|\hat{g}(\mathbf{z})-g(\mathbf{z})\|^{2}]=0$.

Now, note that $\hat{g}(\mathbf{z})=\frac{1}{m}\sum_{j=1}^{m}V_{j}$ where
$V_{j}=\frac{1}{b^{d}}\phi(\frac{\mathbf{z}-Z_{j}}{b})$. By Bernstein’s
inequality, we have

$\displaystyle\mathbf{P}\\{|\hat{g}(\mathbf{z})-\mathbb{E}[\hat{g}(\mathbf{z})]|>\epsilon\\}\leq
2e^{-\frac{(m\epsilon^{2})/2}{mC_{\phi,v}b^{-d}+\frac{1}{3}m\epsilon\phi(0)b^{-d}}}\leq
e^{-Bmb^{d}\epsilon^{2}}$ (32)

for some constant $B$ as long as $\epsilon$ is smaller than a constant (say
$1$). With triangular inequality, we have

$\displaystyle\mathbf{P}\\{|\hat{g}(\mathbf{z})-g(\mathbf{z})|>\epsilon+C_{\phi,b}b^{2}\\}$
$\displaystyle\leq\mathbf{P}\\{|\hat{g}(\mathbf{z})-\mathbb{E}[\hat{g}(\mathbf{z})]|>\epsilon\\}\leq
e^{-Bmb^{d}\epsilon^{2}}$ (33)

which gives us the conclusion as the RHS goes to $0$ as $m\to\infty$.

###  A.3 Proof of Lemma 3.2

Lemma 3.2 says that $b=\Theta(m^{-\frac{1}{d+4}})$ is the optimal shrinkage
rate to minimize $\mathbb{E}[\|\hat{g}(\mathbf{z})-g(\mathbf{z})\|^{2}]$.
Following Eq. (31), by letting $C_{\phi,b}\frac{1}{mb^{d}}=C_{\phi,v}b^{4}$,
we get $b=\Theta(m^{-\frac{1}{d+4}})$. We can also derive this formula by
taking the derivative of Eq. (31) with respect to $b$ and setting it to $0$,
which gives us (asymptotically):

$\displaystyle\frac{-dC_{\phi,b}}{m}b^{-(d+1)}+4C_{\phi,v}b^{3}=0\Rightarrow
b^{*}=C^{\prime}m^{-\frac{1}{d+4}}$ (34)

for some constant $C^{\prime}$. The optimal MSE is thus
$O(m^{-\frac{4}{d+4}})$.

###  A.4 Proof of Theorem 3.3

Denote $m\vcentcolon=\min_{k}\\{m_{k}\\}$. $\forall k\in[K]$, Bernstein’s
inequality666 One could apply Bennett’s inequality to get:
$\displaystyle\mathbb{P}\\{|\hat{\pi}_{k}-\pi_{k}|\geq\epsilon_{1}\\}$
$\displaystyle\leq
e^{-N\frac{\pi_{k}}{1-\pi_{k}}h(\frac{\epsilon_{1}}{\pi_{k}})}+e^{-N\frac{1-\pi_{k}}{\pi_{k}}h(\frac{\epsilon_{1}}{1-\pi_{k}})}$
(35) and repeat the following proof for a slightly tigher bound. However, the
notation is much more complicated.  gives us:

$\displaystyle\mathbb{P}\\{|\hat{\pi}_{k}-\pi_{k}|\geq\epsilon_{1}\\}$
$\displaystyle\leq
2e^{-\frac{N\epsilon_{1}^{2}}{2v_{min}+\frac{2}{3}\epsilon_{1}}}\leq
e^{-B_{2}N\epsilon_{1}^{2}}$ (36)

where $v_{min}=\min_{k}\\{\pi_{k}(1-\pi_{k})\\}$ and some constant $B_{2}$ (we
find the smallest such constant among all classes), as long as $\epsilon_{1}$
is smaller than a constant (e.g. 1).

From Eq. 33, with $b=C^{\prime}m^{\frac{-1}{d+4}}$, and let
$\epsilon=m^{\frac{-\lambda}{d+4}}$ for $\lambda\in(0,2)$, we have, for some
constants $C_{1},B_{1}$:

$\displaystyle\mathbb{P}\\{|\hat{g}(\mathbf{z})-g(\mathbf{z})|>C_{1}m^{\frac{-\lambda}{d+4}}\\}\leq
e^{-B_{1}m^{\frac{4-2\lambda}{d+4}}}.$ (37)

Define
$\delta_{k}\vcentcolon=e^{-B_{1}m_{k}^{\frac{4-2\lambda}{d+4}}}+e^{-B_{2}N\epsilon_{1}^{2}}\leq
e^{-B_{1}m^{\frac{4-2\lambda}{d+4}}}+e^{-B_{2}N\epsilon_{1}^{2}}$. With
probability $\geq 1-\sum_{k}\delta_{k}$ (union bound), for all $k$:

$\displaystyle|\hat{g}_{k}(\mathbf{z})\hat{\pi}_{k}-g_{k}(\mathbf{z})\pi_{k}|$
$\displaystyle\leq|\hat{g}_{k}(\mathbf{z})\hat{\pi}_{k}-g_{k}(\mathbf{z})\hat{\pi}_{k}|+|g_{k}(\mathbf{z})\hat{\pi}_{k}-g_{k}(\mathbf{z})\pi_{k}|$
(38) $\displaystyle\leq
C_{1}m_{k}^{\frac{-\lambda}{d+4}}+g_{k}(\mathbf{z})\epsilon_{1}.$ (39)

Denote
$g^{+}(\mathbf{z})=\max_{k}g_{k}(\mathbf{z}),g^{-}(\mathbf{z})=\min_{k}g_{k}(\mathbf{z})$,
and $\overline{g}(\mathbf{z})=\sum_{k}g_{k}(\mathbf{z})\pi_{k}$. Denote
$\epsilon_{k,2}\vcentcolon=C_{1}m_{k}^{\frac{-\lambda}{d+4}}$, Eq. 39 means:

$\displaystyle\hat{p}_{k}(\mathbf{z})$
$\displaystyle=\frac{\hat{g}_{k}(\mathbf{z})\hat{\pi}_{k}}{\sum_{k^{\prime}}\hat{g}_{k^{\prime}}(\mathbf{z})\hat{\pi}_{k^{\prime}}}\geq\frac{g_{k}(\mathbf{z})\pi_{k}-\epsilon_{k,2}-g_{k}(\mathbf{z})\epsilon_{1}}{\overline{g}(\mathbf{z})+\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}$
(40)
$\displaystyle=\frac{g_{k}(\mathbf{z})\pi_{k}-\epsilon_{k,2}-g_{k}(\mathbf{z})\epsilon_{1}}{\overline{g}(\mathbf{z})}\frac{1}{1+\frac{\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}{\overline{g}(\mathbf{z})}}$
(41)
$\displaystyle\geq\frac{g_{k}(\mathbf{z})\pi_{k}-\epsilon_{k,2}-g_{k}(\mathbf{z})\epsilon_{1}}{\overline{g}(\mathbf{z})}(1-\frac{\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}{\overline{g}(\mathbf{z})})$
(42) $\displaystyle\geq
p_{k}(\mathbf{z})-\frac{\epsilon_{k,2}+g_{k}(\mathbf{z})\epsilon_{1}}{\overline{g}(\mathbf{z})}-\frac{\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}{\overline{g}(\mathbf{z})}$
(43)

Similarly,

$\displaystyle\hat{p}_{k}(\mathbf{z})$
$\displaystyle\leq\frac{g_{k}(\mathbf{z})\pi_{k}+\epsilon_{k,2}+g_{k}(\mathbf{z})\epsilon_{1}}{\overline{g}(\mathbf{z})}\frac{1}{1-\frac{\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}{\overline{g}(\mathbf{z})}}$
(44)
$\displaystyle\leq(p_{k}(\mathbf{z})+\frac{\epsilon_{k,2}+g_{k}(\mathbf{z})\epsilon_{1}}{\overline{g}(\mathbf{z})})(1+2\frac{\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}{\overline{g}(\mathbf{z})})$
(45) $\displaystyle\leq
p_{k}(\mathbf{z})+\frac{\epsilon_{k,2}+g_{k}(\mathbf{z})\epsilon_{1}}{\overline{g}(\mathbf{z})}+\frac{3\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}{\overline{g}(\mathbf{z})}$
(46)

We can proceed from Eq.44 to 45 and from 45 to 46 when
$\frac{\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}{\overline{g}(\mathbf{z})}\leq
0.5$ , which is achievable for a large $m$ (the smallest $m_{k}$, thus $N$)
given any $\mathbf{z}$ as long as $\overline{g}(\mathbf{z})>0$. .

With Eq. 43 and 46, with probability $\geq
1-K(e^{-B_{1}m^{\frac{4-2\lambda}{d+4}}}+e^{-B_{2}N\epsilon_{1}^{2}})$:

$\displaystyle|p_{k}(\mathbf{z})-\hat{p}_{k}(\mathbf{z})|$
$\displaystyle\leq\frac{(3K+1)(\epsilon_{k,2}+g^{+}(\mathbf{z})\epsilon_{1})}{\overline{g}(\mathbf{z})}$
(47)
$\displaystyle=\frac{(3K+1)(C_{1}m^{\frac{-\lambda}{d+4}}+g^{+}(\mathbf{z})\epsilon_{1})}{\overline{g}(\mathbf{z})}$
(48)

If we let $\epsilon_{1}=\Theta(m^{\frac{-\lambda}{d+4}})$ and merge the
constants, we have, with probability $\geq
1-Ke^{-Bm^{\frac{4-2\lambda}{d+4}}}$ (note that $N\geq Km$):

$\displaystyle|p_{k}(\mathbf{z})-\hat{p}_{k}(\mathbf{z})|$
$\displaystyle\leq(3K+1)Cm^{\frac{-\lambda}{d+4}}$ (49)
$\displaystyle\implies|\mathbf{p}(\mathbf{z})-\hat{\mathbf{p}}(\mathbf{z})|_{1}$
$\displaystyle\leq K(3K+1)Cm^{\frac{-\lambda}{d+4}}$ (50)

with some constant $C$ and $B$ that depends on
$\\{g_{k}(\mathbf{z})\\}_{k\in[K]}$.

###  A.5 Proof of Theorem 3.4

If we assume $g_{k}$ is $\alpha$-Hölder continuous for all $k$ then by Theorem
2 in Jiang (2017), there exists positive constant $C^{\prime}$ independent of
$b$ and $m$, such that the following holds with probability $\geq
1-\frac{1}{m_{k}}$

$\displaystyle\sup_{\mathbf{z}}|\hat{g}_{k}(\mathbf{z})-g_{k}(\mathbf{z})|<C^{\prime}\Big{(}b^{\alpha}+\sqrt{\frac{\log{m_{k}}}{m_{k}b^{d}}}\Big{)}.$
(51)

Furthermore, we assume that all the densities are bounded from below (see, for
example, Section 3 in Gadat et al. (2016)). Denote
$U\vcentcolon=\max_{k}\sup_{\mathbf{z}}g_{k}(\mathbf{z})$ and
$L\vcentcolon=\min_{k}\inf_{\mathbf{z}}g_{k}(\mathbf{z})$.

We could replace $\epsilon_{k,2}$ in the previous section with
$\epsilon_{k,2}=C_{1}(b^{\alpha}+\sqrt{\frac{\log{m_{k}}}{m_{k}b^{d}}})$.
Following similar steps leading towards Eq. 43 and Eq. 46, we have, with
probability $\geq 1-K(\frac{1}{m}+e^{-B_{2}N\epsilon_{1}^{2}})$, for any
$\mathbf{z}$:

$\displaystyle|\hat{p}_{k}(\mathbf{z})-p_{k}(\mathbf{z})|$
$\displaystyle\leq\frac{(3K+1)(\epsilon_{k,2}+g^{+}(\mathbf{z})\epsilon_{1})}{\overline{g}(\mathbf{z})}$
(52)
$\displaystyle\leq\frac{(3K+1)}{L}\Big{(}C_{1}(b^{\alpha}+\sqrt{\frac{\log{m}}{mb^{d}}})+U\epsilon_{1}\Big{)}$
(53)

Note that we still need
$\frac{\sum_{k^{\prime}}[\epsilon_{k^{\prime},2}+g_{k^{\prime}}(\mathbf{z})\epsilon_{1}]}{\overline{g}(\mathbf{z})}\leq
0.5$, which is satisfied as $N$ increases because $g_{k}(\mathbf{z})>=L$. Now,
we let $b=\Theta((\frac{\log{m}}{m})^{\frac{1}{d+2\alpha}})$, and
$\epsilon_{1}=\Theta((\frac{\log{m}}{m})^{\frac{\alpha}{d+2\alpha}})$, we have
with probability $\geq
1-K(m^{-1}+e^{-Bm^{\frac{d}{d+2\alpha}}(\log{m})^{\frac{2\alpha}{d+2\alpha}}})=1-K(m^{-1}+m^{-B\frac{2\alpha}{d+2\alpha}m^{\frac{d}{d+2\alpha}}})$:

$\displaystyle|\hat{p}_{k}(\mathbf{z})-p_{k}(\mathbf{z})|$
$\displaystyle\leq(3K+1)C(\frac{\log{m}}{m})^{\frac{\alpha}{d+2\alpha}}.$ (54)

Finally, with probability $\geq
1-K(m^{-1}+m^{-B\frac{2\alpha}{d+2\alpha}m^{\frac{d}{d+2\alpha}}})$, for any
$\mathbf{q}$ in $\Delta^{K-1}$:

$\displaystyle\sup_{\mathbf{z}:\hat{\mathbf{p}}(\mathbf{z})=\mathbf{q}}|\mathbb{P}\\{Y=k|\hat{\mathbf{p}}(\mathbf{z})=\mathbf{q}\\}-q_{k}|=\sup_{\mathbf{z}:\hat{\mathbf{p}}(\mathbf{z})=\mathbf{q}}|p_{k}(\mathbf{z})-\hat{p}_{k}(\mathbf{z})|\leq\sup_{\mathbf{z}}|p_{k}(\mathbf{z})-\hat{p}_{k}(\mathbf{z})|\leq(3K+1)C(\frac{\log{m}}{m})^{\frac{\alpha}{d+2\alpha}}.$
(55)

##  Appendix B Theoretical Analysis of Equal-sized Stratified Sampling in
Training

We adopted equal-sized stratified sampling to facilitate efficient training.
Here we provide some theoretical justification of this choice.

After fixing a $x_{0}$ whose label $y_{0}$ is the prediction target, the
problem is essentially estimating
$\frac{\mu_{k}p_{k}}{\sum_{k^{\prime}}\mu_{k^{\prime}}p_{k^{\prime}}}$ for all
$k$, where $p_{k}$ denotes the frequency of class $k$ in the population777In
our case, this population is the large training set. and $\mu_{k}$ denotes
$\mathbb{E}[\phi(X,x_{0})|Y=k]$. Note that we know $p_{k}$, but not $\mu_{k}$,
since $p_{k}$ is fixed for our training set, but $\mu_{k}$ depends on $x_{0}$
and $\mathbf{\Pi}$, which is what we are training. Suppose we can afford to
use $M$ samples in total to make the prediction, the question is: How do we
distribute these $M$ samples to different classes?

What sampling method to use will depend on many factors, although a stratified
sampling strategy tends to be more efficient in sample size. The sampling
method we use (sample the same number of samples for each class $k$)
intuitively will improve the estimation quality of the rarer class. Here, we
will elaborate why we chose this sampling method, the assumptions behind it,
and why it helps training.

Denoting $S_{k}=\mu_{k}p_{k}$ and $S_{-k}=\sum_{k^{\prime}\neq
k}\mu_{k^{\prime}}p_{k^{\prime}}$, we can apply Taylor expansion to get an
approximation of the variance888Such a derivation could be found in
https://www.stat.cmu.edu/~hseltman/files/ratio.pdf:

$\displaystyle Var(\frac{S_{k}}{S_{-k}+S_{k}})$
$\displaystyle\approx\frac{1}{\mathbb{E}[S_{-k}+S_{k}]^{2}}Var(S_{k})-2\frac{\mathbb{E}[S_{k}]}{\mathbb{E}[S_{-k}+S_{k}]^{3}}Cov(S_{k},S_{-k}+S_{k})$
(56)
$\displaystyle+\frac{\mathbb{E}[S_{k}]^{2}}{\mathbb{E}[S_{-k}+S_{k}]^{4}}Var(S_{-k}+S_{k})$
(57)

If we perform stratified sampling of any kind, then $Cov(S_{k},S_{-k})=0$, and
Eq. (57) becomes:

$\displaystyle Var(\frac{S_{k}}{S_{-k}+S_{k}})$
$\displaystyle\approx\frac{1}{\mathbb{E}[S_{-k}+S_{k}]^{2}}Var(S_{k})-2\frac{\mathbb{E}[S_{k}]}{\mathbb{E}[S_{-k}+S_{k}]^{3}}Var(S_{k})$
(58)
$\displaystyle+\frac{\mathbb{E}[S_{k}]^{2}}{\mathbb{E}[S_{-k}+S_{k}]^{4}}[Var(S_{-k})+Var(S_{k})]$
(59)
$\displaystyle=\frac{\mathbb{E}[S_{k}]^{2}}{\mathbb{E}[S_{-k}+S_{k}]^{4}}\Bigg{(}\Bigg{[}\frac{\mathbb{E}[S_{-k}]}{\mathbb{E}[S_{k}]}\Bigg{]}^{2}Var(S_{k})+Var(S_{-k})\Bigg{)}$
(60)

To further analyze Eq. (60) and gain more intuition, we make the following
assumptions:

  * •

For any $k^{\prime}\neq y_{0}$, $\mu_{k^{\prime}}$ has the same value denoted
as $\mu_{-y_{0}}$ (and is smaller than $\mu_{y_{0}}$). Intuitively, this is
like considering a one-vs-rest classification problem, and we are just saying
data from the same class will look more similar according to our kernel.

  * •

The standard deviation for a single observation is directly proportional to
the mean. Namely, for all $k$,
$\displaystyle\frac{\sqrt{Var(\phi(X,x_{0})|Y=k)}}{\mathbb{E}[\phi(X,x_{0})|Y=k]}\equiv
r$ for a fixed number $r$.

If we assign $m_{k}$ samples to estimate $\mu_{k}$ then we have
$Var(S_{k})=r^{2}\frac{\mathbb{E}[S_{k}]^{2}}{m_{k}}$ and
$Var(S_{-k})=r^{2}\frac{\mathbb{E}[S_{-k}]^{2}}{M-m_{k}}$, where
$M=\sum_{k^{\prime}=1}^{K}m_{k^{\prime}}$ ($M\gg m_{k}$ when $K$ is large).
This transforms Eq. (60) into:

$\displaystyle
Var\Bigg{(}\frac{S_{k}}{S_{-k}+S_{k}}\Bigg{)}\approx\frac{\mathbb{E}[S_{k}]^{2}\mathbb{E}[S_{-k}]^{2}}{\mathbb{E}[S_{-k}+S_{k}]^{4}}r^{2}\Bigg{(}\frac{1}{m_{k}}+\frac{1}{M-m_{k}}\Bigg{)}=C\Bigg{(}\frac{1}{m_{k}}+\frac{1}{M-m_{k}}\Bigg{)}$
(61)

where $C$ is a constant that does not depend on $m_{k}$.

Without prior information, it is natural to assume $C$ is class-independent
(or at least relatively constant across classes). Now, if our goal is to
minimize the average variance, by Cauchy-Schwarts inequality we have:

$\displaystyle\sum_{k=1}^{K}\frac{1}{m_{k}}$
$\displaystyle\geq\frac{K^{2}}{M}$ (62)
$\displaystyle\sum_{k=1}^{K}\frac{1}{M-m_{k}}$
$\displaystyle\geq\frac{K^{2}}{(K-1)M}$ (63)

The equality in both cases is achieved if and only if $m_{k}\equiv\frac{M}{K}$
for all $k$. This means, to minimize the average variance
$\frac{C}{K}\sum_{k=1}^{K}(\frac{1}{m_{k}}+\frac{1}{M-m_{k}})$, we need to
choose $m_{k}$ to be the same for all class $k$.

It is worth noting that the discussion above is about training (and how to get
better estimation therein). This is not referring to errors of the final
$\mathbf{\Pi}$. Given enough time, different ways to sample data lead to
similar performance.

##  Appendix C Additional Experimental Details

###  C.1 Datasets

This section provides more detail on the healthcare datasets, which might be
less familiar to readers.

IIIC (Jing et al., 2021; Ge et al., 2021) is an electroencephalography (EEG)
dataset from the Massachusetts General Hospital EEG Archive. It is collected
for the purpose of automated ictal-interictal-injury-continuum (IIIC)
detection/monitoring. IIIC patterns include seizure and seizure-like patterns
designated Lateralized Periodic Discharges (LPDs), Generalized Periodic
Discharges (GPDs), Lateralized Rhythmic Delta Activity (LRDA), and Generalized
Rhythmic Delta Activity (GRDA)(Ge et al., 2021). The training data has been
enriched with “label spreading” (Ge et al., 2021), whereas the test (and
calibration) data consists of only labels from medical experts. To improve
stability (because IIIC labeling is a challenging task for even experts), any
sample with less than 3 labels are dropped. The majority label is then used as
the truth for the test and calibration ses. For more details on how the data
was collected and labeled, please refer to Jing et al. (2021); Ge et al.
(2021).

ISRUC (Khalighi et al., 2016) is a public polysomnographic (PSG) dataset for
the sleep staging task. It has three groups of data, with the first group
having the most data and most widely used. The (group 1) dataset contains 100
subjects with one recording session per subject. Every 30 second of the
recording is considered an “epoch” and is rated independently by two human
experts. We use the label from the first expert as the gold label. The five
classes of ISRUC correspond to five different stages of sleep, including Rapid
Eye Movement (REM), Non-REM Stage 1 (N1), Non-REM Stage 2 (N2), Non-REM Stage
3 (N3), and Wake (Wake). For more details, please refer to Khalighi et al.
(2016).

PhysioNet Callenge 2017 (PN2017) (Clifford et al., 2017; Goldberger et al.,
2000) is a public (upon request) electrocardiogram (ECG) dataset for ECG
rhythm classification. The ECG recordings are sampled at 300Hz. The original
dataset contains four classes: Normal sinus rhythm (N), Atrial Fibrillation
(AF), Other cardiac rhythms (O) and Noise segment. Among these patterns, AF is
an abnormal heart rhythm, and is the “important class”. We used the same
processing method as Hong et al. (2019), which cuts one segment into several
shorter segments with data augmentation during the training phase.

A summary of the classes can be found below in Table 7.

Table 7:  Additional information about the healthcare datasets used in this
paper.

| IIIC | ISRUC | PN2017
---|---|---|---
Dataset | Name | Train | Cal+Test | Name | Train | Cal+Test | Name | Train | Cal+Test
Class 0 | Other | 42228 | 6852 | Wake | 14325 | 6433 | Normal | 8877 | 2893
Class 1 | Seizure | 3305 | 549 | N1 | 7589 | 3798 | Other | 4524 | 1579
Class 2 | LPD | 17338 | 7589 | N2 | 19501 | 8505 | AF | 1345 | 449
Class 3 | GPD | 16983 | 9737 | N3 | 12012 | 5254 | Noisy | 341 | 145
Class 4 | LRDA | 12515 | 5946 | REM | 8414 | 3452 | – | – | –
Class 5 | GRDA | 11449 | 5067 | – | – | – | – | – | –

Data Licenses and Consent:

  * •

ISRUC: We could not find the license. Per Khalighi et al. (2016), “All
patients referred were submitted to an initial briefing with the support of an
informed consent document. The ethics committee of CHUC approved the use of
the data of the referred patients as anonymous for the research purposes”.

  * •

PN2017: The license is Open Data Commons Attribution License v1.0. The dataset
is donated by AliveCor.

  * •

IIIC: We could not find the license. Per Jing et al. (2021) “the local IRB
waived the requirement for informed consent for this retrospective analysis of
EEG data”.

  * •

CIFAR-100/CIFAR-10: We could not find the license. They are publicly
available.

  * •

SVHN: Under CC0: Public Domain license. It is publicly available.

###  C.2 Baseline Implementation

  * •

Temperature Scaling: We used the github repository accompanying Guo et al.
(2017), https://github.com/gpleiss/temperature_scaling.

  * •

Dirichlet Calibration: We used the code at
https://github.com/dirichletcal/experiments_dnn.

  * •

Focal Loss (Mukhoti et al., 2020): We used the loss function and the gamma
schedule provided in https://github.com/torrvision/focal_calibration, and
replaced our CrossEntropy loss function in all experiments during training.

  * •

Mutual-information-maximization-based Binning (I-Max): We use the official
github implementation https://github.com/boschresearch/imax-calibration. To
normalize and get valid probability vectors, we used softmax on the log-odds
given by I-Max.

  * •

Gaussian Process Calibration: We use the official github implementation
https://github.com/JonathanWenger/pycalib.

  * •

Splines-based Calibration: We use the official github implementation
https://github.com/kartikgupta-at-anu/spline-calibration.

  * •

Intra Order-preserving Calibration: We use the official github implementation
https://github.com/AmirooR/IntraOrderPreservingCalibration.

  * •

MMCE: We use the official github implementation
https://github.com/aviralkumar2907/MMCE with additional temperature scaling on
the calibration set as suggested in the original paper.

###  C.3 Training Details

For CIFAR-10, CIFAR-100, SVHN, and ISRUC, the models are trained for 50
epochs, using a one-cycle Cosine scheduler with 3 warm-up and 10 cool-down
epochs (the other parameters are default in timm). The exact ViT and Mixer are
vit_base_patch16_224_in21k and mixer_b16_224_in21k implemented and pretrained
by timm . For PN2017, the number of epochs is 100, and we use a
ReduceLROnPlateau scheduler that halves the learning rate with the patience
parameter set to 10 epochs. We use a batch size of 128, SGD optimizer and
weight decay rate of 1e-4. For IIIC dataset, we use a AdamW optimizer with a
weight decay rate of 1e-5, and no scheduler. The learning rates are 2e-4 for
CIFAR-10, CIFAR-100 and SVHN, 5e-3 for ISRUC, 1e-2 for PN2017 and 1e-3 for
IIIC. For all datasets except for IIIC, we used LabelSmoothingCrossEntropy in
timm with smoothing being 0.1. For IIIC, since the original dataset contains
pseudo-labels that form a distribution, we use a cross entropy loss. The
experiments for the Focal baseline replace all loss functions with the
proposed focal loss.

To train $\mathbf{\Pi}$, we use an SGD optimizer with a learning rate of 4e-4
for CIFAR-10, CIFAR-100, SVHN and IIIC, 1e-3 for ISRUC and PN2017. We use
ReduceLROnPlateau scheduler that halves the learning rate with the patience
parameter set to 10 epochs, and trains for 100 epochs. Each epoch has a fixed
number of 5000 batches (regardless of the size of the training set) and each
batch consists of $B=64$ prediction samples and a “background” set used to
construct KDE with $m_{k}\equiv m=20$ for all $k$. The exact details could be
found in our code. Training time for the largest dataset (except for
ImageNet), SVHN, is 3 hours for the base neural network, and 1 hour for
$\mathbf{\Pi}$ on a machine with Nvidia RTX 3090 GPU. Inference time is much
shorter.

###  C.4 Additional Evaluation Metrics

In this section, we compute the following variants of the evaluation metrics
presented in the main text. The conclusion stays very similar across all
methods.

  * •

The static (equal-width bins) version of CECE, in Table 8.

  * •

The static (equal-width bins) version of ECE, in Table 9.

  * •

The multi-class version of Brier score, in Table 10. To be specific, the brier
score in the main text is
$\frac{1}{N}\sum_{i=1}^{N}(\hat{\mathbf{p}}_{k_{i}^{*}}(x_{i})-\mathbbm{1}\\{y_{i}=k_{i}^{*}\\})^{2}$
where $k_{i}^{*}=\operatorname*{arg\,max}_{k}\hat{\mathbf{p}}_{k}(x_{i})$. The
multi-class version of Brier score is
$\frac{1}{NK}\sum_{i=1}^{N}\sum_{k=1}^{K}(\hat{\mathbf{p}}_{k}(x_{i})-\mathbbm{1}\\{y_{i}=k\\})^{2}$.

  * •

NLL Loss, in Table 11.

Table 8: (Static) Class-wise ECE in $10^{-2}$ ($\downarrow$ means
lower=better). The best accuracy-preserving method is in bold (p=0.01). The
otherwise lowest number is underscored. KCal almost always achieves the lowest
class-wise ECE, while maintaining accuracy.

CECE $\downarrow$ |  UnCal |  TS |  DirCal |  I-Max |  Focal |  Spline |  IOP |  GP |  MMCE |  KCal
---|---|---|---|---|---|---|---|---|---|---
IIIC (pat) |  8.01$\pm$0.27 |  8.94$\pm$0.86 |  5.11$\pm$1.49 |  9.17$\pm$0.99 |  8.95$\pm$0.52 |  8.55$\pm$0.63 |  8.30$\pm$0.53 |  7.94$\pm$0.65 |  7.09$\pm$0.44 |  4.66$\pm$1.30
IIIC |  7.89$\pm$0.02 |  8.96$\pm$0.50 |  2.13$\pm$0.13 |  8.77$\pm$0.24 |  8.76$\pm$0.02 |  8.41$\pm$0.23 |  7.97$\pm$0.26 |  7.51$\pm$0.24 |  6.66$\pm$0.26 |  2.04$\pm$0.27
ISRUC (pat) |  4.51$\pm$0.25 |  4.68$\pm$0.77 |  4.19$\pm$0.89 |  8.65$\pm$0.99 |  9.24$\pm$0.20 |  4.67$\pm$0.46 |  4.59$\pm$0.59 |  4.63$\pm$0.42 |  4.06$\pm$0.35 |  3.84$\pm$1.22
ISRUC |  4.53$\pm$0.02 |  5.18$\pm$0.79 |  2.73$\pm$0.38 |  9.29$\pm$0.86 |  9.07$\pm$0.02 |  4.75$\pm$0.16 |  4.69$\pm$0.37 |  4.71$\pm$0.25 |  4.07$\pm$0.21 |  1.93$\pm$0.27
PN2017 |  12.20$\pm$0.07 |  12.32$\pm$0.19 |  4.04$\pm$0.54 |  9.70$\pm$1.19 |  16.70$\pm$0.10 |  8.42$\pm$0.73 |  12.10$\pm$0.37 |  12.20$\pm$0.07 |  12.20$\pm$0.32 |  3.83$\pm$1.27
C10 (ViT) |  3.42$\pm$0.01 |  1.39$\pm$0.08 |  1.25$\pm$0.08 |  1.15$\pm$0.06 |  5.19$\pm$0.03 |  1.36$\pm$0.06 |  1.25$\pm$0.07 |  1.23$\pm$0.06 |  1.52$\pm$0.22 |  1.18$\pm$0.08
C10 (Mixer) |  3.36$\pm$0.02 |  2.11$\pm$0.11 |  1.64$\pm$0.08 |  1.76$\pm$0.24 |  7.02$\pm$0.03 |  1.71$\pm$0.09 |  1.78$\pm$0.10 |  1.75$\pm$0.10 |  1.95$\pm$0.27 |  1.59$\pm$0.06
C100 (ViT) |  6.33$\pm$0.05 |  6.43$\pm$0.29 |  5.44$\pm$0.14 |  5.96$\pm$0.21 |  6.07$\pm$0.05 |  5.16$\pm$0.17 |  5.58$\pm$0.14 |  5.54$\pm$0.09 |  5.30$\pm$0.22 |  5.06$\pm$0.11
C100 (Mixer) |  5.60$\pm$0.05 |  6.75$\pm$0.25 |  5.87$\pm$0.20 |  6.64$\pm$0.29 |  6.08$\pm$0.06 |  5.56$\pm$0.13 |  6.09$\pm$0.32 |  5.80$\pm$0.14 |  6.15$\pm$0.21 |  5.16$\pm$0.07
SVHN (ViT) |  3.50$\pm$0.01 |  2.56$\pm$0.58 |  1.40$\pm$0.06 |  2.98$\pm$0.22 |  6.11$\pm$0.02 |  1.51$\pm$0.07 |  1.47$\pm$0.07 |  1.51$\pm$0.05 |  1.63$\pm$0.11 |  1.46$\pm$0.08
SVHN (Mixer) |  3.36$\pm$0.02 |  3.38$\pm$0.67 |  1.39$\pm$0.11 |  3.00$\pm$0.16 |  5.79$\pm$0.02 |  1.66$\pm$0.07 |  1.54$\pm$0.06 |  1.58$\pm$0.06 |  1.73$\pm$0.09 |  1.57$\pm$0.11
ImageNet |  3.70$\pm$0.03 |  3.99$\pm$0.07 |  6.11$\pm$0.22 |  3.29$\pm$0.21 |  – |  2.80$\pm$0.07 |  2.93$\pm$0.16 |  3.05$\pm$0.08 |  – |  2.40$\pm$0.04

Table 9: (Static) ECE in $10^{-2}$ ($\downarrow$ means lower=better). The best
accuracy-preserving method is in bold (p=0.01). KCal is usually on par or
better than the best baseline.

ECE $\downarrow$ | UnCal | TS | DirCal | I-Max | Focal | Spline | IOP | GP | MMCE | KCal
---|---|---|---|---|---|---|---|---|---|---
IIIC (pat) | 9.18$\pm$1.08 | 4.95$\pm$2.77 | 2.87$\pm$1.62 | 10.56$\pm$4.05 | 7.37$\pm$0.53 | 4.54$\pm$2.07 | 4.56$\pm$2.15 | 3.84$\pm$1.63 | 6.34$\pm$3.30 | 4.28$\pm$1.42
IIIC | 9.13$\pm$0.04 | 4.42$\pm$1.53 | 1.22$\pm$0.17 | 10.17$\pm$0.81 | 7.10$\pm$0.04 | 3.08$\pm$0.65 | 3.44$\pm$0.38 | 1.68$\pm$0.55 | 4.78$\pm$2.26 | 2.55$\pm$0.61
ISRUC (pat) | 3.60$\pm$0.32 | 2.70$\pm$1.56 | 2.91$\pm$1.02 | 8.82$\pm$1.41 | 14.95$\pm$0.40 | 1.99$\pm$0.36 | 2.40$\pm$1.43 | 1.94$\pm$0.62 | 2.09$\pm$0.97 | 2.74$\pm$1.29
ISRUC | 3.46$\pm$0.06 | 3.81$\pm$1.67 | 2.20$\pm$0.68 | 9.58$\pm$1.26 | 14.76$\pm$0.05 | 1.48$\pm$0.55 | 2.69$\pm$0.94 | 2.04$\pm$0.76 | 2.08$\pm$1.06 | 1.34$\pm$0.41
PN2017 | 17.10$\pm$0.14 | 17.34$\pm$0.42 | 5.46$\pm$0.66 | 8.97$\pm$1.85 | 24.65$\pm$0.13 | 6.10$\pm$2.22 | 16.55$\pm$2.03 | 17.13$\pm$0.15 | 13.21$\pm$1.08 | 4.56$\pm$1.41
C10 (ViT) | 9.17$\pm$0.05 | 0.76$\pm$0.11 | 0.44$\pm$0.08 | 0.61$\pm$0.06 | 7.19$\pm$0.06 | 0.49$\pm$0.10 | 0.38$\pm$0.05 | 0.28$\pm$0.07 | 0.65$\pm$0.15 | 0.41$\pm$0.10
C10 (Mixer) | 9.06$\pm$0.05 | 1.11$\pm$0.12 | 0.51$\pm$0.05 | 1.04$\pm$0.17 | 12.54$\pm$0.06 | 0.48$\pm$0.08 | 0.56$\pm$0.12 | 0.34$\pm$0.06 | 1.01$\pm$0.40 | 0.65$\pm$0.09
C100 (ViT) | 11.65$\pm$0.14 | 2.81$\pm$0.44 | 0.77$\pm$0.12 | 3.39$\pm$0.23 | 9.98$\pm$0.09 | 1.07$\pm$0.24 | 1.24$\pm$0.27 | 0.92$\pm$0.12 | 1.21$\pm$0.36 | 1.58$\pm$0.33
C100 (Mixer) | 13.71$\pm$0.15 | 3.18$\pm$0.35 | 1.17$\pm$0.26 | 4.82$\pm$0.25 | 14.36$\pm$0.20 | 1.20$\pm$0.35 | 1.82$\pm$0.72 | 1.15$\pm$0.22 | 2.14$\pm$0.49 | 3.11$\pm$0.48
SVHN (ViT) | 10.11$\pm$0.05 | 2.44$\pm$2.72 | 0.61$\pm$0.09 | 2.08$\pm$0.18 | 12.17$\pm$0.08 | 0.64$\pm$0.14 | 0.55$\pm$0.11 | 0.61$\pm$0.10 | 0.66$\pm$0.15 | 0.71$\pm$0.13
SVHN (Mixer) | 10.30$\pm$0.04 | 3.19$\pm$2.55 | 0.57$\pm$0.08 | 2.21$\pm$0.10 | 11.09$\pm$0.06 | 0.67$\pm$0.13 | 0.49$\pm$0.10 | 0.62$\pm$0.08 | 0.69$\pm$0.21 | 0.74$\pm$0.11
ImageNet | 3.06$\pm$0.13 | 3.26$\pm$0.13 | 4.26$\pm$0.74 | 8.05$\pm$0.32 | – | 1.13$\pm$0.15 | 1.38$\pm$0.46 | 0.95$\pm$0.16 | – | 1.30$\pm$0.28

Table 10:  Brier Score (multi-class) in $10^{-2}$ ($\downarrow$ means
lower=better). The best accuracy-preserving methods are in bold (p=0.01).

Brier $\downarrow$ |  UnCal |  TS |  DirCal |  I-Max |  Focal |  Spline |  IOP |  GP |  MMCE |  KCal
---|---|---|---|---|---|---|---|---|---|---
IIIC (pat) |  9.23$\pm$0.18 |  9.11$\pm$0.31 |  8.13$\pm$0.26 |  9.22$\pm$0.44 |  9.69$\pm$0.20 |  9.05$\pm$0.25 |  9.07$\pm$0.27 |  9.01$\pm$0.24 |  9.13$\pm$0.25 |  8.38$\pm$0.36
IIIC |  9.25$\pm$0.01 |  9.10$\pm$0.06 |  7.86$\pm$0.02 |  9.17$\pm$0.05 |  9.68$\pm$0.00 |  9.00$\pm$0.01 |  9.05$\pm$0.03 |  8.95$\pm$0.03 |  9.07$\pm$0.06 |  7.40$\pm$0.04
ISRUC (pat) |  6.84$\pm$0.17 |  6.83$\pm$0.17 |  6.83$\pm$0.21 |  7.15$\pm$0.21 |  7.97$\pm$0.14 |  6.79$\pm$0.17 |  6.82$\pm$0.18 |  6.80$\pm$0.17 |  6.59$\pm$0.14 |  6.67$\pm$0.18
ISRUC |  6.95$\pm$0.02 |  6.97$\pm$0.06 |  6.66$\pm$0.04 |  7.31$\pm$0.11 |  8.07$\pm$0.01 |  6.90$\pm$0.02 |  6.94$\pm$0.04 |  6.90$\pm$0.03 |  6.68$\pm$0.02 |  6.30$\pm$0.03
PN2017 |  14.92$\pm$0.02 |  14.97$\pm$0.11 |  12.85$\pm$0.09 |  14.03$\pm$0.20 |  17.64$\pm$0.01 |  13.78$\pm$0.13 |  14.84$\pm$0.24 |  14.92$\pm$0.02 |  15.26$\pm$0.17 |  12.81$\pm$0.13
C10 (ViT) |  0.27$\pm$0.01 |  0.18$\pm$0.01 |  0.16$\pm$0.01 |  0.17$\pm$0.01 |  0.31$\pm$0.01 |  0.16$\pm$0.01 |  0.16$\pm$0.01 |  0.16$\pm$0.01 |  0.18$\pm$0.01 |  0.15$\pm$0.01
C10 (Mixer) |  0.39$\pm$0.01 |  0.30$\pm$0.01 |  0.30$\pm$0.01 |  0.30$\pm$0.02 |  0.74$\pm$0.01 |  0.29$\pm$0.01 |  0.29$\pm$0.01 |  0.28$\pm$0.01 |  0.30$\pm$0.03 |  0.28$\pm$0.01
C100 (ViT) |  0.14$\pm$0.00 |  0.12$\pm$0.00 |  0.12$\pm$0.00 |  0.12$\pm$0.00 |  0.14$\pm$0.00 |  0.12$\pm$0.00 |  0.12$\pm$0.00 |  0.12$\pm$0.00 |  0.11$\pm$0.00 |  0.11$\pm$0.00
C100 (Mixer) |  0.21$\pm$0.00 |  0.19$\pm$0.00 |  0.18$\pm$0.00 |  0.19$\pm$0.00 |  0.23$\pm$0.00 |  0.18$\pm$0.00 |  0.18$\pm$0.00 |  0.18$\pm$0.00 |  0.17$\pm$0.00 |  0.18$\pm$0.00
SVHN (ViT) |  0.76$\pm$0.01 |  0.65$\pm$0.04 |  0.62$\pm$0.01 |  0.65$\pm$0.01 |  0.95$\pm$0.01 |  0.62$\pm$0.01 |  0.62$\pm$0.01 |  0.62$\pm$0.01 |  0.54$\pm$0.00 |  0.55$\pm$0.01
SVHN (Mixer) |  0.77$\pm$0.01 |  0.68$\pm$0.05 |  0.62$\pm$0.01 |  0.66$\pm$0.01 |  0.97$\pm$0.01 |  0.63$\pm$0.01 |  0.63$\pm$0.01 |  0.63$\pm$0.01 |  0.68$\pm$0.01 |  0.60$\pm$0.01
ImageNet |  0.03$\pm$0.00 |  0.03$\pm$0.00 |  0.03$\pm$0.00 |  0.03$\pm$0.00 |  – |  0.03$\pm$0.00 |  0.03$\pm$0.00 |  0.03$\pm$0.00 |  – |  0.03$\pm$0.00

Table 11:  NLL ($\downarrow$ means lower=better). The best accuracy-preserving
methods are in bold (p=0.01).

NLL $\downarrow$ |  UnCal |  TS |  DirCal |  I-Max |  Focal |  Spline |  IOP |  GP |  MMCE |  KCal
---|---|---|---|---|---|---|---|---|---|---
IIIC (pat) |  1.09$\pm$0.02 |  1.08$\pm$0.05 |  0.97$\pm$0.05 |  1.11$\pm$0.07 |  1.11$\pm$0.03 |  1.07$\pm$0.03 |  1.07$\pm$0.04 |  1.06$\pm$0.03 |  1.07$\pm$0.03 |  1.00$\pm$0.05
IIIC |  1.09$\pm$0.00 |  1.08$\pm$0.01 |  0.92$\pm$0.00 |  1.10$\pm$0.01 |  1.11$\pm$0.00 |  1.06$\pm$0.00 |  1.06$\pm$0.00 |  1.05$\pm$0.00 |  1.06$\pm$0.01 |  0.87$\pm$0.01
ISRUC (pat) |  0.63$\pm$0.02 |  0.62$\pm$0.02 |  0.62$\pm$0.02 |  0.69$\pm$0.03 |  0.72$\pm$0.01 |  0.61$\pm$0.02 |  0.62$\pm$0.02 |  0.61$\pm$0.02 |  0.60$\pm$0.02 |  0.61$\pm$0.02
ISRUC |  0.64$\pm$0.00 |  0.63$\pm$0.01 |  0.60$\pm$0.00 |  0.71$\pm$0.02 |  0.73$\pm$0.00 |  0.63$\pm$0.00 |  0.63$\pm$0.00 |  0.62$\pm$0.00 |  0.61$\pm$0.00 |  0.57$\pm$0.00
PN2017 |  1.00$\pm$0.00 |  1.00$\pm$0.00 |  0.86$\pm$0.01 |  0.96$\pm$0.02 |  1.19$\pm$0.00 |  0.95$\pm$0.01 |  0.99$\pm$0.02 |  1.00$\pm$0.00 |  1.04$\pm$0.03 |  0.86$\pm$0.01
C10 (ViT) |  0.12$\pm$0.00 |  0.05$\pm$0.01 |  0.03$\pm$0.00 |  0.04$\pm$0.00 |  0.10$\pm$0.00 |  0.04$\pm$0.00 |  0.03$\pm$0.00 |  0.03$\pm$0.00 |  0.05$\pm$0.00 |  0.03$\pm$0.00
C10 (Mixer) |  0.15$\pm$0.00 |  0.07$\pm$0.01 |  0.06$\pm$0.00 |  0.07$\pm$0.00 |  0.20$\pm$0.00 |  0.06$\pm$0.00 |  0.06$\pm$0.00 |  0.06$\pm$0.00 |  0.07$\pm$0.02 |  0.06$\pm$0.00
C100 (ViT) |  0.38$\pm$0.00 |  0.29$\pm$0.01 |  0.28$\pm$0.01 |  0.32$\pm$0.01 |  0.36$\pm$0.00 |  0.28$\pm$0.01 |  0.28$\pm$0.01 |  0.27$\pm$0.01 |  0.25$\pm$0.01 |  0.27$\pm$0.00
C100 (Mixer) |  0.54$\pm$0.01 |  0.43$\pm$0.01 |  0.43$\pm$0.01 |  0.47$\pm$0.01 |  0.54$\pm$0.01 |  0.43$\pm$0.01 |  0.43$\pm$0.01 |  0.42$\pm$0.01 |  0.39$\pm$0.01 |  0.44$\pm$0.01
SVHN (ViT) |  0.23$\pm$0.00 |  0.16$\pm$0.02 |  0.15$\pm$0.00 |  0.17$\pm$0.00 |  0.26$\pm$0.00 |  0.15$\pm$0.00 |  0.15$\pm$0.00 |  0.15$\pm$0.00 |  0.13$\pm$0.00 |  0.13$\pm$0.00
SVHN (Mixer) |  0.23$\pm$0.00 |  0.19$\pm$0.03 |  0.15$\pm$0.00 |  0.18$\pm$0.00 |  0.26$\pm$0.00 |  0.16$\pm$0.00 |  0.15$\pm$0.00 |  0.15$\pm$0.00 |  0.16$\pm$0.00 |  0.15$\pm$0.00
ImageNet |  0.84$\pm$0.01 |  0.83$\pm$0.01 |  0.90$\pm$0.02 |  0.87$\pm$0.02 |  – |  0.77$\pm$0.01 |  0.75$\pm$0.01 |  0.75$\pm$0.01 |  – |  0.87$\pm$0.01

###  C.5 Reliability Diagrams

Figure 3, 4, and 5 are the reliability diagrams for the IIIC, ISRUC and PN2017
dataset, respectively. We keep only bins with at least 15 samples, because
otherwise the “gap” is misleading due to small sample and big variance. The
count of samples in each bin is plotted on the right axis (log-scale). The
conclusion is similar. In all cases, TS seems to calibrate the overall ECE but
fails on some classes. DirCal tends to improve on all classes, but KCal
usually closes the gap between actual frequency and the prediction further.

Figure 3:  Reliability diagrams for the IIIC dataset.

Figure 4:  Reliability diagrams for the ISRUC dataset.

Figure 5:  Reliability diagrams for the PN2017 dataset.

##  Appendix D Ablation Study: Linear Projection

A natural first architecture to try for $\mathbf{\Pi}$ is a simple linear
layer. It is however not clear whether a linear projection can learn the best
metric space due to its simplicity. We introduced a mild complexity by having
two layers in $\mathbf{\Pi}$, yet the skip connection should help it learn
well when a linear projection is the most desirable as well.

$\mathbf{f}(X)$LinearELULinear$+$ $\mathbf{\Pi}(\mathbf{f}(X))$ Figure 6:
Structure of the learnable projection $\mathbf{\Pi}$ (in gray).

We empirically compared both versions: KCal, with the architecture showed in
Figure 6, and KCal-Linear, which only uses one linear layer with the same
output dimension ($d$). Both $\mathbf{\Pi}$ normalized $\mathbf{f}(\cdot)$
automatically with a Batch Normalization layer. The results are in Table 12.
As we can see, KCal is generally better than the linear version, but the gap
is generally small. The additional computation time is smaller than 1x the
computation time for KCal-Linear, because the second layer has only $d^{2}$
parameters rather than $hd$ in the first layer ($h>d$). Both have negligible
computation overhead compared with calling $\mathbf{f}$ (see Appendix F).

Table 12:  Comparison between the architecture described in Figure 6 (KCal)
and a simple linear projection with the same input and output dimensions
(KCal-Linear). On average, KCal adapts to different datasets and architectures
better than (KCal-Linear), although the performance is generally similar.

| Accuracy$\uparrow$ | CECE$\downarrow$ | ECE$\downarrow$ | Brier $\downarrow$
---|---|---|---|---
| KCal | KCal-Lienar | KCal | KCal-Lienar | KCal | KCal-Lienar | KCal | KCal-Lienar
IIIC(pat) | 61.67$\pm$2.22 | 61.51$\pm$2.46 | 4.68$\pm$1.27 | 4.68$\pm$1.41 | 4.34$\pm$1.35 | 4.48$\pm$1.99 | 19.33$\pm$0.78 | 19.28$\pm$0.82
IIIC | 66.32$\pm$0.21 | 65.59$\pm$0.20 | 2.03$\pm$0.26 | 2.08$\pm$0.23 | 2.62$\pm$0.59 | 3.12$\pm$0.68 | 17.54$\pm$0.10 | 17.88$\pm$0.09
ISRUC(pat) | 76.13$\pm$0.89 | 76.02$\pm$1.08 | 3.82$\pm$1.24 | 3.96$\pm$1.34 | 2.78$\pm$1.25 | 2.87$\pm$1.53 | 14.97$\pm$0.29 | 15.04$\pm$0.30
ISRUC | 77.45$\pm$0.16 | 77.19$\pm$0.19 | 1.90$\pm$0.28 | 2.01$\pm$0.31 | 1.36$\pm$0.41 | 1.69$\pm$0.46 | 14.28$\pm$0.08 | 14.37$\pm$0.08
PN2017 | 60.36$\pm$0.61 | 60.15$\pm$0.56 | 4.25$\pm$1.26 | 4.21$\pm$1.26 | 4.78$\pm$1.48 | 5.41$\pm$1.14 | 22.56$\pm$0.28 | 22.69$\pm$0.32
C10 (ViT) | 98.98$\pm$0.09 | 98.96$\pm$0.07 | 0.74$\pm$0.07 | 0.72$\pm$0.06 | 0.40$\pm$0.05 | 0.31$\pm$0.06 | 0.75$\pm$0.05 | 0.75$\pm$0.05
C10 (Mixer) | 98.14$\pm$0.06 | 98.12$\pm$0.09 | 1.17$\pm$0.10 | 1.18$\pm$0.07 | 0.59$\pm$0.09 | 0.61$\pm$0.13 | 1.34$\pm$0.04 | 1.34$\pm$0.05
C100 (ViT) | 92.37$\pm$0.15 | 92.47$\pm$0.14 | 4.32$\pm$0.10 | 4.37$\pm$0.08 | 1.50$\pm$0.32 | 1.43$\pm$0.33 | 5.01$\pm$0.08 | 4.93$\pm$0.08
C100 (Mixer) | 87.55$\pm$0.16 | 88.00$\pm$0.24 | 4.62$\pm$0.10 | 4.73$\pm$0.12 | 3.07$\pm$0.49 | 2.78$\pm$0.45 | 7.61$\pm$0.09 | 7.39$\pm$0.07
SVHN (ViT) | 96.42$\pm$0.05 | 96.36$\pm$0.06 | 1.23$\pm$0.10 | 1.32$\pm$0.08 | 0.64$\pm$0.12 | 0.65$\pm$0.09 | 2.49$\pm$0.03 | 2.49$\pm$0.03
SVHN (Mixer) | 96.10$\pm$0.04 | 96.13$\pm$0.04 | 1.40$\pm$0.08 | 1.49$\pm$0.08 | 0.73$\pm$0.10 | 0.61$\pm$0.09 | 2.68$\pm$0.03 | 2.69$\pm$0.03

##  Appendix E Ablation Study: Using the classification logits

We empirically compared using the penultimate-layer embeddings and the
predicted logits in Table 13. As we can see, KCal is generally better than the
alternative that uses the logits.

Table 13:  Comparison between using the penultimate layer embedding vs the
prediction logits as the input to $\mathbf{\Pi}$ (KCal-Logits). Overall, KCal
is significantly better than KCal-Logits, but KCal-Logits also has competitive
performance.

| Accuracy$\uparrow$ | CECE$\downarrow$ | ECE$\downarrow$ | Brier $\downarrow$
---|---|---|---|---
| KCal | KCal-Logits | KCal | KCal-Logits | KCal | KCal-Logits | KCal | KCal-Logits
IIIC(pat) | 61.67$\pm$2.22 | 61.21$\pm$2.66 | 4.68$\pm$1.27 | 4.26$\pm$1.30 | 4.34$\pm$1.35 | 4.02$\pm$1.51 | 19.33$\pm$0.78 | 19.07$\pm$0.77
IIIC | 66.32$\pm$0.21 | 65.26$\pm$0.20 | 2.03$\pm$0.26 | 2.11$\pm$0.27 | 2.62$\pm$0.59 | 2.77$\pm$0.37 | 17.54$\pm$0.10 | 17.90$\pm$0.05
ISRUC(pat) | 76.13$\pm$0.89 | 75.57$\pm$1.02 | 3.82$\pm$1.24 | 3.95$\pm$1.44 | 2.78$\pm$1.25 | 2.75$\pm$1.27 | 14.97$\pm$0.29 | 15.30$\pm$0.31
ISRUC | 77.45$\pm$0.16 | 76.75$\pm$0.12 | 1.90$\pm$0.28 | 1.97$\pm$0.32 | 1.36$\pm$0.41 | 1.62$\pm$0.48 | 14.28$\pm$0.08 | 14.60$\pm$0.09
PN2017 | 60.36$\pm$0.61 | 59.99$\pm$0.56 | 4.25$\pm$1.26 | 4.13$\pm$1.22 | 4.78$\pm$1.48 | 5.18$\pm$0.96 | 22.56$\pm$0.28 | 22.64$\pm$0.34
C10 (ViT) | 98.98$\pm$0.09 | 98.94$\pm$0.06 | 0.74$\pm$0.07 | 0.79$\pm$0.07 | 0.40$\pm$0.05 | 0.43$\pm$0.05 | 0.75$\pm$0.05 | 0.79$\pm$0.04
C10 (Mixer) | 98.14$\pm$0.06 | 98.11$\pm$0.06 | 1.17$\pm$0.10 | 1.21$\pm$0.07 | 0.59$\pm$0.09 | 0.54$\pm$0.06 | 1.34$\pm$0.04 | 1.37$\pm$0.04
C100 (ViT) | 92.37$\pm$0.15 | 91.11$\pm$0.14 | 4.32$\pm$0.10 | 4.67$\pm$0.10 | 1.50$\pm$0.32 | 1.95$\pm$0.37 | 5.01$\pm$0.08 | 5.55$\pm$0.08
C100 (Mixer) | 87.55$\pm$0.16 | 85.07$\pm$0.26 | 4.62$\pm$0.10 | 4.98$\pm$0.13 | 3.07$\pm$0.49 | 3.73$\pm$0.54 | 7.61$\pm$0.09 | 8.84$\pm$0.06
SVHN (ViT) | 96.42$\pm$0.05 | 96.05$\pm$0.05 | 1.23$\pm$0.10 | 1.53$\pm$0.12 | 0.64$\pm$0.12 | 0.91$\pm$0.08 | 2.49$\pm$0.03 | 2.76$\pm$0.03
SVHN (Mixer) | 96.10$\pm$0.04 | 95.90$\pm$0.05 | 1.40$\pm$0.08 | 1.65$\pm$0.11 | 0.73$\pm$0.10 | 0.88$\pm$0.09 | 2.68$\pm$0.03 | 2.84$\pm$0.03

##  Appendix F Ablation Study: Effect of $d$

To investigate the effect of $d$, we tried $d=$8, 16, 32, 64, and 128 and
repeat the experiments. The performance and the inference time (overhead) can
be found in Figure 7. The inference time depends on the size of the
calibration set, which is specified in Section 4.

Generally speaking, we can only tell for sure that increasing $d$ increases
the overhead, although the overhead is always small compared with calling
$\mathbf{f}$. The effect on other metrics, including accuracy, ECE and CEC, is
not monotonic, and the best $d$ probably depends on many factors.

Figure 7:  Change in performance and inference time if we we change $d$ (the
output embedding size of $\mathbf{\Pi}$. “DNN time” refers to the average time
running $\mathbf{f}$ for one input $x$, and “KCal time” refers to the average
time transforming $\mathbf{f}(x)$ to $\hat{\mathbf{p}}(x)$ using KCal. For
Accuracy, ECE and CECE, the unit is percentage. The band represents the median
50% among 10 experiments. For time, the unit is second. Performance is not
always improving as $d$ increases, but a larger $d$ naturally leads to larger
overhead. It is however worth noting that in all experiment, the overhead
(“KCal time”) is negligible compared with the ‘DNN time”.

##  Appendix G Computing bandwidth

As suggested in the main text, although there is a bandwidth selection step
that seemingly prevents KCal from efficiently updating predictions in an
online manner, we could actually leverage Lemma 3.2 to compute $b$ as opposed
to actually performing cross-validation. To verify empirically that this is
feasible in practice, we perform experiments where we vary the size of the
calibration set, and plot the cross-validation-selected bandwidth $b$ against
the predicted value $\Theta(m^{-\frac{1}{d+4}})$. The results are in Figure 8.

Figure 8:  Empirically-selected bandwidth ($b^{*}$) on the y-axis, and
predicted bandwidth ($\Theta(m^{-\frac{1}{d+4}})$) on the x-axis. For each
calibration set size we have 10 experiments like in the main text, and we plot
the scatter plot and median of the experiments. As expected, we see a nearly
linear relationship for most data, except for IIIC, which exhibits a piece-
wise linear pattern. This suggests that in practice, as new samples are added
into the calibration set in an online manner, we could compute the bandwidth
$b$ and only re-do the cross validation sparingly.

If everything is perfect, we should see a linear relation in all plots, and we
can use this relationship to compute $b^{*}$ when we gradually add samples to
the calibration set. It is clear that if we use the estimated constant in the
$\Theta(\cdot)$ and the calibration set size (per class) $m$ to set the
bandwidth, we are still very close to the empirically selected value most of
the time. In practice, this means that we only need to perform the actual
cross validation occasionally, and predict the $b^{*}$ in between. Note that
from left to right, $m$ decreases, so the optimal $b^{*}$ increases and the
variance increases greatly due to $m$ being small. In practice, one might keep
updating $b^{*}$ using cross validation when $m$ is small (and cross-
validation takes very little time) and only compute $b^{*}$ when $m$ is
already large.

While computation will give good estimates for $b^{*}$ for most datasets,
especially when $m$ is large and the estimate of $b^{*}$ is relatively stable
(towards the left ends of plots), IIIC (and ISRUC to some extent) seems to
show two different slopes. As $m$ increases, from right to left, $b^{*}$ seems
to first decrease, and then stop decreasing. While a detailed analysis for
this are beyond the scope of this paper, there are a few possible reasons.

  1. 1.

First, and most importantly, the optimal bandwidth derived in Lemma 3.2 is
“best” for estimating the density, $f_{k}$ (in Eq. (4), not
$\mathbb{P}\\{\cdot|X\\}$. $b^{*}$ is however chosen according to the log-loss
of the KDE classifier. As a result, the formula should be more relevant when
$K$ is large and the difference between $\hat{\mathbf{p}}_{k}(X)$ and
$\mathbb{P}\\{Y=k|X\\}$ is essentially linear in $\hat{f}_{k}-f_{k}$ (as the
denominator is much more accurate than the numerator). The experiment does
support this point, since CIFAR100, with 100 classes, exhibits the clearest
linear relationship.

  2. 2.

Lemma 3.2 is not applicable if $f_{\mathbf{\Pi}\circ\mathbf{f}}$ violates the
assumptions. For example, if $\mathbf{f}$ creates a discontinuity in the
density, with a lot of data from different classes mapped to the same
embedding. This means decreasing $b$ might not decrease the bias term in
Section A.2, and only increases variance. This could be what is happening in
CIFAR10-ViT (with 99% accuracy) and in the left end of IIIC: decreasing $b$
might not improve log-loss as we have exhausted the discriminative power of
$\mathbf{f}$.

##  Appendix H Bandwidth Selection

In Section 3.4, we stated that we use Golden-Section search because we assume
the cross entropy loss is convex in bandwidth $b$. While the convexity is
expected from the bias-variance trade-off, we show in Figure 9 that this is
indeed the case.

Figure 9:  Change in cross validation loss used for the Golden-Section Search
mentioned in Section 3.4 as a function of bandwidth. As we can see, the loss
is indeed roughly convex in the bandwidth for all datasets.

##  Appendix I Effect of $|\mathcal{S}_{\text{cal}}|$

In Figure 10, we plot the accuracy, Brier score, CECE and ECE as a function of
$|\mathcal{S}_{\text{cal}}|$ for different datasets. As expected, as
$|\mathcal{S}_{\text{cal}}|$ increases, the performance of KCal increases and
then stabilizes.

Figure 10:  We change the size of $\mathcal{S}_{\text{cal}}$ and repeat the
experiment for KCal. The red dashed line denotes UnCal. We see that, as
expected, all metrics improves as the size of the calibration set increases,
and the performance is generally stable.