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

Abstract: In many natural language processing (NLP) tasks the same input (e.g. source sentence) can have multiple possible outputs (e.g. translations). To analyze how this ambiguity (also known as intrinsic uncertainty) shapes the distribution learned by neural sequence models we measure sentence-level uncertainty by computing the degree of overlap between references in multi-reference test sets from two different 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 uncertain tasks such as GEC. Furthermore, we propose a novel exact n-best search algorithm for neural sequence models, and show that intrinsic uncertainty affects model uncertainty as the model tends to overly spread out the probability mass for uncertain tasks and sentences.

## introduction with the advent of deep learning, many applications of machine learning have converged on a similar set of methods and models. for example, the transformer @xcite sequenceto-sequence architecture is ubiquitous in various fields of natural language processing (nlp) such as machine translation (mt), grammatical error correction (gec), speech recognition @xcite , etc., and has also been applied successfully to other tasks such as computer vision @xcite . recent large pre-trained nlp models such as bert @xcite , gpt-3 @xcite , t5 @xcite , roberta @xcite , and xlnet @xcite are all based on the transformer, with relatively minor changes to the architecture itself. we show that despite this architectural uniformity the learned distribution over sequences has strikingly different characteristics for different nlp tasks. inspired by @xcite we identify intrinsic uncertainty -the nature of some nlp tasks to allow multiple viable outputs for a given input foot_0 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 @xcite @xcite -transformer models suffer from a high number of beam search errors @xcite , an inadequacy of the mode @xcite , and translation performance degradation with large beam sizes @xcite (also known as the "beam search curse"). in contrast, for the correction of writing errors in text (grammatical error correction -gec) @xcite , a task with a lower level of uncertainty @xcite , none of these pathologies are evident. this pattern holds even at the sequence-level: input sentences with high uncertainty tend to result in more search errors and a less tractable search space. to study the influence of uncertainty on sequences around the mode, we propose an exact n-best search algorithm for neural sequence models. we show that the probability mass covered by the n-best candidates differs markedly between certain and uncertain tasks and sentences, which shows that intrinsic uncertainty also affects the spread of probability mass and thus the model uncertainty. we confirm recent work showing that beam search has drawbacks as a decoding scheme for mt. nevertheless, it is effective for gec, a problem where modes are adequate, search errors are rare, and the n-best lists cover a large fraction of the probability mass. ## measuring intrinsic uncertainty intrinsic uncertainty refers to the inherent nature of some nlp tasks to allow for more than one feasible output for a given input. for example, intrinsic uncertainty in mt stems from the fact that there are often several semantically equivalent translations for the same source sentence, or that the translation into a highly inflected language is sometimes underspecified @xcite . studies have shown that even for tasks like gec, annotators do not always agree @xcite @xcite , but the level of intrinsic uncertainty is arguably lower than for mt because there is a limited number of ways to correct an ungrammatical sentence. we propose a simple way to measure sentencelevel output uncertainty by making use of multireference test sets. for an n-way annotated sentence with references y 1 , ..., y n we define the uncertainty u as the average relative edit distance between two references: ## mode-seeking search neural sequence-to-sequence models define a probability distribution p (y|x) over target sequences y given a source sequence x: sequences are typically computed over a subword @xcite vocabulary v and end with a special end-of-sentence @xmath0: input: n: search for n global best sequences x: source sequence y: target prefix (default: ) p: log p (y|x) (default: 0.0) γ: lower bound (default: -∞) ỹ : priority queue (default: ∅) 1: if y |y| = </@xmath1: ỹ .push((p, y)) ## n -best search in addition to our investigations into the mode we also examine the cumulative probability mass that is covered by the n best hypotheses. if a hypothesis set covers a large fraction of the entire probability mass it approximates the full model distribution well. approximating the full model distribution is useful for various methods such as minimum risk training @xcite , reinforcement learning @xcite , minimum bayes risk decoding @xcite @xcite , etc. @xcite argued that the fraction of probability mass which is covered by a fixed number of candidates reflects the model uncertainty on the sequence level. we show that this model uncertainty is in line with our notion of intrinsic uncertainty that we measure with u (sec. 2). to that end, we propose a generalization of the exact search algorithm of @xcite that is able to find the n global best hypotheses rather than the single best one. similarly to the single-best algorithm, we use the monotonicity of neural sequence model scores: in contrast, we keep track of the n-th best complete hypothesis score by keeping the n best complete hypotheses in a priority queue. our exact n-best search algorithm is listed in algorithm 1. note that we recover the dfs scheme of @xcite with @xmath3. ## experimental setup we trained four transformer neural machine translation (nmt) models ( ## results in this work our focus is to analyze the impact of intrinsic uncertainty on search. thus we keep our setup simple, reproducible, and computationally economical rather than obtain new state-of-the-art results. nevertheless, tables 3 and 4 show that our baselines are not unreasonably far off from the best results in the literature given that the systems we compare with are often highly engineered and use many more parameters. xia et al. (2019) used various techniques like back-translation, ensembling, dual learning, mass pre-training, architecture search, larger models, etc. to improve their systems, and rothe et al. (2021) used a 11b parameters t5 (raffel et al., 2020) model. ## related work ambiguity is one of the core challenges in mt, a fact that is supported (inter alia) by the long history of designing evaluation metrics that are robust against it @xcite @xcite . in this work we examine the impact of ambiguity on the nmt search space, and show how it is related to various wellknown issues of nmt models like the beam search curse @xcite , a pathology that has also been linked to the local normalization in sequence models @xcite or poor model calibration @xcite . our work is heavily inspired by @xcite who analyzed different kinds of uncertainty in nmt. in particular, they found that nmt spreads out the probability mass over a large number of candidates, and connected the beam search curse with uncertainty. we confirm their results and extend their line of research along the following directions: we introduce a measure for uncertainty in multi-reference test sets, and show that the negative effects of uncertainty are visible even on the sentence level. second, we propose an exact nbest search algorithm and demonstrate how it can be used to analyze the spread of probability mass. third, we focus not only on mt but also on gec. @xcite showed that beam search errors often obscure the length deficiency of the nmt modes, and reducing search errors by using large beams exposes this model error. in this work, we found that these mechanics are limited to nmt: gec does not suffer from the beam search curse since search errors are rare and modes are not too short. eikema and aziz (2020) suggested that picking a hypothesis based solely on probability is erratic because nmt spreads out the probability mass over a large set of hypotheses with similar probabilities. therefore, alternative approaches that in addition to the probabilities incorporate mt-specific metrics such as bleu @xcite or bleurt @xcite have recently been in focus of research, including minimum bayes risk decoding @xcite @xcite , monte-carlo tree search @xcite , and energy-based @xcite or discriminatively trained @xcite rerankers. our work on how uncertainty determines the spread of probability mass is relevant to those approaches. ## conclusion we identified a major culprit behind various inference-related issues in sequence-to-sequence models such as the intractability of the search space, degenerate large beam or exact search outputs and the large spread in probability mass over the output space. this factor is intrinsic uncertainty -the existence of multiple ways to correctly map an input sequence. we measured the intrinsic uncertainty of input sentences as the degree of agreement between multiple references and showed that ambiguous sentences typically result in a higher number of beam search errors and an exceedingly flat output distribution. we also find that known nmt pathologies such as the beam search curse or inadequate modes do not extend to less ambiguous tasks like gec despite using the same neural architecture.