Combining Priors with Experience: Confidence Calibration Based on Binomial Process Modeling

The true calibration error is described as the $l_{p}$ norm difference between the confidence score of the predicted class and the true likelihood of being correct (Kumar, Liang, and Ma 2019):

The true calibration curve $P(H=1|\hat{S})$ and the distribution of confidence scores $\hat{S}\sim\hat{\mathcal{S}}$ determine the value of TCE. TCE is not computable since the ground truth of $P(H=1|\hat{S})$ and the true distribution of $\hat{S}$ cannot be obtained in practice. Therefore, statistical methods are needed to estimate $P(H=1|\hat{S})$ and the distribution of $\hat{\mathcal{S}}$, and then estimate the true calibration error.

Binning-based calibration metrics use the average accuracy of each bin to approximate $P(H=1|\hat{S})$ and use the sample size proportion of the bin to approximate the $\hat{\mathcal{S}}$. Formally, assume that all confidence scores are partitioned into $M$ equally-spaced non-overlapping bins, and the $i$-th bin is represented by $B_{i}$, then the binning-based expected calibration error ($ECE_{bin}$) is calculated as follows:

where $N$ represents the total number of samples, $|B_{i}|$ represents the element count of $B_{i}$, ${\rm acc}(B_{i})$ represents the average accuracy on $B_{i}$, and ${\rm conf}(B_{i})$ represents the average confidence on $B_{i}$. Typically, the binning scheme is divided into equal width binning (Guo et al. 2017; Naeini, Cooper, and Hauskrecht 2015) and equal mass binning (Kumar, Liang, and Ma 2019; Zadrozny and Elkan 2001). Recently, $Nixon\ et\ al.$ (Nixon et al. 2019) and $Roelofs\ et\ al.$ (Roelofs et al. 2022) observed that $ECE_{bin}$ with equal mass binning produces more stable calibration effect. $ECE_{bin}$ is sensitive to the binning scheme (Kumar, Liang, and Ma 2019; Nixon et al. 2019). Therefore, some improvements to $ECE_{bin}$ have been proposed. $Ferro$ and $Fricker$ (Ferro and Fricker 2012) and $Brocker$ (Bröcker 2012) propose a debiased estimator, $ECE_{debiased}$, which employs a jackknife technique to estimate the per-bin bias in the standard $ECE_{bin}$. This bias is then subtracted to estimate the calibration error better. $Roelofs\ et\ al.$ (Roelofs et al. 2022) propose $ECE_{sweep}$, which introduces the monotonically increasing property of the calibration curve into $ECE_{bin}$.

In recent years, confidence calibration evaluation methods that are not based on binning have also been proposed. $Gupta\ et\ al.$ (Gupta et al. 2020) proposed $KS-error$, which uses the Kolmogorov-Smirnov statistical test to evaluate the calibration error. $Zhang\ et\ al.$ (Zhang, Kailkhura, and Han 2020) and $Błasiok\ et\ al.$ (Blasiok and Nakkiran 2023) propose smoothed Kernel Density Estimation (KDE) methods for evaluating calibration error. $Chidambaram\ et\ al.$ (Chidambaram et al. 2024) smooth the logit and then use the smoothed logit to build calibration metric.

For any fixed $\hat{S}$, the repeated sampling process of $H$ is a binomial distribution on $N_{{}^{\hat{S}}}^{pos}$, where $N_{{}^{\hat{S}}}^{pos}=\sum\nolimits_{i=1}^{{N_{\hat{S}}}}{H_{i}^{(\hat{S})}}$ represents the number of “hit”, ${H_{i}^{(\hat{S})}}$ represents the $i$-th “hit” label at $\hat{S}$, ${{N_{\hat{S}}}}$ represents the number of samples at $\hat{S}$. Specifically, $N_{{}^{\hat{S}}}^{pos}\sim\mathcal{BI}({N_{\hat{S}}},P(H=1|\hat{S}))$, where $\mathcal{BI(\cdot)}$ represents binomial distribution. Formally, the following equation is satisfied:

where $C_{{N_{\hat{S}}}}^{N_{\hat{S}}^{pos}}$ is the binomial coefficient.

Furthermore, for all $\hat{S}\in[0,1]$, the repeated sampling process of $H$ is a binomial process. Binomial process is a random process (Grimmett and Stirzaker 2020) with binomial distribution in a continuous domain. Specifically, in the binomial process, the distribution of random variable $N_{{}^{\hat{S}}}^{pos}$ under every point $\hat{S}$ in the continuous domain $[0,1]$ is a binomial distribution. Since we are interested in $P(H=1|\hat{S})$, $P(H=1|\hat{S})$ is modeled as a prior function family $g(\hat{S};\theta)$. Formally, the following equation is satisfied:

where $\mathcal{BP}(\cdot)$ represents binomial process, and $\hat{S}\in[0,1]$.

Our purpose is to estimate the calibration curve $g(\hat{S};\theta)$. Usually, solving $g(\hat{S};\theta)$ requires a combination of prior and experience. Prior defines that $g(\hat{S};\theta)$ follows a function family of fixed parameter form or structure. Experience represents seeking the optimal parameter $\theta$ from the data. Maximum likelihood estimation is a classic and effective solution to this problem. Formally, the following equation needs to be solved:

where $D$ is the calibration data set, and $D=\{{\hat{s}_{i}},{h_{i}}\}_{1\leq i\leq N}$. Equivalently, $D=\{(\hat{s}_{j},N_{\hat{s}_{j}},N_{\hat{s}_{j}}^{pos})\}_{1\leq j\leq N^{{}^{\prime}}}$, where $N^{{}^{\prime}}$ is the number of sampling locations of $\hat{S}$. Therefore:

Therefore, Eq. 7 can be solved just by knowing $P(\hat{S})$. Typically, estimating $P(\hat{S})$ requires discretization methods. In order to make $P(\hat{S})$ as accurate as possible, the idea of bayesian averaging is adopted here. Formally, Eq. 7 becomes that:

where $B\in\cal B$ represents $B$-th binning scheme in $D$, $\cal B$ represents the binning scheme space, $b$ represent the $b$-th bin in $B$, $\hat{S}_{b}$ represent the average confidence score in the $b$-th bin, ${N_{{{\hat{S}}_{b}}}}$ represent the sample size in the $b$-th bin. In this paper, a uniform prior for modeling $P(B)$ is used, and $P(b)=|b|/|D|$, where $|\cdot|$ the element count function.

Directly solving Eq. 8 can obtain a feasible solution. However, due to the non-convexity of the likelihood function with respect to $g(\hat{S};\theta)$ in Eq. 8, the feasible solution may not be the global optimal solution. This non-global optimal solution will affect the estimation of the calibration curve. To solve this problem, an equivalent new optimization problem is proposed whose objective function is convex on $g(\hat{S};\theta)$, as shown below:

The proof of equivalence between Eq. 8 and Eq. 9 is provided in Appendix A.1. In general, Eq. 9 can be solved well using a common optimizer (e.g., Gradient Descent (Andrychowicz et al. 2016), Quasi-Newton Methods (Mokhtari and Ribeiro 2020), Nelder-Mead (Nelder and Mead 1965)).

Continuity with respect to data distribution is an important property for a calibration method and metric. It tells us whether a slight change in data distribution will lead to a drastic jump in the calibration curve and the calibration metric. Before conducting continuity analysis, a distance measure of the data distributions needs to be defined. It tells us how far away the two distributions are. In this paper, Wasserstein distance is used, as shown in Definition 15. Wasserstein distance measures the minimum cost of transforming one distribution into another.

Next, this paper first proves that $g(\hat{S};\theta)$ obtained by Algorithm 1 is Lipschitz continuity $w.r.t.$ data distributions, as shown in Theorem 17. Then, this paper proves that $TCE_{bpm}$ is Lipschitz continuity $w.r.t.$ data distribution when certain conditions are met, as shown in Theorem 2. The proofs of Theorem 17 and Theorem 2 are given in Appendix A.3.

To theoretically prove the effectiveness of a calibration metric, $Błasiok\ et\ al.$ (Błasiok et al. 2023) have proposed a unified theoretical framework: consistent calibration measure. Consistent calibration measure means two things: 1) When the true distance to calibration is small, the calibration metric should also be small(i.e., Robust completeness); 2) When the true distance to calibration is large, the calibration metric should also be large (i.e., Robust soundness).

Before defining the consistent calibration measure, we need to define how far a data distribution $D$ is from its nearest perfect calibration distribution, as shown in the Definition 3. Then, the consistent calibration measure can be defined as shown in Definition 4.

Theorem 3 proves that $TCE_{bpm}$ is a consistent calibration measure when certain conditions are met. Corollary 1 proves that when $P(\hat{S}|H=0)$ and $P(\hat{S}|H=1)$ follow beta distribution, $TCE_{bpm}$ calculated using Eq. 12 is a consistent calibration measure. The proof of Theorem 3 is given in Appendix A.4, and the proof of Corollary 1 is given in Appendix A.5.

Sample efficiency tells us how many samples a method requires to keep the error small enough. According to Hoeffding’s inequality, the sample size required for histogram binning is $N\geq\frac{B\cdot\rm{In}(1/\delta)}{2\varepsilon^{2}}$, where $B$ represents the number of bins. Specifically, for the error of the histogram binning to be lower than $\varepsilon$, $\frac{{{\rm{In}}({\rm{1/}}\delta)}}{{2{\varepsilon^{2}}}}$ samples are required at each bin. Next, we will prove that the sample efficiency of Algorithm 1 is $N\geq\frac{3\cdot\rm{In}(1/\delta)}{2\varepsilon^{2}}$, as shown in Theorem 4. This is due to the fact that the prior function of the calibration curve has three parameters, which ensures that the calibration curve can be uniquely determined by three distinct observation points. Therefore, in theory, as long as selecting three most representative bins, a good calibration curve can be estimated by Algorithm 1. The proof of Theorem 4 is given in Appendix A.6.

The estimated results of the calibration curve on the public ResNet110’s logit dataset trained on Cifar10 is shown in (a) of Fig. 1. The results on other datasets are shown in Appendix B.3. In order to intuitively show the effect of the calibration curve estimated by our method, the means and ranges of the calibration values estimated by the histogram binning under various binning schemes are simultaneously visualized. The calibration curve estimated by our method is close to the mean result of the histogram binning under various binnings and always falls within the result range of histogram binning under various binnings, indicating a relatively accurate and robust performance. In addition, Appendix B.3 shows that our method can achieve such performance under various sharpness, meaning that our method has certain versatility. Furthermore, in the regions of low confidence scores, which are also the regions of low density of confidence scores, the calibration confidence estimated by the binning method fluctuates greatly (e.g., the result range is broad when the confidence score is lower than 0.8 in (a) of Fig. 1) and sometimes even non-monotonic (e.g., (e), (g), and (h) in Fig. 3 of Appendix B.3). The two situations are obviously unreasonable (Kumar, Liang, and Ma 2019; Roelofs et al. 2022). Thanks to the continuous and monotonic prior distribution, the two unreasonable situations can be well avoided by adopting our method.

The estimated result of the calibration curve on the dataset simulated by the true distribution D1 is shown in (b) of Fig. 1. The results on other true distributions are shown in Appendix B.4. The calibration curve estimated by our method is closely aligned with the true calibration curve, with a mean absolute error (see Eq. 51 in Appendix B.2) of 0.0099, which is lower than 0.0233 of the mean result of histogram binning. This verifies the effectiveness of our method. In addition, in the regions of low confidence scores (i.e., the low-density regions of confidence scores), the broad result range indicates that the results estimated by the histogram binning method under a specific binning scheme may deviate from the true calibration value. Even the mean result of histogram binning under various binning schemes sometimes deviates significantly from the true calibration curve (e.g., when the confidence score is around 0.8 in D2 of Fig. 4 in Appendix B.4). However, in our method, benefiting from the excellent integration between the well-informed prior distribution and the empirical data, the calibration curve can be well estimated even in the low-density regions of confidence scores. This good estimation effect makes us believe that fully integrating well-informed prior distribution with empirical data is a promising future direction for confidence calibration.