On Efficiently Representing Regular Languages as RNN s (2024)

Abstract: Recent work by Hewitt et al. (2020) provides an interpretation of the empirical success of recurrent neural networks (RNNs) as language models (LMs). It shows that RNNs can efficiently represent bounded hierarchical structures that are prevalent in human language.This suggests that RNNs’ success might be linked to their ability to model hierarchy. However, a closer inspection of hewitt-etal-2020-rnns construction shows that it is not inherently limited to hierarchical structures. This poses a natural question: What other classes of LMs RNNs can efficiently represent? To this end, we generalize Hewitt et al.’s (2020) construction and show that RNNs can efficiently represent a larger class of LMs than previously claimed—specifically, those that can be represented by a pushdown automaton with a bounded stack and a specific stack update function. Altogether, the efficiency of representing this diverse class of LMs with RNN LMs suggests novel interpretations of their inductive bias.

## introduction neural lms have demonstrated a human-level grasp of grammar and linguistic nuance. yet, a considerable gap remains between our empirical observations and our theoretical understanding of their capabilities. one approach to bridge this gap is to study what classes of formal languages neural lms can efficiently represent. the rationale behind this object of study is that a neural lm's ability to represent a language efficiently suggests the presence of an inductive bias in the model architecture that prefers that language over others, and may make it specifically easier to learn, e.g., due to occam's razor. exploring lms' ability to model formal languages has garnered significant interest in recent years; see, e.g., the surveys by merrill (2023) and strobl et al. (2023). investigation into this area has a particularly long history in the context of rnns (mcculloch and pitts, 1943; minsky, 1954; siegel-y1 y2 ¨¨¨yt´4 yt´3 yt´2 yt´1 y t ¨¨ÿ t´1 y t´4 y 2 ‚ h py ăt q p py t | y ăt q softmax peh pyătq `uq y t figure 1 : an illustration of how an rnn can store information about a fixed number of symbols (in this case, three) that have appeared in the string y ăt . using some mechanism, the symbols y 2 , y t´4 , y t´1 have been selected for determining the continuation of the string and are stored in h. these symbols are used to compute the conditional probability of the next symbol y t . the non-hierarchical nature of bpdas leads us to contend that the reason some lms lend themselves to exponential compression has little to do with their hierarchical structure. this offers two intriguing insights. first, it shows that the inductive biases of rnn lms might be difficult to link to a hierarchical structure. second, it provides a new perspective on which languages rnns efficiently encode, i.e., those representable by sequential machines with a bounded stack. such a machine is illustrated in fig. 1 . ## preliminaries we begin by introducing some core concepts. an alphabet σ is a finite, non-empty set of symbols. its kleene closure σ ˚is the set of all strings of symbols in σ. the length of the string y " y 1 . . . y t p σ ˚, denoted by |y| " t , is the number of symbols it contains. a language model p is a probability distribution over σ ˚. two lms p and q are weakly equivalent if p pyq " q pyq for all y p σ ˚and two families of lms p and q are weakly equivalent if, for any p p p, there exists a weakly equivalent q p q and vice versa. most modern lms define p pyq as a product of conditional probability distributions: a historically important class of lm are those that obey the n-gram assumption. assumption 2.1. the n-gram assumption states that the probability p py t | y ăt q only depends on n ´1 previous symbols y t´1 , . . . , y t´n`1 : fig. 2 shows an example of an 2-gram lm. the weights on the transitions denote the conditional probabilities of the next symbol given the previous n ´1 " 2 symbols encoded by the current state. ## discussion this work was motivated by the question of what classes of lms beyond those over dpb, nq can be @xcite the prefixes at the beginning of the string have to be appropriately padded. hewitt et al. (2020). we address this with thm. 4.1, whose implications we discuss next. ## conclusion we build on hewitt et al.'s (2020) results and show that rnns can efficiently represent a more general class of lms than those over bounded dyck languages. concretely, we introduce bounded stack lms as lms defined by automata that keep m selected symbols that have occurred in the string so far and update the memory using simple update mechanisms. we show that instances of such lms can be represented by rnn lms in optimal space. this provides a step towards a more holistic grasp of the inductive biases of rnn lms.