# Know Your Limits: Uncertainty Estimation with ReLU Classifiers Fails at
Reliable OOD Detection

Dennis Ulmer ITU Copenhagen
Copenhagen, Denmark  Giovanni Cinà Pacmed BV
Amsterdam, Netherlands

###### Abstract

A crucial requirement for reliable deployment of deep learning models for
safety-critical applications is the ability to identify out-of-distribution
(OOD) data points, samples which differ from the training data and on which a
model might underperform. Previous work has attempted to tackle this problem
using uncertainty estimation techniques. However, there is empirical evidence
that a large family of these techniques do not detect OOD reliably in
classification tasks.

This paper gives a theoretical explanation for said experimental findings and
illustrates it on synthetic data. We prove that such techniques are not able
to reliably identify OOD samples in a classification setting, since their
level of confidence is generalized to unseen areas of the feature space. This
result stems from the interplay between the representation of ReLU networks as
piece-wise affine transformations, the saturating nature of activation
functions like softmax, and the most widely-used uncertainty metrics.

##  1 Introduction

Notwithstanding the tremendous improvements achieved in recent years by means
of novel and larger deep learning architectures, advanced models still lack
certain properties that guarantee their safety in high-stakes applications
like health care [He et al., 2019], autonomous driving [McDermid et al.,
2019], and more. Among other traits, the capability to discern familiar data
samples seen during the training stage (in-distribution) from abnormal inputs
(out-of-distribution) is of paramount importance in certain contexts. Take for
instance a hospital, in which an algorithm is used to predict complications
for a patient. Due to factors like changing patient demographics or protocols,
but also simply different hospital environments, predictions might become less
reliable and cause harm to the patient. A degradation of the model performance
might only be detected much later, when the shift in the test data becomes
more apparent - at which point further damage accumulates, hence the need
arises to implement techniques that can detect OOD samples reliably.

Unfortunately, it is well-known that neural network classifiers tend to be
overconfident in their predictions [Guo et al., 2017], i.e. exhibiting high
levels of certainty when it is unwarranted, and often fail to correctly
identify OOD samples [Ovadia et al., 2019, Nalisnick et al., 2019]. A recent
study on medical tabular data has shown that even techniques specifically
developed to quantify the model’s uncertainty struggle at detecting OOD
samples for a relatively simple classification task [Ulmer et al., 2020].
Crucially, it was shown that neural discriminators tend to project vast areas
of high certainty far away from the training distribution - a behaviour that
seems completely at odds with reliable OOD detection. These observations can
easily be replicated on synthetic data, as displayed in Figure 1(a), where one
can observe open areas of constant certainty stretching beyond the training
data. The reasons for this behavior in a classification setting are hitherto
much less studied.

(a) Predictive entropy
$\tilde{\mathbb{H}}[p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})]$
of ReLU classifier.

(b) Polytopal linear regions induced by same classifier [Arora et al., 2018].

(c) Magnitude of gradient of predictive entropy
$||\nabla_{\operatorname{\mathbf{x}}}\tilde{\mathbb{H}}[p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})]||_{2}$.

Figure 1: (a) Uncertainty of a neural classifier with ReLU activations
measured by predictive entropy on synthetic data, illustrated by increasing
shades of purple with white denoting absolute certainty. (b) Polytopal, linear
regions in the feature space induced by the same classifier (as introduced by
Arora et al. [2018]). (c) Norm of the gradient of the predictive entropy
plotted by increasing shades of green, showing how small perturbations in the
input have a decreasing influence on the uncertainty of the network as we
stray away from the training data, creating large areas in which uncertainty
levels are overgeneralized. Exceptions to this are the model’s decision
boundaries, which is discussed in Section 6. Polytopes are drawn using the
code of Jordan et al. [2019].

In this paper we propose a novel theoretical argument to explain such
phenomena, showing that certainty levels are generalized on sub-spaces defined
by the network (see Figure 1(b) and 1(c)). We do this by simulating covariate
shift for single feature values of real variables and studying the asymptotic
behavior of the model. Our contributions are as follows:

  1. 1.

Our first result shows that, under mild assumptions about the network’s
behaviour on certain subspaces, ReLU-based neural network classifiers coupled
with widely used uncertainty metrics always converge to a fixed uncertainty
level on OOD samples.

  2. 2.

We extend this result by proving that variational inference-based and
ensembling methods in combination with several uncertainty estimation
techniques suffer from the same problem (Theorem 1). This phenomenon is
illustrated and discussed on synthetic data.

These results entail that, when the conditions of the theorem are met, these
models cannot be used to reliably detect OOD: since the level of certainty is
generalized from seen to unseen data, the models are unable to differentiate
between the two. The findings of this article have bearings on OOD detection
for several critical applications using neural classifiers with ReLU
activation functions.

##  2 Related Work

Overconfidence in neural networks has been studied from several angles; we
summarize here some of the main lines of research. One way to counteract the
problem of overconfidence lies in the quantification of a network’s
uncertainty, which is usually divided into aleatoric and epistemic
uncertainty. The former denotes _non-reducible_ uncertainty, e.g. uncertainty
intrinsic to the data generating process, while the latter refers to
_reducible_ uncertainty. This includes the knowledge about the best model
class, as well as about the parameters which explain the data best [Der
Kiureghian and Ditlevsen, 2009, Hüllermeier and Waegeman, 2019]. In this
article, we are interested in the effect of methods that estimate uncertainty
post-hoc. One way to evaluate uncertainty estimation methods is the study of
their behaviour in presence of OOD samples [Ovadia et al., 2019]. Ulmer et al.
[2020] specifically show how the methods used in our work fail in practice to
detect clinically relevant OOD groups of patients in a medical context. Kompa
et al. [2020] conclude that many uncertainty methods produce confidence
intervals which do not include the actual observations on OOD data.

A variety of articles approaches the phenomenon of overconfidence from a
calibration perspective: starting with the work of Guo et al. [2017], follow-
up work develops improved variants of temperature scaling [Laves et al., 2019]
or new types of scaling altogether Kumar et al. [2018], Kull et al. [2019]. A
separate line of enquiry investigates the effect of different activation
functions [Bridle, 1990, Ramachandran et al., 2018], exploring alternatives to
the sigmoid or softmax function111Their relationship is outlined in more
detail in Appendix A.1 or Bridle [1990]. as the final component of neural
discriminators [de Brébisson and Vincent, 2016, Hendrycks and Gimpel, 2017,
Laha et al., 2018, Martins and Astudillo, 2016]. But to the best of our
knowledge, only Hein et al. [2019] give a theoretical explanation for this
behavior in ReLU-networks showing that, when a point is scaled uniformly, the
network’s probability mass is placed on a single class. However, they do not
extend their findings to uncertainty estimation metrics nor investigate the
implications for variational approaches or ensembling. Mukhoti et al. [2021]
show that epistemic and aleatoric uncertainty cannot be disentangled
successfully purely based on the output distribution of a single network.

##  3 Preliminaries

In this section we introduce some notation and relevant definitions for the
rest of this work.

###  3.1 Notation

We denote sets in calligraphic letters, e.g. $\mathcal{P}$ or $\mathcal{C}$.
Vectors are represented using lower-case bold letters such as
$\operatorname{\mathbf{x}}$ or $\operatorname*{\bm{\theta}}$. For functions
with multiple outputs, a lowercase index refers to a specific component of the
output, e.g. with a function $f:\mathbb{R}\rightarrow\mathbb{R}^{N}$,
$f(x)_{n}$ denotes one of the output components with $n\in 1,...,N$.
Furthermore, we use $\odot$ to denote the Hadamard product and
$||\ldots||_{2}$ for the $l_{2}$-norm.

###  3.2 Out-of-Distribution Data

Given a set $\mathcal{C}=\\{1,\ldots,C\\}$ of numbers denoting class labels,
we define a data set to be a finite set
$\mathcal{D}\subset\mathbb{R}^{D}\times\mathcal{C}$ containing $N$ ordered
pairs of $D$-dimensional feature vectors $\operatorname{\mathbf{x}}_{i}$ and
corresponding class labels $y_{i}$ obtained from some (unknown) joint
distribution $\operatorname{\mathbf{x}}_{i},y_{i}\ \sim\
p(\operatorname{\mathbf{x}},y)$ s.t.
$\mathcal{D}=\\{(\operatorname{\mathbf{x}}_{i},y_{i})\\}_{i=1}^{N}$. Although
there exist many different notions of dataset shift [Shimodaira, 2000, Moreno-
Torres et al., 2012], we particularly focus on _covariate shift_ , in which
the distribution of feature values - the covariates - differs from the
original training distribution $p(\operatorname{\mathbf{x}})$. We focus on
this kind of shift as it is especially common in non-stationary environments
like healthcare [Curth et al., 2019] and many other applications.

To simulate covariate shift, we obtain OOD samples by shifting points away
from the training distribution by means of a scaling factor. This approach is
in line with recent experiments on covariate shift and OOD detection [Ovadia
et al., 2019, Ulmer et al., 2020]. We would expect a reliable OOD detection
model to output increasingly higher uncertainty as points stray further and
further away from the mass of $p(\operatorname{\mathbf{x}})$, thus we study
the behaviour of OOD detection models in the limit, when the scaling factor is
allowed to grow indefinitely in at least one dimension.

###  3.3 Uncertainty Metrics

We begin by defining a neural discriminator, which we assume to follow common
architectural conventions, i.e. to consist of a series of affine
transformations with ReLU [Glorot et al., 2011] activation functions. Together
with a final softmax function [Bridle, 1990], it parametrizes a categorical
distribution over classes.

######  Definition 1.

Let $\operatorname{\mathbf{x}}\in\mathbb{R}^{D}$ be an input vector and $C$
the number of classes in a classification problem. The unnormalized output of
the network after $L$ layers is a function
$f_{\operatorname*{\bm{\theta}}}:\mathbb{R}^{D}\rightarrow\mathbb{R}^{C}$ with
the final output following after an additional softmax function
$\bar{\sigma}(\cdot)$ s.t. $p_{\operatorname*{\bm{\theta}}}=\bar{\sigma}\circ
f_{\operatorname*{\bm{\theta}}}$, so
$p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\equiv\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}$.
Thus the discriminator is represented by a function
$p_{\operatorname*{\bm{\theta}}}:\mathbb{R}^{D}\rightarrow[0,1]^{C}$ which is
parametrized by a vector $\operatorname*{\bm{\theta}}$.

The softmax function $\bar{\sigma}:\mathbb{R}^{C}\rightarrow\mathbb{R}^{C}$ is
commonly defined as

$\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}=\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\prime}=1}^{C}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}})}$
(1)

We will consider a (non-exhaustive) set of popular uncertainty metrics in this
work, which we introduce in turn. Hendrycks and Gimpel [2017] introduce a
simple baseline, which is the highest probability observed for any class:

$y_{\text{max}}=\max_{c\in\mathcal{C}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})$

Ideally, the model’s predictive distribution would become more uniform for
challenging inputs (e.g. in areas of class overlap) and thus produce a lower
confidence score $y_{\text{max}}$.222Which is why we measure _un_ certainty by
$1-y_{\text{max}}$. The other uncertainty estimation techniques introduced
below try to approximate the uncertainty of the predictive distribution for a
new data point $\operatorname{\mathbf{x}}^{\prime}$, which is commonly
factorized as follows:

$p(y|\operatorname{\mathbf{x}}^{\prime},\mathcal{D})=\int
p(y|\operatorname{\mathbf{x}}^{\prime},\operatorname*{\bm{\theta}})p(\operatorname*{\bm{\theta}}|\mathcal{D})d\operatorname*{\bm{\theta}}$
(2)

In the following, we use
$p(y|\operatorname{\mathbf{x}},\operatorname*{\bm{\theta}})\equiv
p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})$. This equation
is intractable: the weight posterior
$p(\operatorname*{\bm{\theta}}|\mathcal{D})$ cannot be computed precisely
using Bayes’ rule. Hence the weight posterior is often replaced by a
variational posterior $q(\operatorname*{\bm{\theta}})$ and the expectation
formed by this expression is commonly approximated by a Monte Carlo
approximation:

$\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\approx\frac{1}{K}\sum_{k=1}^{K}p^{(k)}_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}});\quad{\operatorname*{\bm{\theta}}}^{(k)}\sim
q(\operatorname*{\bm{\theta}})$ (3)

Other methods for which a similar aggregation of predictions can be used
include Markov-chain Monte-Carlo procedures [Welling and Teh, 2011, Neklyudov
et al., 2020] or simply ensembling [Lakshminarayanan et al., 2017], which does
not require sampling. In this work, we will use the term _instance_ to refer
to a network characterized by $\operatorname*{\bm{\theta}}^{(k)}$ in order to
group all of these methods together. We follow the reasoning of Wilson and
Izmailov [2020] to interpret both variational and ensembling methods as
examples of Bayesian model averaging. A very intuitive method to aggregate all
instances’ predictions and estimate uncertainty is to compute the variance
over all classes, such as in Smith and Gal [2018]:

$\displaystyle\bar{\sigma}^{2}$
$\displaystyle=\frac{1}{C}\sum_{c=1}^{C}\mathbb{E}_{#1}\bigg{[}\Big{(}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{)}^{2}\bigg{]}$
$\displaystyle-\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}^{2}$

The more predictions disagree, the larger the average variance per class will
become. Another approach lies in measuring the Shannon entropy $\mathbb{H}$ of
the predictive distribution [Gal, 2016]:

$\tilde{\mathbb{H}}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}=\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}$

Entropy is maximal when all probability mass is centered on a single class,
i.e. all aggregated predictions agree on a label, and minimum when the
predictive distribution is uniform. As these two metrics capture only the
total uncertainty, we finally also consider the mutual information between
model parameters and a data sample [Smith and Gal, 2018], which aims to
isolate epistemic uncertainty:

$\displaystyle\underbrace{\mathbb{I}(y,{\operatorname*{\bm{\theta}}}|\mathcal{D},\operatorname{\mathbf{x}})}_{\text{Model
uncertainty}}$
$\displaystyle\approx\underbrace{\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}}_{\text{Total
uncertainty}}$
$\displaystyle-\underbrace{\mathbb{E}_{#1}\bigg{[}\mathbb{H}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}}_{\text{Data
uncertainty}}$

The term itself can be interpreted as the gain in information about the ideal
model parameters and correct label upon receiving an input. If we can only
gain a little, that implies that parameters are already well-specified and
that the epistemic uncertainty is low.

###  3.4 Additional Definitions

Here we introduce some concepts related to monotonicity, which will become
central in the next sections. In the univariate case, we call a function
strictly increasing on an interval $\mathcal{I}=[a,b]$ with $a<b$ and
$a,b\in\mathbb{R}$ if it holds that

$\forall x^{\prime}\in\mathcal{I}\ \bigg{(}\frac{\partial}{\partial
x}f(x)\Big{|}_{x=x^{\prime}}>0\bigg{)}$

where $\cdot|_{x=x^{\prime}}$ refers to evaluating the value of the derivative
of $f$ at $x^{\prime}$. This definition can also be extended to multivariate
functions by requiring strict monotonicity (strictly increasing or decreasing)
in all dimensions:

######  Definition 2.

We call a multivariate function $f:\mathbb{R}^{D}\rightarrow\mathbb{R}$
strictly monotonic on a subspace $\mathcal{P}\subseteq\mathbb{R}^{D}$ if it
holds that

$\displaystyle\forall d\in 1,\ldots,D,$
$\displaystyle\Bigg{(}\forall\operatorname{\mathbf{x}}^{\prime}\in\mathcal{P},\
\Big{(}\nabla_{\operatorname{\mathbf{x}}}f(\operatorname{\mathbf{x}})\Big{|}_{\operatorname{\mathbf{x}}=\operatorname{\mathbf{x}}^{\prime}}\Big{)}_{d}<0\
$ (4) $\displaystyle\vee\
\forall\operatorname{\mathbf{x}}^{\prime}\in\mathcal{P},\
\Big{(}\nabla_{\operatorname{\mathbf{x}}}f(\operatorname{\mathbf{x}})\Big{|}_{\operatorname{\mathbf{x}}=\operatorname{\mathbf{x}}^{\prime}}\Big{)}_{d}>0\Bigg{)}$

where $(\cdot)_{d}$ refers to $\frac{\partial f(x_{d})}{\partial
x_{d}}|_{x_{d}=x^{\prime}_{d}}$, the $d$-th component of the gradient
$\nabla_{\operatorname{\mathbf{x}}}f(\operatorname{\mathbf{x}})$ evaluated at
$\operatorname{\mathbf{x}}^{\prime}$. We call a multivariate function
$f:\mathbb{R}^{D}\rightarrow\mathbb{R}^{C}$ _component-wise strictly
monotonic_ if the above definition holds for the gradient of every output
component
$\nabla_{\operatorname{\mathbf{x}}}f(\operatorname{\mathbf{x}})_{c}$.

We note here that the softmax function is an example for a component-wise
strictly monotonic function. As later lemmas investigate the behavior of
functions in the limit, it is furthermore useful to define regions of the
feature space that are unbounded in at least one direction. We call a
_partially-unbounded polytope_ (henceforth abbreviated by PUP) a convex
subspace of $\mathbb{R}^{D}$ that is unbounded in at least one dimension $d$,
i.e. if the polytope’s projection onto $d$ is either left-bounded by $-\infty$
or right-bounded by $\infty$, or both.

##  4 Convergence of Predictions on OOD

Figure 2: Dependencies between theoretical results. Information in parentheses
denotes the section in the document.

In this section we will show that, moving the input to the extremes of the
feature space, a ReLU classifier will converge to a fixed prediction. To
demonstrate this, we must establish how the distance from the training data
affects the network’s logits. To this end, we utilize a known result stating
that neural networks employing piece-wise linear activation functions
partition the input space into polytopes (such as in Figure 1(b); Arora et
al., 2018). Given the saturating nature of the softmax, we conclude in
Proposition 1 that even for extreme feature values in the limit, the output
distribution of the model will not change anymore. In order to help the reader
untangle the interdependence of upcoming results, we provide a flow chart in
Figure 2.

We first describe how to re-write a ReLU network - or any other network with
piece-wise linear activation functions - as a piece-wise affine
transformation, borrowing from Croce and Hein [2018], Hein et al. [2019]. We
start with the common form of $f_{\operatorname*{\bm{\theta}}}$ as a series of
affine transformations, interleaved with ReLU activation functions, which we
will denote by $\phi$:

$\displaystyle f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})=$
$\displaystyle\operatorname{\mathbf{W}}_{L}\phi\big{(}\operatorname{\mathbf{W}}_{L-1}\phi\big{(}\ldots\phi\big{(}\operatorname{\mathbf{W}}_{1}\operatorname{\mathbf{x}}+\operatorname{\mathbf{b}}_{1}\big{)}\ldots\big{)}$
(5)
$\displaystyle+\operatorname{\mathbf{b}}_{L-1}\big{)}+\operatorname{\mathbf{b}}_{L}$

In the following, let
$f_{\operatorname*{\bm{\theta}}}^{l}(\operatorname{\mathbf{x}})$ denote the
output of layer $l$ before applying an activation function. We now define a
layer-specific diagonal matrix $\Phi_{l}\in\mathbb{R}^{n_{l}\times n_{l}}$ in
the following way, where $n_{l}$ denotes the hidden units in layer $l$:

$\operatorname{\bm{\Phi}}_{l}(\operatorname{\mathbf{x}})=\begin{bmatrix}\mathbbm{1}(f_{\operatorname*{\bm{\theta}}}^{l}(\operatorname{\mathbf{x}})_{1}>0)&\cdots&0\\\
\vdots&\ddots&\vdots\\\
0&\cdots&\mathbbm{1}(f_{\operatorname*{\bm{\theta}}}^{l}(\operatorname{\mathbf{x}})_{n_{l}}>0)\\\
\end{bmatrix}$

This allows us to rewrite Equation 5 by replacing the usage of $\phi$ with a
matrix multiplication using $\operatorname{\bm{\Phi}}_{l}$:

$\displaystyle f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})=$
$\displaystyle\operatorname{\mathbf{W}}_{L}\operatorname{\bm{\Phi}}_{L-1}(\operatorname{\mathbf{x}})\big{(}\operatorname{\mathbf{W}}_{L-1}\operatorname{\bm{\Phi}}_{L-2}(\operatorname{\mathbf{x}})\big{(}\ldots$
(6)
$\displaystyle\operatorname{\bm{\Phi}}_{1}(\operatorname{\mathbf{x}})\big{(}\operatorname{\mathbf{W}}_{1}\operatorname{\mathbf{x}}+\operatorname{\mathbf{b}}_{1}\big{)}\ldots\big{)}+\operatorname{\mathbf{b}}_{L-1}\big{)}+\operatorname{\mathbf{b}}_{L}$

Finally, by distributing the matrix products inside-out (see Appendix A.2 for
more detail), we can rewrite the network as a single affine transformation
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{V}}(\operatorname{\mathbf{x}})\operatorname{\mathbf{x}}+\operatorname{\mathbf{a}}(\operatorname{\mathbf{x}})$
with

$\operatorname{\mathbf{V}}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{W}}_{L}\bigg{(}\prod_{l=1}^{L-1}\operatorname{\bm{\Phi}}_{l}(\operatorname{\mathbf{x}})\operatorname{\mathbf{W}}_{L-l}\bigg{)}$
$\operatorname{\mathbf{a}}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{b}}_{L}+\sum_{l=1}^{L-1}\bigg{(}\prod_{l^{\prime}=1}^{L-l}\operatorname{\mathbf{W}}_{L+1-l^{\prime}}\operatorname{\bm{\Phi}}_{L-l^{\prime}}(\operatorname{\mathbf{x}})\bigg{)}\operatorname{\mathbf{b}}_{l}$

Note that the definition of
$\operatorname{\mathbf{V}}(\operatorname{\mathbf{x}})$ corresponds to the
Jacobian of $f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})$,
meaning that $v_{cd}=\frac{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}}{\partial
x_{d}}$ This is very useful, as it allows to quickly check whether a network
$f_{\operatorname*{\bm{\theta}}}$ is component-wise strictly monotonic by
checking $\operatorname{\mathbf{V}}(\operatorname{\mathbf{x}})$ for entries
containing zeros. As Hein et al. [2019] show, this formulation can also be
used to characterize a set of polytopes $\mathcal{Q}=\\{Q_{1},\ldots,Q_{M}\\}$
induced by $f_{\operatorname*{\bm{\theta}}}$ and that within each polytope,
the function has a unique representation as an affine transformation. For this
reason, we drop the dependence of $\operatorname{\mathbf{V}}$ and
$\operatorname{\mathbf{a}}$ on $\operatorname{\mathbf{x}}$ when we refer to a
specific polytope. Such polytopes are constructed by first retrieving the
half-spaces induced by each of the network’s neurons and then intersecting all
said half-spaces to generate convex regions or polytopes.333We refer the
reader to Appendix A.3 or Hein et al. [2019] for details on the construction,
since it is not central to our reasoning. We are especially interested in
polytopes that are unbounded in at least one direction. In this regard, the
results of Croce and Hein [2018] and Hein et al. [2019] show that there is a
finite number of polytopes corresponding to the given network, and their Lemma
3.1 proves the existence of at least one unbounded polytope. Furthermore,
under a mild condition on $\operatorname{\mathbf{V}}$, we can ascertain that
$f_{\operatorname*{\bm{\theta}}}$ will be component-wise strictly monotonic on
any polytope.

######  Lemma 1.

Suppose $f_{\operatorname*{\bm{\theta}}}$ is a ReLU network according to
Definition 1. Then $f_{\operatorname*{\bm{\theta}}}$ is a component-wise
strictly monotonic function on every of its polytopes $Q\in\mathcal{Q}$, as
long as its corresponding matrix $\operatorname{\mathbf{V}}$ has no zero
entries.

###### Proof.

Let $Q$ be one such polytope. As discussed, when restricted to $Q$, the
network corresponds to an affine transformation
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{V}}\operatorname{\mathbf{x}}+\operatorname{\mathbf{a}}$
with $\operatorname{\mathbf{V}}\in\mathbb{R}^{C\times D}$ and
$\operatorname{\mathbf{a}}\in\mathbb{R}^{C}$.
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}$ thus
corresponds to the dot product of the $c$-th row of
$\operatorname{\mathbf{V}}$ and $\operatorname{\mathbf{x}}$ plus the $c$-th
element of $\operatorname{\mathbf{a}}$. It follows that the partial derivative
of $f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}$ with
respect to a dimension $d$ would then amount to the element $v_{cd}$ in
$\operatorname{\mathbf{V}}$. This entails that, if $v_{cd}\neq 0$, at any
point $\operatorname{\mathbf{x}}\in Q$ the gradient will be always positive or
always negative. ∎

We note here that the component-wise strict monotonicity of
$f_{\operatorname*{\bm{\theta}}}$ and softmax do not entail the same property
for $p_{\operatorname*{\bm{\theta}}}$.444To see a counterexample, the reader
can check that even assuming component-wise strict monotonicity for
$f_{\operatorname*{\bm{\theta}}}$, if the matrix $\operatorname{\mathbf{V}}$
associated to $f_{\operatorname*{\bm{\theta}}}$ on a specific polytope has a
column $d$ filled with the same value $a$, then the resulting
$p_{\operatorname*{\bm{\theta}}}$ will have a gradient of 0 at dimension $d$,
regardless of what class we are considering. This is because the partial
derivatives of the softmax, when all multiplied by the same constant $a$, add
up to zero. Nonetheless, the monotonic behaviour of
$f_{\operatorname*{\bm{\theta}}}$ is sufficient to drive the logits to plus or
minus infinity in the limit, a phenomenon that constrains the output of
$p_{\operatorname*{\bm{\theta}}}$ as we scale a data sample away from training
data.

We begin our investigation of behaviour in the limit by showing that if we
scale a vector only in a single dimension, we eventually always remain within
a unique PUP.

######  Lemma 2.

Let $\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$ and
$\mathcal{Q}=\\{Q_{1},\ldots,Q_{M}\\}$ be the finite set of polytopes
generated by a network $f_{\operatorname*{\bm{\theta}}}$. Let
$\operatorname{\bm{\alpha}}\in\mathbb{R}^{D}$ be a vector s.t. $\forall
d^{\prime}\neq d,\alpha_{d^{\prime}}=1$. There exist a value $\beta>0$ and
$m\in{1,\dots,M}$ such that for all $\alpha_{d}>\beta$, the product
$\operatorname{\mathbf{x}}^{\prime}\odot\operatorname{\bm{\alpha}}$ lies
within $Q_{m}$.

###### Proof.

The proof mirrors the proof of Lemma 3.1 in Hein et al. [2019], so we only
provide the intuition. By contradiction, suppose that there is no unique
polytope and thus the point
$\operatorname{\mathbf{x}}^{\prime}\odot\operatorname{\bm{\alpha}}$ must
traverse different polytopes as we scale up $\alpha_{d}$. Since there are
finitely many polytopes, eventually the same polytope $Q_{m}$ will have to be
traversed twice. Since the polytopes are convex, all the points on the line
connecting the locations of where the boundary of $Q_{m}$ was crossed the
first and second time must lie within $Q_{m}$, but this contradicts the fact
that the scaled point traverses different polytopes. ∎

From here onward, we adapt the following shorthand to simplify notation: Given
a scaling vector $\operatorname{\bm{\alpha}}\in\mathbb{R}^{D}$ s.t. $\forall
d^{\prime}\neq d,\alpha_{d^{\prime}}=1$, we use
$\mathcal{P}(\operatorname{\mathbf{x}}^{\prime},d)$ to denote the PUP that
$\operatorname{\mathbf{x}}^{\prime}$ lands in when scaling it with
$\alpha_{d}$ in the limit. This definition implies that we can only scale
parallel to the basis vectors (for a discussion on how restrictive this is,
see Section 6).

Finally, in the next lemma we establish that the output distribution converges
to a fixed point using the $l_{2}$-norm of the gradient
$\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})$.
Generally, in regions of the feature space where the classifier is predicting
the same probability distribution over classes, small perturbations in the
input $\operatorname{\mathbf{x}}$ will not change the prediction. Therefore,
the gradient in these regions w.r.t. the input will be small and potentially
even correspond to the zero vector, with a norm of (or close to) zero.

######  Proposition 1 (Convergence of predictions in the limit).

Suppose that $f_{\operatorname*{\bm{\theta}}}$ is a ReLU-network. Let
$\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$, suppose
$\operatorname{\bm{\alpha}}$ is a scaling vector and that the associated PUP
$\mathcal{P}(\operatorname{\mathbf{x}}^{\prime},d)$ has a corresponding matrix
$\mathbf{V}$ with no zero entries. Then it holds that

$\forall c\in\mathcal{C},\
\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}=0$

The whole proof exceeds the available space and can be found in Appendix A.4,
so we present the main intuitions here. Because of Lemma 2, we know the scaled
point $\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}$ will
end in a unique PUP. The assumption on $f_{\operatorname*{\bm{\theta}}}$ then
triggers Lemma 1, from which we can infer that scaling the input in a single
dimension leads all logits to $\pm\infty$. Because of the saturating property
of the softmax, this will in turn provoke the output of
$p_{\operatorname*{\bm{\theta}}}$ to converge to a fixed point.

As an aside, we now recast Theorem 3.1 in Hein et al. [2019] in our framework,
showing that the model becomes increasingly certain in a single class, placing
all its probability mass on it in the limit. The proof of this additional
Proposition is in Appendix A.5.

######  Proposition 2.

Let $f_{\operatorname*{\bm{\theta}}}$ be ReLU network. Let
$\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$, suppose
$\operatorname{\bm{\alpha}}$ is a scaling vector and that the associated PUP
$\mathcal{P}(\operatorname{\mathbf{x}}^{\prime},d)$ has a corresponding matrix
$\mathbf{V}$ with no zero entries. Assume the $d$-th column of
$\operatorname{\mathbf{V}}$ has no duplicate entries. Then there exists a
class $c$ such that

$\lim_{\alpha_{d}\rightarrow\infty}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}))_{c}=1$

In conclusion, we have shown in this section that the output probabilities of
ReLU networks are less and less sensitive to small perturbations of the input
in the limit and, under the assumptions of Proposition 2, will converge to
favor a single class, in which they appear to be very confident in. In the
next section we prove that all other uncertainty metrics also converge to
fixed values in the limit.

##  5 Convergence of Uncertainty Estimation Metrics

In Proposition 1, we have established how the prediction of a model converges
to a fixed point when feature values become extreme. We now want to show a
similar property about the uncertainty estimation techniques introduced in
Section 3.3. To this end, we have to establish how the predictions coming from
multiple model instances interact, a point we analyze in Lemma 4. Then, we
demonstrate how the uncertainty metrics also converge to a fixed value in the
limit by proving the case for each of them in turn, before bundling our
results in Theorem 1. We start with the easiest metric, which also applies to
a single model.

######  Lemma 3.

(Max. softmax probability) Suppose that $f_{\operatorname*{\bm{\theta}}}$ is a
ReLU-network. Let $\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$,
suppose $\operatorname{\bm{\alpha}}$ is a scaling vector and that the
associated PUP $\mathcal{P}(\operatorname{\mathbf{x}}^{\prime},d)$ has a
corresponding matrix $\mathbf{V}$ with no zero entries. It holds that

$\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\max_{c\in\mathcal{C}}\Big{(}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{)}\Big{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}=0$

###### Proof.

The gradient of the $\max$ function will be a specific
$\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})$,
which reduces this to the case already proven in Proposition 1. ∎

Note that for this metric, the combination with Proposition 2 shows that the
model be fully confident in a single class in the limit. For our following
lemmas, we want to consider uncertainty scores that are based on multiple
instances, e.g. different ensemble members or forward passes using re-sampled
dropout masks. What all of these approaches have in common is that for every
$k$, the network parameters $\operatorname*{\bm{\theta}}^{(k)}$ will differ,
and thus also the polytopal tesselation of the feature space. Hence, we have
to adjust our assumptions accordingly. For every instance $k$, let us denote
the affine function on a polytope $Q^{(k)}$ as
$f_{\operatorname*{\bm{\theta}}}^{(k)}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{V}}^{(k)}\operatorname{\mathbf{x}}+\operatorname{\mathbf{a}}^{(k)}$.
In order for our previous strategy to hold, we now assume $\forall k\in
1,\ldots,K$ that $\mathcal{P}^{(k)}(\operatorname{\mathbf{x}}^{\prime},d)$ has
a matrix $\operatorname{\mathbf{V}}^{(k)}$ which does not have any zero
entries. Note that even though this assumption has to hold for all $k$, this
does not mean that the matrices have to be identical.

######  Lemma 4 (Convergence of aggregated predictions in the limit).

Suppose that
$f_{\operatorname*{\bm{\theta}}}^{(1)},\ldots,f_{\operatorname*{\bm{\theta}}}^{(K)}$
are ReLU networks. Let $\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$,
suppose $\operatorname{\bm{\alpha}}$ is a scaling vector and that the for all
$k$, the associated PUP
$\mathcal{P}^{(k)}(\operatorname{\mathbf{x}}^{\prime},d)$ has a corresponding
matrix $\mathbf{V}^{(k)}$ with no zero entries. It holds that

$\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\
\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}=0$

The full proof of this lemma can be found in appendix section A.6. The
analogous lemmas for the remaining uncertainty metrics are stated and proved
in appendix sections A.7, A.8 and A.9. The proof strategy for all further
metrics is to simplify and reduce the uncertainty metrics such that Lemma 4 or
Proposition 1 can be applied. All of these result combined now pave the way
for our central theorem.

######  Theorem 1 (Convergence of uncertainty level in the limit).

Suppose that
$f_{\operatorname*{\bm{\theta}}}^{(1)},\ldots,f_{\operatorname*{\bm{\theta}}}^{(K)}$
are ReLU networks. Let $\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$,
suppose $\operatorname{\bm{\alpha}}$ is a scaling vector and that the for all
$k$, the associated PUP
$\mathcal{P}^{(k)}(\operatorname{\mathbf{x}}^{\prime},d)$ has a corresponding
matrix $\mathbf{V}^{(k)}$ with no zero entries. Then, whenever uncertainty is
measured via either of the following metrics 1. Maximum softmax probability 2.
Class variance 3. Predictive entropy 4. Approximate mutual information the
network(s) will converge to fixed uncertainty scores for
$\operatorname{\mathbf{x}}^{\prime}\odot\operatorname{\bm{\alpha}}$ in the
limit of $\alpha_{d}\rightarrow\infty$

###### Proof.

The four parts of the theorem are proven separately by lemmas 3, 5 (A.7), 6
(A.8) and 7 (A.9). ∎

What follows from this result is that methods based on multiple instances of
ReLU classifiers will suffer from the aforementioned problem as long as
uncertainty is estimated with one of the techniques listed above. Next we
demonstrate how these assumptions and results apply on synthetic data.

##  6 Synthetic Data Experiments

(a) Neural discriminator with maximum probability [Hendrycks and Gimpel,
2017].

(b) MC Dropout [Gal and Ghahramani, 2016] with mutual info. [Smith and Gal,
2018].

(c) Neural ensemble [Lakshminarayanan et al., 2017] with class variance.

(d) Anchored ensemble [Pearce et al., 2020] with mutual information [Smith and
Gal, 2018].

Figure 3: Uncertainty on the half-moon dataset, including the binary
classification AUC-ROC. (Top row) The uncertainty surface is represented with
increasingly darker shades of purple, with white being the lowest uncertainty.
Open-ended regions of static certainty appear across different models and
metrics, bein extrapolated to unseen data (see 3(a)-3(c)); this phenomenon is
less apparent in some instances (3(d)). (Bottom row) Increasing shades of
green indicate the magnitude of the gradient of the uncertainty score w.r.t.
the input. All metrics show open ended regions where the magnitude approaches
zero.

To illustrate our findings, we plot the uncertainty surfaces and the gradient
magnitudes of different models and uncertainty metric pairings on the half
moons dataset, which we generate using the corresponding function in the
scikit-learn package [Pedregosa et al., 2011]. Detailed information about the
procedure can be found in Appendix B along with additional plots.555The code
used for the experiments is publicly available under
https://github.com/Kaleidophon/know-your-limits.

For a single network, we can observe in Figure 3(a)) that there exist vast
open-ended regions of stable confidence, confirming the findings of Theorem 1.
However, in the bottom part of Figure 3(a)) we can observe green regions with
high gradient magnitude which do not seem to comply with our findings. In this
case, we can see that these regions follow the decision boundaries. Due to the
exponential function in the softmax, it is intuitive that small perturbation
in these areas would have a large impact on the uncertainty score, resulting
in a high gradient magnitude. But why does the magnitude not decrease in the
limit as predicted by Theorem 1? We formulated our scaling vector
$\operatorname{\bm{\alpha}}$ in way that only allows scaling along one of the
coordinate axes. Therefore, if the decision boundaries are not parallel to the
axes, by scaling we eventually escape the green areas and arrive at an area
with gradient of magnitude zero. If the green regions were parallel to the
axes then this would result in a violation of our main assumption. Traversing
the input space parallel to a decision boundary in direction $d$ will not
influence the prediction within the polytope, meaning that there will be
entries $v_{cd}=0$.666A decision boundary in a polytope is not the only way in
which this assumption can be broken, but it still appears to hold reasonably
often. For instance, just around $6.3\%$ of plotted points in Figure 1 possess
a matrix $\operatorname{\mathbf{V}}$ with at least one zero entry - all
located in the PUP in the top right corner.

Turning to predictions aggregated from multiple network instances in Figures
3(b)-3(d), we again observe large regions of constant uncertainty. The high-
confidence region in the plots using mutual information displays a different
behaviour from the others. As this metric aims to isolate epistemic
uncertainty, it makes sense that uncertainty would be lowest around the
training data, i.e. where the model is best specified. The character of the
green regions in the bottom part of Figures 3(c) and 3(d) can again be
explained by decision boundaries: In these cases, we have multiple instances
with parameters $\operatorname*{\bm{\theta}}^{(k)}$, all with their own
polytopal structure. When they overlap, the regions of the feature space where
the assumption of our theorem is violated can either extend (Figure 3(c)) or
shrink (Figure 3(d)), based on the diversity among instances. The fact that
the anchored ensemble in Figure 3(d) does not exhibit such uniform regions of
uncertainty like the vanilla ensemble could be explained by the fact that its
training procedure encourages diversification between members. In turn, the
difference between MC Dropout and ensemble models can be elucidated using
recent insights that variational methods tend to only explore a single mode of
the weight posterior $p(\operatorname*{\bm{\theta}}|\mathcal{D})$, while
ensemble members often spread across multiple modes [Wilson and Izmailov,
2020].

Overall, we have seen that our theorem can explain why an overgeneralization
of uncertainty scores beyond the training data results in failure in OOD
detection. We also explored the cases in which our assumptions are violated,
i.e. by multiple, diverse model instances. In such scenarios, identification
of OOD samples could in theory succeed, but often fails to do so reliably, see
e.g. Ovadia et al. [2019], Ulmer et al. [2020]. These insights can also help
explain many other empirical findings in this regard on a variety of real-
world datasets, e.g. Smith and Gal [2018], Kompa et al. [2020].

##  7 Discussion

In the past sections, we have proven that a single model will produce very
confident softmax probabilities and that even for models using multiple
network instances like ensembling and MC Dropout, all the uncertainty metrics
analyzed will tend to fixed scores on far away samples, generalizing along
open-ended polytopes induced by their architecture. The significance of this
observation is that, albeit some modest success at OOD detection that might
take place locally, the models we analyzed have an inherent overgeneralization
bias: by extrapolating their level of uncertainty beyond the seen data, they
hinder their ability to discern between in-distribution and OOD data.

For a single network, it can even be proven that the predictions attained on
OOD samples is not just fixed but also unreasonably high in one class, as
shown in our Proposition 2, which adapts the main result in Hein et al. [2019]
to our framework. Our formulation shows that this result is also obtained when
scaling a point along a single dimension.

Most of our results depend on an assumption on the matrix
$\operatorname{\mathbf{V}}$ corresponding to the PUP containing the OOD
sample. Like discussed in Section 6, except for the case of decision
boundaries that run parallel to a basis vector, this assumptions should rarely
be broken for ReLU networks, as their are known to be resistant to the problem
of vanishing gradients [Glorot et al., 2011]. We thus expect the behaviour
described in our theoretical results to be very common, as confirmed by our
experiments.

It remains to be explored how the stable level of certainty that we derive for
all metrics relates to the degree of diversity of the underlying set of model
instances, but given our experimental results it appears to be dependent on
the level of “disagreement” among them, i.e. when polytopes of different
instances overlap to an increasing degree. Since it is hard to flag instances
of OOD reliably this way, the aforementioned methods run a concrete risk of
missing OOD samples, with potentially unintended, negative side-effects. These
investigations bring us closer to a theoretically-motivated explanation to
observations such as reported in Smith and Gal [2018], Ovadia et al. [2019],
Kompa et al. [2020], Ulmer et al. [2020] and to enable the discovery of more
effective methods.

Future research might be divided in two categories: efforts to solve the
problem of OOD detection, and attempts at sharpening our theoretical
understanding of the issue. The following approaches fall into the first
category. One way consists of complementing neural discriminators with
density-based approaches such as in Grathwohl et al. [2020]. Other lines of
research try to have neural discriminators parametrize Dirichlet instead of
categorical distributions [Malinin and Gales, 2018, Joo et al., 2020,
Charpentier et al., 2020] or making models distance-aware [Liu et al., 2020]
or supplementing the network architecture with Bayesian capabilities
[Kristiadi et al., 2020]. In the second category we mention that more work is
needed to cover the case of discrete features. Reasoning in the limit is not
available for categorical or ordinal variables and one would probably have to
resort to techniques that address directly the difference between the training
and the new distribution. Furthermore, it remains an open question whether the
results presented here can be extended be extended to GELU activations
[Hendrycks and Gimpel, 2016], which represent a continuous approximation of
the ReLU function with the same asymptotic behavior. The GELU has recently
become a very popular alternative in deep neural networks [Devlin et al.,
2019, Lan et al., 2020, Brown et al., 2020]. Lastly, the similarity between
lemmas used for Theorem 1 suggest that similar results could be derived for a
whole family of uncertainty metrics. These investigations are left to future
work.

## Author Contributions

Both authors contributed equally in writing the paper and deriving theoretical
results. Dennis Ulmer implemented the code to run experiments and create plots
and illustrations in this work.

## Acknowledgements

We would like to thank Mareike Hartmann, Adam Izdebski, Natalie Schluter,
Emese Thamó and Christina Winkler for their tremendously helpful feedback on
this work.

## References

  * Arora et al. [2018] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee.  Understanding deep neural networks with rectified linear units.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018.
  * Blundell et al. [2015] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra.  Weight uncertainty in neural networks.  _arXiv preprint arXiv:1505.05424_ , 2015.
  * Bridle [1990] John S Bridle.  Probabilistic interpretation of feedforward classification network outputs, with relationships to statistical pattern recognition.  In _Neurocomputing_ , pages 227–236. Springer, 1990.
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.  URL https://proceedings.neurips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html.
  * Charpentier et al. [2020] Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann.  Posterior network: Uncertainty estimation without OOD samples via density-based pseudo-counts.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Croce and Hein [2018] Francesco Croce and Matthias Hein.  A randomized gradient-free attack on relu networks.  In _German Conference on Pattern Recognition_ , pages 215–227. Springer, 2018.
  * Curth et al. [2019] Alicia Curth, Patrick Thoral, Wilco van den Wildenberg, Peter Bijlstra, Daan de Bruin, Paul Elbers, and Mattia Fornasa.  Transferring clinical prediction models across hospitals and electronic health record systems.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 605–621. Springer, 2019.
  * de Brébisson and Vincent [2016] Alexandre de Brébisson and Pascal Vincent.  An exploration of softmax alternatives belonging to the spherical loss family.  In Yoshua Bengio and Yann LeCun, editors, _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016.
  * Der Kiureghian and Ditlevsen [2009] Armen Der Kiureghian and Ove Ditlevsen.  Aleatory or epistemic? does it matter?  _Structural safety_ , 31(2):105–112, 2009.
  * Devlin et al. [2019] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In Jill Burstein, Christy Doran, and Thamar Solorio, editors, _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pages 4171–4186. Association for Computational Linguistics, 2019\.  10.18653/v1/n19-1423.  URL https://doi.org/10.18653/v1/n19-1423.
  * Gal [2016] Yarin Gal.  Uncertainty in deep learning.  _University of Cambridge_ , 1(3), 2016.
  * Gal and Ghahramani [2016] Yarin Gal and Zoubin Ghahramani.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In _International conference on Machine Learning_ , pages 1050–1059, 2016.
  * Gao and Pavel [2017] Bolin Gao and Lacra Pavel.  On the properties of the softmax function with application in game theory and reinforcement learning.  _arXiv preprint arXiv:1704.00805_ , 2017.
  * Glorot et al. [2011] Xavier Glorot, Antoine Bordes, and Yoshua Bengio.  Deep sparse rectifier neural networks.  In _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , pages 315–323. JMLR Workshop and Conference Proceedings, 2011.
  * Grathwohl et al. [2020] Will Grathwohl, Kuan-Chieh Wang, Jörn-Henrik Jacobsen, David Duvenaud, Mohammad Norouzi, and Kevin Swersky.  Your classifier is secretly an energy based model and you should treat it like one.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_ , 2020.
  * Guo et al. [2017] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger.  On calibration of modern neural networks.  In _Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017_ , pages 1321–1330, 2017.
  * He et al. [2019] Jianxing He, Sally L Baxter, Jie Xu, Jiming Xu, Xingtao Zhou, and Kang Zhang.  The practical implementation of artificial intelligence technologies in medicine.  _Nature medicine_ , 25(1):30–36, 2019.
  * Hein et al. [2019] Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf.  Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 41–50, 2019.
  * Hendrycks and Gimpel [2016] Dan Hendrycks and Kevin Gimpel.  Gaussian error linear units (gelus).  _arXiv preprint arXiv:1606.08415_ , 2016.
  * Hendrycks and Gimpel [2017] Dan Hendrycks and Kevin Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  2017\.
  * Hüllermeier and Waegeman [2019] Eyke Hüllermeier and Willem Waegeman.  Aleatoric and epistemic uncertainty in machine learning: A tutorial introduction.  _arXiv preprint arXiv:1910.09457_ , 2019.
  * Joo et al. [2020] Taejong Joo, Uijung Chung, and Min-Gwan Seo.  Being bayesian about categorical probability.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 4950–4961. PMLR, 2020\.
  * Jordan et al. [2019] Matt Jordan, Justin Lewis, and Alexandros G. Dimakis.  Provable certificates for adversarial examples: Fitting a ball in the union of polytopes.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 14059–14069, 2019.
  * Kompa et al. [2020] Benjamin Kompa, Jasper Snoek, and Andrew Beam.  Empirical frequentist coverage of deep learning uncertainty quantification procedures.  _arXiv preprint arXiv:2010.03039_ , 2020.
  * Kristiadi et al. [2020] Agustinus Kristiadi, Matthias Hein, and Philipp Hennig.  Being bayesian, even just a bit, fixes overconfidence in relu networks.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 5436–5446. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/kristiadi20a.html.
  * Kull et al. [2019] Meelis Kull, Miquel Perelló-Nieto, Markus Kängsepp, Telmo de Menezes e Silva Filho, Hao Song, and Peter A. Flach.  Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 12295–12305, 2019.  URL https://proceedings.neurips.cc/paper/2019/hash/8ca01ea920679a0fe3728441494041b9-Abstract.html.
  * Kumar et al. [2018] Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain.  Trainable calibration measures for neural networks from kernel mean embeddings.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pages 2810–2819, 2018.  URL http://proceedings.mlr.press/v80/kumar18a.html.
  * Laha et al. [2018] Anirban Laha, Saneem Ahmed Chemmengath, Priyanka Agrawal, Mitesh Khapra, Karthik Sankaranarayanan, and Harish G Ramaswamy.  On controllable sparse alternatives to softmax.  In _Advances in Neural Information Processing Systems_ , pages 6422–6432, 2018.
  * Lakshminarayanan et al. [2017] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell.  Simple and scalable predictive uncertainty estimation using deep ensembles.  In _Advances in neural information processing systems_ , pages 6402–6413, 2017.
  * Lan et al. [2020] Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut.  ALBERT: A lite BERT for self-supervised learning of language representations.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020.  URL https://openreview.net/forum?id=H1eA7AEtvS.
  * Laves et al. [2019] Max-Heinrich Laves, Sontje Ihler, Karl-Philipp Kortmann, and Tobias Ortmaier.  Well-calibrated model uncertainty with temperature scaling for dropout variational inference.  _4th workshop on Bayesian Deep Learning (NeurIPS 2019), Vancouver, Canada_ , 2019.
  * Liu et al. [2020] Jeremiah Liu, Zi Lin, Shreyas Padhy, Dustin Tran, Tania Bedrax Weiss, and Balaji Lakshminarayanan.  Simple and principled uncertainty estimation with deterministic deep learning via distance awareness.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Malinin and Gales [2018] Andrey Malinin and Mark Gales.  Predictive uncertainty estimation via prior networks.  In _Advances in Neural Information Processing Systems_ , pages 7047–7058, 2018.
  * Martins and Astudillo [2016] Andre Martins and Ramon Astudillo.  From softmax to sparsemax: A sparse model of attention and multi-label classification.  In _International Conference on Machine Learning_ , pages 1614–1623, 2016.
  * McDermid et al. [2019] John Alexander McDermid, Yan Jia, and Ibrahim Habli.  Towards a framework for safety assurance of autonomous systems.  In _Artificial Intelligence Safety 2019_ , pages 1–7. CEUR Workshop Proceedings, 2019.
  * Moreno-Torres et al. [2012] Jose G Moreno-Torres, Troy Raeder, RocíO Alaiz-RodríGuez, Nitesh V Chawla, and Francisco Herrera.  A unifying view on dataset shift in classification.  _Pattern recognition_ , 45(1):521–530, 2012.
  * Mukhoti et al. [2021] Jishnu Mukhoti, Andreas Kirsch, Joost van Amersfoort, Philip HS Torr, and Yarin Gal.  Deterministic Neural Networks with Appropriate Inductive Biases Capture Epistemic and Aleatoric Uncertainty.  _arXiv preprint arXiv:2102.11582_ , 2021.
  * Nalisnick et al. [2019] Eric T. Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Görür, and Balaji Lakshminarayanan.  Do deep generative models know what they don’t know?  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.
  * Neklyudov et al. [2020] Kirill Neklyudov, Max Welling, Evgenii Egorov, and Dmitry P. Vetrov.  Involutive MCMC: a unifying framework.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , pages 7273–7282, 2020\.
  * Ovadia et al. [2019] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek.  Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift.  In _Advances in Neural Information Processing Systems_ , pages 13991–14002, 2019.
  * Pearce et al. [2020] Tim Pearce, Felix Leibfried, and Alexandra Brintrup.  Uncertainty in neural networks: Approximately bayesian ensembling.  In _International Conference on Artificial Intelligence and Statistics_ , pages 234–244, 2020.
  * Pedregosa et al. [2011] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.
  * Ramachandran et al. [2018] Prajit Ramachandran, Barret Zoph, and Quoc V. Le.  Searching for activation functions.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Workshop Track Proceedings_. OpenReview.net, 2018.
  * Shimodaira [2000] Hidetoshi Shimodaira.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  _Journal of statistical planning and inference_ , 90(2):227–244, 2000.
  * Smith and Gal [2018] Lewis Smith and Yarin Gal.  Understanding measures of uncertainty for adversarial example detection.  In _Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018_ , pages 560–569, 2018.
  * Ulmer et al. [2020] Dennis Ulmer, Lotta Meijerink, and Giovanni Cinà.  Trust issues: Uncertainty estimation does not enable reliable ood detection on medical tabular data.  In _Machine Learning for Health Workshop (NeurIPS 2020)_ , pages 341–354. PMLR, 2020.
  * Welling and Teh [2011] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pages 681–688, 2011.
  * Wilson and Izmailov [2020] Andrew Gordon Wilson and Pavel Izmailov.  Bayesian deep learning and a probabilistic perspective of generalization.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.

##  Appendix A Additional Proofs

This appendix section contains additional proofs and derivations that could
not be included in the main paper due to spatial constraints.

###  A.1 Connection between Softmax and Sigmoid

In this section we briefly outline the connection between the softmax and the
sigmoid function, which was originally shown in Bridle [1990]. Let the sigmoid
function be defined as

$\sigma(x)=\frac{\exp(x)}{1+\exp(x)}$

and softmax according to the definition Section 3.3. The output of
$f_{\operatorname*{\bm{\theta}}}$ in a multi-class classification problem with
$C$ classes corresponds to a $C$-dimensional column vector that is based on an
affine transformation of the network’s last intermediate hidden representation
$\operatorname{\mathbf{x}}_{L}$, such that
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{W}}_{L}\operatorname{\mathbf{x}}_{L}$.777The
bias term $\operatorname{\mathbf{b}}_{L}$ was omitted here for clarity.
Correspondingly, the output of $f_{\operatorname*{\bm{\theta}}}$ for a single
class $c$ can be written as the dot product between
$\operatorname{\mathbf{x}}_{L}$ and the corresponding row vector of
$\operatorname{\mathbf{W}}_{L}$ denoted as
$\operatorname{\mathbf{w}}_{L}^{(c)}$, such that
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\equiv{\operatorname{\mathbf{w}}_{L}^{(c)T}}\operatorname{\mathbf{x}}_{L}$.
For a classification problem with $C=2$ classes, we can now rewrite the
softmax probabilities in the following way:888The following argument holds
without loss of generality for
$p_{\operatorname*{\bm{\theta}}}(y=0|\operatorname{\mathbf{x}})$.

$\displaystyle p_{\operatorname*{\bm{\theta}}}(y=1|\operatorname{\mathbf{x}})$
$\displaystyle=\frac{\exp({\operatorname{\mathbf{w}}_{L}^{(1)T}}\operatorname{\mathbf{x}}_{L})}{\exp({\operatorname{\mathbf{w}}_{L}^{(0)T}}\operatorname{\mathbf{x}}_{L})+\exp({\operatorname{\mathbf{w}}_{L}^{(1)T}}\operatorname{\mathbf{x}}_{L})}$

Subtracting a constant from the weight term inside the exponential function
does not change the output of the softmax function. Using this property, we
can show the sigmoid function to be a special case of the softmax for binary
classification:

$\displaystyle p_{\operatorname*{\bm{\theta}}}(y=1|\operatorname{\mathbf{x}})$
$\displaystyle=\frac{\exp((\operatorname{\mathbf{w}}_{L}^{(1)}-\operatorname{\mathbf{w}}_{L}^{(0)})^{T}\operatorname{\mathbf{x}}_{L})}{\exp((\operatorname{\mathbf{w}}_{L}^{(0)}-\operatorname{\mathbf{w}}_{L}^{(0)})^{T}\operatorname{\mathbf{x}}_{L})+\exp((\operatorname{\mathbf{w}}_{L}^{(1)}-\operatorname{\mathbf{w}}_{L}^{(0)})^{T}\operatorname{\mathbf{x}}_{L})}$
$\displaystyle=\frac{\exp((\operatorname{\mathbf{w}}_{L}^{(1)}-\operatorname{\mathbf{w}}_{L}^{(0)})^{T}\operatorname{\mathbf{x}}_{L})}{1+\exp((\operatorname{\mathbf{w}}_{L}^{(1)}-\operatorname{\mathbf{w}}_{L}^{(0)})^{T}\operatorname{\mathbf{x}}_{L}}=\frac{\exp({\operatorname{\mathbf{w}}_{L}^{*T}}\operatorname{\mathbf{x}}_{L})}{1+\exp({\operatorname{\mathbf{w}}_{L}^{*T}}\operatorname{\mathbf{x}}_{L})}$

where
$\operatorname{\mathbf{w}}_{L}^{*}=\operatorname{\mathbf{w}}_{L}^{(1)}-\operatorname{\mathbf{w}}_{L}^{(0)}$
corresponds to the new parameter vector which is used to parametrize a single
output unit for a network in the binary classification setting.

###  A.2 Linearization of ReLU networks

In the section we give a more detailed version of the derivation of the
linearization
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{V}}(\operatorname{\mathbf{x}})\operatorname{\mathbf{x}}+\operatorname{\mathbf{a}}(\operatorname{\mathbf{x}})$
with

$\operatorname{\mathbf{V}}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{W}}_{L}\bigg{(}\prod_{l=1}^{L-1}\operatorname{\bm{\Phi}}_{l}(\operatorname{\mathbf{x}})\operatorname{\mathbf{W}}_{L-l}\bigg{)}$
$\operatorname{\mathbf{a}}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{b}}_{L}+\sum_{l=1}^{L-1}\bigg{(}\prod_{l^{\prime}=1}^{L-l}\operatorname{\mathbf{W}}_{L+1-l^{\prime}}\operatorname{\bm{\Phi}}_{L-l^{\prime}}(\operatorname{\mathbf{x}})\bigg{)}\operatorname{\mathbf{b}}_{l}$

We start from Equation 6:

$\displaystyle f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})=$
$\displaystyle\operatorname{\mathbf{W}}_{L}\operatorname{\bm{\Phi}}_{L-1}(\operatorname{\mathbf{x}})\big{(}\operatorname{\mathbf{W}}_{L-1}\operatorname{\bm{\Phi}}_{L-2}(\operatorname{\mathbf{x}})\big{(}\ldots$
$\displaystyle\operatorname{\bm{\Phi}}_{1}(\operatorname{\mathbf{x}})\big{(}\operatorname{\mathbf{W}}_{1}\operatorname{\mathbf{x}}+\operatorname{\mathbf{b}}_{1}\big{)}\ldots\big{)}+\operatorname{\mathbf{b}}_{L-1}\big{)}+\operatorname{\mathbf{b}}_{L}$

To make the steps more intuitive and to retain readability, we illustrate the
necessary steps on a simple three layer network:

$\displaystyle f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})=$
$\displaystyle\operatorname{\mathbf{W}}_{3}\operatorname{\bm{\Phi}}_{2}(\operatorname{\mathbf{x}})\big{(}\operatorname{\mathbf{W}}_{2}\operatorname{\bm{\Phi}}_{1}(\operatorname{\mathbf{x}})\big{(}\operatorname{\mathbf{W}}_{1}\operatorname{\mathbf{x}}+\operatorname{\mathbf{b}}_{1})+\operatorname{\mathbf{b}}_{2})+\operatorname{\mathbf{b}}_{3}$
$\displaystyle=$
$\displaystyle\operatorname{\mathbf{W}}_{3}\operatorname{\bm{\Phi}}_{2}(\operatorname{\mathbf{x}})\big{(}\operatorname{\mathbf{W}}_{2}\operatorname{\bm{\Phi}}_{1}(\operatorname{\mathbf{x}})\operatorname{\mathbf{W}}_{1}\operatorname{\mathbf{x}}+\operatorname{\mathbf{W}}_{2}\operatorname{\bm{\Phi}}_{1}(\operatorname{\mathbf{x}})\operatorname{\mathbf{b}}_{1})$
$\displaystyle+\operatorname{\mathbf{b}}_{2})+\operatorname{\mathbf{b}}_{3}$
$\displaystyle=$
$\displaystyle\underbrace{\operatorname{\mathbf{W}}_{3}\operatorname{\bm{\Phi}}_{2}(\operatorname{\mathbf{x}})\operatorname{\mathbf{W}}_{2}\operatorname{\bm{\Phi}}_{1}(\operatorname{\mathbf{x}})\operatorname{\mathbf{W}}_{1}}_{=\operatorname{\mathbf{V}}(x)}\operatorname{\mathbf{x}}$
$\displaystyle+\underbrace{\operatorname{\mathbf{W}}_{3}\operatorname{\bm{\Phi}}_{2}(\operatorname{\mathbf{x}})\operatorname{\mathbf{W}}_{2}\operatorname{\bm{\Phi}}_{1}(\operatorname{\mathbf{x}})\operatorname{\mathbf{b}}_{1}+\operatorname{\mathbf{W}}_{3}\operatorname{\bm{\Phi}}_{2}(\operatorname{\mathbf{x}})\operatorname{\mathbf{b}}_{2}+\operatorname{\mathbf{b}}_{3}}_{=\operatorname{\mathbf{a}}(\operatorname{\mathbf{x}})}$

which we can identify as the parts of the affine transformation above.

###  A.3 Construction of polytopal regions

In this section, we reiterate the reasoning by Hein et al. [2019] behind the
construction the polytopal regions. For this purpose, the authors define an
additional diagonal matrix
$\operatorname{\bm{\Delta}}_{l}(\operatorname{\mathbf{x}})$ per layer $l$:

$\operatorname{\bm{\Delta}}_{l}(\operatorname{\mathbf{x}})=\begin{bmatrix}\text{sign}({f_{\operatorname*{\bm{\theta}}}^{l}(\operatorname{\mathbf{x}})_{1}})&\cdots&0\\\
\vdots&\ddots&\vdots\\\
0&\cdots&\text{sign}({f_{\operatorname*{\bm{\theta}}}^{l}(\operatorname{\mathbf{x}})_{n_{l}}})\\\
\end{bmatrix}$

Together with the linearization of the network at $\operatorname{\mathbf{x}}$
explained in Appendix A.2, this is used to define a set of half-spaces for
every neuron in the network:

$\mathcal{H}_{l,i}(\operatorname{\mathbf{x}})=\Big{\\{}\operatorname{\mathbf{z}}\in\mathbb{R}^{d}\
\Big{|}\
\operatorname{\bm{\Delta}}_{l}(\operatorname{\mathbf{x}})\big{(}\operatorname{\mathbf{V}}_{l}(\operatorname{\mathbf{x}})_{i}\operatorname{\mathbf{z}}+\operatorname{\mathbf{a}}_{l}(\operatorname{\mathbf{x}})_{i}\big{)}\geq
0\Big{\\}}$

Here, $\operatorname{\mathbf{V}}_{l}(\operatorname{\mathbf{x}})_{i}$ and
$\operatorname{\mathbf{b}}_{l}(\operatorname{\mathbf{x}})_{i}$ denote the
parts of the affine transformation obtained for the $i$-th neuron of the
$l$-th layer, so the $i$-th row vector in
$\operatorname{\mathbf{V}}_{l}(\operatorname{\mathbf{x}})$ and the $i$-th
scalar in $\operatorname{\mathbf{b}}_{l}(\operatorname{\mathbf{x}})$,
respectively. Finally, the polytope $Q$ containing $\operatorname{\mathbf{x}}$
is obtained by taking the intersection of all half-spaces induced by every
neuron in the network:

$Q(\operatorname{\mathbf{x}})=\bigcap_{l\in 1,\ldots,L}\bigcap_{i\in
1,...,n_{l}}\mathcal{H}_{l,i}(\operatorname{\mathbf{x}})$

###  A.4 Proof of Proposition 1

Figure 4: Illustration taken from the work of Gao and Pavel [2017],
illustrating the interplay of softmax probabilities between components for
$C=2$ in $\mathbb{R}^{2}$.

We proceed to analyze the behaviour of gradients in the limit via two more
lemmas; First, we establish the saturating property of the softmax In Lemma 9,
i.e. the model doesn’t change its decision anymore in the limit.

######  Lemma 9.

Let $c,c^{\prime}\in\mathcal{C}$ be two arbitrary classes. It then holds for
their corresponding output components (logits) that

$\lim_{f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\pm\infty}\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}=0$
(7)

###### Proof.

Here, we first begin by evaluating the derivative of one component of the
function w.r.t to an arbitrary component:

$\displaystyle\ \ \ \frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}=\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})}$
$\displaystyle=\frac{\mathbbm{1}(c=c^{\prime})\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})}-\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}})}{\big{(}\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})\big{)}^{2}}$

This implies that $\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}=$

$\begin{cases}\begin{aligned}
\displaystyle&-\frac{\exp(2f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\big{(}\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})\big{)}^{2}}\\\
&+\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})}&\quad\text{If
}c=c^{\prime}\\\\[14.22636pt]
\displaystyle&-\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}+f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}})}{\big{(}\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})\big{)}^{2}}&\quad\text{If
}c\neq c^{\prime}\\\ \end{aligned}\end{cases}$ (8)

or more compactly:

$\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}=\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}\big{(}\mathbbm{1}(c=c^{\prime})-\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c^{\prime}}\big{)}$

Based on Equation 8, we can now investigate the asymptotic behavior for
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\infty$
more easily, starting with the $c=c^{\prime}$ case:

$\displaystyle\lim_{f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\infty}\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}$
(9)
$\displaystyle=\underbrace{\lim_{f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\infty}-\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})}\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})}}_{\text{-1}}$
$\displaystyle+\underbrace{\lim_{f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\infty}\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})}}_{1}=0$

With the numerator and denominator being dominated by the exponentiated
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}$ in Equation
LABEL:eq:softmax-derivative-equal, the first term will tend to $-1$, while the
second term will tend to $1$, resulting in a derivative of $0$. The $c\neq
c^{\prime}$ can be analyzed the following way:

$\displaystyle\lim_{f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\infty}\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}$
(10)
$\displaystyle=\underbrace{\lim_{f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\infty}\bigg{(}-\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})}\bigg{)}}_{-1}$
$\displaystyle\cdot\underbrace{\lim_{f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\infty}\bigg{(}\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}})}{\sum_{c^{\operatorname{{\prime\prime}}}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\operatorname{{\prime\prime}}}})}\bigg{)}}_{0}=0$

Again, we factorize the fraction in Equation LABEL:eq:softmax-derivative-
unequal into the product of two softmax functions, one for component $c$, one
for $c^{\prime}$. The first factor will again tend to $-1$ as in the other
case, however the second will approach $0$, as only the sum in the denominator
will approach infinity. As the limit of a product is the products of its
limits, this lets the whole expression approach $0$ in the limit.

When
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow-\infty$,
both cases approach $0$ due to the exponential function, which proves the
lemma. ∎

How to interplay between different softmax components produces zero gradients
in the limit is illustrated in Figure 4. In Lemma 10, we compare the rate of
growth of different components of $p_{\operatorname*{\bm{\theta}}}$. We show
that for the decomposed function $p_{\operatorname*{\bm{\theta}}}$, the rate
at which the softmax function converges to its output distribution in the
limit outpaces the change in the underlying logits w.r.t. the network input.

######  Lemma 10.

Suppose that $f_{\operatorname*{\bm{\theta}}}$ is a ReLU-network. Let
$\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$, suppose
$\operatorname{\bm{\alpha}}$ is a scaling vector and that the associated PUP
$\mathcal{P}(\operatorname{\mathbf{x}}^{\prime},d)$ has a corresponding matrix
$\mathbf{V}$ with no zero entries. Then it holds that

$\displaystyle\forall c^{\prime}\in\mathcal{C},$
$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\bigg{(}\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}\bigg{)}^{-1}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}$
(11) $\displaystyle-\bigg{(}\frac{\partial}{\partial
x_{d}}f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}\bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}=\infty$

###### Proof.

We evaluate the first term of Equation 11 to show that it grows exponentially
in the limit. By Lemma 2 we know that in the limit $\alpha_{d}\to\infty$ the
vector $\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}$
will remain within $\mathcal{P}(\operatorname{\mathbf{x}}^{\prime},d)$. Since
the matrix associated with this PUP has no zero entries, we know by Lemma 1
that the gradient of
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}$ on dimension
$d$ is either always positive or negative, hence
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\pm\infty$.
Given Lemma 9 describing the asymptotic behavior in the limit, it follows that

$\lim_{f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\pm\infty}\bigg{(}\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}\bigg{)}^{-1}=\infty$

where we can see that the result is a symmetrical function displaying
exponential growth in the limit of
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\pm\infty$.
We now show that because we assumed $f_{\operatorname*{\bm{\theta}}}$ to be a
neural network consisting of $L$ affine transformations with ReLU activation
functions, the output of the final layer is only going to be a linear
combination of its inputs.999Here we make the argument for the whole function
$f_{\operatorname*{\bm{\theta}}}:\mathbb{R}^{D}\rightarrow\mathbb{R}^{C}$, but
the conclusions also applies to every output component of the function
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}$. This can be
proven by induction. Let us first look at the base case $L=1$. In the rest of
this proof, we denote $\operatorname{\mathbf{x}}_{l}$ as the input to layer
$l$, with $\operatorname{\mathbf{x}}_{1}\equiv\operatorname{\mathbf{x}}$, and
$\operatorname{\mathbf{W}}_{l},\operatorname{\mathbf{b}}_{l}$ the
corresponding layer parameters. $\operatorname{\mathbf{a}}_{l}$ signifies the
result of the affine transformation that is then fed into the activation
function.

$\displaystyle f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})$
$\displaystyle=\phi(\operatorname{\mathbf{a}}_{1})=\phi(\operatorname{\mathbf{W}}_{1}\operatorname{\mathbf{x}}_{1}+\operatorname{\mathbf{b}}_{1})$
(12) $\displaystyle\frac{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})}{\partial\operatorname{\mathbf{x}}_{1}}$
$\displaystyle=\frac{\phi(\operatorname{\mathbf{a}}_{1})}{\partial\operatorname{\mathbf{a}}_{1}}\frac{\partial\operatorname{\mathbf{a}}_{1}}{\partial\operatorname{\mathbf{x}}_{1}}=\bm{\mathbbm{1}}(\operatorname{\mathbf{x}}_{1}>\mathbf{0})^{T}\operatorname{\mathbf{W}}_{1}\
$ $\displaystyle\frac{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})}{\partial x_{1d}}$
$\displaystyle=\mathbbm{1}(x_{d}>0)w_{1d}$

where
$\bm{\mathbbm{1}}(\operatorname{\mathbf{x}}_{1}>\mathbf{0})=[\mathbbm{1}(x_{11}>0),\ldots,\mathbbm{1}(x_{1d}>0)]^{T}$,
$w_{1d}$ denotes the $d$-th column of $\operatorname{\mathbf{W}}_{1}$. This is
a linear function, which proves the base case. Let now
$\frac{\partial\operatorname{\mathbf{x}}_{l}}{\partial\operatorname{\mathbf{x}}_{1}}$
denote the partial derivative of the input to the $l$-th layer w.r.t to the
input and suppose that it is linear by the inductive hypothesis. Augmenting
the corresponding network by another linear adds another term akin to the
second expression in Equation 12 to the chain of partial derivatives:

$\frac{\partial\operatorname{\mathbf{x}}_{l+1}}{\partial\operatorname{\mathbf{x}}_{1}}=\frac{\partial\operatorname{\mathbf{x}}_{l+1}}{\partial\operatorname{\mathbf{x}}_{l}}\frac{\partial\operatorname{\mathbf{x}}_{l}}{\partial\operatorname{\mathbf{x}}_{1}}$
(13)

which is also a linear function of, proving the induction step. Because we
know that both terms of the product in Equation 13 are linear, the second term
of the Equation 11 is as well. Together with the previous insight that the
first term is exponential, this implies that it will outgrow the second in the
limit, creating an infinitively-wide gap between them and thereby proving the
lemma. ∎

Equipped with the results of Lemmas 9 and 10, we can finally prove the
proposition:

###### Proof.

We show that one scalar factor contained in the factorization of the gradient
$\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})$
tends to zero under the given assumptions, having the whole gradient become
the zero vector in the limit. We begin by again factorizing the gradient
$\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})$
using the multivariate chain rule:

$\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})=\sum_{c^{\prime}=1}^{C}\frac{\partial}{\partial
f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}}\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}\cdot\nabla_{\operatorname{\mathbf{x}}}f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}$
(14)

By Lemma 1 and 2 we know that $f_{\operatorname*{\bm{\theta}}}$ is a
component-wise strictly monotonic function on
$\mathcal{P}(\operatorname{\mathbf{x}}^{\prime},d)$, which implies for the
limit of $\alpha_{d}\rightarrow\infty$ that $\forall
c\in\mathcal{C}:f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\pm\infty$.
Then, Lemma 9 implies that the first factor of every part in the sum of
Equation 14 will tend to zero in the limit. Lemma 10 ensures that the first
factor approximates zero quicker than every component of the gradient
$\nabla_{\operatorname{\mathbf{x}}}f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}$
potentially approaching infinity, causing the product to result in the zero
vector. As this results in a sum over $C$ zero vectors in the limit, this
proves the lemma. ∎

###  A.5 Proof of Proposition 2

###### Proof.

We start by rewriting the softmax probability for the $c$-th logit:

$\displaystyle\bar{\sigma}(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}}))_{c}$
$\displaystyle=\frac{\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c})}{\sum_{c^{\prime}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}})}$
$\displaystyle=1-\frac{\sum_{c^{\prime\prime}\in\mathcal{C}\setminus\\{c\\}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime\prime}})}{\sum_{c^{\prime}\in\mathcal{C}}\exp(f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}})}$

By Lemma 1 and 2 we have shown that $f_{\operatorname*{\bm{\theta}}}$ is a
component-wise strictly monotonic function on
$\mathcal{P}(\operatorname{\mathbf{x}}^{\prime},d)$, so we know that $\forall
c^{\prime}\in\mathcal{C}:f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c^{\prime}}\rightarrow\pm\infty$
as $\alpha_{d}\rightarrow\infty$. We now treat the two limits $\pm\infty$ in
order. Because of the assumption that $d$-column of $\mathbf{V}$ has no
duplicate entries, this implies that there must be a $c\in\mathcal{C}$ s.t.
$\forall c^{\prime}\neq c:\ v_{cd}>v_{c^{\prime}d}$. Thus, in the limit of
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow\infty$,
the sum in the _denominator_ of the fraction including the logit of $c$ will
tend to infinity faster than the the sum in the _numerator_ not including
$c$’s logit, and thus the fraction itself will tend to $0$, proving this case.
In the case of
$f_{\operatorname*{\bm{\theta}}}(\operatorname{\mathbf{x}})_{c}\rightarrow-\infty$,
the _numerator_ of the fraction will tend to $0$ faster than the _denominator_
, having the fraction approach $0$ in the limit as well, proving the second
case and therefore the lemma. ∎

###  A.6 Proof of Lemma 4

###### Proof.

$\displaystyle\lim\limits_{\alpha\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\
\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Linearity of gradient: $\displaystyle=$
$\displaystyle\lim\limits_{\alpha\to\infty}\operatorname{\bigg{|}\bigg{|}}\mathbb{E}_{#1}\bigg{[}\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Utilize Jensen’s inequality
$\phi(\mathbb{E}_{#1}[\operatorname{\mathbf{x}}])\leq\mathbb{E}_{#1}[\phi(\operatorname{\mathbf{x}})]$
as $l_{2}$-norm is a convex function and Proposition 1: $\displaystyle\leq$
$\displaystyle\lim\limits_{\alpha\to\infty}\mathbb{E}_{#1}\bigg{[}\
\underbrace{\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}}_{=0\
(\text{Proposition }\ref{proposition:overconfidence-softmax})}\ \bigg{]}=0$

Because the last expression is an upper bound to the original expression and
the $l_{2}$ norm is lower-bounded by $0$, this proves the lemma. ∎

###  A.7 Proof of Lemma 5

######  Lemma 5.

(Asymptotic behavior with softmax variance) Suppose that
$f_{\operatorname*{\bm{\theta}}}^{(1)},\ldots,f_{\operatorname*{\bm{\theta}}}^{(K)}$
are ReLU networks. Let $\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$,
suppose $\operatorname{\bm{\alpha}}$ is a scaling vector and that for all $k$,
the associated PUP $\mathcal{P}^{(k)}(\operatorname{\mathbf{x}}^{\prime},d)$
has a corresponding matrix $\mathbf{V}^{(k)}$ with no zero entries. It holds
that

$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\
\frac{1}{C}\sum_{c=1}^{C}\mathbb{E}_{#1}\bigg{[}\Big{(}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{)}^{2}\bigg{]}$
$\displaystyle-\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}^{2}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}=0$

###### Proof.

$\displaystyle\lim\limits_{\alpha\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\frac{1}{C}\sum_{c=1}^{C}\mathbb{E}_{#1}\bigg{[}\Big{(}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{)}^{2}\bigg{]}$
$\displaystyle-$
$\displaystyle\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}^{2}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Linearity of gradient: $\displaystyle=$
$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\frac{1}{C}\sum_{c=1}^{C}\nabla_{\operatorname{\mathbf{x}}}\mathbb{E}_{#1}\bigg{[}\Big{(}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{)}^{2}\bigg{]}$
$\displaystyle-$
$\displaystyle\nabla_{\operatorname{\mathbf{x}}}\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}^{2}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Apply triangle inequality $||x+y||\leq||x||+||y||$ to sum over all $c$:
$\displaystyle\leq$
$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\frac{1}{C}\sum_{c=1}^{C}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\mathbb{E}_{#1}\bigg{[}\Big{(}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{)}^{2}\bigg{]}$
$\displaystyle-$
$\displaystyle\nabla_{\operatorname{\mathbf{x}}}\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}^{2}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
On the first term use linearity of gradients and apply chain rule, do it in
the reverse order on the second term: $\displaystyle=$
$\displaystyle\lim\limits_{\alpha_{d}\to\infty}$
$\displaystyle\frac{1}{C}\sum_{c=1}^{C}\operatorname{\bigg{|}\bigg{|}}\mathbb{E}_{#1}\bigg{[}2p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\underbrace{\vrule
width=0.0pt,height=0.0pt,depth=9.24706pt{\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})}}_{=\bm{0}\text{
(Proposition \ref{proposition:overconfidence-
softmax})}}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\bigg{]}$
$\displaystyle-$
$\displaystyle\Bigg{(}2\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}\Bigg{)}$
$\displaystyle\cdot$ $\displaystyle\mathbb{E}_{#1}\bigg{[}\underbrace{\vrule
width=0.0pt,height=0.0pt,depth=11.38092pt{\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})}}_{=\bm{0}\text{
(Proposition \ref{proposition:overconfidence-
softmax})}}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\bigg{]}\operatorname{\bigg{|}\bigg{|}}_{2}=0$

We can see that due to an intermediate result of Proposition 1, i.e. that
$\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})$
approaches the zero vector in the limit, the innermost gradients tend to zero,
bringing the whole expression to 0.

Because the final is an upper bound to the original expression and because the
$l_{2}$ norm has a lower bound of $0$, this proves the lemma. ∎

###  A.8 Proof of Lemma 6

######  Lemma 6.

(Asymptotic behavior for predictive entropy) Suppose that
$f_{\operatorname*{\bm{\theta}}}^{(1)},\ldots,f_{\operatorname*{\bm{\theta}}}^{(K)}$
are ReLU networks. Let $\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$,
suppose $\operatorname{\bm{\alpha}}$ is a scaling vector and that for all $k$,
the associated PUP $\mathcal{P}^{(k)}(\operatorname{\mathbf{x}}^{\prime},d)$
has a corresponding matrix $\mathbf{V}^{(k)}$ with no zero entries. It holds
that

$\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}=0$

###### Proof.

$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
$\displaystyle=\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\Bigg{(}\sum_{c=1}^{C}\
\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}$
$\displaystyle\cdot\log\bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\bigg{)}\Bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Linearity of gradient:
$\displaystyle=\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\sum_{c=1}^{C}\
\nabla_{\operatorname{\mathbf{x}}}\Bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}$
$\displaystyle\cdot\log\bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\bigg{)}\Bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Apply product rule:
$\displaystyle=\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\Bigg{(}\sum_{c=1}^{C}\
\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}$
$\displaystyle\cdot\bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\bigg{)}^{-1}$
$\displaystyle\cdot\nabla_{\operatorname{\mathbf{x}}}\Bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\Bigg{)}$
$\displaystyle+\nabla_{\operatorname{\mathbf{x}}}\bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\bigg{)}$
$\displaystyle\cdot\log\bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Factor out gradient:
$\displaystyle=\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\sum_{c=1}^{C}\
\nabla_{\operatorname{\mathbf{x}}}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}$
$\displaystyle\cdot\bigg{(}1+\log\bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\bigg{)}\bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Apply triangle inequality to sum over all $c$: $\displaystyle\leq$
$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\sum_{c=1}^{C}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}$
$\displaystyle\cdot\bigg{(}1+\log\bigg{(}\mathbb{E}_{#1}\bigg{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\bigg{]}\bigg{)}\bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
As the log expectation just evaluates to a scalar, it can be pulled out of the
norm and we can apply Lemma 4
$\displaystyle=\lim\limits_{\alpha_{d}\to\infty}\sum_{c=1}^{C}\
\underbrace{\bigg{(}1+\log\bigg{(}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\bigg{)}\bigg{)}}_{\text{Scalar}}$
$\displaystyle\cdot\underbrace{\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{]}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}}_{=0\
(\text{Lemma }\ref{aggregation-theorem})}=0$

As the final result is an upper bound to the original expression and is lower-
bounded by $0$ due to the $l_{2}$ norm, this proves the lemma. ∎

###  A.9 Proof of Lemma 7

######  Lemma 7.

(Asymptotic behavior for approximate mutual information) Suppose that
$f_{\operatorname*{\bm{\theta}}}^{(1)},\ldots,f_{\operatorname*{\bm{\theta}}}^{(K)}$
are ReLU networks. Let $\operatorname{\mathbf{x}}^{\prime}\in\mathbb{R}^{D}$,
suppose $\operatorname{\bm{\alpha}}$ is a scaling vector and that for all $k$,
the associated PUP $\mathcal{P}^{(k)}(\operatorname{\mathbf{x}}^{\prime},d)$
has a corresponding matrix $\mathbf{V}^{(k)}$ with no zero entries. It holds
that

$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\bigg{(}\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}$
$\displaystyle-\mathbb{E}_{#1}\bigg{[}\mathbb{H}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}\bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}=0$

###### Proof.

$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\bigg{(}\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}$
$\displaystyle-\mathbb{E}_{#1}\bigg{[}\mathbb{H}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}\bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Linearity of gradients: $\displaystyle\leq$
$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\bigg{(}\nabla_{\operatorname{\mathbf{x}}}\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}$
$\displaystyle-\nabla_{\operatorname{\mathbf{x}}}\mathbb{E}_{#1}\bigg{[}\mathbb{H}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}\bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Linearity of gradients on second part of difference: $\displaystyle=$
$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\bigg{(}\nabla_{\operatorname{\mathbf{x}}}\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}$
$\displaystyle-\mathbb{E}_{#1}\bigg{[}\nabla_{\operatorname{\mathbf{x}}}\mathbb{H}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}\bigg{)}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Applying chain rule and intermediate result of Proposition 1: $\displaystyle=$
$\displaystyle\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}$
$\displaystyle-\mathbb{E}_{#1}\bigg{[}\sum_{c=1}^{C}\Big{(}1+\log
p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})\Big{)}\underbrace{\vrule
width=0.0pt,height=0.0pt,depth=7.82433pt{\nabla_{\operatorname{\mathbf{x}}}p_{\operatorname*{\bm{\theta}}}(y=c|\operatorname{\mathbf{x}})}}_{=\bm{0}\text{
Proposition \ref{proposition:overconfidence-softmax})}}\bigg{]}$
$\displaystyle\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}$
Because this lets the entire second term become the zero vector in the limit,
the remaining part reduces to the case proven in Lemma 6: $\displaystyle=$
$\displaystyle\underbrace{\lim\limits_{\alpha_{d}\to\infty}\operatorname{\bigg{|}\bigg{|}}\nabla_{\operatorname{\mathbf{x}}}\mathbb{H}\bigg{[}\mathbb{E}_{#1}\Big{[}p_{\operatorname*{\bm{\theta}}}(y|\operatorname{\mathbf{x}})\Big{]}\bigg{]}\bigg{|}_{\operatorname{\mathbf{x}}=\operatorname{\bm{\alpha}}\odot\operatorname{\mathbf{x}}^{\prime}}\operatorname{\bigg{|}\bigg{|}}_{2}}_{\text{Lemma
}\ref{lemma:asymptotic-predictive-entropy}}=0$

As the final result is an upper bound to the original expression and the
$l_{2}$ norm provides a lower bound of $0$, this proves the lemma. ∎

##  Appendix B Synthetic Data Experiments

We perform our experiments on the half-moons dataset, using the corresponding
function to generate the dataset in scikit-learn [Pedregosa et al., 2011],
producing $500$ samples for training and $250$ samples for validation using a
noise level of $.125$.

We do hyperparameter search using the ranges listed in Table 2, settling on
the values given in Table 1 after $200$ evaluation runs per model (for NN and
MCDropout; the hyperparameters found for NN were then used for PlattScalingNN,
AnchoredNNEnsemble, NNEnsemble as well). We also performed a similar
hyperparameter search for the Bayes-by-backprop [Blundell et al., 2015] model,
which seemed to not have yielded a suitable configuration even after extensive
search, which is why results were omitted here. All models were trained with a
batch size of $64$ and for $20$ epochs at most using early stopping with a
patience of $5$ epochs and the Adam optimizer.

All of the plots produced can be found in Figure 5 and 6, where uncertainty
values where plotted for different ranges depending on the metric (variance:
$0$-$0.25$; (negative) entropy: $0$-$1$; mutual information: $4-5$; (1 -) max.
prob: $0-0.5$), with deep purple signifying high uncertainty and white
signifying low uncertainty / high certainty.

Table 1: Best hyperparameters found on the half-moon dataset.

Model | Hyperparameter | Value
---|---|---
NN | hidden_sizes | $[25,25,25]$
NN | dropout_rate | $0.014552$
NN | lr | $0.000538$
MCDropout | hidden_sizes | $[25,25,25,25]$
MCDropout | dropout_rate | $0.205046$
MCDropout | lr | $0.000526$

Table 2: Distributions or options that hyperparameters were sampled from
during the random hyperparameter search.

Hyperparameter | Description | Chosen from
---|---|---
hidden_sizes | Hidden layers | 1-5 layers of $15$, $20$, $25$
lr | Learning rate | $\mathcal{U}(\log(10^{-4}),\log(0.1))$
dropout_rate | Dropout rate | $\mathcal{U}(0,0.5)$

We can see in Figure 5 that maximum probability and predictive entropy behave
quite similarly, forming a tube-like region of high uncertainty along what
appear to be the decision boundary. In both cases, the region appears to be
sharper in the case of maximum probability (right column) and also more
defined after additional temperature scaling (bottom row). For all models and
metrics, we see that the gradient magnitude decreases and approaches zero away
from the training data (yellow / green plots), except for the cases discussed
in Section 6.

| Predictive Entropy | Maximum probability
---|---|---
NN |  |
|  |
PlattScalingNN |  |
|  |

Figure 5: Uncertainty measured by different metrics for single-instance models
(purple plots) and their gradient magnitude (yellow / green plots).

In the next figure, Figure 6, we observe the uncertainty surfaces for models
using multiple network instances. For the remaining models it is interesting
to see that class variance (left column) didn’t seem to produce significantly
different values across the feature space except for the anchored ensemble.
For predictive entropy (central column), we can see a similar behaviour
compared to the single-instances models. Interestingly, the “fuzziness” of the
high-uncertainty region increases with the ensemble and becomes increasing
large with its anchored variant. Nevertheless, regions with static levels of
certainty still exist in this case. For the mutual information plots (right
column), epistemic uncertainty is lowest around the training data, where the
model is best specified, which creates another tube-like region of high
confidence even where there is no training data, an effect that is reduced
with the neural ensemble and almost completely solved by the anchored
ensemble. For all metrics, we see a magnitude close to zero for the
uncertainty gradient away from the training data, except for the decision
boundaries, as discussed in Section 6.

| Class variance | Predictive Entropy | Mutual Information
---|---|---|---
MCDropout |  |  |
|  |
NNEnsemble |  |  |
|  |
AnchoredNNEnsemble |  |  |
|  |  |

Figure 6: Uncertainty measured by different metrics for multi-instance models
(purple plots) and the gradient of the uncertainty score w.r.t to the input
(yellow / green plot).