NUQ: Nonparametric Uncertainty Quantification for Deterministic Neural Networks
Authors: Nikita Yurevich Kotelevskii
Alexander Fishkov
Kirill Fedyanin
Aleksandr Petiushko
Maxim Panov
Venue: ICLR 2022 Submitted (2022)
Keywords: Out-of-distribution detection
uncertainty quantification
epistemic uncertainty
aleatoric uncertainty
non-parametric models
Nadaraya-Watson estimator
Misclassification detection

Abstract:   This paper proposes a fast and scalable method for uncertainty quantification of machine learning models' predictions. First, we show the principled way to measure the uncertainty of predictions for a classifier based on Nadaraya-Watson's nonparametric estimate of the conditional label distribution. Importantly, the approach allows to disentangle explicitly \textit{aleatoric} and \textit{epistemic} uncertainties. The resulting method works directly in the feature space. However, one can apply it to any neural network by considering an embedding of the data induced by the network. We demonstrate the strong performance of the method in uncertainty estimation tasks on a variety of real-world image datasets, such as MNIST, SVHN, CIFAR-100 and several versions of ImageNet.

Under review as a conference paper at ICLR 2022
NUQ: NONPARAMETRIC UNCERTAINTY QUANTIFICA- TION FOR DETERMINISTIC NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper proposes fast and scalable method for uncertainty quantification of machine learning models' predictions, First, we show the principled way to measure the uncertainty of predictions for classifier based on Gadaraya-Watson nonparametric estimate of the conditional label distribution. Importantly, the approach allows disentangle explicitly aleatoric and epistemic uncertainties. The resulting method works directly in the feature space. However, one can apply it to any neural network by considering an embedding of the data induced by the network. We demonstrate the strong performance of the method in uncertainty estimation tasks on a variety of real-world image datasets, such as MNIST, SVHN, CIFAR-I00 and several versions of ImageNet.
INTRODUCTION
is crucial in many applications of modern machine learning methods to complement the prediction with some sort of a "confidence" score. In particular, deep neural network models, which usually achieve state-of-the-art results in various tasks, are notorious for providing overconfident predictions on data they did not see during training (Nguyen et al.] (2015). This issue restricts their wide usage in the fields with high costs of wrong predictions, such as medicine (Miotto et al. 2016)). autonomous driving (Levinson et al., 2011T; Filos al. 2020), finance (Brando et al., (018)) and others. Thus, developing a reliable method of quantifying uncertainty is of great interest to researchers and especially practitioners.
The community in recent years made tremendous efforts to develop different uncertainty estimation methods and approaches, including calibration Guo et al. (2017) ensembling (Laashmminarayaan
et al. 2017), Bayesian methods (Gal & Ghahramani] (016). and many others (Ovadia et al.) [0199]
Wang et al. 2019). Recently, a series methods uncertainty estimation based on the single deterministic neural network model was developed (Van Amersfoort al. 2020 Liu et al. 2020 van Amersfoort et al. 2021). Their primary focus is on ensuring that embeddings of the data obtained some layer of network capture the geometrical relationships between the data samples in the input space, which is done via different regularization strategies. Given this property, one can apply certain approach to capture uncertainty in the embedding space. The crucial property of these methods is the relatively mild required change in architectures and training procedures, which allows the application of the majority of existing deep learning models.
In practice it is usually important to distinguish two types of uncertainty: aleatoric and epis- temic (Der Kiureghian Ditlevsen 2009 Kendall & Gal 2017). The aleatoric uncertainty reflects the internal noise in the data due to class overlap, data markup errors, or other reasons. This type of uncertainty can be reduced by providing more data. The epistemic uncertainty reflects the model's ignorance of data. We can reduce the uncertainty of this type once we get more data. Epistemic uncertainty, thus, may be used to identify out-of-distritn disiiiiiiittuoon OOD data. If the model can quantify this type of uncertainty. it may abstain from prediction and address it to human expert. Also, the ability to quantify epistemic uncertainty helps in active learning (Gal et al.) 2017). where lack of "knowledge" naturally indicates in which areas should label samples. Importantly, there is single definition of uncertainty, and diverse, often heuristic treatments are usually used in practice.
Summary of the contributions. In this paper, develop new and theoretically grounded method of uncertainty quantification applicable to any deterministic neural network model. More specifically, contributions are follows.

---

Under review as a conference paper at ICLR 2022
1. We rigorously define the uncertainty of the model prediction at particular data point. This is done by direct consideration of the probability of the wrong prediction.
2. We provide corresponding uncertainty estimate by computing the variance of the kernel estimate of conditional density with the appropriately chosen bandwidth.
3. We apply the resulting method of uncertainty estimation in the neural network's ' embedding space. Our approach complements recent works uncertainty estimation for determin- istic neural networks, which suffered from a lack of principled method to quantify the uncertainty.
4. We implement the method in scalable manner, which allows it to be used on large datasets such as ImageNet. The experimental results misclassification detection and OOD detection tasks show the significant potential of the proposed approach.
The rest of the work is organised follows. Section describes the theoretical background and the resulting uncertainty estimation method. Section 3 reviews the related works. In Section 4 we describe the experimental evaluation of the proposed method. fection|3conccee the study.
2
NONPARAMETRIC UNCERTAINTY QUANTIFICATION
2.1 ESTIMATION UNDER COVARIATE SHIFT
Let's consider the standard binary classification setup (X,Y) E Rd x {0,1) with (X,Y) ~ P... We assume that we observe the dataset D = ((X,, YD) of i.i.d. points from F...
The classical problem in statistics and machine learning is find rule based on the dataset D which approximates the optimal one:
arg min ((g(X) FV)
Here g: Rd - f0, 1} is any classifier and the probability of wrong classification Rg = P(g(() # Y) is usually called risk. The rule g" is given by the Bayes optimal classifier:
1. π(x) > 1
(x)
0, n(x)
where 7/z)) = p(Y = | which is the conditional distribution of Y given X under the distribution P.
In this work, we consider situation when the distribution of the test samples Piest is different from the one for the training dataset P.r. i.c. P Prest # Ptr- Obviously, the rule g obtained for I., might no longer be optimal if the aim is to minimize the error on the test data Prost (g( X) * Y).
In order to formulate a meaningful estimation problem, some additional assumptions are needed. First of all, we assume that the distribution Pret is unknown at the model construction moment, and only the dataset DD is available, Also, we will assume that the conditional label distribution p(y is the same under both Pt, and Ptsst. The latter assumption has two important consequences:
1. All the difference between Ptr and Ptes test is due to the difference between marginal distribu- tions of X: Perain (X) and Prest The situation when (X) * Pirain (X) is known as covariate shift.
2. The Bayes rule still valid, i.e., optimal even under P Pesst.
However, while Bayes rule g" is still optimal, its approximation 9 might be arbitrary bad under the covariate shift. The reason for that is that can't 't expect Ò to approximate g" well in the areas where we have few samples from the training set or don't have them at all. Thus, some special treatment of covariate shift is required. We will discuss the particular problem statement in the next section.
2

---

Under review as a conference paper at ICLR 2022
2.2 PROBLEM STATEMENT
We consider a classification rule 5(x) = (D(x) constructed solely based on the dataset D. Let us start from defining pointwise risk of estimation:
R(x) P((()) x
where (()(X) x x xx) +
xx= x) under the assumptions above. The value R(x) is independent of covariate distribution Ptest (X) and essentially allows to define a meaningful target of estimation which is based solely on the quantities known for the training distribution.
Po
Let us note that the total risk value R(x) admits the following decomposition:
R(x) R((x) (x),
where R²)x) PX) + x)) is Bayes risk and R(x) ((((X) # Y X
is an excess risk. Here (x) corresponds to aleatoric uncertainty as it completely depends on the data distribution. Excess risk R(x) directly measures imperfectness of model ! and thus can be seen as a measure of epistemic uncertainty.
a))
To proceed, we first assume that the classifier ý has the standard form:
((x) 1, 1(x) 2
00 f)(>) < 2
where fi(x) = p(Y = X =) an estimate of the conditional density 17x))
For such estimate efficiently bound the excess risk via the following classical inequal- ity Devroye et al. (2013):
R(x) = (X) x =) *Y X = x) 21(((² 77x)).
allows us to obtain an upper bound for the risk:
R(x) S L(x) (x) 2 1/(3)),
where (x)x) = min ( is just the Bayes risk. While the upper bound still depends on the unknown quantity 77(z), we will see in the next section that [(x) allows for an efficient approximation under mild assumptions.
2.3
NONPARAMETRIE UNCERTAINTY QUANTIFICATION
2.3.1 KERNEL DENSITY ESTIMATE AND ITS ASYMPTOTIC DISTRIBUTION
To execute the approach above we need to consider some particular type of estimator for g. In this work, we suggest to consider classical kernel-based estimator of the conditional density as allows for simple description of its asymptotic properties. For an arbitrary class label the conditional probability estimate can be expressed as:
EN Kn(ai - 1) = Fi
i( = c X = x)
(1)
Lj Kn(I; - x)
Note that in case of c 1 the equation above gives n)(x))
In our experiments, we consider one dimensional kernel function K; IR + R2 and construct the resulting kernel in Rdd of the following form:
x yd
Kn(x -
-I
K
3

---

Under review as a conference paper at ICLR 2022
Different choices of kemels possible, see Supplementary Material, Section A.4.1 A well-known fact (see, e.g. PPweel (2010)) is that the difference between f)(x) - -m(a)) for properly chosen bandwidth h converges in distribution as follows:
[a(x) ((x) - n(x) - N Nhá p(z) (IK(())aa))))
where n is the number of data points in the training set, (-) is the kernel used for kernel density estimate (KDE), h the bandwidth the kernel; is the dimensionality of the problem and o² (ar) is the standard deviation of the data label at point 2.
Note that we can efficiently approximate the variance term in (2) To start with, the integral [[K (u)]=du can be computed in the closed form for various standard kernels, see Supplemen- tary Material, 3 Second, we approximate the marginal density of objects p(z). The density can be again obtained via KDE: p(z) = Nh Σ Ka( - x;). However, one can choose the other estimates of the density, not necessarily related to the considered kernel estimate. For example, Gaussian Mixture Model (GMM) can be used similarly to Mukhoti et al. (002T). The only thing left the variance which can be estimated as o²
8² z) f)(2(11 7(z)).
Now equipped with estimate of the distribution for ri(x) n(x). Let denote by r(x) the standard deviation of a Gaussian from equation (2)
2x)) 1 (x) Nhd p(x)
{ (IK())Pdu)
Based the obtained approximation of the distribution for C(x), procedure that takes into account properties of this distribution and study the theoretical properties of the resulting method similarly (Zaoui et 2020). We defer these studies future work and focus on the practical approach for obtaining uncertainty estimates which directly follows from the derivations above.
construct abstention
2.3.2 ESTIMATES OF TOTAL, ALEATORIC AND EPISTEMIC UNCERTAINTY
In this work, suggest particular uncertainty quantification procedure inspired by the derivation above. More specifically, we suggest to consider the following measure of the total uncertainty:
(x(2) = min(n(x), 1 - -(x)] + 2/ + T(x),
which is obtained by considering an asymptotic approximation of
EpC(x) min (n(x), m/()} + +EE [xxx) 77xx)
in a view of (2) and the fact, that E|gl = std(E)/ for the zero-mean normal variable Ç. The resulting estimate upper bounds the average error of estimation at point and thus indeed can be used as the measure of total uncertainty.
We also can write the corresponding measures of aleatoric and epistemic uncertainties:
(x) = min(n(2), 77x))) U,(2) = =2 / T(x).
Finally, the data-driven uncertainty estimates Ú,(2) and Ú,(x) can be obtained via plug-in using (a) [[([u)]'d du.
estimates f(xz), & (z). p(x) and, consequently, +²(x) NE. p(a)
The generalization of the considered uncertainty measures to the case of multiple classes results in the total uncertainty given by
2 U+(x) min nx(2)} + +2 r(x),
4

---

Under review as a conference paper at ICLR 2022
maxe maxe foi(e)
where (2) = Nha p(a)
[[[[w]] dd
du and 0z((x) - 7n 7n(x) 1e (1-)))_))) The derivation of
these formulas can be found in Supplementary Material, Section A. We note that the resulting
formula for aleatoric uncertainty (a(=) min. (1 Mc(a)) coineides with classical maximum probability (MaxProb) uncertainty measure.
The only remaining unspecified ingredient of the procedure is the choice of bandwidth for KDE.
2.4 How TO CHOOSE BANDWIDTH PROPERLY?
The choice of the optimal bandwidth parameter is well-developed in the theory of kernel density estimation. For example, one can base on asymptotically optimal values and select the bandwidth accordingly in Silverman's (Silverman 2018) or Scott's (Scoti. 1979) rules. However, such estimates are usually very crude in practice.
In this work, consider the choice of bandwidth based the Improved Sheather-Jones algo- rithm (Botev et al. 2010). We assume that the bandwidth optimal for the primary problem (density estimation) is also helpful for OOD detection. It is not necessarily in practice. Thus, it might be beneficial to tune the bandwidth to optimize the quality of OOD detection if some set of OOD points is available at the training time. However, we find that considered estimates perform fairly well in practice, see the experimental evaluation in Section 4
2.5 HOw TO COMPUTE KERNEL ESTIMATE WHEN N IS LARGE?
Our nonparametric method involves This could be intractable in practice when we are working with large datasets. However, the typical kernel Kn quickly approaches zero with the increase of the norm of the argument: || xz ||| Thus, we can use an approximation of kernel estimates: instead of the sum over all elements in the dataset, we consider the contribution of only several nearest neighbors. requires a fast algorithm for finding the nearest neighbors. For this purpose, we use the approach of Malkov & Yashunin (2018) based on Hierarchical Navigable Small World graphs (HNSW). It provides a fast, scalable, and easy-to-use solution to the computation of nearest neighbors.
the whole available data to compute the estimates.
3 RELATED WORK
The notion of uncertainty naturally shows up Bayesian statistics (Gelman al. 2013), and, thus, Bayesian methods are often used for uncertainty quantification. The idea to utilize posterior distribution over some hidden variables (or model parameters) to receive an uncertainty estimate. However, exact Bayesian inference is intractable for modern architectures with many parameters, and approximations are used.
Two popular approximation ideas Markov Chain Monte Carlo sampling (MCMC; Neal et al.) and Variational Inference (VI: Blei et al. (207)). The former has theoretical guarantees to be asymptoti- cally unbiased, but has high computational cost. A popular alternative is VI-based mean-field ap- proximation with a Gaussian distribution or distributions, enhanced with normalizing flows (Rezende) al., 2021; Kobyzev
Mohamed] 2015 Dinh et al., 2017 Papamakarios ever, standard VI-based methods usually do not scale well enough to apply to really large modern neural networks. That's why some alternatives are considered, such as the Bayesian treatment of Monte-Carde dropout (Gal & Ghahramani 2016).
al., 2020). How-
Despite all efforts, these approximations do not reach the state-of- of-the-art results, which belong to Deep Ensembles ([akshminarayanal et al. (007)). The ensembles are efficient but again computationally demanding. That's why a series of papers developed ways of approximating the distribution obtained by an ensemble of models by single probabilistic model (Malinin & Gales] 2018) Malinin et al.) 2020; Sensoy et al. 2018). These methods require changing the training procedure and/or at least double the number of trainable parameters.
Recently, another popular type of model for uncertainty quantification was proposed. Specifically, was proposed to consider single deterministic neural network model and only apply mild changes to the architecture and training procedure. The crucial idea behind these methods to ensure that an embedding space induced by the network captures the geometry of the input space. More specifically,
5

---

Under review as a conference paper at ICLR 2022
Aleatoric uncertainty
Epistemic uncertainty
12.5
0.3
-25
-0.
Figure 1: Left plot shows the data and the result of the classification by the Bayes classifier based on the nonparametric estimate of conditional density. The next two plots show different types of uncertainties: "aleatoric" and "epistemic" The lighter color, the higher uncertainty. We see that the former does not increase as we go away from training data, while the latter does.
was suggested to consider ResNet-type arcitectures (He et al. 2016) with some regularization, which ensures that the model becomes bi-Lipchitz (Van Amersfoort et al. 2020 van Amersfoort et al., Mukhoti et al.) [2021] Liu et al. (2020). These regularization techmiques are weight clipping, gradient penalty, and spectral normalization. Deep neural networks trained in this way achieve results comparable with standard approaches but with some training overhead. For uncertainty estimation with such networks variety of approaches were proposed. In DUQ (Van Amersfoort al. 2020). an RBF layer is added to the network with custom procedure to adjust the centroid points (in embedding space). The downside the method its inability to distinguish aleatoric and epistemic uncertainty. The heuristic to capture epistemic uncertainty was proposed in the DDU approach (Mukhoti et al.) 202T) which uses Gaussian Discriminant Analysis embedding space trained neural network for that. SNGP (Liu et al.) (020)) and DUE (van Amersfoort et al. [222]) are similar but use a Gaussian process as the final layer, requiring estimating covariance with the use inducing points or RFF expansion. While aiming for simplicity and minimal changes to the existing approaches for the construction neural network models, the majority these methods still require setting additional hyperparameters and/or increased computational cost.
EXPERIMENTS
4.1
TOY EXAMPLE
We start this section with the application of the proposed Nonparametric Uncertainty Quantification (NUQ) method to a toy example. As dataset, we use a 2-dimensional mixture of three Gaussians with centers at points [3, -2], [3, 21, [0, 10], and variance equal to 1. Each Gaussian is treated as separate class (see Figure D the leftmost panel).
We consider the Bayes classifier based on the nonparametric estimate of the conditional density ①I and compute aleatoric and epistemic uncertainty values according to equations 33). Bandwidth was selected according to Improved Sheather-Jones "ISJ"") rule (Botev et al.) 2010) independently for each data dimension. Classification results and uncertainties for this toy problem are presented in Figure The first plot shows the raw data and the result of the classification by the Bayes rule. Two other plots present aleatoric and epistemic uncertainty estimates obtained. The uncertainty measures show the desired behavior: aleatoric uncertainty large in-between the classes, while epistemic uncertainty increases with the increase of the distance to the training data.
4.2 IMAGE CLASSIFICATION DATASETS
In this section, we consider a series of experiments on image datasets. In contrast to the toy example above, should first train model and then apply NUQ to its predictive features. We emphasise, that NUQ is the postprocessing method, which fitted to the embeddings obtained from given model. In what follows, call this model "base model". In the experiments of this section,

---

Under review as a conference paper at ICLR 2022
Accuracy, MNIST rotated
MNIST vs grayscale SVHN
Rotated MNIST vs grayscale SVHN
MaxProb Entropy
10000
Random
10000
Random
SVPNN objects included
Optimal
SS SAYMIN 0000 included
Optimal
8000
8000
0.9
MaxProb
MaxProb
Accuracy
Entropy
Entropy
NUQ
NUQ
0.8
4000
4000
2000
2000
0.7
2000 4000
D0O0 BOOU
10000
0
5000 10000 15000 20000
5000 10000 15000 20000
Samples selected
Total oojects included
Total objects included
(a)
(b)
(c)
Figure 2: (a) Accuracy for images sorted by uncertainty on rotated MNIST. (b) Share of SVHN images included into consideration vs unrotated MNIST. In this simpler version, even the basic entropy manages to achieve good result. (c) More challenging task share of SVHN images included into consideration vs rotated MNIST. NUQ still distinguish between datasets with close to an optimal solution
use logits extracted features, if not explicitly stated otherwise. However, other options also possible; see Supplementary Material, Section A.4.
We compare popular measures of uncertainty which do not require significant modifications model architectures and training procedures. More specifically, we consider:
1. Maximum probability (MaxProb): 1 max ply = c xz);
2. Entropy: -E ply x²) log ply x);
3. Monte-Carlo dropout (Gal & Ghahramani] 2016);
4. Ensemble of models trained with different random seeds;
5. Test-Time Augmentation (TTA) augmentation, applied to data at inference time;
6. DDU (Mukhoti et al. 2021) involves Gaussian Mixture Model (GMM)-like approximation extracted features to predict uncertainties.
For Monte-Carlo dropout, Ensembles, and TTA, we first compute average vectors predictions and then compute its entropy (as noticed) among MaxProb, Standard deviation, and BALD entropy provides the best ROC-AUC results). More details can be found in Supplementary Material, Section A.2
4.2.1 ROTATED MNIST
The second example misclassification detection on MNIST (LeCun et al. 2010). We train a small convolutional neural network with three convolution layers, Supplementary Material, Section A.2 This is the base model we use to obtain logits for the input objects. We consider particular instance of distribution shift for evaluation by using a test set of MNIST images rotated at a random angle in the range from 30 to 45 degrees. This set contains 10000 images. The range of angles reassures that the data does not look like the original MNIST data, though many resulting pictures can still remind the ones from training.
In this experiment, we consider MaxProb and Entropy- based uncertainty estimates of the base model (using base model predictions, not NUQ) and compare them with NUQ-based estimate of total uncertainty (z).. To evaluate the quality of the uncertainty estimates, we sort the objects from the test dataset order of ascending uncertainties. Then we obtain the model's predictions and plot how accuracy changes with the number of objects taken into consideration; see Figure 2a The valid uncertainty estimation method is expected to produce the plot with accuracy decreasing when more samples are taken into account. Moreover, the higher is the plot, the better is the quality of the corresponding uncertainty estimate. We see that the plots for all the considered methods show the expected trend, while uncertainties obtained by NUQ more reliable.
7

---

Under review as a conference paper at ICLR 2022
OOD dataset MaxProb*
Entropy
Dropout
Ensemble
TIA
DDU
NUQ*
SVHN
19.
81.1=1.6
77.6#2.5
82,9+0,9
81.6#1.2
89.621.6
89.7+1.6
LSUN
81.5+2.0
83.0=2.1
76.8=5.1
86.5+0.8
85.0=2.7
92.1=0.6
92.3+0.6
Smooth 76.6#3.5
77.8+5.2
63.3#3.8
83.7+1.2
73.2+10.8
97.143.1
96.8+3.8
Table 1: OOD detection for CIFAR-100 in-distribution dataset with ResNet-50 neural network. The top two results are shown in bold. Evaluation is done for three models trained with different seeds to estimate the standard deviation. Methods requiring a single pass over the data to compute uncertainty estimates are marked with *
4.2.2 MNIST Vs. SVHN
To make the problem more challenging, we consider the SVHN dataset (Netzer et al. 2011), convert it to grayscale, and resize it the shape of 28 x 28. The size of this additional Wrseeddsed dataset is again 10000. We take the base model trained on MNIST from the previous section and consider the problem of OOD detection with SVHN being the OOD dataset.
As in-distribution, we first consider the test set of 10000 MNIST images. We again compute uncertainties for each object of this concatenated dataset (10000 MNIST and 10000 of SVHN) and sort them by their uncertainties in ascending order. For NUQ we use total uncertainty (.(a: this experiment. In Figure 2b we plot the share of objects included from the SVHN dataset. It is clearly seen that NUQ assigns higher uncertainties to objects from SVHN. In fact, NUQ almost perfectly separates MNIST from SVHN (optimal result is also depicted the plot). Although NUQ is the leader in this task, competitors show good performance, and we move on to make the problem more challenging.
We consider the problem of separation between rotated MNIST (see Section 4.2.1 and SVHN. We expect that it is harder to distinguish between them rotated MNIST images differ from those used to train the network. However, Figure 2c shows that NUQ still does very good job and allows for almost perfect separation. Interestingly, other methods completely fail and perform no better than random baseline.
4.2.3 CIFAR-100
To reinforce our results on simpler datasets, we further conduct experiments on more challenging CIFAR- 100 (Krizhevsky) 2009). We want model to detect the unconventional samples, and thus we treat the out-of-distribution detection as a binary classification task (OOD/not-OOD) by uncertainty score, and we report the ROC-AUC for that task. Following the setup from the recent works (Van Amersfoort et al. 2020 van Amersfoort et al. 2021 Sastry & Oore 2020). we use SVHN, LSUN (Yu al. 2015) and Smooth (Hein al. 2019) datasets OOD datasets.
We trained the ResNet-50 model from scratch on CIFAR-100. For our method and DDU, we use training with spectral normalization (Miyato al.) 2018) ensure the bi-Lipshitz constraint for mappings at each layer. In this experiment, NUQ was applied to the features from the penultimate layer, and the density estimate is given by GMM. See the results for other choices of hyperparameters in the Supplementary Material, Section A.4
The results are presented in Table The ensemble has strong performance, which is expected. The TTA performs reasonably well with the quality close to the one of the ensemble. We can clearly see that NUQ and DDU show close results while outperforning the competitors with a significant margin.
One may ask whether nonparametric classification method used in NUQ, trained on some embedding from the base model, has any relation to the original neural network. To reassure the reader, we provide an argument that it well approximates the predictions of the base model and NUQ- based uncertainty estimates can be used for the base model well. Specifically, we compute the agreement between predictions obtained from the Bayes classifier based on kernel estimate (i.e. the one used in NUQ) and base models' predictions. This metric formally can be defined as agreement($. p) = Σ 1 aarg max, p(y j xx)) = arg max, p(y = xx)] ] For CIFAR-100, this metric gives the agreement of 0.975, which tells that the approach is accurate.
8

---

Under review as a conference paper at ICLR 2022
OOD dataset
MaxProb*
Entropy
TTA
Ensemble
DDU
NUQ
ImageNet-R 80.4
83.6
85.8
84.4
80.1
99.5
ImageNet-O 28.2
29.1
30.5
51.9
74.1
82.4
Table 2: ROC-AUC score for ImageNet out-of-distribution detection tasks for different methods. Methods requiring single pass over the data to compute uncertainty estimates marked with *
Low uncertainty
Medium uncertainty
about my ERMIT crabs!
High uncertainty
Figure 3: Typical OOD images for different levels of uncertainty as predicted by NUQ.
4.2.4 IMAGENET
To evaluate the method's applicability to the large-scale data, we have applied our approach to the ImageNet (Deng et al., (209) dataset. As OOD data we used the ImageNet-O (Hendrycks al., 2021b) and ImageNer-R(Hendrrck et al.) 2021a) datasets. ImageNet-O consists images from classes that not found in the standard ImageNet- Ik dataset. ImageNet-R contains different artistic renditions ImageNet classes.
It turned out that in these experiments, NUQ beats all the competitors with large margin; Table The advantage over DDU can be explained by the fact that DDU involves GMM-like approximation of the feature density, one mixture component per class. In ImageNet, there 1000 classes, and appears to be an issue for GMM to approximate in such high-dimensional space efficiently. Also importantly, the resulting inference time for the NUQ estimator was quite fast, with less than minutes needed to process the whole dataset on a moderate machine.
Additionally, we looked at some typical samples from these datasets with low, moderate, and high levels of uncertainty as assigned by NUQ, see Figure 3 We observe that the uncertainty value corresponds well to the intuitive degree of complexity for these images compared to the original ImageNet data. Interestingly, the images with a low degree of uncertainty look like those that can be easily classified by a typical neural network trained on ImageNet.
CONCLUSIONS
In this work, we propose NUQ, new principled uncertainty estimation method that applies to wide range neural network models. does not require retraining the model and acts as a postprocessing step working in the embedding space induced by the neural network. NUQ significantly outperforms the competing approaches with only recently proposed DDU method (Mukhoti et al. 2021) showing comparable results. Importantly, in the most practical example of OOD detection for ImageNet data, NUQ shows the best results with a significant margin. All the code to reproduce the experiments is available at /ttt:://// //q thub. com httmm//mmtttteeeeeeeeeeeeee wtte//t///eeeeeeeeeeeeeee http:///reeeereeee/nnnnniieteeee anonymity

---

Under review as a conference paper at ICLR 2022
We hope that our work opens new perspective on model-free uncertainty quantification methods for deterministic neural networks. Since the usage of deep models in high-risk real-world applications is usually limited due to the inability to account for uncertainty, believe that our ideas could help the community bridge this gap. We also believe that NUQ is suitable for in-depth theoretical investigation, which we defer future work.
BIBLIOGRAPHY
Aleksandr Artemenkov and Maxim Panov. Nevis: Noise contrastive approach for scalable vi- sualization. In Proceedings of The Web Conference 2020, WWW '20, pp. 2941-2947, New York, NY, USA, 2020, Association for Computing Machinery. ISBN 9781450370233, doi:
(0.1145/33664333338006
11151/..1115/333623333 33555/333364223330008333 3380061
David M Blei, Alp Kucukelbir, et al. Variational Inference: A Review for Statisticians. Journal of the American Statistical Association, 1 8):85)8877,,20111
Zdravko Botev, Joseph F Grotowski, et al. Kernel Density Estimation via Diffusion. The Annals of Statistics, (8(5):2916-2957 2010.
Axel Brando, Jose Rodríguez- et al. Uncertainty Modelling in Deep Networks: Forecasting Short and Noisy Series. In Joint European Conference Machine Learning and Knowledge Discovery Databases, pp. 325-340. Springer, 2018.
Jia Deng, Wei Dong, et al. Imagenet: A Large-Scale Hierarchical Image Database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255. leee, 2009.
Armen Der Kiureghian and Ove Ditlevsen. Aleatory or Epistemic? Does It Matter? Structural Safety, 31(2):105 112, 2009.
Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition, volume 31. Springer Science & Business Media, 2013.
Laurent Dinh, Jascha Sohl-Dickstein, et al. Density Estimation using Real NVP. In 5th Interna- tional Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net,200 2017. URL
net/
Forum?id=Hkpb.lte
Angelos Filos, Panagiotis Tigkas, et al. Can Autonomous Vehicles Identify, Recover from, and Adapt to Distribution Shifts? In International Conference on Machine Learning, pp. 3145-3153, PMLR, 2020.
Yarin Gal and Zoubin Ghahramani. Dropout a Bayesian Approximation: Representing Model Un- certainty in Deep Learning. In Maria-Floring Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1050-1059, JMLR.org, 2016. URL htttp::/prroceedinggg. mlr. wwwps/
htmll
Yarin Gal, Riashat Islam, et al. Deep Bayesian Active Learning with Image Data. In International Conference on Machine Learning, pp. 1183-1192. PMLR, 2017.
Andrew Gelman, John B Carlin, et al. Bayesian Data Analysis. CRC press, 2013.
Chuan Guo, Geoff Pleiss, al. On Calibration of Modern Neural Networks. In International Conference on Machine Learning, pp. 1321-1330. PMLR, 2017.
Kaiming He, Xiangyu Zhang, et al. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Matthias Hein, Maksym Andriushchenko, et al. Why Relu Networks Yield High- Cogh-Confieence Predic- tions Far away from the Training Data and How to Mitigate the Problem. In Proceedings of the IEFF/CVF Conference Computer Vision and Pattern Recognition, pp. 41-50, 2019.
10

---

Under review as a conference paper at ICLR 2022
Dan Hendrycks, Steven Basart, et al. The Many Faces of Robustness: A Critical Analysis of sutto--Distribution Generalization. ICCV, 2021a.
Dan Hendrycks, Kevin Zhao, et al. Natural Adversarial Examples. CVPR, 2021b.
Alex Kendall and Yarin Gal. What Uncertainties Do We Need in Bayesian Deep Learn- In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp.
ing for Computer Vision?
2017. URL https: htttpps:/ppoceeeiingg http://s.....ii.p.e.c..crrr////a cctppappr//01//aall. 025568998566006662222266628 Absrsssttttbb-bratttttct
Abstract .httraaccttmmml
Ivan Kobyzev, Simon Prince, et al. Normalizing Flows: An Introduction and Review of Current Methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. Technical report, 2009,
URL
https:/ htops://wwwxt www. cs. toronto www.rotttedddo-eeee
wwwtarnnnn--eauuuueeeeeeeeeeaeee features-
pdf
Balaji Lakshminarayanan, A. Pritzel, al. Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles. In NIPS, 2017.
Yann LeCun, Corinna Cortes, et al. MNIST Handwritten Digit Database. ATT Labs [Online]. 2, 2010.
Available: http://yam.lecun.commeee
Jesse Levinson, Jake Askeland, al. Towards Fully Autonomous Driving: Systems and Algorithms. In 2011 IEEE Intelligent Vehicles Symposium (/V), pp. 163-168. IEEE, 2011.
Jeremiah Z. Liu, Zi Lin, et al. Simple and Principled Uncertainty Estimation with Deterministic Deep Learning via Distance Awareness. In Hugo Larochelle, Marc Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL SttLattts//procctdtl Abst cattsraccttmmll html
www.newweeeeuuneeeeeeee cc/paper/
2020/hash/ 4eteeh//523333342445538 (tta////8077TTaaaaaaaaaaaeee3a33
Andrey Malinin and Mark J. F. Gales. Predictive Uncertainty Estimation via Prior Networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchh and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 7047-7058, 2018. URL
/c/ htmll
Andrey Malinin, Bruno Mlodozeniec, et al. Ensemble Distribution Distillation. In 8th International Conference on Learning Representattinns, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Yu A Malkov and Dmitry A Yashunin. Efficient and Robust Approximate Nearest Neighbor Search using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824-82) 836, 2018.
Riccardo Miotto, Li Li, al. Deep Patient: an Unsupervised Representation to Predict the Future of Patients from the Electronic Health Records. Scientific Reports, 6(1):1-10, 2016.
Takeru Miyato, Toshiki Kataoka, al. Spectral Normalization for Generative Adversarial Networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedingy. OpenReview.net, 2018. URL https /openrevvi ew net. fftr/forumm3 dd wdwpd=B1111i111eee Q-
Jishnu Mukhoti, Andreas Kirsch, et al. Deterministic Neural Networks with Appropriate Inductive Biases Capture Epistemic and Alcatoric Uncertainty. CoRR, 10122102.11182, 2021. URL https //axiiv.e wwwp..wwwww.././..eo. 11582
11

---

Under review as a conference paper at ICLR 2022
Radford M Neal et al. MCMC using Hamiltonian Dynamics. Handbook of Markov Chain Monte Carlo,.
Yuval Netzer, Tao Wang, al. Reading Digits in Natural Images with Unsupervised Feature Learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Anh M Nguyen, Yosinski, et al. Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 427-436, 2015.
Yaniv Ovadia, E. Fertig, et al. Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift. NeurIPS, 2019.
George Papamakarios, Eric Nalisnick, al. Normalizing Flows for Probabilistic Modeling and Inference. Journal of Machine Learning Research, 22(57):1-64, 2021.
Adam Paszke, Sam Gross, al. PyTTorch: An Imperative Style, Perfforeffr Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc; E. Fox,
and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024- 8035. Curran Associates, Inc., 2019. URL http::/pppprrs..euuiii.. wwtp://www.pp....ppppp...eeee
library.
pdf
James L. Powell. Notes On Nonparametric Regression Estimation. Manuscript, 2010. URL
pdf
Danilo Rezende and Shakir Mohamed. Variational Inference with Normalizing Flows. In International Conference Machine Learning, pp. 1530-1538 PMLR, 2015.
Chandramouli Shama Sastry and Sageev Oore. Detecting Out-of- Dittrf-Distribution Examples with Gram Matrices. In ICML, 2020.
David W Scott. On Optimal and
Histograms. Biometrika, 66(3):605 610, 1979.
Murat Sensoy, Lance M. Kaplan, et al. Evidential Deep Learning to Quantify Clas- sification Uncertainty. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kris- ten Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 3183-3192 2018. URL /ettps:/prroceeeeee neuriiggggn...ussssoeee..e.r...e CC/ a98
Abst html
Bernard W Silverman. Density Estimation for Statistics and Data Analysis. Routledge, 2018.
Joost Van Amersfoort, Lewis Smith, et al. Uncertainty Estimation using Single Deep Deterministic Neural Network. In International Conference on Machine Learning, pp. 9690-9700, PMLR, 2020.
Joost van Amersfoort, Lewis Smith, et al. Improving Deterministic Uncertainty Estimation in Deep Learning for Classification and Regression. CoRR, abs/2102.11409, 2021. URL https
http://ba220000 11409
G. Wang, Wenqi Li, et al. Aleatoric Uncertainty Estimation with Test-Time Augmentation for Medical Image Segmentation with Convolutional Neural Networks. Neurocomputing, 335:34 45, 2019.
Fisher Yu, Yinda Zhang, al. LSUN: Construction of Large-Scale Image Dataset using Deep Learning with Humans in the Loop. CoRR, abs//506.00336 2015. URL
abs/1506. 03365
Ahmed Zaoui, Christophe Denis, et al. Regression with Reject Option and Application to kNN. Advances in Neural Information Processing Systems, 33:20073-20082, 2020.
12

---

Under review as a conference paper at ICLR 2022
A SUPPLEMENTARY MATERIAL
A.1 MULTICLASS GENERALIZATION FOR UNCERTAINTIES
In this section we show, how our method can be generalized from binary classification multiclass problems. Consider data pairs (X, Y) ~ P. Now, X E E and Y E L...., C, where C is the number of classes. We also denote Ti (z) IP(Y c =
Let us start with the Bayes risk:
P(Y g"(())
= = = - g (x=)
1 max = min (1- [=))
where 9 (x) == arg max. (x) is Bayes optimal classifier.
Let us further move to the excess risk. Denote by (a((:) density, we approximate. Analogously, g(x) == arg max. (Ir)
P(Y # x(x) X x x) - P(Y # g x x) = (a) - (x(
(1) (x) fg. (2) (x) + (z) - (x) + (gg())()) - (x))
< (x) - fg- (c) (x)) + [x( (z))=
where we used the fact that 0g (x) (z) (n( (x) S 0 for any x.
The expectation of the right hand can be upper bounded by 2 2 (x), where r(x) is defined below.
Total uncertainty for multiclass problem is thus
2 -((),, U+(x) min (1 no(x)} + +2
x
where
(x) 1 max ( [x)(x)) /
[K(w)]&dc du
Nhd p(x)
and ((()))
A.2 ARCIITECTURES
A.2.1 BASE MODEL
For CIFAR-100 and ImageNet-like datasets, we are using ResNet50 with or without spectral nor- malization (Myyato et al. 2018). For the spectral normalization, we use 3 iterations of the power method. We use a ResNet50 architecture with implementation from PyTorch (Paszke et al., 2019). This architecture was implemented for the ImageNet dataset; thus, for the CIFAR- 100, we had to adapt it. We changed the first convolutional layer and used kernel size 3x3 with stride and padding 1 (instead of kernel size 7x7 with stride 2 and padding 3). For CIFAR- 100, we train the model for 200 epochs with an SGD optimizer, starting with a learning rate of 0.1 and decaying it times on 60, 120, and 160 epoch. For ImageNet, train the model for 90 epochs with an SGD optimizer learning rate decaying 10 times every 30 epochs.
For MNIST, train small convolutional neural network with three convolution layers with padding of and kernel size of 3. Each of these layers is followed by a batch normalization layer. Finally, has linear layer with Softmax activation. This network achieves accuracy of 0.99 the holdout set.
We refer readers code for more specific details.
13

---

Under review as a conference paper at ICLR 2022
MAIS
0.90
MadPob VTrOgy
actrego
6.0
DCU
M8A2
0.90
800
2000
6023
6065
3000
10006
Tiaal cipeeeeecccceeee
(a)
(b)
(c)
Figure 4: (a) Accuracy for images sorted by uncertainty rotated MNIST. (b) Share of SVHN images included into consideration vs unrotated MNIST. In this simpler version, even the basic entropy manages achieve good result. (c) More challenging task share of SVHN images included into consideration vs rotated MNIST. NUQ still distinguish between datasets with close to an optimal solution
A.2.2 ENSEMBLE
For ensemble with a combination of base models, trained with different random seeds.
A.2.3 TEST-TIME AUGMENTATION (TTA)
base model with applying transformation the inference stage. Images of CIFAR- 100 are randomly cropped with padding 4, randomly horizontally flipped, and randomly rotated up to 15 degrees. ImageNet is randomly cropped from 256 224, randomly horizontally flipped, and the color was jittered (0.02).
For TTA.
A.2.4 SPECTRALLY NORMALIZED MODELS
For both DDU and NUQ, we need spectral normalized models to extract features. We're wrapping each convolutional and linear layer with spectral normalization (PyTorch implementation). We used 3 iterations of the power method in our experiments.
A.3 MORE BASELINES ON ROTATED MNIST BENCHMARK
We provide two more baselines for the rotated MNIST experiments: Deep ensemble and DDU, Overall, we consider this example being too simplistic to make general conclusions and the experiment included in the main paper is mostly for illustrative purposed and sanity check. Nevertheless, more complete picture with additional based is presented on Figure 4 The NUQ distinctly outperforms ensembles on all examples and is on on-par with DDU on out-of-distribution test. However, NUQ is better then DDU in the example with rotated MNIST, Figure The possible reason is that NUQ considers total uncertainty which is natural this examples as rotated-MNIST has naturally the same classes MNIST and
in misclassification detection scenario (not pure OOD detection). DDU worse as it targets only epistemic uncertainty.
A.4 ABLATION STUDY ON CIFAR-100
A.4.1 CHOICE OF KERNEL FOR UNCERTAINTY QUANTIHICATION
In this section, we study the choice of a kernel for uncertainty quantification.
We consider the following choices:
We need a probability density estimation for our method, and there are different options: we consider kernel method with RBF kernel and logistic kernel and Gaussian mixtures models. There is also question about which embeddings to use the DDU paper proposes to take the features from the second last layer; we believe the logits from the last layer reasonable choice well. To validate
14

---

Under review as a conference paper at ICLR 2022
Kernel name
Formula K (u))
Integral K(u)
Gaussian (RBF)
exp -u=}
22
2
Sigmoid
a expl texp(a)
Logistic
exp (2+
Table 3: Different types of kernels (u)) considered and corresponding values of the integral
J K du.
the options, we conducted some ablation study on out-of-distribution detection for the CIFAR-100 dataset, similar to the main experiment.
First, we compare the DDU and NUQ on embeddings from the pre-last and last layer (Table on SVHN, LSUN, and Smooth datasets. Secondly, we compare the NUQ method on RBF, logistic kernel, and GMM for both last and penultimate layer embeddingssTablee 5). As we can see from the tables, the optimal is the option with GMM density the penultimate layer.
DDU, features
DDU, logits
NUQ, features
NUQ, logits
SVHN
89.6=1.6
88.240.6
89.7=1.6
88.240.6
LSUN
92.1+0.6
90.9+0.4
92.3+0.6
90.9+1.4
Smooth
97.1#3.1
96.3+4.1
96.8+3.8
96.244.1
Table 4: Comparison of DDU and NUQ predictions different type of embeddings logits (last. layer) and features (second last layer).
RBF f
RBF,
Logistic, f
Logistic,
GMM, f
GMM,
SVHN
84.4+3.2
84.7+3.1
84.8+2.9
86.7+2.6
89.7+1.6
88.240.6
LSUN
88.2+1.0
100.8
88,5+4.0
90.3*1.0
92.340.6
90.9+0.4
Smooth
85.5+6.8
87.7+9.4
86.2+8.2
90.8+7.8
96.8+3.8
96.2+4.1
Table 5: Probability density methods comparison radial basis function kernel (RBF), logistic kernel, gaussian mixture models (GMM). 'f" (Features) marks models, built on embeddings from a second last layer and 'I' (logits) is for the ones built embeddings from a last layer.
Kernel-based methods rely the "reasonable" geometry of the embedding space, meaning that embeddings of similar images should not be too far and different images should not collapse into a single point. Our motivation to spectral normalization during training make the embedding space more smooth with respect to input images. We have conducted an extra ablation study, comparing the result for feature extractors with and without spectral normalization, Table The results confirm our hypothesis, as the beats the baseline even without applying the modification the ResNet training. We also show here that entropy performs better than maximum probability as an uncertainty measure.
version performs better, though the NUQ
OOD dataset
MaxProb
Entropy
DDU DDU (spectral)
NUQ
NUQ (spectral)
SVHN
79.7+1.3
81.1+1.6
88.7+4.3
89.6+1.6
86.8+1.2
89.7+1.6
LSUN
81.5+2.0
83.0+2.1
91.3+0.9
92.1+0.6
91.2+1.1
92.3+0.6
Smooth
76.6#3.5
77.8+5.2
95.7+1.2
97.1#3.1
95.5+1.3
96.8+3.8
Table 6: Comparing the influence of spectral normalization on the model performance for OOD detection, ROC-AUC.
A.5 PERFORMANCE DIFFERENCE ON CIFAR- 100 AND IMAGENET
One of the things that caught our attention is superior performance of NUQ on ImageNet, given that it has very similar results with DDU CIFAR-100. One of our hypotheses that embeddings have more complex and multi-modaa distribution for more complex Imagenet dataset compared to simpler CIFAR- 100. To check this, made t-SNE based embeddings of out-of-distribution and test
15

---

Under review as a conference paper at ICLR 2022
First 15 classes CIFAR full embeddlings
First 15 classes Imagenet full embeddings
30
20
20
0
-10
-20-
000 (imagenet_
/
-30
-20 -10 0 10 20 30
-30
-20
-10
10
20
(a)
(b)
Figure 5: Embeddings space visualization for CIFAR (a) and ImageNet (b). We present the em- beddings for first 15 classes on test dataset (in various colors) and all the embeddings for out- of-distribution datasets (in blue). The OOD dataset for CIFAR SVHN and for ImageNet it ImageNet-R.
data (see Figure 5). While we understand the limitation of this type of visualization, the ImageNet embeddings appear be much more irregular compared to well-shaped clusters for CIFAR-100. Because of that the modelling of the class with single Gaussian (in DDU) might not work very well for ImageNet. NUQ approach performs the modelling of distributions much more flexible way which is beneficial for approximation of complex distributions. We hypothesize that this is the reason of the NUQ's 's superior performance.
A.6 TOY EXPERIMENT ON DETECTING ACTUAT, ALEATORIC AND EPISTEMIC UNCERTAINTIES
In this section, we conduct toy experiment, for which explicitly know what should be the true probability of class one, as well as the true data density.
Let consider binary classification problem. Our dataset consists of 5000 samples from three different mie-dimensional Gaussians, located so that classes are mixed (see picture). Colors denote class label: red 0; green 1 (Left in Figure 6) For this particular data model, we can compute the conditional probability of a data point x belongs to class 1: p(y = 1 Iz). We build an estimate of this conditional using our Nadaraya- Mattrayy--Wtsonn Watson kernel-based approach. Further, grid, and for each point of this grid, using our method, we can upper bound difference between the true conditional and our approximation. This difference, according to our approach, is considered as an epistemic uncertainty (Middle in the Figure 6). The green line in this plot denotes an absolute difference between the true conditional and our approximation. The red line denotes our epistemic uncertainty. From the picture, we can see that our epistemic uncertainty approximates the probabilities difference well. Next, we show how our aleatoric uncertainty relates to the true class conditional probability. In the right plot of the Figure 6 we show true conditional distribution p(y 1|ar) and our approximation the alcatoric uncertainty. We can see that our approximation is high exactly in the same regions where the true conditional is absolutely unsure about the class label.
generate uniform
A.7 PSEUDO-CODE
16

---

Under review as a conference paper at ICLR 2022
0.34
Data density
Data densiry prob. Alnatoric
0.12
Epistemic
0.30
Uncertaitty (spiseeii)
0.8
Proh. dilf.
Uncorainty (alatoric)
0.08
0.6-
0.4-
0.4
0.94
0.2
0.2
0.00
0.0-
0.0
-10
10
-10
10
Figure 6: Left: Mixture one dimensional Gaussians we took samples from. Color denotes class label. Middle: Epistemic uncertainty our model assigns to data points. Note that the uncertainty is quite high in the region 3-5. For the sake of visualization, clipped the maximum value be 1. Right: Our approximation of aleatoric uncertainty is built along with the true conditional probability.
Input:
Training set (( y:) inference point
Output: Prediction y(z) and uncertainty u(z)
K ( === &- K nearest neighbours of z among [x;),, N
(=(=)) <- En=1 (un, =2)
EE_ (mi, =2)
(2(2) Tc(2)(1 (1 ne(2)
0(2) argmax (2)
p(z) < NAd Ek Kn (2ix - 2)
?2(2) + Nha p(z) f K (u) 2 du
max (z)
u(z) - min { {z{} + 2 [z(2)
Algorithm 1: NUQ inference algorithm.
17


Reviews:
[{"review_id": "yBLZvDjjAD", "reviewer": "Reviewer_EX9M", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Relevance**: The paper proposes a deterministic uncertainty estimation method for deep learning. Various other methods in that direction have been proposed recently (SNGP, DDU, DUE, etc) to avoid computing an expensive model average over multiple forward passes. The submission is therefore timely and relevant.\n\n**Novelty**: My understanding is that the paper mostly combines results from the literature (the upper bound on the Bayes risk, the variance of the excess risk). This is of course a worthwhile contribution, but arguably at the lower end of the novelty spectrum. Prior work is clearly referenced.\n\n**Clarity**: The high-level flow of the paper is clear and easy to follow. In some places I feel like the text could be expanded a bit to not only re-state results from prior works, but give the reader some intuition forwhy they are true and how they are derived. More importantly, I find the paper fairly unclear regarding the method that is ultimately implemented, section 2 ends fairly abruptly for my taste. I would suggest adding an algorithm or pseudo-code box to make it clear what exactly is implemented. This would also help to substantiate the statement that the paper presents a “fast and scalable method”.\n\n**Empirical evaluation**: Overall the choice of problems and metrics is standard. My biggest concern is that the comparison to reasonable baselines is fairly lackluster. The small scale experiments (toy-classification and MNIST) only compare to deterministic networks which are well-known to not provide useful uncertainty estimates. So I find it hard to conclude much from these. An equivalent of Fig. 1 should be provided for DDU and the MNIST benchmarks from sections 4.2.1 and 4.2.2 should show results for ensembles and DDU (although I could imagine that the former won’t work very well out-of-the-box since MNIST is too simple, perhaps using something like FashionMNIST would be more interesting).\n\nThe ImageNet results look promising. It is a bit surprising, however, that NUQ is not able to outperform DDU on CIFAR100 (my impression is that usually if anything performance gains don’t translate from the smaller CIFAR datasets to ImageNet). The argument that the number of classes is too high for DDU is quite speculative. It seems to me like including another baseline method such as [SNGP](https://arxiv.org/abs/2006.10108) or [DUE](https://arxiv.org/abs/2102.11409) would solidify these results.\n\n**Other notes/questions**:\n* Just under eq (1): “In our experiments, we consider one dimensional kernel function”, but (2) has a power to dimensionality -- what exactly is happening here? Is the KDE fit jointly on all features or independent across dimensions?\n* The statement in the 3rd point at the end of the introduction that recent work “suffered from a lack of a principled method to quantify the uncertainty” is extremely vague and should be substantiated (what do you mean by principled and how is prior work not principled?) or removed.\n* “Thus, it might be beneficial to tune the bandwidth to optimize the quality of OOD detection if some set of OOD points is available at the training time”. I would ideally like to see a small ablation results on this, e.g. with the SVHN validation and test sets. It would be useful to know how much performance could be gained by tuning the bandwidth on a known OOD dataset.\n* The captions of Fig 2 and 3 are too close to each other and should be spaced evenly with Fig 4.\n* Broken link to supplement at the beginning of 4.2.1.\n* The references are formatted extremely inconsistently. Please don’t just copy-paste bibtex entries from google scholar, but make capitalization, initials/full first names, venue names etc consistent.\n", "summary_of_the_paper": "The paper proposes a post-hoc KDE-based method (NUQ) for single-pass uncertainty estimation. It reports improvements in robustness to data perturbation and OOD detection over deterministic networks on MNIST-based benchmarks, comparable performance to DDU (Mukhoti et al., 2021) on CIFAR100-based out-of-distribution detection and improvements on ImageNet.", "summary_of_the_review": "Overall, this is an interesting, but not groundbreaking paper with a few issues around clarity and the empirical evaluation, so I am currently **leaning towards a reject**.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "uS_nMplJdeS", "reviewer": "Reviewer_S6bt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\nReasons for score:\n\nAlthough the idea is interesting, my main concern is about the significance of the proposed method. See my detailed comments below.\n\n---\n\nPros:\n\n- The paper uses the excess risk and Bayes risk to quantify the epistemic uncertainty and the aleatoric uncertainty, which is interesting.\n- Practical method for large datasets is described, which is very important for nonparametric methods.\n- Substantial experimental results are provided on several different image datasets.\n\n---\n\nConcerns:\n\nMy first concern is about the significance of the proposed method. \n\n1) The method is actually only nonparametric in the feature space of a neural network. Therefore, the feature extracting process, which involves a large number of parameters, is extremely important. Although the uncertainty is defined rigorously, it is not clear whether it is still informative in the feature space of an arbitrary neural network. Previous work (Van Amersfoort et al., 2020;2021, Liu et al., 2020) shows that a crucial difficulty of uncertainty estimation in deterministic neural networks is feature collapse, i.e., the network maps both data samples and OOD samples to a very narrow region in the feature space, resulting in unexpected/uncalibrated predictive uncertainty. It seems the proposed method can also suffer from the feature collapse issue, while no theoretical analysis can be found in the paper (except that the issue is alleviated using spectral normalization, which is also proposed in previous work).\n\n2) The authors claim that the proposed method complements recent works that suffer from a lack of a principled method to quantify the uncertainty. However, there are several other methods that can produce principled uncertainty. For example, being Bayesian in the last layer (Kristiadi et al., 2020), which is equivalent to using a Bayesian linear/logistic regression in the last layer, or using a Gaussian process in the feature space (Liu et al., 2020), which is also kernel-based and nonparametric. Given the fact that these methods can also distinguish epistemic uncertainty and aleatoric uncertainty, what are the advantages of the proposed method compared with these methods?\n\n3) I also have a concern about efficiency. The authors described several existing methods as *still require setting additional hyperparameters and/or increased computational cost*. However, the proposed method requires extra GMM modeling, nearest neighbor search, and kernel bandwidth selection. I suggest the authors provide a detailed discussion and justification about the efficiency.\n\n\nMy second concern is about the experiments. As mentioned above, I think more methods should be compared, such as Kristiadi et al., 2020, DUQ and SNGP. The author has explained that the compared methods do not require significant modifications to model architecture and training procedures. However, given the fact that SN regularization is also adopted, the training procedure in the proposed method is actually modified and therefore the mentioned methods seem like fair competitors.\n\n---\n\nReference:\nAgustinus Kristiadi et al., 2020, Being Bayesian, Even Just a Bit, Fixes Overconfidence in ReLU Networks\n\n\n", "summary_of_the_paper": "This paper proposes a nonparametric uncertainty quantification method for deep neural networks. Using a kernel-based estimator of the conditional density (i.e., the predictive distribution $p(y|x)$) in the feature space of a pre-trained neural network, the epistemic and the aleatoric uncertainty can be obtained separately from an upper bound of the excess risk and Bayes risk. For practical feasibility, several subproblems are approached with existing methods, such as kernel density estimation/GMM for $p(x)$, Improved Sheather-Jones algorithm for kernel bandwidth selection, HMSW for fast nearest neighbors retrieval. Finally, good OOD detection performance is demonstrated on several image datasets including MNIST, CIFAR, and ImageNet.", "summary_of_the_review": "In summary, I raised several concerns about the theoretical and empirical significance of the proposed method, which currently prevents me from rating this paper higher. I will consider raising my evaluation if the authors address my concerns or point out my misunderstandings.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fFikSvJik3a", "reviewer": "Reviewer_CWxx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Using the logits as input to the kernel machinery may be problematic, as highlighted for example by Postels et al 2021 (arXiv:2107.00649), because these logits will be invariant to many directions in input space (especially if the input is high-dimensional, like an image, compared to the number of classes). It means that the output logits may be invariant to a large volume of changes that may occur when going from in-distribution to out-of-distribution (in fact to volume of output-sensitive directions may be of null measure), making ANY method unable to detect changes in those directions. Hence I would advise against using the output logits.\n\nIt is not clear to what extent NUQ is fundamentally different from DUQ (yes, using a sum of kernels rather than a mixture of Gaussians, depending on how many Gaussians are fitted, of course) and the results seem to be very similar between the two in table 1.\n\nFor MNIST vs greyscale SVHN, I see in fig 4 that NUQ does the same as the stupid entropy, which is interesting to observe and suggests that in this case it is easy to detect these OOD examples. I also notice that none of the more 'serious' competitive baselines (like Ensembles and DDU) were included in the evaluation. Why?\n\nHow were the other methods optimized? have you optimized the number of networks in the Ensemble, for example? How about MC-dropout: how are its hyper-parameters optimized? It does not look like the authors did a serious job of optimizing the hyper-parameters of the other methods.\n\nHow accurate is the proposed method in terms of estimating the TRUE epistemic uncertainty? In cases where the generative distribution is known, this should be easy to compute. And how would that compare with PROPERLY OPTIMIZED alternatives?\n", "summary_of_the_paper": "\nThis paper proposes NUQ, a kernel-based estimation of epistemic uncertainty regarding a kernel-based probabilistic classifier applied on the input or on the top hidden layer on on output logits of a pre-trained deep net classifier.\n\nExperiments on OOD vs in-distribution binary classification based on the uncertainty score suggest that NUQ works better than several other methods.\n", "summary_of_the_review": "\nThe proposed approach is suspicious on theoretical grounds, in that it relies essentially on the ratio of some estimation of training uncertainty and density in representation-space in order to estimate epistemic uncertainty.\n\nThe experimental results are also worrisome because it does not look like appropriate efforts were made to tune the hyper-parameters of baseline methods.\n\nFinally, there is no attempt to actually compare the estimated epistemic uncertainty with the ground truth epistemic uncertainty.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a simple approach to quantify uncertainty in "deterministic" neural networks, not unlike the works of SNGP, DDU, and DUE, where one only performs one forward pass rather than in an ensemble or Monte Carlo sample. In particular, they propose a kernel-based method on a network's logits to estimate uncertainty, obtaining data and model uncertainty estimates separately using a bound on Bayes risk.

While I agree with the relevance of the problem, there's a shared concern among reviewers across both technical novelty and experimental validation---particularly compared to prior work that can be difficult to understand the key distinguishing factor. I recommend the authors use the reviewers' feedback to enhance their preprint should they aim to submit to a later venue.
Decision: Reject