Year: 2021

Abstract:
Probabilistic classifiers output confidence scores along with their predictions, and these confidence scores should be calibrated, i.e., they should reflect the reliability of the prediction. Confidence scores that minimize standard metrics such as the expected calibration error (ECE) accurately measure the reliability on average across the entire population. However, it is in general impossible to measure the reliability of an individual prediction. In this work, we propose the local calibration error (LCE) to span the gap between average and individual reliability. For each individual prediction, the LCE measures the average reliability of a set of similar predictions, where similarity is quantified by a kernel function on a pretrained feature space and by a binning scheme over predicted model confidences. We show theoretically that the LCE can be estimated sample-efficiently from data, and empirically find that it reveals miscalibration modes that are more fine-grained than the ECE can detect. Our key result is a novel local recalibration method LoRe, to improve confidence scores for individual predictions and decrease the LCE. Experimentally, we show that our recalibration method produces more accurate confidence scores, which improves downstream fairness and decision making on classification tasks with both image and tabular data.

text: Probabilistic classifiers output confidence scores along with their predictions, and these confidence scores should be calibrated, i.e., they should reflect the reliability of the prediction. Confidence scores that minimize standard metrics such as the expected calibration error (ECE) accurately measure the reliability on average across the entire population. However, it is in general impossible to measure the reliability of an individual prediction. In this work, we propose the local calibration error (LCE) to span the gap between average and individual reliability. For each individual prediction, the LCE measures the average reliability of a set of similar predictions, where similarity is quantified by a kernel function on a pretrained feature space and by a binning scheme over predicted model confidences. We show theoretically that the LCE can be estimated sample-efficiently from data, and empirically find that it reveals miscalibration modes that are more fine-grained than the ECE can detect. Our key result is a novel local recalibration method LoRe, to improve confidence scores for individual predictions and decrease the LCE. Experimentally, we show that our recalibration method produces more accurate confidence scores, which improves downstream fairness and decision making on classification tasks with both image and tabular data.

heading: 1 INTRODUCTION
text: Uncertainty estimation is extremely important in high stakes decision-making tasks. For example, a patient wants to know the probability that a medical diagnosis is correct; an autonomous driving system wants to know the probability that a pedestrian is correctly identified. Uncertainty estimates are usually achieved by predicting a probability along with each classification. Ideally, we want to achieve individual calibration, i.e., we want to predict the probability that each sample is misclassified.
However, each sample is observed only once for most datasets (e.g., image classification datasets do not contain identical images), making it impossible to estimate, or even define, the probability of incorrect classification for individual samples. Because of this, commonly used metrics such as the expected calibration error (ECE) measure the gap between a classifier’s confidence and accuracy averaged across the entire dataset. Consequently, ECE can be accurately estimated but does not measure the reliability of individual predictions.
In this work, we propose the local calibration error (LCE), a calibration metric that spans the gap between fully global (e.g., ECE) and fully individual calibration. Motivated by the success of kernel-based locality in other fields such as fairness (where similar individuals should be treated similarly) (Dwork et al., 2012; Pleiss et al., 2017) and causal inference (where matching techniques are used to find similar neighboring samples) (Stuart, 2010), we approximate the probability of misclassification for an individual sample by computing the average classification error over similar samples, where similarity is measured by a kernel function in a pre-trained feature space and a binning scheme over predicted confidences. Intuitively, two samples are similar if they are close in a pretrained feature space and have similar predicted confidence scores. By choosing the bandwidth of the kernel function, we can trade off estimation accuracy and individuality: when the bandwidth is very large, we recover existing global calibration metrics; when the bandwidth is small, we approximate individual calibration. We choose an intermediate bandwidth, so our metric can be accurately estimated, and provides some measurement on the reliability of individual predictions.
Theoretically, we show that the LCE can be estimated with polynomially many samples if the kernel function is bounded. Empirically, we also show that for intermediate values of the bandwidth, the LCE can be accurately estimated and reveals modes of miscalibration that global metrics (such as ECE) fail to uncover.
In addition, we introduce a non-parametric, post-hoc localized recalibration method (LoRe), for lowering the LCE. Empirically, LoRe improves fairness by achieving low calibration error on all potentially sensitive subsets of the data, such as racial groups. Notably, it can do so without any prior knowledge of those groups, and is more effective than global methods at this task. In addition, our recalibration method improves decision making when there is a “safe” action that is selected whenever the predicted confidence is low. For example, an automated system which classifies tissue samples as cancerous should request a human expert opinion whenever it is unsure about a classification. In a simulation on an image classification dataset, we show that recalibrated prediction models more accurately choose whether to use the “safe” action, which improves the overall utility.
In summary, the contributions of our paper are as follows. (1) We introduce a local calibration metric, the LCE, that is both easy to compute and can estimate the reliability of individual predictions. (2) We introduce a post-hoc localized recalibration method LoRe, that transforms a model’s confidence predictions to improve the local calibration. (3) We empirically evaluate LoRe on several downstream tasks and observe that LoRe improves fairness and decision-making more than existing baselines.

heading: 2 BACKGROUND AND RELATED WORK

heading: 2.1 GLOBAL CALIBRATION METRICS
text: Consider a classification task that maps from some input domain (e.g., images) X to a finite set of labels Y = {1, · · · ,m}. A classifier is a pair (f, p̂) where f : X → Y maps each input x ∈ X to a label y ∈ Y and p̂ : X → [0, 1] maps each input x to a confidence value c. Let Pr be a joint distribution on X × Y (e.g., from which training or test data pairs (x, y) are drawn). The classifier (f, p̂) is perfectly calibrated (Guo et al., 2017) with respect to Pr if for all c ∈ [0, 1]
Pr[f(X) = Y | p̂(X) = c] = c. (1)
To numerically measure how well a classifier is calibrated, the most commonly used metric is the expected calibration error (ECE) (Naeini et al., 2015; Guo et al., 2017), which measures the average absolute deviation from Eq. 1 over the domain. In practice, given a finite dataset, the ECE is approximated by binning. The predicted confidences p̂ are partitioned into bins B1, . . . , Bk, and then a weighted average is taken of the absolute difference between the average confidence conf(Bi) and average accuracy acc(Bi) for each bin Bi:
ECE(f, p̂) := k∑ i=1 |Bi| N |conf(Bi)− acc(Bi)|. (2)
Similarly, the maximum calibration error (MCE) (Naeini et al., 2015; Guo et al., 2017) measures the average deviation from Eq. 1 in the bin with the highest calibration error, and is defined as
MCE(f, p̂) := max i |conf(Bi)− acc(Bi)|. (3)

heading: 2.2 EXISTING GLOBAL RECALIBRATION METHODS
text: Many existing methods apply a post-hoc adjustment that changes a model’s confidence predictions to improve global calibration, including Platt scaling (Platt, 1999), temperature scaling (Guo et al., 2017), isotonic regression (Zadrozny & Elkan, 2002), and histogram binning (Zadrozny & Elkan, 2001). These methods all learn a simple transformation from the original confidence predictions to new confidence predictions, and aim to decrease the expected calibration error (ECE). Platt scaling fits a logistic regression model; temperature scaling learns a single temperature parameter to rescale confidence scores for all samples simultaneously; isotonic regression learns a piece-wise constant monotonic function; histogram binning partitions confidence scores into bins {[0, ), [ , 2 ), · · · , [1− , 1]} and sorts each validation sample into a bin based on its confidence p̂(x); it then resets the confidence level of all samples in the bin to match the classification accuracy of that bin.

heading: 2.3 LOCAL CALIBRATION
text: Two notions of calibration that address some of the deficits of global calibration are class-wise calibration and group-wise calibration. Class-wise calibration groups samples by their true class label (Kull et al., 2019; Nixon et al., 2019) and measures the average class ECE, while group-wise calibration uses pre-specified groupings (e.g., race or gender) (Kleinberg et al., 2016; Pleiss et al., 2017) and measures the average group-wise ECE or maximum group-wise MCE.
A few recalibration methods have been proposed for these notions of calibration as well. Dirichlet calibration (Kull et al., 2019) achieves calibration for groups defined by class labels, but does not generalize well to settings with many classes (Zhao et al., 2021). Multicalibration (Hébert-Johnson et al., 2017) achieves calibration for any group that can be represented by a polynomial sized circuit, but lacks a tractable algorithm. If the groups are known a priori, one can also apply global calibration methods within each group; however, this is impractical in many situations where the groups are not known for new examples at inference time.
At an even more local level, Zhao et al. (2020) look at individual calibration in the regression setting and conclude that individual calibration is impossible to verify with a deterministic forecaster, and thus there is no general method to achieve individual calibration.

heading: 2.4 KERNEL-BASED CALIBRATION METRICS
text: Kumar et al. (2018) introduce the maximum mean calibration error (MMCE), a kernel-based quantity that replaces the hard binning of the standard ECE estimator with a kernel similarity k(p̂(x), p̂(x′)) between the confidence of two examples. They further propose to optimize the MMCE directly in order to achieve better model calibration globally. Widmann et al. (2019) extend their work and propose the more general kernel calibration error. Zhang et al. (2020) and Gupta et al. (2020) also consider kernel-based calibration. However, these methods only consider the similarity between model confidences p̂(x), p̂(x′), rather than the inputs x, x′ themselves.

heading: 3 THE LOCAL CALIBRATION ERROR
text: Recall that commonly used metrics for calibration, such as the ECE or the MCE, are global in nature and thus only measure an aggregate reliability over the entire dataset, making them insufficient for many applications. An ideal calibration metric would instead measure calibration at an individual level; however, doing so is impossible without making assumptions about the ground truth distribution (Zhao et al., 2020). A localized calibration metric represents an adjustable balance between these two extremes. Ideally, such a metric should measure calibration at a local level (where the extent of the local neighborhood can be chosen by the user) and group similar data points together.
In this section, we introduce the local calibration error (LCE), a kernel-based metric that allows us to measure the calibration locally around a prediction. Our metric leverages learned features to automatically group similar samples into a soft neighborhood, and allows the neighborhood size to be set with a hyperparameter γ. We also consider only points with a similar model confidence as the prediction, so that similarity is defined in terms of distance both in the feature space and in model confidence. Thus, the LCE effectively creates soft groupings that depend on the feature space; with a semantically meaningful feature space, these groupings correspond to useful subsets of the data. We then mention a few design choices and visualize LCE maps over a 2D feature space to show that we can use our metric to diagnose regions of local miscalibration.

heading: 3.1 LOCAL CALIBRATION ERROR METRIC
text: We propose a metric to measure calibration locally around a given prediction. The calibration of similar samples should be similar, so we use a kernel similarity function kγ : X × X → R+, which provides similarity scores, to define soft local neighborhoods. kγ(x, x′) has bandwidth γ > 0, which determines the extent of the local neighborhood — as γ increases, the neighborhood grows. Less similar (i.e., further away) samples x′ have less influence on the local calibration metric at x. Also, as with the ECE and MCE (Eqs. 2 and 3), we use binning and consider only the points in the same
confidence bin as x. Thus, the samples that influence the local calibration metric at x are similar to x in both features and model confidences.
More formally, let φ : X → Rd be a feature map that transforms an input to a feature vector, and let kγ be parameterized as kγ(x, x′) = g((φ(x)− φ(x′))/γ) for some Lipschitz function g : Rd → R+. Then given a data point x ∈ X and a classifier (f, p̂), the local calibration error (LCE) of the model at x is the expected difference between the model’s confidence and accuracy on a randomly sampled data point x′ ∼ Pr, weighted by the kernel similarity kγ(x, x′). We say a probabilistic classifier (p̂, f) is perfectly locally calibrated with respect to kγ if
sup x∈supp(Pr)
E(x′,y′)∼Pr [ (p̂(x′)− 1[f(x′) = y′])kγ(x, x′) ∣∣∣ p̂(x′) = p̂(x)]︸ ︷︷ ︸ :=LCE?γ(x;f,p̂) = 0.
Similar to perfect calibration, perfect local calibration is achieved by the Bayes-optimal classifier. In general, perfect local calibration is a much stricter notion than perfect calibration due to localizing to each indiviudal data point x, and reduces to perfect calibration if kγ(x, x′) ≡ 1 is a trivial kernel. To define LCE on a finite dataset, we perform an additional binning on the confidence to deal with the conditioning. LetD = ((x1, y1), . . . , (xN , yN )) be a dataset, and let β(x) = {i : p̂(xi) ∈ B(p̂(x))} be the set of indices of the points inD occupying the same confidence bin as x. Then we can compute the LCE by
LCEγ(x; f, p̂) = ∣∣∣∣∣ ∑ i∈β(x)(p̂(xi)− 1[f(xi) = yi])k(x, xi)∑
i∈β(x) k(x, xi) ∣∣∣∣∣. (4) Note that the quantity (p̂(xi)− 1[f(xi) = yi]) is simply the difference between the confidence and the accuracy for sample xi, and the denominator is a normalization term.
We then define the maximum local calibration error (MLCE) as MLCEγ(f, p̂) := max
x LCEγ(x; f, p̂). (5)
Intuitively, the LCE considers a neighborhood about a sample x (as defined by the kernel kγ and the confidence bin B), and computes the kernel-weighted average of the difference between the confidence and accuracy for each sample in that neighborhood. Note that by changing the bandwidth γ, we can interpolate the LCE between an individualized calibration metric (as γ → 0) and a global one (as γ →∞). Lemma 1 makes this more concrete under the assumption that limγ→∞ kγ(x, x′) = 1 (proof in Appendix C). For example, the Laplacian and Gaussian kernels satisfy this condition. Lemma 1. As γ →∞, the MLCE converges to the MCE.
Theorem 1 shows that under certain regularity conditions, the finite-sample estimator LCE(x) converges uniformly and sample-efficiently to its true expected value LCE∗(x): Theorem 1. (Informal) Let α ≤ infx∈X E [kγ(X,x)1[p̂(X) ∈ B(p̂(x))]] be a lower bound on the expectation of the kernel, and d be the dimension of the kernel’s feature space. If the sample size is at least Õ(d/α4 2) where > 0 is a target accuracy level, then with probability at least 1− δ we have
sup x∈X ∣∣LCEγ(x; f, p̂)− LCE∗γ(x; f, p̂)∣∣ ≤ . Here, Õ hides log factors of the form log(1/αγδ ). In practice, α depends inversely on γ.
To summarize, the MLCE measures a worst-case individual calibration error as γ → 0 (i.e., the effective neighborhood is very small) and converges to the global MCE metric as γ →∞ (i.e., the effective neighborhood is very large). In practice, one must pick intermediate values of γ to balance a more local notion of calibration error with the sample efficiency of its estimation. A more formal statement and full proof of Theorem 1 can be found in Appendix D.

heading: 3.2 CHOICE OF KERNEL AND FEATURE MAP
text: In this work, we compute the LCE using 15 equal-width bins and use the Laplacian kernel
kγ(x, x ′) = exp ( − ‖φ(x)− φ(x′)‖1
dγ
)
Because distances in a high-dimensional input space (e.g., image data) may not be meaningful on their own, we evaluate the kernel on a feature representation of x rather than on x itself. Features learned from neural networks have proven useful for a wide range of tasks, and they have been shown to capture useful semantic features of their inputs (Huh et al., 2016; Chen et al., 2020; Li et al., 2020). The kernel similarity term kγ(x, x′) in the LCE thus leverages learned features to automatically capture rich subgroups of the data. For image data, we chose an Inception-v3 model as our feature map, since Inception features are widely accepted as useful and representative in many areas (e.g., for generative models (Salimans et al., 2016)), though other neural features can also be used (Appendix B). For tabular data, we used the final hidden layer of the neural network trained for classification.
In general, we also use t-SNE or PCA to reduce the dimension of the feature space. For example, the 2048-D Inception-v3 embedding is still very high-dimensional. We report results using t-SNE to reduce the dimension to 2 or 3, as well as PCA to reduce the dimension to reduce the dimension to 50 for image data and 20 for tabular data. Thus the overall representation function is φ(x) = φ2(φ1(x)), where φ1 maps from the inputs to the neural features, and φ2 reduces the feature space dimension.
Figure 1 plots the MLCE as a function of the kernel bandwidth for an ImageNet classification task. Note that when γ is small, the MLCE is 1 (a worst-case individual calibration error), and when γ is large, the MLCE approaches the global MCE. To obtain a single summary statistic describing the local calibration error, we can view this plot and pick a value of γ between the lim-
iting behaviors. We find that γ = 0.2 and γ = 0.4 are good intermediate points for the 3-D t-SNE and 50-D PCA features, respectively (Figure 1).
3.3 LOCAL CALIBRATION ERROR VISUALIZATIONS
To provide more intuition for the LCE, we will now visualize some examples of the LCE metric over a 2-D feature embedding. We consider a ResNet-50 model pre-trained on ImageNet as our classifier
(f, p̂), and pre-trained Inception-v3 features as a feature map φ1 : X → R2048. φ2 : R2048 → R2 then reduces the 2048-D feature vectors with t-SNE to two dimensions for ease of visualization in the LCE landscapes, so our overall representation function is φ = φ2(φ1(x)). Figure 2 visualizes the landscape of LCE0.2(x; f, p̂) as a function of φ(x) for the entire ImageNet validation set, as well as the marginal CDF of LCE0.2(x, f, p̂). We show these visualizations for the two confidence bins with the best and worst global calibration.
In the bin with the best global calibration, Figure 2 (top) shows that the landscape of the LCE is highly non-uniform, and the CDF of the LCE lies almost entirely to the right of the bin’s average calibration error. Numerically, the bin’s average calibration error is 0.0022, while its average LCE is 0.0259. This implies that the regions where the model is underconfident and overconfident are spatially clustered within the bin. Because global calibration metrics solely consider the average accuracy and average confidence within a bin, confidence predictions that are too high and too low are averaged out to obtain a low overall error value; they fail to capture this localized miscalibration.
In the bin with the worst global calibration, Figure 2 (bottom) clearly shows that the LCE still has high variance, even though the average calibration error of the bin (0.0455) is much closer to its average LCE (0.0515). The CDF plot provides more evidence that the landscape is not flat — there is no sharp rise at the bin calibration error. However, in this case the regions that are underconfident and overconfident are not clustered spatially.

heading: 4 LCE RECALIBRATION
text: In this section, we introduce local recalibration (LoRe), a non-parametric recalibration method that adjusts a model’s output confidences to achieve better local calibration. Our method improves the LCE more than existing recalibration methods, and using our method improves performance on both downstream fairness tasks and downstream decision-making tasks. Specifically, we can leverage the kernel similarity to achieve strong calibration for all sensitive subgroups of a population, without knowing those groups a priori. As long as the feature space is semantically meaningful, LoRe provides utility for downstream tasks without needing subgroup labels for the samples. If the subgroups are known, one can recover standard group-wise recalibration methods (and metrics) by using the improper kernel k(x, x′) = 1[x, x′ in same group].
The idea behind our method is simple: we can compute the kernel-weighted accuracy for each point x of all the points that are in the same confidence bin as x, and then reset the confidence of x to this kernel-weighted accuracy value. Note that using the kernel function to compute this value is intuitively like taking a weighted average of the accuracy of the points in the local neighborhood of x. Thus, LoRe can be considered a local analogue to histogram binning.
More formally, given a trained classifier (f, p̂), a recalibration dataset D = ((x1, y1), . . . , (xN , yN )), and a fixed point x ∈ X , let β(x) = {i : p̂(xi) ∈ B(p̂(x))} be the set of indices of the points in D occupying the same confidence bin as x. Then, we compute the recalibrated confidence as
p̂′(x) = ∑ i∈β(x) kγ(x, xi)1[f(xi) = yi]∑
i∈β(x) kγ(x, xi) . (6)
Equation 6 represents the kernel-weighted average accuracy of all points in the same confidence bin as x. In the limit as the kernel bandwidth γ →∞, p̂′(x)→ ∑ i∈β(x) 1[f(xi) = yi]/|β(x)| recovers histogram binning. As γ → 0, p̂′(x)→ 1[f(xi∗) = yi∗ ], where i∗ = arg mini∈β(x) kγ(x, xi), thus recovering a nearest-neighbor method. For intermediate γ, our method interpolates between the two extremes. Throughout this work, we used used γ = 0.2 for LoRe with tSNE and γ = 0.4 for LoRe with PCA throughout this work, since these represent intermediate points between the limiting behaviors of the LCE (e.g., see Fig. 1).

heading: 5 EXPERIMENTS
text: In this section, we show empirically that LoRe substantially improves LCE values, and that these lower LCE values lead to better performance on downstream fairness and decision-making tasks. In particular, we evaluate the local calibration through the MLCE, because we are interested in
understanding a model’s worst-case local miscalibration. On each task, we compare the performance of LoRe to no recalibration (‘Original’), temperature scaling (‘TS’) (Guo et al., 2017), histogram binning (‘HB’) (Zadrozny & Elkan, 2001), isotonic regression (‘IR’) (Zadrozny & Elkan, 2002), and direct MMCE optimization (‘MMCE’) (Kumar et al., 2018), all strong global recalibration methods.
We first run extensive experiments on three datasets to demonstrate that LoRe outperforms all baselines and achieves the lowest MLCE over a wide range of γ values. We then evaluate the performance of our method on a fairness task, where it is important that a model is well-calibrated for all sensitive subgroups of a given population, and we demonstrate that it achieves the lowest group-wise MCE. Notably, we find that the MLCE is well-correlated with the group-wise MCE across all experimental settings, and thus achieving low MLCE is a good indicator that a model has good group-wise calibration. Finally, we compare the performance of our method against the baselines on a cost-sensitive decision-making task, where there is a low cost for a prediction of “unsure” but a high cost for an incorrect prediction, and show that our method achieves the lowest cost.

heading: 5.1 DATASETS
text: ImageNet dataset (Deng et al., 2009): A large-scale dataset of natural scene images with 1000 classes; over 1.3 million images total. The training/validation/test split is 1.3mil / 25,000 / 25,000.
UCI Communities and Crime dataset (Dua & Graff, 2017): This tabular dataset contains a number of attributes about American neighborhoods (e.g., race, age, employment, housing, etc.). The task is to predict the neighborhood’s violent crime rate. The training/validation/test split is 1494 / 500 / 500. We randomize the training/validation/test split over multiple trials.
CelebA dataset (Liu et al., 2015): A large-scale dataset of face images with 40 attribute annotations (e.g., glasses, hair color, etc.); 202,599 images total. The training/validation/test split is 162,770 / 19,867 / 19,962.

heading: 5.2 RECALIBRATION PERFORMANCE
text: LoRe substantially improves the LCE values. In Figure 3, we plot the MLCE as a function of γ. We can see that our method outperforms all baselines (strong global calibration methods) across a wide range of γ values on ImageNet. This is true despite the fact that we only implement LoRe for a single γ. Appendix B provides similar results on the Communities & Crime, CelebA, CIFAR-10, and CIFAR-100 datasets. Note that LoRe works well regardless of the feature map and the dimensionality reduction method (see Section 5.3 for results with both t-SNE and PCA). Although the results shown in this section use Inception-v3 features, we show similar results in Appendix B with AlexNet (Krizhevsky, 2014), DenseNet121 (Huang et al., 2018), and ResNet101 (He et al., 2015) features.
Recall that as γ gets large, the MLCE recovers the MCE; because LoRe does well even at large γ, our method also works well at minimizing global calibration errors. The fact that LoRe lowers the worst-case LCE suggests that it leads to lower LCE values across the entire dataset.

heading: 5.3 DOWNSTREAM FAIRNESS PERFORMANCE
text: Experimental Setup In many fairness-related applications, it is important to show that a model is well-calibrated for all sensitive subgroups of a given population. For example, when predicting the crime rate of a neighborhood, a model should not be considered well-calibrated if it consistently underestimates the crime rate for neighborhoods of one demographic, while overestimating the crime rate for neighborhoods of a different demographic. Therefore, in this section, we examine the worst-case group-wise miscalibration of a classifier, as measured by the maximum group-wise MCE when evaluated only on sensitive sub-groups. We consider the following experimental settings:
1. UCI Communities and Crime: Predict whether a neighborhood’s crime rate is higher than the median; group neighborhoods by their plurality race (White, Black, Asian, Indian, Hispanic). 60 random seeds for model training. 2. CelebA: Predict a person’s hair color (bald, black, blond, brown, gray, other); group people by hair type (bald, receding hairline, bangs, straight, wavy, other). 20 random seeds for model training. 3. CelebA: Predict a person’s hair type; group people by their hair color; inverse of Setting 2. 20 random seeds for model training.
For each task, we train a classifier (see Appendix A for full details) and recalibrate its output confidences using each of the recalibration methods.
Results Table 1 reports the maximum group-wise MCE for each of the recalibration methods on each of the three tasks. LoRe outperforms the other baselines, achieving an average 49% reduction over no recalibration and an average 23% improvement over the next best global recalibration method. (Note in Figures 5, 6, and 7 in Appendix B that LoRe is the most effective method of lowering the MLCE over a wide range of γ). Notably, LoRe is robust to the feature map used (tSNE vs. PCA). It even outper-
forms global methods applied to each individual group, implying that correcting local calibration errors is a robust way to improve group calibration that generalizes better than naive alternatives.
Moreover, Table 2 shows that the maximum group-wise MCE is well-correlated with the MLCE, and it is in fact much better correlated with MLCE than with global calibration metrics Taken together, our results indicate that lowering the LCE has positive implications in fairness settings that cannot be achieved by simply lowering global metrics like the ECE. For reference, we also include the performance of all recalibration methods on various global calibration metrics in Table 3, which shows that LoRe is able to improve worst-case group-wise calibration without meaningfully sacrificing (and in some cases improving) average-case global calibration.

heading: 5.4 DOWNSTREAM DECISION-MAKING
text: Experimental Setup Machine learning predictions are often used to make decisions, and in many situations an agent must select a best action in expectation. As an example, suppose there is a low
cost u associated with returning “unsure” and a high cost w associated with returning an incorrect classification (e.g., in situations such as autonomous driving, being unsure incurs only the small cost of calling a human operator, but making an incorrect classification incurs a high cost). An agent with good uncertainty quantification can make a more optimal decision about whether to return a classification or return “unsure”; for a calibrated model, it would be optimal for the agent to return “unsure” below the confidence threshold of 1− u/w, and return a prediction above this threshold. Following this policy — i.e., returning “unsure” when the confidence is below this threshold and returning a prediction when the confidence is above it, we used a ResNet-50 model to make predictions on ImageNet, and recalibrated the predictions with each of the recalibration methods. For each method, we then calculated the total reward attained under various reward ratios w/u, as well as the prediction rejection area ratio (PRR) (Malinin et al., 2020), which measures the quality of the rejection curve when a model can choose to not provide any prediction. Note that a PRR of 1.0 indicates optimal rejection, and a PRR of 0.0 indicates “random” rejection; a higher PRR is better.
Results In Figure 4, we show the improvement in the total reward over the original classifier (i.e., no recalibration) as a function of the reward ratio w/u (the ratio of the cost of an incorrect classification to the cost of being unsure). Across a wide range of reward ratios, LoRe achieves the highest reward. The MLCE curves for this task are shown in Figure 3; note that LoRe also achieves lower LCE values than the global recalibration methods. Table 4 also reports the PRR achieved
with each method under a cost function of u = −1, w = −10, as well as several global calibration metrics; LoRe generally outperforms the other baselines in terms of both PRR and global calibration metrics. These results indicate that our recalibration method most effectively lowers LCE values without sacrificing (and indeed often improving) average-case global calibration, and that these lower LCE values correspond to better performance on this decision-making task.

heading: 6 CONCLUSION
text: In this paper, we introduce the local calibration error (LCE), a metric that measures calibration in a localized neighborhood around a prediction. The LCE spans the gap between fully global and fully individualized calibration error, with an effective neighborhood size that can be set with a bandwidth parameter γ. We also introduce LoRe, a recalibration method that greatly improves the local calibration. Finally, we demonstrate that achieving lower LCE values leads to better performance on downstream fairness and decision-making tasks. In future work, we hope to explore better feature spaces to define similarity, since the quality of our metric depends on the quality of the feature space.

heading: A MODEL ARCHITECTURE, TRAINING, AND OTHER HYPERPARAMETERS
text: For ImageNet and CelebA, we compute the ECE, MCE, and LCE using 15 equal-width confidence bins. For the UCI communities and crime dataset, we use 5 equal-width bins because the dataset is much smaller (500 datapoints for recalibration). These numbers of bins represent a good tradeoff between bias and variance in estimating the relevant calibration errors. We also ran some initial experiments with equal-mass binning, but found that the results were very similar to those obtained with equal-width binning.
A.1 IMAGENET
For all experiments with the ImageNet dataset, we used the pre-trained ResNet-50 model from the PyTorch torchvision package as our classifier. To calculate the LCE and apply LoRe, we used pre-trained Inception-v3 features, applying either t-SNE to reduce their dimension to 3 or PCA to reduce their dimension to 50, as a feature representation for the kernel.
A.2 UCI COMMUNITIES AND CRIME
For all experiments with the UCI communities and crime dataset, we used a 3-hidden-layer dense neural network as our base classifier. Each hidden layer had a width of 100 and was followed by a Leaky ReLU activation. We applied dropout with probability 0.4 after the final hidden layer. We trained the model using the Adam optimizer with a batch size of 64 and a learning rate of 3× 10−4 until the validation accuracy stopped improving. All other hyperparameters were PyTorch defaults. Training was done locally on a laptop CPU. We trained 60 different models with different random seeds to perform the experiments described in Section 5.3 and Figure 5. To calculate the LCE and apply LoRe, we used the final hidden layer representation learned by our model, applying t-SNE to reduce the dimension to 2 or PCA to reduce their dimension to 20, as a feature representation for the kernel.
A.3 CELEBA
For all experiments with the CelebA dataset, we trained a ResNet50 model and used it as our base classifier. We applied standard data augmentation to our training data (random crops & random horizontal flips), and trained all models for 10 epochs using the Adam optimizer with a learning rate of 1 × 10−3 and a batch size of 256. All other hyperparameters were PyTorch defaults. Training was distributed over 4 GPUs, and training a single model took about 30 minutes. For both Setting 2 and Setting 3 (described in Section 5.3), we trained 20 models with different random seeds to perform the experiments shown in Figures 6 and 7. To calculate the LCE and apply LoRe, we used pre-trained Inception-v3 features, applying t-SNE to reduce their dimension to 2 or PCA to reduce their dimension to 50, as a feature representation for the kernel.

heading: B ADDITIONAL EXPERIMENTAL RESULTS
text: In Figures 5, 6, and 7, we visualize the MLCE achieved by all recalibration methods for the three experimental settings evaluated in Section 5.3. Figure 3 in the main paper shows the same visualization for all methods on ImageNet. In Figure 8, we plot the MLCE achieved by all recalibration methods for CIFAR-100, and in Figure 9, we do the same for CIFAR-10. Across all settings and datasets, our method LoRe is the most effective at minimizing MLCE across a wide range of γ, even accounting for variations between runs.
In these figures, “Original” represents no recalibration, “TS” represents temperature scaling, “HB” represents histogram binning, “IR” represents isotonic regression, “MMCE” represents direct MMCE optimization, and “LoRe” is our method.
Next, we examine the influence of the specific feature map used. In Figures 10, 11, 12, and 13, we plot the MLCE achieved by all recalibration methods for ImageNet using Inception-v3, AlexNet, DenseNet121, and ResNet101 features. In Figures 14 and 15, we plot the MLCE achieved by all recalibration methods for ImageNet when the features used to calculate the MLCE are different from the features used by LoRe. For completeness, in Figures 16, 17, 18, and 19, we also visualize the average LCE for all experimental settings. All plots show similar results: LoRe performs best over a wide range of γ.

heading: C PROOF OF LEMMA 1
text: We restate Lemma 1 below, and provide the proof: Lemma 2. Assume that limγ→∞ kγ(x, x′) = 1 for all x, x′ ∈ X . Then, as γ → ∞, the MLCE converges to the MCE.
Proof. Since limγ→∞ kγ(x, x′) = 1 identically,
lim γ→∞ max x L̂CEγ(x; f, p̂) = max x
1
|β(x)| ∣∣∣∣∣∣ ∑ i∈β(x) p̂(xi)− 1 [f(xi) = yi] ∣∣∣∣∣∣ = max
k
1
|Bk| ∣∣∣∣∣∑ i∈Bk p̂(xi)− 1 [f(xi) = yi] ∣∣∣∣∣ = max
k |conf(Bk)− acc(Bk)|
= MCE(x; f, p̂)

heading: D FORMAL STATEMENT AND PROOF OF THEOREM 1
text: Let B1, . . . , BN denote a set of bins that partition [0, 1], and B(p) denote the bin that a particular p ∈ [0, 1] belongs to. Let af (x, y) = 1 [f(x) = y] indicate the accuracy of a the classifier (f, p̂) on an input x. We consider the signed local calibration error (SLCE):
SLCEγ(x; f, p̂) := E[(p̂(X)− af (X,Y ))kγ(X,x) | p̂(X) ∈ B(p̂(x))]
E[kγ(X,x) | p̂(X) ∈ B(p̂(x))]
= E[(p̂(X)− af (X,Y ))kγ(X,x)1 [p̂(X) ∈ B(p̂(x))]]
E[kγ(X,x)1 [p̂(X) ∈ B(p̂(x))]] .
D.1 ASSUMPTIONS AND FORMAL STATEMENT OF THEOREM
We make the following assumptions: Assumption A (Lipschitz kernel). The kernel kγ takes the form
kγ(x, x ′) = g
( φ(x)− φ(x′)
γ
) ,
where φ : X → Rd is a representation function, and g : Rd → [0, 1] is L-Lipschitz with respect to some norm ‖·‖.
Note this definition may require an implicit rescaling (for example, we can take φ(x)← φfeature(x)/d for a d-dimensional feature map φfeature and take g(z) = exp(−‖z‖1), which corresponds to the Laplacian kernel we used in Section 3.2). Assumption B (Binning-aware covering number). For any > 0, the range of the representation function φ(X ) := {φ(x) : x ∈ X} has an -cover in the ‖·‖-norm of size (C/ )d for some absolute constant C > 0: There exists a setN ∈ X with |N | ≤ (C/ )d such that for any x ∈ X , there exists some x′ ∈ N such that ‖φ(x)− φ(x′)‖ ≤ and B(p̂(x)) = B(p̂(x′)). Assumption C (Lower bound on expectation of kernel within bin). We have
inf x∈X
E[kγ(X,x)1 [p̂(X) ∈ B(p̂(x))]] ≥ α
for some constant α ∈ (0, 1).
The constant α characterizes the hardness of estimating the SLCE from samples. Intuitively, with a smaller α, the denominator in SLCE gets smaller and we desire a higher accuracy in estimating both the numerator and the denominator. Also note that in practice the value of α typically depends on γ.
We analyze the following estimator of the SLCE using n samples:
ŜLCEγ(x; f, p̂) = 1 n
∑n i=1(p̂(xi)− af (xi, yi))kγ(xi, x)1 [p̂(xi) ∈ B(p̂(x))]
1 n ∑n i=1 kγ(xi, x)1 [p̂(xi) ∈ B(p̂(x))]
. (7)
Theorem 2. Under Assumptions A, B, and C, Suppose the sample size n ≥ Õ(d/α4 2) where > 0 is a target accuracy level, then with probability at least 1− δ we have
sup x∈X ∣∣∣ŜLCEγ(x; f, p̂)− SLCEγ(x; f, p̂)∣∣∣ ≤ , where Õ hides log factors of the form log(L/γ δα).
Theorem 2 shows that Õ(d/ 2α4) samples is sufficient to estimate the SLCE simultaneously for all x ∈ X . When α = Ω(1), this sample complexity only depends polynomially in terms of the representation dimension d and logarithmically in other constants (such as L, γ, and the failure probability δ).
D.2 PROOF OF THEOREM 2
Step 1. We first study the estimation at finitely many x’s. Let N ⊆ X be a finite set of x’s with |N | = N . Since kγ ∈ [0, 1] and |p̂(x) − af (x, y)| ≤ 1 are bounded variables, by the Hoeffding inequality and a union bound, we have
P (
sup x∈N ∣∣∣∣ 1n n∑ i=1 (p̂(xi)− af (xi, yi))kγ(xi, x)1 [p̂(xi) ∈ B(p̂(x))]
− E[(p̂(X)− af (X,Y ))kγ(X,x)1 [p̂(X) ∈ B(p̂(x))]] ∣∣∣∣ > α /10)
≤ exp ( −cnα2 2 + logN ) .
Therefore, as long as n ≥ O(log(N/δ)/ 2α2) samples, the above probability is bounded by δ. In other words, with probability at least 1− δ, we have simultaneously∣∣∣∣ 1n n∑ i=1
(p̂(xi)− af (xi, yi))kγ(xi, x)1 [p̂(xi) ∈ B(p̂(x))]︸ ︷︷ ︸ :=Â(x)
− E[(p̂(X)− af (X,Y ))kγ(X,x)1 [p̂(X) ∈ B(p̂(x))]]︸ ︷︷ ︸ :=A(x) ∣∣∣∣ ≤ α /10.
for all x ∈ N . Similarly, when n ≥ O(log(N/δ)/ 2α4), we also have (with probability at least 1− δ) ∣∣∣∣ 1n n∑ i=1
kγ(xi, x)1 [p̂(xi) ∈ B(p̂(x))]︸ ︷︷ ︸ :=B̂(x) −E[kγ(X,x)1 [p̂(X) ∈ B(p̂(x))]]︸ ︷︷ ︸ :=B(x) ∣∣∣∣ ≤ α2 /10 On these concentration events, we have for any x ∈ N that∣∣∣ŜLCEγ(x; f, p̂)− SLCEγ(x; f, p̂)∣∣∣ = ∣∣∣∣∣ Â(x)B̂(x) − A(x)B(x) ∣∣∣∣∣
≤ ∣∣∣Â(x)∣∣∣∣∣∣∣∣ 1B̂(x) − 1B(x) ∣∣∣∣∣+ 1|B(x)| ∣∣∣Â(x)−A(x)∣∣∣ ≤ 1 · α 2 /10
α(α− α2 /10) +
1 α · α /10
≤ .
Step 2. We now extend the bound to all x ∈ X using the covering argument. By Assumption B, we can take an α2 γ/(10L)-covering of φ(X ) with cardinality N ≤ (10CL/α2 γ)d. Let N ⊂ X denote the covering set (in the X space). This means that for any x ∈ X , there exists x′ ∈ N such that ‖φ(x)− φ(x′)‖ ≤ α2 γ/(10L) amd B(p̂(x)) = B(p̂(x′)), which implies that for any x̃ ∈ X we have
|k(x̃, x)− k(x̃, x′)| = ∣∣∣∣f(φ(x̃)− φ(x)γ ) − f ( φ(x̃)− φ(x′) γ )∣∣∣∣ ≤ L γ ‖φ(x)− φ(x′)‖
≤ α2 /10,
where we have used the Lipschitzness assumption of g (Assumption A). This further implies∣∣∣Â(x)− Â(x′)∣∣∣ = ∣∣∣∣ 1n n∑ i=1 (p̂(xi)− af (xi, yi))kγ(xi, x)1 [p̂(xi) ∈ B(p̂(x))]
− 1 n n∑ i=1 (p̂(xi)− af (xi, yi))kγ(xi, x′)1 [p̂(xi) ∈ B(p̂(x′))] ∣∣∣∣
= ∣∣∣∣ 1n n∑ i=1 (p̂(xi)− af (xi, yi))[kγ(xi, x)− kγ(xi, x′)]1 [p̂(xi) ∈ B(p̂(x))] ∣∣∣∣
≤ 1 n n∑ i=1 |p̂(xi)− af (xi, yi)| · |kγ(xi, x)− kγ(xi, x′)| · 1 [p̂(xi) ∈ B(p̂(x))]
≤ α2 /10.
Similarly, we have |A(x) − A(x′)| ≤ α2 /10, |B̂(x) − B̂(x′)| ≤ α2 /10, and |B(x) − B(x′)| ≤ α2 /10. This means that the estimation error at x is close to that at x′ ∈ N and consequently also bounded by :∣∣∣ŜLCEγ(x; f, p̂)− SLCEγ(x; f, p̂)∣∣∣ = ∣∣∣∣∣ Â(x)B̂(x) − A(x)B(x) ∣∣∣∣∣
≤ ∣∣∣∣∣ Â(x)B̂(x) − Â(x ′) B̂(x′) ∣∣∣∣∣+ ∣∣∣∣∣ Â(x′)B̂(x′) − A(x ′) B(x′) ∣∣∣∣∣+ ∣∣∣∣A(x′)B(x′) − A(x)B(x) ∣∣∣∣ ≤ 3 [ 1 · α 2 /10
α(α− α2 /10) +
1 α · α2 /10 ] ≤ .
Therefore, taking this N in step 1, we know that as long as the sample size
N ≥ O (
log(|N |/δ) 2α4
) = O ( d [ log ( 10CL/α2 γ ) + log(1/δ) ] α4 2 ) = Õ ( d/α4 2 ) ,
we have with probability at least 1− δ that
sup x∈X ∣∣∣ŜLCEγ(x; f, p̂)− SLCEγ(x; f, p̂)∣∣∣ ≤ . This is the desired result.

Review summaries:
This work proposes a new metric for calibration in classification where calibration is measured over localities in the input space, and the localities are determined with a kernel over the feature space. A recalibration algorithm (LoRe) is additionally proposed, which aims to recalibrate the class predictions w.r.t. local calibration error (LCE). The experiments show that 1) LoRe achieves better local calibration (measured by MLCE, i.e. maximum LCE) than baseline recalibration methods on ImageNet, 2) LoRe achieves better group-wise calibration (measured by worst group-wise maximum calibration error) across 3 datasets with identifiable groups, and 3) achieves competitive performance in a simple decision making task where confident incorrect predictions incur high costs. 

This paper proposes a new measure of calibration called Local Calibration. While conventional calibration measures are only defined with probabilistic outputs, the proposed local calibration measure further incorporates the feature space by considering the neighbouring region with a kernel. The authors also propose a calibration method according to the definition and experimentally demonstrate the advantages.