Lower Bounds on the Expressivity of Recurrent Neural Language Models (2024)

Abstract: The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their abilities. Describing their abilities through LMs’ representational capacity is a lively area of research. Investigations of the representational capacity of neural LMs have predominantly focused on their ability to recognize formal languages. For example, recurrent neural networks (RNNs) as classifiers are tightly linked to regular languages, i.e., languages defined by finite-state automata (FSAs). Such results, however, fall short of describing the capabilities of RNN language models (LMs), which are definitionally distributions over strings. We take a fresh look at the represen- tational capacity of RNN LMs by connecting them to probabilistic FSAs and demonstrate that RNN LMs with linearly bounded precision can express arbitrary regular LMs.

## introduction neural language models (lms) excel at many nlp tasks, e.g., machine translation, conversational ai, text classification, and natural language inference @xcite @xcite . their strong empirical performance suggests the need for theory to explain what lms can and cannot do in a formal sense. such theory should serve to better understand as well as alleviate the practical limitations of neural lms. however, the most common paradigm to perform such an analysis of neural lms revolves around proving which formal languages common lm architectures can express @xcite @xcite , i.e., to characterize the representational capacity of neural lms with tools from the theory of computation. formally, a language model is a probability distribution over σ ˚, the set of all strings from some alphabet σ. 1 we say that two language models are weakly equivalent if they express the same distribution over strings. pfsas (both deterministic and non-deterministic) and recurrent neural lms, e.g., those derived from elman recurrent neural networks (rnns; @xcite , however, are instances of families of language models, i.e., sets of distributions over strings that can be represented under the specific formalism. for instance, if one changes the parameters of a pfsa, one arrives at a different language model. therefore, going beyond the formal comparison of individual lms, we may also desire to make formal statements about families of models. one natural way to construct an (upper) bound on the representational capacity of an entire family of language models f 1 , e.g., those expressible by rnns, is to find another family of language models f 2 and show that, for every language model q p f 2 , there exists a weakly equivalent p p f 1 . our goal in this paper is to show that, for every non-deterministic pfsa, there exists a weakly equivalent rnn lm. the approach to studying language models presented in the previous paragraph differs fundamentally from most work that uses formal language theory to study the representational capacity of language models. indeed, most papers try to relate language models to language acceptors (siegelmann and @xcite @xcite . e.g., finite-state automata have been linked to rnns extensively before @xcite @xcite . however, acceptors are fundamentally different objects than lms, as they define sets of strings rather than distributions over them. thus, analyzing acceptors, does not address our desire to understand recurrent neural lms as probability distributions over σ ˚. in previous work, @xcite demonstrate a particularly close relationship between recurrent neural language models and deterministic pfsas. however, their theory does not extend to the family of non-deterministic exact simulation with sparsemax and ∥¨∥ 1 normalization. ## preliminaries we begin by introducing some preliminaries. ## exact simulation this section presents our results on the exact simulation (that is, weak equivalence) of regular lms with both sparsemax as well as softmax-normalized elman lms. the results rely on thm. 3.1, which provides the basis for all our subsequent results by showing that elman rnns with linear precision can compute the state-string distributions p a pq, yq (cf. eq. ( 9 )) of any pfsa a. a note on notation. throughout the paper, we implicitly index vectors and matrices directly with symbols for conciseness. concretely, we assume an implicit ordering of the symbols and a corresponding ordering of the vector and matrix entries. this ordering is effected through a bijection n : σ ñ r|σ|s (or any other set in place of σ). we then define, for x p r |σ| , x y def " x npyq and, for theorem 3.1. let a be a pfsa with the statestring distribution p a pq, y ďt q (cf. eq. ( 9 )). then, there exists an elman rnn r with linearly bounded precision such that for all q p q and all y ďt " y 1 . . . y t p σ hpy ďt q pq,yq " 1 ty " y t u p a pq, y ăt q . (18) proof intuition. the proof translates the computation of the state-string probabilities under the pfsa (cf. eq. ( 9 )) into the recurrence of the elman rnn. see app. b for the details. ■ ## conclusion we study a practically relevant formulation of elman lms with real-time processing and linear precision with respect to the string length and describe its probabilistic representational capacity in terms of regular lms. concretely, we show that elman lms with non-standard normalization and activation functions can simulate arbitrary non-deterministic pfsas (cors. 3.1 and 3.2). we then extend these exact simulation results to approximation-based ones, where we show that elman lms as used in practice can approximate regular lms arbitrarily well as measured by total variation distance (thm. 4.2). the intuitive constructions provide a better understanding of the representational capacity of elman lms and showcase the probabilistic representational capacity of elman lms in a new light.