Uncertainty Estimation and Calibration with Finite-State Probabilistic RNNs
Authors: Cheng Wang
Carolin Lawrence
Mathias Niepert
Venue: ICLR 2021 Poster (2021)
Keywords: uncertainty estimation
calibration
RNN

Abstract: Uncertainty quantification is crucial for building reliable and trustable machine learning systems. We propose to estimate uncertainty in recurrent neural networks (RNNs) via stochastic discrete state transitions over recurrent timesteps. The uncertainty of the model can be quantified by running a prediction several times, each time sampling from the recurrent state transition distribution, leading to potentially different results if the model is uncertain. Alongside uncertainty quantification, our proposed method offers several advantages in different settings. The proposed method can (1) learn deterministic and probabilistic automata from data, (2) learn well-calibrated models on real-world classification tasks, (3) improve the performance of out-of-distribution detection, and (4) control the exploration-exploitation trade-off in reinforcement learning. An implementation is available.

Published as a conference paper at ICLR 2021
UNCERTAINTY ESTIMATION AND CALIBRATION WITH FINITE-STATE PROBABILISTIC RNNs
Cheng Wang" Carolin Lawrence', Mathias Niepert
NEC Laboratories Europe
{cheng. wang, ca rol in. lawrence, wat waw.lii..mmaaaa.a....... ma
ABSTRACT
Uncertainty quantification crucial for building reliable and trustable machine learning systems. We propose estimate uncertainty in recurrent neural networks (RNNs) via stochastic discrete state transitions over recurrent timesteps. The un- certainty of the model can be quantified by running prediction several times, each time sampling from the recurrent state transition distribution, leading to po- tentially different results if the model is uncertain. Alongside uncertainty quantifi- cation, our proposed method offers several advantages in different settings. The proposed method can (1) learn deterministic and probabilistic automata from data, (2) learn well-calibrated models on real-world classification tasks, (3) improve the performance -f--tiiibiitttioon detection, and (4) control the exploration- exploitation trade-off in reinforcement learning. An implementation is available
INTRODUCTION
Machine learning models well-calibrated if the probability associated with the predicted class reflects its correctness likelihood relative to the ground truth. The output probabilities of modern neural networks are often poorly calibrated (Guo et al., 2017). For instance, typical neural networks with a softmax activation tend to assign high probabilities to out-of-distribution samples (Gal & Ghahramani] 2016b). Providing uncertainty estimates is important for model interpretability as allows users to assess the extent to which they can trust a given prediction (Jiang et al. 2018). Moreover, well-calibrated output probabilities are crucial in several use cases. For instance, when monitoring medical time-series data (see Figure [a)), hospital staff should also be alerted when there is low-confidence prediction concerning a patient's health status.
Bayesian neural networks (BNNs), which place a prior distribution on the model's parameters, are a popular approach to modeling uncertainty. BNNs often require more parameters, approximate inference, and depend crucially on the choice of prior (Gal 2016 Lakshminarayanan et al.) 2017). Applying dropout both during training and inference can be interpreted as a BNN and provides more efficient method for uncertainty quantification (Gal & Ghahramani 2016b). The dropout probability, however, needs to be tuned and, therefore, leads to a trade-off between predictive error and calibration error.
Sidestepping the challenges of Bayesian NNs, we propose an orthogonal approach to quantify the uncertainty in recurrent neural networks (RNNs). At each time step, based the current hidden (and cell) state, the model computes a probability distribution over a finite set of states. The next state of the RNN then drawn from this distribution. We use the Gumbel softmax trick (Gumbel 1954 Kendall & Gal 2017 Jang et al. (017) to perform Monte-Carlo gradient estimation. Inspired by the effectiveness of temperature scaling (Guo et al. (017)) which usually applied to trained models, we learn the temperature 7 of the Gumbel sofimax distribution during training to control the concentration of the state transition distribution. Learning 7 as parameter can be seen as
entropy regularization (Szegedy et al.) 2016] Pereyra et al.) [017 Jang al., (017). The resulting model, which we name ST-r. defines for every input sequence a probability distribution over state-
"qqual contribution. Work done at NEC Lahoratories Europe.
https:: / thub. com/ nec- research/ htt_thstttt

---

Published as a conference paper at ICLR 2021
1.5
1.0
Normal Model
Abnormal Model wrong
Confidence
Mean
Magnitude
1.0
0.8
Standard Deviation
0.5
0.6
0.0
mean
std
0.4
-0.5
50
100
150
200
250
what a
script
what a
story
what a mess
Time (ms)
(a) Heart Rate Classification
(b) Sentiment Classification
Figure 1: (a) Prediction uncertainty of ST-T, our proposed method, for an ECG time-series based on 10 runs, To the left of the red line ST-r classifies heart beat as normal. To the right of the red line, ST-r makes wrong predictions. Due to its drop in certainty, however, it can alert medical personnel. (b) Given a sentence with negative sentiment, ST-r reads the sentence word by word. The y-axis presents the model's confidence of the sentence having negative sentiment. After the first few words, the model leans towards a negative sentiment, but is uncertain about its prediction. After the word "mess," its uncertainty drops and it predicts the sentiment as negative.
transition paths similar to a probabilistic state machine. To estimate the model's uncertainty for a prediction, ST-7 is run multiple times compute mean and variance of the prediction probabilities.
We explore the behavior of ST-r in a variety of tasks and settings. First, we show that ST-7 can learn deterministic and probabilistic automata from data. Second, we demonstrate real-world classi- fication tasks that ST-- learns well calibrated models. Third, we show that ST-- is competitive in -utoo--distribution detection tasks. Fourth, in reinforcement learning task, find that ST-r is able to trade off exploration and exploitation behavior better than existing methods. Especially the out- of-distribution detection and reinforcement learning tasks are not amenable post-hoc calibration approaches (Guo et al. (017)) and, therefore, require a method such as ours that is able to calibrate the probabilities during training.
UNCERTAINTY IN RECURRENT NEURAL NETWORKS
2.1 BACKGROUND
An RNN is a function f defined through neural network with parameters w that is applied over time steps: at time step f, it reuses the hidden state h of the previous time step and the current input x; to compute new state h, f (h,-1.X) > h, Some RNN variants such as LSTMs have memory cells C, and apply the function f (h,-1- Ct- x,) - h, at each step. A vanilla RNN maps two identical input sequences to the same state and it is therefore not possible to measure uncertainty of a prediction by running inference multiple times. Furthermore, is known that passing h, through a softmax transformation leads to overconfident predictions calibrated probabilities (Guo et al. 2017). In a Bayesian RNN the weight matrices w are drawn from distribution and, therefore, the output is average of infinite number of models. Unlike vanilla RNNs, Bayesian RNNs are stochastic and it is possible to compute average and variance for a prediction. Using prior to integrate out the parameters during training also leads a regularization effect. However, there are two major and often debated challenges of BNNs: the right choice of prior and the efficient approximation of the posterior.
samples and poorly
With this paper, we side-step these challenges and model the uncertainty of an RNN through proba- bilistic state transitions between a finite number of & learnable states Sg. Given a state h, we compute a probability distribution over the learnable states. Hence, for the same state and input, the RNN might move to different states in different runs. Instead of integrating over possible weights, as in the case of BNNs, we sum over all possible state sequences and weigh the classification probabil- ities by the probabilities of these sequences. Figure iillustaate the proposed approach and contrasts it with vanilla and Bayesian RNNs The proposed method combines two building blocks. The first is State-regularization (Wang& & Nieperl 2019) as a way to compute probability distribution over a finite set of states in an RNN. Stateeregularizztiinn. however, is deterministic and therefore we utilize the second building block, the Gumbel softmax trick (Gumbel 1954 [addison et al., 2017] Dang et al. 2017) sample from categorical distribution. Combining the two blocks allows create
2

---

Published as a conference paper at ICLR 2021
accept
0.1
0.3
accept
b
b
0.2
reject
0.6
0.7
reject
0.5
accept
accept
0.1
0.5
reject
b 0.2 reject
0.3
0.9
accept
b
b 0.1
reject
Illustration of several ways to model uncertainty in recurrent models. Left, top: In standard recurrent models the sequence of hidden states is identical for any two runs the same input. Uncertainty is typically modeled with a softmax distribution over the classes (here: accept and reject). Left, bottom: Bayesian NNs make the assumption that the weights are drawn from distribution. Uncertainty is estimated through model averaging, Right: The proposed class of RNNs assumes that there is a finite number of states between which the RNN transitions. Uncertainty for an input sequence is modeled through probability distribution over possible state-transition paths.
Figure 2:
stochastic state RNN which can model uncertainty. Before we formulate our method, we first introduce the necessary two building blocks.
Deterministic State-Regularizz RNNs. State regularization (Wang & Niepert 2019) extends RNNs by dividing the computation of the hidden state h, into two components. The first compo- nent is an intermediate vector u, E Rd computed in the same manner as the standard recurrent component, u, = (h:-1, (h,-1, C.). The second component models probabilistic state transitions between a finite set of k learnable states $1, ..... Sk, where s; Rd, [L, k] and which can also be written as a matrix S, E Rdxk S, is randomly initialized and learnt during backpropagation like any other network weight. At time step t, given ue, the transition is computed by: 0, (S,, Uz), where 0g ...,..... Or and & is some pre-defined function. In Wang & Niepert 2019), sp was a matrix-vector product followed by SOFTMAX function that ensures Σ 01, 1. The hidden state h, then computed by
next possible states
h ((.) ST. h, E ER.
(1)
where g(-) is another function, e.g. to compute the average. Because Equation cannot capture and estimate epistemic uncertainty.
11 is deterministic,
Monte-Carlo Estimator with Gumbel Trick.
The Gumbel softmax trick is an instance of path-
wise Monte-Cario gradient estimator (Gumbel) 1954. Maddison et al.] 2017 Jang al., 2017). With the Gumbel trick, it is possible draw samples z from a categorical distribution given by paramaters 0, that is, z ONE ONE_HOTT arg max; + log 0.l), E [1... ......k k). where is the number of categories and 7/ are i.i.d. samples from the GUMBEL(O, 1), that is, 7 = log(- log(u)), u ~ UNIFORM(O, 1). Because the arg operator breaks end-to-end differentiabilityy the categorical distribution can be approximated using the differentiable softmax function (Jang et al. 2017] Maddison et al. 2017). This enables to draw k-dimensional sample vector E A== where
A A is the (k 1)-dimensional probability simplex.
2.2 STOCHASTIC PINITE-STATT RNNS (ST-T)
Our goal is to make state transitions stochastic and uitilize them an input sequence, the uncertainty is modeled via the probability distribution over possible state- transition paths (see right half of Figure 2). We achieve this by setting ş be matrix-vector product and using 0, to sample from Gumbel softmax distribution with temperature parameter т. Applying Monte Carlo estimation, at each time step t, we sample a distribution over state transition probabilities a from the Gumbel softmax distribution with current parameter where each state transition has the probability
uncertainty: given
exp((lo((0r.) + 76)/T) i [1... ΣS exp((log(0..) +)))/)))))))))
The resulting a, = R can be seen as a probability distribution that judges how important each learnable state St is. The new hidden state h, now be formed either as
3

---

Published as a conference paper at ICLR 2021
X
1xd
dxk
kxd
1xd
CLi
SOFBEL-SOFTMAX
h,
-11
8
S.
S,
S
h
Figure? 3: One step of ST-T (for batch size 1). First, previous hidden state h previous cell state C.-1 (if given) and imput X;, are passed into RNN cell (e.g. LSTM). The RNN cell returns an updated hidden state u, and cell state e₁- Second, u, is further processed by using the learnable states matrix S, in the state transition step (Right) and returns
hidden state h
an average, h. = Ei ar,s (the "soft" Gumbel estimator), or as a one-hot vector, h, ONE_HOT arg max, (log(())( + %l). For the latter, gradients can be estimated using the straight- through estimator. Empirically, we found the average to work better. By sampling from the Gumbel softmax distribution at each time step, the model is stochastic and it possible to measure variance across predictions and, therefore, estimate epistemic uncertainty. For more theoretical details refer the reader to Appendix 2.3
The parameter of the Gumbel softmax distribution is learned during training (Jang et al.. 2017). This allows us to directly adapt probabilistic RNNs to the inherent uncertainty of the data. In- tuitively, the parameter т influences the concentration of the categorical distribution, that is, the larger r the more uniform the distribution. Since we influence the state transition uncertainty with the learned temperature т, we refer to our model as ST We provide an ablation experiment of learning versus keeping it fixed in Appendix
E
Figure 3 iillustrates the proposed model. Given the previous hidden state of RNN, first an interme- diate hidden state is computed using a standard RNN cell. Next, the intermediate representation u, multiplied with & learnable states arranged as a matrix S,, resulting in Oz. Based on O,, sam- ples are drawn from Gumbel softmax distribution with learnable temperature parameter The sampled probability distribution represents the certainty the model has moving to the other states. Rumning the model the same input several times (drawing Monte-Carlo samples) allows to estimate the uncertainty of the ST-r model.
2.3 ALEATORIC AND EPISTEMIC UNCERTAINTY
Let y be set of class labels and D be a of training samples. For classification problem and given ST-r model with states {si...., s we can write for every E y
ply (X1,..., x,))
Σ b..)e
p((n.... ................................ hn) xx q (y h,)
where h, E {Si..... 5x} and the sum is over all possible paths (state sequences) V of length n. More- over, p( p(h h,) x) is the probability of path vi (hi.... hn) E V given input sequence and class given that we are state h,, Instead of integrating over possi-
q (y h,) ) is the probability ble weights, as in the case of BNNs, with ST-r we integrate (sum) over all possible paths and weigh the class probabilities by the path probabilities. The above model implicitly defines a probabilistic ensemble of several deterministic models, each represented by a particular path. As mentioned in a recent paper about aleatoric and epistemic uncertainty in ML (Hüllermeier & Waegeman| 2019): "the variance of the predictions produced by an ensemble good indicator of the (epistemic) uncertainty in a prediction."
Let us now make this intuition more concrete using recently proposed measures of aleatoric and epistemic uncertainty (Depeweg et al.) 2018); further discussed in (Hällermeier & Waegeman, 2019). In Equation (19) (Hüllermeier Waegeman 2019) the rotal uncertainty defined as the entropy of the predictive posterior distribution
H (p(y x)] E(y xx) log, p(y/x).
NEY
The above term includes both aleatoric and epistemic uncertainty (Depeweg et al.) 2018 Hüllermeier Waegeman] 2019). Now, in the context of Bayesian NNs, where we have dis- tribution over the weights of neural network, the expectation of the entropies wrt said distribution
4

---

Published as a conference paper at ICLR 2021
4 [h) = 0.3 q(y h.)) 0.7
4 [h.) = 0.1
1.0
0.5
q h) =09
0.0
40% h.) = 0.5 q by) 0.5
0.5
q bb) 0.5
q h.) = 0.5
Figure 4: Two different probabilistic finite-state RNNs.
is the aleatoric uncertainty (Equation 20 in Hüllermeier & Waegeman (219
Ey(wED) (ply
w, x)]==-] p D)
Σ BEY
ply w, x) log, ply w, w,x) dw.
Fixing the parameter weights to particular values eliminates the epistemic uncertainty. Finally, the epistemic uncertainty is obtained as the difference of the total and alcatoric uncertainty (Equation 21 in Hüllermeier & Waegeman (219
Ue (x) H [p(y x)] B)( [p(y
w, w.x)].
Now, let return to finite-state probabilistic RNNs. Here, the aleatoric uncertainty is the expecta- tion of the entropies with respect to the distribution over the possible paths Vr:
Epcete H (ply x),x
Σ p(u x) NEW
Σ plu wh, x) logg ply vx yEV
where ply v. x) is the probability of class y conditioned on x and a particular path v. The epistemic uncertainty for probabilistic finite-state RNNs can then be computed by
(x())= == H Ip(v | x)] Ep(r)x) H [p(y v,,x]
Probabilistic sinite-state RNNs capture epistemic uncertainty when the equation above is non non-zero. As an example let us take a look at the two ST-- models given Figure + Here, we have for input x two class labels y/ and y/. three states (s;,
{0. 1, and two paths. In both cases, we have that H [p(y x)] = (0.3 log, 0.3 + 0.7 log, 0.7) 0.8813. Looking at the term for the aleatoric uncertainty, for the ST-r depicted on the left side we have Ep (<) H [p(y v v,x]] (0.3 log, 0.3 + 0.7 loga 0.7) x 0.8813. In contrast, for the ST-r depicted on the right side we have Eprwpo H [ply v6 x) R 0.7345. Consequently, the left side ST-r has an epistemic uncertainty of (x(x) but the right side ST-- exhibits an epistemic uncertainty of ue (x) 0.1468.
This example illustrates three main observations. First, we can represent epistemic uncertainty through distributions over possible paths. Second, the more spiky the transition distributions, the more deterministic the behavior of the ST-7 model, and the more confident it becomes with its pre- diction by shrinking the reducible source of uncertainty (epistemic uncertainty). Third, both models are equally calibrated their predictive probabilities are, in expectation, identical for the same inputs. Hence, ST-r not merely calibrating predictive probabilities but also captures epistemic uncertainty. Finally, want stress the connection between the parameter (the temperature) and the degree of (cpistemic) uncertainty of the model. For small 7 the ST-r model behavior is more deterministic and, therefore, has lower degree of epistemic uncertainty. For instance, the ST-r the left Figure has 0 epistemic uncertainty because all transition probabilities are deterministic. Empirically, find that the temperature and, therefore, the epistemic uncertainty often reduces during training, leaving the irreducible uncertainty (aleatoric) to be the main source of uncertainty.
3 RELATED WORK
Uncertainty quantification for safety-critical applications (Kzzywisski & Altman 2013) has been explored for deep neural nets in the context of Bayesian learning (Blundell et al.
Uncertainty.
2015
Gal & Ghahramani] 20166; Kendall & Gal 2017] Kwon et al. 2018). Bayes by Back-
prop (BBB) (Blundell et al. 2015) is variational inference scheme for learning distribution
5

---

Published as a conference paper at ICLR 2021
over weights in neural networks and assumes that the weights distributed normally, that is, we ~ [N,, o The principles of bayesian neural networks (BNNs) have been applied to RNNs and shown to result in superior performance compared to vanilla RNNs in natural language processing (NLP) tasks (Fortunato et al., 2017). However, BNNs come with a high computational cost because need to learn jr and for each weight in the network, effectively doubling the number of param- eters. Furthermore, the prior might not be optimal and approximate inference could lead inaccurate estimates (Kuleshov al. 2018). Dropout (Hinton et al. 2012, Srivastava al. (2014) can be seen as a variational approximation of a Gaussian Process (Gal & Ghahramani 201 a). By leaving dropout activated at prediction time, it can be used measure uncertainty. However, the dropout probability needs to be tuned which leads to a trade-off between predictive error and calibration er- ror (see Figure 10 in the Appendix for an empirical example). Deep ensembles (Lakshminarayanan er al..,22077 (017) offer a non-Bayesian approach to measure uncertainty by training multiple separate net- works and ensembling them. Similar to BNNs, however, deep ensembles require more resources as several different RNNs need to be trained. We show that ST-r is competitive to deep ensembles with- out the resource overhead. Recent work (Hwang et al. (2200) describes a sample-fres uncertainty estimation for Gated Recurrent Units (SP-GRU) (Chung et al.) 2014), which estimates uncertainty by performing forward propagation in a series of deterministic linear and nonlinear transformations with exponential family distributions. ST-x estimates uncertainties through the stochastic transitions
between two consecutive recurrent states.
Calibration. Platt scaling (Platt al. 1999) is calibration method for binary classification settings and has been extend to multi-class problems ZZarrzzyy& & Elkan (2002) and the structured prediction settings (Kuleshov & Liang 2013). (Guo et 2017) extended the method to calibrate modern deep neural networks, particularly networks with a large number of layers. In their setup, temperature parameter for the final softmax layer is adjusted only after training. In contrast, our method learns the temperature and, therefore, the two processes are not decoupled. In some tasks such as time- series prediction or RL it crucial to calibrate during training and not post-hoc.
Deterministic & Probabilistic Automata Extraction. Deterministic Finite Automata (DFA) have been used to make the behavior of RNNs more transparent. DFAs can be extracted from RNNs after an RNN is trained by applying clustering algorithms like k-means to the extracted hidden states (Wang et al., 2018) or by applying the exact learning algorithm L (Weiss et al.) 2018). Post- hoc extraction, however, might not recover faithful DFAs. Instead, (Wang & Niepert (2199) pro- posed rtgte-regularized RNNs where the finite set of states is learned alongside the RNN by using probabilistic state transitions. Building on this, we use the Gumbel softmax trick to model stochastic state transitions, allowing us to learn probabilistic automata (PAs) (Rabin 1963) from data.
Hidden Markov Models (HMMs) & State-Space Models (SSMs) & RNNs. HMMs
transducer-style probabilistic automata, simpler and more transparent models than RNNs. (Bridle) 1990) explored how HMM can be interpreted as an RNNs by using full likelihood scoring for each
word model. (Krakovna& & Doshi- Velez 2016) studied various combinations of HMMs and RNNs to
increase the interpretability of RNNs. There have also been ideas on incorporating RNNs to HMMs to capture complex dynamics (Dai et al. 2017: Doerr et al. 2018). Another relative group of work SSMs, e.g., rSLDS (Linderman et al. (017), Kalman VAB (Fraccaro et al. 2017). PlaNet (Hafner et al. 2019) and RKN (Becker et al. (019). They can be extended and viewed as another way to inject stochasticity to RNN-based architectures. In contrast, ST-r models stochastic finite-state tran- sition mechanisms end-to-end in conjunction with modern gradient estimators to directly quantify and calibrate uncertainty and the underlying probabilistic system. This enables ST-7 to approximate and extract the probabilistic dynamics in RNNs.
4 EXPERIMENTS
The experiments are grouped into five categories. First, we show that it is possible to use ST-r to learn deterministic and probabilistic automata from language data (Sec. H.I.. This demonstrates that ST-r can capture and recover the stochastic behavior of both deterministic and stochastic lan- guages. Second, we demonstrate on classification tasks (Sec. 4.2 that ST-7 performms better than or similar to existing baselines both in terms of predictive quality and model calibration. Third, compare ST-r with existing baselines using diitr-i-iitiitttinn detection tasks (Sec. 4.3). Fourth, conduct reinforcement learning experiments where we show that the learned parameter 7 can

---

Published as a conference paper at ICLR 2021
11.00
1
(
(0.15)
[0.7]
[0.3]
O [0.3)
1 [0:3]
29,0000
I [1.0000]
[0.71]
11.00
[0.3]
00.3000077
[0:7]
(
[0:7]
(0.71.000)
(a) True PA-1
(b) Extracted PA-1
(c) True PA-2
(d) Extracted PA-2
Figure 5: (a)+(c): ground truth probabilistic automata (PAs) used for generating training samples. (b)+() the PAs extracted from ST-T The single and double circles represent reject and accept states respectively. The PA (d) resulted from minimization of the actual extracted PA.
calibrate the sample complexity. Fifth, we report results on a regression task (Appendix
trade-off during learning (Appendix D leading to a lower
Models. We compare the proposed ST-F method to four existing models. First, vanilla LSTM (LSTM). Second, a Bayesian RNN (BBB) (Blundell et al., 2013 Fortunato et al.) 2017). where each network weight w; is sampled from a Gaussian distribution N (u, wi +++ a 6, with = 1o + exp(p)) and e ~ (0, 1). To estimate model uncertainty, we keep the same sampling strategy as employed during training (rather than using wy μ)). Third, RNN that employs Variational Dropout (VD) (Gal & Ghahramani 2016a). In variational dropout, the same dropout mask is applied at all time steps for one input. To use this method to measure uncertainty, we keep the same dropout probability at prediction time (Gal & Ghahramani 2016a). Fourth, deep ensemble of a LSTM base model (Lakshminarayanar hidden state using the soft version of the Gumbel softmax estimator (Jang et al. (017). All models
[017]. For ST-- we compute the new
contain only a single LSTM layer, are implemented Tensorflow (Abadi et al. 2015), and use the ADAM (Kingma & Ba 2015) optimizer with initial learning rate 0.001.
4.1 DETERMINISTIC & PROBABILISTIC AUTOMATA EXTRACTION
We aim to investigate the extent to which ST-- can learn deterministic and probabilistic automata from sequences generated by regular and stochastic languages. Since the underlying languages are known and the data is generated using these languages, we can exactly assess whether ST-f can recover these languages. We refer the reader to the appendix for a definition of deterministic finite automata (DFA) and probabilistic automata (PA). The set of languages recognized by DFAs and PAs are referred to as, respectively, regular and stochastic languages. For the extraction experiments we use the GRU cell it does not have cell state. This allows to read the Markovian transition probabilities for each inptt symbol pair directly from the trained ST-r.
Regular Languages. We conduct experiments on the regular language defined by Tomita grammar 3. This language consists of any string without an odd number of consecutive O's after an odd number of consecutive I's (Tomita 1982). Initializing 7 1, train ST (with k 10 states) to learn a ST-r model to represent this grammar and then extract DFAS (see Appendix [A.4] for the extraction algorithm). In principle, & 2 # of classes, the model learns to select a finite set of (meaningful) states to represent language, as shown in Appendix Figure 8. ST- is able to learn that the underlying language is deterministie, learning the temperature parameter T accordingly and the extraction produces the correct underlying DFA. The details are discussed in the appendix.
Stochastic Languages We explore whether it is possible recover PA from a ST-- model trained on the data generated by a given PA. While probabilistic deterministic finite automata (PDFAs) have been extracted previously (Weiss et al., 2019) to the best of our knowledge, this is the first work to directly learn a PA, which is more expressive than PDFA (Denis & Esposito| 2004), by extraction from a trained RNN. We generate training data for two stochastic languages defined by the PAs shown in Figure 5 (a) and (c). Using this data, we train ST-7 with GRU with k 4 states and we directly use the Gumbel softmax distribution to approximate the probability transitions of the underlying PA (see Appendix A.3 for more details and the extraction algorithm). Figures 5 (b, d) depict the extracted PAs. For both stochastic languages the extracted PAs indicate that ST is able to learn the probabilistic dynamics of the ground-truth PAs.
7

---

Published as a conference paper at ICLR 2021
Datasct
BIH
IMDB
Metrics
PE
ECE
MCE
PE
ECE
MCE
LSTM
1.40
0.78
35.51
10.42
3.64
11.24
Ensembles
1.51=le-s
0.72110.10
31.49:18.52
10.5611:e-*
3.45111.47
12.16:1..68
BBB
4.69=:2
-3
0,54:10.11
12.4447.65
10.841:2e -4
2.10:0.02
6.15:10.25
VD
1.51+3e
0.80++0.03
24.71+16.70
10.56+6e"
3.41+0.07
14.08+0.87
ST-r = 5/2
2.12+55e
0.45++0.03
23.11+12.76
10.95+-5e
0.89++0.05
3.70++0.63
ST-- l 10 2.11+55
0,40++0.05
11.73+11.115
11,16+7e
3.38
9.09++0.74
Table 1: Predictive Error (PE) and calibration errors (ECE, MCE) for the datasets BIH and IMDB (lower is better for all metrics). ST-y offers the best and reliable trade-off between predictive error and calibration errors. Furthermore, it does not require more parameters as BBB (double) or Deep Ensemble (order of magnitude more) nor does hyperparameter has to be tuned as in VD. Stochastic predictions are averaged across 10 independent runs and their variance is reported. Best and second best results are marked in bold and underlined (PE: bold models are significantly different at level p S 0.005). An ablation experiment with post-hoc temperature scaling is in Appendix B.3.
1.0
1.0
PUNIC O11S0P)
PPNIC Cnidesin
9.8
9.8
0.8
0.8
MICE 11487
MCE - 23, 22
NCCE 9:39
2.35
0.8
DGE
9.4
9.4
0.4
0.2
0.2
0.2
0.2
0.02
0.25
2.50
0.75
3.50
5.00
0.25
0.50
0.75
1:50
3.00
0.25
0.50
0.75
3.00
0.00
0.25
0.50
0.75
3.00
Corfidence
Confidence
Confidence
Confidence
(a) LSTM (error 1.32%)
(b) BBB (error 4.29 86) (c) VD 0.05 (error 1.45%) (d) ST-F (error 2.09%)
Figure 6: Calibration plots (for one run) on the BIH dataset (corresponding to the left half of Table using N = 10 bins. ST-r (k = 2) is closest to the diagonal line, that is, perfect calibration.
4.2 MODEL CALIBRATION
We evaluate ST 's prediction and calibration quality on two classification tasks. The first task is heartbeat classification with classes where we use the MIT-BIH arrhythmia dataset (Goldberger et al. 2000 Moody & Mark 2001). It consists of 48 half-hour excerpts of electrocardiogram (ECG) recordings. To preprocess the recordings we follow Kachuee et al. (2018) (Part III.A). The second task is sentiment analysis where natural language text is given as input and the problem is binary sentiment classification. We use the IMDB dataset (Maas et al. 2011). which contains reviews of movies that are to be classified as being positive or negative. For further dataset and hyperparameter details, please see Appendix [.2]
We compute the output of each model 10 times and report mean and variance. For the deep ensem- ble, we train 10 distinct LSTM models. For VD, we tuned the best dropout rate in {0.05, 0.1, 0.15} and for BBB we tuned f (0, 0.01) and p {-1, 1, -2, 2, -3, -4), choosing the best setup by low- est predictive error achieved on validation data. For ST-r, we evaluate both, setting the number of states the number of output classes (k: 5/2, BIH and IMDB, respectively) and a fixed value k = 10. We initialize with = 1 and use a dense layer before the softmax classification. For more details see Appendix, Table With a perfectly calibrated model, the probability of the output equals the confidence of the model. However, many neural networks do not behave this way Guo et al. (2017). To assess the extent to which a model is calibrated, we use reliability diagrams as well as Expected Calibration Error (ECE) and Maximum Calibration Error (MCE). Please see Appendix B.T for details. For VD, the best dropout probability on the validation set 0.05. Lower is better for all metrics. For PE, all models are marked bold if there is no significant difference at level p < 0.005 to the best model.
The results are summarized in Table 1 For the BIH dataset, the vanilla LSTM achieves the smallest PE with a significant difference to all other models at p S 0.005 using an approximate randomization test (Noreen) 1989). It cannot, however, measure uncertainty and suffers from higher ECE and MCE. Similarly. VD exhibits a large MCE. The situation is reversed for BBB were we find a vastly higher PE, but lower MCF. In contrast, ST-- achieves overall good results: PE is only
Results.
8

---

Published as a conference paper at ICLR 2021
Datasets
IMDB(In/Movicc(un) O-AUPR
Method
Accuracy
O-AUPR
O-AUROC
Accuracy
O-AUROC
LSTM (max. prob.)
87.9
72.5
77.3
88.1
66.7
71.6
VD 0.8
88.5
74.8
80.6
87.5
69.3
74.7
BBB p -3
87.6
67.4
72.0
87.6
67.1
71.9
ST-- l =
88.3
80.1
84.5
88.1
75.1
81.0
0.8
88.5
67.8
76.5
87.5
63.8
71.8
BBB p = -3
87.6
76.0
75.4
87.6
76.8
75.6
ST-T l 100
86.5
78.9
82.8
85.9
74.0
78.7
ST-- & 10
88.3
65.0
76.5
88.1
64.1
75.1
Ensembles (max.prob.)
88.6
78.9
84.4
88.3
74.5
79.6
Ensembles (variance)
88.6
79.7
84.0
88.3
75.8
79.9
Results (averaging on 10 runs for VD, BBB, ST Ensembles are based on 10 mod- els) of the out-of-distribution (OOD) detection with max-probability based (top), variance max- probability based (middle) and ensembles (bottom). ST-- exhibits very competitive performance.
Table 2:
slightly higher than the best model (LSTM) while achieving the lowest ECE and the second low- the
MCE. The calibration plots of Figure 6 show that ST-ris well-calibrated in comparison other models. For the IMDB dataset, ST-- has slightly higher PE than the best models, but has the lowest ECE and MCE offering good trade-off. The calibration plots of IMDB can be found in In addition to achieving consistently competitive results across all metrics,
the Appendix, Figure 9 ST-r has further advantages compared the other methods. The deep ensemble doubles the number of parameters by the number of model copies used. BBB requires the doubling of parameters and carefully chosen prior, where ST-- does only require a slight increase in number of parameters com- pared to vanilla LSTM. VD requires the tuning of the hyperparameter for the dropout probability, which leads to a trade-off' between predictive and calibration errors (see Appendix B.3.2
4.3 OUT-OF-DISTRIBUTTIN DETECTION
We explore the ability of ST-7 to estimate uncertainty by making it detect out-of-distribution (OOD) samples following prior work (Hendrycks Gimpel 2017). The in-distribution dataset is IMDB and we use two OOD datasets: the Customer Review test dataset (Hu & Liu 2004) and the Movie review test dataset (Pang al., 2002). which consist of, respectively, 500 and 1. 1,000 samples. As in Hendrycks & Gimpel (2017). we use the evaluation metrics AUROC and AUPR. Additionally, we report the accuracy on in-distribution samples. For VD we select the dropout rate from the values (0.05, 0, 0.2} and for BBB we select the best μ (0, 0.01) and
1-1,-2 -3 -4), based on best AUROC and AUPR. For ST-r we used 10 and & = 100. Beside using maximum probability of the softmax (MP) baseline (Hendrycks & Gimpel 2017). we also consider the variance of the maximum probability (Var-MP) across 10 runs. The number of in-domain samples is set to be the same the number of out-of-domain samples from IMDB (Maas al. 2011). Hence, a random baseline should achieve 50% AUROC and AUPR.
Results. Table 2 lists the results. ST-7 and deep ensembles the best methods in terms of OOD detection and achieve better results for both MP and Var-MP. The MP results for ST-r are among the best showing that the proposed method is able estimate out-of-distribution uncertainty. We consider these results encouraging especially considering that we only tuned the number of learnable finite states e ST-r. Interestingly, larger number of states improves the auriance-based out-of- distribution detection of ST-r. In summary, ST-r is highly competitive in the OOD task.
5 DISCUSSION AND CONCLUSION
We proposed ST-r a novel method to model uncertainty in recurrent neural networks. ST-T achieves competitive results relative to other strong baselines (VD, BBB, Deep Ensembles). while circum- venting some of their disadvantages, e.g., extensive hyperparameters tuning and doubled number of parameters. ST-r provides novel mechanism capture the uncertainty from (sequential) data over time steps. The key characteristic which distinguishes ST-f from baseline methods its ability to model discrete and stochastic state transitions using modern gradient estimators at each time step.

---

Published as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving. Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vin- cent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Watten- berg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: Large-scale machine learning on heterogeneous distributed systems, 2015.
Bram Bakker. Reinforcement learning with long short-term memory. Advances in Neural Infor- mation Processing Systems (NIPS), 2002.
Philipp Becker, Harit Pandya, Gregor Gebhardt, Cheng Zhao, C. James Taylor, and Gerhard Neu- mann. Recurrent kalman networks: Factorized inference high-dimensional deep feature spaces. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, CA, USA, volume of Proceedings of Machine Learning Research, pp- 544 552, 2019. URL http:tt:///ppt ints http:/ppiitttntnn.o...... wincolnnnnnn. ac..iinnnccccc.. ac uk/ wttp:///......kk.///////e//// http////////////228555555/
Charles Blundell, Julien Comebiiee, Koray Kavukcuoglu, and Daan Wierstra. Weight Uncertainty in Neural Networks. In Proceedings of the 32nd International Conference on International Confer- ence on Machine Learning (ICML), 2015.
John S Bridle. Alpha-nets: recurrnt 'neural' network architecture with a hidden markov model interpretation. Speech Communication, 911:833-9,, 1990.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym, 2016.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555. 2014.
Hanjun Dai, Bo Dai. Yan-Ming Zhang, Shuang Li, and Le Song. Recurrent hidden model. In International Conference on Learning Representations (ICLR), 2017.
Morris DeGroot and Stephen Fienberg. The comparison and evaluation of forecasters. The Statisti- cian, 1983.
François Denis and Yann Esposito. Learning classes of probabilistic automata. In International Conference on Computational Learning Theory, pp. 124-139. Springer, 2004.
Stefan Depeweg, Jose-Miguel Hernandez-Lobato, Finale Velez, and Steffen Udluft. Decom- position of uncertainty in bayesian deep learning for efficient and risk-sensitive learning. In International Conference on Machine Learning, pp. 1184-1193. PMLR, 2018
Andreas Doerr, Christian Daniel, Martin Schiegg, Nguyen- Tuyyen Duy, Stefan Schaal, Mare Tous- saint, and Trimpe Sebastian. Probabilistic recurrent state-space models. In International Confer- ence on Machine Learning, pp. 1280-1289, 2018.
Meire Fortunato, Charles Blundell, and Oriol Vinyals. Bayesian Recurrent Neural Networks. CORR, abs/1 704.00798. 2017.
Marco Fraccaro, Simon Kamronn, UIrich Paquet, and Ole Winther. A disentangled recognition and nonlinear dynamics model for unsupervised learning. In Advances Neural Information Processing Systems, pp. 3601-3610, 2017.
Yarin Gal. Uncertainty in Deep Learning, PhD thesis, University of Cambridge, 2016.
Yarin Gal and Zoubin Ghahramani. A Theoretically Grounded Application of Dropout in Recurrent Neural Networks. In Advances in Neural Information Processing Systems (NIPS), 2016a.
Yarin Gal and Zoubin Ghahramani. Dropout as Bayesian Approximation: Representing Model Uncertainty in Deep Learning. In Proceedings of The 33rd International Conference on Machine Learning (PMLR), New York, New York, USA, 2016b.
10

---

Published as a conference paper at ICLR 2021
AL Goldberger, LA Amaral, L Glass, JM Hausdorff, PC Ivanov, RG Mark, JE Mietus, GB Moody, CK Peng, and HE Stanley. PhysioBank, PhysioToolkit, and PhysioNet: components of a new research resource for complex physiologic signals. Circulation, 101(23):E215 20, June 2000. ISSN 0009-7322. doi: 10. 161//1.cirr. 101.23..222. 23..211..
Faustino J Gomez and Jürgen Schmidhuber. Co-evolving recurrent neurons learn deep memory pomdps. In Proceedings of the 7th annual conference Genetic and evolutionary computation, pp. 491-498, 2005.
Emil Julius Gumbel. Statistical Theory of Extreme Values and Some Practical Applications. A Series of Lectures. Number 33. US Govt. Print. Office, 1954.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinherger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In International Conference on PMLR, 2019.
Machine Learning, pp.
Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. ICLR, 2017.
Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhut- dinov. Improving neural networks by preventing co-adaptation of feature detectors. CoRR, hls/1207.05800 2012.
Minqing Hu and Bing Liu. Mining and summarizing customer reviews. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 168-177, 2004.
Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: A tutorial introduction. arXiv preprint arXiv:1910.09457, 2019.
Scong Jae Hwang, Ronak R Mehta, Hyunwoo Kim, Sterling C Johnson, and Vikas Singh. Sampling-free uncertainty estimation in gated recurrent units with applications to normative mod- eling in neuroimaging. In Uncertainty in Artificial Intelligence, pp. 809-819. PMLR, 2020.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical Reparamettrrizttion with Gumbel-Softmax. In 5th International Conference on Learning Representations (ICLR), 2017.
Heinrich Jiang, Been Kim, Melody Guan, and Maya Gupta. To trust or not to trust classifier. In Advances in neural information processing systems, pp. 5541-5552, 2018.
M. Kachuee, S. Fazeli, and M. Sarrafzadeh. ECG Heartbeat Classification: A Deep Transferable Representation. In IEEE International Conference on Healthcare Informatics (ICHI), 2018.
Alex Kendall and Yarin Gal. What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision? In Advances in Neural Information Processing Systems (NIPS), 2017.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Viktoriya Krakovna and Finale Doshi Velez. Increasing the interpretability of recurrent neural net- works using hidden markov models. arXiv preprint arXiv: 1606.:6600.05522 05000, 2016.
Martin Krzywinski and Naomi Altman. Points of significance: Importance of being uncertain.
Nature Methods, (099)809-8100 2013. ISSN 1548-7091. doi: 10. 10.10388mmethh2613..
Volodymyr Kuleshov and Percy S Liang. Calibrated structured prediction. Advances in Neural Information Processing Systems, pp. 3474-3482, 2015.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate Uncertainties for Deep Learn ing Using Calibrated Regression. In Proceedings of the 35th International Conference on Machine Learning (ICMI), 2018.
11

---

Published as a conference paper at ICLR 2021
Yongchan Kwon, Joong-Ho Won, Beom Joon Kim, and Myunghee Cho Paik. Uncertainty quan- tification using Bayesian neural networks in classification: Application to ischemic stroke lesion segmentation. In International Conference Medical Imaging with Deep Learning (MIDL), 2018.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles. In Advances in Neural Information Processing Systems (NIPS), 2017.
Scott Linderman, Matthew Johnson, Andrew Miller, Ryan Adams, David Blei, and Liam Paninski. Bayesian learning and inference in recurrent switching linear dynamical systems. Artificial Intelligence and Statisfics, pp. 914 922, 2017.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. Learning Word Vectors for Sentiment Analysis. In Proceedings of the 49th Annual Meet- ing of the Association for Computational Linguistics: Human Language Technologies (NAACL), 2011.
Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables. In 5th International Conference on Learning Repre- sentations (ICIR),, 2017.
Ali Malik, Volodymyr Kuleshov, Jiaming Song, Danny Nemer, Harlan Seymour, and Stefano Er- mon. Calibrated model-based deep reinforcement learning. In International Conference on Ma- chine Learning, pp. 4314 4323,, 2019.
G. B. Moody and R. G. Mark. The impact of the MIT-BIH Arthythmia Database. IEEE Engineering in Medicine and Biology Magazine, 20(3):45-333 May 2001. ISSN 0739-5175. doi: 10.1109/51. 932724.
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the Twenty-Nini AAAI Conference on Artificial Intelligence (AAAI), 2015.
Alexandru -iculescu-Mizil and Rich Caruana. Predicting Good Probabilities with Supervised Learning. In Proceedings of the 22nd International Conference on Machine Learning (ICML), 2005.
Eric W. Noreen. Computer Intensive Methods for Testing Hypotheses: An Introduction. Wiley, New York, 1989.
Bo Pang. Lillian Lee, and Shivakumar Vaithyanathan. Thumbs up? sentiment classification using machine learning techniques. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002), pp. 79 86. Association for Computational Lin- guistics, July 2002.
Gabriel Pereyra, George Tucker, Jan Chorowski, Lukasz Kaiser, and Geoffrey Hinton. Regularizing neural networks by penalizing confident output distributions. arXiv preprint arXiv: 2017.
John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers, 10(3):61-74, 1999.
Michael O Rabin. Probabilistic automata. Information and Control, 6(3):230-245) 1963.
Anton Maximilian Schäfer. Reinforcement learning with recurrent neural networks, 2008
Ingo Schellhammer, Joachim Diederich, Michael Towsey, and Claudia Brugman. Knowledge Ex- traction and Recurrent Neural Networks: An Analysis of Elman Network Trained on Natural Language Learning Task. In Proceedings of the Joint Conferences on New Methods Language Processing and Computational Natural Language Learning, 1998.
12

---

Published as a conference paper at ICLR 2021
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, 1lya Sutskever, and Ruslan Salakhutdinov. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. Journal of Machine Learn ing Research, 15:1999-1958, 2014.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
M. Tomita. Dynamic construction of finite automata from examples using hill-climbing. In Pro- ceedings of the Fourth Annual Conference of the Cognitive Science Society, pp. 105-108, 1982.
Cheng Wang and Mathias Niepert. State-Regularized Recurrent Neural Networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
Qinglong Wang, Kaixuan Zhang, Alexander G. Ororbia II, Xinyu Xing. Xue Liu, and C. Lee Giles. An Empirical Evaluation of Rule Extraction from Recurrent Neural Networks. Neural Computa- tion, 30(9):2568-258) 2018.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples. In Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research, 2018.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Learning Deterministic Weighted Automata with Queries and Counterexamples. In Advances in Neural Information Processing Systems 32, pp- 8558-8569. Curran Associates, Inc., 2019.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass proba- bility estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowl- edge discovery and data mining, pp. 694-699, 2002.
13

---

Published as a conference paper at ICLR 2021
A DETERMINISTIC & PROBABILISTIC AUTOMATA EXTRACTION
For the ST-- models we use an embedding layer and an LSTM layer (both with 100 hidden units) and dense layer which accepts the last hidden state output and has two output neurons (accept, reject). The training objective aims to minimize cross-entropy loss for a binary classification problem (accept reject).
A.1 DEFINITION OF DETERMINISTIC FINITE AUTOMATA
Deterministic Finite Automata (DFA) is t-tuple (Ω. Σ, 6, 9o. F) consisting of a finite set of states Q; finite set of input tokens > (called the input alphabet); transition function d 2 start state qo: and a set of accept states F C Q. Given a DFA and an input, it is possible to follow how an accept or reject state reached. DFAS can be extracted from RNNs in order offer insights into the workings of the RNN, making it more interpretable. SR-R RRNNN (Wang & Niepert 2019) extract DFAs from RNNs by counting the number transitions that have occurred between a state and its subsequent states, given certain input (Schellhammer et al., 1998). However, this extraction method is deterministic and cannot give any uncertainty estimates for the extracted DFA. By adding stochasticity using the Gumbel softmax distribution, we can additionally offer uncertainty measures for the state transitions.
Q:
A.2 EXTRACTING AUTOMATA FOR REGULAR LANGUAGES
With this experiment, r changes as training progresses (see Figure (a)). At the beginning of training, т first increases, allowing the model to explore the state transitions and select the states which will represent the cor- responding grammar (in our example, the model selects out of 10 states to represent Tomita 3, see Figure (b, c)). Later, decreases and the transition uncertainty is calibrated have tighter bounds, becoming more deterministic). Second, we want to see if ST-- can model the uncertainty in transi- tions and adaptively learn calibrate the state transition distributions. For this, we extract DFAs at two different iterations (see Figure 7 (b, c)). After 50k iterations, correct DFA can be extracted. However, the transitions are not well calibrated. The ideal transition should be deterministic and have transition probability close to 1. For example, at state 7, for input "I", only 53% of the time the model transitions to the correct state 9. contrast, after 250k iterations, the transitions are well calibrated and all transition are almost deterministic. At the same time, 7 has lowered, indicating that the model has become more certain.
explore two features of ST-r First,
understand how
A.3 DEFNITION OF PROBABILISTIC AUTOMATA
The stochasticity in ST-r also allows extract Probabilistic Automata (PA) (Rabin 1963) which
have a stronger representational power than DFAs. A PA is defined as a tuple ( Σ. o, Yo- F) con- sisting of finite of states Q: finite set of input tokens V; transition function 8 Q x Σ P.
where P is the transition probability for a particular state, and P(Q) denotes the power set of Q; start state Qu and set of accept states F S Q.
A.4 EXTRACTING DFAS WITH UNCERTAINTY INFORMATION
Let p(sj (8;, I2), i.j (1...,k), k), It E Σ be the probability of the transition to state 8j, given current state s; and current input symbol F; at given time step We query each training sample to model and record the transition probability for each input symbol. The DFA extraction algorithms (Schellhammer al. 1998, Wang et al. 2018) are based on the count transitions. In contrast, extraction algorithm utilizes the transition probability, as described in Algorithm
A.5 EXTRACTING PROBABILISTIC AUTOMATA
We first define two probabilistic automata as shown in Figure 5 ()) to generate samples from i
We generated 10,170 samples for stochastic language 1 (abbreviated SL-1) with PA-1 (Figure 5 a))
We generate samples without combining identical samples. For instance, consider sequence drawn from PA-2 which has probability 0..7 to he rejected and probability 0.3 be accepted. In this case, generate 10
14

---

Published as a conference paper at ICLR 2021
3
100
150
200
250
300
350
Iterationsxx10")
(a) Temperature over iterations
[0.69.0.01]
[0. 84.0.00
[0.77.0.01]
06,001
0 (0.22.0.01]
[0.7.0.01]
[0.53,0.01]
[0.86.0.0]
[0.92.0.0]
10.9000))
(b) Extracetd DFA after 50x 10 iterations, T =2.98.
00.96.0.0]
|0 99.0.0
[0.98.0.0]
[0.99.0.0]
[0.98.0.0]
[0.98.0.0]
[0.96,0.0]
[0.99.0.0]
[1.0,00]]
(c) Extracetd DFA after 250x 10 iterations, = =1.61
Figure 7: (a) As training progresses the learned temperature decreases. This indicates that the model has reduced its epistemic uncertainty. c) The extracted DFAs different iterations on the Tomita grammar with input symbol and, in square brackets, the transition probability and uncertainty, quantified by the variance. the earlier stage training (b), the probabilities are still far away from being deterministic. which is also indicated by the higher value of r and the non- zero variance. Later (c), the transition probabilities are close to being deterministic, the temperature has lowered and there is more epistemic uncertainty. States 1-3, 8, 10 are missing as the model choose not to use these states.
and sample length E [1, For SL-2 with PA-2, we generated 20,4 20,460 samples with sample length I E 10]. The learning procedure is described in Algorithm 2 We use the Gumbel softmax distribution in ST-r approximate the probability distribution of next state p(s, [s; 22). To achieve this goal, we set the number of states k to an even number and force the first half of the state to "reject" state and the second half of states be "accept". This allows us to ensure that the model models both "reject" and "accept" with the same number of states.
In the main part of the paper we report results when setting ST-r have Here, additionally present the results for k: = 6 in Figure g which yields comparable results, showing that ST-r is not overly sensitive to the number of states. is however, helpful have the same number of accept and reject states.
states for SL=22.
training samples with the sequence, 7 of which are labeled "0" (reject) and of which are labeled "1" (accept) expectation.
15

---

Published as a conference paper at ICLR 2021
Algorithm Extracting DFAs with Uncertainty Information
Input:
model M, dataset alphabet Σ, start token Iig
Output:
transition function 6
Initialize an empty dictionary Z|s [8s, x4] = Ø
2: Compute the probability distribution over & states when input zo:
Pi.k _M $j = arg max (1.....)) [P1:s]
3: Set s; s,, Update Z[sy|za) = {pp}
4: for (2,, TT) E do
5: for E [1,....]] T] do
6:
P1:k _M (s, .)
arg (I...) (1
7:
Set 8; = 8j. Update Z[s [s,y|s;,00 rz]:
8:
s Z[sy su Z Z(s, st. xel {p5),
9: end for
10: end for
11: Compute transition function 6, transition probability mean Pa and variance pvar:
12: for i.J {1....,k) k} and E Σ do
13: Pu = mean (2)aan([(s))) 5; Rx)))
14: Pear var (s3 88, m4)])
15: ((5518;,z4) = arg max (E Pu
16: end for
Algorithm Extracting PAs with ST-r
Input: dataset D
Output: network loss
for x. E D do
initialize ho with the 1st state s1, 81 (=
ho $
for Fı xx [1, .... T] do
sigmaa W W. Ught-1)
Ft sigma W,,t U,h;-11
St. tahn(W gx' h1ght-1
Ur 2: @ h4-1 + (1 2+) 3 gt
Pt Su,
P: GUMBEL T)
h Pe Ts
ý Pt
end for
if y
then
0. 1, 1..11
R/2
k/2
else
y
1.1,,.1,,000
k/2
end if
Compute cross-entropy loss:
I. -.=COOSS-ENTROPY((..
end for
16

---

Published as a conference paper at ICLR 2021
[1.00.00
[0.111.0.0
[0.27.00.6]
|1.0,0.01
14 0.0.000
[0.2.0006]
[0.06.0.01
[1.0.00]]
[0.21 005
0
[0.1 11.0.33
[0.26.0.07]
[1.0]]
[0.24.0.05]
[1.0.000
10000
0 [0.7]
[0.11.0.44
1002111
[0.22]
1 [0.3]
[0.23.0.06]
[0.5]
11.0
[100000]
[1.0]
[0.3]
0 [0.29]
[0.12.0003
[0.7]
(a) Truth PA-2
(b) Extracted PA-2
(c) Minimized PA-2
Figure 8: True PA (a) used for generating training samples and the respective extracted PAs (b, c) from the trained ST-7 models with 6 states. We merged reject and accept nodes in (b) to retain one reject (start state is not merged) and accept node in (c). For a given state and input symbol, the probability of accept and reject for (a) and are nearly equivalent, For example, state 8 in (a), input "O", p(accept) A "0") 0.3 x 0.29 = placcept(s,, "0") and p(accept|sA, "0") = 0.7 R 0.71 0.5 0.21 placcept]s1, s1 "0"))
17

---

Published as a conference paper at ICLR 2021
B MODEL CALIBRATION
We address the problem of supervised multi-class sequence classification with recurrent neural networks. We follow the definitions and evaluation metries as (Guo et al. 2017). Given in- put X E X' and ground-truth label Y V. probabilistic classifier m(X) (Y,P). The Y (u1,..., ) P {fr...., p&) present the predicted class label and confidence (the probability of correctness) over classes and Σ P. = 1.
Definition of Calibration A model is perfectly calibrated if the confidence estimation equals the true probability, that is, P(Y- P p) - p. 1].
B. EVALUATION OF CALIBRATION
Reliability Diagrams (DeGroot Fienberg 1983 Niculescu-Mizil & Caruana 2005) visualise whether a model is over- or under-confident by grouping predictions into bins according to their prediction probability. The predictions are grouped into N interval bins (each of of size 1/N) and the accuracy of samples wrt. to the ground truth label ý: in each bin b, is computed as:
1 Σ
acc(b,,)
1 yi),
(4)
1nl
where i indexes all examples that fall into bin ba- Let pi be the probability for sample yis then average confidence is defined as
[bml Σp. p..
conf (..))
(5)
A model is perfectly calibrated if acc(b,.) conf(b,,), Vn. and in diagram the bins would follow the identity function. Any derivation from this represents miscalibration.
Based on the accuracy and confidence measures, two calibration error metrics have been introduced (Naeini et al. 2015).
Expected Calibration Error (ECE). Besides the reliability diagrams, ECE is convenient tool to have scalar summary statistic of calibration. computes the difference between model accuracy and confidence weighted average across bins,
N ECE
(ace(b,)) conf(b,)).
(6)
where m is the total number of samples.
Maximum Calibration Error (MCE) is particularly important in high-risk applications where liable confidence measures are absolutely necessary. measures the worst-case deviation between accuracy and confidence,
MCE max (1..,. (bcc(b,)) conf bb,)
For perfectly calibrated classifier, the ideal ECE and MCE both equal to 0.
Dataset Train
IMDB
BIH
23k
78k:
Validation
2k
8k
Test
25k
21k
Max Length
2,956
187
# Classes
2 Language
Type
BCG
Table Overview used datasets, if applicable, numbers are rounded down.
18

---

Published as a conference paper at ICLR 2021
1.0
1.0
1.0
1,0
Pobii Critutie
NITE 23
12.=122.2
6.84
0.6
Accracy
0.6
0.5
Accuney
0.5
0.4
0.4
0.4
0.4
0.00
0.25
0.50
0.75
1.09
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Confidence
Confidence
Confisence
Conficence
(a) LSTM (error 10.90%)
(b) BBB (error 11.17%)
(c) VD 0.1 (error 10.80%)
(d) ST-7 (error 10.89%)
Figure 9: Calibration plots for the IMDB dataset (corresponding to the right half of Table 1 using N 10 bins. BBB, VD and ST-- are all quite well calibrated this data set. The first run is displayed. Best viewed in colour.
Hyperparameters Hidden dim.
IMDB
BIH
256
128
Learning rate
0,001
0.001
Batch size
8
256
Validation rate
1k
1k:
Maximum validations
20
50
ST-F # states
2
BBB f
0.0
0.01
BBB
-3
-3
VD Prob.
0.1
0.05
Table 4: Overview of the different hyperparameters for the different datasets. Validation rate indi- cates after how many updates validation is performed.
PE
ECE
MCE
LSTM
1.40
0.30
13.02
Ensemble
1.51le
0.22:10.05
21.90=16.62.522
BIH
BBB
4.69+22
0.36=#0.09
10.43=7.886
VD
0.05
1.51
0.27+0.02
23.60=18.66
ST-r
2.1245e
0.45+00.03
15.38
LSTM
10.42
1.19
5.82
IMDB
Ensemble
10.56-13-
1.26:10.56
5.87+2.40
BBB
10.84
0.63
2.69 L0.33
V.
10.56-6e-4
2.34+10.01
10.86+1.333
ST-r
10.95
1.00
3.84
Table 5: Same [able] but with post-hoc temperature scaling. Among the models (Ensemble, BBB, VD) that can estimate uncertainty, ST-- is very competitive, i.c., the second best on both the BIH and the IMDB datsaet. LSTM is not able to provide any uncertainty information. Predictive Error (PE) and calibration errors (ECE, MCE) for the various RNNs on the datasets BIH and IMDB (lower is better for all metrics). ST-7 offers the best and reliable trade-off between predictive error and calibration errors. Furthermore, it does not require double the parameters as BBB nor does hy- perparameter have to be tuned as in VD. Stochastic predictions are averaged across independent runs and their variance is reported. For VD, report the best dropout probability on the valida- tion set. Best and the second best results are marked bold and underlined (PE: bold models are significantly different at level p < 0.005 non-bold models).
B.2 DATASET AND HYPERPARAMETER DETAILS
For the experiments of Section 4.2 provide overview of the used datasets in Table and give details on the different hyperparameters used in the experiments in Table 4 On BIH, we use the training / test split of (Kachuee et al. 2018) however additionally split off 10% of the training
19

---

Published as a conference paper at ICLR 2021
40
PE VI
ST-T
Error(%)
ECE
20
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0 ST-r
Dropout Probability
BIH
40
Error(%)
ST-T
NCE VD
MCE ST.T
20
0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
ST-r
Dropout Probability
(b) IMDB
Figure 10: For VD we plot various dropout probabilities prediction time and their corresponding етrог rates (PE, ECE, MCE). Additionally we report the results of ST--. For VD, while lowering the probability rate decreases the predictive error (PE), it the same time increases MCE and/or ECE. On the other hand, ST-r combines the best of both worlds without having to tune any parameters.
data to use as a validation set. On IMDB, the original dataset consist of 25k training and 25k test samples, we split 2k from training set as validation dataset. The word dictionary size is limited to 5,000.
B.3 ADDITIONAL EXPERIMENTS
Here we report three groups of additional or ablation experiments: (1) All baseline method and ST- r with directly employing post-training temperature scaling. (2) The trade-off between predictive and calibrate performance with different dropout ratio in variational dropout (VD). (3) Additional calibration plots for the IMDB dataset.
B.3.1 EXPERIMENTS WITH TEMPERATURE SCALING
For classification calibration experiments, the post-hoc temperature scaling can also be used to cal- ibrate models. However, please note, post-hoc temperature scaling not be used when need to calibrate a model during training stages, for example, the tasks like DFA or PA extraction, rein- forcement learning tasks.
report3 the results with temperature scaling where temperature tuned on valid set. Among the models (Ensemble, BBB, VD) that can estimate uncertainty, ST-r is very competitive, for ex- ample, the second best on both the BIH and the IMDB datsaet. While LSTM can achieve better predictive performance and sometimes better calibration performance, LSTM is not able provide any uncertainty information.
B.3.2 EXPERIMENTS WITH DIFFERENT DROPOUT RATE
To gain better understanding of how crucial the hyperparameter of VD is, investigate the effect of the dropout probability during prediction with VD. We perform an experiment where we vary the dropout probability in the range of [0.0, 0.9] with increments of 0.1. In Figures (a, b) we plot the result for BIH and IMDB, respectively, reporting PE, ECE and MCE for the various VD settings as well as ST
On both datasets, for VD, the point of lowest PE does not necessarily coincide with the points of lowest MCE and/or ECE, For example BIH, VD achieves the lowest PE when dropout is switched
20

---

Published as a conference paper at ICLR 2021
1.0
LSTM: mean = 1.588e std = 4.812e
0.5
0.0
20
40
60
80
100
1.0
BBB: mean 8.25e 7, std 3627e
0.5
0.0
20
40
60
80
100
1.0
VD: mean 0.736e - std 143.
0.5
Global Active Power
0.0
60
80
100
1.0
ST-r: mean = 0.735e std 54.5e
0.5
0.0
20
40
60
80
100
Samples
Figure 11: The test mean squared error (MSE) of different methods on predicting power consump- tion over time steps (x axis). The results are based on averaging 3 runs. The shaded areas present standard deviation, the first 100 samples are displayed. ST-r and VD provide the best predictive performance, while ST-r exhibits tighter uncertainty bounds.
off (0.0), but then uncertainty cannot be measured. On the other hand, choosing the next lowest PE results in high MCE. In contrast, ST-r directly achieves good results for all three metrics. Similarly, on IMDB, at the point where VD has the lowest PE is also has highest MCE, In conclusion, VD requires careful tuning which comes with choosing trade-off between the different metries, while ST-r achieves good results directly, without any tuning.
B.3.3 CALIBRATION PLOTS FOR THE IMDB DATASET
Figure g shows the calibration plots for IMDB. For the binary classification task BBB achieves the best calibration performance and VD achieves the best predictive performance. It should be noted that ST-r achieves the best trade-off between predictive and calibration performance without doubling parameters (for BBB) and without tuning dropout rate for (VD).
C REGRESSION
Calibration plays an important role in probabilistic forecasting. We consider time-series forecast- ing regression task using the individual household electric power consumption dataset The goal of the task is to predict the global active power at the current time (t) given the measurement and other features the previous time step. The dataset was sampled at the time step of an hour (the original data are given in minutes), which leads to 34,588 samples. We split it 25,000/2,000/7 .888 for training/validatioontess One LSTM layer with 100 hidden units is used for the baselines (LSTM, BBB and VD) and ST-r (the number of states is set 10). The evaluation metric mean squared emror (MSE) and we use the model with lowest MSE on the validation dataset at test stage.
http:://archit ics uci
power4consumption The data is preprocessed by following httpps://www kaggle.com www.aeiannnnttn seriee--eee -etiees--aaaaaa -ataeeeddaaaaaalalaeaaaa - waw.igg---tttoooommm
21

---

Published as a conference paper at ICLR 2021
50
50
60
Recwnds
Rewarrss
Rowarrs
40
30
20
20
270
EpisonetNL07
Episode/x109
Epteodetsc10f
(a) MDP, sampling
(b) MDP, greedy
(c) POMDP, sampling
(d) POMDP, greedy
Figure 12: Average cumulative reward and standard deviation (in log scale, the shade areas) over time steps (episode) the Cartpole task. Results averaged over 5 randomly initialized runs. In all cases ST-- achieves a higher averaged cumulative reward given lower sample complexity.
Left
Right
Figure 13: In the cartpole task the goal is to balance the pole upright by moving the cart left or right each time step (9 the angle).
Figure 11 presents the performance. LSTM, VD and ST-r perform very well this task, achieving MSE close to zero. BBB performs worse than the other methods, For uncertainty estimation. BBB, VD and ST-r are able provide uncertainty information alongside the predictive score. BBB gives high uncertainty, while VD and ST-r are more confident in their prediction, with ST-r offering the tightest uncertainty bounds.
D REINFORCEMENT LEARNING
We explore the ability of ST to learn the exploration-exploittionn trade-off in reinforcement learn- evaluate ST-r in the continuous control environment CART- POLE (Figure (3) of OpenAl Gym (Brockman et al. 2016). The objective of the task is to train an agent balance pole for 1 second (which equals 50 time steps) given environment observations O. To keep the pole balance, the agent has to move the pole either left or right, that is, the possible actions
ing. To demonstrate this empirically,
[LEFT, RIGHT). If the chosen action keeps the pole in balance, the agent receives reward of and continues; otherwise reward of 0 is given and the run stops.
The environment
be formulated as reinforcement learning problem (S, A, R) where S is of states. Each state {ax f, B, }}- E S consists of x: cart position, ã: cart velocity, 3: angle position, and 8: angle velocity.
the set of actions, the state transition probability, and the reward. We consider two different setups. In the first setup, the CARTPOLE environment is fully observable Markov Decision Process (MDP setup) where the agent has full access to observation Ó
that is, O {a, -, 3, 33 E S. In the second and more difficult setup (POMDP), the environment is partially observable, where O {x. 3} S. For the latter, the agent cannot observe the state cart velocity and angular velocity information. It has to learn to approximate them using its recurrent connections, and thus needs to retain long-term history (Bakker, 2002; Gomez & Schmidhuber, 2005] Schateer 2008). The various RNN-based models are trained to output a distribution over actions at each time step f, that is, T<a 8t, at),, where π is the set of policy. For selecting the next action, we consider two policies: (1) sampling: a++1 ~ (a 8t, at), and (2) greedy: 0c+1 arg max 7 (al 8t, a.). For baselines, we use one LSTM layer and one dense layer with softmax to return the distribution over actions. Each layer has 100 hidden units. For VD we tuned the dropout
rate (0.05, 0.1, 0.2} and for BBB μ = {0, 0.01, 0.05, 0.1} and p p= 1-1.-2,- -3, -4}. For ST-- we simply set the initial temperature value to 1, the number of possible states the number of actions (k- = 2), and the next action directly selected based on the Gumbel softmax distribution over states.
22

---

Published as a conference paper at ICLR 2021
80
84
88.5
78
Accuracy
88.0
O-AUPR
76
O-AUROC
82
87.5
74
80
72
87.0
78
70
10
20
50
10
20
50
10
20
50
Number States
Number of States
Number States
75
87.5
74
80
Accuracy
AUPR
O-AUROC
87.0
72
86.5
71
86.0
85.5
10
50
2
10 20
50
Number States
Number of States
Number of States
Figure 14:
Apblation study for ST-- with (1) different number of states (k=2, 10, 20, 50) and (2) learning temperature T (green) and fixed temperature = (blue) on the Out-of-Distribution Detection (OOD) task. The max-probabie max-probability based O-AUPR and O-AUROC are reported. Top: (MDBBln)Cuustomr((Ouu) Bottom: IMDB(nn)Movie(Outt) The results are averaged over 10 runs. Learning the temperature akin to entropy regularization (Szegedy et al.] 2016)] Pereyra et al., Jang al. 2017) and adjusts the confidence (epistemic uncertainty) during training.
2017
An important criteria for evaluating RL agents is the sample complexity (Malik al.) 2019), that is, the amount of interactions between agent and environment before a sufficiently good reward is obtained. For both environment setups and both policy types, ST-r achieves a higher averaged cumulative reward given lower sample complexity. Moving from sampling to greedy policy, ST-- performance slightly drops. This is easily explained by the in- herent sampling process due to the Gumbel softmax. Interestingly, it seems it this sampling process which allows ST-- to exhibit lower sampling complexity in the sampling setups compared LSTM and VD. contrast, LSTT and VD show poor performance for the greedy policy setups because they no longer explore by sampling from the softmax. BBB consistently performs worse than the other methods and we conjecture that this is due to the much larger number of parameters of this model, leading to worse sampling complexity. Moving from the MDP to the POMDP, the average accumulative reward naturally drops, as the agents receive less information, but ST-r again exhibits the best performance for both policy types.
Results are presented in Figure 12
E ABLATION STUDY ON OUT-OF-DISTRIBUTIO DETECTION
Figure [4]epicts the results of ablation study focusing on the number of states and whether or not the temperature 7 was learned. The results are for the two IMDB Out-of-Distribution Detection (OOD) tasks from section 4.3 The results indicate that smaller number of states is sufficient to capture the ST-- model's 's uncertainty on out-of-distribution data. Especially when the temperature parameter is learned during training (the green, solid line), ST-7 shows the best results. Increasing the number of states of ST-r, gives the model more capacity to model uncertainty. For 50 states, fixing the temperature to constant values works better but does not reach the accuracy of ST- models with fewer states and learned temperature.
23


Reviews:
[{"review_id": "vmtF4mdMQck", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a novel approach for uncertainty estimation with RNNs. More precisely, the task is to both fit a model on the data and to learn the uncertainty of the fitted model at the same time.\n\nThe proposed approach fits a random model, with its randomness adjusted to the level of uncertainty. The probability of the potential outputs on a given input is then estimated by sampling the model (i.e., re-evaluating it multiple times on the same input). This, in turn, can also be used to estimate the uncertainty of the model.\n\nOne important detail that the paper does not discuss but would be important to understand is how S_t is trained/updated? (Actually, the same question goes for \\tau.) In fact, referring to S_t as states is quite confusing; from the formulas it seems that they are used as weights. The authors should discuss these questions in detail.\n \nApart of these issues, the paper is relatively well written and the considered problem is important to various applications. The proposed model also makes sense on the high level (although the missing details make it hard to claim the same in general). Finally, empirical evaluations show the effectiveness of the method, and also that its performance is comparable - and in many cases superior - to vanilla LSTM, Bayesian RNN. RNN with variational dropout, and a deep ensemble of LSTM based model.\n\n\n\nREMARKS\n\nSection 2.2.\nSetting \\varphi to be a dot-product does not seem right: as its two attributes are \\theta_t \\in R^d and S_t \\in S^{d x k}, the dimensions do not match. Simple matrix-vector product does work though.\n\nIn fact, Section 2 could be somewhat polished; it is not always easy to understand what is part of the proposed method, and what is explained in relation to other models only. Additionally, it would be helpful to have a brief recap at the end of the section about how the uncertainty estimation is done for the model.\n\nIn (1), t_i does not seem to be defined. Actually, should it not be {t,i}? Additionally, \\alpha_i two lines below (2) should be \\alpha_{t,i}, presumably.", "extra_scores": {}, "extra_text": {}}, {"review_id": "tRTdJHJsBXj", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a novel method to estimate uncertainties in recurrent neural networks. The proposed model explicitly computes a probability distribution over a set of discrete hidden states given the current hidden state in an RNN. Leveraging the Gumbel softmax trick, the proposed method performs MC gradient estimation. A temperature parameter is also learned to control the concentration of state transition distribution. To estimate uncertainty of a given input, the proposed model is run multiple times to draw samples for estimating the mean and variance. Experiments are conducted in a variety of sequential prediction problems, including a reinforcement learning task, demonstrating the effectiveness of the proposed uncertainty estimation method.\n\n\nPros:\nEstimating uncertainty of predictions is important for data-driven machine learning models, especially for detecting out-of-distribution data;\nThe proposed method directly quantifies and calibrates uncertainty, and therefore does not use much more parameters (compared to BNNs) and requires less parameter tuning;\nThe paper selects a good range of task domains and strong baseline methods, demonstrating comparable performance.\n\nCons:\nWhile the proposed method demonstrates good performance on both modeling stochastic processes and estimating out-of-distribution data, it is unclear whether the method itself can separate epistemic uncertainty from aleatoric  uncertainty if both exists; meanwhile, most of the selected baseline methods focuses exclusively on estimating the epistemic uncertainty; if possible, it is desired to see a comparison of the proposed method with baseline methods that are designed to exclusively model aleatoric uncertainties for RNNs;\nIt is mentioned that a large number of states improves performance in the experiments for predicting OOD data; a plot for the relationship between performance and the number of states used would be useful to understand how sensitive the performance is to the number of states used;\nIf possible, the authors should also discuss the proposed work’s relationship with the sampling-free method of Hwang et al. [1] and how the choice of using discrete state distribution would outperform a parametric distribution.\n\n\n[1] Hwang, S. J., Mehta, R. R., Kim, H. J., Johnson, S. C., & Singh, V. (2020, August). Sampling-free uncertainty estimation in gated recurrent units with applications to normative modeling in neuroimaging. In Uncertainty in Artificial Intelligence (pp. 809-819). PMLR.\n\n\n------------------------------------\nUpdate: the major concerns above have been addressed in the appendix of the updated manuscript. I'm moving my initial rating of 6 to 7.", "extra_scores": {}, "extra_text": {}}, {"review_id": "pSP5cz2E4DZ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper proposes a method to quantify the uncertainty for RNN. Different from  the traditional Bayesian RNN, the proposed method is more efficient. At each  time, based on the current hidden state and memory, it generates a probability  distribution over the state transition paths on the transition probability by  using the Gumbel softmax function. The next state is computed based on the weighted average of the sampled states and its uncertainty can be  qualified by the sample variance. The hyper-parameter tau of the Gumbel function  is learnt from data to better capture the inherent uncertainty in the data.\n\nTo demonstrate their method, they perform several experiments. First, they show that their model can  capture the stochastics in language better than other methods  Second, they demonstrate their  method performs better in classification on benchmark datastes than baseline methods  such as the ensemble and BBB methods in terms of both prediction accuracy and efficiency.   Third, they evaluated their method for out-of-distribution detection and their experiments again show their method performs better than the baseline methods on benchmark datasets.  Finally, they show that when applied to reinforcement  learning, their method is better than existing  methods in sample complexity. \n\nStrengths:\nThe proposed method for uncertainty quantification is efficient, compared with other methods such as Bayesian RNN.  The performances of their methods have been evaluated for different tasks on benchmark datasets and show competitive performance versus the baseline methods.\n\nWeaknesses: \nFirst, technical novelty is minor; it is largely based on the exiting work on Gumbel function.  More importantly, is unclear why the Gumbel softmax function, even with the learnt tau parameter, can capture the data uncertainty and better theoretical justification  is needed.   Second, it is unclear how to compute the aleraeroic and epistemic uncertainties separately from their method as the latter is needed for OOD detection.  Third, it is unclear how to quantify the accuracy with the estimated uncertainty and how the improved uncertainty quantification can translate into improved performance in classification /regressions.  Fifth, the experimental comparisons are only done for baseline methods for each task.  The authors should also compare their methods to SOTA methods for each task.  Finally, they need do an ablation study on their method to figure out what contributes to their method’s improved performance for certain tasks. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gSP20LdcKgC", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n----------\n\nThis paper presents an approach to uncertainty modeling in recurrent neural networks through a discrete hidden state. The training of this discrete model is done using a reparameterizable approximation (in particular, using the Gumbel-Softmax trick). The authors show the utility of this method on a variety of problems, including showing effective out of distribution detection and improved calibration in classification tasks.\n\nComments\n----------\n\nThis paper presents a relatively simple idea that builds relatively directly from previous work, and uses the now common Softmax-Gumbel trick to enable differentiability. The main strength of this paper is the thorough experimental evaluation, on a wide variety of problems. \n\nThe main weakness of this paper is the very unclear presentation of the method. In section 2.1, the authors do not define all quantities, the mathematics of the method is interspersed with discussions of the approaches of others, and the writing is unclear. The authors must clarify the presentation of their method, and have this presentation be distinct from discussion of previous work. \n\nOverall, the experimental results seem compelling and interesting. The authors should clarify their discussion of the partially observed RL task. In the partially observed task, is the agent only provided lagged measurements of the state? The presentation if quite confusing and the authors should state what this task is as clearly as possible. \n\nPost-Rebuttal\n----------\nI thank the authors for their response. Both of the sections are now more clear, although the authors should make an effort to polish the narrative of the paper and the clarity of exposition throughout. The discussion of epistemic versus aleatoric uncertainty in the appendix is also interesting. I have increased my score from 6 to 7. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to quantify the uncertainty for RNN, which is an important problem in various applications. It provides results in a variety of domains demonstrating that the proposed method outperforms baselines. However, these experiments would benefit greatly from a comparison with SOTA methods for the specific tasks in addition to the considered baselines (e.g. covariance propagation, prior network, and orthonormal certificates). The paper could also be improved by adding a theoretical justification to explain how the Gumbel softmax function is able to capture the underlying data and model uncertainty.
Decision: Accept (Poster)