Deep Discriminative to Kernel Density Graph for In- and Out-of-distribution Calibrated Inference

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:09:26

Abstract: Deep discriminative approaches like random forests and deep neural networks have recently found applications in many important real-world scenarios. However, deploying these learning algorithms in safety-critical applications raises concerns, particularly when it comes to ensuring confidence calibration for both in-distribution and out-of-distribution data points. Many popular methods for in-distribution (ID) calibration, such as isotonic and Platt’s sigmoidal regression, exhibit excellent ID calibration performance. However, these methods are not calibrated for the entire feature space, leading to overconfidence in the case of out-of-distribution (OOD) samples. On the other end of the spectrum, existing out-of-distribution (OOD) calibration methods generally exhibit poor in-distribution (ID) calibration. In this paper, we address ID and OOD calibration problems jointly. We leveraged the fact that deep models, including both random forests and deep-nets, learn internal representations which are unions of polytopes with affine activation functions to conceptualize them both as partitioning rules of the feature space. We replace the affine function in each polytope populated by the training data with a Gaussian kernel. Our experiments on both tabular and vision benchmarks show that the proposed approaches obtain well-calibrated posteriors while mostly preserving or improving the classification accuracy of the original algorithm for ID region, and extrapolate beyond the training data to handle OOD inputs appropriately.

Main paper: 
 introduction: 
 Machine learning methods, specially deep neural networks and random forests have shown excellent performance in many real-world tasks, including drug discovery, autonomous driving and clinical surgery [1] [2] [3] . However, calibrating confidence over the whole feature space for these approaches remains a key challenge in the field [4] . Calibrated confidence within the training or in-distribution (ID) region as well as in the out-of-distribution (OOD) region is crucial for safety critical applications like autonomous driving and computer-assisted surgery, where any aberrant reading should be detected and taken care of immediately [4, 5] .The approaches to calibrate OOD confidence for learning algorithms described in the literature can be roughly divided into two groups: discriminative and generative. Intuitively, the easiest solution for OOD confidence calibration is to learn a function that gives higher scores for in-distribution samples and lower scores for OOD samples [6] . The discriminative approaches try to either modify the loss function [7] [8] [9] or train the network exhaustively on OOD datasets to calibrate on OOD samples [10, 4] .Recently, Hein et al. [4] showed ReLU networks produce arbitrarily high confidence as the inference point moves far away from the training data. Therefore, calibrating ReLU networks for the whole OOD region is not possible without fundamentally changing the network architecture. As a result, all of the aforementioned algorithms are unable to provide any guarantee about the performance of the network throughout the whole feature space. The other group tries to learn generative models for the Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.in-distribution as well as the out-of-distribution samples. The general idea is to do likelihood ratio test for a particular sample using the generative models [11] , or threshold the ID likelihoods to detect OOD samples. However, it is not obvious how to control likelihoods far away from the training data for powerful generative models like variational autoencoders (VAEs) [12] and generative adversarial networks (GAN) [13] . Moreover, Nalisnick et al. [14] and Hendrycks et al. [10] showed VAEs and GANs can also yield overconfident likelihoods far away from the training data.The algorithms described so far are concerned with OOD confidence calibration for deep-nets only.However, we show that other approaches which partition the feature space, for example random forest, can also suffer from poor confidence calibration both in the ID and the OOD regions. Moreover, the algorithms described above are concerned about the confidence in the OOD region only and do not address the confidence calibration within the ID region at all. This issue is addressed separately in a different group of literature [15] [16] [17] [18] [19] [20] . Instead, we consider both calibration problems jointly and propose an approach that achieves good calibration throughout the whole feature space.In this paper, we conceptualize both random forest and ReLU networks as partitioning rules with an affine activation over each polytope. We consider replacing the affine functions learned over the polytopes with Gaussian kernels. We propose two novel kernel density estimation techniques named Kernel Density Forest (KDF) and Kernel Density Network (KDN). Our proposed approach completely excludes the need for training on OOD examples for the model (unsupervised OOD calibration). We conduct several simulation and real data studies that show both KDF and KDN are well-calibrated for OOD samples while they maintain good performance in the ID region. 
related works and our contributions: 
 There are a number of approaches in the literature which attempt to learn a generative model and control the likelihoods far away from the training data. For example, Ren et al. [11] employed likelihood ratio test for detecting OOD samples. Wan et al. [8] modified the training loss so that the downstream projected features follow a Gaussian distribution. However, there is no guarantee of performance for OOD detection for the above methods. To the best of our knowledge, apart from us, only Meinke et al. [5] has proposed an approach to guarantee asymptotic performance for OOD detection. Compared to the aforementioned methods, our approach differs in several ways:• We address the confidence calibration problem for both ReLU-nets and random forests.• We address ID and OOD calibration problem as a continuum.• We provide an algorithm for OOD confidence calibration for both tabular and vision datatsets whereas most of the existing methods are tailor-made for vision problems.• We propose an unsupervised post-hoc OOD calibration approach.3 Technical Background 
setting: 
 Consider a supervised learning problem with independent and identically distributed training samples{(x i , y i )} n i=1 such that (X, Y ) ∼ P X,Y , where X ∼ P X is a X ⊆ R D valued input and Y ∼ P Y is a Y = {1, • • • , K} valued class label.Let S be the high density region of the marginal, P X , thus S ⊊ X . Here the goal is to learn a confidence score, g :R D → [0, 1] K , g(x) = [g 1 (x), g 2 (x), . . . , g K (x)]such that,EQUATIONwhere P Y |X (y|x) is the posterior probability for class y given by the Bayes formula:EQUATIONHere P X|Y (x|y) is the class conditional density which we will refer as f y (x) hereafter for brevity.Deep discriminative networks partition the feature space R d into a union of p affine polytopes Q r such that p r=1 Q r = R d , and learn an affine function over each polytope [4, 21] . Mathematically, the unnormalized class-conditional density for the label y estimated by these deep discriminative models at a particular point x can be expressed as:EQUATIONFor example, in the case of a decision tree, a r = 0, i.e., decision tree assumes uniform distribution for the class-conditional densities over the leaf nodes. Among these polytopes, the ones that lie on the boundary of the training data extend to the whole feature space and hence encompass all the OOD samples. Since the posterior probability for a class is determined by the affine activation over each of these polytopes, the algorithms tend to be overconfident when making predictions on the OOD inputs.Moreover, there exist some polytopes that are not populated with training data. These unpopulated polytopes serve to interpolate between the training sample points. If we replace the affine activation function of the populated polytopes with Gaussian kernels and prune the unpopulated ones, the tail of the kernel will help interpolate between the training sample points while assigning lower likelihood to the low density or unpopulated polytope regions of the feature space. This results in better confidence calibration for the proposed modified approach.We will call the above discriminative approaches as the 'parent approach' hereafter. Consider the collection of polytope indices P from the parent approach which are populated by the training data.We replace the affine functions over the populated polytopes with Gaussian kernels G(•; μr , Σr ). For a particular inference point x, we consider the Gaussian kernel with the minimum distance from the center of the kernel to the corresponding point:EQUATIONwhere ∥ • ∥ denotes a distance. As we will show later, the type of distance metric considered in Equation 4 highly impacts the performance of the proposed model. In short, we modify Equation 3from the parent ReLU-net or random forest to estimate the class-conditional density (unnormalized):EQUATIONwhere n y is the total number of samples with label y and n ry is the number of samples from class y that end up in polytope Q r . We add a small constant to the class conditional density fy :EQUATIONNote that in Equation 6, b log(n) → 0 as the total training points, n → ∞. The intuition behind the added constant will be clarified further later in Proposition 2. The confidence score ĝy (x) for class y given a test point x is estimated using the Bayes rule as:EQUATIONwhere PY (y) is the empirical prior probability of class y estimated from the training data. We estimate the class for a particular inference point x as:EQUATION4 Model Parameter Estimation 
gaussian kernel parameter estimation: 
 We fit Gaussian kernel parameters to the samples that end up in the r-th polytope. We set the kernel center along the d-th dimension:EQUATIONwhere x d i is the value of x i along the d-th dimension. We set the kernel variance along the d-th dimension:EQUATION)where λ is a small constant that prevents σd r from being 0. We constrain our estimated Gaussian kernels to have diagonal covariance.For a high dimensional dataset with low training sample size, the polytopes are sparsely populated with training samples. For improving the estimate of the ratio nry ny in Equation 5, we incorporate the samples from other polytopes Q s based on the similarity w rs between Q r and Q s as:EQUATIONAs n → ∞, the estimated weights w rs should satisfy the condition:EQUATIONFor simplicity, we will describe the estimation procedure for w rs in the next sections. Note that if we satisfy Condition 12, then we have nry ny → nry ny as n → ∞. Therefore, we modify Equation 5 as:EQUATIONwhere r * x = argmin r ∥μ r -x∥. Now we use fy (x) estimated using (13) in Equation ( 6), ( 7) and ( 8), respectively. Below, we describe how we estimate w rs for KDF and KDN .Consider T number of decision trees in a random forest trained on n iid training samples{(x i , y i )} n i=1. Each tree t partitions the feature space into p t polytopes resulting in a set of polytopes:{{Q t,r } pt r=1 } T t=1 .The intersection of these polytopes gives a new set of polytopes {Q r } p r=1 for the forest. For any two points x ∈ Q r and x ′ ∈ Q s , we define the kernel K(r, s) as:EQUATIONwhere t rs is the total number of trees, x and x ′ end up in the same leaf node. Here, 0 ≤ K(r, s) ≤ 1.If the two samples end up in the same leaf in all the trees, i.e., K(r, s) = 1, they belong to the same polytope, i.e. r = s. In short, K(r, s) is the fraction of total trees where the two samples follow the same path from the root to a leaf node. We exponentiate K(r, s) so that Condition 12 is satisfied:EQUATION)We choose k using grid search on a hold-out dataset.Consider a fully connected L layer ReLU-net trained on n iid training samples {(x i , y i )} n i=1 . We have the set of all nodes denoted by N l at a particular layer l. We can randomly pick a node n l ∈ N l at each layer l, and construct a sequence of nodes starting at the input layer and ending at the output layer which we call an activation path: m = {n l ∈ N l } L l=1 . Note that there areN = Π L i=1 |N l |possible activation paths for a sample in the ReLU-net. We index each path by a unique identifier number z ∈ N and construct a sequence of activation paths as:M = {m z } z=1,••• ,N . Therefore, Mcontains all possible activation pathways from the input to the output of the network.While pushing a training sample x i through the network, we define the activation from a ReLU unit at any node as '1' when it has positive output and '0' otherwise. Therefore, the activation indicates on which side of the affine function at each node the sample falls. The activation for all nodes in an activation path m z for a particular sample creates an activation mode a z ∈ {0, 1} L . If we evaluate the activation mode for all activation paths in M while pushing a sample through the network, we get a sequence of activation modes:A r = {a r z } N z=1 .Here r is the index of the polytope where the sample falls in.If the two sequences of activation modes for two different training samples are identical, they belong to the same polytope. In other words, if A r = A s , then Q r = Q s . This statement holds because the above samples will lie on the same side of the affine function at each node in different layers of the network. Now, we define the kernel K(r, s) as:EQUATION)Note that 0 ≤ K(r, s) ≤ 1. In short, K(r, s) is the fraction of total activation paths which are identically activated for two samples in two different polytopes r and s. We exponentiate the kernel using Equation 15. Pseudocodes outlining the two algorithms are provided in Appendix D.Consider P n = {Q 1 , Q 2 , • • • , Q p } as a partition of R dgiven by a random forest or a ReLU-net after being trained on n training samples. We measure distance between two points x ∈ Q r , x ′ ∈ Q s using the kernel introduced in Equation 14 and Equation 16, and call it 'Geodesic' distance [22] :EQUATIONProposition 1. (P n , d) is a metric space.Proof. See Appendix A.1 for the proof.We use Geodesic distance to find the nearest polytope to the inference point. As Geodesic distance cannot distinguish between points within the same polytope, it has a resolution similar to the size of the polytope. For discriminating between two points within the same polytope, we fit a Gaussian kernel within the polytope (described above). As h n → 0, the resolution for Geodesic distance improves. In Section 5, we will empirically show that using Geodesic distance scales better with higher dimension compared to that of Euclidean distance.Given n training samples {(x i , y i )} n i=1 , we define the distance of an inference point x from the training points as:d x = min i=1,••• ,n ∥x -x i ∥, where ∥ • ∥ denotes Euclidean distance.Proposition 2 (Asymptotic OOD Convergence). Given non-zero and bounded bandwidth of the Gaussians, then we have almost sure convergence for ĝy as:lim dx→∞ ĝy (x) = PY (y).Proof. See Appendix A.2 for the proof. 
empirical results: 
 We conduct several experiments on simulated, OpenML-CC18 [23] 1 and vision benchmark datasets to gain insights on the finite sample performance of KDF and KDN. The details of the simulation datasets and hyperparameters used for all the experiments are provided in Appendix C. For Trunk simulation dataset, we follow the simulation setup proposed by Trunk [24] which was designed to demonstrate 'curse of dimensionality'. In the Trunk simulation, a binary class dataset is used where each class is sampled from a Gaussian distribution with higher dimensions having increasingly less discriminative information. We use both Euclidean and Geodesic distance to detect the nearest polytope (see Equation ( 4)) on simulation datasets and use only Geodesic distance for benchmark datasets. For the simulation setups, we use classification error, Hellinger distance [25, 26] from the true class conditional posteriors and mean max confidence [4] as performance statistics. While measuring in-distribution calibration for the datasets in OpenML-CC18 data suite, we used maximum calibration error as defined by Guo et al. [18] with a fixed bin number of R = 15 across all the datasets.Given n OOD samples, we define OOD calibration error (OCE) to measure OOD performance for the benchmark datasets as:EQUATION)For the tabular and the vision datasets, we have used ID calibration approaches, such as Isotonic [15, 16] and Sigmoid [17] regression, as baselines. Additionally, for the vision benchmark dataset, we provide results with OOD calibration approaches such as: ACET [4] , ODIN [6] , OE (outlier exposure) [10] . For each approach, 70% of the training data was used to fit the model and the rest of the data was used to calibrate the model. Row 6 of Figure 1 shows KDF-Geodesic and KDN-Geodesic scale better with higher dimensions compared to their Euclidean counterpart algorithms respectively.We use OpenML-CC18 data suite for tabular benchmark dataset study. We exclude any dataset which contains categorical features or NaN values2 and conduct our experiments on 45 datasets with varying dimensions and sample sizes. For the OOD experiments, we follow a similar setup as that of the simulation data. We normalize the training data by their maximum l 2 norm and sample 1000 testing samples uniformly from hyperspheres where each hypersphere has increasing radius starting 224 from 1 to 5. For each dataset, we measure improvement with respect to the parent algorithm: where E p =classification error, MCE or OCE for the parent algorithm and E M represents the performance of the approach in consideration. Note that positive improvement implies the corresponding approach performs better than the parent approach. We report the median of improvement on different datasets along with the error bar in Figure 2 . The extended results for each dataset is shown separately in the appendix. EQUATIONIn vision data, each image pixel contains local information about the neighboring pixels. To extract the local information, we use convolutional or vision transformer encoders at the front-end. More precisely, we have a front-end encoder, h e : R D → R m and typically, m << D. After the encoder there is a few fully connected dense layers for discriminating among the K class labels,h f : R m → R K .Note that the m-dimensional embedding outputs from the encoder are partitioned into polytopes by the dense layers (see Equation ( 3)) and we fit a KDN on the embedding outputs. The above approach results in extraction of better inductive bias by KDN from the parent model and makes KDN more scalable with larger parent models and training sample size.For the simulation study, we use a simple CNN with one convolutional layer (3 channels with 3 × 3 kernel) followed by two fully connected layers with 10 and 2 nodes in each. We train the CNN on 2000 circle (radius 10) and 2000 rectangle (sides 20, 50) images with their RGB values being fixed at [127, 127, 127] and their centers randomly sampled within a square with sides 100. The other pixels in the background where there is no object (circle, rectangle or ellipse) were set to 0.We perform three experiments while inducing semantic shifts in the inference points as shown in Figure 3 . In the first experiment, we randomly sampled data similar to the training points. However, we added the same shift to all the RGB values of an inference point (shown as color intensity in Figure 3 D ). Therefore, the inference point is ID for color intensity at 127 and otherwise OOD. In the second experiment, we kept the RGB values fixed at [127, 127, 127] while taking convex combination of a circle and a rectangle. Let images of circles and rectangles be denoted by X c and X r . We derive an interference point as X inf :EQUATION) Therefore, X inf is maximally distant from the training points for ϵ = 0.5 and closest to the ID points at ϵ = {0, 1}. In the third experiment, we sampled ellipse images with the same RGB values as the training points. However, this time we gradually change one of the ellipse axes from 0.01 to 40 while keeping the other axis fixed at 10. As a result, the inference point becomes ID for the axis length of 10. As shown in Figure 3 (D, E, F ), in all the experiments KDN becomes less confident for the OOD points while the parent CNN remains overconfident throughout the semantic shifts of the test points.In this study, we use a V iT _B16 (provided in keras-vit package) vision transformer encoder [27] pretrained on ImageNet [28] dataset and finetuned on CIFAR-10 [29] . We use the same encoder for all the baseline algorithms and finetune it with the corresponding loss function without freezing any weight. As shown in Table 1 , pretrained vision transformers are already well-calibrated for ID and the OOD approaches (ACET, ODIN, OE) degrade ID calibration of the parent model. On the contrary, ID calibration approaches (Isotonic, Sigmoid) perform poorly compared to that of KDN in the OOD region. KDN achieves a compromise between ID and OOD performance while having reduced confidence on wrongly classified ID samples. The number of populated polytopes (and Gaussians) for KDN is 9323 ± 353. See Appendix F for the corresponding experiments using Resnet-50.  
limitations: 
 Training time complexity for KDF and KDN is O(n 2 l f ) which is dominated by the Geodesic distance calculation. Here l f = total number of leaves in the forest or total nodes in the dense layers of the network and n = total training samples. However, the distance calculation can be done in parallel using our provided code. Additionally, note that the number of Gaussian kernel used by KDN is upper bounded by number of training samples. Therefore, KDN may not scale for really big datasets like ImageNet [28] . However, the scaling issue may be solved by selectively pruning neighboring polytopes which we will pursue in future. 
discussion: 
 In this paper, we demonstrated a simple intuition that renders traditional deep discriminative models into a type of binning and kerneling approach. The bin boundaries are determined by the internal structure learned by the parent approach and Geodesic distance encodes the low dimensional structure learned by the model. Moreover, Geodesic distance introduced in this paper may have broader impact on understanding the internal structure of the deep discriminative models which we will pursue in future. Our code, including the package and the experiments in this manuscript, will be made publicly available upon acceptance of the paper.A.1 Proof of Proposition 1For proving that d is a valid distance metric for P n , we need to prove the following four statements:1. d(r, s) = 0 when r = s.Proof: By definition, K(r, s) = 1 and d(r, s) = 0 when r = s.2. d(r, s) > 0 when r ̸ = s.Proof: By definition, 0 ≤ K(r, s) < 1 and d(r, s) > 0 for r ̸ = s.3. d is symmetric, i.e., d(r, s) = d(s, r).Proof: By definition, K(r, s) = K(s, r) which implies d(r, s) = d(s, r).4. d follows the triangle inequality, i.e., for any three polytopesQ r , Q s , Q t ∈ P n : d(r, t) ≤ d(r, s) + d(s, t).Proof: Let A r denote the set of activation modes in a ReLU-net and the set of leaf nodes in a random forest for a particular polytope r. N is the total number of possible activation paths in a ReLU-net or total trees in a random forest. Below c(•) denotes the cardinality of the set. We can write:N ≥ c((A r ∩ A s ) ∪ (A s ∩ A t )) (21) = c(A r ∩ A s ) + c(A s ∩ A t ) -c(A r ∩ A s ∩ A t ) ≥ c(A r ∩ A s ) + c(A s ∩ A t ) -c(A r ∩ A t ).Rearranging the above equation, we get:EQUATIONA.2 Proof of Proposition 2Note that first we find the nearest polytope to the inference point x using Geodesic distance and use Gaussian kernel locally for x within that polytope. Here the Gaussian kernel uses Euclidean distance from the kernel center to x (within the numerator of the exponent). The value out of the Gaussian kernel decays exponentially with the increasing distance of the inference point from the kernel center.We first expand ĝy (x): • Spiral is a two-class classification problem with the following data distributions: let K be the number of classes and S ∼ multinomial( 1 K ⃗ 1 K , n). Conditioned on S, each feature vector is parameterized by two variables, the radius r and an angle θ. For each sample, r is sampled uniformly in [0, 1]. Conditioned on a particular class, the angles are evenly spaced between 4π(k-1)t K K and 4π(k)t K K , where t K controls the number of turns in the spiral. To inject noise along the spirals, we add Gaussian noise to the evenly spaced angles θ ′ : θ = θ ′ + N (0, 0.09). The observed feature vector is then (r cos(θ), r sin(θ)).• Circle is a two-class classification problem with equal class priors. Conditioned on being in class 0, a sample is drawn from a circle centered at (0, 0) with a radius of r = 0.75.Conditioned on being in class 1, a sample is drawn from a circle centered at (0, 0) with a radius of r = 1, which is cut off by the region bounds. To inject noise along the circles, we add Gaussian noise to the circle radii r ′ : r = r ′ + N (0, 0.01).• Sinewave is a two-class classification problem based on sine waves. Conditioned on being in class 0, a sample is drawn from the distribution y = cos(πx). Conditioned on being in class 1, a sample is drawn from the distribution y = sin(πx). We inject Gaussian noise to the sine wave heights y ′ : y = y ′ + N (0, 0.01).• Polynomial is a two-class classification problem with the following data distributions: y = x a . Conditioned on being in class 0, a sample is drawn from the distribution y = x 1 .Conditioned on being in class 1, a sample is drawn from the distribution y = x 3 . Gaussian noise is added to variables y ′ : y = y ′ + N (0, 0.01).• Trunk is a two-class classification problem with gradually increasing dimension and equal class priors. The class conditional probabilities are Gaussian: where µ 1 = µ, µ 2 = -µ, µ is a d dimensional vector whose i-th component is ( 1 i ) 1/2 and I is d dimensional identity matrix. P (X|Y = 0) = G(µ 1 , I), P (X|Y = 1) = G(µ 2 , I),We provide the pseudocode for our porposed algorithms in Algorithm 1, 2 and 3.See Figure 5 (1) x i , x j ∈ R 1×d ▷ two input samples to be weighted (2) θ ▷ parent random forest with T trees Output:w ij ∈ [0, 1]▷ compute similarity between i and j-th samples. 1: function COMPUTEWEIGHTS(x i , x j , θ)I i ← PUSHDOWNTREES(x i , θ) ▷ push x i down T trees and get the leaf numbers it end up in.I j ← PUSHDOWNTREES(x j , θ) ▷ push x j down T trees and get the leaf numbers it end up in. (1)x i , x j ∈ R 1×d ▷ two input samples to be weighted (2) θ ▷ parent deep-net model Output: w ij ∈ [0, 1]▷ compute similarity between i and j-th samples. 1: function COMPUTEWEIGHTS(x i , x j , θ)A i ← PUSHDOWNNETWORK(x i , θ) ▷ get activation modes A i 3:A j ← PUSHDOWNNETWORK(x j , θ) ▷ get activation modes A j 4: l ← COUNTMATCHES(A i , A j ) ▷ count the number of times the two samples activate the activation paths in a similar way In this experiments, we use a Resnet-50 encoder pretrained using contrastive loss [30] as described in http://keras.io/examples/vision/supervised-contrastive-learning. The encoder projects the input images down to a 256 dimensional latent space and we add two dense layers with 200 and 10 nodes on top of the encoder. We use the same pretrained encoder for all the baseline algorithms.As shown in Table 4 , KDN achieves good calibration for both ID and OOD datasets whereas the ID calibration approaches are poorly calibrated in the OOD regions and the OOD approaches have poor ID calibration. https://www.openml.org/s/99We also excluded the dataset with dataset id 23517 as we could not achieve better than chance accuracy using RF and DN on that dataset. 
 
 Appendix:  


Decision: **Paper summary**

This paper addresses the problem of learning a probabilistic classifier (or a posterior distribution) that is both in-distribution (ID) and out-of-distribution (OOD) calibrated. The idea starts from the observation that a function modeled by a deep ReLU network can be equivalently written as a union of polytopes with affine activation functions. The proposed idea replaces the affine function with a Gaussian kernel. Relying on the fact that a Gaussian kernel decays exponentially quickly as one moves away from its center, the constructed posterior model can be made to recover the class prior distribution as a test point becomes far away from training examples. This alleviates the problem of model overconfidence when given an OOD test example and helps with OOD calibration.

**Review**

All reviewers note that the proposed method is well motivated. The proposed solution nicely addresses ID and OOD calibration at the same time (fbQU). The method is mathematically grounded (Reviewer tAq4). Runtime of the method was an issue raised by a few reviewers. The rebuttal sufficiently addressed this issue with results showing the relationship of training time and the number of hidden nodes.

Sticking issues discussed during the discussion phase were 1. novelty of the Gaussian-based model, and 2. preciseness of Proposition 2.

1. The Gaussian-kernel-based construction of a posterior distribution that decays to the prior as one moves away from the training points is not entirely new. This property has been used in, for instance, the Gaussian process regression literature (among others). It can be useful for OOD calibration but the novelty is limited.

2. Proposition 2 (arguably the main theorem in the work) is not precise for a few reasons. Firstly it is unclear for what random variable the almost-sure convergence applies to. "Almost sure" convergence is mentioned in the statement. Secondly, its implication on OOD calibration is unclear. Proposition 2 ensures that as one moves away from the training points, the posterior reduces to the prior, ensuring no overconfidence issues. However, this is an asymptotic statement.  As Reviewer gpCb sums up nicely, “for calibration, we expect a non-asymptotic guarantee that ensures the output confidence is accurate”.

Recommendation: reject.

Reviews: review: paper_summary: paper_summary: The paper introduces a way to calibrate ReLU networks or random forests by breaking them down into piecewise linear functions on polytopes and replacing the linear parts with Gaussian kernels. This approximation allows to naturally calibrate the models for the ID domain, where confidence will be high due to the density of ID samples that translates into high kernel values, and for the OOD domain, where confidence will be low due to the large distance to ID samples.
strength_weakness: strength_weakness: The main weakness I find is about the computational time of the method. The number of polytopes scales exponentially with the number of neurons, so I am concerned with the applicability of the method to large (or even medium-scale) neural networks. What is the computational cost of the method for the considered benchmarks, in terms of runtime?

The toy simulations are unnecessarily tedious to grasp and take up a lot of space. I do not say that they are complex, but they hinder the reading flow and do not bring much to the presentation. I would advise putting some of them in the appendix to leave more space for other explanations. Indeed, Section 5 is difficult to read (many "chunk" paragraphs with mathematical notations) and would benefit from more structured writing and more flow.
questions: questions: 1. Section 4.4 How is $\omega_{rs}$ estimated in that case?
2. Table 1: what is the Parent approach exactly compared to KDN and KDF? The definition of Section 3.3 does not seem to describe a whole model but only the parent idea that is then declined with KDN and KDF. 
3. What would be the AUROC, FPR, i.e. metrics commonly used in OOD detection?
4. Figure 1. What is "dimensions" in x-axis?
5. l. 192 I do not get how OCE measures an error since it only includes estimated quantities, and I do not see the estimated confidence score $\hat{g}_y(x)$. In addition, are $x_i$ OOD samples in that case? If yes it should be made explicit.
6. l. 213 I disagree that normalizing ensures that distances up to 1 are ID and above are OOD. There can be "holes" in the distribution (as the circle dataset), or modes. What is the authors' opinion about that?
limitations: limitations: The authors have adequately addressed the limitations
paper_summary: paper_summary: The paper proposes a novel approach for OOD detection by learning a posterior distribution that is calibrated for both ID and OOD individuals. It models the class-wise conditional distribution of features by a gaussian kernel respectively for a set of polytopes that cover the feature space. The tail property of gaussian kernels contribute to both ID and OOD calibration. Empirical evidence shows the power of the proposed algorithm across tabular and vision dataset under both ID and OOD settings.
strength_weakness: strength_weakness: The major concern is insufficient discussion over the research context of the paper, which renders it hard to precisely evaluate the contribution. The related work section is short. Section 2 shows that "OOD detection" is the closest area to this paper, but this keyword is totally absent from the introduction, where the research area is named "OOD confidence calibration". What is the relation between OOD detection and OOD confidence calibration? 
The introduction also reveals two potential approaches for this area: discriminative and generative methods. There are also two settings: ID and OOD confidence calibration. The readers might expect to review current progress for all those categories in the related work section.
questions: questions: 1. In Eq 3, how to ensure the non-negativity of the class-conditional density? The model of affine function might take negative values.
2. The model of class-conditional density with gaussian kernels, referring to Eq 5, resembles Kernel Density Estimation. Could the author please discuss the relation between KDE and the proposed method?
3. In Fig 1, KDF shows a weaker advantage for low dimensional settings. Could the author please explain why?
4. In Fig 2, why are OOD approaches absent? Fig 2 demonstrates the effectiveness of KDF compared to ID approaches in terms of OOD calibration. The readers could be more interested in the performance of OOD approaches.
5. In Table 1, it seems OOD approaches including ACET and ODIN can't even beat the parent model under OOD settings. Could the author please explain why?
limitations: limitations: The author has addressed limitations of their work in terms of sample complexity.
paper_summary: paper_summary: This paper proposes new methods, Kernel Density Forest (KDF) and Kernel Density Network (KDN), to address issues in confidence calibration for traditional deep learning models and random forests. The motivation stems from the existing literature that deep neural networks using ReLU tend to exhibit high confidence on out-of-distribution (OOD) data due to affine transformations. The proposed methods improve confidence calibration for both in-distribution (ID) and OOD data by partitioning the feature space into polytopes and replacing affine functions within each polytope with Gaussian kernels. Experimental results demonstrate that the proposed methods outperform existing techniques in terms of calibration performance.
strength_weakness: strength_weakness: Validity of Metrics:
The paper evaluates calibration using Maximum Calibration Error (MCE) for ID data, but does not justify the use of MCE over Expected Calibration Error (ECE) or Adaptive Calibration Error (ACE)[1]. A more detailed explanation and comparison of these metrics would enhance the paper's credibility. Additionally, the definition and justification for OCE (Out-of-distribution Calibration Error) would benefit from a similar comparison with ACE.

[1] https://arxiv.org/abs/1904.01685

Experiments:
To emphasize the effectiveness of the proposed methods, a comparison of execution times would be beneficial, especially since practical applications like web Click-Through Rate (CTR) estimation place significant importance on runtime. The paper should clarify what the noise in Table 1 represents. It would also be advantageous to include experiments on larger and more varied datasets, as well as an evaluation of the methods' performance when combined with in-training calibration methods, which are commonly used alongside post-hoc calibration methods.
questions: questions: Does the formulation of OCE assume a lack of usable features from the in-distribution domain? What practical and theoretical conditions are required for this assumption? For instance, it is known that large parameter models can improve OOD ECE even when trained with ERM on in-distribution features [2].

[2] https://arxiv.org/abs/2307.08187
limitations: limitations: This paper mentions computational complexity and limitations in practical applications, but lacks detailed experimental results to support these claims. Including such data would provide valuable insights for future research and implementation.

Comments: title: Thanks!
Official Comment by Reviewer fbQU
Thanks!
comment: Thank you so much for your effort and valuable feedback! They improved our work by a huge margin.
I thank the authors for their detailed response. I am satisfied with the answers provided, and I would like to raise my score.
- “This experimental setting essentially reduces the task to a binary one: whether to output normal confidence for an ID sample or just a prior for an OOD sample. ”
> The reviewer is correct, in the experimental setting, as one moves further away from the ID setting, an OOD calibrated classifier will output the prior.  However, close to the ID setting, the OOD calibrated classifier will output a probability that the sample is in any given class.  This is in contrast to an OOD detector, which, regardless of how close or far the data are from the ID data, if is OOD, it always effectively outputs the prior.
- “A binary OOD detector can also immediately output a confidence based on the prior if a sample is identified as OOD.”
> Yes, a binary OOD detector can output a confidence based on the prior.  However, without calibration, there is no reason to expect that confidence to be….calibrated.  This is precisely why the OOD calibration is more difficult, and more informative, than pure OOD detection.
- “Therefore, the proposed method is essentially an OOD detector, which implies the need to reconsider both the theoretical and empirical results within the broader literature of OOD detection.”
> We would say that our method subsumes OOD detection, because it also includes ID calibration, and OOD calibration. To our knowledge, there are no other papers demonstrating any algorithm with all these properties.
Thank the author for their detailed and patient responses. To summarize, the author has explained how OOD calibration is connected to and distinguished from calibration (ID) and OOD detection, respectively. From the rebuttal, it is revealed that OOD calibration is a new setting/metric proposed by this paper, which is certainly a contribution. (Although the author mentioned that a similar idea is only studied in a particular theorem of [1], the literature is also well-established for OOD detection, as is also evidenced by the title.) In my original review, I identified a weakness in the unclear discussion of related work, which was largely due to the mixed usage of OOD detection and OOD calibration. The author has clarified in the rebuttal that ACET, OE, and ODIN, stated in the paper as OOD calibration methods, are actually focused on OOD detection. Given the contribution of setting up OOD calibration, which lies somewhere between OOD detection and calibration, I still have concerns about whether this setting, as well as the introduced method, has a significant edge over both related fields.

**OOD Calibration vs. OOD Detection**: The author claims that OOD calibration is more challenging because it involves predicting a continuous and aligned confidence, while OOD detection is a binary decision. However, the author also mentions that the empirical study is conducted without access to labels, even at the evaluation stage, resulting in a metric OCE that depends completely on a prior of labels. This experimental setting essentially reduces the task to a binary one: whether to output normal confidence for an ID sample or just a prior for an OOD sample. A binary OOD detector can also immediately output a confidence based on the prior if a sample is identified as OOD. Therefore, the proposed method is essentially an OOD detector, which implies the need to reconsider both the theoretical and empirical results within the broader literature of OOD detection.

**OOD Calibration vs. Calibration**: As stated above, OOD calibration defined in an unsupervised manner is closer to OOD detection. However, there is established research for calibration [2] under distribution shift, which studies algorithms to produce calibrated outputs for different distributions. I believe this line of research is also relevant to the new notion.

Overall, I remain concerned about the exact boundary of the newly proposed notion of OOD calibration and the introduced methodology. Therefore, I maintain my evaluation of this paper. 

[1] Meinke, Alexander, Julian Bitterwolf, and Matthias Hein. “Provably Robust Detection of Out-of-distribution Data (almost) for free.” arXiv preprint arXiv:2106.04260 (2021).

[2] Kim, M. P., Kern, C., Goldwasser, S., Kreuter, F., & Reingold, O. (2022). Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119(4), e2108097119.
Thanks for elaborating the above concern. Sorry that we did not understand it fully previously.  The idea seems intuitive for measuring calibration in transfer learning settings with distribution shift in the feature space for the target task. We are not sure we understand how to measure ECE for OOD points in our setting. According to the definition of ECE, the calibration error is the difference between the fraction of predictions in the bin that are correct (accuracy) and the mean of the probabilities in the bin (confidence).  To calculate ECE, we need to measure accuracy. OOD points are unsupervised in our setting, i.e., there is no label associated with an OOD point. Our goal (Eq. 1 in our paper) is to calibrate the model so that it knows whenever it faces an OOD point (same as existing OOD detection approaches). There is not a target task in this setting where we want to do transfer learning. If a model is well-calibrated in the OOD region, it will always predict the majority (max prior) class in the ID training data for the OOD points. How do we calculate accuracy in this case? To clarify it further, consider we train a model on CIFAR10 and test it on OOD points from CIFAR100. The model will predict class labels within 1 to 10, but CIFAR100 has 100 classes. To the model (if it is calibrated) CIFAR100 should look like unknown points and hence it will have confidence at the prior level.
Thank you so much for your intuitive and valuable feedback! It improved our work significantly. We will make sure our presentation is significantly improved taking in consideration all the points raised by you for the camera ready version.
I thank the authors for their clarification and raised my rating. I strongly encourage them to polish the presentation for the camera ready version.
I acknowledge and thank the author for their response. In the rebuttal, the author has addressed the paper’s relation to OOD detection in detail. My remaining concern is about the relation between OOD calibration and IID calibration. It is an important and relevant problem to learn a posterior distribution that is calibrated simultaneously for both ID and OOD samples. However, as noted by other reviewers, it is confusing why a metric like ECE or ACE is not simultaneously adopted for both settings, which could have made the results more convincing.

The author has claimed ECE as a metric only for IID calibration, but I do not see a specific distribution assumption for ECE, and I believe ECE is still valid out-of-distribution. To illustrate this, consider the extreme setting where the outcome is independent of the feature. In this case, ECE is 0 if and only if the predictor outputs the prior label distribution, which behaves similarly to OCE. Additionally, ECE has the advantage of measuring calibration error when the distribution shift is moderate, such that the feature is still predictive, albeit less so, for the label.