Recurrent Neural Language Models as Probabilistic Finite-state Automata (2023)

Abstract: Studying language models (LMs) in terms of well-understood formalisms allows us to precisely characterize their abilities and limitations. Previous work has investigated the expressive power of recurrent neural network (RNN) LMs in terms of their capacity to recognize unweighted formal languages. However, LMs do not describe unweighted formal languages—rather, they define probability distributions over strings. In this work, we study what classes of such probability distributions RNN LMs can represent, which allows us to make more direct statements about their capabilities. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata, and can thus model a strict subset of probability distributions expressible by finite-state models. Furthermore, we study the space complexity of representing finite-state LMs with RNNs. We show that, to represent an arbitrary deterministic finite-state LM with N states over an alphabet \Sigma , an RNN requires \Omega\left(N |\Sigma|\right) neurons. These results present a first step towards characterizing the classes of distributions RNN LMs can represent and thus help us understand their capabilities and limitations.

## introduction we start with a few definitions. an alphabet σ is a finite, non-empty set. a formal language is a subset of σ's kleene closure σ ˚, and a language model (lm) p is a probability distribution over σ ˚. lms have demonstrated utility in a variety of nlp tasks and have recently been proposed as a general model of computation for a wide variety of problems requiring (algorithmic) reasoning (brown et al., 2020; chen et al., 2021; hoffmann et al., 2022; chowdhery et al., 2022; wei et al., 2022a,b; kojima et al., 2023; kim et al., 2023, inter alia). our paper asks a simple question: how can we characterize the representational capacity of an lm based on a recurrent neural network (rnn)? probabilistic finite-state language models probabilistic fsas probabilistic regular grammars discrete hmms deterministic probabilistic finite-state language models deterministic probabilistic fsas heaviside elman rnns efficiently rnn-representable finite-state language models n-gram lms dpk, mq complexity class of languages computational models, examples of languages in other words: what classes of probability distributions over strings can rnns represent? answering this question is essential whenever we require formal guarantees of the correctness of the outputs generated by an lm. for example, one might ask a language model to solve a mathematical problem based on a textual description (shridhar et al., 2023) or ask it to find an optimal solution to an everyday optimization problem (lin et al., 2021, fig. 1 ). if such problems fall outside the representational capacity of the lm, we have no grounds to believe that the result provided by the model is correct in the general case. the question also follows a long line of work on the linguistic capabilities of lms, as lms must be able to implement mechanisms of recognizing specific syntactic structures to generate grammatical sequences (linzen et al., 2016; hewitt and manning, 2019; jawahar et al., 2019; liu et al., 2019; icard, 2020; manning et al., 2020; rogers et al., 2021; belinkov, 2022, inter alia). a natural way of quantifying the representational capacity of computational models is with the class of formal languages they can recognize (deletang et al., 2023). previous work has connected modern lm architectures such as rnns (elman, 1990; hochreiter and schmidhuber, 1997; cho et al., 2014) and transformers (vaswani et al., 2017) to formal models of computation such as finite-state automata, counter automata, and turing machines (e.g., mcculloch and pitts, 1943; kleene, 1956; siegelmann and sontag, 1992; hao et al., 2018; korsky and berwick, 2019; merrill, 2019; merrill et al., 2020; hewitt et al., 2020; merrill et al., 2022; merrill and tsilivis, 2022, inter alia). through this, diverse formal properties of modern lm architectures have been shown, allowing us to draw conclusions on which phenomena of human language they can model and what types of algorithmic reasoning they can carry out. @xcite however, most existing work has focused on the representational capacity of lms in terms of classical, unweighted, formal languages, which arguably ignores an integral part of an lm: the probabilities assigned to strings. in contrast, in this work, we propose to study lms by directly characterizing the class of probability distributions they can represent. concretely, we study the relationship between rnn lms with the heaviside activation function h pxq def " 1 tx ą 0u and finite-state lms, the class of probability distributions that can be represented by weighted finite-state automata (wfsas). finitestate lms form one of the simplest classes of probability distributions over strings (icard, 2020) and include some well-known instances such as n-gram lms. we first prove the equivalence in the representational capacity of deterministic wfsas and rnn lms with the heaviside activation function, where determinism here refers to the determinism in transitioning between states conditioned on the input symbol. to show the equivalence, we generalize the well-known construction of an rnn encoding an unweighted fsa due to minsky (1954) to the weighted case, which enables us to talk about string probabilities. we then consider the space complexity of simulating wfsas using rnns. minsky's construction encodes an fsa with n states in space o p|σ|n q, i.e., with an rnn with o p|σ|n q hidden units, where σ is the alphabet over which 2 see §7 for a thorough discussion of relevant work. the wfsa is defined. indyk (1995) showed that a general unweighted fsa with n states can be simulated by an rnn with a hidden state of size o `|σ| ? n ˘. we show that this compression does not generalize to the weighted case: simulating a weighted fsa with an rnn requires ω pn q space due to the independence of the individual conditional probability distributions defined by the states of the wfsa. lastly, we also study the asymptotic space complexity with respect to the size of the alphabet, |σ|. we again find that it generally scales linearly with |σ|. however, we also identify classes of wfsas, including n-gram lms, where the space complexity scales logarithmically with |σ|. these results are schematically presented in fig. 1 . ## finite-state language models most modern lms define p pyq as a product of conditional probability distributions p: definition 2.1 (weakly equivalent). two lms p and q over σ ˚are weakly equivalent if p pyq " q pyq for all y p σ @xcite finite-state automata are a tidy and wellunderstood formalism for describing languages. definition 2.2. a finite-state automaton (fsa) is a 5-tuple pς, q, i, f, δq where σ is an alphabet, q a finite set of states, i, f ď q the set of initial and final states, and δ ď q ˆσ ˆq set of transitions. we assume that states are identified by integers in z |q| def " t0, . . . , |q| ´1u. @xcite we also adopt a more suggestive notation for transitions by denoting pq, y, q 1 q p δ as q y ý ñ q 1 . we call transitions of the form q y ý ñ q 1 y-transitions and define the children of the state q as the set we denote pq, y, w, q 1 q p δ with q y{w ý ý ñ q 1 and if there are no y-transitions from q to q 1 . @xcite the underlying fsa of a wfsa is the fsa obtained by removing the transition weights and setting i " tq p q | λ pqq ‰ 0u and f " tq p q | ρ pqq ‰ 0u. definition 2.4. an fsa a " pς, q, i, f, δq is deterministic if |i| " 1 and for every pq, yq p q ˆσ, there is at most one in contrast to unweighted fsas, not all nondeterministic wfsas admit a weakly equivalent deterministic one, i.e., they are non-determinizable. definition 2.5. a path π is a sequence of consecutive transitions the path's length |π| is the number of transitions on it and its scan s pπq is the concatenation of the symbols on its transitions. we denote with πpaq the set of all paths in a and with πpa, yq the set of all paths that scan y p σ ˚. the weights of the transitions along a path are multiplicatively combined to form the weight of the path. the weights of all the paths scanning the same string are combined additively to form the weights of that string. definition 2.6. the path weight of π p πpaq is the stringsum of y p σ ˚is a pyq def " ř πpπpa,yq w pπq. a class of wfsas important for defining lms is probabilistic wfsas. definition 2.7. a wfsa a " pς, q, δ, λ, ρq is probabilistic (a pfsa) if all transition, initial, and @xcite throughout the text, we use ˝as a placeholder a free quantity, in this case, to any weight w p r. in case there are multiple ˝'s in an expression, they are not tied in any way. the initial weights, and, for any q p q, the weights of its outgoing transitions and its final weight, form a probability distribution. the final weights in a pfsa play an analogous role to the eos symbol-they represent the probability of ending a path in q: ρ pqq corresponds to the probability of ending a string y, p peos | yq, where q is a state arrived at by a after reading y. we will use the acronym dpfsa for the important special case of a deterministic pfsa. definition 2.8. a language model p is finite-state (an fslm) if it can be represented by a pfsa, i.e., if there exists a pfsa a such that, for every y p σ ˚, p pyq " a pyq. see fig. 2 for an example of a pfsa defining an fslm over σ " ta, bu. its support consists of the strings ab n ab m and bb m for n, m p n ě0 . in general, there can be infinitely many pfsas that express a given fslm. however, in the deterministic case, there is a unique minimal canonical dpfsa. definition 2.9. let p be an fslm. a pfsa a is a minimal dpfsa for p if it defines the same probability distribution as p and there is no weakly equivalent dpfsa with fewer states. definition 3.1. an elman rnn (ernn) r " pς, σ, d, u, v, b, h 0 q is an rnn with the following hidden state recurrence: an rnn r can be used to specify an lm by using the hidden states to define the conditional distributions for y t given y ăt . definition 3.2. let e p r |σ|ˆd and let r be an rnn. an rnn lm pr, eq is an lm whose conditional distributions are defined by projecting eh t onto the probability simplex ∆ |σ|´1 using some we term e the output matrix. the most common choice for f is the softmax defined for x p r d and d p z d as an important limitation of the softmax is that it results in a distribution with full support for all x p r d . however, one can achieve 0 probabilities by including extended real numbers r def " r y t´8, 8u: any element with x d " ´8 will result in softmaxpxq d " 0. recently, a number of alternatives to the softmax have been proposed. this paper uses the sparsemax function (martins and astudillo, 2016), which can output sparse distributions: on determinism. unlike pfsas, elman rnns (and most other popular rnn architectures, such as the lstm and gru) implement inherently deterministic transitions between internal states. as we show shortly, certain types of elman rnns are at most as expressive as deterministic pfsas, meaning that they can not represent non-determinizable pfsas. common choices for the nonlinear function σ in eq. ( 2 ) are the sigmoid function σpxq " 1 1`expp´xq and the relu σpxq " maxp0, xq. however, the resulting nonlinear interactions of the parameters and the inputs make the analysis of rnn lms challenging. one fruitful manner to make the analysis tractable is making a simplifying assumption about σ. we focus on a particularly useful simplification, namely the use of the heaviside activation function. @xcite definition 3.3. the heaviside function is defined as hpxq def " 1 tx ą 0u. see fig. 3 for the graph of the heaviside function and its continuous approximation, the sigmoid. for cleaner notation, we define the set b def " t0, 1u. using the heaviside function, we can define the heaviside ernn, the main object of study in the rest of the paper. definition 3.4. a heaviside elman rnn (hrnn) is an ernn r " pς, σ, d, u, v, b, h 0 q where σ " h. ## equivalence of hrnns and fslms the hidden states of an hrnn live in b d , and can thus take 2 d different values. this invites an interpretation of h as the state of an underlying fsa that transitions between states based on the hrnn recurrence, specifying its local conditional distributions with the output matrix e. similarly, one can also imagine designing a hrnn that simulates the transitions of a given fsa by appropriately specifying the parameters of the hrnn. we explore this connection formally in this section and present the main technical result of the paper. the central result that characterizes the representational capacity hrnn can be informally summarized by the following theorem. the proof closely follows the intuitive connection between the 2 d possible configurations of the rnn hidden state and the states of the strongly equivalent dpfsa. the outgoing transition weights of a state q are simply the conditional probabilities of the transition symbols conditioned on the rnn hidden state represented by q. @xcite this implies that hrnns are at most as expressive as dpfsas, and as a consequence, strictly less expressive as non-deterministic pfsas. we discuss the implications of this in §6. ## discussion in §4 and §5 we provided the technical results behind the relationship between hrnn lms and dpfsas. to put those results in context, we now discuss some of their implications. ## related work to the best of our knowledge, the only existing connection between rnns and weighted automata was made by peng et al. (2018), where the authors connect the recurrences analogous to eq. ( 2 ) of different rnn variants to the process of computing the probability of a string under a general pfsa. with this, they are able to show that the hidden states of an rnn can be used to store the probability of the input string, which can be used to upper-bound the representational capacity of specific rnn variants. importantly, the interpretation of the hidden state is different to ours: rather than tracking the current state of the pfsa, peng et al. (2018)'s construction stores the distribution over all possible states. while this suggests a way of simulating pfsas, the translation of the probabilities captured in the hidden state to the probability under an rnn lm is not straightforward. weiss et al. (2018), merrill (2019) and merrill et al. (2020) consider the representational capacity of saturated rnns, whose parameters take their limiting values ˘8 to make the updates to the hidden states discrete. in this sense, their formal model is similar to ours. however, rather than considering the probabilistic representational capacity, they consider the flexibility of the update mechanisms of the variants in the sense of their long-term dependencies and the number of values the hidden states can take as a function of the string length. connecting the assumptions of saturated activations with the results of peng et al. (2018), they establish a hierarchy of different rnn architectures based on whether their update step is finite-state and whether the hidden state can be used to store arbitrary amounts of information. analogous to our results, they show that elman rnns are finitestate while some other variants such as lstms are provably more expressive. in a different line of work, weiss et al. (2019) study the ability to learn a concise dpfsa from a given rnn lm. this can be seen as a relaxed setting of the proof of lemma 4.1, where multiple hidden states are merged into a single state of the learned dpfsa to keep the representation compact. the work also discusses the advantages of considering deterministic models due to their interpretability and computational efficiency, motivating the connection between lms and dpfsas. discussion of some additional (less) related work can be found in appendix d. ## conclusion we prove that heaviside elman rnns define the same set of probability distributions over strings as the well-understood class of deterministic probabilistic finite-state automata. to do so, we extend minsky's classical construction of an hrnn simulating an fsa to the probabilistic case. we show that minsky's construction is in some sense also optimal: any hrnn representing the same distribution as some dpfsa over strings from an alphabet σ will, in general, require hidden states of size at least ω p|σ||q|q, which is the space complexity of minsky's construction.