Greedy Bayesian Posterior Approximation with Deep Ensembles
Authors: Aleksei Tiulpin
Matthew B. Blaschko
Venue: ICLR 2022 Submitted (2022)
Keywords: Bayesian posterior
deep ensembles
submodular optimization

Abstract: Ensembles of independently trained neural networks are a state-of-the-art approach to estimate predictive uncertainty in Deep Learning, and can be interpreted as an approximation of the posterior distribution via a mixture of delta functions. The training of ensembles relies on non-convexity of the loss landscape and random initialization of their individual members, making the resulting posterior approximation uncontrolled. This paper proposes a novel and principled method to tackle this limitation, minimizing an $f$-divergence between the true posterior and a kernel density estimator in a function space. We analyze this objective from a combinatorial point of view, and show that it is submodular with respect to mixture components for any $f$. Subsequently, we consider the problem of greedy ensemble construction, and from the marginal gain of the total objective, we derive a novel diversity term for ensemble methods. The performance of our approach is demonstrated on computer vision out-of-distribution detection benchmarks in a range of architectures trained on multiple datasets. The source code of our method is made publicly available.

Under review as a conference paper at ICLR 2022
GREEDY BAYESIAN POSTERIOR WITH DEEP ENSEMBLES
APPROXIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Ensembles of independently trained neural networks are state-of-the-art approach to estimate predictive uncertainty in Deep Learning, and can be interpreted as an approximation of the posterior distribution via a mixture of delta functions. The training of ensembles relies on non-convexity of the loss landscape and ran- dom initialization of their individual members, making the resulting posterior approximation uncontrolled. This paper proposes a novel and principled method to tackle this limitation, minimizing an laaiggnnnnaiiiii f-divergence between the true posterior and a kernel density estimator in function space. We analyze this objective from a combinatorial point of view, and show that it is submodular with respect to mixture components for any f. Subsequently, ensemble construction, and from the marginal gain the total objective, we derive novel diversity term for ensemble methods. The performance of our approach is demonstrated on computer vision out-of out-of-distributin distribution detection benchmarks in a range of architectures trained multiple datasets. The source code of method is made publicly available.
consider the problem of greedy
INTRODUCTION
Estimation of predictive uncertainty is one of the most important challenges to solve in Deep Learning (DL). Applications in finance, medicine and self-driving cars are examples where reliable uncertainty estimation may help avoid substantial financial losses, improve patient outcomes, or prevent fatal accidents (Gal 2016). However, to date, despite rapid progress, there is a lack of principled methods that reliably estimate the predictive uncertainty of deep neural networks (DNNs).
Numerous attempts have been made to develop Bayesian techniques for uncertainty estimation in
DL (Gal & Ghahramani] 2016 Lakshminarayanan et al./ 2017 Wilson & Izmailov 2020 Maddox
ett al. 2019 Izmailov et al. [2020] Van Amersfoort et al.) 2020; Wenzel al.) [2020b). One of
the most practical and empirically best-performing approaches is based on training a series of independent DNNs (Lakshminarayanan et al. 2017; Wilson & Izmailov] 2020; Ashukha al.)
2020:
Lu et al. 2020
[ Wenzel et al. 2020b). The main method in this category. Deep Ensembles
(DE)
Lakshminarayanan et al. 2017 is used as reference approach in the context of this paper.
Recent studies, e.g. Wilson & Izmailoy (020) interpret ensembles as an approximation of predictive posterior. While this interpretation is correct from a Bayesian point of view, obtaining individual ensemble members via maximum a posteriori probability (MAP) estimation, as e.g. done in DE (Lakshminarayanan et al. 2017), may not lead obtaining good coverage of the full support of the posterior distribution, and has arbitrary bad approximation guarantees. For example, the resulting approximation can be poor in the case when the true posterior distribution is unimodal. In this work, we argue that enforcing coverage of posterior (i.e. ensemble diversity) is non-trivial, and needs specialized principled approach. We highlight this graphically in Figure
Another important line of work in modern Bayesian DL (BDL) is paradigm of performing Bayesian inference in the weight space. While distributions over weights induce distributions over func- tions (Wilson & Izmailov 2020), it is rather unclear what the properties of such functions are, and whether Bayesian posteriors obtained in the weight space yield good quality approximations in the function space. For example, it is known that diverse weights do not necessary yield diverse functions, thus sampling from weight- based posteriors may yield poor quality uncertainty estimation, e.g. in detecting auttof-distribution (OOD) data (Garipov et al. 2018 Hafner et al. 2020).

---

Under review as a conference paper at ICLR 2022
2.4
9.2
0.20
2.2
015
2.
04-
0.0
15 30 0.0
15
25
20
(a)
(b)
(C)
Figure 1: Illustration of how method (c) approximates ID multimodal distribution p(z) com- pared to randomization-base mode picking (a), and naïve diversity training (b). Blue shows the true distribution and red approximations. This figure can be reproduced using the provided source code.
Recent studies (Wang et al. 2019 D' Angelo & Fortuin inference (POVI) done in the function space, however, the performance of those methods is not state-of-the-ar due to the use of BNN priors. In practice, a weight decay prior combined with batch normalization, data augmentation and dropout are often employed due to empirical improvement, and theoretical guarantees are traded for practical performance. Furthermore, space VI requires training an ensemble of BNNs simultaneously, which is not only difficult to implement, but also requires extensive resources for parallelization.
2021) show the promise of particle variational
function
Summary of the contributions. In this paper, we propose a novel and principled methodology for approximate function space posterior inference for DNNs. Contrary to the mainstream approach BDL, which based on defining a posterior distribution over the model parameters (Maddox al. 2019), we take functional view, which allows optimization over sets. Namely, selecting a set of functions to approximate the Bayesian posterior is fundamentally similar to problems such facility location and cover, which frequently solved using submodular optimization (Krause et al. 2008). Specifically, our contributions are:
treat the problem of training ensembles as
We show that fitting a kernel density estimator to a distribution using an f-divergence is cardinality- fixed non-monotone submodular maximization problem.
2. Inspired by the Random Greedy algorithm for submodular maximization (Buchbinder et al. method for the function space Bayesian posterior approximation via
2014), design greedy training of ensembles with justified coverage-promoting diversity term.
3. We demonstrate the effectiveness and competitiveness of our approach compared to DE in the OOD detection task on MNIST, CIFAR, and SVHN, benchmarks tures and ensemble sizes. Furthermore, we show that our method can use state-of state-of-the-ar training technqiues, compared to the existing Bayesian approaches, and yeilds state-of -hhee----- art performance.
different architec-
PRELIMINARIES
2.1 PROBLEM STATEMENT
Consider an ensemble to be parameterized by set of functions 2 = {2m [ C F, where F is class of continuous functions, 2m RRd RR', with d the dimensionality the imput data, and e the dimensionality of the output. When training ensembles, we generally want to solve the following optimization problem:
min R(Z) 1xx (Z),
2,12 =M
where R(2) = + MN
37 EM 1 2m (x;). is the empirical risk the ensemble, E: V'yy -
R. is a loss function, D = {I,, Vi V is training dataset of size N, and Zxxr (Z) is some diversity- promoting term, with diversity regularization strength Am-
Empirical observations in the earlier works on ensembles (Lakshminarayanan et al. 2017 Wilson
& Izmailov 2020: Fort et al. 2019) have shown that simply ignore axy (2), and rely
2

---

Under review as a conference paper at ICLR 2022
non-convexity of the loss landscape, optimizing the risks of individual ensemble members. From variational inference (VI) perspective (Zhang et (011), this can be seen as a mode-seeking method, and it has been shown experimentally that every ensemble member may discover different modes of the posterior distribution in the function space p(z[D).
Approximation of p(z|D) is the ultimate aim of this paper, and argue that randomization- based mode-seeking is insufficient to obtain a good quality approximation of p(z[D), as this procedure does not maximize the coverage of the support of the posterior. By contrast, we aim find an Sx ) such that the posterior coverage is also maximized. Taking a VI perspective again (Zhang al., 2019). 22 ( (Z) needs to enforce that 1 = M R(Z) Qxx (Z) has rather seen-sseeing behavior, while still discovering the high density modes.
2.2 A COMBINATORIAL VIEW OF ENSEMBLE CONSTRUCTION
Having now defined the main criteria for TT) we highlight that the problem of constructing an ensemble can be seen from a combinatorial point of view. We therefore treat ensemble construction as subset selection from some ground set of functions, and introduce the main notions of submodular analysis, a powerful tool that enables the analysis of the optimization of set functions (Bach 2013 Fujishige 2005).
Definition 1 (Submodularity), A set function g 2 + R. for the power set of a base set V, is submodular for all C V and V \B
- 2 (BU g(().
Definition 2 (Supermodularity and modularity). A set function is called supermodular if its negative submodular, and modular if it both submodular and supermodular.
Consider now problem (
Assuming that the loss function É is convex, can derive an upper-bound on the risk RZ) using Jensen's 's inequality, and obtain a method, which generalizes DE
1 M
min Z
R(zm) Sxsr
If M is fixed during optimization, 1 Em=1 R(2m) contributes a positive modular term to the overall objective. Adding a positive modular function to any set function does not change its submodularity or supermodularity, thus focus ax (Z). A trivial approach would be to enforce wiie diversity by computing norm of the pairwise differences between functions, submodular minimization problem. It is known that it strongly NP-hard, i.e. there exists no general polynomial time approximation algorithm for it (Svitkina & Fleischer 2011). The poor quality approximation of this approach is highlighted in Figure I We therefore conclude that the choice of f2x,, (Z) has direct impact on the approximabilty of the objective.
ie. setting axx (Z) Av Eizz || 2, 11. However, this is cardinality-fiae
SUBMODULAR ANALYSIS OF F-DIVERGENCES
3.1 Í-DIVERGENCES SUPERMODULAS FUNCTIONS
Main result. We now consider the problem of approximating Bayesian posterior via minimization of an f-divergence. Here, we specifically aim our optimization procedure to have both mode and mean-seeking behaviors, i.e. cover the posterior distribution much as possible, ending up in its mode. We furthermore aim to obtain a polynomial time algorithm that yields a good quality approximation guarantee. In this paper, we leverage classic definitions of approximation algorithm and approximation guarantees.
Definition 3 (Approximation algorithm and guarantees (Williamson & Shmoys, 2011 A 7- approximation algorithm for optinization problem is polynomial -imee algorithm that for all instances of the problem produces a solution whose value within a factor o of the optimal solution. y in this case called approximation guarantee.
3

---

Under review as a conference paper at ICLR 2022
Let us now formally introduce f-divergences. Definition 4 (f (f-eieergence). Let f: R - RR be a convex finction such that f(1) 0. The f-divergence between distributions P= and Q= (P= being absolutely continuous with respect to Qz). admitting densities p(z) 2) and g(z) defined as
Dy(P:1lQ:) /
((2) ((2))
(()ddz.
(4)
Consider some density p(=) over continuous functions. We define gM = M Σm= K(d(2,
2,)).
Kj(z) (2, 2ÿ) is kernel centered at 2j used approximate the modes of p(z). Theorem 1. f f-divergence
(
p(2) E E5 Ky(2)
Σ M
1
Km (2)dz
(5)
between distribution p(z) and normalized mixture of M kernels with equal weights is supermodu- alar in cardinality- fixed setting, assuming that 42 maxqM Dy(p(z) (gas (2)) cc.
Proof. The proof is shown in Appendix A.I
Minimization of 5 is equivalent to constrrin maximization of non-monotone Approximation guarantees for problems of this form are
submodular function of Z f2...... 3. given for non -egativee submodular functions (Buchbinder et al. 2014).
One can convert ( to a non-negative function by defining:
F(Z) := (Dy(pl))))) +
where C maxz ((p) is pre-defined constant, which is important for understanding approxi- mation guarantees, but does not need be computed in practice. After the described transformation, which leads to 66, we obtain F (Z)) a non-negative non-monotone submodular function.
Approximation guarantees for f-divergences. In the context of submodular functions, there exists an inapproximability result, obtained in (Gharan & Vondrák (011), which states that no general polynomial time algorithm with guarantees better than 0.491 exists solve submodular maximization problem with constrained cardinality. We, however, that in practice, it might still be possible to obtain better approximation factor than 0.491 for some specific types of divergences, as these guarantees are defined for all instances of the optimization problem (Definition 3).
Let us consider the approximation guarantees for 6 denoting by lhr the optimal solution, and by fM solution found by some algorithm. For an approximation factor we have
(Py(ll) + 2 (-D (xllat) C).
Simple algebra shows that this implies
Dy(pl(âm) S Y min (y(pl(g + (1 77) max D (p(pl)qas) QMEF
where F is a family of distributions over the spaces of candidate functions. The derived result indicates that the upper bound on the approximate solution found by minimizing an f-divergence can be substantially dominated by (1 (1) max D (pllgm) if F is chosen poorly. The impact of the choice of function space, determined largely by the neural network architecture, is therefore unavoidable when designing algorithms for approximating the Bayesian posterior.
3.2 GREEDY MINIMIZATION OF SFEEEIONNEODDEEEEEEEEEEEE f-DIVERGENCES
Random greedy algorithm. Although submodular optimization has natural parallel extensions and associated approximation guarantees, due to the simplicity of presentation, we focus in this paper on forward greedy selection and use Algorithm for optimizing submodular functions. This algorithm has approximation guarantee of 1/e in general. The only required step for this greedy algorithm is a computation of the marginal gain on the objective function F(Z), i.e. A(a = F(Z U {=x}) F(Z). We argue that due to randomized initialization in neural networks, one can use a naive greedy algorithm instead of the sampling procedure in lines 7 and we show the implementation of the resulting training procedure in Appendix B.
4

---

Under review as a conference paper at ICLR 2022
Algorithm Random Greedy algorithm
1: Input: V Ground set
2: Input: F Arbitrary submodular function
3: Input: M Cardinality of the solution
4: Z 5-0
5: for m 1 to M do
6:
< arg maXTCV Ever A(z1Z)
7:
u; f Uniform
8:
+ Z U }
9: end for
10: return Z
Marginal gain. At each step of a greedy algorithm, a marginal gain (zz|Z)= = F(Z U (xx})
F(Z) of adding new element 2 to an existing mixture E/=1 K2(2) is maximized. For f- divergences, we thus formulate the following proposition:
Proposition 1. Consider C max ( where Dy(pllga) is an arbitrary f-divergence be- tween some distribution p(z) and mixture of kernels qm (M) = M Σş Kz(2), and D Dy(pllam) < 00. Then, maximization of a marginal gain for set function
F(Z) -1)=--11( |
p(z)
Σ m=1
M
Km (2)d2
(9)
M
at step k of a greedy algorithum corresponds to
p(2)
arg max (zzk 2) = arg min E (.)
(10)
1= K2(
M
Proof. The proof is shown Appendix A.2
The case of reverse KL divergence. Having mean-seeking behavior useful to fit the kernel density estimator using forward divergences. However, if one wants to optimize marginal gains, they need have a mode-seeking behavior, which is achieved via optimizing reverse divergences (Zhang et al. 2019).
If we consider the generator for the reverse KL-divergence, f(x) simplifies to
llog x, the minimization
min Bz~ 1o) + log
Σ K5(2))
(11)
M
In the sequel, we leverage the standard reverse KL-divergence generator, which aims to discover the modes of p(z), but also enforces the coverage of the approximation. Finally, note that it is costly to compute the expectation in practice; we thus use the following point estimate of (T)
k- K5((H)
min - log (o2)((22) + log
Σ
(12)
M
4 GREEDY APPROXIMATION OF THE BAYESIAN POSTERIOR
Objective function. In this section, we consider parametric functions Rd + RS, where denotes the parameters determining the function. We now use Bayes' theorem and mean-field approximation to express the posterior of an ensemble of such functions as
p(2olD) x p(20, ........... ...., 20 (D)
II p(D) k0... )p(2o.)) m=1
(13)
5

---

Under review as a conference paper at ICLR 2022
where 8m parameters, p(D (0) the likelihood and p(2e) the prior; p(D]20)
Ih= (xp((=(2x(zz)) yi)). and p(2p) & exp(->]013)
To solve the problem defined by [2) in the context of Bayesian posterior approximation, we define the kernel density components via generalized exponential kernels Kj (z() oc Spp(-Aas((za... )²,
where AM is proportional to the kernel width. Therefore, at hthh greedy step, we minimize
J(O)) = ((x.)))-pa..)) (22 (x). + 11 + log Σ exp (- AM j=1
(-M d(zg2, 20, 2l,6):20,))))
(14)
Marginal gain on R(Z)
Marginal goin R2
which is similar to the marginal gain originally defined high-level objective I except that the diversity term Q has a different form based on our submodular f-divergence optimization.
Sampling- baased approximation of the diversity term. able to compute the diversity term Ω log Σ (5(-Ard(( žq; =0,)²) )²), which is derived from
When minimizing (14). one needs to be
kernel density estimator we aim to fit the true posterior. We note that this needs to be done in the function space, which makes this computation non-trivial.
We earlier defined (=(=) to be an individual kernel in mixture 37 Σド= Ky(2). In order to be able use the f-divergence, the individual components Ky(=) must be density functions centered at zj- which implies the need of notion of similarity or the existence of a function norm, which are known be NP-hard compute for any neural network with depth greater than 3 (Rannen-Tiie Triki al. 2019). We note that this intrinsic hardness result applies to all methods that define a meaningful posterior distribution in function space through kernel density estimator. We thus use here method from (Rannen- Triki et al. (2119) to approximate || 112 via i.i.d. samples Z; P", where p is weighting distribution, which is required to ensure that Monte Carlo integration yields a reasonable approximation. This leads to the following sampling-basse baased approximation of the diversity term:
AM M
log
exp
(-M
E Exnp's (a) I0p (x) z0, (x)1
(15)
note on practical implementation. To this point, we defined all the main components of our method, except the weighting distribution in (15). The desirable behavior, which expect ensemble to exhibit, is that it must be uncertain on the OOD data and certain in the regions where the training data are available. This implies that p" p"(x) must include OOD samples. One can use OOD data in training explicitly, however, we resort to setting when OOD data are unknown, and use simple heuristic, which fits Gaussian to every data dimension with the variance x5 larger than the variance of the data. We specify further details about the full algorithm in Apppeddix B.1
RELATED WORK
Haadomiizatio--basee ensembles. Generally, ensembles have been studied in Machine Learning over several decades for different classes of models (Hansen & Salamon, 1990; Breiman 1996
Freund & Schapire 1997| Lakshminarayanan et al. 2017). One distinguish several main methods
for diverse ensemble construction (Pearce et al.] (0200: randomization training initialization and hyperparameters (Hansen & Salamon] 1990 Wenzel al. 2020b Wilson & Izmailov 2020 Zaidi
et al. 2020), bagging (Breiman) 1996 2001), boosting (Freund & Schapire 1997). and explicit
diversity training (Kuncheva & Whitaker 2003 Ross al.) |2200] Yang al. 2020 Brown al.
2005 Kariyappa & Qureshi 2019 Sinha et al. 2020 Melville & Mooney] 2005). Randomization
based ensemble construction has shown good results in in-domain uncertainty (Ashukha al. 2020
estimation, but also in the detection of OOD data [Lakssminarayanan et al. 2017).
Submodular ensemble pruning and greedy ensemble construction Submodularity in ensemble learning has previously been discussed in the context of ensemble pruning (Sha et al., 2014). The

---

Under review as a conference paper at ICLR 2022
goal of ensemble pruning is to trim a large ensemble of models that the accuracy of the ensemble remains the same. We note that recently, inspired by the submodular pruning approach, a greedy algorithm has been applied to randomization based ensembles (Wenzel et al. 2020b) Zardi et al.] 2020). However, we also note that neither of these works approached the problem of ensemble construction from Bayesian posterior approximation point of view. However, they provide extensive experimental evidence on the plausibility of greedy approach. Our work sheds light on why in Wenzel al. 2020b; Zaidi et al. (2220) ensembles constructed greedily worked well in OOD detection tasks.
Diversity-rromoting regularization for ensemble training. The ensemble literature contains a
line of work focusing on explicitly promoting regularization in ensembles (Kuncheva & Whitaker
2003 Ross et al. [020 Yang et al. [2020] [Brown et al., [2005] Kariyappa Qureshi] 2019 [Sinha
al. 2020 Melville & Mooney| 2005 Havasi et al. [202]] In terms of promoting diversity outside
training data, the closest work to ours is (Ross et al., 2020; Rame & Cord. 202I), and in terms
of the form of diversity regularization it is (Kariyappa & Qureshi| 2019). However, none of these
works takes the perspective of approximating the Bayesian posterior. Another limitation of most of these approaches is that they use either out-of-distribution data in training, adversarial examples, or expensive generative models, thus making those methods difficult to scale to large datasets.
POVI A problem of learning diverse ensembles can be seen from POVI perspective: in particular Stein Variational Gradient Descent (SVGD) (Wang & Liu, 2019). SVGD aims to learn diverse set of functions Z, approximating arbitrary distributions via set of particles using a reverse KL divergence. This approach is similar to ours, however, we tackle the problem of optimizing general f-divergence in the function space. Furthermore, to our knowledge, the present work is the first that takes submodular minimization perspective in BDI.
Greedy POVI Another line of work in the POVI family also considers greedy approximations (Fu- [ami et al. 2019; Jerfel et al., 2021). In both of these works, the authors perform particle based inference by also optimizing the kernel widths of the KDE, which is different to our method. Further- more, these works do not tell what the diversity term for ensemble training should look like, and how to compute it in practice.
Function space POVI Conventionally, Bayesian inference in DL is thought of in the weight space (MacKayl 1992. Blundell et al. 2015 Gal & Ghahramani] 2016 Izmailov et al. 2020 Wilson & Izmailov] 2020 Pearce al. 2020 Wenzel et 2000a). However, recent studies point out that despite the fact that simple priors over weights may imply complex posteriors in the function space,
the connection between two of these is difficult to establish (Sun al.
2019: Hafner et al. 2020).
Recent papers on function-space POVI (Wang et al. 2019 D Angelo & Fortuin 2021) point out that one can do Bayesian inference in the function space by optimizing an objective function with a repulsive term. Notably, they draw connection to the reverse KL-divergence minimization, and we thus consider our method to be closely connected to function space POVI.
EXPERIMENTS
6.1 SETUP
Datasets and models. We ran our main experiments on CIFARIO. CIFARI00 (Krizhessky) 2009) and SVHN (Netzer et al.) 2011) in-distribution datasets. Our OOD detection benchmark included CIFAR1O, CIFAR 100, DTD (Cimpoi et al. 2014). SVHN (Netzer et al. 2011). LSUN (Yu et al.) 2015), TinyImageNet (Le & Yang 2015p. Places 365 (Zhou et al. 2017). Bernoulli noise images, Gaussian noise, random blobs image, and uniform noise images. The composition of the benchmark was inspired by the work of Hendryeks et al. (2018). We excluded the in in-distribution datasets for each of the settings, resulting in total of 10 OOD datasets for each in-distribution dataset. The full description of the benchmark is shown in Apppeddix B.2,
The experiments were conducted using 16s (pre-activated version; denoted as PreRes- Net164) (He et al. 2016). VGG16 (with batch normalization (Toffe & Szegedy 2013): denoted as VGG16BN) (Simonyan & Zisserman) 2015), and WideResNee28x 10 (Zagoruyko & Komodakis
7

---

Under review as a conference paper at ICLR 2022
(a) Deep Ensembles
(b) AM = 0.1
(c) AM
(d) AM 10
Figure 2:
Uncertainty of ensemble of two layer neural networks
moons dataset (size
M = 11). Compared to DE, which is uncertain only close to the decision boundary, our method yields the desired behavior the further we move from training data, the higher uncertainty is. Such behavior is controlled by the diversity regularization coefficient AM-
2016). All our models in the ensembles were trained for 100 epochs using PyTorch (Paszke et al. 2019), each ensemble on a single NVIDIA V100 GPU. In the case of CIFAR and SVHN experiments, we trained ensembles of size M 11, and report the results across 5 different random seeds. For the CIFAR experiments, we selected Am f0.001, 0.005, 0.01, 0.05, 0.1, 0.5. 1,3, 5, 7, 10). In addition to the CIFAR and SVHN experiments, we used MNIST (LeCun et al. 1998) with ResNet8. The
details of those experiments are shown in Appendix B.2
Model selection and metries. We used mutual information (MI) between the distribution of predicted label ý for the point & and the posterior distribution functions P(f(D), to evaluate the epistemic uncertainty (Malinin & Gales 2018 Depeweg et al. 2018) and reported the area under the ROC curve (AUC) and area under the precision-recal (PR) curve, i.e. average precision (AP) to quantify the OOD detection performance. Furthermore, we computed the false positive rate at 95% true positive rate (FPR95). Details the computation of epistemic uncertainty can be found in Appendix B.3
6.2 RESULTS
Illustrative examples. Figure illustrates how our method performs on the two moons dataset. Here, we used two-layer fully-connected network with ReLU activations (Fukushima 1988). Having a high AM is important to obtain good uncertainty estimation. As expected, compared to our method, the DE method does not explicitly maximize the coverage of the posterior, and thus fails to be uncertain outside the training data.
nut-of-distribution detection. We present aggregated results for all the models and in-distribution datasets in Table I It is clear that on average (across OOD datasets), our method is substantially better than DE. This holds for all the architectures and in-distribution datasets. We show the expanded version of all the OOD detection results in Appendix C.3) An example of these results is shown in Figure 3 for all the models trained on CIFAR 100. Here, one can see that our method is at least similar to DE, and substantially better overall. Finally, some examples of OOD detection by both DE and our method are shown in Figure 4 Here, we computed optimal thresholds for each of the methods by optimizing the trade-off between the true positive and true negative rates.
DISCUSSION
In this paper, we have introduced novel paradigm for Bayesian posterior approximation in Deep Learning using greedy ensemble construction via submodular optimization. We have proven new general theoretical result, which shows that minimization of an f-divergence between some distribution and kernel density estimator has approximation guarantees, and can be done greedily. We then derived a novel coverage promoting diversity term for ensemble construction. The results presented in this paper, well in Anpppediix C.4 demonstrate that method outperforms the
8

---

Under review as a conference paper at ICLR 2022
Table Averaged metrics across OOD datasets.
Deep Ensembles
Ours
Model
Dataset
AUC (?)
(1)
FPR95 (
(?)
AP
(1)
C10
0.92
0.95
Pr
C100
0.79
0.80
0.47
0.88
0.88
0.40
SVHN
0.99
0.97
0.02
1.00
0.98
0.01
C10
0.95
0.94
0.15
0.96
0.96
0.12
11deResNe128x10
C100
SVHN
0.99
0.96
0.03
1.00
0.99
0.01
C10
0.92
0.91
0.23
0.95
0.95
0.18
VGGI6HN
C100
0.83
0.82
0.45
0.89
0.90
0.36
SVHN
0.02
Lap reageed
(a) PreResNet164
(b) VGG16BN
(c) WidoResNet28x10
Figure 3: Out-of distribution detection results CIFAR 100 for different architectures (read column-wise). Here, we show AUC values from 0.5 to averaged across 5 seeds.
Ouc 0.21
Bar 3.00
Del 5.00
Bul
6
7399 CE:1-13
8
DC 035
BE 8664
PC 333
0E:3-6
BE 8.
BE: 3:10
DE: 605
BE 6.12
Dt: 6.2
(a)
(b)
Figure OOD detection examples. In subplot (a), the top row shows true positives, and the bottom true negatives detected by our method. We also show the uncertainty values. Subplot (b) shows the failures of both DE and our method on positives (top row) and negatives (bottom row), respectively. Here, we used PreResNet16A trained on CIFARIO (M 11). SVHN was used an OOD dataset.
state-of-the-ee approach for ensemble construction, DE (Lakshminarayanan al. 2017), on range of benchmarks.
This study has some limitations, which outline several directions for the future work. Firstly, we did not compare our approach to variety of existing methods for ensemble generation, e.g. snapshot ensembles (Huang et al. 2017). batch ensembles (Wen al. 2020) or hyperparameter ensembles heuristic, and as discussed in the related work.
(Wenzel et al. 2020b). However, these methods our method can be used conjunction with them to make them more principled. Furthermore, we note that the main contribution of this paper is novel theory.
The second limitation of this work is that does not compare to f-POVI Wang et al. 2019) Annelo & Fortuin (2021). However, noted earlier, those methods are in different class, they focus on training models without trate-of-the-e art training techniques such as batch normalization (loffe Szegedy 2015) and data augmentation.

---

Under review as a conference paper at ICLR 2022
The third limitation is that did not fully explore different techniques of generating weighting distributions for the diversity term. However, we still evaluated the possibility using real images for this purpose in outlier exposure (Appendix C.4).
The final limitation is related to our method, as lacks parallelization possibilities compared to DE. We note, however, that there is class of parallel submodular optimization algorithms that enable parallelization and retain approximation guarantees (Ene Nguyen 2020).
To conclude, this paper provides novel foundational framework for Bayesian Deep Learn- ing. We hope for the wide adaption of the proposed method by practitioners across the fields. Our code is available athttps://anonymoos 4open. sci wtwpe//ggeeeyy.eeeeeee/e///eeeee enseeeedde_eeembmmeeeee
t Eraining-OCD5
REFERENCES
Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov. Pitfalls of in-domain uncertainty estimation and ensembling deep learning. arXiv preprint vrXiv:2002.06470, 2020.
Francis Bach. Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning. 6(2-3):145-373, 2013.
Francis Bach. Submodular functions: from discrete to continuous domains. Mathematical Program ming, 175(1):419455, 2019.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International Conference on Machine Learning, pp. 1613-1622. PMLR, 2015.
Leo Breiman. Bagging predictors. Muchine learning, 24(2):123-140, 1996.
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
Gavin Brown, Jeremy L Wyatt, Peter Tino, and Yoshua Bengio. Managing diversity in regression ensembles. Journal of machine learning research, 6(9), 2005.
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fftth annual ACM-SIAM symposium on Discrete algorithmss, pp.
SIAM, 2014.
Mircea Cimpoi, Subhransu Maji, lasonas Kokkinos, Sammy Mohamed, and Andrea Vedaldi. De- scribing textures in the wild. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pp. 3606-3613, 2014.
Francesco D' Angelo and Vincent Fortuin. Repulsive deep ensembles are bayesian. arXiv preprint arXiv:2106.1 1642, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Stefan Depeweg, Migeel Hernandez-Lobato, Finale Doshi-Velez, and Steffen Udluft. Decom- position of uncertainty bayesian deep learning for efficient and risk-sensitive learning. In International Conference Machine Learning, pp. 1184-1193, PMLR, 2018.
Alina Ene and Huy Nguyen. Parallel algorithm for non-monotone dr-submodular maximization. In International Conference Machine Learning, pp. 2902-2911. PMLR, 2020.
Stanislav Fort, Huiyi Hu, and Balaji Lakshninarayanan. Deep ensembles: A loss landscape perspec- tive. arXiv preprint arXiv:1912.02757. 2019.
Yoav Freund and Robert E Schapire A decision -eciornttthhrticccccco generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 199-199,,13,,, 1997.
Satoru Fujishige. Submodular functions and optimization. Elsevier, 2005.
10

---

Under review as a conference paper at ICLR 2022
Kunihiko Fukushima. Neocognitron: A hierarchical neural network capable of visual pattern recognition. Neural networks, 1(2):119-130, 1988.
Futoshi Futami, Zhenghang Cui, Issei Sato, and Masashi Sugiyama. Bayesian posterior approximation via greedy particle optimization. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3606-3613, 2019.
Yarin Gal. Uncertainty in Deep Learning. PhD thesis, University of Cambridge, 2016.
Yarin Gal and Zoubin Ghahramani. Dropout as a Bayesian approximation: Representing model uncertainty in deep learning. In international conference machine learning, pp. 1050-1059.
PMLR, 2016.
Timur Garipov, Pavel Izmailov, Dmitri Podoprikhin, Dmitry Vetrov, and Andrew Gordon Wilson. Loss surfaces, mode connectivity, and fast ensembling of DNNs. Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 5803-8812, 8812, 2018.
Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 1098 1116. SIAM, 2011.
Danijar Hafner, Dustin Tran, Timothy Lillicrap, Alex Irpan, and James Davidson. Noise contrastive priors for functional uncertainty. In Uncertainty in Artificial Intellignce, pp. 905-914. PMLR, 2020.
Lars Kai Hansen and Peter Salamon. Neural network ensembles. IEEE transactions pattern analysis and machine intelligence, 12(10))993-100) 1001, 1990.
Marton Havasi, Rodolphe Jenatton, Stanislav Fort, Jeremiah Zhe Liu, Jasper Snoek, Balaji Lak- shminarayanan, Andrew Mingbo Dai, and Dustin Tran. Training independent subnetworks for robust prediction. In International Conference Learning Representations, 2021. URL
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 630 645. Springer, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. arXiv preprint arXiv: 1ttp//993.....1 2019.
Dan Hendrycks, Mantas Mazeika, and Thomas Dietterich. Deep anomaly detection with outlier exposure. arXiv preprint 1812::111..466000 2018.
Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E Hoperoft, and Kilian Q Weinberger. Snapshot ensembles: Train 1, get for free. arXiv preprint arXiv:1704.00/00 2017.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Pavel Izmailov, Wesley Maddox, Polina Kirichenko, Timur Garipov, Dmitry Vetrov, and An- drew Gordon Wilson. Subspace inference for Bayesian deep learning. In Uncertainty in Artificial Intelligence, pp. 1179-1179. PMLR, 2020.
Ghassen Jerfel, Serena Wang, Clara Fannjiang, Katherine A Heller, Yian Ma. and Michael I Jordan. Variational refinement for importance sampling using the forward Kullback-Leibles divergence. arXiv preprint arXiv:2 00..0.0...600 55800, 2021.
Sanjay Kariyappa and Moinuddin K Qureshi. Improving adversarial robustness of ensembles with diversity training. arXiv preprint arXiv:1901.0998) 2019.
Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008
11

---

Under review as a conference paper at ICLR 2022
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Ludmila I Kuncheva and Christopher J Whitaker. Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy. Machine learning, 51(2):181-207, 2003,
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum, Human-level concept learning through probabilistic program induction. Science, 35006266) 2015.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive
uncertainty estimation using deep ensembles. In Advances in neural information processing systems, pp. 6402-6413, 2017.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, Stanford University, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322, 1998.
Zhiyun Lu, Eugene le, and Fei Sha. Uncertainty estimation with infinitesimal jackknife, its distribution and mean-field approximation. arXiv preprint arXiv:2006.0755 2020.
David JC MacKay. A practical Bayesian framework for backpropagation networks. Neural computa- tion, 4(3):448-4777 1992.
Wesley Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson. A simple baseline for Bayesian uncertainty in deep learning. In Advances in Neural Information Processing Systems, pp. 13132-13143, 2019.
Andrey Malinin and Mark Gales. Predictive uncertainty estimation via prior networks. NIPS' 18, pp. 7047-7058, Red Hook, NY, USA, 2018. Curran Associates Inc.
Prem Melville and Raymond J Mooney. Creating diversity in ensembles using artificial data. Infor- mation Fusion, 6(1):99-111, 2005.
Dragoslav S Mitrinovic and Petar M Vasic. Analytic inequalities, volume 61. Springer, 1970.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Jeremy Nixon, Michael W Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measuring calibration in deep learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, volume 2, 2019.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshninarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. arXiv preprint 1rXiv:/906.008
2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32: 8026-8037, 2019.
Tim Pearce, Felix Leibfried, and Alexandra Brintrup. Uncertainty in neural networks: Approximately Bayesian ensembling. In International conference on artificial intelligence and statisties, pp. 234-244. PMLR, 2020.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning python. the Journal of machine Learning research, 12:2825-2830. 2011.
Alexandre Rame and Matthieu Cord. Dice: Diversity in deep ensembles via conditional redundancy adversarial estimation. arXiv preprint arXiv: (00::220000000 100.05544, 2021.
12

---

Under review as a conference paper at ICLR 2022
Amal Rannen-Trik Maxim Berman, Vladimir Kolmogorov, and Matthew B Blaschko. Function norms for neural networks. In Proceedings of the IEEE International Conference on Computer Vision Workshops, 2019.
Andrew Ross, Weiwei Pan, Leo Celi, and Finale Doshi-Velez. Ensembles of locally independent prediction models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5127-5537566 2020.
Chaofeng Sha, Kegiang Wang, Xiaoling Wang, and Aoying Zhou. Ensemble pruning: A submodular function maximization perspective. In International Conference on Database Systems for Advanced Applications, pp. 1-15. Springer, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http::tttt/attttte httpp//rggbbbbba..ab/// 1556
Samarth Sinha, Homanga Bharadhwaj, Anirudh Goyal, Hugo Larochelle, Animesh Garg, and Florian Shkurti. Dibs: Diversity inducing information bottleneck in model ensembles. arXiv preprint 2xXiv:2003.04514 2020.
Leslie N Smith and Nicholay Topin. Super-convergence: Very fast training of neural networks using large learning rates. In Artificial Intelligence and Machine Learning for Multi- Mialii-Dmmann Operations Applications, volume 1 11006. pp- 1100612. International Society for Optics and Photonics, 2019.
Shengyang Sun, Guodong Zhang, Jiaxin Shi, and Roger Grosse. Functional variational Bayesian neural networks. arXiv preprint arXiv:1903.0577 2019.
Zoya Svitkina and Lisa Fleischer. Submodular approximation: Sampling bounds. SIAM Journal on Computing, 40(6): 2011.
bampling-based based algorithms and lower
Joost Van Amersfoort, Lewis Smith, Yee Whye Teh, and Yarin Gal. Uncertainty estimation using single deep deterministic neural network. International Conference on Machine Learning, pp- 9690-9700. PMLR, 2020.
Dilin Wang and Qiang Liu. Nonlinear Stein variational gradient descent for learning diversified mixture models. In International Conference on Machine Learning, pp. 6576-6585, 2019.
Ziyu Wang, Tongzheng Ren, Jun Zhu, and Bo Zhang. Function space particle optimization for Bayesian neural networks. arXiv preprint arXiv:1902.09754, 2019.
Yeming Wen, Dustin Tran, and Jimmy Ba. Batchensemble: an alternative approach to efficient ensemble and lifelong learning. arXiv preprint arXiv:2002.06715. 2020.
Florian Wenzel, Kevin Roth, Bastiaan S Veeling, Jakub Šwiqtkowski, Linh Tran, Stephan Mandt, Jasper Snoek, Tim Salimans, Rodolphe Jenatton, and Sebastian Nowozin. How good is the Bayes posterior in deep neural networks really? arXiv preprint arXiv:2002.024000 2020a.
Florian Wenzel, Jasper Snoek, Dustin Tran, and Rodolphe Jenatton. Hyperparameter ensembles for robustness and uncertainty quantification. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 6514-6527. Curran Associates, Inc., 2020b.
David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
Andrew Gordon Wilson and Pavel Izmailov. Bayesian deep learning and probabilistic perspective of generalization. arXiv preprint arXiv:2002.08791, 20200
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.007477 077477 2017.
Huanrui Yang, Jingyang Zhang, Hongliang Dong, Nathan Inkawhich, Andrew Gardner, Andrew Touchet, Wesley Wilkes, Heath Berry, and Hai Li. Dverge: diversifying vulnerabilities for enhanced robust generation of ensembles. arXiv preprint arXiv:2009.14730 2020.
13

---

Under review as a conference paper at ICLR 2022
Fisher Yu, Ari Seff, Yinda Zhang, Shuran Song, Thomas Funkhouser, and Jianxiong Xiao. Lsun: Construction of large-scale image dataset using deep learning with humans the loop. arXiv preprint arXiv:1106.033: 03365, 2015.
Sergey 7agoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
Sheheryar Zaidi, Arber Zela, Thomas Elsken, Chris Holmes, Frank Hutter, and Yee Whye Teh. Neural ensemble search for performant and calibrated predictions. arXiv preprint arXiv:2006.08573. 2020.
Mingtian Zhang, Thomas Bird, Raza Habib, Tianlin Xu, and David Barber. Variational f-divergence minimization. arXiv preprint vrxivv/907.118990 2019.
Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE transactions pattern analysis and machine intelligence, 4066):452-1144, 2017.
A PROOFS
A.1 PROOF OF THEOREM 1
To prove this proposition, we make use of the following theorem:
Theorem A1 (Theorem 1.4 from (Mitrinovic & Vasic 1970)). A function f D - R is convex on D [a, b] if and only Va < 02
< 4z
E
F1
f(1
F2
f(22)
0.
(16)
[3 [
1
Theorem 1. Any f-divergence
Dy(pllan)= = f
p(2) K2(
Σ
Km (z)dz
(17)
ΣØ=1
M
M
M7
between distribution p(z) and mixture of M kernels with equal weights is supermodualar in cardinality-fixer setting, assuming that Vz max D (p(()))lax<)) oo.
Proof. In order to prove that f-divergences are supermodular, we need show that Vo 0, x xf( is convex, because q (2) is positive modular function (Bach 2019 Proposition 6.1), due to M being fixed.
From Theorem
A1
Vx
02 < 2g in [a, f(x) is convex if an only if
I1 f(x1)
1
F22 f(x2)
2 0.
(18)
E3
f(rz)
1
know that #i S d2 S 3z
and æ a > 0. We divide each 7th row by ne
1
1 f(1))
21
f(22)
1
0.
(19)
T
23 f(2))
z3
After the division, denote new variables #1 y1 U2 < ya, because in 22 Øg. We then get
1.
y2
and y3
One can that
us
02
22
14

---

Under review as a conference paper at ICLR 2022
y33
1
y/
2
0.
(20)
1
y1
Changing the first and the third row of the determinant will change the sign. Changing the third and the first columns will also change the sign. Therefore
1/1
1
V1
1/2
1
2
0,
(21)
ya
1
and thus we get that
1
Vx E la, b), zf
is convex
f(x) is convex.
(22)
Consider mapping y. which preserves convexity:
ayy
a _
orj2
2 0.
(23)
ayy
agaf
Division of the first and the second column by does not change the sign of the determinant, therefore
f(x) convex,
(24)
which concludes the proof.
A.2 PROOF OF PROPOSITION
Proposition 1. Consider C max (plllam, where Dy(pllgm)) is an arbitrary f-divergence be- tween some distribution p(z) and mixture of kernels qu = M En Kz(2), and D (y(pllas)) < co. Then, maximization of a marginal gain for set function
F(Z) = =(Z)=-
-
p(z)
Σ (z)d2 m=
M
(25)
TI I K,(z)
M
at step k of a greedy algorithm corresponds to
p(2) K2(2)
arg max A Z)
arg min E Ke() 26
(26)
M K]
2k
Proof. We aim derive marginal gain of adding an element defined by 24 Σイ K2
Let us denote G(z) = f Ej ky(e))
Mp(=)
Et K,(x)
Mp(=)
Then
-fs
Mp(z) 1
Σ
Km(z)dz C+ /
Mp(z)
1
Σ Km
-C=
Σラ Kz(2)
M m=1
E K,(:))
M
m=1
1
G(z)
1-1
Km(2)dz - -f
Mp(z) E K2(2)
Kx(2) dz.
(27)
M
M
m=1
Note: is a constant, which remains unchanged all iterations of the greedy algorithm.
15

---

Under review as a conference paper at ICLR 2022
One observe that the first term of (27 is upper-bounded by constant, which is not dependent Zg²
[CL M
Σ Km)zz)d S zʃ E
kp(z) K2(z)
1
Σ
K5(z)dz const,
(28)
M
therefore, to maximize the marginal gain, one needs maximize the second term. Consequently, write the objective corresponding to a marginal gain as
A zx) = f
p(2) =1 Kz(2)
K& (x)adz,
(29)
1 M
maximization of which is equivalent to
p(2)
arg min E (ew))(s)
(30)
M EØ=1 K2(2)
1
which concludes the proof.
B IMPLEMENTATION DETAILS
B. PRACTICAL IMPLEMENTATION OF THE ALGORITHM
Weighting distribution for the diversity term We propose the following simple heuristic, defining p" (x) as normal distribution N (HD, a Ep) of dimensionality, corresponding to the training data. The covariance 2p for this distribution is set to diagonal, such that the variance for every dimension j is Ed[j.j] (a o,)² where
is scaling parameter, and of is variance of the dimension j computed from samples of the training dataset D. Similarly, Ppp the vector expected values for was found to work well, and we thus report all the experimental results with fixed. We note that a similar technique, but for in-distribution data generation has been used earlier in (Melvilee & Mooney 2005).
every dimension, is also computed from the training data. Finally, the hyperparameter
The resulting algorithm The resulting, computationally tractable optimization algorithm for en- sembles, which minimizes marginal gains (10). is shown in Algorithm B2 For simplicity, omit the snapshot selection step, i.e. early stopping.
We note that contrary to the general Random Greedy method, shown in the main text, can resort to a method with complexity of O(k). This achieved through the fact that uniform selection of the elements maximizing the marginal gain be avoided, since at each greedy step, initialize the new models randomly before maximizing the marginal gain. Another performance improvement can be gained by storing the evaluations (x,) Vj I....,k in memory before executing each hth step.
We report here also one important practical trick, which we found important during the training. Specifically, freezing the batch normalization layers (Totte & Szegedy (015)) before computing the diversity term turned out to help the convergence substantially. We anticipate that the diversity term simple multivariate Gaussian with diagonal covariance may
weighting distribution approximated be corrupting the batch norm statistics. We thus think that using other, more sophisticated techniques for generating the weighting distribution samples might provide better results.
B.2 OOD DETECTION BENCHMARKS
MNIST The MNIST dataset benchmark included 6 datasets: Fashion MNIST Xiao al. (2017). DTD Cimpoi et al. (2014), Omniglot Lake et al. (003)), Gaussian noise, Bernoulli noise, and uniform noise datasets (see Table BI) We re-scaled all the images the range of [0, 1). Subsequently, applied the same mean and standard deviation as we have applied to the original images before feeding them to the network.
16

---

Under review as a conference paper at ICLR 2022
Algorithm B2 (k) Random Greedy algorithm for training ensembles of neural networks.
1: Input: D {a Vi )=) Dataset
2: Input: M Size of the ensemble
3: Input: N Number itcrations
4: Input: Variance parameter for (x)
5: Input: Ng- Mini-batch size
6: Z < 0
7: D < {(,;y] b ~ (ipD, Ep)
8: while |2| < M do
9: A: |
10: Randomly initialize zay:
for 1o N do
12:
D. + {(Ib. yo) ) ~ D;
13:
Dj + {zg]b= D"
14:
+ ((,,))), {=0,, (2), 0) + 1110
15:
16:
if > 1 then
17:
for j = 1 to h do
18:
di RD =0 (x*) 20, (x* 112
19:
end for
20:
Ω log Dm=1 exp( Ay d...)
21:
end if
Update 0 using V (L+ end for
23:
< Z 7
25:
end while
26:
return
The CIFAR and SVHN OOD benchmark included 10 different datasets. Here, we also DTD. Bernoulli noise, Gaussian noise and uniform noise datasets, and added Places 365 (Zhou et al.
CTFAR and SVHN
datasets 2017), Tiny ImageNet (Le & Yang 2015 Deng et al. 2009), and LSUN Yu et al. 2015) benchmark. For CIFARIO as in in-aimiin data, we added CIFAR100 and SVHN Netzer et al. 2011) to the benchmark. For CIFAR100 CIFAR10 10 and SVHN. Finally, for SVHN, we added CIFARTO and CIFAR 100 as OOD datasets, making total of 10 OOD datasets per in-distribution dataset. The details about each of the datasets are shown in Table B1
Before feeding the images to the network, we applied re-scaling similarly to the MNIST setting. We also used the same mean and standard deviation normalization procedure, as for the in-domain data.
Table B1: Description of the datasets used in all the exp. R indicates real images, S synthetic.
Dataset
Type # samples
Comment
Uniform
25. 000
N/A
Gaussian
25. 000)
Generated once, used in all experiments
Blobs
S
25. 0000
N/A
Bernoulli
25. 000
N/A
Omniglot
13. 181
Evaluation images
CIFARIO
10. 000
Test set (not
training)
CIFAR100
10. 000
Test set (not used training)
SVHN
73, 257
Test set (not used training)
Places 365
10. 000
First 10, 000 images from test set (sorted alphahetically)
R
TinyImageNet
10. 000
Original validation set images
DTD
5, 640
Release 1.0.1
LSUN
10. 000
Test set
Fashion MNIST
10. 000
Test set
17

---

Under review as a conference paper at ICLR 2022
B.3 EPISTEMIC UNCERTAINTY COMPUTATION
We used the epistemic uncertainly, i.e. mutual information (Ml) between the distribution of pre- dicted label for the point & and the posterior distribution over functions p p([(), evaluate the uncertainty (Malinin & Gales 2018; Depeweg et al. 2018). As distribution over weights induces a distribution over functions, we approximate the MI as:
I(ú: f|& D) H [Bx(0)) D)] D) H [p((p 0,)
(31)
where H[|] denotes the entropy. One can see that this metric can be efficiently computed from the predictions of an ensemble.
C EXPERIMENTS
C.I EXPERIMENTAL DETAILS
Model selection Contrary to the commonly used practice, we did not use CIFAR10/100 and SVHN test set sets for model selection. Neither did any OOD data. Instead, used validation set accuracy (10% of the training data; randomly chosen stratified split) to select the models when optimizing the marginal gain. The best snapshot found using the validation data, was then selected for final testing. When selecting the models for evaluation on OOD data, we first evaluated ensembles on the in-distribution test set (Appendix C.2). Subsequently, we selected the highest Am that did not harm the test set (in-domain) performance (no overlap of confidence intervals defined as mean standard error). To provide additional information, we also analyzed adaptive calibration error (ACE) with 30 bins NNxon al. 2019).
Two moons dataset For the synthetic data experiments, we used scikit-learn (Pedregosa et al. 201T), and generated two-moons dataset with 300 points in total, having the noise parameter fixed to 0.3. Here, we used a two-layer neural network with ReLU (Krizhevsky 2009) activations and hidden layer size 128.
CIFAR10/100 and SVHN The main training hyper-parameters were adapted from (Maddox et al., 2019) (see Table C2). but with additional modifications inspired by (Malinin & Gales) 2018 Smith & Topin 2019). which helped train the CIFAR models to state-of-the. art performance in only 100 epochs. As such, we first employed a warm-up of the learning rate (LR) from a value 10 times lower than the initial LR. (Lai in Table C2) for epochs. Subsequently, after 50% of the training budget, we linearly annealed the LR to the value of LR x lr scate until 90% the training budget is reached, after which we kept the value of LR constant.
All models were trained using stochastic gradient descent with momentum of 0.9 and a total batch size of 128. We employed standard training augmentations horizontal flipping. reflective padding to 34 x 34, and random crop to 34 x 34 pixels.
Model
LR
Nesterov
Weight Decay
tracute
Table C2: Main hyper-
parameters all the mod-
Pre6esNet164
0.1
Yes
0.0001
0.01
els used in the CIFAR and SVHN in-domain experi- ments.
VGGI6BN
0.05
No
0.0005
0.01
11deResNet2&x10
0.1
No
0.0005
0.001
MNIST addition to the CIFAR10/100 experiments, we also trained our method on MNIST (L Cun et al. 1998) with PreResNet8 architecture. As OOD, used FashionMNIST (Xiao al. 2017) and Omniglot (Lake et al. 2015) datasets. We also tested other architectures, such as Net2osNet20, but the models with higher depth than 8 already gave nearly perfect scores MNIST.
Hyper-parameter wise, we trained all the models for 20 epochs without warmup with the batch size of 256 using plain SGD with momentum. The weight decay was set 1e - 5. We used LR annealing similarly as for CIFAR experiments, but used Ir Ir = 0.0001. No data augmentations were used in any of the MNIST experiments. Xa was searched in range {0.0001, 0.001, 0.01, 0.11, 7} for
18

---

Under review as a conference paper at ICLR 2022
97.0
1.0
0.8
Aecurney
ACE (10)
0.6
0.4
94.0
VGS1
02
93.5
93.0
255
5.0
5.0 Au
7.5
0.0
2.5
100
0.0
0.0
2.5
7.5
10.0
(a)
(b)
(c)
(d)
Figure C1: Relationship between accuracy, ACE, and AM (M 11). Subplots (a) and (b) show the results for CIFARIO. Subplots (c) and (d) show the results for CIFARI00.
M E 13,5, 5, 9, 15). This series experiments was re-run times, the MNIST dataset is rather simple, and the test scores have low variance between the runs.
C.2 CIFARIO/100 AND SVHN IN-DOMAIN PERFORMANCE
CIFARI0/100 in-distribution performance vs. diversity. Figure CI provides an illustration of how the test set performance changes with AM CIFAR data. One can general trend that when AM approaches M, the models lose the ability to make accurate predictions, which results in lower accuracy and poorer calibration. Interestingly, performance the VGG model degrades much slower with AM compared to other architectures. Similar findings were also obtained for the SVHN dataset. Based the test performance, we selected the models for further evaluation OOD benchmark.
shows the results of all the trained that the results between Deep Ensembles (DE) (Lakshmi) narayanan et al., 2017) do not differ significantly. We trained all these models according to the earlier specified sypee-pprammters and the learning rate schedule. Models selected in Table C3 are used to report the results in the main experiments.
CIFAR and SVHN: best models' performance Table C3
models on the in- nn-oomain data. One
C.3 DETAILED CIFAR, SVHN RESULTS
Detalized versions of the results presented the main text are shown Table C4 AM coefficients are the same as in Table C3
The corresponding
C.3.1 MNIST DETAILED RESULTS
In-domain performance Model selection scheme on MNIST was exactly the same as for the CIFARIO/10N We illustrate the relationship between AM accuracy, and the Adaptive Calibration eтror (ACE) in Figure C2 One can see that AM remains the same even when M is increasing. Table C7 shows detailed in-domain performance for the best AM, equal to 0.1.
100.00
30
05
Figure C2: Relationship be- tween accuracy, negative log- likelihood, ACE, and A' for different M on MNIST (Le Cun al. 1998). Subplots (a) and (b) show the results for PreResNet8. Experiments were re-run times with differ- ent seeds. found that best results were obtained with AM = 0.1.
94.55
25
0.4
20
99.5
0.3
20.00
25.75
3850
40.00
05
(a)
(b)
(c)
19

---

Under review as a conference paper at ICLR 2022
Table C3: In-domain performance on the test sets of CIFARI0/100 and SVHN for all the models used in the experiments (M = 11). We report mean and standard error over 5 random seeds for each of the models. Aas indicates Deep Ensembles (Lakshminarayanan et al. (017). Standard errors are reported if they are more than 0.01 across runs. DE indicates Deep Ensembles.
Architecture
Dataset
Method
Accuracy (%)
NLL x 100
ACE (%)
DE
95.70
13.28 10.08
0.18
C10
Ours (AM 3)
95.66
13. 13.1820.09
0.16
Prt
DE
49.97
73.44 73.4440.17
0.08
C100
Ours (AM 5)
79.93
74.1640.91
0.09
DE
99.46 49.464
2.3440.04
0.25
SVHN
Ours (AM 1)
99.38
3.1620.13
0.81
DE
94.55 1..5..0.0
17.59
0.23
C10
Ours (AM 5)
94.4840
17.81
0.23
VGGI6BN
DE
76.32
91.07
0.11
C100
Ours (AM 5)
76.78
89.10.0.33
0.10
DE
99.40
2.71
0.18
SVHN
Ours (AM 1)
99.25 10.01
3.94
0.95
DE
96.5640.02
10.7620.06
0.1620.01
C10
Ours (AM 1)
96.54
10.99
0.18
1e
DE
83.08 +0.09
62.05
0.09
C100
Ours (AM
83. 03.022...00
62.20
0.08
DE
99.45
2.53 03
0.43
SVHN
Ours (AM
99.38
2.87
0.46
Out of distribution detection The final OOD benchmark results on MNIST are summarized in Table C8 One can see that on MNIST, our method yields performance boost for any size of an ensemble, even for the very small ones (M = 3).
C.4 ADDITIONAL RESULTS
Does the choice weighting distribution for the diversity term affect the results? We considered PreResNet164 64 trained on CIFAR with CIFARIO weighting distribution dataset. This approach can be seen as a form of outlier exposure technique, earlier proposed by Hendryeks et al. (2018). The results on OOD benchmark (excluding CIFAR 10) are shown in Table C9 One can observe that relationship between changing to dataset of real images and the OOD detection performance is non non-trivial. While for some datasets outlier exposure did bring benefit, for some other datasets, did not. Notably, the datasets which the benefit of outlier exposure the best were datasets of real images, and we think that in case unlabeled images with non-overlapping class distribution are available, using them can bring benefit.
Effect of model capacity While the main experiments in the paper were conducted using large models, we also investigated whether ensembles of smaller models can benefit from our method. We followed the same Am selection procedure as for the main experiments in the paper, and report results for PreResNet20 in Table CTO for an ensemble size M = 11. We found that the optimal Aus in this case is smaller compared to AMs for 1reResNet164, and our method here does not yield any substantial boost over Deep Ensembles on these data. We found that all the models with small capacity trained CIFAR diverged with high Am
Robustness to distribution shift As additional evaluation, investigated whether our method performs on par with DE under the distribution shift, to make sure that introduction of additional regularization did not affeet the robustness properties. We thus use corrupted version of CIFARI0 test set released by (Hendrycks & Dietterich, 2201), (2009), and has been recently shown that DE outperform many other methods on this benchmark (Ovadia al., 2019). Here, report the results for
20

---

Under review as a conference paper at ICLR 2022
Table C4: CIFARIO results, We report mean and standard error over random seeds for each of the models. Standard errors are reported if they are more than 0.01 across runs. DE indicates Deep Ensembles.
DE
Ours
Architecture
OOD dataset
AUC
AP
FPR95 (L)
AUC (1)
AP (1)
FPR95
hernoulli
1..01
1..01
0.00
1.00
1.00
0.00
blobs
0.96
0.98
0.12
0.96
0.98
0.12
cifar100
0.90
0.30
0.90
0.88
0.30
dtd
0.93
0.19
gaussian
0.93=a.01
0.94
0.16+0..01
0.96:40.02
0.97=0.022
0.11==0.0x 0..8
PreResNet164
Isun
0.93
0.89
0.20
0.95
0.94
0.18
places
0.92
0.89
0.21
0.94
0.93
0.19
svhn
0.94
0.99
0.16
0.95
0.99
0.14
tiny imagenet
0.91
0.88
0.28
0.92
0.89
0.26
uniform
0.98
1.00
1.04
1.00
1.00
0.00
bernoulli
0.
0.95
0.11
1.00
1.00
0.00
blobs
0.96
0.98
0.16
0.96
0.98
0.15
cifar100
0.89
0.86
0.34
0.89
0.86
0.34
dtd
0.90
0.77
0.25
0.96
0.92
0.18
gaussian
0.95
0.97
0.14+0.01
0.99
0.99
0.05
VGGI6BN
0.93
0.21
places
0.91
0.27++0.01
0.94
svhn
0.87
0.97
0.281
0.87
0.97
0.27
tiny imagenet
0.90
0.88
0.33
0.90
0.88
0.32
uniform
0.90 02
0.89
0.16
1.00
1.00
0.00
hernoulli
1.00
1.00
0.00
1.00
1.00
0.00
blohs
0.96
0.97
0.11
0.97
0.98
0.10
c0far100
0.92
0.27
0.91
0.89
0.27
dtd
0.93
0.861..01
0.22:10.01
0.97
0.94
0.14
WideResNet28x10
gaussian
0.9610.01
0.97
10.00
1.00
1.00
0.00
Isun
0.93
0.95
0.95
0.17=0.01
places
0.93
0.21
0.95
0.94
0.18
svhn
0.96
0.95
0.99
0.13=n.01
tiny imagenct
0.92
0.90
0.27
0.93
0.91
0.25
uniform
1.00
1.00
0.00
1.00
1.00
0.00
VGG16BN and PreResNet164, they yielded OOD performance gain in both SVHN and LSUN datasets. One can see from Figure C3 that our method performs on-par with DE, statistical significance in difference between methods can be concluded from this plot. This further supports our claims that the developed greedy ensemble training approach works the same on par with DE.
Effeet of ensemble size on CIFAR We ran our experiments using PreResNetl64 with on Cl- FARTON 1O/10/ having M (3, 7} and Amr (0.1, 0.5, 0.8. 1, 1.5. 3). Both in-domain accuracy, and the OOD detection on LSUN and SVHN are shown in Table CTT The results that table show that with small ensemble size, our method may yield better performance than DE on SVHN, abut even with an ensemble of size M = 3, it has substantial boost over DE in detecting LSUN.
Qualitative results on CIFAR100. In Figure C4 we further illustrate capabilities uncertainty estimation of our method for the PreResNet trained CIFAR 100 (M 11). Our method has better true positive rate (as can also be seen from the histograms). and slightly better precision when the threshold for the recall is high. We note that the histograms of epistemic uncertainties still overlap significantly. however, with our method, the model does not have a high number of overconfident predictions coming from the OOD data anymore.
21

---

Under review as a conference paper at ICLR 2022
Table C5: CIFARI00 results. We report mean and standard error over random seeds for each of the models. Standard errors are reported if they more than 0.01 across runs. DE indicates Deep Ensembles.
DE
Ours
Architecture
OOD dataset
AUC (1)
AP
FPR95 ())
AUC (t)
AP (1)
FPR95
bernoulli
0.81 0.81 +0.03
0.82
0.24
1.00
1.00
0.00
blobs
0.92
0.95
g.25
0.92
0.95
0.23
cifarl0
0.80
0.76
0.7816.01
0.75
0.67
0.76=0.01
0.61+
0.64=0.01
0.80=0.01
0.75=0.01
0.78+0.05
gaussian
0.8010001
0.8310.01
1..02
0.95.1002
0.97
0.16.0.00
PreResNet164
Isun
0.86
0.81
0.45
0.87
0.85
0.47:2001
places
0.82
0.77
0.52
0.83
0.81
0.60
svhn
0.80
0.96
0.55
0.83 01
0.96
0.50
tiny imagenet
0,82
0.79
0.53
0.82
0.79
0.58+0.01
uniform 0.51
0.66
0.55
1.00
1.00
0.00
bernoulli
0.87
0.88+0.02
0.24
1.00
1.00
0.00
blobs
0.95
0.97
0.16.0001
0.97
0.98
0.1210.02
cifar10
0.78
0.73
0.63
0.78
0.74
0.64:0.01
dtd
0.73
0.53
0.62+0.01
0.86
0.80
0.50
gaussian
0..020.02
1.9010.01
0.35
0.9510.01
0.97
0.15
VGGI6BN
Isun
0.85
0.82
U.47
0.90
0.89
0.40
places
0.82
0.78
0.55
0.86
0.85
0.51
svhn
0.76
0.95
0.67
0.76
0.95
0.72
tiny imagenet
0.81
0.78
U.56
0.79
0.55
uniform
0.86.0.02
0.89
0.28
1.00
1.00
0.00
bernoulli
1.9720.02
0.9610.02
0.04
1.00
1.00
0.00
blohs
0.95
0.97
0.1640.01
0.98
0.99
0.09
cifar10
0,80
0.74
0.53
0.81
0.76
0.5410.01
0.8420.01
0.75+0.01
0.54
0.88 01
0.84:.0.1
0.49
gaussian
0.72+a.0s
0.78
0.39
9.440..0
0.97
0.20
1ideResNec28x10
Isun
0.87
0.81 10.01
0.35
0.91
0.90
0.
places
0.84
0.7940.01
0.44g0.01
0.88
0.87
0.41:0.01
svhn
0.80
0.95
0.52
0.80
0.95
0.52
tiny imagenet
0.84
0.78
0.46
0.85
0.81
0.46
uniform 0.95
0.96
0.12
1.00
1.00
0.00
80
60
40-
despent
20
severty
severty
(b)
80-
seuerty
severit
(d)
Figure C3: CIFARIO Robustness benchmark results (M = 11) Henddrycks & Dietterich 2019). Subplots (a) and (b) show the results for PreResNet164 trained with X 3. Subplots (c) and show the results for VGG16BN trained with Aa = 5. The results have been averaged over 5 seeds.
22

---

Under review as a conference paper at ICLR 2022
Table C6: SVHN results (averaged across 5 seeds)
DE
Ours
Architecture
OOD dataset
AUC (1)
(t)
FPR95 ())
AUC (1)
AP (1)
FPR95 ())
bernoulli
1.00
0.99
0.01
1.00
1.00
0.00
blobs
1.00
0.99
0.01
0.99
0.98
0.02
cifar10
0.99
0.97
0.02
0.99
0.97
0.02
cifar100
0.99
0.96
0.02
0.99
0.96
0.04
dtd
0.99
0.94
0.02
1.00
0.98
0.01
PreResNet164
gaussian
1.00
0.99
0.01
1.00
1.00
0.00
Isun
0.99
0.96
0.02
1.00
0.98
places
0.99
0.96
0.02
1.00
0.98
tiny imagenet
0.99
0.96
0.02
1.00
0.97
0.02
uniform
1.00
0.99
0.01
1.00
1.00
0.00
bernoulli
1.00
0.99
0.01
1.00
0.00
blobs
1.00
0.98
0.01
1.00
0.01
c0far10
0.99
0.95
0.02
0.99
0.96
0.03
cifar100
0.99
0.94
0.02
0.99
0.95
0.05
dtd
0.99
0.93
0.02
1.00
0.97
0.01
VGG16BN
gaussian
1.00
0.99
0.01
1.00
1.00
0.00
Isun
0.99
0.95
0.02
1.00
0.99
0.01
places
0.99
0.96
0.02
1.00
0.98
0.01
tiny imagenet
0.99
0.95
0.02
0.99
0.97
0.03
uniform
1.00
0.99
0.01
1.00
1.00
0.00
bernoulli
1.00
0.99
0.022=0.01
1.00
1.0U
0.00
blobs
0.99
0.98
0.02
1.00
0.99
0.01
c0
0.99
0.96
0.02
1.00
0.97
0.02
cifar100
0.99
0.95
0.03
0.99
0.97
0.02
dtd
0.99
0.91
0.04
1.00
0.99
0.00
WideResNer28x
gaussian
1.00
0.98
0.02
1.00
1.00
0.00
Isun
0.99
0.95
0.03
1.00
0.99
0.00
places
0.99
0.95
0.03
1.00
0.99
0.00
tiny imagenet
0.99
0.96
0.02
1.00
0.98
0.01
uniform
0.99
0.98 20.01
0.03
1.00
1.00
0.00
Method
Accuracy (%)
NLL x100
ECE (%)
Table C7: Test set results (in-domain perfor-
mance) of our method on PreResNet8 trained
DE
99. 00.40
1.72a.03
0.23
3
Ours
49.43.00s
1.74
0.24
MNIST with different ensemble sizes M. We report the means over 3 random seeds for each of the models. AM 0.1 Was used for
DE
99.43
1.65
0.22
5
Ours
99. 4620.01
1.72
0.32
DR
99 44
1.61 40.0
0.25
all the experiments when training our method.
Ours
99. 4lo0
1 1.60
0.25
Standard emrors are reported if they more than 0.01 across runs. DE indicates Deep En- sembles.
DE
99. 00.44
1 0..5
0,28
9
Ours
09.47.0.01
1. 1.624a.0a
0.31
DE
99.47
1.60
0.29
Ours
99.49
1.57 40.0a
0.30
23

---

Under review as a conference paper at ICLR 2022
Table C8:
detection results of our method with PreResNet8 trained on MNIST with different ensemble sizes M. We report the means over 3 random seeds for each of the models. Am 0.1 Was used for all the experiments when training our method. Standard errors are reported they are more than 0.01 across runs. DE indicates Deep Ensembles.
DE
Ours
Size OOD dataset
AUC (?)
AP (f)
FPR95 (J)
AUC (1)
AP (f)
FPR95 (.)
hernuull
0.09
0.5210.01
0.98
1.00
1.00
0.00
did
0.41 20.16
0.47
0.97
1.00
0.99
0.00
fashion mnist
a0.0s
0.92
0.71
0.99
0.99
0.07
3
gaussian
a.98
0.99
(..6
0.99
1.00
0.03
omniglot
0.98
0.98
0.08
0.98
0.98
0.08
uniform
0.23
0.58
0.90
1.00
1.00
0.00
bernoulli
0.02
0.50
0.98
1.00
1.00
0.00
did
0.48
0,55
0.94=0.0a
1.00
1.00
0.00
5 fashion mnist
0.805
0,92+0.03
0.67=2.21
0.99
0.99
0.04
guussian
1.00
1.00
0.02.
1.00
1.00
0.01
omniglot
0.98
0.99
0.06
0.98
0.99
0.07
uniform
0.30
0.62
0.77
1.00
1.00
0.00
bernoulli
2.33
0,66 1.66
0. 0.77
1.00
1.00
0.00
0.75
0.76+0.11
0.67
1.00
1.00
0.00
fashion mnist
0.95
0.97
2.29
0.05
7
guussian
1.00
1.00
0.02
1,00
1.00
0.02
omniglot
0.99
0,99
0.06
0.99
0.99
0.06
uniform
0.49
0.7
0.64
1.00
1.00
0.00
hernoulli
0.45
0.70
0.90
1.00
1.00
0.00
dtd
0.83
0.83.20.06
0.68
1,00
0.00
9 fashion mnist
0.97 1..0
0.97
0.16
1.00
1.00
0.01
gaussian
1.00
1.00
10.01
1.00
1.00
0.00
omniglot
0.99
0.99
0.06
0.99
0.99
0.06
uniform
0.72gm.35
0.82gu.09
0.50
0.00
bernoulli
a.18
0.55
0.99
0.00
dud
0.82+a.04
0.80
0.84=0.00
1.00
1,00
0.00
fashion mnist
0.97
0.97
0.17
1.00
1.00
0.01
guussian
1.00
1.00
0.01 20.01
1.00
1.00
0.01
omniglot
0.99
0.05
0.99
0.05
uniform
0.70
0.80
0.53
1.00
1.00
0.00
Table C9: Outlier exposure results for PreResNet164 trained CIFAR100 with CIFARIO weighting distribution for the diversity term. We found Am = 1 to be the best one for this experiment in the outlier exposure. The most optimal setting for our model was Am and AM
respectively.
DE
Ours
Ours w. Outlier Exposure
OOD dataset
AUC (1)
AP (t)
FPR95 ())
AUC (1)
(?)
FPR95 (L)
AUC (f)
AP (t)
FPR95 (1)
bernoulli
0.81 20.00
0.82_0.05
0.244004
1.00
1.00
0.00
1.00
1.00
0.00
blobs
0.92+a.01
0.95
0.25 02
0.95 0.92-a.02
0.23
0.96 01
0.98
0.14
dtd
0.76
0.61
0.644001
0.80
0. 0.75 01
0.78
0.81
0.71
0.57
gaussion
0.80g0.01
0.83=0,01
0.37 0.37+0.02
0. 0.95+0.02
0.97 17:0000
0.16==0.0
0.91==0.01
0.96g0.01
0. 1.1990..0
Isun
0.86
0.81
0.45
0.37
0.85
0.47 00.7
0.89
0.88_0.01
0.40
places
0.82
0.77
0.52
0.83
0.81
0.60 0.60
0.86
0.84 0.84_o.m
0.19 19.1
svhn
0.80
0.96
0.55440.1
0.83
0.96
0.50=o.01
0.78
0.96
0.56
tiny imagenet
0.82
0.79
0.53
0.82
0.79
0.58 0.58
0.83
0.79
0.52
uniform
0.5l
0.60=a0.05
0.53
1.00
1.00
0.00
0.98
0.98-20.02
0.05
24

---

Under review as a conference paper at ICLR 2022
Table C10: Out of distribution detection for small-capacity model PreResNer20 (M = 11).
Results were averaged over random seeds. Standard errors are not reported they less than 0.01
across runs. DE indicates Deep Ensembles.
DE
Ours
Dataset
OOD dataset
AUC (1)
AP (1)
FPR95 (1)
AUC
AP (t)
FPR95 ())
berouuli
2.90
2.00
0.05
1.00
1.00
0.00
blobs
0.12.0.61
cifar100
0.88
0. 16
0.37
0.89
0.86
0.36
did
0.93
0.86g.0.1
0.22
0.94
0.89 1.00 01
0.20
C10
goussian
0.94
O. 20.66.0.01
18
0.95
0.97
0.15
Isun
0.93
1..92
0, 0,25
0.91
0.93
0 23:00.02
places
0.92
0.26
svhn
0.91
0.98
0.23
0.91
0.98
0.23
tiny imagenet
uniform
0.99
0.90
0.03 on
1.00
1.00
0.00
berouulli
0.91
g..3
0.19
1.00
1.00
0.00
blobs
0.95
0.97
0.17
0.97
0.98
0.12
cifar10
0.78
0.73
0.63
0.77
0.72
0.63
did
0.81
0.72
0.66 na
0.83
0.77
0.63
C100
gaussian
0.98
0.90
0.07
0.90
0.90
0.04.10.0
Isun
0.88
0.87
0 0.43
0.89
0.88
0.41
places
0.55
0.52
svhn
0.85
0.97
0..8
0.84...01
0.97
0.49
tiyy imagenct
0.82
0.78
0.82
0.79
0.54
uniform
0.90
0.92
0.23
1.00
1.00
0.00
Table C11: Test set and OOD detection performances on PreResNet164 for ensemble sizes M E {3. 5, 7). We report the means over different seeds. Standard errors reported if they non-zero across the runs.
SVHN
LSUN
M
Dataset
Method
Accuracy (%)
NLL x100
ACE (%)
AUC (t)
AP (?)
AUC (1)
AP (1)
DE
95.38
15.3910.14
0.25
0.93
0.95
0.92
0.87
C10
Ours
95. 05.32.1.04
15.67
0.24
0.94_o.01
0.96
0.94
0.91:0001
3
DR
78. 78.67
84.35+0.18
0.10
0.78_a.02
0.87=a.m
0.82
0.76
C1000
Ours
78.51
84.35
0.10
0.76
0.86
0.82
0.7620.02
DE
95.55
14.1410.14
0.20.o.01
0.93
0.96
0.92
0.88
C10
Ours
95.5 95.58
14.31 10.07
0.19
0.94
0.96
0.95
0.93
DE
79.50.ao.m
78.85
0.09
0.78_a.01
0.87 0.88
0.84
0.79
C100
Ours
79.33 1: 0.13
78.59+0.80
0.09
0.80
0.86
0,82=2.01
DE
95. 64.6440.004
13.7944..06
0.19
0.94
0.96
0.92
0.88
C10
Ours
95.6 95.6240.04
14.07
0.22
0.94
0.96
0.94
0.93
DE
79. 11 10.06
76.1210.22
0.08
0.78
0.78_o.01
0.87
0.85
0.79
C100
Ours
79.7644..0
78.0941.41
0.1
0.78-
0.88
0.86
0.83
25

---

Under review as a conference paper at ICLR 2022
3000
3000
1,0
1.0
ISUN
2500
CIFAR100
2500
CIFAR1DO
0.8
2000
0.6
0.8
550
1500
0.6
Am
500
500
- 0
0
0.0
0.5
1.0
0.0
0.5 Recall
Epistemic
Epistemic
(b)
(c)
(d)
3000
3000
SVHN
SVHIN
CIFAR100
CIFAR100
2000
2000
Count
0.5
1500
1000
1900
0.2
5
0.2
5
0.5
Ap
-
0.0
A= 0
0.50
0.75
1.00
0.50
Epistemic unc.
uri
PPR
Recall
(c)
(f)
(h)
Figure C4: Uncertainty estimation quality on PreResNet164 (He al., 2016 trained on CIFAR100
and evaluated on CIFAR100 test set vs LSUN and SVHN, respectively. Histograms (a) and (e) indicate Deep Ensembles (Lakshminarayanan et al. 2017). Histograms (b) and (f) show our method trained with AM 5. Subplots (c) and (d) show the ROC and PR curves for the LSUN dataset, respectively. Subplots (g) and (h) show the ROC and PR curves for the SVHN dataset, respectively The curves were computed using average epistemic uncertainty per sample (5 seeds). Standard errors were < 0.01.
26


Reviews:
[{"review_id": "OWGpBqiIqp0", "reviewer": "Reviewer_dcPg", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "PROS\n\n1. The approach targets diversity, a relevant and interesting phenomena, and gives a technically non-trivial algorithm for controlling it. Especially, I like the connection to the empirical risk in Eq. (1) and the flexibility of the method (it works for any f-divergence). To me it seems the authors expertize in combinatorial optimization.\n\n2. The results seem convincing that the proposed method can outperform standard deep ensembles in OOD tasks. Moreover, Figure 3 is a nice representation of the OOD detection results.\n\n3. The Related Work section and the literature study in the introduction are dense. The authors have clearly spent time probing the field. These sections are nice to read and are useful for navigating in this evolving domain (although I miss one reference, see 2. below).\n\n\nCONS\n\n1. My main concern is regarding accessibility and clarity of how the method is described. As this is posed as a competing method/framework to standard deep ensembles, the paper should be accessible to practitioners and researchers with a broad technical background. As such, the concepts submodularity, supermodularity and modularity, as well as their definitions in the paper, need to be contextualized.\n\nFor instance, I have been working a lot with deep ensembles and Bayesian deep learning, and am interested in the method proposed in the paper, but I have a hard time understanding the motivation of using the modularities? I see that they help devise the method theoretically, but what are f, V, B and A in Definition 1? As an example of contextualization, simply state what f is in this setting. All I understand about f right now is that it is a mapping from a binary input of dimension V to the real line. Also, is f in Def. 1 the same f as in f-divergence? If not, please consider distinguishing them.\n\nIn my opinion, the delivery of the method in, especially, sections 2.2 and 3.1 is not easy to follow. These two sections essentially contain enumerations of definitions and I have a hard time finding motivations for them. As far as I am aware, you do not reference the definitions or the theorem in the text.\n\n2. Although the sections Related Work and Introduction are thorough, I think [1] should be included. In [1] they correlate the ensemble components by letting them share weights. Your objective function also correlates the ensemble components. In fact, I think the results in the paper would benefit a lot from comparing with [1] *and*, e.g., [2]. [2] since, as is pointed out in Sec 5, it is \"closely connected\". Not comparing with POVI methods overall is not well motivated, in my opinion.\n\n3. How did you obtain Figure 1? It is not obvious to me that (a) and (b) would occur. It seems speculative and unmotivated as is (this alone makes my \"Correctness\" score = 3).\n\n4. The paper has an OK structure in the majority of the sections (especially Sec. 1, 5, 6 and 7) and the language is generally good. However, there are many disturbing typos which could easily have been caught by reading through the paper.\n\n[1] \"Training independent subnetworks for robust prediction\", Havasi et al., ICLR 2021\n[2] \"Repulsive deep ensembles are bayesian.\", Francesco D’Angelo and Vincent Fortuin. NeurIPS 2021", "summary_of_the_paper": "The paper presents a combinatorial approach to controlling and improving the effects of diversity; a relevant and interesting feature in Bayesian networks. The approach is general in the sense that it involves minimization of an f-divergence, for any f. The approach is mainly compared to standard deep ensembles, i.e. without controlling diversity. Additionally, the paper provides a theoretical result with approximation guarantees, which might be useful outside this specific application.", "summary_of_the_review": "I am certain that the proposed method can indeed be useful and of interest for many in the field, and the method appears to be largely novel. However, I am concerned that it will not be very impactful, the way it is delivered now. To be clear, I don't believe that the mathematical approach is necessarily complicated. However, the provided explanations are over-complicated, and the approach is insufficiently motivated/contextualized.\n\nTo address this concern, I suggest that, for instance, redundant definitions (as Def. 4?) are moved to the Appendix (if at all needed). Instead, there should be some paragraphs in Section 2 that puts concepts like submodularity in context. Can you map it to a concept in Bayesian DL?\n\nRegarding the baselines, I think it is important to compare the method to more recent advances in order to fully grasp its capabilities. As is shown in the Related Work, the field has evolved a lot since deep ensembles were first proposed. Question to the authors: how come more baselines were not considered?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2UL28GUYC_", "reviewer": "Reviewer_xECp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "In general, the paper provides a novel perspective for constructing the ensemble, connecting f-divergence between a distribution and a kernel mixture with sub-modular functions. Submodularity is useful in exploration, e.g., submodular set function maximization. The general idea is novel and intuitive, which could be helpful for the research in deep ensemble.\n\nThe execution of the implementation is solid in general. Some findings and analysis are interesting, e.g., a better approximation factor compared with theoretical guaranteed factor could be achieved for f-divergence. I have the following questions or comments before making the final decision:\n1. Could you provide a high level explanation of why sub-modularity might be helpful for constructing the ensemble before introducing the definitions, theorems and algorithms? Jumping to this functional view after brief review of previous works might be too abrupt.\n2. How are the mode-seeking and mean-seeking ability of the proposed method justified theoretically or empirically?\n3. There are a few approximations like using the point estimate for the reverse KL. How does it affect the general performance and how is this quantified?\n4. It is claimed the heuristic techniques like batchensemble or hyper parameter ensemble could be used adjunct with the proposed method. However, those methods are scalable to large datasets like ImageNet and could be computed efficiently. I wonder if the proposed method could be extended to ImageNet level datasets.\n5. How is the performance of robustness under adversarial attack?", "summary_of_the_paper": "This proposes studies ensemble construction from a combinatorial point of view. Analysis are conducted in function space, where the intuition are from and algorithm are developed. Specifically, it starts by formally defining the sub-modularity then proving f-divergence for a distribution and a mixture of kernels to be super-modular function. A greedy maximization of f-divergence is given and its implementation for approximating Bayesian posterior are presented. The experiments on synthetic data show the ability of covering the posterior of the proposed method, compared with the deep ensemble approach. It also conducts experiments on real-world data for OOD detection tasks. ", "summary_of_the_review": "This paper is with interesting idea and solid execution. I recommend a weak accept before the questions are answered.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "117qNiEsKUs", "reviewer": "Reviewer_ZKEY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "# Strengths\n- The problem of making Deep Ensemble Bayesian is important for the community, and the proposed method seems to be a viable approach to solve this problem.\n\n- To my knowledge, the idea of rephrasing the Bayesian inference problem as a submodular one is conceptually novel.\n\n- The theoretical justification is impressive and interesting.\n\n# Weaknesses & Concerns\n\n- It seems that, eventually, you use the reverse KL divergence as an instantiation of the f-divergence, and develop the practical training loss Eq 12 and Eq 14. \nThough your modeling is applicable to arbitrary f-divergence, you have not demonstrated the implications of such universality.\n\n- Eq 14 is closely related to the function-space POVI (Wang et al., 2019). The difference is that you train these ensemble candidates sequentially with weight decay while function-space POVI trains them in parallel without weight decay? I would like to see an empirical/theoretical clarification of the connections/difference between these two approaches.\n\n- Although I know the main contribution of this work is on a new theoretical framework for Bayesian Deep Ensemble, I still want to see that this works can beat Deep Ensemble significantly in more scenarios. The current performance gains in Table 1 are marginal.", "summary_of_the_paper": "The paper proposes a novel and principled method to make Deep Ensemble Bayesian. It minimizes an f-divergence between the true posterior and a kernel density estimator fitting the functions associated with the ensemble candidates. The authors formulate the learning as a submodular problem and propose to use a greedy approach to solve it. The resultant learning objective consists of a novel diversity term. Some out-of-distribution detection results in computer vision demonstrate the efficacy of the proposed method.", "summary_of_the_review": "This paper has done a great job in making Deep Ensemble Bayesian theoretically, despite being short of empirical verification. So, currently,  I recommend a weak acceptance for it.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a new framework to make deep ensembles provide better coverage of the posterior and be less reliant on initialisation. The authors generally did a good job presenting their approach, avoiding dubious claims that deep-ensembles are non-Bayesian, and instead focusing on ways in which deep ensembles can be improved, practically and theoretically. It is worth noting in a revised version, however, that many approximate inference procedures do not have theoretical guarantees. The claim that deep ensembles have "arbitrary bad approximation guarantees" is vague and appears to single them out in a way that could confuse the reader. Regarding priors, it is also worth noting that Wilson & Izmailov (2020) provide evidence that the prior in weight space induces a prior in function space with useful properties, although the prior can be improved.

The authors do a good job of responding to reviewers, and describing limitations. Ultimately, however, the general opinion was not swayed to accept. In addition to reviewer concerns, the experimental evaluation could be substantially improved. There are several procedures that build on deep ensembles to capture uncertainty within modes. How does this procedure compare? Why are no likelihood evaluations considered? What about accuracy? In its present form, it's unclear what practical value the contributions are providing, besides possibly better OOD detection, but even that direction is explored in a relatively limited way. It could also be interesting to measure the distance of the predictive distribution to a good proxy for the Bayesian model average. Overall, there are the raw ingredients of a good paper here, and the authors are encouraged to continue with this work.
Decision: Reject