Uncertainty Determines the Adequacy of the Mode and the Tractability of Decoding in Sequence-to-Sequence Models

Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 8634 - 8645 May 22-27, 2022 c⃝2022 Association for Computational Linguistics Uncertainty Determines the Adequacy of the Mode and the Tractability of Decoding in Sequence-to-Sequence Models Felix Stahlberg1 and Ilia Kulikov2∗and Shankar Kumar1 1Google Research, 2New York University {fstahlberg, shankarkumar}@google.com, ik1147@nyu.edu Abstract In many natural language processing (NLP) tasks the same input (e.g. source sentence) can have multiple possible outputs (e.g. transla- tions). To analyze how this ambiguity (also known as intrinsic uncertainty) shapes the dis- tribution learned by neural sequence models we measure sentence-level uncertainty by com- puting the degree of overlap between refer- ences in multi-reference test sets from two dif- ferent NLP tasks: machine translation (MT) and grammatical error correction (GEC). At both the sentence- and the task-level, intrinsic uncertainty has major implications for various aspects of search such as the inductive biases in beam search and the complexity of exact search. In particular, we show that well-known pathologies such as a high number of beam search errors, the inadequacy of the mode, and the drop in system performance with large beam sizes apply to tasks with high level of ambiguity such as MT but not to less uncer- tain tasks such as GEC. Furthermore, we pro- pose a novel exact n-best search algorithm for neural sequence models, and show that intrin- sic uncertainty affects model uncertainty as the model tends to overly spread out the probabil- ity mass for uncertain tasks and sentences. 1 Introduction With the advent of deep learning, many applica- tions of machine learning have converged on a similar set of methods and models. For example, the Transformer (Vaswani et al., 2017) sequence- to-sequence architecture is ubiquitous in various fields of natural language processing (NLP) such as machine translation (MT), grammatical error correction (GEC), speech recognition (Karita et al., 2019), etc., and has also been applied successfully to other tasks such as computer vision (Dosovitskiy et al., 2021). Recent large pre-trained NLP models ∗ Research done during internship at Google Research, now at Meta AI. such as BERT (Devlin et al., 2019), GPT-3 (Brown et al., 2020), T5 (Raffel et al., 2020), RoBERTa (Liu et al., 2019), and XLNet (Yang et al., 2019) are all based on the Transformer, with relatively minor changes to the architecture itself. We show that despite this architectural unifor- mity the learned distribution over sequences has strikingly different characteristics for different NLP tasks. Inspired by Ott et al. (2018) we identify in- trinsic uncertainty – the nature of some NLP tasks to allow multiple viable outputs for a given input1 – to be a major factor that shapes the search space of Transformer models and determines its tractability. In machine translation (MT) – a task known to have high intrinsic uncertainty (Padó et al., 2009; Dreyer and Marcu, 2012; Ott et al., 2018) – Transformer models suffer from a high number of beam search errors (Stahlberg and Byrne, 2019), an inadequacy …

Content truncated to 500 words