A Measure-Theoretic Characterization of Tight Language Models (2023)

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 pathological cases, probability mass can “leak” onto the set of infinite sequences. In order to characterize 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.

## introduction language modeling is a core task in natural language processing. as canonically defined, language 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 distribution over the language's sentences. since @xcite , language modeling has been used to estimate statistical properties of language and has become essential for computational linguistics research @xcite . further, it is also central to a wide range of natural language processing applications, whether as a source model in a noisy channel architecture @xcite , as a way of learning better representations of language @xcite , or, more recently, for prompted generation @xcite , where the distribution defined by a language model is employed in tasks like question-answering @xcite , style transfer @xcite , and even sequence tagging @xcite . more formally, a language model is typically defined to be a distribution over the countably infinite 1 or perhaps alphabetic symbols or subwords; see, e.g., @xcite . it is here that a subtlety arises: the set of infinite sequences is uncountably infinite. properly treating a distribution over this sample space requires a modicum of measure theory. 3 to clarify the situation, we review the measure-theoretic treatment of distributions over infinite sequences. we then make use of a termination symbol eos to define a random variable whose value can be a string, i.e., an element of σ * , or an infinite sequence. in a tight language model, this random variable has probability 1 of being a string and hence finite. beyond offering a measure-theoretic formalization, our paper also demonstrates how tightness relates to the borel-cantelli lemmata, simplifying a recent result by @xcite . to conclude our paper, we analyze several language modeling architectures and give conditions on their tightness. we demonstrate that n-gram language modelsand more generally, language models defined by stochastic finite-state automata-can be non-tight, and we give a simple necessary and sufficient condition for tightness in terms of the inverse of the automaton's transition matrix. this builds on a known result due to @xcite . we also discuss when neural language models become non-tight. we prove that transformer-based language models @xcite are always tight and that recurrent neural language models are always tight when they employ a bounded activation function. however, we also exhibit a recurrent neural network (rnn) language model with a relu activation @xcite that is non-tight in a simpler construction than the one offered by @xcite . as a byproduct, we also generalize and strengthen the results given by @xcite , who give a sufficient condition for tightness of recurrent neural language models in terms of the norm of the hidden state. ## motivating examples let σ be an alphabet, i.e., a finite set of symbols, and let eos / ∈ σ be a distinguished end-ofsequence symbol. let σ @xmath0. a string of length @xmath1. . . x n where each x @xmath2. by convention, we say that x n+1 = eos, although x n+1 is not an element of the sequence x. for any integer 1 ≤ @xmath3, we write @xmath4. we now begin to distinguish between "language models" and "sequence models." as is traditional in the nlp literature, we henceforth define a language model to be a probability distribution over the countable set σ * of all strings (see def. 3.4). it is popular to specify such a distribution in terms of its conditional probabilities p(x t | @xmath5. definition 2.1. an autoregressive sequence model (asm) is a conditional probability distribution p(x t | @xmath6. if p is an asm, then we define a non-negative function p over σ * by p(x) but is p a language model? not always, since as we will see below, it is possible for p(σ * ) @xmath7. of course this "bad" case never happens if the asm's conditional probabilities are derived from a known lm, in which case p simply recovers that lm. 4 in this case clearly p(σ * ) = 1. it follows that if p(σ * ) < 1, then the asm's conditional probabilities do not match the conditional probabilities of any language model p 0 . we now exhibit such a "bad" asm. although the conditional probability distributions p(• | @xmath8, they fail to combine into a model p that sums to 1 over σ * (i.e., a language model). example 2.2 (non-tight bigram model). consider the bigram model defined in fig. 1a over the alphabet σ = {a, b}. under this model, any finite string that contains the symbol b will have probability 0, since 1b , obtained from ex. 2.2 by changing the arcs from the b state, p(σ * ) = 1. see app. b for details of this calculation. ex. 2.2 above confirms that the autoregressive formulation does not necessarily yield p that is a valid distribution over σ * . but if p is not a language model, what is it? it is intuitive to suspect that, in a model with p(σ * ) < 1, the remainder of the probability mass "leaks" to infinite sequences, i.e., the generative process may continue forever with @xmath9. we will make this intuition formal in §3. by analogy with @xcite and @xcite , we refer to such models as non-tight. 5 the non-tightness of ex. 2.2 is related to the fact that the probability of eos is 0 at some states, in contrast to ex. 2.3. however, requiring p(eos | @xmath10. it is not necessary because one can, for example, construct an asm in which p(eos | @xmath11.1 when t is even @xmath12. such a model generates only odd-length strings but is tight. it is not sufficient because of the following example, in which p(eos | @xmath13. example 2.4 (non-tight rnn). consider an rnn over a small alphabet σ = {a, eos} with the fol-then by the chain rule of probability, p(x) = p0(x) for each @xmath14. thus @xmath15, so p is a language model. 5 in @xcite and @xcite , a pcfg is non-tight if its generative process may not terminate, and consequently the total probability of all finite trees is less than 1. lowing hidden state recurrence: in this case, the hidden state admits a closed-form expression h @xmath16. setting the (1-dimensional) embedding of the alphabet to be v @xmath17, we arrive at the eos probability is always strictly positive, but thm. 4.7 shows that this sequence model is nontight. numerically, p(σ * ) ≈ 0.702 < 1. on the other hand, an asm may be tight after all if the probability of eos decays more slowly-even when it still approaches 0. example 2.5 (tight rnn). consider again an rnn over the alphabet σ = {a, eos} with the following recurrence using softplus activation: foot_3 h 1 = 0, h @xmath18. starting from h 1 = 0 = log 1, a simple induction argument shows that h @xmath19. (4) again, setting v @xmath20, we arrive at this decays slowly to 0: finally, we illustrate the peril of not treating distributions over uncountable sets carefully. example 2.6 (infinite coin toss). consider the infinite independent fair coin toss model, where we aim to place a distribution over {h, t} ∞ , the uncountable set of infinite sequences of {h, t}. intuitively, such a distribution corresponds to an asm in which for all @xmath21, p(h | @xmath22. clearly, each individual infinite sequence over {h, t} should be assigned probability ( 1 2 ) ∞ = 0. without a formal foundation, one may arrive at the following paradox: together, these examples suggest that one must take care to characterize tightness. and, to the authors' surprise, it does not appear as if such a careful characterization yet exists in the nlp literature. ## the language model measure in this section, we rigorously characterize the kind of distribution induced by an asm. as mentioned earlier, an asm can lose probability mass to the set of infinite sequences, σ ∞ . however, σ ∞ , unlike σ * , is uncountable, and it is due to this fact that we need to work explicitly with the measure-theoretic formulation of probability. ## characterizing tightness beyond the measure-theoretic formalization, a goal of this paper is to provide an exact characterization of tightness in asms. the results presented in this section generalize lemma 3.2 in @xcite . first, we consider the event in the probability space (σ ∞ , σ(c), p). intuitively, a k is the event that an eos symbol appears at position k in the string. note that under this definition the a k are not disjoint. for example, the string ω = ab eos c eos dd • • • lives in the intersection of a 3 and a 5 since eos appears at both position 3 and position 5. using eq. ( 16 ), we can express the event consisting of all finite strings as ∞ @xmath23. it follows that we can express the event of an infinite string as thus, using the random variable x, we can express the probability of generating an infinite string as hence, we can now formalize the notion of tightness, which we have introduced in §2 and def. 3.4. definition 4.1. a sequence model p is said to be tight if p (@xmath24, in which case it is also a language model (cf. prop. c.9). otherwise, we say that it is non-tight. note that the definition of a k only uses a string's k-prefix, and hence is a cylinder set of rank k. recalling that the cylinder sets are measurable and so are the sets countably generated by them, we see that both the event consisting of all finite strings and the event consisting of all infinite strings are measurable. thus, p (∪ ∞ @xmath25. ## analysis of common language models we now put into practice the foundations built up in the previous sections and discuss the tightness of several classes of asms. ## conclusion this paper presents a measure-theoretic treatment of language modeling and its tightness. practical implications of our results include determining when sampling from an autoregressive sequence model is guaranteed to terminate and whether mcmc algorithms over such models will mix to the correct distribution. to this end, we first defined various components of language modeling in measure-theoretic terminology. this in turn allows us to understand the portion of probability mass allocated to infinite-length strings. importantly, this presentation formalizes a definition of sequence modeling under which the probability of producing an infinite-length sequence is non-zero; while today's models are often capable of producing such strings, previously there was no rigorous treatment of this case. indeed, such a definition is useful when considering a number of neural architectures (e.g., a simple rnn as in @xcite and language generation systems (e.g., the distribution induced by nucleus sampling; @xcite . in particular, we showed that perhaps the most commonly-used nlp architecture, the transformer language model, is indeed a language model-a tight distribution over finite strings-a property that had been called into question by previous work.