What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages (2024)

Abstract: What can large language models learn? By definition, language models (LM) are distributionsover strings. Therefore, an intuitive way of addressing the above question is to formalize it as a matter of learnability of classes of distributions over strings. While prior work in this direction focused on assessing the theoretical limits, in contrast, we seek to understand the empirical learnability. Unlike prior empirical work, we evaluate neural LMs on their home turf—learning probabilistic languages—rather than as classifiers of formal languages. In particular, we investigate the learnability of regular LMs (RLMs) by RNN and Transformer LMs. We empirically test the learnability of RLMs as a function of various complexity parameters of the RLM and the hidden state size of the neural LM. We find that the RLM rank, which corresponds to the size of linear space spanned by the logits of its conditional distributions, and the expected length of sampled strings are strong and significant predictors of learnability for both RNNs and Transformers. Several other predictors also reach significance, but with differing patterns between RNNs and Transformers.

## introduction language models are, definitionally, distributions over strings. however, not all neural lms are capable of learning-or even representing-all possible distributions. this raises two natural questions: what classes of distributions can neural lms represent and what can they learn from training examples? in terms of the first question, the relationship between recurrent neural networks and more symbolic computational models has been subject to study for over three decades @xcite @xcite @xcite @xcite @xcite @xcite @xcite . moreover, @xmath0.6 < l a t e x i t s h a 1 _ b a s e 6 4 = " e v j a o o y l l v v o + j e q y a / e c u 6 j e h @xmath1 z 6 e o e 2 m y z m p j e 9 m f i f 1 8 1 m d b 3 k x k a z y z i u f k w z w c b b s 8 / x g c t g j z h y q q j i 9 l z m r 0 q r a m w + f r u c t / z y x 9 i 6 d 7 x l 5 + k + x m v c w z e l h k m j e d 9 o a w l 5 z x v t f j 6 z w n z a 3 u n u r v x 1 e m m c a 1 i w h p v j r c m n e k a g g y 4 b a e k y h f x 2 o p g t 1 o / 9 u i v z o l 8 m o o u h g i p j i s z w c z k a t 7 x 3 o t e t e a 5 3 g z o l / e l u o m c j v 7 1 s 9 t p s c a o n i r j r t u + l 5 o w x 8 o w w u m k 0 s 0 0 t t e z 4 q h t w c q x o d r m z 8 d o 0 j f v + i h o l c 1 p 0 e z 9 o z f j o f v y r l z t y d p u i 9 5 u / m / r z c a + c n m m 0 8 x q s e a l 4 o w j k 6 d p 5 6 j p f c w a closer look at the existing work on the empirical learnability of formal languages (see app. a for an overview) reveals a categorical mismatch between what lms are, i.e., probability distributions over strings, and what learning a formal language means, i.e., classifying strings as members of a specific language, i.e., a set of strings @xcite @xcite . in response, we propose to investigate the practical representation capacity of neural lms by testing their ability to learn distributions over strings. by sampling training corpora from probabilistic finite-state automata (pfsa), we can ask precise questions about the learnability. we offer an empirical study, sampling datasets of 20k strings from 2100 randomly generated pfsas, and training 15k rnn and transformer language models with a varying hidden state size on datasets. our study is informed by various theoretical results on the representational capacity of rnns concerning probabilistic finite-state automata. we assess the learnability by approximating the kl divergence between pfsas and neural lms. in a regression analysis, we find that a large number of properties of the automaton, e.g., the number of states, the number of transitions, the rank of its emission matrix, and its entropy all contribute to learnability. in particular, the rank of the emission matrix and expected length of the sampled strings are strong predictors of learnability for both rnn and transformer lms. several other predictors also demonstrate relevance in accounting for learnability, but have differing magnitudes and patterns of significance for the rnn and transformer lms. similar to @xcite , we find that rnns are better suited to modeling formal languages than transformers. ## preliminaries we begin with an introduction of the relevant mathematical preliminaries, based on @xcite . an alphabet σ is a finite, non-empty set of symbols. the kleene closure σ ˚of the alphabet σ is the set of all strings of the symbols in σ. the length of the string y " y 1 . . . y t p σ ˚, denoted by |y| " t , is the number of symbols the string contains. a language model p is a probability distribution over σ ˚. two lms p and q are equivalent if p pyq " q pyq for all y p σ ˚. most modern lms define p pyq as a product of conditional probability distributions: ## representing rlms with neural lms neural lms have demonstrated an ability to model human language well. this raises the question of what enables their success in capturing human language and how we can improve them further. however, neural lms are notoriously challenging to analyze, making it difficult to state any formal claims on what they are (in)capable of modeling. to amend this, a large body of work has linked neural lms to formal models of computation. dpfsas feature prominently in this line of research @xcite @xcite . to facilitate a detailed inspection of how neural lms can represent dpfsas, we now formalize dpfsas in a way that is particularly easy to connect to softmax-normalized representation-based neural lms, see app. b for the definition of dpfsa. ## practical learnability of rlms our main goal is to provide a principled study of the ability of neural lms to learn rlms. we now describe and justify our experimental design. ## discussion implications of thm. 3.1. thm. 3.1 concretely quantifies the minimum size of the representation space of any neural lm required for the correct representation of regular lms. while this is special case of the so-called softmax bottleneck principle @xcite , it is, to the best of our knowledge, the first result connecting the principle to formal models of computation. practical implementations of rlms might use state spaces and alphabets of sizes ranging from tens of thousands to hundreds of thousands @xcite , which is much larger than the representa- takeaways from the empirical results. the empirical results in §5.2 complement the theoretical discussion from §3 and the growing field of literature characterizing the representational capacity of neural lms. in line with the theoretical setting and in contrast to related work, our approach directly evaluates the kl divergence between neural lms and dpfsas, instead of relying on classification or next-token prediction accuracy measures. comparing distributions over strings offers a more holistic view of a neural lm's overall ability to emulate dpfsas allowing us to provide compelling insights into what aspects of distributions affect the learnability of formal lms by controlling for various properties of the dpfsas being learned. neatly, the observed effects of the rank and the neural lm hidden state size on kl divergence align with the theoretical results derived in thm. 3.1: namely, as the rank of a dpfsa grows, a larger hidden state is required in the neural lm to model the dpfsa's language appropriately. the dependence of the performance on the rank of the dpfsa demonstrates the utility of formal language theory in providing interpretable insights into the learning abilities of neural lms. another noteworthy observation is the negative influence of the dpfsa entropy on the kl divergence, indicating that neural lms tend to better learn rlms with higher intrinsic randomness. a possible explanation for this counter-intuitive result is that when a dpfsa is truly random, its simulation is trivial. however, it is more challenging to accurately learn rlms with more underlying latent structures. extensions. we focus on the learnability of deterministic pfsas. this makes the theoretical results from §3 particularly interpretable. extensions to the non-deterministic automata, however, are an interesting next step. note that in this case, the pfsa rank analysis is slightly more nuanced. a non-deterministic pfsa can, at any point, be in any of the |q| states (with a probability distribution over them), meaning that the probability of the next symbol is a convex combination of the individual conditional probability distributions (not their logits). this makes the analysis trickier and less interpretable; we leave it for future work to make the current exposition more concise. a further interesting follow-up is also the study of the learnability of (deterministic) context-free lms represented by probabilistic pushdown automata (pp-das). ppdas augment pfsas by implementing a stack that gives the automaton infinitely many configurations. despite the infinitely many configurations, controlling for their rank analogously to the rank of a pfsa could elucidate how efficiently they are representable by neural lms. ## conclusion we provide a comprehensive empirical study of the learnability of dpfsas by neural lms. more concretely, we investigate how well rnn and transformer lms learn to match the distributions over strings generated by dpfsas of varying complexity. to this end, we operationalized learning difficulty using the kl divergence between such distributions over strings; this measure holistically captures the similarity between the neural lm and the targeted regular lm. in an regression analysis of kl divergence variation, several complexity parameters of the dpfsa reached significance, along with the hidden state size of the neural lm. of note were the dpfsa rank and the expected length of sampled strings, which corresponded to significant increases in kl divergence across the rnn and transformer results. we establish that for equivalence, a neural lm's hidden state size is theoretically lower-bounded by the dpfsa's rank. this is consistent with the results of our controlled experiments. our results demonstrate that using probabilistic formal language theory can help us generate insights into what neural lms can and cannot learn. nevertheless, our findings call for further theoretical investigations closer to practical applications.