# Walk Extraction Strategies for Node Embeddings with RDF2Vec in Knowledge
Graphs

Gilles Vandewiele
IDLab
Ghent University – imec
Belgium
<EMAIL_ADDRESS>
&Bram Steenwinckel
IDLab
Ghent University – imec
Belgium
<EMAIL_ADDRESS>
&Pieter Bonte
IDLab
Ghent University – imec
Belgium
<EMAIL_ADDRESS>
&Michael Weyns
IDLab
Ghent University – imec
Belgium
<EMAIL_ADDRESS>
&Heiko Paulheim
Data and Web Science Group
University of Mannheim
Germany
<EMAIL_ADDRESS>
&Petar Ristoski
IBM Research Almaden
IBM
United States of America
<EMAIL_ADDRESS>
&Filip De Turck
IDLab
Ghent University – imec
Ghent, Belgium
<EMAIL_ADDRESS>
&Femke Ongenae
IDLab
Ghent University – imec
Ghent, Belgium
<EMAIL_ADDRESS>

###### Abstract

As KGs are symbolic constructs, specialized techniques have to be applied in
order to make them compatible with data mining techniques. RDF2Vec is an
unsupervised technique that can create task-agnostic numerical representations
of the nodes in a KG by extending successful language modelling techniques.
The original work proposed the Weisfeiler-Lehman (WL) kernel to improve the
quality of the representations. However, in this work, we show both formally
and empirically that the WL kernel does little to improve walk embeddings in
the context of a single KG. As an alternative to the WL kernel, we propose
five different strategies to extract information complementary to basic random
walks. We compare these walks on several benchmark datasets to show that the
_n-gram_ strategy performs best on average on node classification tasks and
that tuning the walk strategy can result in improved predictive performances.

_K_ eywords Knowledge graphs $\cdot$ Embeddings $\cdot$ Representation
Learning

##  1 Introduction

As a result of the recent data deluge, we are increasingly confronted with
more information than we can meaningfully make sense of. Above all, this
information is characterised by contextual heterogeneity: its origins are
semantically and syntactically diverse. Insights derived through traditional
data mining procedures will be constrained precisely because such procedures
fail to account for this staggering diversity. To deal with such a myriad of
contextual environments and backgrounds, the Semantic Web’s (SW) Linked Open
Data (LOD) initiative can be used to interlink various data sources and unite
them under a common queryable interface. The product of such a consolidation
effort is often called a Knowledge Graph (KG). In addition to unifying
information from various sources, KGs are able to enrich classical data
formats by explicitly encoding relations between different data points in the
form of edges.

Using KGs to enhance traditional data mining techniques with background
knowledge is a relatively recent endeavour [1]. Because KGs are symbolic
constructs, their compatibility with such techniques is rather limited. In
fact, data mining techniques usually require inputs to be presented as
numerical feature vectors, and are therefore unable to process background
knowledge directly. With this in mind, some of the earliest knowledge-enhanced
data mining approaches proceeded by extracting custom features from specific
and generic relations inside the graph [2]. While these approaches produce
human-interpretable variables, they have to be tailored to the task at hand
and therefore require extensive effort. As an alternative to feature-based
approaches, techniques can be applied to learn vector representations, called
embeddings, for each of the entities inside a graph based on a limited set of
global latent features [3, 4]. These techniques are task-agnostic, which
allows them to be used for different downstream tasks, such as predicting
missing links inside a graph or categorizing different nodes [5].

Natural language and graphs often share similarities. As an example,
frequencies of language symbols or graph structures both tend to approximate
Zipf’s law. Techniques such as DeepWalk [6] and Node2Vec [7] were among the
first to leverage these similarities, by extending successful language
modelling techniques, such as Word2Vec [8], to deal with graph-based data.
Their proposed techniques rely on the extraction of sequences of graph
vertices, which are then fed as sentences to language models. Similarly, work
on (deep) graph kernels also relies on language modelling to learn the latent
representations of graph substructures [9, 10, 11]. RDF2Vec is a technique
that builds on the progress made by these previous two types of techniques by
adapting random walks and the Weisfeiler-Lehman (WL) subtree kernel to
directed graphs with labelled edges, i.e. KGs [12].

In this work, we show that the WL kernel, while effective for measuring
similarities between nodes or when working with regular graphs, offers little
improvements in the context of a single KG with respect to walk embeddings. In
response to this observation, we propose various alternative walk strategies
for RDF data to improve upon basic random walks and compare them on different
benchmark datasets.

The remainder of this paper is structured as follows. In Section 2, background
information is provided on KGs, RDF2Vec, walk embeddings and the WL kernel.
Next, in Section 3, we provide a formal discussion of our claim with respect
to the feasibility of Weisfeiler-Lehman subtree RDF graph kernels. Following
this, Section 4 discusses a number of possible alternative walk strategies,
including pseudo-code listings for each algorithm. Section 5 then describes
the datasets used to evaluate these alternative strategies and lists the
corresponding results. These results are subsequently discussed in Section 6.
Finally, in Section 7 we conclude this work with a general reflection.

##  2 Background

###  2.1 Knowledge graphs

A KG is a multi-relational directed graph, $\mathbb{G}=(\mathbb{V},\
\mathbb{E},\ \ell)$, where $\mathbb{V}$ are the vertices in our graph,
$\mathbb{E}$ the edges or predicates and $\ell$ a labelling function that maps
each vertex or edge onto its corresponding label. It should further be noted
that we can identify three different types of vertices: (i) _entities_ , (ii)
_blank nodes_ , and (iii) _literals_. We can simplify further analysis by
applying a transformation to the knowledge graph which removes the multi-
relational aspect, as done by de Vries et al. [13]. This is done by
representing each (subject, predicate, object) triple from the original
knowledge graph by three labelled nodes and two unlabelled edges (subject
$\rightarrow$ predicate and predicate $\rightarrow$ object).

###  2.2 RDF2Vec

Machine learning algorithms cannot work directly with graph-based data, as
they require numerical vectors as input. RDF2Vec [12] is an unsupervised,
task-agnostic approach that solves this problem by first transforming the
information of the nodes in the graph into numerical data, which are called
latent representations or embeddings. The goal is to capture as much of the
semantics as possible in the numerical representation, i.e. entities that are
semantically related should be close to each other in the embedded space.
RDF2Vec builds on word embedding techniques, which have shown great success in
the domain of natural language processing. These word embedding techniques
take a corpus of sentences as input, and learn a latent representation for
each of the unique words within the corpus. Learning this latent
representation can be done, for example, by learning to predict a word based
on its context (continuous bag-of-words) or predicting the context based on a
target word (skip-gram) [14, 8].

###  2.3 (Random) walk embeddings

In the context of (knowledge) graphs, we can construct an input corpus by
extracting walks. A walk is a sequence of vertices that can be found in the
graph by traversing the directed links. We can notate a walk of length n as
follows:

$v_{0}\rightarrow v_{1}\rightarrow\ldots\rightarrow v_{n-1}$ (1)

We can then use the graph labelling function to create a sentence:

$\ell(v_{0})\rightarrow\ell(v_{1})\rightarrow\ldots\rightarrow\ell(v_{n-1})$
(2)

It should be noted that, due to the previously discussed transformation of our
KG, nodes with an even index in the walk correspond to entities of the
original knowledge graph, while nodes with an odd index correspond to
predicates.

The most straightforward strategy to extract walks is by doing a breadth-first
traversal of the graph starting from the nodes of interest. Since the total
number of walks that can be extracted grows exponentially in function of the
depth, sampling can be applied after each iteration of breadth-first
traversal. This sampling can either be guided by some metric, resulting in a
collection of biased walks [15], or can be performed at random, which results
in _random_ walks.

###  2.4 Weisfeiler-Lehman kernel

The WL kernel was proposed as an extension to the labelling function. The WL
kernel is an algorithm to test whether two graphs were isomorphic in
polynomial time [16]. The intuition behind the algorithm was to assign new
labels to each of the nodes, where each of the newly assigned labels captured
the information of an entire subgraph up to a certain depth. This algorithm
was later adapted to serve as a kernel, or similarity measure, between graphs
[17, 18], by counting the number of WL labels two graphs had in common. The WL
relabelling for a node $v$ is performed by recursively hashing the
concatenation of the label of an entity and the (sorted) labels the nodes of
its neighbours:

$\displaystyle\textsc{wl}_{0}(v)=$ $\displaystyle\ \ell(v)$
$\displaystyle\textsc{wl}_{k}(v)=$ $\displaystyle\
\textsc{hash}(\textsc{wl}_{k-1}(v)\oplus\textsc{sort}(\\{\textsc{wl}_{k-1}(v_{n})\
|\ v_{n}\in\bm{\mathcal{N}}(v)\\}))$ (3)

with $k\geq 1$, $\textsc{wl}_{k}(v)$ the corresponding wl label of a node
after $k$ iterations, hash a hashing function, sort a sorting function,
$\oplus$ the string concatenation operator and $\bm{\mathcal{N}}(v)$ the
neighbourhood of $v$. We assume that the hashing function does not produce
collisions. This can easily be achieved by, for example, mapping each unique
label to an integer. The neighbourhood of a vertex $v$ is defined as the set
of vertices $v^{\prime}$ with an edge going to $v$:

$\bm{\mathcal{N}}(v)=\\{v^{\prime}\ |\ (v^{\prime},v)\in\mathbb{E}\\}$ (4)

##  3 Weisfeiler-Lehman kernel for Knowledge Graphs

Ristoski et al. proposed to use the wl kernel in order to relabel nodes as an
alternative to extracting random walks [12]. We will refer to this as the _WL_
strategy in the remainder of this paper. However, we argue that this _WL_
strategy provides no additional information with respect to entity
representations when extracting a fixed number of random walks from a
knowledge graph. We now formally demonstrate this claim on al three types of
vertices:

###  3.1 Entities

The _wl_ strategy brings little to no added value in comparison to random
walks, when applied to entities in a knowledge graph, due to the properties of
rdf data. Entities in rdf are represented by Uniform Resource Identifiers
(uri), which need to be unique111https://www.w3.org/DesignIssues/Axioms.html.
As such:

$\ell(x)=\ell(y)\iff x=y$ (5)

Due to this property, wl relabelling, when applied on rdf data, is nothing
more than a bijection from the hops in random walks to the hops in the walks
obtained through wl relabelling. This means that wl relabelling does not add
any useful additional information. When two wl labels are equal, their
underlying entities are always equal as well. We will now prove this formally.
First, from Eq. 2.4 we can deduce that when two wl labels of two nodes are
equal, then at least the labels of these nodes should be equal and they should
have the same neighbours222Proof omitted due to space restrictions, but as wl
is recursive, it can be proven through induction.. Formally this means that:

$\textsc{wl}_{k}(v_{j})=\textsc{wl}_{k}(v_{i})\iff\ell(v_{j})=\ell(v_{i})\wedge\bm{\mathcal{N}}(v_{j})=\bm{\mathcal{N}}(v_{i})$
(6)

#### Proof:

$\textsc{wl}_{k}(v_{j})=\textsc{wl}_{k}(v_{i})\iff v_{j}=v_{i}$

Step 1: $\textsc{wl}_{k}(v_{j})=\textsc{wl}_{k}(v_{i})\implies v_{j}=v_{i}$

$\displaystyle\textsc{wl}_{k}(v_{j})=\textsc{wl}_{k}(v_{i})$
$\displaystyle\implies\ell(v_{j})=\ell(v_{i})\wedge\bm{\mathcal{N}}(v_{j})=\bm{\mathcal{N}}(v_{i})$
(Eq. 6) $\displaystyle\implies\ell(v_{j})=\ell(v_{i})$ (Conjunction Elim.)
$\displaystyle\implies v_{j}=v_{i}$ (Eq. 5)
$\displaystyle\hfill\hbox{}\nobreak\hfill\square$

Step 2: $v_{j}=v_{i}\implies\textsc{wl}_{k}(v_{j})=\textsc{wl}_{k}(v_{i})$

$\displaystyle v_{j}=v_{i}$ $\displaystyle\implies\ell(v_{j})=\ell(v_{i})$
(Eq. 5)
$\displaystyle\implies\ell(v_{j})=\ell(v_{i})\wedge\bm{\mathcal{N}}(v_{j})=\bm{\mathcal{N}}(v_{i})$
(Eq. 4 and $v_{j}=v_{i}$)
$\displaystyle\implies\textsc{wl}_{k}(v_{j})=\textsc{wl}_{k}(v_{i})$ (Eq. 6)
$\displaystyle\hfill\hbox{}\nobreak\hfill\square$

###  3.2 Blank nodes and literals

In contrast to _entities_ , Eq. 5 does not hold for blank nodes and literals.
This implies that multiple nodes could have the same original label but have
different WL labels (one-to-many mapping). However, the added value of WL is
limited even in these cases due to the fact that blank nodes rarely have the
exact same neighbourhoods and because literals only have one incoming edge and
no outgoing edges. Moreover, due to the fact that RDF2Vec treats each hop in
the walk as categorical data, RDF2Vec does not handle literals well.

##  4 Custom walk extraction strategies

Based on the observation probably discussed, we now identify two types of
strategies to construct a corpus of walks:

Type 1 - Extraction:

strategies that define how walks for each of the entities are extracted. The
_random_ walk strategy is an example of such a strategy, where breadth-first
traversal is applied to extract walks.

Type 2 - Transformation:

strategies that transform walks extracted by a Type 1 strategy. The _WL_
strategy is an example of this type. In order for such a strategy to provide
information complementary to the originally provided walks, it must define a
_one-to-many_ or _many-to-one_ mapping from the original labels to the new
labels.

We now propose five different strategies complementary to the _random_
strategy. One of these strategies can be classified as being of Type 1 while
the other four are of Type 2.

###  4.1 Community hops

As opposed to iteratively extending the walk with neighbours of a vertex, we
could allow with a certain probability for teleportation to a node that has
properties similar to a certain neighbor [19]. In order to group nodes with
similar properties together, unsupervised community detection can be applied
[20]. In this work, we opted to use the Louvain method [21] due to its
excellent trade-off between speed and clustering quality. The idea of
introducing community hops is to capture implicit relations between nodes that
are not explicitly modelled in the KG, and to allow for including related
pieces of knowledge in the walks which are otherwise out of reach. We provide
pseudo-code for this strategy in Algorithm 1. This strategy is of Type 1. We
will refer to this strategy as _community_.

# List of communities and dictionary {vertex: community}

com, com_map = com_detection($\mathbb{G}$)

walks = { (v,) }

for _$d$ in range($depth$)_:

new = set()

for _walk in walks_:

for _n in get_neighbours($\mathbb{G}$, v)_:

# Sample neighbourhood

if _random() $<$ p_:

new.add(walk + (n,))

# Hop to community

if _random() $<$ hop_prob_:

c_n = com[com_map[n]]

hop = choice(c_n)

new.add(walk + (hop,))

walks = new

return walks

Alg. 1 community_walk($\mathbb{G}$, v, depth, p, hop_prob)

###  4.2 Anonymous walks

The random walks discussed in the previous section can be anonymized, which
transforms label information into positional information. More formally, a
walk $w=v_{0}\rightarrow v_{1}\rightarrow\ldots\rightarrow v_{n}$, is
transformed into $f(v_{0})\rightarrow f(v_{1})\rightarrow\ldots\rightarrow
f(v_{n})$ with $f(v_{i})=\min(\\{i\ |\ w[i]\ =\ v_{i}\\})$, which corresponds
to the first index where $v_{i}$ can be found in the walk $w$ [22]. The notion
behind anonmyous walks is that local graph structures often bear enough
information for encoding and reconstructing a graph, even when ignoring the
node labels, i.e., the mere topology surrounding a node is often sufficient
for identifying that node. Ignoring the labels, on the other hand, allows for
a computationally efficient generation of the walks. We present pseudo-code
for this transformation in Algorithm 2. This strategy is of Type 2. We will
refer to this strategy as _anonymous_.

anon_walks = [ ]

for _walk in walks_:

new = [ walk[0] ]

for _hop in walk[1:]_:

new.append(walk.index(hop))

anon_walks.append(new)

return anon_walks

Alg. 2 anonymize(walks)

###  4.3 Walkets

Walks can be transformed into walklets, which are walks of length two
consisting of the root of the original walk and one of the hops. Provided a
walk $w=v_{0}\rightarrow v_{1}\rightarrow\ldots\rightarrow v_{n}$, we can
construct sets of walklets $\\{(v_{0},v_{i})\ |\ 1\leq i\leq n\\}$ [23]. While
standard RDF2Vec does not consider the distance between two nodes in a walk,
walklets are explicitly created for different scales. Hence, they allow for
such a distinction between a direct neighbor and a node which is further away.
Pseudocode for this approach is provided in Algorithm 3. This strategy is of
Type 2. We will refer to this strategy as _walklet_.

walklets = set()

for _walk in walks_:

for _i in range(1, $|$walk$|$)_:

walklets.add((walk[0], walk[i]))

return walklets

Alg. 3 walklets(walks)

###  4.4 Hierarchical random walk (HALK)

The frequency of entities in a knowledge graph often follows a long-tailed
distribution, similar to natural language. Entities rarely occurring often
carry little information, and increase the number of hops between the root and
potentially more interesting entities. As such, the removal of rare entities
from the random walks can increase the quality of the generated embeddings
while decreasing the memory usage [24]. Pseudo-code for this strategy is
provided in Algorithm 4. This strategy is of Type 2. We will refer to this
strategy as _HALK_.

# Count nr. of walks a hop occurs

counts = { }

for _i in range($|$walk$|$)_:

for _hop in walks[i]_:

if _hop not in frequencies_:

counts[hop] = {i}

else:

counts[hop].add(i)

# Skip rare hops

halk_walks = [ ]

for _thresh in thresholds_ :

for _walk in walks_ :

new = [ walk[0] ]

for _hop in walk[1:]_:

if _$\frac{|\textrm{counts[hop]}|}{|\textrm{walks}|}\geq$ thresh_:

new.append(hop)

halk_walks.append(new)

return halk_walks

Alg. 4 halk(walks, thresholds)

###  4.5 N-Gram walks

Another approach that defines a one-to-many mapping is relabelling n-grams in
the random walks. The intuition behind this is that the predecessors of a node
that two different walks have in common can be different. Additionally, we can
inject wildcards into the walk before relabelling n-grams [25]. The injection
of wildcards allows subsequences with small differences to be mapped onto the
same label. Pseudo-code for this strategy is provided in Algorithm 5. This
strategy is of Type 2. We will refer to this strategy as _n-gram_.

# Introduce wildcards in the walks

extended_walks = walks

for _walk in walks_:

idx = range(1, $|$walk$|$)

combs = combinations(idx, n_wild)

for _comb in combs_:

new = walk

for _i in comb_:

new[i] = ‘*’

extended_walks.append(new)

# Relabel ngrams in the walk

ngram_walks = [ ]

map = { }

for _walk in extended_walks_:

new = walk[:n]

for _i in range(n, $|$walk$|+1$)_:

ngram = walk[i-n:i]

if _ngram not in map_:

map[ngram] = $|$map$|$

new.append(map[ngram])

ngram_walks.append(new)

return ngram_walks

Alg. 5 ngram(walks, n, n_wild)

###  4.6 Example

In order to further clarify each of the proposed strategies, we provide an
example in Figure 1.

Figure 1: An example of each of our proposed strategies. We extract walks with
the _random_ and _community_ strategy of exactly depth 2 from nodes “A" and
“F". For other strategies, we transform the walks extracted by the _random_
strategy. Nodes “C" and “H" belong to the same community.

##  5 Results

To evaluate the impact of custom walking strategies, we measure the predictive
performance on different datasets and various tasks.

###  5.1 Datasets

Three different types of datasets are used, in order to ensure enough
variation in our evaluation. Moreover, these datasets are commonly used in
(knowledge) graph-based machine learning studies.

####  5.1.1 Node classification benchmark datasets

We will be using four benchmark data sets, each describing knowledge graphs,
that serve as benchmarks for node classification and are available from a
public repository set up by Ristoski et al. [26]. The names of these benchmark
datasets are AIFB, MUTAG, BGS and AM. For each of these data sets, we remove
triples with specific predicates that would leak the target from our knowledge
graph, as provided by the original authors. Moreover, a predefined split into
train and test set, with the corresponding ground truth, is provided by the
authors, which we used in our experiments.

####  5.1.2 Citation networks

We converted three citation networks [27], which describe scientific papers,
to knowledge graphs. The three citation networks used are CORA, CITESEER and
PUBMED. Each paper is represented by a bag-of-word or tf-idf representation of
their content and a list of citations to other papers in the network. A fixed
train/test split is provided for each of the datasets and the associated task
is to categorize each of the papers into the correct research domain, which
can be seen as a node classification task. For each paper $p$, we obtained the
words $w$ from the bag-of-words or tf-idf vector with a value greater than 0
and add the following triples to our KG: $\\{(p,\ hasWord,\ w)\ |\
f(p,w)>0\\}$, with $f(p,w)$ a function that retrieves the bag-of-word or tf-
idf value of word $w$ for paper $p$. Moreover, for each paper $p^{\prime}$
cited by $p$ we add the following triple: $(p,\ cites,\ p^{\prime})$.

####  5.1.3 DBpedia

We use the English version of the 2016-10 DBpedia dataset [28], which contains
4,356,314 entities and 52,689,448 triples in total. In our evaluation, we only
consider object properties, and ignore datatype properties and literals. We
use the obtained embeddings in multiple different downstream tasks: 5
different classification tasks (AAUP, Cities, Forbes, Albums and Movies),
document similarity and entity relatedness. For more details on each of these
tasks, we refer the reader through to the original RDF2Vec paper by Ristoski
et al. [12].

###  5.2 Setup

For each of the entities in all of the datasets, walks of depth $4$ are
exhaustively extracted. A depth of $4$ is chosen as it results in the best
predictive performances on average for all strategies and datasets. Only for
the entities of DBpedia, the maximum number of walks per entity is limited to
500. These walks are then provided to a Word2Vec model to create
$500$-dimensional embeddings. The hyper-parameters of the Word2Vec model are
the same for all experiments in this study. Skip-Gram is used, the window size
is equal to $5$ and the maximum number of iterations is equal to $10$ with
negative sampling set to $25$. These configurations are identical to the
original RDF2Vec study. The embeddings are learned, in an unsupervised manner,
for both the train and test set. For node classification tasks, embeddings are
fed to a Support Vector Machine (SVM) classifier with Radial Basis Function
(RBF) kernel. The regularization strength of the SVM is tuned to be one of
$\\{0.001,0.01,0.1,1.0,10.0,100.0,1000.0\\}$. For tasks other than node
classification, an evaluation framework is used [29]. For document similarity,
we measure the Pearson’s linear correlation coefficient, Spearman’s rank
correlation and their harmonic mean. For entity relatedness, we measure the
Kendall’s rank correlation coefficient. For the benchmark datasets and
citation networks, a pre-defined train/test split is used and experiments are
repeated 5 times in order to report a corresponding standard deviation. For
the tasks involving DBpedia data, 10-fold cross-validation is used and
experiments are only repeated once for timing reasons. Moreover, the community
strategy was excluded from the DBpedia experiments, as it cannot be
efficiently performed on large knowledge graphs.

For each of the walking strategies, we tune the following hyper-parameters
using either a provided validation set or by using cross-validation on the
train set:

  * •

The _random_ , _anonymous_ and _walklet_ strategies are hyper-parameter-free.

  * •

For the _n-gram_ walker, we tune $n\in[1,2,3]$ and the number of introduced
wildcards to be either 0 or 1.

  * •

For the _community_ strategy, we set the resolution of the Louvain algorithm
to 1.0 [30] and the probability to teleport to a node from the community to
10%.

  * •

For the _WL_ strategy, we use the original algorithm used by Ristoski et al.
[12]. We set the number of iterations of the Weisfeiler-Lehman kernel to 4 and
extract walks of fixed depth for each of the iterations, including zero. This
causes the WL walker to extract 5 times as many walks as the random walker,
which causes the results to differ from those of the random walk strategy.

  * •

For the _HALK_ strategy, we extract sets of walks using different thresholds:
$[0.0,0.1,0.05,0.01,0.005,0.001,0.0005,0.0001]$.

###  5.3 Evaluation results

The results for the various classification tasks are provided in Table 1. The
results for the document similarity and entity relatedness task are provided
in Table 2.

| Random | WL | Walkets | Anonymous | HALK | N-Gram | Community
---|---|---|---|---|---|---|---
AIFB | 86.11 $\pm$ 2.48 | 91.67 $\pm$ 0.00 | 63.89 $\pm$ 0.00 | 41.67 $\pm$ 0.00 | 86.11 $\pm$ 0.00 | 88.33 $\pm$ 1.11 | 88.89 $\pm$ 1.76
MUTAG | 76.76 $\pm$ 0.59 | 75.00 $\pm$ 2.46 | 72.06 $\pm$ 0.00 | 66.18 $\pm$ 0.00 | 75.00 $\pm$ 0.00 | 77.65 $\pm$ 2.85 | 74.71 $\pm$ 3.99
BGS | 79.31 $\pm$ 0.00 | 80.69 $\pm$ 6.40 | 65.52 $\pm$ 0.00 | 65.52 $\pm$ 0.00 | 80.00 $\pm$ 4.57 | 83.45 $\pm$ 4.02 | 84.14 $\pm$ 3.52
AM | 75.56 $\pm$ 2.70 | 82.53 $\pm$ 1.68 | 47.47 $\pm$ 0.00 | 34.85 $\pm$ 0.00 | 80.10 $\pm$ 0.88 | 84.44 $\pm$ 2.22 | 73.94 $\pm$ 2.70
CORA | 77.20 $\pm$ 0.00 | 74.32 $\pm$ 1.56 | 58.20 $\pm$ 0.00 | 14.30 $\pm$ 0.00 | 76.62 $\pm$ 0.36 | 76.46 $\pm$ 0.78 | 67.92 $\pm$ 1.22
CITESEER | 64.68 $\pm$ 1.58 | 64.02 $\pm$ 1.46 | 38.40 $\pm$ 0.00 | 16.00 $\pm$ 0.00 | 66.90 $\pm$ 0.00 | 65.38 $\pm$ 1.22 | 58.66 $\pm$ 0.50
PUBMED | 75.66 $\pm$ 1.36 | 73.70 $\pm$ 2.87 | 68.30 $\pm$ 0.00 | 24.20 $\pm$ 0.00 | 75.56 $\pm$ 0.08 | 78.48 $\pm$ 0.35 | 54.64 $\pm$ 2.40
DBP: AAUP | 67.94 | 69.88 | 69.27 | 54.73 | 60.08 | 66.96 | /
DBP: Cities | 79.07 | 79.12 | 79.08 | 55.34 | 73.34 | 79.79 | /
DBP: Forbes | 63.73 | 64.60 | 62.28 | 55.16 | 60.98 | 63.65 | /
DBP: Albums | 75.24 | 79.31 | 79.99 | 54.45 | 66.89 | 79.38 | /
DBP: Movies | 80.06 | 80.48 | 78.89 | 59.40 | 68.11 | 78.84 | /
Table 1: The accuracy scores obtained by various techniques on different
datasets. Table 2: Document similarity and entity relatedness results

##  6 Discussion

Based on the provided results, several observations can be made. The _random_
and _WL_ are used in the original RDF2Vec study [12]. As such, the results
reported in this study can be seen as a reproduction of those results. It is
important to note here that the only reason why the results obtained by the
_WL_ and _random_ strategy differ in this and the original work, is because
walks are extracted after each iteration of the _WL_ relabelling algorithm.
This results in $k$ times as many walks, with $k$ the number of iterations in
the relabelling algorithm. If walks from only one of the iterations would be
used, the results would be identical to those of the _random_ strategy.
Nevertheless, this simple trick does often result in increased predictive
performances, as was empirically shown by Ristoski et al. [12]. We hypothesize
that this is due to more weight being given, internally in Word2Vec, to the
entities where many walks can be extracted from. While the original _WL_ and
_random_ strategies result in very strong performances, especially on the
downstream tasks of DBpedia they are often outperformed by custom strategies
proposed in this work.

While the results indicate that there is no one-size-fits-all walking strategy
for all tasks and datasets, it seems that the _n-gram_ strategy results in the
best predictive performances on average for node classification tasks. The
average rank of the _n-gram_ strategy on the four node classification and
three citation network datasets, using all seven techniques, is equal to
$1.86$, followed by $3$ of the _HALK_ strategy and $3.07$ of both the _random_
and _WL_ strategy. An average rank of $1$ would mean that the technique
outperforms all others on each dataset. The average rank of the _n-gram_
strategy on all the node classification tasks, excluding the _community_
strategy, is equal to $2.08$, followed by $2.375$, $2.875$ and $3.67$ by
_random_ , _WL_ and _HALK_ respectively.

The performance of the _community_ strategy varies a lot. On some datasets,
such as AIFB and BGS, its performance is among the best while it performs a
lot worse than _random_ walks on others. This is due to the fact that the
quality of the walks is highly dependent on the quality of the community
detection. If the groups of nodes, clustered by the community detection, do
not align well with the downstream task, the performance worsens.

Further, it is important to note that the various strategies are complementary
to each other. Even when equal accuracies are achieved, the confusion matrices
can differ. Therefore, the combination of several strategies can further
increase the predictive performance. There are different points within the
pipeline where the combination of strategies can take place: (i) at corpus
level before feeding the walks to Word2Vec, (ii) at embedding level, by
combining the different produced embeddings, and (iii) at prediction level, by
aggregating the predictions of the different models. We consider this
combination of strategies to be an interesting future step. While the
predictive performances of some of the strategies proposed in this work, such
as the _anonymous_ and _walklet_ strategy, do often not come near that of the
_random_ strategy, a combination of these strategies could improve
performance.

Some limitations of this study can be identified. Firstly, no comparisons with
other techniques are performed. Here, it is important to note that RDF2Vec is
an unsupervised and task-agnostic technique. As such, comparisons with
supervised techniques, specifically trained for certain tasks, such as
Relational Graph Convolutional Networks [31] are rather unfair. In the
original work of Ristoski et al. [12] it was already shown that RDF2Vec
outperforms other unsupervised variants such as TransE, TransH and TransR.
This was independently confirmed by Zouaq and Martel, who additionally showed
that RDF2Vec outperformed ComplEx and DistMult as well [32]. Second, a fixed
depth and fixed hyper-parameters for the Word2Vec model were used within this
study. While tuning these hyper-parameters could possibly result in increased
predictive performances, it should be noted that the number of hyper-
parameters and the range of a Word2Vec model are very large and that the time
required to generate the embedding is significant. We therefore opted to fix
the hyper-parameters on sensibly chosen values, as was done by Ristoski et al.

##  7 Conclusion

In this work, five walk strategies that can serve as an alternative to the
basic random walk approach are proposed as a response to the observation that
the WL kernel offers little improvement in the context of a single KG. Results
indicate that there is no one-size-fits-all strategy for all datasets and
tasks, and that tuning the strategy to a specific objective, as opposed to
simply using the random walk approach, can result in increased predictive
performances.

There are several future directions that we deem interesting. First, it would
be interesting to study the impact on the performance when the strategies are
combined with different biased walk strategies and embedding algorithms that
differ from the Word2Vec model used within this work. Second, all of the
strategies proposed in this work are unsupervised, but supervised approaches
could be evaluated that sacrifice generality to gain predictive performance.
Third, as already mentioned, the walking strategies are complementary to each
other and combining them could potentially result in increased predictive
performances. Therefore an evaluation of different combination strategies
would be an interesting addition.

## Reproducibility and code availability

We provide a Python implementation of RDF2Vec with can be combined with any of
the walking strategies discussed in this
work333github.com/IBCNServices/pyRDF2Vec. Moreover, we provide all code
required to reproduce the reported
results444github.com/GillesVandewiele/WalkExperiments.

## Acknowledgements

GV (1S31417N) and BS (1SA0219N) are funded by a strategic base research grant
of the Fund for Scientific Research Flanders (fwo).

## References

  * [1] Xander Wilcke, Peter Bloem, and Victor De Boer.  The Knowledge Graph as the Default Data Model for Machine Learning.  Data Science, 1:1–0, 2017.
  * [2] Petar Ristoski and Heiko Paulheim.  A comparison of propositionalization strategies for creating features from linked open data.  Linked Data for Knowledge Discovery, 6, 2014.
  * [3] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich.  A review of relational machine learning for knowledge graphs.  Proceedings of the IEEE, 104(1):11–33, 2015.
  * [4] William L Hamilton, Rex Ying, and Jure Leskovec.  Representation Learning on Graphs: Methods and Applications.  Preprint of article to appear in the IEEE Data Engineering Bulletin, 2017.
  * [5] Petar Ristoski and Heiko Paulheim.  Semantic web in data mining and knowledge discovery: A comprehensive survey.  Journal of Web Semantics, 36:1–22, 2016.
  * [6] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710, 2014.
  * [7] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016.
  * [8] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In Advances in neural information processing systems, pages 3111–3119, 2013.
  * [9] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt.  Graph kernels.  Journal of Machine Learning Research, 11(Apr):1201–1242, 2010.
  * [10] Pinar Yanardag and SVN Vishwanathan.  Deep graph kernels.  In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365–1374, 2015.
  * [11] Nils M Kriege, Fredrik D Johansson, and Christopher Morris.  A survey on graph kernels.  Applied Network Science, 5(1):1–42, 2020.
  * [12] Petar Ristoski, Jessica Rosati, Tommaso Di Noia, Renato De Leone, and Heiko Paulheim.  Rdf2vec: Rdf graph embeddings and their applications.  Semantic Web, 10(4):721–752, 2019.
  * [13] Gerben Klaas Dirk de Vries and Steven de Rooij.  Substructure counting graph kernels for machine learning from rdf data.  Web Semantics: Science, Services and Agents on the World Wide Web, 35:71–84, 2015.
  * [14] Yoav Goldberg and Omer Levy.  word2vec explained: deriving mikolov et al.’s negative-sampling word-embedding method.  arXiv preprint arXiv:1402.3722, 2014.
  * [15] Michael Cochez, Petar Ristoski, Simone Paolo Ponzetto, and Heiko Paulheim.  Biased graph walks for rdf graph embeddings.  In Proceedings of the 7th International Conference on Web Intelligence, Mining and Semantics, pages 1–12, 2017.
  * [16] Boris Weisfeiler and Andrei A Lehman.  A reduction of a graph to a canonical form and an algebra arising during this reduction.  Nauchno-Technicheskaya Informatsia, 2(9):12–16, 1968.
  * [17] Gerben KD de Vries.  A fast approximation of the weisfeiler-lehman graph kernel for rdf data.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 606–621. Springer, 2013.
  * [18] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt.  Weisfeiler-lehman graph kernels.  Journal of Machine Learning Research, 12(Sep):2539–2561, 2011.
  * [19] Mohammad Mehdi Keikha, Maseud Rahgozar, and Masoud Asadpour.  Community aware random walk for network embedding.  Knowledge-Based Systems, 148:47–54, 2018.
  * [20] Santo Fortunato.  Community detection in graphs.  Physics reports, 486(3-5):75–174, 2010.
  * [21] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  Journal of statistical mechanics: theory and experiment, 2008(10):P10008, 2008.
  * [22] Sergey Ivanov and Evgeny Burnaev.  Anonymous walk embeddings.  arXiv preprint arXiv:1805.11921, 2018.
  * [23] Bryan Perozzi, Vivek Kulkarni, Haochen Chen, and Steven Skiena.  Don’t walk, skip! online learning of multi-scale network embeddings.  In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, pages 258–265, 2017.
  * [24] Jörg Schlötterer, Martin Wehking, Fatemeh Salehi Rizi, and Michael Granitzer.  Investigating extensions to random walk based graph embedding.  In 2019 IEEE International Conference on Cognitive Computing (ICCC), pages 81–89. IEEE, 2019.
  * [25] Gilles Vandewiele, Bram Steenwinckel, Femke Ongenae, and Filip De Turck.  Inducing a decision tree with discriminative paths to classify entities in a knowledge graph.  In SEPDA2019, the 4th International Workshop on Semantics-Powered Data Mining and Analytics, pages 1–6, 2019.
  * [26] Petar Ristoski, Gerben Klaas Dirk De Vries, and Heiko Paulheim.  A collection of benchmark datasets for systematic evaluations of machine learning on the semantic web.  In International Semantic Web Conference, pages 186–194. Springer, 2016.
  * [27] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  AI magazine, 29(3):93–93, 2008.
  * [28] Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick Van Kleef, Sören Auer, et al.  Dbpedia–a large-scale, multilingual knowledge base extracted from wikipedia.  Semantic Web, 6(2):167–195, 2015.
  * [29] Maria Angela Pellegrino, Abdulrahman Altabb, Martina Garofalo, Petar Ristoski, and Michael Cochez.  Geval: a modular and extensible evaluation framework for graph embedding techniques.  In European Semantic Web Conference. Springer, 2020.
  * [30] Renaud Lambiotte, J-C Delvenne, and Mauricio Barahona.  Laplacian dynamics and multiscale modular structure in networks.  arXiv preprint arXiv:0812.1770, 2008.
  * [31] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling.  Modeling relational data with graph convolutional networks.  In European Semantic Web Conference, pages 593–607. Springer, 2018\.
  * [32] Amal Zouaq and Felix Martel.  What is the schema of your knowledge graph? leveraging knowledge graph embeddings and clustering for expressive taxonomy learning.  In Proceedings of The International Workshop on Semantic Big Data, pages 1–6, 2020.


# A Comparison of Uncertainty Estimation Approaches in Deep Learning
Components for Autonomous Vehicle Applications

Fabio Arnez1 Huascar Espinoza1 Ansgar Radermacher1&François Terrier1
1CEA LIST, Gif-sur-Yvette, France
{fabio.arnez, huascar.espinoza, ansgar.radermacher<EMAIL_ADDRESS>
###### Abstract

A key factor for ensuring safety in Autonomous Vehicles (AVs) is to avoid any
abnormal behaviors under undesirable and unpredicted circumstances. As AVs
increasingly rely on Deep Neural Networks (DNNs) to perform safety-critical
tasks, different methods for uncertainty quantification have recently been
proposed to measure the inevitable source of errors in data and models.
However, uncertainty quantification in DNNs is still a challenging task. These
methods require a higher computational load, a higher memory footprint, and
introduce extra latency, which can be prohibitive in safety-critical
applications. In this paper, we provide a brief and comparative survey of
methods for uncertainty quantification in DNNs along with existing metrics to
evaluate uncertainty predictions. We are particularly interested in
understanding the advantages and downsides of each method for specific AV
tasks and types of uncertainty sources.

Copyright © 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).

##  1 Introduction

In the last decade, Deep Neural Networks (DNNs) have witnessed great advances
in real-world applications like Autonomous Vehicles (AVs) to perform complex
tasks such as object detection and tracking or vehicle control. Despite
substantial performance improvements introduced by DNNs, they still have
significant safety shortcomings due to their complexity, opacity and lack of
interpretability McAllister et al. (2017). In particular, DNNs are brittle to
operational domain shift and even small data corruption or perturbations
Kuutti et al. (2020). This impedes ensuring the reliability of the DNNs
models, which is a precondition for safety-critical systems to ensure
compliance with automotive industry safety standards and avoid jeopardizing
human lives.

A concrete safety problem is to detect abnormal situations under uncertain
environment conditions and DNN-specific unpredictability. These situations are
difficult to analyze during system development phases, in a way that they can
be properly mitigated at a real-time scale. Indeed, although a DNN model
achieves great performance in a validation set from its operation environment,
it is currently impossible to test and provide the same performance guarantees
in all the possible environment configurations the system could encounter in
the real world Kuutti et al. (2020). A common practice to overcome this
problem is to use runtime monitoring of DNN components, so that safety can be
ensured even if the component was not fully validated at design time Henne et
al. (2020); Koopman et al. (2019). A central aspect to enable DNN monitoring
is to provide a runtime treatment of uncertainties associated with DNN’s
predictions McAllister et al. (2017); Koopman et al. (2019).

In this paper, we review common uncertainty estimation methods for DNNs and
compare their performance and benefits for different AV tasks. These methods
offer a potential solution for runtime DNN confidence prediction and detection
of Out-of-Distribution (OOD) samples, since prediction probability scores in
DNNs do not provide a true representation of uncertainty Mohseni et al.
(2019). However, these methods still demand a high computational load,
incorporate extra latency, and require a larger memory footprint. We compare
these factors since they can represent a major impediment in safety-critical
applications with tight time constraints and limited computation hardware. We
also briefly focus on surveying uncertainty metrics that evaluate the
performance of quantification methods, as another critical factor to ensure
safety in AV systems.

The remainder of the paper is structured as follows. Section 2 describes the
sources of uncertainty in deep learning for AVs. Section 3 presents a
comparison of recent works in AV tasks that include uncertainty estimation
methods for DNNs. It provides a brief review of common uncertainty estimation
methods in deep learning as well as metrics for predictive uncertainty
evaluation in classification and regression tasks. Section 4 discusses the
open challenges and possible directions for future work.

##  2 Background

###  2.1 Sources of Uncertainty in Deep Learning for Autonomous Vehicles

Autonomous vehicles have to deal with dynamic, non-stationary and highly
unpredictable operational environments. Taking into account all the details
from the operational environment at design time is an intractable task.
Instead, the operational environment is constrained in a way that it considers
only a subset of all possible situations that the system can encounter in
operation. This process is known as Operational Design Domain (ODD) adoption
Koopman and Fratrik (2019), and safety requirements are built on the top of
the ODD specification.

Given the constrained operational environment within system ODD, ensuring
safety in an AV requires the identification of unfamiliar contexts by modeling
AV’s uncertainty McAllister et al. (2017). However, there are many factors,
not only related to the environment, that affect the system performance by
introducing some degree of uncertainty. Czarnecki and Salay (2018) identify a
set of factors that contribute to uncertainty in the perception function in an
AV, and in this manner affect its performance. From this set, we take special
attention to sensor properties, model uncertainty, situation and scenario
coverage, and operational domain uncertainty factors. In the context of DNNs,
the first two factors can be modeled by using uncertainty estimation methods,
while the last two correspond to some degree of dataset shift (i.e. breaking
the independent and identically distributed assumption between training and
testing data.) and Out-of-Distribution (OOD) samples Quionero-Candela et al.
(2009); Mohseni et al. (2019).

Sensor properties like range, resolution, noise characteristics, and
calibration can influence the amount of information in the samples delivered
to a machine learning model during training or testing. In consequence, the
effect of these properties are captured as noise and ambiguities inherent to
the obtained samples. This type of noise in the data is known as Aleatoric
uncertainty, and represents the incapability of completely sensing all the
details of the environment Kendall and Gal (2017); Lee et al. (2019b);
Gustafsson et al. (2019). Aleatoric uncertainty can be further further
classified into homoscedastic uncertainty (uncertainty that remains constant
for different samples), and heteroscedastic uncertainty (uncertainty that can
vary between samples).

Model uncertainty is often referred to as Epistemic uncertainty, and accounts
for uncertainty in the model parameters. This type of uncertainty captures the
ignorance of the model as a consequence of a dataset that does not represent
the ODD well, or that is not sufficiently large Kendall and Gal (2017); Lee et
al. (2019b). Epistemic uncertainty is expected to increase in unknown
situations (e.g. different environment ODD conditions such as weather or
lightning), and can be explained away by incorporating more data.

Situation and scenario coverage is related to the degree in which situations
and scenarios from an ODD are reflected in training and operation stages;
while operational domain uncertainty refers to a discrepancy between ODD
situations and scenarios present at training and those encountered at
operation (e.g. scenarios from two different ODDs) Czarnecki and Salay (2018).
In both cases, uncertainty can be reduced by incorporating more data, or by
adjusting the ODD specification. However, it is extremely important to detect
and discover OOD samples (i.e. outliers), especially those that have not been
seen before, since those can lead to highly confident predictions that are
wrong, i.e., the unknown-unknowns Bansal and Weld (2018).

In a similar fashion as the cases presented before, automotive industry
standard ISO/PAS 21448 or SOTIF (Safety Of The Intended Functionality) ISO
(2019), provides a process to identify unknown and potentially unsafe
scenarios to minimize the risk by recognizing the performance limitations from
sensors, algorithms, or user misuse. Unsafe scenarios can be further
classified into unsafe-known (e.g out of ODD samples) or unsafe-unknown (e.g.
OOD samples). Once an unknown-unsafe scenario or situation is identified, it
becomes a known-unsafe scenario that can be mitigated at design time Rau et
al. ; Mohseni et al. (2019).

###  2.2 Uncertainty Estimation Methods for DNNs

In recent years, many probabilistic deep learning methods have been proposed
to obtain an uncertainty measure from an approximation to the (highly multi-
modal) predictive distribution, as well as methods for calibrating the outputs
of DNNs. In general, there are two approaches for DNN predictive uncertainty
calculation: sampling-based and sampling-free methods. Sampling-based methods
rely on taking multiple predictive samples based on the same input to get the
estimator that will be associated with uncertainty. Sampling-free methods
require one single predictive output. These methods are further discussed in
Section 3.

####  2.2.1 Neural Network Calibration

Confidence calibration represents the degree to which a model’s predicted
probability estimates the true correctness likelihood Guo et al. (2017). Under
ideal circumstances, we expect that the normalized outputs from a DNN (i.e
softmax outputs) correspond to the true correctness likelihood Guo et al.
(2017). From a frequentist perspective, this can be viewed as a discrepancy
measure between local confidence (or uncertainty) predictions and the expected
performance in the long-run Hubschneider et al. (2019); Lakshminarayanan et
al. (2017). For example, we expect that a class predicted with probability $p$
is correct $p$% of the time, i.e. from 100 samples predicted with confidence
0.9, we expect 90 correct predictions. DDNs can be calibrated by using
Temperature Scaling, a simple post-processing technique Guo et al. (2017), or
more recently, Dirichelt calibration Kull et al. (2019). For a regression
setting, Kuleshov et al. (2018); Hubschneider et al. (2019) formalize the
calibration notion for continuous variables, in which a $p$% confidence
interval should contain the true outcome $p$% of the time.

Despite the improvements achieved with calibration methods, they can not be
seen as a complete solution for uncertainty estimation problem, since
calibration is performed relative to a validation dataset Kull et al. (2019);
Ashukha et al. (2020) (i.e., calibration methods rely on in-distribution
samples to learn a calibration map). In the presence of OOD samples, a model
is no longer calibrated. This limits the contribution of calibration
techniques to scenarios where huge training datasets are available.

##  3 Comparison of Uncertainty Estimation Methods in AV Domain

In this section, we compare and analyze some common uncertainty estimation
methods in terms of out-of-the-box calibration in the predictions (i.e.
without a prior calibration), computational budget, memory footprint, and
required changes in the DNN for applying each method (architecture, loss
function, and others). We have chosen the most representative works to the
best of our knowledge in each application. Some of the listed works introduce
improvements by performing combinations between other methods. This is
summarized in Table 1.

###  3.1 Methods Limited to Aleatoric Uncertainty

The first four methods listed in Table 1 exclusively deal with aleatoric
uncertainty. In classification tasks, uncertainty is usually represented by
normalized logits at the output layer (e.g. softmax output) which can be
interpreted as a probability distribution related to aleatoric uncertainty
Gustafsson et al. (2019). Unfortunately, normalized outputs as probability
distributions fail to capture model uncertainty and this very often results in
overconfident predictions that are wrong Guo et al. (2017), especially in the
presence of dataset-shift. To overcome the problems of softmax, Gast and Roth
(2018) propose to use a Dirichlet distribution instead.

In a regression configuration, deep learning models do not have an uncertainty
representation by default. The outputs of a DNN are intended to parameterize a
probability distribution (e.g., Gaussian, Laplace) to obtain a probabilistic
representation. This modification of the architecture allows DNNs to learn
aleatoric uncertainty from the data itself by using thes heteroscedastic loss
and maximum likelihood Kendall and Gal (2017); Ilg et al. (2018). Similarly,
in the heteroscedastic version of the classification, Kendall and Gal (2017)
place a Gaussian distribution over the output logits (i.e., each logit with
its respective variance), before the softmax layer is applied. An alternative
approach replaces the input, output and activation functions of a DNN with
probability distributions Gast and Roth (2018). This method allows the
propagation of a fixed uncertainty at the input to the output of the DNN
employing Assumed Density Filtering (ADF).

###  3.2 Bayesian Neural Networks

Bayesian Neural Networks (BNNs), aim to learn a distribution over the weights
instead of point estimates. In this way, we look for the posterior
distribution of the weights given the data $p(\mathbf{w}|\mathcal{D})$, by
applying Bayes’ theorem from the data likelihood and a chosen prior
distribution over the weights $p(\mathbf{w})$:

$p(\mathbf{w}|\mathcal{D})=\frac{p(\mathcal{D}|\mathbf{w})p(\mathbf{w})}{p(\mathcal{D})}=\frac{p(\mathcal{D}|\mathbf{w})p(\mathbf{w})}{\int
p(\mathcal{D}|\mathbf{w})p(\mathbf{w})d\mathbf{w}}$ (1)

Given the predictive posterior distribution $p(\mathbf{w}|\mathcal{D})$, we
obtain the predictive posterior distribution for a new input $\mathbf{x^{*}}$
by marginalizing over the model parameters:

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

Instead of relying on only one configuration of the weights, we use every
possible configuration of the weights (all possible models) weighted by the
posterior on the parameters, to make a prediction, i.e.
$p(\mathbf{y^{*}}|\mathbf{x^{*}},\mathcal{D})=\mathbb{E}_{p(\mathbf{w}|\mathcal{D})}[p(\mathbf{y^{*}}|\mathbf{x^{*}},\mathbf{w})]$.
This represents the Bayesian Model Average (BMA) and accounts for epistemic
uncertainty Wilson and Izmailov (2020); Gal (2016); Blundell et al. (2015).

Unfortunately, the integrals from (1) and (2) are intractable. Thus, we must
build a distribution that approximates the true posterior distribution on the
weights, $q(w)\approx p(\mathbf{w}|\mathcal{D})$. Two main paradigms exist to
build $q(w)$: Markov Chain Monte Carlo (MCMC) and Variational Inference (VI)
methods. In the former, the gold standard is Hamiltonian Monte Carlo (HMC),
and other methods like Stochastic Gradient MCMC (SG-MCMC) have been explored.
However, MCMC methods are in general hard to scale to large DNNs due to the
high-dimensional and multi-modal posterior distribution Gustafsson et al.
(2019). In the latter case, VI methods approximate the posterior over the
weights by approximating a simpler distribution $q_{\phi}(\mathbf{w})$ (e.g. a
gaussian) parameterized by $\phi$. The parameters of $q_{\phi}(\mathbf{w})$
are found by minimizing the KL-divergence to $p(\mathbf{w}|\mathcal{D})$.

A particular scalable and easy to implement sample-based method for
approximate VI is Monte Carlo Dropout (MCD) Gal and Ghahramani (2016). In this
method, dropout regularization is also applied at test time, so that
$q_{\phi}(\mathbf{w})$ is a Bernoulli distribution. Dropout is only performed
in some of the deeper layers of the DNN to model better high-level features
and to avoid slow training Mukhoti and Gal (2018); Kendall et al. (2015).
Dropout probabilities can be set manually, or the network can tune dropout
rates during training Gal et al. (2017).

All the MCD-related methods listed in Table 1 refer to this approximation of
BNNs. It can be noted from the performance comparison criteria, that the need
to take multiple forward passes (output samples) for the same input to
approximate the distribution from Equation 2 represents a major impediment to
safety-critical applications with tight time constraints and limited
computation hardware.

To get a representation of both types of uncertainty (aleatoric and
epistemic), the methods presented in Section 3.1 have been used in combination
with MCD. For example, in a regression configuration, a set of $T$ samples are
taken from the predictions of a DNN that parameterize a distribution in its
output: $\\{\mathbf{\hat{y}_{t}},\hat{\sigma}_{t}\\}_{t=1}^{T}$. However,
since aleatoric uncertainty is learned from the data itself (by using the
heteroscedastic loss), this approach could produce wrong uncertainty
estimations in samples that include a higher level of uncertainty than that
observed during training. Another approach presented in Loquercio et al.
(2020), applies MCD to take samples from a DNN where the input, output and
activation functions are replaced by probability distributions according to
Gast and Roth (2018). This method permits uncertainty propagation at the input
to the output of the DNN using ADF (e.g., sensor noise can be propagated to
the output of the DNNs). This is an appealing method for AV applications where
sensor properties are commonly known. Interestingly, the authors show that
this method can be applied to trained DNNs and is architecture agnostic.

Method Autonomous Vehicle Task Uncertainty Captured Comparison Criteria
Aleatoric Epistemic Out-of-the box Calibration Computational Budget Memory
Footprint Changes in DNN Softmax logits as parameters of a prob. dist. \-
Object Detection Feng et al. (2019b) ✓ ✗ Bad Fair Slow Small Outputs as
parameters of a prob. dist. \- Object Detection Feng et al. (2019b) ✓ ✗ Bad
Fair Slow Small Inputs, activation and output as prob. dist. & ADF \- Optical
Flow Gast and Roth (2018) ✓ ✗ Undefined Low Low Mid Point estimate & MCD
regression \- Steering Angle Prediction Hubschneider et al. (2019); Michelmore
et al. (2018, 2019) ✗ ✓ Fair Fair Low None Softmax & MCD \- Traffic Sign
Recognition Henne et al. (2020) \- Semantic Segmentation Phan et al. (2019);
Mukhoti and Gal (2018); Gustafsson et al. (2019) ✗ ✓ Fair Fair Low None Deep
Ensembles \- Steering Angle Prediction Hubschneider et al. (2019) \- Traffic
Sign Recognition Henne et al. (2020) \- Semantic Segmentation Gustafsson et
al. (2019) \- Depth Estimation Gustafsson et al. (2019) ✓ ✓ Good High High
Small Bootstrap Ensembles \- Steering Angle Prediction Hubschneider et al.
(2019) \- Optical Flow Ilg et al. (2018) ✓ ✓ Bad Fair Fair Mid Softmax logits
as parameters of a prob. dist. & MCD \- Object Detection Feng et al. (2018) ✓
✓ Fair High Low Small Outputs as parameters of a prob. dist. & MCD \- Object
Detection Feng et al. (2018) \- Steering Angle Prediction Lee et al. (2019b,
c, a) \- Depth Estimation Gustafsson et al. (2019) ✓ ✓ Fair High Low Small
Inputs, activation and output as prob. dist. & ADF &MCD \- Steering Angle
Prediction Loquercio et al. (2020) ✓ ✓ Undefined High Low Mid MDNs \- Steering
Angle Prediction Hubschneider et al. (2019); Choi et al. (2018) \- Future
Prediction Makansi et al. (2019) ✓ ✓ Bad Low Low None MDNs with stages \-
Future Prediction Makansi et al. (2019) ✓ ✓ Undefined Low Low High

Table 1: Uncertainty Estimation Methods Comparison

###  3.3 Deep Ensembles

A Deep Ensemble (DE) is another sample-based method, in which $M$ DNNs are
trained to obtain the predictive distribution $p(\mathbf{y|x})$
Lakshminarayanan et al. (2017). Each DNN learns a set of parameters
$\mathbf{w}$ that are point estimates, starting for different random
initialization and repeating the minimization $M$ times. In an ensemble,
predictions are averaged and can be considered as a mixture model that is
equally weighted:

$p(\mathbf{y|x})=\frac{1}{M}\sum_{i=1}^{M}p(\mathbf{y|x,\hat{w}}^{i}),\;\\{\mathbf{\hat{w}}^{(i)}\\}_{i=1}^{M}$
(3)

For classification, equation (3) corresponds to an average of the softmax
probabilities. For regression, the outputs that parameterize a probability
distribution are averaged to represent the mean and variance of the mixture.
In this manner, both types of uncertainty (aleatoric and epistemic) can be
easily captured. Although DE is considered a non-Bayesian method, expression
(3) represents an approximation of (2) since
$\\{\mathbf{\hat{w}}^{(i)}\\}_{i=1}^{M}$ can be seen as samples taken from
distribution that approximates the true posterior, by exploring different
modes of from $p(\mathbf{w}|\mathcal{D})$ Fort et al. (2019); Wilson and
Izmailov (2020).

As presented in Table 1, the DE method tends to outperform approximate
Bayesian inference methods like MCD, for both, uncertainty estimates and
accuracy Gustafsson et al. (2019). A recent work from Snoek et al. (2019) also
shows, that DE is more robust to dataset shift. These works suggest that DE
should be considered as the new standard method for predictive distributions
and uncertainty estimation. However, DE has some drawbacks, especially if the
target application is a safety-critical application. DE requires a higher
computational load and a larger memory footprint, as shown in Table 1. For the
training and testing stage, the number of parameters, and the inference times
scale linearly with $M$. To mitigate this problem, Osband et al. (2016)
propose a fused version of ensembles with multiple heads. All the heads share
the convolutional layers (feature extractors) and each head is trained using
boostrap samples.

###  3.4 Mixture Density Networks

Mixture Density Networks (MDN) Bishop (1994), is a sample-free method for
regression tasks, where the aim is to train a DNN that predicts the parameters
of a Gaussian Mixture Model (GMM) given an input $\mathbf{x}$. A GMM is formed
by a weighted sum of $K$ Gaussians, to model the conditional distribution:

$p(\mathbf{y|x})=\sum_{i=1}^{K}\pi_{i}(\mathbf{x})\mathcal{N}(\mathbf{y}|\mu_{i}(\mathbf{x}),\Sigma_{i}(\mathbf{x}))$
(4)

where $\pi_{i}(\mathbf{x}),\mu_{i}(\mathbf{x}),\Sigma_{i}(\mathbf{x})$
represent the set of parameters of the GMM as a function of the input
$\mathbf{x}$ for $K$ mixtures. For training, Negative Log-likelihood (NLL) is
used as loss function.

By using the law of total variance, Choi et al. (2018) formalized the
acquisition of aleatoric and epistemic uncertianty in MDNs. As a first step,
the expectation of the GMM is obtained as a combination of the mixture
components in a weighted sum:
$\mathbb{E}[\mathbf{y|x}]=\sum_{i=1}^{K}\pi_{i}(\mathbf{x})\mu_{i}(\mathbf{x})$.
The predicted variance is composed of the weighted sum of the variances and
the weighted variances of the means:

$\displaystyle\mathbb{V}[\mathbf{y|x}]=\sum_{i=1}^{K}\pi_{i}(\mathbf{x})\Sigma_{i}(\mathbf{x})+\sum_{i}^{K}\pi_{i}(\mathbf{x})\left\lVert\mu_{i}(\mathbf{x})-\sum_{i}^{K}\pi_{i}(\mathbf{x})\mu_{i}(\mathbf{x})\right\rVert^{2}$

(5)

where the first term represents the aleatoric uncertainty and the second term
represents the epistemic uncertainty. We refer the reader to Choi et al.
(2018) for more details about uncertainty acquisition in MDNs.

As pointed out in Table 1, the sampling-free nature of this method reduces the
computation load, memory footprint, and permits complex distribution modeling
with respect to the methods described before. These characteristics are
attractive for real-time applications. However, MDNs suffer from numerical
instability for high dimensional problems and mode collapse when using
regularization techniques Makansi et al. (2019).

###  3.5 Quality Metrics for Uncertainty Estimation

In this section, we discuss common metrics for evaluating the quality of
uncertainty estimation.

##### Classification Metrics.

Different methods for uncertainty estimation exist for classification tasks.
Variation Ratio and information metrics such as Predictive Entropy, Mutual
Information, can be used in classification settings to represent uncertainty
Gal (2016). Variation ratio is a measure of dispersion; mutual information
captures model confidence, and predictive entropy accounts for epistemic and
aleatoric uncertainty Mukhoti and Gal (2018); Michelmore et al. (2018); Phan
et al. (2019). Mukhoti and Gal (2018) propose specific performance metrics for
semantic segmentation to evaluate Bayesian models. Since there is no ground-
truth for uncertainty estimation, Snoek et al. (2019); Lakshminarayanan et al.
(2017) argue that proper scoring rules are NLL and Brier score. NLL depends on
predictive uncertainty and is commonly evaluated in a held-out set, however,
it can overestimate tail probabilities; whereas Brier-score measures the
accuracy of predictive probabilities by a sum of squared differences between
the predicted probability vector and the target, nonetheless, this score is
prone to avoid capturing infrequent events. Other evaluation metrics
independent of score values are: the Area Under the Receiver Operating
Characteristic (AUROC), Area Under Precision Recall Curve (AUPRC), and Area
Under Risk-Coverage (AURC) Hendrycks and Gimpel (2016); Ding et al. (2019).

##### Regression Metrics.

Similarly, in regression tasks, NLL is a proper scoring rule for a likelihood
that follows Gaussian distribution Lakshminarayanan et al. (2017); Kendall and
Gal (2017). Furthermore, Ilg et al. (2018) introduces a relative measure for
uncertainty estimation, the Area Under the Sparsification Error (AUSE) curve,
that measures the difference between the dispersion of predictions (affected
by predictive uncertainty), and a oracle in terms of true prediction error,
e.g. Root Mean Squared Error (RMSE) Gustafsson et al. (2019).

##### Calibration Metrics.

For classification tasks, common quality metrics are Expected Calibration
Error (ECE) and Maximum Calibration Error (MCE) Guo et al. (2017). The former
measures the difference between expected accuracy and expected confidence; the
latter identifies the largest discrepancy between accuracy and confidence,
which is of particular interest in safety-critical applications. For a
regression configuration, Kuleshov et al. (2018) use calibration error as a
metric that represents the sum of weighted squared differences between the
expected and observed (empirical) confidence levels; correspondingly in
Gustafsson et al. (2019), the authors propose to use the Area Under the
Calibration Error curve (AUCE) as an absolute measure of uncertainty. The
before-mentioned authors use reliability diagrams (i.e. calibration plots) to
get a visual representation of model calibration. Regardless of drawbacks with
OOD samples, calibration plots and measures are used extensively to compare
the predictive quality of other uncertainty estimation methods.

###  3.6 Considerations per AV Task Type

In the context of AVs, for (end-to-end) steering angle prediction, a broad
variety of uncertainty estimation methods have been applied. In some works
only epistemic uncertainty was captured by using MCD Michelmore et al. (2018,
2019). However, usually both types of uncertainty are captured Lee et al.
(2019b, c, a) by using the method proposed by Kendall and Gal (2017), or by
using DE, boostrap ensembles, or MDNs. The calibration plots presented in
Hubschneider et al. (2019) show that MCD has better out-of-the-box calibration
than bootstrap ensembles or MDNs; the last two methods are overconfident in
their predictions. In this particular task, safety mechanisms have been
proposed when uncertainty estimations surpass a given or learned threshold in
order to improve vehicle safety Michelmore et al. (2018, 2019); Lee et al.
(2019b).

Under the modular pipeline paradigm for AV control, probabilistic modeling has
mainly been applied to perception tasks like object detection from 3D Lidar,
semantic segmentation and depth estimation. For 3D object detection from Lidar
point-clouds, Feng et al. (2018) estimate aleatoric and epistemic uncertainty
using the methods proposed by Kendall and Gal (2017). However, epistemic
uncertainty estimation with MCD introduces a high computational cost. A later
work from Feng et al. (2019b) leverages aleatoric uncertainties to greatly
improve the performance and reduce the computational load from MCD. In Feng et
al. (2019a) the authors show that predictions for classification and
regression are miscalibrated, and propose methods to fix calibration of DNNs
and produce better uncertainty estimates.

For semantic segmentation, Phan et al. (2019); Mukhoti and Gal (2018);
Gustafsson et al. (2019) model aleatoric uncertainty from the softmax output,
and epistemic uncertainty by using MCD or ensembles. Common uncertainty
metrics in this case are predictive entropy and mutual information Mukhoti and
Gal (2018). For Depth estimation, Gustafsson et al. (2019) compares DE with
the heteroscedastic regression in combination with MCD Kendall and Gal (2017).
In both previous tasks (semantic segmentation and depth estimation) DE
achieves better performance and calibration than MCD variants Gustafsson et
al. (2019). However, in DE the computational cost at training and testing
grows linearly with the number of ensembles. Similarly for traffic sign
recognition, DE exhibit the best-calibrated outputs, but in this case, MCD in
combination with softmax also produces well-calibrated outputs close to that
from DE Henne et al. (2020).

For optical flow, Gast and Roth (2018) capture aleatoric uncertainty by
replacing the input, output and activation functions with probability
distributions. This method allows propagating a fixed value of uncertainty at
the input to the output of the DNN. Ilg et al. (2018) present an alternative
approach, where DE and bootstrap ensembles were used to obtain the predictive
uncertainty.

For future prediction, Makansi et al. (2019) propose an improvement to MDNs to
predict the multi-modal distribution of positions of a vehicle in the future.
This method presents two stages: a sampling and a fitting network. The former
network receives the current position of the vehicle as an input and outputs a
fixed number of hypotheses for future positions. The latter network fits a
mixture distribution to the hypothesis estimated in the first network. This
improvement helps to avoid mode collapse in MDNs, however, high dimensional
outputs remain challenging for this approach.

##  4 Conclusions

We presented a comparative survey for uncertainty estimation methods for both,
classification and regression tasks, in the AV domain. We also provide a
general comparative analysis of these methods. From this analysis we can see
that DE has become a gold-standard for uncertainty quantification in many AV
tasks thanks to its high-quality uncertainty predictions and its robustness to
OOD samples. However, the high computational load and large memory footprint,
can hinder its use in safety-critical applications that have hardware
limitations or tight time-constraints. Here, sampling-free methods are an
interesting avenue for future research. New robust (to OOD) and lightweight
approaches should be explored in the AV domain, to produce good-quality
uncertainty estimates. We also observed that predictions from these methods
are uncalibrated (overconfident or underconfident) and are usually applied to
classification tasks. We encourage the application of calibration methods also
for regression tasks by using the methods proposed by Kuleshov et al. (2018)
instead of limiting the assessment of predictions with only reliability
diagrams. We also suggest to study and compare uncertainty estimation methods
under dataset-shift conditions to assess their robustness. For future work, we
plan to incorporate uncertainty information into the Responsability-Sensitive
Safety model Shalev-Shwartz et al. (2017). This generalizes the approach from
Salay et al. (2020) by considering component uncertainty from different AV
subsystems and propagating it through them. These subsystems could include
DNNs e.g. for planning and control.

## Acknowledgments

This work has received funding from the COMP4DRONES project, under Joint
Undertaking (JU) grant agreement N°826610. The JU receives support from the
European Union’s Horizon 2020 research and innovation programme and from
Spain, Austria, Belgium, Czech Republic, France, Italy, Latvia, Netherlands.

## References

  * Ashukha et al. [2020] Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov.  Pitfalls of in-domain uncertainty estimation and ensembling in deep learning.  arXiv preprint arXiv:2002.06470, 2020.
  * Bansal and Weld [2018] Gagan Bansal and Daniel S Weld.  A coverage-based utility model for identifying unknown unknowns.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * Bishop [1994] Christopher M Bishop.  Mixture density networks.  1994\.
  * Blundell et al. [2015] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra.  Weight uncertainty in neural network.  In International Conference on Machine Learning, pages 1613–1622, 2015.
  * Choi et al. [2018] Sungjoon Choi, Kyungjae Lee, Sungbin Lim, and Songhwai Oh.  Uncertainty-aware learning from demonstration using density networks with sampling-free variance modeling.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 6915–6922. IEEE, 2018.
  * Czarnecki and Salay [2018] Krzysztof Czarnecki and Rick Salay.  Towards a framework to manage perceptual uncertainty for safe automated driving.  In International Conference on Computer Safety, Reliability, and Security, pages 439–445. Springer, 2018.
  * Ding et al. [2019] Yukun Ding, Jinglan Liu, Jinjun Xiong, and Yiyu Shi.  Evaluation of neural network uncertainty estimation with application to resource-constrained platforms.  arXiv preprint arXiv:1903.02050, 2019.
  * Feng et al. [2018] Di Feng, Lars Rosenbaum, and Klaus Dietmayer.  Towards safe autonomous driving: Capture uncertainty in the deep neural network for lidar 3d vehicle detection.  In 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pages 3266–3273. IEEE, 2018.
  * Feng et al. [2019a] Di Feng, Lars Rosenbaum, Claudius Glaeser, Fabian Timm, and Klaus Dietmayer.  Can we trust you? on calibration of a probabilistic object detector for autonomous driving.  arXiv preprint arXiv:1909.12358, 2019.
  * Feng et al. [2019b] Di Feng, Lars Rosenbaum, Fabian Timm, and Klaus Dietmayer.  Leveraging heteroscedastic aleatoric uncertainties for robust real-time lidar 3d object detection.  In 2019 IEEE Intelligent Vehicles Symposium (IV), pages 1280–1287. IEEE, 2019.
  * Fort et al. [2019] Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan.  Deep ensembles: A loss landscape perspective.  arXiv preprint arXiv:1912.02757, 2019.
  * 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.
  * Gal et al. [2017] Yarin Gal, Jiri Hron, and Alex Kendall.  Concrete dropout.  In Advances in neural information processing systems, pages 3581–3590, 2017.
  * Gal [2016] Yarin Gal.  Uncertainty in deep learning.  University of Cambridge, 1:3, 2016.
  * Gast and Roth [2018] Jochen Gast and Stefan Roth.  Lightweight probabilistic deep networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3369–3378, 2018.
  * 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-Volume 70, pages 1321–1330. JMLR. org, 2017.
  * Gustafsson et al. [2019] Fredrik K Gustafsson, Martin Danelljan, and Thomas B Schön.  Evaluating scalable bayesian deep learning methods for robust computer vision.  arXiv preprint arXiv:1906.01620, 2019.
  * Hendrycks and Gimpel [2016] Dan Hendrycks and Kevin Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  arXiv preprint arXiv:1610.02136, 2016.
  * Henne et al. [2020] Maximilian Henne, Adrian Schwaiger, Karsten Roscher, and Gereon Weiss.  Benchmarking uncertainty estimation methods for deep learning with safety-related metrics.  2020\.
  * Hubschneider et al. [2019] Christian Hubschneider, Robin Hutmacher, and J Marius Zöllner.  Calibrating uncertainty models for steering angle estimation.  In 2019 IEEE Intelligent Transportation Systems Conference (ITSC), pages 1511–1518. IEEE, 2019.
  * Ilg et al. [2018] Eddy Ilg, Ozgun Cicek, Silvio Galesso, Aaron Klein, Osama Makansi, Frank Hutter, and Thomas Brox.  Uncertainty estimates and multi-hypotheses networks for optical flow.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 652–667, 2018.
  * ISO [2019] ISO ISO.  Pas 21448-road vehicles-safety of the intended functionality.  International Organization for Standardization, 2019.
  * Kendall and Gal [2017] Alex Kendall and Yarin Gal.  What uncertainties do we need in bayesian deep learning for computer vision?  In Advances in neural information processing systems, pages 5574–5584, 2017.
  * Kendall et al. [2015] Alex Kendall, Vijay Badrinarayanan, and Roberto Cipolla.  Bayesian segnet: Model uncertainty in deep convolutional encoder-decoder architectures for scene understanding.  arXiv preprint arXiv:1511.02680, 2015.
  * Koopman and Fratrik [2019] Philip Koopman and Frank Fratrik.  How many operational design domains, objects, and events?  2019\.
  * Koopman et al. [2019] Philip Koopman, Beth Osyk, and Jack Weast.  Autonomous vehicles meet the physical world: Rss, variability, uncertainty, and proving safety.  In International Conference on Computer Safety, Reliability, and Security, pages 245–253. Springer, 2019.
  * Kuleshov et al. [2018] Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon.  Accurate uncertainties for deep learning using calibrated regression.  arXiv preprint arXiv:1807.00263, 2018.
  * Kull et al. [2019] Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach.  Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration.  In Advances in Neural Information Processing Systems, pages 12295–12305, 2019.
  * Kuutti et al. [2020] Sampo Kuutti, Richard Bowden, Yaochu Jin, Phil Barber, and Saber Fallah.  A survey of deep learning applications to autonomous vehicle control.  IEEE Transactions on Intelligent Transportation Systems, 2020.
  * 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.
  * Lee et al. [2019a] Keuntaek Lee, Gabriel Nakajima An, Viacheslav Zakharov, and Evangelos A Theodorou.  Perceptual attention-based predictive control.  arXiv preprint arXiv:1904.11898, 2019.
  * Lee et al. [2019b] Keuntaek Lee, Kamil Saigol, and Evangelos A Theodorou.  Early failure detection of deep end-to-end control policy by reinforcement learning.  In 2019 International Conference on Robotics and Automation (ICRA), pages 8543–8549. IEEE, 2019.
  * Lee et al. [2019c] Keuntaek Lee, Ziyi Wang, Bogdan Vlahov, Harleen Brar, and Evangelos A Theodorou.  Ensemble bayesian decision making with redundant deep perceptual control policies.  In 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA), pages 831–837. IEEE, 2019.
  * Loquercio et al. [2020] Antonio Loquercio, Mattia Segu, and Davide Scaramuzza.  A general framework for uncertainty estimation in deep learning.  IEEE Robotics and Automation Letters, 5(2):3153–3160, 2020.
  * Makansi et al. [2019] Osama Makansi, Eddy Ilg, Ozgun Cicek, and Thomas Brox.  Overcoming limitations of mixture density networks: A sampling and fitting framework for multimodal future prediction.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7144–7153, 2019.
  * McAllister et al. [2017] Rowan McAllister, Yarin Gal, Alex Kendall, Mark Van Der Wilk, Amar Shah, Roberto Cipolla, and Adrian Weller.  Concrete problems for autonomous vehicle safety: Advantages of bayesian deep learning.  International Joint Conferences on Artificial Intelligence, Inc., 2017\.
  * Michelmore et al. [2018] Rhiannon Michelmore, Marta Kwiatkowska, and Yarin Gal.  Evaluating uncertainty quantification in end-to-end autonomous driving control.  arXiv preprint arXiv:1811.06817, 2018.
  * Michelmore et al. [2019] Rhiannon Michelmore, Matthew Wicker, Luca Laurenti, Luca Cardelli, Yarin Gal, and Marta Kwiatkowska.  Uncertainty quantification with statistical guarantees in end-to-end autonomous driving control.  arXiv preprint arXiv:1909.09884, 2019.
  * Mohseni et al. [2019] Sina Mohseni, Mandar Pitale, Vasu Singh, and Zhangyang Wang.  Practical solutions for machine learning safety in autonomous vehicles.  arXiv preprint arXiv:1912.09630, 2019.
  * Mukhoti and Gal [2018] Jishnu Mukhoti and Yarin Gal.  Evaluating bayesian deep learning methods for semantic segmentation.  arXiv preprint arXiv:1811.12709, 2018.
  * Osband et al. [2016] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy.  Deep exploration via bootstrapped dqn.  In Advances in neural information processing systems, pages 4026–4034, 2016.
  * Phan et al. [2019] Buu Phan, Samin Khan, Rick Salay, and Krzysztof Czarnecki.  Bayesian uncertainty quantification with synthetic data.  In International Conference on Computer Safety, Reliability, and Security, pages 378–390. Springer, 2019.
  * Quionero-Candela et al. [2009] Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence.  Dataset shift in machine learning.  The MIT Press, 2009.
  * [44] Paul Rau, Christopher Becker, and John Brewer.  Approach for deriving scenarios for safety of the intended functionality.
  * Salay et al. [2020] Rick Salay, Krzysztof Czarnecki, Maria Soledad Elli, Ignacio J Alvarez, Sean Sedwards, and Jack Weast.  Purss: Towards perceptual uncertainty aware responsibility sensitive safety with ml.  In SafeAI@ AAAI, pages 91–95, 2020.
  * Shalev-Shwartz et al. [2017] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua.  On a formal model of safe and scalable self-driving cars.  arXiv preprint arXiv:1708.06374, 2017.
  * Snoek et al. [2019] Jasper Snoek, Yaniv Ovadia, Emily Fertig, Balaji Lakshminarayanan, Sebastian Nowozin, D Sculley, Joshua Dillon, Jie Ren, and Zachary Nado.  Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift.  In Advances in Neural Information Processing Systems, pages 13969–13980, 2019.
  * Wilson and Izmailov [2020] Andrew Gordon Wilson and Pavel Izmailov.  Bayesian deep learning and a probabilistic perspective of generalization.  arXiv preprint arXiv:2002.08791, 2020.