Year: 2021

Abstract:
Uncertainty estimation is important for ensuring safety and robustness of AI systems. While most research in the area has focused on unstructured prediction tasks, limited work has investigated general uncertainty estimation approaches for structured prediction. Thus, this work aims to investigate uncertainty estimation for autoregressive structured prediction tasks within a single unified and interpretable probabilistic ensemble-based framework. We consider uncertainty estimation for sequence data at the token-level and complete sequence-level; interpretations for, and applications of, various measures of uncertainty; and discuss both the theoretical and practical challenges associated with obtaining them. This work also provides baselines for token-level and sequence-level error detection, and sequencelevel out-of-domain input detection on the WMT’14 English-French and WMT’17 English-German translation and LibriSpeech speech recognition datasets.

heading: 1 INTRODUCTION
text: Neural Networks (NNs) have become the dominant approach in numerous applications (Simonyan & Zisserman, 2015; Mikolov et al., 2013; 2010; Bahdanau et al., 2015; Vaswani et al., 2017; Hinton et al., 2012) and are being widely deployed in production. As a consequence, predictive uncertainty estimation is becoming an increasingly important research area, as it enables improved safety in automated decision making (Amodei et al., 2016). Important advancements have been the definition of baseline tasks and metrics (Hendrycks & Gimpel, 2016) and the development of ensemble approaches, such as Monte-Carlo Dropout (Gal & Ghahramani, 2016) and Deep Ensembles (Lakshminarayanan et al., 2017)1. Ensemble-based uncertainty estimates have been successfully applied to detecting misclassifications, out-of-distribution inputs and adversarial attacks (Carlini & Wagner, 2017; Smith & Gal, 2018; Malinin & Gales, 2019) and to active learning (Kirsch et al., 2019). Crucially, they allow total uncertainty to be decomposed into data uncertainty, the intrinsic uncertainty associated with the task, and knowledge uncertainty, which is the model’s uncertainty in the prediction due to a lack of understanding of the data (Malinin, 2019)2. Estimates of knowledge uncertainty are particularly useful for detecting anomalous and unfamiliar inputs (Kirsch et al., 2019; Smith & Gal, 2018; Malinin & Gales, 2019; Malinin, 2019).
Despite recent advances, most work on uncertainty estimation has focused on unstructured tasks, such as image classification. Meanwhile, uncertainty estimation within a general, unsupervised, probabilistically interpretable ensemble-based framework for structured prediction tasks, such as language modelling, machine translation (MT) and speech recognition (ASR), has received little attention. Previous work has examined bespoke supervised confidence estimation techniques for each task separately (Evermann & Woodland, 2000; Liao & Gales, 2007; Ragni et al., 2018; Chen et al., 2017; Koehn, 2009; Kumar & Sarawagi, 2019) which construct an "error-detection" model on top of the original ASR/NMT system. While useful, these approaches suffer from a range of limitations. Firstly, they require a token-level supervision, typically obtained via minimum edit-distance alignment to a ground-truth transcription (ASR) or translation (NMT), which can itself by noisy. Secondly, such token-level supervision is generally inappropriate for translation, as it doesn’t account for the validity of re-arrangements. Thirdly, we are unable to determine whether the error is due to knowledge or
1An in-depth comparison of ensemble methods was conducted in (Ashukha et al., 2020; Ovadia et al., 2019) 2Data and Knowledge Uncertainty are sometimes also called Aleatoric and Epistemic uncertainty.
data uncertainty. Finally, this model is itself subject to the pitfalls of the original system - domain shift, noise, etc. Thus, unsupervised uncertainty-estimation methods are more desirable.
Recently, however, initial investigations into unsupervised uncertainty estimation for structured prediction have appeared. The nature of data uncertainty for translation tasks was examined in (Ott et al., 2018a). Estimation of sequence and word-level uncertainty estimates via Monte-Carlo Dropout ensembles has been investigated for machine translation (Xiao et al., 2019; Wang et al., 2019; Fomicheva et al., 2020). However, these works focus on machine translation, consider only a small range of uncertainty adhoc measures, provide limited theoretical analysis of their properties and do not make explicit their limitations. Furthermore, they don’t identify or tackle challenges in estimating uncertainty arising from exponentially large output space. Finally, to our knowledge, no work has examined uncertainty estimation for autoregressive ASR models.
This work examines uncertainty estimation for structured prediction tasks within a general, probabilistically interpretable ensemble-based framework. The five core contributions are as follows. First, we derive information-theoretic measures of both total uncertainty and knowledge uncertainty at both the token level and the sequence level, make explicit the challenges involved and state any assumptions made. Secondly, we introduce a novel uncertainty measure, reverse mutual information, which has a set of desirable attributes for structured uncertainty. Third, we examine a range of Monte-Carlo approximations for sequence-level uncertainty. Fourth, for structured tasks there is a choice of how ensembles of models can be combined; we examine how this choice impacts predictive performance and derived uncertainty measures. Fifth, we explore the practical challenges associated with obtaining uncertainty estimates for structured predictions tasks and provide performance baselines for tokenlevel and sequence-level error detection, and out-of-domain (OOD) input detection on the WMT’14 English-French and WMT’17 English-German translation datasets and the LibriSpeech ASR dataset.

heading: 2 UNCERTAINTY FOR STRUCTURED PREDICTION
text: In this section we develop an ensemble-based uncertainty estimation framework for structured prediction and introduce a novel uncertainty measure. We take a Bayesian viewpoint on ensembles, as it yields an elegant probabilistic framework within which interpretable uncertainty estimates can be obtained. The core of the Bayesian approach is to treat the model parameters θ as random variables and place a prior p(θ) over them to compute a posterior p(θ|D) via Bayes’ rule, where D is the training data. Unfortunately, exact Bayesian inference is intractable for neural networks and it is necessary to consider an explicit or implicit approximation q(θ) to the true posterior p(θ|D) to generate an ensemble. A number of different approaches to generating ensembles have been developed, such as Monte-Carlo Dropout (Gal & Ghahramani, 2016) and DeepEnsembles (Lakshminarayanan et al., 2017). An overview is available in (Ashukha et al., 2020; Ovadia et al., 2019).
Consider an ensemble of models {P(y|x;θ(m))}Mm=1 sampled from an approximate posterior q(θ), where each model captures the mapping between variable-length sequences of inputs {x1, · · · , xT } = x ∈ X and targets {y1, · · · , yL} = y ∈ Y , where xt ∈ {w1, · · · , wV }, yl ∈ {ω1, · · · , ωK}. The predictive posterior is obtained by taking the expectation over the ensemble:
P(y|x,D) = Eq(θ) [ P(y|x,θ) ] ≈ 1
M M∑ m=1 P(y|x,θ(m)), θ(m) ∼ q(θ) ≈ p(θ|D) (1)
The total uncertainty in the prediction of y is given by the entropy of the predictive posterior.
H[P(y|x,D)]︸ ︷︷ ︸ Total Uncertainty = EP(y|x,D)[− ln P(y|x,D)] = − ∑ y∈Y P(y|x,D) ln P(y|x,D) (2)
The sources of uncertainty can be decomposed via the mutual information I between θ and y:
I [ y,θ|x,D ]︸ ︷︷ ︸ Know. Uncertainty =Eq(θ) [ EP(y|x,θ) [ ln P(y|x,θ) P(y|x,D) ]] = Ĥ [ P(y|x,D) ]︸ ︷︷ ︸ Total Uncertainty −Eq(θ) [ Ĥ[P(y|x,θ)] ]︸ ︷︷ ︸ Expected Data Uncertainty (3)
Mutual information (MI) is a measure of ‘disagreement’ between models in the ensemble, and therefore a measure of knowledge uncertainty (Malinin, 2019). It can be expressed as the difference between the entropy of the predictive posterior and the expected entropy of each model in the ensemble.
The former is a measure of total uncertainty and the latter is a measure of data uncertainty (Depeweg et al., 2017). Another measure of ensemble diversity is the expected pairwise KL-divergence (EPKL):
K [ y,θ|x,D ] = Eq(θ)q(θ̃) [ EP(y|x,θ) [ ln
P(y|x,θ) P(y|x, θ̃)
]] q(θ) ≈ p(θ|D) (4)
where q(θ) = q(θ̃) and θ̃ is a dummy variable. This measure is an upper bound on the mutual information, obtainable via Jensen’s inequality. A novel measure of diversity which we introduce in this work is the reverse mutual information (RMI) between each model and the predictive posterior:
M [ y,θ|x,D ] = Eq(θ) [ EP(y|x,D) [ ln
P(y|x,D) P(y|x,θ)
]] , q(θ) ≈ p(θ|D) (5)
This is the reverse-KL divergence counterpart to the mutual information (3), and has not been previously explored. As will be shown in the next section, RMI is particularly attractive for estimating uncertainty in structured prediction. Interestingly, RMI is the difference between EPKL and MI:
M [ y,θ|x,D ] = K [ y,θ|x,D ] − I [ y,θ|x,D ] ≥ 0 (6)
While mutual information, EPKL and RMI yield estimates of knowledge uncertainty, only mutual information ‘cleanly’ decomposes into total and data uncertainty. EPKL and RMI do not yield clean measures of total and data uncertainty, respectively. For details see appendix A.
Unfortunately, we cannot in practice construct a model which directly yields a distribution over an infinite set of variable-length sequences y ∈ Y . Neither can we take expectations over the this set. Instead, autoregressive models are used to factorize the joint distribution over y into a product of conditionals over a finite set of classes, such as words or BPE tokens (Sennrich et al., 2015).
P(y|x,θ) = L∏
l=1
P(yl|y<l,x;θ), xt ∈ {w1, · · · , wV }, yl ∈ {ω1, · · · , ωK} (7)
Here the distribution over each yl is conditioned on all the previous y<l = {y1, · · · , yl−1}, which we shall refer to as the context. This set of conditional independence assumptions allows us to define a model on the finite space YL. This formulation describes all machine translation (Bahdanau et al., 2015; Vaswani et al., 2017), end-to-end speech recognition (Chan et al., 2015) and other related tasks. Alternative factorization orders, representing different conditional independence assumptions, can be considered. However, without loss of generality, we will use the standard factorization.
For these models uncertainty estimation can be examined at two levels - the token level, which considers uncertainty in the prediction of a single yl, and the sequence level, which considers the uncertainty of predicting the entire sequence y. Token-level uncertainty estimation for autoregressive models is isomorphic to un-structured uncertainty estimation with additional conditioning on the context y<l, and so is presented in appendix A.1. Instead, we focus on discussing sequence-level uncertainty estimation in autoregressive models. We have chosen to focus on autoregressive models as they present interesting challenges, are more general than models with stronger conditional independence assumptions, and are widely applied to tasks of practical value. We emphasize that the proposed ensemble-based approach is general and can be applied to structured tasks with different conditional independence assumptions (Graves et al., 2006; Gales & Young, 2008; Gu et al., 2017)

heading: 3 MONTE-CARLO APPROXIMATIONS
text: The key challenge of autoregressive models is that expressions (2)-(5) are intractable to evaluate. Specifically, all expectations over y are intractable to evaluate due to the combinatorial explosion of the hypothesis space - there are a total of |K|L possible L-length sequences in YL, where K is the vocabulary size, and it is necessary to do a forward-pass through the model for each hypothesis. This is an issue which was ignored in prior work (Wang et al., 2019; Fomicheva et al., 2020; Xiao et al., 2019). Clearly, it is necessary to consider Monte-Carlo approximations to make this tractable. A key desiderata of these approximations is that they should be obtainable at no extra cost on top of standard beam-search inference from the ensemble. We examine two types of Monte-Carlo (MC) approximations for expressions (2)-(5) which are identical in the limit, but have different attributes given a finite sample size. Properties of these approximation are detailed in appendix A.
A result of the auto-regressive conditional independence assumption is that distributions over long sequences can have higher entropy than over short ones. To compare uncertainties of sequences of different lengths, in accordance with the desiderata in the introduction, we consider length-normalized ‘rate’ (Cover & Thomas, 2006) equivalents of all uncertainty measures, denoted by ‘∧’. The simplest Monte-Carlo estimation for entropy is to approximate (2) using S samples:
Ĥ(S)S-MC [ P(y|x,D) ] ≈ − 1
S S∑ s=1 1 L(s) ln P(y(s)|x,D), y(s) ∼ P(y|x,D) (8)
where y(s) is a realization of the random variable y. Alternatively, we can approximate (2) as a sum of conditional entropies via the entropy chain-rule (Cover & Thomas, 2006):
Ĥ(S)C-MC[P(y|x,D)] ≈ 1
S S∑ s=1 1 L(s) L(s)∑ l=1 H[P(yl|y(s)<l ,x,D)], ∀y (s) <l ⊂ y (s) ∼ P(y|x,D) (9)
Given a set of consistent contexts y<l ⊂ y ∀l ≤ L, this approximation reduces to averages of token-level uncertainty estimates as a consequence of the entropy chain-rule.
Approximations (8) and (9) both yield exact estimates of total uncertainty (2) in the limit as S →∞. However, (8) only considers the probabilities of individual tokens y(s)l along a hypothesis y
(s), while (9) considers the entire conditional distribution over each yl. Consequently, (9) may yield a more stable approximation using a smaller number of samples. At the same time, while (8) yields a noisier estimate for a finite S, it is more sensitive to the particular set of hypotheses considered.
Monte-Carlo approximations can also be considered for mutual information (3):
Î(S)MC [ y,θ|x,D ] ≈ 1 S S∑ s=1 1 L(s) ln P(y(s)|x,θ(s)) P(y(s)|x,D) , y(s) ∼ P(y|X,θ(s)), θ(s) ∼ q(θ) (10)
Unfortunately, this requires sampling from each model individually - obtaining this estimate does not come ‘for free’ with standard ensemble inference. An efficient approximation can be obtained via the relative-entropy chain-rule (Cover & Thomas, 2006):
Î(S)C-MC [ y,θ|x,D ] ≈ 1 S S∑ s=1 1 L(s) L(s)∑ l=1 I[yl,θ|y(s)<l ,x,D], ∀y (s) <l ⊂ y (s) ∼ P(y|x,D) (11)
Unlike (10), (11) uses samples from the predictive posterior and reduces to averages of token-level mutual information I[yl,θ|y(s)<l ,x,D]. Thus, it is obtained at no extra cost with standard ensemble inference. However, it will not yield (3) as S →∞. Nevertheless, this estimate may still be useful in practice. An approximation K̂(S)C-MC for EPKL (4) with identical properties is described in appendix A. Asymptotically exact joint-sequence and chain-rule MC estimates of knowledge uncertainty can be obtained ‘for free’ during inference from P(y|x,D) by considering the new measure RMI (5):
M̂(S)S-MC [ y,θ|x,D ] ≈ Eq(θ) [ 1 S S∑ s=1 1 L(s) ln P(y(s)|x,D) P(y(s)|x,θ) ] , y(s) ∼ P(y|x,D) M̂(S)C-MC [ y,θ|x,D ] ≈ 1 S S∑ s=1 1 L(s) L(s)∑ l=1 M[yl,θ|y(s)<l ,x,D], ∀y (s) <l ⊂ y (s) ∼ P(y|x,D) (12) (13)
Similar to (9) and (11), (13) is also an average of token-level RMIM[yl,θ|y(s)<l ,x,D], and like (8), (12) is sensitive to a particular set of hypotheses, while (13) is more stable.
Practical Considerations Before applying the proposed Monte-Carlo approximations, two practicalities need to be considered. Firstly, due to the vastness of the hypothesis space YL, Monte-Carlo sampling requires prohibitively many samples and the introduction of a decision rule, whose approximation may require a costly computation and whose effectiveness is not yet fully understood, to find a good set of hypotheses (Eikema & Aziz, 2020; Holtzman et al., 2019). Instead, beam-search
is typically used for inference, as it efficiently finds high-quality hypotheses. With regards to the Monte-Carlo estimators above, beam-search can be interpreted as a form of importance-sampling which yields hypotheses from high-probability regions of the hypothesis space. As each hypothesis is seen only once during beam-search, the uncertainty associated with each hypothesis y(b) within a beam B in the MC estimators above must be importance-weighted in proportion to P(y(b)|x,D).
Ĥ(B)S-IW[P(y|x,D)] ≈ − B∑
b=1
πb L(b) ln P(y(b)|x,D),y(b) ∈ B, πb = exp 1T ln P(y (b)|x,D)∑B k exp 1 T ln P(y (k)|x,D)
Ĥ(B)C-IW[P(y|x,D)] ≈ B∑
b=1 L(b)∑ l=1 πb L(b) H[P(yl|x,y(b)<l ,D)]
(14)
(15)
Note that here we introduce temperature calibration T , which allows us to ‘soft-adjust’ the contribution of the lower-probability hypotheses to the resulting measures of uncertainty. Higher temperature make the importance weights more uniform across the hypotheses. The effects of this are detailed in appendix G. Equivalent expressions for Î(B)C-IW, K̂ (B) C-IW, M̂ (B) S-IW and M̂ (B) C-IW are provided in appendix A.
Second, we must consider how to obtain the predictive posterior for an ensemble of autoregressive models. The models can be combined either as a expectation-of-products or a product-of-expectations:
PEP(y|x,D) = Eq(θ) [ L∏ l=1 P(yl|y<l,x,θ) ] , PPE(y|x,D) = L∏ l=1 Eq(θ) [ P(yl|y<l,x,θ) ] (16)
The former represents sequence-level Bayesian model averaging, while the latter token-level Bayesian model averaging. Both are methods to do model combination3, but only the former is fully consistent with the sequence-level uncertainty measure defined in section 2, as they assume that all tokens in the sequence y are generated from the same θ(m). However, it is not clear a-priori which combination yields superior predictive performance given a set of samples of parameters θ(m) from a particular q(θ) and an inference method. If hypotheses are obtained via beam-search, which is typically a sequence of token-level decisions, considering PPE(y|x,D) may be advantageous. The choice of combination also affects how the token-level predictive posterior P(yl|y(b)<l ,x,D) is obtained:
PEP(yl|y(b)<l ,x,D) = Eq(θ)[P(yl,y (b) <l ,x,θ)]
Eq(θ)[P(y (b) <l ,x,θ)]
, PPE(yl|y(b)<l ,x,D) = Eq(θ)[P(yl|y (b) <l ,x,θ)] (17)
This choice affects measures derived from the sequence and token-level predictive posteriors. However, all measures can still be calculated for both forms at the same time, regardless of which was used for inference. Thus, the choice of combination depends on which yields superior performance.

heading: 4 EXPERIMENTAL EVALUATION
text: The current section provides performance baselines on three applications of structured uncertainty estimates: sequence-level and token-level error detection, and out-of-distribution input (anomaly) detection. Additional analysis is provided in appendices C-J. We also compare performance to prior heuristic ensemble-based approaches. This work only considers ensembles of autoregressive neural machine translation (NMT) and speech recognition (ASR) models generated by training identical models from different random initializations (Lakshminarayanan et al., 2017). This approach was shown to consistently outperform other ensemble generation techniques using exponentially smaller ensembles (Ashukha et al., 2020; Ovadia et al., 2019; Fort et al., 2019). Ensembles of 10 transformerbig (Vaswani et al., 2017) models were trained on the WMT’17 English-to-German (EN-DE) and WMT’14 English-to-French (EN-FR) translation tasks and evaluated on the newstest14 (nwt14) dataset. All models were trained using the configuration described in (Ott et al., 2018b). Ensembles of 6 VGG-Transformer (Mohamed et al., 2019) models were trained on the LibriSpeech (Panayotov et al., 2015) (LSP) ASR dataset. Standard Fairseq (Ott et al., 2019) implementations of all models are used. Details of model configurations are available in appendix B. Note that no comparison is made
3In the current Fairseq (Ott et al., 2019) implementation ensembles are combined as a product-of-expectations.
to supervised uncertainty estimation techniques for NMT/ASR, such as those described in (Liao & Gales, 2007; Koehn, 2009), for two reasons. Firstly, the focus of this work is general, unsupervised uncertainty estimation approaches based on ensemble methods. Secondly, to our knowledge, they have not been applied to autoregressive models and doing so is beyond the scope of this work.
Choice of Ensemble Combination As discussed in section 3, ensembles can be combined as an expectation-of-products (ExPr) or as a product-of-expectations (PrEx) (16). Therefore, it is necessary to evaluate which yields superior predictive performance. We evaluate EN-DE and EN-FR NMT models on newstest14 and the ASR models on LibriSpeech test-clean (LTC) and test-other (LTO).
Results in table 1 show that a product-of-expectations combination consistently yields marginally higher translation BLEU and lower ASR word-error-rate (WER) in beam-search decoding for all tasks4. Beam-width for NMT and ASR models is 5 and 20, respectively. We speculate that this is because beam-search inference, which is a sequence of greedy token-level decisions, benefits more from token-level Bayesian model averaging. At the same time, both combination strategies yield equivalent teacher-forcing mean length-normalized negative-log-likelihood on reference data. This may be because the models in the ensemble yield consistent predictions on in-domain data, in which case the two combinations will yield similar probabilities. Further experiments in this work will use hypotheses obtained from a product-of-expectations ensemble combination, as it yields marginally better predictive performance. Additional analysis and results are available in appendix C.
Sequence-level Error Detection We now investigate whether the sequence-level uncertainty measures can be used to detect sentences which are challenging to translate or transcribe. In the following experiment a model’s 1-best hypotheses are sorted in order of decreasing uncertainty and incrementally replaced by the references. The mean sentence-BLEU (sBLEU) or sentence-WER (sWER) is plotted against the fraction of data replaced on a rejection curve. If the uncertainties are informative, then the increase in sBLEU or decrease in sWER should be greater than random (linear). Rejection curves are summarised using the Prediction Rejection Ratio (PRR) (Malinin, 2019; Malinin et al., 2020), describe in appendix D.2, which is 100% if uncertainty estimates perfectly correlate with sentence BLEU/WER, and 0% if they are uninformative. In these experiments information only from the 1-best hypothesis is considered.5 While the 1-best hypotheses are obtained from a product-ofexpectation combination, we consider uncertainty estimates obtained by expressing the predictive posterior both as a product-of-expectations (ENS-PrEx) and expectation-of-products (ENS-ExPr).
Table 2 shows several trends. First, measures of total uncertainty yield the best performance. Furthermore, joint-sequence estimates of total uncertainty consistently outperform chain-rule based estimates. This is because, unlike chain-rule approximations, joint-sequence approximations do not account for probabilities of non-generated tokens and only consider probabilities along the 1-best hypothesis, and therefore assess its quality. This is consistent with results for unstructuredprediction (Malinin, 2019). Second, measures derived from a product-of-expectation predictive
4BLEU was calculated using sacrebleu (Post, 2018) and WER using sclite. 5Assessment of uncertainty derived from all hypotheses in the beam are analyzed in appendix D.
posterior tend to yield superior performance than their expectation-of-products counterparts. However, this does not seem to be a property of the 1-best hypotheses, as results in appendix D on hypotheses obtained from a expectation-of-products ensemble show a similar trend. Third, out of all measures of knowledge uncertainty, joint-sequence RMI performs best. Finally, the performance gap between chain-rule and joint-sequence estimates of total uncertainty is larger for NMT. This is because compared to ASR, NMT is a task with intrinsically higher uncertainty, and therefore more irrelevant information is introduced by considering the probabilities of non-generated tokens.
The results also show that uncertainty-based rejection works better for ASR than NMT. The issue lies in the nature of NMT - it is inherently difficult to objectively define a bad translation6. While WER is an objective measure of quality, BLEU is only a proxy measure. While a high sBLEU indicates a good translation, a low sBLEU does not necessarily indicate a poor one. Thus, a model may yield a low uncertainty, high-quality translation which has little word-overlap with the reference and low sBLEU, negatively impacting PRR. A better, but more expensive, approach to assess uncertainty estimates in NMT is whether they correlate well with human assessment of translation quality.
Token-level Error Detection We now assess whether token-level uncertainties can be used to detect token-level errors in the models’ 1-best hypotheses. Note that token-level error labelling is ill-posed for translation, where correct tokens can be mislabelled as errors due valid word re-arrangements and substitutions. Thus, token-level error detection is only investigated for ASR. Ground-truth error-labels are obtained by aligning the hypotheses to the references using the SCLITE NIST scoring tool and marking insertions and substitutions7. Performance is assessed via area-under a Precision-Recall curve. Random performance corresponds to the baseline recall, which is equal to the token error rate. Results in table 3 are consistent with the previous section. First, measures of total uncertainty outperform measures of knowledge uncertainty. Second, estimates derived from conditional logscores P of the generated token outperform the entropy H of the token-level predictive posterior. This is because the latter relates to probability of an error at this position, while the former relates to the probability of this particular token being an error. Finally, deriving uncertainties from a product-of-expectation token-level predictive posterior PPE(yl|y(1)<l ,x,D) yields superior results.
Out-of-Domain input Detection We now consider out-of-domain input (anomaly) detection. The goal is use uncertainty estimates to discriminate between in-domain test data and a selection of out-
6Provided that the model is high-performing in general. 7Detecting deletions is, in general, a far more challenging task.
of-domain (OOD) datasets. Performance is assessed via area under a ROC-curve (ROC-AUC), where 100% is ideal performance, 50% is random and below 50% indicates that the model yields lower uncertainty for the OOD data. Results are presented in table 4, additional results in appendices F,G,I.
First, let’s examine OOD detection for speech recognition. Three OOD datasets are considered, each covering a different form of domain shift. First, LibriSpeech test-other (LTO), which represents a set of sentences which are more noisy and difficult to transcribe. Second, the AMI meeting transcription dataset (Kraaij et al., 2005), which represents spoken English from a different domain, mismatched to LibriSpeech, which consist of books being read. Finally, we consider speech in a different language (French), taken from the Common Voice Project (Ardila et al., 2019). The results show that OOD detection becomes easier the greater the domain mismatch. Curiously, there is marginal difference between the performance of measures of uncertainty. This is likely because ASR models tend to be very ‘sharp’ and are naturally more entropic in mismatched conditions.
Now let’s consider OOD detection for WMT’17 English-German machine translation. The following OOD datasets are considered. First, the LibriSpeech test-clean (LTC) reference transcriptions, which are OOD in terms of both domain and structure, as spoken English is structurally distinct from written English. Second, newstest14 sentences corrupted by randomly permuting the source-tokens (PRM). Third, French and German source-sentences from newstest14 (L-FR and L-DE). Results show that discriminating between spoken and written English is challenging. In contrast, it is possible to near-perfectly detect corrupted English. Interestingly, detection of text from other languages is particularly difficult. Inspection of the model’s output shows that the ensemble displays a pathological copy-through effect, where the input tokens are copied to the output with high confidence. As a result, estimates of total uncertainty are lower for the (OOD) French or German data than for (ID) English data. Notably, estimates of knowledge uncertainty, especially reverse mutual information (RMI), M̂(B)C-IW and M̂ (B) S-IW, are affected far less and discriminate between the in-domain and OOD data. This effect true in general, but is especially pronounced when the copy-through effect is triggered. This highlights the value of the RMI, for which asymptotically exact approximations can be obtained.
Clearly, ASR ensembles are better at OOD detection than NMT ensembles. This is expected, as ASR models receive a continuous-valued input signal which contains information not only about the content of the speech, but also the domain, language, speaker characteristics, background noise and recording conditions. This makes the task easier, as the model conditions on more information. This is also why ASR has low intrinsic data uncertainty and why the best OOD detection performance for ASR is obtained using measures of total uncertainty. In contrast, NMT models only have access to a sequence of discrete tokens, which contains far less information. This also highlights the value of knowledge uncertainty, as it disregard the high intrinsic data uncertainty of NMT.
An interesting effect, which is fully explored in appendix G, is that when considering all the hypotheses within the beam for uncertainty estimation, it is beneficial for NMT to use a higher importance-weighting temperature (T = 10), increasing the contribution from competing hypotheses. In contrast, this detrimental for ASR, and temperature is kept at T = 1. We hypothesise that this may be an artifact of the multi-modality of translation - multiple hypotheses could be equally good and contribute valuable information. In contrast, in ASR there is only one correct transcription, though not necessarily the 1-best, and considering competing hypotheses is detrimental.
The results also show that chain-rule and joint-sequence approximations yield similar performance and that, with the exception of M̂(B)S-IW, using information from the full beam yields benefits minor improvements compared during using just the 1-best hypotheses. Uncertainties derived from PEP(y|x,D) and PPE(y|x,D) yield comparable performance, with the exception of mutual information and EPKL, where PEP(y|x,D) yields consistently poorer performance. This suggests that PPE(y|x,D) yields more robust uncertainty estimates. Comparison to heuristic uncertainty measures We close with a comparison of the proposed information-theoretic measures of knowledge uncertainty to the ’heuristic’ measures describes in (Wang et al., 2019; Fomicheva et al., 2020; Xiao et al., 2019). These measures, and our modifications thereof, are detailed in appendix I. We examine the variance of the length-normalized probability and log-probability of hypotheses across the ensemble, as well as the cross-hypothesis WER/BLEU. The use of more than the 1-best hypothesis is our extension for the variance-based measures.
All of these measures aim to evaluate the diversity of ensemble of models in different ways. In this regard they are all measures of knowledge uncertainty. Their main limitations, as originally presented, are the following. All measures focused on the diversity in the probabilities or surface forms of only the 1-best hypothesis. While sufficient in some tasks, such as sequence-error detection, this prevents them from fully capture information about the behavior of the space of possible translations/transcriptions. In this regard, the information theoretic measures presented in our work are an advantage, as they naturally allow to do this. We attempt to address this for the variance-based measures by considering the importance-weighted variance of the probability/log-probability of each hypothesis in the beam. While not strictly rigorous, this nonetheless attempts to address the problem. Such an extension to cross-BLEU/WER is not possible, as it is not clear how to match up different hypotheses across all decodings of each model in the ensemble. Cross-BLEU/WER have the additional limitation of needing a separate decoding of each model in the ensemble, which is undesirable and expensive. Finally, it is likely that there is bias towards longer hypotheses as being more diverse, as there is a greater chance of a surface form mismatch.
The results in table 5 show that information-theoretic measures consistently yield better performance, though sometimes only marginally. Cross-BLEU/WER typically yields the worst performance, especially for NMT. Finally, including information from competing hypotheses can be advantageous for the variance based measures. However, sometimes the performance is degraded - this is because the information was integrated in an adhoc, rather than theoretically meaningful, fashion. We also show in appendix I that length-normalization, which was used inconsistently in prior work, is important both for these measures, and appendix H for the information-theoretic ones.

heading: 5 CONCLUSION
text: This work investigated applying a general, probabilistically interpretable ensemble-based uncertainty estimation framework to structured tasks, focusing on autoregressive models. A range of informationtheoretic uncertainty measures both at the token level and sequence level were considered, including a novel measure of knowledge uncertainty called reverse mutual-information (RMI). Two types of Monte-Carlo approximations were proposed - one based on the entropy chain rule, and the other on sequence samples. Additionally, this work examined ensemble combination through both token-level and sequence-level Bayesian model averaging. Performance baselines for sequence and token-level error detection, and out-of-domain (OOD) input detection were provided on the WMT’14 EnglishFrench and WMT’17 English-German translation datasets, and the LibriSpeech ASR dataset. The results show that ensemble-based measures of uncertainty are useful for all applications considered. Estimates of knowledge uncertainty are especially valuable for NMT OOD detection. Crucially, it was shown that RMI is consistently the most informative measure of knowledge uncertainty for structured prediction. Notably, it was found that token-level Bayesian model averaging consistently yields both marginally better predictive performance and more robust estimates of uncertainty. However, it remains unclear why this is the case, which should be investigated in future work. Future work should also investigate alternative ensemble generation techniques and compare ensemble-based uncertainty estimates to the task-specific confidence-score estimates previously explored for ASR and NMT. Another interesting direction is to assess the calibration of autoregressive ASR models.

heading: A DERIVATIONS OF UNCERTAINTY MEASURES
text: The current appendix details token-level measures of uncertainty for autoregressive models and provides the derivations of the sequence-level measures of uncertainty discussed in section 3 as well as extended discussions of their theoretical properties.

heading: A.1 TOKEN-LEVEL UNCERTAINTY ESTIMATES
text: As was stated in section 2, token-level ensemble-based uncertainty estimates for autoregressive models are isomorphic to un-structured uncertainty estimates (Malinin, 2019). However, for completeness, they are described in the current section.
First, let’s consider the predictive posterior P(yl|y<l,x,D). As discussed in section 3, the token-level predictive posterior of an autoregressive models can be obtained in two ways. One corresponds to token-level Bayesian model averaging, while the other corresponds to sequence-level Bayesian model averaging. The first can be expressed as follows:
P(yl|y<l,x,D) = Eq(θ) [ P(yl|y<l,x,θ) ] = 1
M M∑ m=1 P(yl|y<l,x,θ(m)), θ(m) ∼ q(θ) (18)
While the latter is expressed like so:
P(yl|y<l,x,D) = P(yl,y<l,x,D) P(y<l,x,D = Eq(θ)[P(yl,y<l,x,θ)] Eq(θ)[P(y<l,x,θ] ≈ 1 M
∑ m P(yl,y<l,x,θ
(m)) 1 M ∑ m P(y<l,x,θ (m)) (19)
Clearly, token-level BMA is more consistent with estimating the uncertainty in the prediction of the current token yl, regardless of how the context tokens were generated. In contrast, sequence-level BMA considers how the entire sequence was generated.
Regardless of how the predictive posterior is obtained, the estimate of total uncertainty will be given its entropy:
H [ P(yl|y<l,x,D) ]︸ ︷︷ ︸ Total Uncertainty = − K∑ k=1 P(yl = ωk|y<l,x,D) ln P(yl = ωk|y<l,x,D) (20)
Furthermore, by considering the mutual information between yl and θ we can obtain measures of total uncertainty, knowledge uncertainty and expected data uncertainty:
I [ yl,θ|y<l,x,D ]︸ ︷︷ ︸ Knowledge Uncertainty = Eq(θ) [ EP(yl|y<l,x;θ) [ ln P(yl|y<l,x;θ) P(yl|y<l,x;D) ]] = H [ P(yl|y<l,x,D)
]︸ ︷︷ ︸ Total Uncertainty −Eq(θ) [ H[P(yl|y<l,x;θ)] ]︸ ︷︷ ︸ Expected Data Uncertainty
(21)
Alternatively, the expected pair-wise KL-divergence (EPKL) between models in the ensemble at the token level can also be considered:
K[yl,θ|y<l,x,D]︸ ︷︷ ︸ Knowledge Uncertainty
= Eq(θ)q(θ̃) [ KL[P(yl|y<l,x,θ)||P(yl|y<l,x, θ̃)] ] = EP(yl|y<l,x,D) [ Eq(θ̃)[− ln P(yl|y<l,x; θ̃)] ] − Eq(θ) [ H[P(yl|y<l,x;θ)]
]︸ ︷︷ ︸ Expected Data Uncertainty
(22)
where q(θ) = q(θ̃). This yields an alternative measure of ensemble diversity which is a Jensenderived upper bound on mutual information. Both EPKL and mutual information yield the same estimate of data uncertainty. We can also consider novel measures of diversity, and therefore knowledge uncertainty, called reverse mutual information (RMI)M defined as follows:
M [ yl,θ|y<l,x,D ]︸ ︷︷ ︸ Knowledge Uncertainty = Eq(θ) [ EP(yl|y<l,x;D) [ ln P(yl|y<l,x;D) P(yl|y<l,x;θ) ]] = EP(yl|y<l,x,D) [ Eq(θ)[− ln P(yl|y<l,x;θ)] ] −H [ P(yl|y<l,x,D)
]︸ ︷︷ ︸ Total Uncertainty (23)
This is effectively the reverse-KL divergence counterpart to the mutual information, which is the mean KL-divergence between each model and the predictive posterior. It yields the same estimates of total uncertainty. Just like for the sequence-level measures of uncertainty, it is trivial to derive a relationship between these token-level measures of ensemble diversity:
M [ yl,θ|y<l,x,D ] = K [ yl,θ|y<l,x,D ] − I [ yl,θ|y<l,x,D ] (24)
Thus, RMI is the difference between the EPKL and mutual information. Consequently, while mutual information, EPKL and RMI all yield estimates of knowledge uncertainty, only mutual information ‘cleanly’ decomposes into total uncertainty and data uncertainty. In contrast, EPKL does not yield clean measures of total uncertainty and RMI does not yield clean measures of data uncertainty.
All of these measures of uncertainty considered above use information from the full distribution over tokens yl. However, we can also examine measures which only consider the probability assigned to the predicted token ω̂l. Firstly, we can examine the log-likelihood of the predicted token under the predictive posterior:
P = − ln P(yl = ω̂l|y<l,x,D) (25) This is a measure of total uncertainty. Alternatively, we can consider the mean negative Point-wise Mutual Information (Murphy, 2012) between the model θ(m) and the prediction yl across all models:
Mωl = − Eq(θ) [ ln
P(yl = ω̂l|y<l,x,θ) P(yl = ω̂l|y<l,x,D) ] ︸ ︷︷ ︸
Pointwise Mutual Information
(26)
This is effectively the RMI at the point prediction, rather than an expectation over all classes.
For autoregressive models, these measures represent uncertainty in the prediction given a specific combination of input x and context y<l. However, at the beginning of a sequence token-level measures of uncertainty are more sensitive to the input x and at the end of a sequence become more sensitive to the context y<l.

heading: A.2 DERIVATION OF SEQUENCE-LEVEL MONTE-CARLO APPROXIMATIONS
text: In the current section we detail the derivations of joint-sequence and chain-rule derived Monte-Carlo approximations of sequence-level measures of uncertainty defined in 3. Crucially, they make use of the chain rules of entropy and relative entropy (Cover & Thomas, 2006):
Ĥ[P(y|x,θ)] = 1 L L∑ l=1 EP(y<l|x,θ) [ H[P(yl|x,y<l,θ)] ] K̂L[P(y|x)‖Q(y|x)] = 1
L L∑ l=1 EP(y<l|x) [ KL[P(yl|y<l,x‖Q(yl|y<l,x)]
] (27)
(28)
We omit the derivation for the entropy of the predictive posterior as they are straightforward. Instead, we focus on measures of knowledge uncertainty. First, lets consider a direct joint-sequence MonteCarlo estimate for mutual information:
Î(S) [ y,θ|x,D ] ≈ 1 S S∑ s=1 1 L(s) ln P(y(s)|x,θ(s)) P(y(s)|x,D) , y(s) ∼ P(y|x,θ(s)),θ(s) ∼ q(θ) (29)
Clearly, this is inference inefficient, as it requires independently sampling from each model. As a result, we cannot obtain this estimate of mutual information for free during sampling (or Beam-Search decoding) from the ensemble’s predictive posterior. However, it is possible to obtain an inference efficient approximation by consider the chain rule of relative entropy:
Î [ y,θ|x,D ] = Eq(θ) [ 1 L L∑ l=1 EP(y<l|x,θ) [ KL[P(yl|y<l,x,θ)‖P(yl|y<l,x,D)] ]] (30)
Here, we have expressed mutual information as a sum of expected token-level KL-divergences. However, by replacing the expectation with respect to each individual model by the expectation with respect to the predictive posterior, we obtain the following approximation:
Î [ y,θ|x,D ] ≈ Eq(θ) [ 1 L L∑ l=1 EP(y<l|x,D) [ KL[P(yl|y<l,x,θ)‖P(yl|y<l,x,D)] ]] = 1
L L∑ l=1 EP(y<l|x,D) [ I[yl,θ|y<l,x,D] ] ≈ 1 S S∑ s=1 1 L(s) L(s)∑ l=1 I[yl,θ|y(s)<l ,x,D], ∀y (s) <l ⊂ y (s) ∼ P(y|x,D)
(31)
This reduces to the sum of token-level mutual information along hypotheses drawn from the ensemble’s predictive posterior. However, this approximation will not longer yield equation 3 in the limit as S →∞. Nevertheless, this approximation, while inexact, may still be useful in practice. We can also examine sequence-level EPKL. Similar to the exact Monte-Carlo estimate of mutual information, exact Monte-Carlo estimation for EPKL is also inference in-efficient, as it requires sampling for all models individually:
K̂(S) [ y,θ|x,D ] ≈ 1 S S∑ s=1 1 L(s) ln P(y(s)|x,θ(s)) P(y(s)|x, θ̃(s)) , y(s) ∼ P(y|x,θ(s)),θ(s)∼q(θ), θ̃(s)∼q(θ̃)
(32)
As before, we can use the chain-rule of relative entropy and replace sampling from each individual model with sampling from the predictive posterior:
K̂(S) [ y,θ|x,D ] = Eq(θ)q(θ̃) [ 1 L L∑ l=1 EP(y<l|x,θ) [ KL[P(yl|y<l,x,θ)‖P(yl|y<l,x, θ̃)] ]] ≈ Eq(θ)q(θ̃) [ 1 L L∑ l=1 EP(y<l|x,D) [ KL[P(yl|y<l,x,θ)‖P(yl|y<l,x, θ̃)]
]] = 1
L L∑ l=1 EP(y<l|x,D) [ K[yl,θ|y<l,x,D] ] ≈ 1 S S∑ s=1 1 L(s) L(s)∑ l=1 K[yl,θ|y(s)<l ,x,D], ∀y (s) <l ⊂ y (s) ∼ P(y|x,D)
(33)
This approximation becomes the sum of token-level EPKL along hypotheses generated by the ensemble’s predictive posterior.This approximation will also not yield equation 4 in the limit as S →∞. However, while asymptotically exact inference-efficient Monte-Carlo estimates of sequence-level knowledge uncertainty cannot be obtained via mutual information and EPKL, they can by considering the novel measure RMI equation 5, which defined as an expectation with respect to the predictive posterior. A direct joint-sequence Monte-Carlo approximation can be obtained as follows:
M̂(S) [ y,θ|x,D ] ≈ − Eq(θ) [ 1 S S∑ s=1 1 L(s) ln P(y(s)|x,θ) P(y(s)|x,D) ] , y(s) ∼ P(y|x,D) (34)
Similarly, we can also obtain an asymptotically exact chain-rule approximation:
M̂(S) [ y,θ|x,D ] = Eq(θ) [ 1 L L∑ l=1 EP(y<l|x,D) [ KL[P(yl|y<l,x,D)‖P(yl|y<l,x,θ)] ]] = 1
L L∑ l=1 EP(y<l|x,D) [ M[yl,θ|y<l,x,D] ] ≈ 1 S S∑ s=1 1 L(s) L(s)∑ l=1 M[yl,θ|y(s)<l ,x,D], ∀y (s) <l ⊂ y (s) ∼ P(y|x,D)
(35)
A.3 IMPORTANCE WEIGHTING
As discussed in section 3, beam-search decoding can be interpreted as a form of importance sampling. For the Monte-Carlo approximations for sequence-level measures of uncertainty to be used with beam search, they need to be adjusted such that uncertainty associated with each hypothesis y(b) within the beam B is weighted in proportion to it’s probability:
y(b) ∈ B, πb = exp 1T ln P(y (b)|x,D)∑B k exp 1 T ln P(y (k)|x,D) (36)
All chain-rule derived measures of uncertainty will be expressed as follows:
Ĥ(B)C-IW[P(y|x,D)] ≈ B∑
b=1
πb L(b) L(b)∑ l=1 H[P(yl|x,y(b)<l ,D)]
Î(B)C-IW [ y,θ|x,D ] ≈ B∑ b=1 πb L(b) L(b)∑ l=1 I[yl,θ|y(b)<l ,x,D]
K̂(B)C-IW [ y,θ|x,D ] ≈ B∑ b=1 πb L(b) L(b)∑ l=1 K[yl,θ|y(b)<l ,x,D]
M̂(B)C-IW [ y,θ|x,D ] ≈ B∑ b=1 πb L(b) L(b)∑ l=1 M[yl,θ|y(b)<l ,x,D]
(37)
(38)
(39)
(40)
Joint-sequence measures of uncertainty are similarly modified:
Ĥ(B)S-IW[P(y|x,D)] ≈ − B∑
b=1
πs L(b) ln P(y(b)|x,D)
M̂(B)S-IW[y,θ|x] ≈ Eq(θ) [ B∑ b=1 πs L(b) ln P(y(b)|x,D) P(y(b)|x,θ)
] (41)
(42)

heading: B EXPERIMENTAL CONFIGURATION
text: The current section of the appendix provides both a description of the datasets and details of the models and experimental setups used in this work.

heading: B.1 ASR MODEL CONFIGURATION
text: In this work ensembles of the VGG-Transformer sequence-to-sequence ASR model (Mohamed et al., 2019) were considered. An ensemble of 6 models was constructed using a different seed for both initialization and mini-batch shuffling in each model. We used ensembles of only 6 VGG-Transformer models for inference. We used the Fairseq (Ott et al., 2019) implementation and training recipe for this model with no modifications. Specifically, models were trained at a fixed learning rate for 80
epochs, where an epoch is a full pass through the entire training set. Checkpoints over the last 30 epochs were averaged together, which proved to be crucial to ensuring good performance. Training took 8 days using 8 V100 GPUs. Models were trained on the full 960 hours of the LibriSpeech dataset (Panayotov et al., 2015) in exactly the same configuration as described in (Mohamed et al., 2019). LibriSpeech is a dataset with ∼1000 hours of read books encoded in 16-bit, 16kHz FLAC format. The reference transcriptions were tokenized using a vocabulary of 5000 tokens, as per the standard recipe in Fairseq for the VGG-transformer (Ott et al., 2019; Mohamed et al., 2019). For OOD detection we considered the evaluation subset of the AMI dataset (Kraaij et al., 2005), which is a dataset of meeting transcriptions, as well as the Russian and French datasets of the Common Voice Project (Ardila et al., 2019), which consist of people reading diverse text from the internet. AMI is encoded in 16-bit, 16Khz WAV format. Common Voice data was stored as 24kHz 32-bit MP3 files which were converted into 16-bit 16kHz WAV format via the SOX tool. WER was evaluated using the NIST SCLITE scoring tool.

heading: B.2 NMT MODEL CONFIGURATION
text: This work considered ensembles of Transformer-Big (Vaswani et al., 2017) neural machine translation (NMT) models. An ensemble 10 models was constructed using a different seed for both initialization and mini-batch shuffling in each model. NMT models were trained on the WMT’14 English-French and WMT’17 English-German datasets. All models were trained using the standard Fairseq (Ott et al., 2019) implementation and recipe, which is consistent with the baseline setup in described in (Ott et al., 2018b). The data was tokenized using a BPE vocabulary of 40,000 tokens as per the standard recipe (Sennrich et al., 2015). For each dataset and translation direction an ensemble of 10 models was trained using different random seeds. All 10 models were used during inference. Models trained on WMT’17 English-German were trained for 193000 steps of gradient descent, which corresponds to roughly 49 epochs, while WMT’14 English-French models were trained for 800000 steps of gradient descent, which corresponds to roughly 19 epochs. Models were checkpoint-averaged across the last 10 epochs. All models were trained using mixed-precision training. Models were evaluated on newstest14, which was treated as in-domain data. OOD data was constructed by considering
BPE-token permuted and language-flipped versions of the newstest14 dataset. Furthermore, the khresmoi-summary medical dataset as well the reference transcriptions of the LibriSpeech test-clean and test-other datasets were also used as OOD evaluation datasets. All additional datasets used consistent tokenization using the 40K BPE vocabulary.

heading: C PREDICTIVE PERFORMANCE ABLATION STUDIES
text: The current section provides additional results assessing the predictive-performance and negative log-likelihood of ensembles of autoregressive NMT and ASR models. Additionally, we include an ablation study of how the number of models in an ensemble affects the performance in terms of BLEU and NLL. Tables 8 and 9 include expanded set of results. Crucially the results show that for all languages, tasks and datasets a product-of-expectations yields superior performance (with one exception) in beam-search decoding and and a consistently lower NLL on reference transcriptions and translations.
Finally, we present an ablation study, which shows how the predictive performance varies with the number of models in an ensemble. The ablation shows several trends. Firstly, both BLEU/WER and NLL begin to shown diminishing returns for using more models. This suggests that using 4-6 NMT models and 2-3 ASR models will allow most of the gains to be derived at half the cost of a full 10 or 6-model ensemble. Secondly, it shows that the advantage of a product-of-expectations combination is remains consistent with the number of models. This shows that regardless of the number of models available, it is always better to combine as a product-of-expectations.

heading: D SEQUENCE-LEVEL ERROR DETECTION
text: The current appendix provides a description of the Prediction Rejection Ratio metric, the rejection curves which correspond to results in section 4, and histograms of sentence-WER and sentence-BLEU which provide insights into the behaviour of the corresponding rejection curves.

heading: D.1 PREDICTION REJECTION RATIO
text: Here we describe the Prediction Rejection Ratio metric, proposed in (Malinin, 2019; Malinin et al., 2017), which in this work is used to assess how well measures of sequence-level uncertainty are able to identify sentences which are hard to translate/transcribe. Consider the task of identifying misclassifications - ideally we would like to detect all of the inputs which the model has misclassified based on a measure of uncertainty. Then, the model can either choose to not provide any prediction for these inputs, or they can be passed over or ‘rejected’ to an oracle (ie: human) to obtain the correct prediction (or translation/transcription). The latter process can be visualized using a rejection curve depicted in figure 4, where the predictions of the model are replaced with predictions provided by an
oracle in some particular order based on estimates of uncertainty. If the estimates of uncertainty are uninformative, then, in expectation, the rejection curve would be a straight line from base error rate to the lower right corner, given the error metric is a linear function of individual errors. However, if the estimates of uncertainty are ‘perfect’ and always bigger for a misclassification than for a correct classification, then they would produce the ‘oracle’ rejection curve. The ‘oracle’ curve will go down linearly to 0% classification error at the percentage of rejected examples equal to the number of misclassifications. A rejection curve produced by estimates of uncertainty which are not perfect, but still informative, will sit between the ‘random’ and ‘oracle’ curves. The quality of the rejection curve can be assessed by considering the ratio of the area between the ‘uncertainty’ and ‘random’ curves ARuns (orange in figure 4) and the area between the ‘oracle’ and ‘random’ curves ARorc (blue in figure 4). This yields the prediction rejection area ratio PRR:
PRR = ARuns ARorc
(43)
A rejection area ratio of 1.0 indicates optimal rejection, a ratio of 0.0 indicates ‘random’ rejection. A negative rejection ratio indicates that the estimates of uncertainty are ‘perverse’ - they are higher for accurate predictions than for misclassifications. An important property of this performance metric is that it is independent of classification performance, unlike AUPR, and thus it is possible to compare models with different base error rates. Note, that similar approaches to assessing misclassification detection were considered in (Lakshminarayanan et al., 2017; Malinin et al., 2017; Malinin, 2019). In this work instead of considered misclassifications we assess whether measures of uncertainty correlate well with sentence-level BLEU or WER. The overall ‘error’ is then the average of sentence-level BLEU/WER over the test-set.

heading: D.2 REJECTION CURVES
text: The rejection curves for all NMT models on newstest14 and the ASR model on LibriSpeech test-clean and test-other are presented in figure 5. The main difference between the NMT and ASR curves is that the ‘oracle’ rejection curve for the former is not much better than random, while the rejection curve for the latter is far better than random. This can be explained by considering the histograms of sentence-level BLEU and sentence-level WER presented in figure 6. Notice, that the sentence-level BLEUs are varied across the spectrum, and very few sentences reach a BLEU of 100. In contrast, 55-75% of all utterances transcribed by the ASR models have a sentence-WER of 0-10%, and then there are a few utterances with a much larger WER. Thus, if the measures of uncertainty can identify the largest errors, which contribute most to the mean WER over the dataset, then a large decrease can be achieved. Hence the shape of the ‘oracle’ WER-rejection curve. In contrast, the contributions from each sentence to mean sentence-BLEU are more evenly spread. Thus, it is difficult to significantly raise the mean-sentence BLEU by rejecting just a few sentences. Hence the shape of the ‘oracle’ BLEU rejection curve for NMT.
Figure 6e shows that the sentence-WER on AMI eval is distributed more like the sentence-BLEU is for NMT tasks - few correct sentence and a much more uniform distribution of error. Thus, the corresponding ‘oracle’ rejection curve’s shape is more similar to the NMT ‘oracle’ rejection curves. This clearly shows that the shape of the oracle curve is not determined by the task (ASR/NMT), but the error (BLEU/WER) distribution across a dataset.
The second trend in the results provided in section 4 is that score-based measures of uncertainty work better than entropy-based measures on NMT tasks, while on ASR they perform comparably. The justification provided states that NMT models yield far less confident predictions, and therefore entropy-based measures suffer due to probability mass assigned to other tokens. In contrast, ASR
models yield more confident predictions, as shown in figure 7. Notably, on AMI and Common Voice datasets the ASR model also yields less confident predictions, and thus the score-based measures of uncertainty do better than entropy-based ones in the AMI rejection curve in figure 5e. These results show that on tasks where it is important to determine which particular translation/transcription hypotheses are worse, score-based measures of uncertainty do as well as or better than entropybased measures. This result is consistent with confidences being a better measure of uncertainty for misclassification detection in unstructured prediction tasks (Malinin, 2019).

heading: D.3 ADDITIONAL RESULTS
text: The current section provides additional sequence-level error detection results. We examine sequencelevel error detection of hypotheses produced by an ensemble combined as an expectation-of-products. Results presented in table 10 serve to confirm the previously observed trends and illustrate that the superior performance of measures of uncertainty derived from an product-of-expectations posterior does not depend on the nature of the hypotheses.

heading: E TOKEN-LEVEL ERROR DETECTION
text: Current appendix provides additional results for token-level error detection. Notably, we present results using a score-based measures of knowledge uncertaintyMωl , as well as results on hypotheses derived from an expectation-of-products ensemble combination. Results in table 11 that the new measures of uncertainty consistently outperforms token-level mutual-information and RMI.
Results in table 12 show that the observed trends do not depend from which ensemble-combination the hypotheses were obtained.

heading: F OUT-OF-DISTRIBUTION INPUT DETECTION
text: In the current section additional OOD input detection results are provided for En-De and En-Fr NMT models and the ASR model in a Beam-Search decoding regime. Additionally, we provide results for En-De and En-Fr models on reference hypotheses in a teacher-forcing regime.

heading: F.1 ADDITIONAL RESULTS
text: Table 13 provides a full of OOD detection results using an ensemble of EN-FR translation models. All hypotheses are derived from a product-of-expectations ensemble. These results tell essentially the same story as OOD detection on En-De models. However, it seem that because WMT’14 En-Fr is roughly ten times larger than WMT’17 En-Fr, OOD detection in some cases, notably LTC, PRM and L-FR is easier. However, L-DE are significantly worse. Note that for En-FR, L-DE is the heldout language, while L-FR is more familiar. One explanation is that the copy-through effect is so strong on an unfamiliar language that even measures of knowledge uncertainty are drastically affected. This suggests that it is necessary to eliminate this regime, as it strongly compromises the measures of uncertainty.
Table 14 provides a full set of OOD detection results on hypotheses generated from an ensemble combined as an expectation-of-products. The results essentially tell the same story those obtained on hypotheses generated from an ensemble combined as a product-of-expectations. This confirms the trend that measures of uncertainty derived by expressing the predictive posterior as a productof-expectations typically yield marginally better performance, with expceptions where they yield significantly better performance, regardless of the nature of the hypotheses.

heading: F.2 TEACHER-FORCING
text: Table 15 provides a set of OOD detection results for EN-DE/EN-FR translation models evaluated in a teacher-forcing regime, where ‘references’ are fed into the decoder. The aim is to further explore
OOD detection of foreign languages and the copy-through effect. Here, in-domain data is En-De and En-Fr newstest14 for En-De and En-Fr models, respectively. As OOD data we also consider newstest14 data, but where the either source, target or both languages are changed. The results show that when the source and target languages are both changed (L-DEEN, L-FREN), then this is an easy to detect scenario, as copy-though is forcibly avoided. We also consider situations where we forcibly initiate copy-through. Here, we have matched pairs of source-source or target-target language. Measures of total uncertainty fail, while measures of knowledge uncertainty do not. However, the effect is more severe when source sentences are copied through, rather than target sentences. We speculate that this is an affect of the decoder being familiar with target sentences and still trying to do something sensible. These results clearly show that if the copy-through effect is somehow eliminated, then detection of OOD sentences by NMT models because as easy as for ASR models, where copy-though cannot occur by construction. Finally, we note that again, deriving uncertainties from a product-of-expectations predictive posterior yields marginally better results. Additionally, chain-rule RMI seems to be the best measures of knowledge uncertainty overall. Note that in teacher-forcing, we have access to only a single hypothesis per input, which is a regime where joint-sequence estimates of knowledge uncertainty, specifically RMI, tend to perform worse than chain-rule derived estimates.

heading: G SENSITIVITY OF MC ESTIMATORS TO NUMBER OF SAMPLES AND CALIBRATION
text: In this section we explore in detail the effect of using more than the 1-best hypothesis in the MonteCarlo estimation of entropy and reverse mutual information (RMI). We consider both chain-rule and joint-sequence estimators. Performance is evaluated on the tasks of sequence error detection and OOD detection. Figure 8 shows that for sequence error detection using more hypotheses within the beam either has little effect, or is detrimental. This is expected, as this makes the estimate less sensitive to the particular hypothesis which is being assessed. Notable, joint-sequence estimates are affected the most, while chain-rule estimators demonstrate more stable behaviour.
Figure 8 shows that considering more hypotheses is generally beneficial for OOD detection, especially for joint-sequence estimates of RMI. This is also expected, as for OOD detection it is useful to have information about the effect of the input on more than just the 1-best hypothesis. The performance gain is, ultimately, unsatisfying.
We consider what happens if we increase the importance weighting temperature T, which increases the contribution for the remaining hypotheses to the uncertainty estimate. Figure 10 shows, unsurprisingly that this is extremely detrimental to sequence error detection, as it introduce even more irrelevant information. However, figure 11 shows that for OOD detection, the is unexpectedly interesting behaviour. Using higher temperature for NMT always leads to significantly performance, especially for joint-sequence estimates of RMI. However, what is especially surprising, is that for ASR the OOD detection performance degrades. It is not entirely clear why up-weighting information from competing hypotheses is detrimental to performance. Unfortunately, investigating the underlying cause of this effect is beyond the scope of this work. Ultimately, it suggests that analysis of the calibration of autoregressive structured prediction models is an interesting area of future research.

heading: H EFFECTS OF LENGTH-NORMALIZATION
text: In section 3 we make the claim that length-normalization in important - in this section we provide evidence in support of that claim. Here we compare sequence error detection and OOD detection performance for WMT’17 EN-DE NMT and LibriSpeech ASR systems when using the standard length-normalized versions of the uncertainties as well as their non-length-normalized counterparts. In these experiments we only consider translation/transcription hypotheses obtained via beam-search decoding from a product-of-expectations ensemble, and uncertainty measures obtained using the same combination approach.
The results in tables 16-17 definitively show, with one exception, that length-normalization consistently boosts the performance on all tasks. The only exception in for OOD detection when French (L-FR) input sentences are given to the ensemble. In this case there is a large improvement from not using length normalization. This seems odd, given than when German input sentences are using (in and En-De system) the same effect does not appear. Not that in both of these cases the pathological copy-through effect appears. However, it seems likely that the copy-through effect is far more pronounced for L-FR. The likely reason for length-norm proving detrimental is for long sentences - as the length of the translation increases, so does the chance of a token which is not copied successfully, on which the models will yield a far higher estimate of ensemble diversity. Length-normalization would mask such an effect relative.

heading: I COMPARISON TO HEURISTIC MEASURES OF UNCERTAINTY
text: In this work we considered a range of information-theoretic measures of uncertainty, describe them theoretically in section 2 and provide Monte-Carlo estimators in section 3. However, in (Xiao et al., 2019; Fomicheva et al., 2020; Wang et al., 2019) a range of other measures was considered, though their properties were not analyzed. Firstly, (Xiao et al., 2019) considered computing the cross-BLEU or ’BLEU-Variance‘ of an ensemble. Here, the average square of the complement of pairwise sentence-BLEU between 1-best hypotheses ŷ(m) produced by each individual model in the ensemble is used as a measure of uncertainty:
X-BLEU = 1
M(M − 1) M∑ m=1 M∑ q 6=m ( 100− BLEU(ŷ(m), ŷ(q)) )2 (44)
Similarly, an equivalent measure of ASR can be derived, which we will call cross-WER:
X-WER = 1
M(M − 1) M∑ m=1 M∑ q 6=m ( WER(ŷ(m), ŷ(q)) )2 (45)
These two measure of uncertainty assess the diversity between the 1-best hypotheses of each model in an ensemble. In this way they are conceptually related to measures of knowledge uncertainty. Notably, as they are only sensitive to the 1-best hypothesis, they are ‘hard’ versions of ensemble diversity, as they operate on the surface forms, rather than over probabilities. While a heuristically sensible measure, the main detraction is that this requires doing beam-search inference of each model in an ensemble, which is expensive and undesirable. Especially if the final prediction is derived through inference of the joint-ensemble.
Additionally, Fomicheva et al. (2020); Wang et al. (2019) consider the variance of the sentencelevel probability and length-normalized log-probability of the 1-best hypothesis across models in an ensemble:
V[P ] = Vq(θ) [ P(y1-best|x,θ) ] V̂[lnP ] = Vq(θ) [ 1 L ln P(y1-best|x,θ) ] (46) (47)
These are also measures of diversity, and therefore knowledge uncertainty. However, they are not strictly information-theoretically meaningful and it is not how to relate them to concepts, such as entropy. Given these two measures, it is unclear how to include information from other hypotheses and whether length-normalization is necessary. First we address the latter - we consider a lengthnormalized version of variance, and the non-length-normalized variance of the log-probability.
V̂[P ] = Vq(θ) [ P(y1-best|x,θ) 1 L ] V[lnP ] = Vq(θ) [ ln P(y1-best|x,θ) ] (48) (49)
(50)
Secondly, we extend all four of these measures to average variances of the hypotheses within the beam as follows:
V(B)[P ] = B∑
b=1
πbVq(θ) [ P(y(b)|x,θ) ] , y(b) ∈ B
V̂(B)[P ] = B∑
b=1
πbVq(θ) [ P(y(b)|x,θ) 1 L(b) ] , θ) ] ,y(b) ∈ B
V(B)[lnP ] = B∑
b=1
πbVq(θ) [ ln P(y(b)|x,θ) ] ,θ) ] , y(b) ∈ B
V̂(B)[lnP ] = B∑
b=1
πbVq(θ) [ 1 L(b) ln P(y(b)|x,θ) ] ,θ) ] , y(b) ∈ B
(51)
(52)
(53)
(54)
Thus, we explore the effect of considering additional hypotheses and whether these measures need length-normalization or not.
Table 18 explores the utility of these uncertainty measures and compares them to the best-performing measures of knowledge uncertainty uncertainty - reverse mutual information on the task of OOD input detection. The results show that, with one exception, estimates of reverse mutual information outperform these ‘heuristic’ measures. With regards to the measures - it is clear that length-normalization, with one exception, improves performance. We can also see that these heuristic measures can be improved by considering importance-weighted averages across the hypotheses within the beam. However, these gains are inconsistent, and sometimes this is detrimental. This highlights both the value of information theoretic measures, whose behaviour is far more consistent.

heading: J CHECKPOINT ENSEMBLES
text: This work focused mainly on ensemble of models constructed by training from different random initializations. While this tends to yield the best ensembles, this is an extremely expensive process, especially for large transformer models trained on industrial scale corpora. Thus, in this section we conduct a preliminary investigation of checkpoint ensembles - ensembles of models constructed by considering different checkpoints within a single training run. In this work we consider the checkpoints for the 10 last epochs for NMT model training. For ASR, we checkpoint average 5 checkpoints at 5-checkpoint intervals within the last 30 epochs, yielding an ensemble of 6 checkpoints, where each is an average of five checkpoints. Results in tables 19-20 shows that checkpoint ensemble yield better predictive performance than single models (CPT-AVG), on average. However, random-init ensembles (those considered in the main work), yield consistently superior performance.
We also compare checkpoint ensembles with random-init ensembles of OOD detection. The results, which are a pleasant surprise, show that while checkpoint ensembles are consistently inferior, they are only marginally so. The biggest differences occur on NMT L-FR and L-DE datasets, where the pathological ’copy-through’ effect kicks in. However, even here the difference between the best CPT-ENS and RND-ENS measures is only about 6% ROC-AUC points. This shows that the approach considered in this work need to be too expensive for practical application, and useful ensembles can
be formed even from the last 10 checkpoints of a standard transformer model training run, enabling usage in extreme-scale industrial applications.

Review summaries:
This paper proposes two different measures of knowledge (epistemic) uncertainty in structured prediction with an autoregressive model and discusses how to compute their approximations. The main contribution is the proposed reverse mutual information (RMI) as a measure of epistemic uncertainty in structured prediction. Experiments on benchmark datasets demonstrate the effectiveness of the proposed method in error detection and OOD detection.

This work introduce rigorous information-theoretic measures for structured prediction tasks. It proposed metrics for both `"total uncertainty" (entropy) and "knowledge uncertainty" (MI, EPKL and RMI) on the sequence level, introduced efficient Monte-Carlo approaches to estimate them in practice. Finally, author conducted thorough experiment to evaluate the effect of ensemble strategy and choice of metric for error detection and OOD detection in ASR and NMT.