A Measure-Theoretic Characterization of Tight Language Models

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 9744–9770 July 9-14, 2023 ©2023 Association for Computational Linguistics A Measure-Theoretic Characterization of Tight Language Models Li Du6 Lucas Torroba Hennigen@ Tiago PimentelD Clara MeisterQ Jason Eisner6 Ryan CotterellQ 6Johns Hopkins University @MIT DUniversity of Cambridge QETH Zürich leodu@cs.jhu.edu lucastor@mit.edu tp472@cam.ac.uk clara.meister@inf.ethz.ch jason@cs.jhu.edu ryan.cotterell@inf.ethz.ch Abstract Language modeling, a central task in natural language processing, involves estimating a probability distribution over strings. In most cases, the estimated distribution sums to 1 over all finite strings. However, in some patho- logical cases, probability mass can “leak” onto the set of infinite sequences. In order to char- acterize the notion of leakage more precisely, this paper offers a measure-theoretic treatment of language modeling. We prove that many popular language model families are in fact tight, meaning that they will not leak in this sense. We also generalize characterizations of tightness proposed in previous works. 1 Introduction Language modeling is a core task in natural lan- guage processing. As canonically defined, lan- guage modeling involves estimating a distribution over the set of strings over a given alphabet. If the alphabet is the set of words in a language,1 then a language model can be thought of as a distribu- tion over the language’s sentences. Since Shannon (1948), language modeling has been used to es- timate statistical properties of language and has become essential for computational linguistics re- search (Hale, 2001; Meister et al., 2021). Further, it is also central to a wide range of natural language processing applications, whether as a source model in a noisy channel architecture (Weaver, 1955; Je- linek, 1976), as a way of learning better represen- tations of language (Peters et al., 2018), or, more recently, for prompted generation (Brown et al., 2020), where the distribution defined by a language model is employed in tasks like question-answering (Petroni et al., 2019), style transfer (Reif et al., 2022), and even sequence tagging (Liu et al., 2022). More formally, a language model is typically de- fined to be a distribution over the countably infinite 1Or perhaps alphabetic symbols or subwords; see, e.g., Bostrom and Durrett (2020). set Σ∗ of all (finite) strings (Booth and Thompson, 1973).2 However, it has been shown that some classes of autoregressive language models have pa- rameter settings in which the generative process terminates with probability < 1. Welleck et al. (2020) discuss this issue for recurrent neural net- work language models. Models whose generative process may fail to terminate are called non-tight (Chi, 1999, who discussed non-tight PCFGs). If an autoregressive language model is non-tight, it may generate infinite sequences and MCMC algo- rithms over such models will not mix to the correct distribution. It is here that a subtlety arises: the set of infinite sequences is uncountably infinite. Properly treat- ing a distribution over this sample space requires a modicum of measure theory.3 To clarify the sit- uation, we review the measure-theoretic treatment of distributions over infinite sequences. We …

Content truncated to 500 words