Limitations of Autoregressive Models and Their Alternatives

Limitations of Autoregressive Models and Their Alternatives Chu-Cheng Lin♯∗ Aaron Jaech♭ Xin Li♯ Matthew R. Gormley♮ Jason Eisner♯ ♯Department of Computer Science, Johns Hopkins University ♭Facebook AI ♮Machine Learning Department, Carnegie Mellon University {kitsing,lixints,jason}@cs.jhu.edu ajaech@fb.com mgormley@cs.cmu.edu Abstract Standard autoregressive language models per- form only polynomial-time computation to compute the probability of the next symbol. While this is attractive, it means they cannot model distributions whose next-symbol prob- ability is hard to compute. Indeed, they can- not even model them well enough to solve associated easy decision problems for which an engineer might want to consult a language model. These limitations apply no matter how much computation and data are used to train the model, unless the model is given access to oracle parameters that grow superpolynomially in sequence length. Thus, simply training larger autoregressive lan- guage models is not a panacea for NLP. Al- ternatives include energy-based models (which give up efficient sampling) and latent-variable autoregressive models (which give up efficient scoring of a given string). Both are powerful enough to escape the above limitations. 1 Introduction Sequence modeling is a core NLP problem. Many sequence models ˜푝 are efficient at scoring strings: given a string x, its score ˜푝(x) can be computed in 푂(poly(|x|)). For example, an RNN (Mikolov et al., 2011) scores x in time 푂(|x|) while a Transformer (Vaswani et al., 2017) does so in time 푂(|x|2). The score may be an unnormalized probability, and can be used to rank candidate strings. Many sequence models also make it easy to compute marginal properties of ˜푝. They support efficient sampling of strings x (which allows unbiased approximation of marginal expectations). And they support efficient computation of the normalizing constant 푍 = � x ˜푝(x) (or simply guarantee 푍 = 1) for any value of the model parameters. How about training? Briefly: If a sequence model can efficiently compute ˜푝(x) (and its derivatives ∗Part of this work was done at Facebook AI. Figure 1: Valid answers to hard natural language inference problems can be hard to find (Munroe, 2009), but in many cases can be checked efficiently (e.g. the Knapsack problem in the comic). Given a large enough parametric autoregressive model with correct parameters, we can efficiently solve all problem instances with input length 푛, and efficiently verify the solutions — but the required model size can grow superpolynomially in 푛. (This allows the model to store precomputed results that we can look up in 푂(푛) at test time.) A main observation of this paper is that assuming NP ⊈ P/poly, then without such a superpolynomial growth in model size, autoregressive models cannot even be used to verify answers to some problems where polynomial-time verification algorithms do exist. with respect to model parameters), then it is efficient to compute parameter updates for noise-contrastive estimation (Gutmann and Hyvärinen, 2010; Gutmann and Hyvärinen, 2012) or score-matching (Hyvärinen, 2005). If sampling x or computing 푍 (and its deriva- tives) is also efficient, then it is efficient to compute parameter updates for ordinary …

Content truncated to 500 words