Uncertainty in Structured Prediction

Andrey Malinin, Mark J. F. GalesarXiv 2020 · arXiv

Introduction

Deploying neural networks in safety-critical applications requires models that not only provide accurate predictions but also a reliable estimate of their own confidence. While uncertainty estimation is well-established for unstructured tasks like image classification, it remains a significant challenge for structured prediction tasks such as Neural Machine Translation (NMT) and Automatic Speech Recognition (ASR). The primary difficulty lies in the combinatorial explosion of the output space; calculating exact uncertainty over an exponentially large number of possible sequences is mathematically intractable.

This paper introduces a unified, probabilistically interpretable framework for estimating uncertainty in sequence-to-sequence models. By leveraging Deep Ensembles and introducing a novel metric called Reverse Mutual Information (RMI), the authors provide a mathematically grounded method to detect model errors and out-of-domain (OOD) inputs without requiring task-specific, supervised heuristics.

Methodology: Decomposing Uncertainty

The authors adopt a Bayesian approach using Deep Ensembles—training multiple identical models with different random initializations. This allows for the decomposition of total uncertainty into two distinct components:

  1. Data Uncertainty: The inherent noise or ambiguity in the task itself (e.g., a muffled audio clip in ASR).
  2. Knowledge Uncertainty: The model's ignorance resulting from a lack of representative training data, which is essential for detecting anomalies.

To address the intractability of the sequence space, the framework utilizes Monte-Carlo (MC) approximations that integrate with standard beam-search decoding. By treating beam-search as a form of importance sampling, uncertainty estimates are obtained with minimal additional computational overhead during inference.

Conceptual comparison of information-theoretic uncertainty measures: (a) Mutual Information, (b) Reverse Mutual Information, and (c) Expected Pairwise KL.

A core contribution of this work is Reverse Mutual Information (RMI). Unlike standard Mutual Information, RMI measures the reverse-KL divergence between each individual ensemble model and the predictive posterior. As illustrated in Figure 1, this directional shift provides a more robust measure of knowledge uncertainty, particularly effective for identifying when a model is operating outside its training distribution.

Experimental Setup and Insights

The framework was evaluated across diverse datasets and tasks:

  • NMT: Models were trained on WMT datasets and tested on newstest14, with OOD scenarios including permuted text and foreign language inputs.
  • ASR: Models were trained on LibriSpeech and tested against the AMI meeting corpus (mismatched acoustic domain) and Common Voice French (mismatched language).

Key Insights

  • Token-Level Averaging: The study compared two ensemble combination strategies: sequence-level ("expectation-of-products") and token-level ("product-of-expectations"). Surprisingly, token-level averaging consistently yielded superior predictive performance and more robust uncertainty estimates.
  • RMI for Anomaly Detection: In NMT, models often exhibit a "copy-through" effect when encountering foreign languages, confidently outputting the input text. While standard metrics fail to flag this, RMI successfully identifies these inputs as OOD because the ensemble models disagree on the underlying representation, even if the final output appears confident.
  • ASR vs. NMT Robustness: ASR models naturally outperformed NMT models in OOD detection. This is attributed to the rich, continuous context of audio signals compared to the sparse, discrete nature of text tokens.

Results

The proposed information-theoretic metrics consistently outperformed prior heuristic baselines, such as the variance of log-probabilities or cross-hypothesis BLEU/WER.

Out-of-distribution detection performance (AUC-ROC %) across various tasks and datasets, highlighting the effectiveness of RMI (denoted as M).

As shown in Figure 5, Knowledge Uncertainty (specifically RMI) dominated in OOD detection tasks. For instance, RMI achieved up to 96-98% ROC-AUC in detecting permuted English text in NMT models. For error detection, total uncertainty measures (joint-sequence estimates) proved to be the best predictors, correlating strongly with BLEU and WER scores.

Conclusion and Future Work

This work provides a rigorous foundation for uncertainty in structured prediction. The introduction of RMI offers a powerful tool for anomaly detection, while the discovery that token-level averaging outperforms sequence-level methods opens new theoretical questions. Future research will explore the underlying causes of calibration differences between ASR and NMT and investigate more computationally efficient ensemble techniques, such as checkpoint ensembling, to make these methods more accessible for large-scale industrial models.

Summary updated

Abstract

Uncertainty estimation is important for ensuring safety and robustness of AI systems. While most research in the area has focused on un-structured 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 sequence-level out-of-domain input detection on the WMT'14 English-French and WMT'17 English-German translation and LibriSpeech speech recognition datasets.
BibTeX
@misc{malinin2020uncertainty,
  author = {Andrey Malinin and Mark J. F. Gales},
  title = {{Uncertainty in Structured Prediction}},
  year = {2020},
  eprint = {2002.07650},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.07650},
}
Figure