Neural Networks and the Chomsky Hierarchy — part 1/6
Cleaned-text code points [0, 14220). Bibliography omitted here; source.md includes it.
# Neural Networks and the Chomsky Hierarchy
###### Abstract
Reliable generalization lies at the heart of safe ML and AI. However, understanding when and how neural networks generalize remains one of the most important unsolved problems in the field. In this work, we conduct an extensive empirical study ( 20 910 20\,910 models, 15 tasks) to investigate whether insights from the theory of computation can predict the limits of neural network generalization in practice. We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of-distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTMs can solve regular and counter-language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.
## 1 Introduction
Statistical learning theory is the most widely used theory of generalization in practical machine learning, justifying empirical risk minimization and estimating the generalization error via a test set ( Vapnik, 1998 ) . However, its central assumption that training and test data are independent and identically distributed (i.i.d.) is violated for many problems of interest (distribution shifts, continual learning, etc.). An example of such a non-i.i.d. setting is testing generalization on sequence prediction problems, where an agent is trained with sequences of length ℓ ≤ N \ell\leq N and tested with arbitrarily longer sequences ℓ ≫ N \ell\gg N . This problem is of particular importance since it subsumes all computable problems ( Dawid, 1984 ; Rich, 2007 ; Sipser, 1997 ; Solomonoff, 2009 ; Solomonoff, 2010 ) . Central to sequence prediction is inductive inference , which consists of deriving a general rule from a finite set of concrete instances and using this rule to make predictions. For example, in program induction ( Goldberg, 1989 ; Gomez et al., 2008 ; Holland, 1992 ; Liang et al., 2013 ; Nordin, 1997 ; Solomonoff, 1964a ; Solomonoff, 1964b ; Wineberg & Oppacher, 1994 ) , the goal is to obtain a model that correctly identifies the underlying data-generating process given examples of input-output sequences. Then, if the model is correct, it can produce results in accordance with the generative process for previously unseen input sequences.
The key challenge of inductive inference (as opposed to deduction) is that it does not allow selecting one hypothesis with certainty among the ones that fit the data. For instance, the sequence 2 , 4 , 6 , 8 2,4,6,8 has infinitely many possible continuations. Thus, any principle that selects a particular continuation requires additional assumptions that are independent of the data, i.e., inductive biases ( Mitchell, 1980 ) . In machine learning, the network architecture, training mechanisms (e.g., gradient descent), and initial distributions over parameters all generate their corresponding inductive biases. This has led to a vast number of approaches for designing inductive biases via architectural and training protocol changes (see Battaglia et al. (2018) for an overview). However, the problem is that stronger inductive biases generally come at the cost of decreasing the universality of a model, and thus finding a good balance between the two is one of the biggest challenges in the contemporary literature.
Even if a neural architecture is theoretically universal or Turing complete, gradient-based training, which cannot exhaustively search the parameter space, can impede finding the right solution and thus practically render the model non-universal. Therefore, both architectural and training limitations impact which sequence prediction problems a model can solve in practice. In formal language theory, the Chomsky hierarchy ( Chomsky, 1956 ) classifies such (sequence prediction) problems by increasing complexity. This hierarchy is associated with an equivalent hierarchy of models (automata) that can solve different problem classes ( Savage, 1998 ; Sipser, 1997 ) . Lower-level automata have restrictive memory models and can only solve lower-level problems, while Turing machines with infinite memory and unrestricted memory access lie on top of the hierachy and can solve all computable problems. However, unlike for classical automata, a unified placement of neural architectures on the Chomsky hierarchy has not yet been practically established, which is precisely the goal of our work.
##### This work
We conduct an extensive empirical study with the aim of discovering how neural network models used for program induction relate to the idealized computational models defined by the Chomsky hierarchy in practice (see Fig. 1 for a summary of our findings). We investigate whether the theoretical limitations of certain neural models hold in practice when trained with gradient-based methods. For example, previous work has theoretically argued that RNNs are Turing complete ( Siegelmann & Sontag, 1994 ) . However, more recent theoretical analyses ( Ackerman & Cybenko, 2020 ; Merrill, 2019 ; Weiss et al., 2018 ) showed that RNNs lie much lower on the Chomsky hierarchy. To complement these theoretical analyses, we conduct a large-scale empirical evaluation on sequence prediction problems. We make the following main contributions:
• We conduct an extensive generalization study ( 20 910 20\,910 models, 15 tasks) of state-of-the-art neural network architectures (RNN, LSTM, Transformer) and memory-augmented networks (Stack-RNN, Tape-RNN) on a battery of sequence-prediction tasks spanning the entire Chomsky hierarchy that can be practically tested with finite-time computation.
• We open-source a length generalization benchmark ( https://github.com/deepmind/neural_networks_chomsky_hierarchy ) that is out of reach for state-of-the-art sequence prediction models and allows us to pinpoint the failure modes of these architectures.
• We show how increasing amounts of training data do not enable generalization on our tasks higher up in the hierarchy for some architectures (under sufficient capacity to perfectly learn the training data) potentially implying hard limitations for scaling laws ( Kaplan et al., 2020 ) .
• We demonstrate how augmenting architectures with differentiable structured memory (e.g., with a stack or a tape) can enable them to solve tasks higher up the hierarchy.
## 2 Related work
##### Learning formal languages
A long line of work has empirically investigated whether common machine learning architectures, including RNNs ( Elman, 1990 ) , GRUs ( Cho et al., 2014 ) , SCNs ( Giles et al., 1992 ; Pollack, 1991 ) , LSTMs ( Hochreiter & Schmidhuber, 1997 ) , and Transformers ( Vaswani et al., 2017 ) , are capable of learning formal languages. The main insights are: These networks can learn simple counting languages ( Hölldobler et al., 1997 ; Steijvers & Grünwald, 1996 ; Wiles & Elman, 1995 ; Rodriguez & Wiles, 1997 ) and the Dyck-1 language ( Skachkova et al., 2018 ; Suzgun et al., 2019a ) . To learn more advanced languages, RNNs and LSTMs require exponential memory in terms of the input length ( Sennhauser & Berwick, 2018 ) , as they lack an external memory structure. They are capable of learning simple context-sensitive languages, such as a n b n c n a^{n}b^{n}c^{n} , but in a very limited way, i.e., they generalize only to lengths close to those seen during training ( Bodén & Wiles, 2000 ; Bodén & Wiles, 2002 ; Gers & Schmidhuber, 2001 ) . Similarly, Transformers cannot learn Dyck- n n languages for n > 1 n>1 and long sequences ( Ebrahimi et al., 2020 ) . Concurrent work also studies length generalization on synthetic reasoning tasks (akin to learning formal languages) but for pretrained large language models ( Anil et al., 2022 ; Zhang et al., 2022 ) . Thus, while prior work has investigated a single architecture on a restricted set of tasks under different experimental conditions, we provide a unified experimental protocol that spans all the levels of the Chomsky hierarchy for a wide range of models.
##### Neural networks and the Chomsky hierarchy
It was theoretically shown that RNNs and Transformers are Turing complete ( Chen et al., 2018 ; Pérez et al., 2019 ; Pérez et al., 2021 ; Siegelmann & Sontag, 1994 ) . However, these results are impractical as they rely on an unbounded number of recurrent steps and on arbitrary numerical precision. Thus, more recent work ( Ackerman & Cybenko, 2020 ; Bhattamishra et al., 2020 ; Hahn, 2020 ; Hao et al., 2022 ; Korsky & Berwick, 2019 ; Merrill, 2019 ; Merrill et al., 2020 ; Merrill & Sabharwal, 2022 ; Weiss et al., 2018 ) has refined these theoretical analyses by considering linear computation steps and logarithmic precision, showing that: (i) RNNs and GRUs can, in theory, recognize regular languages, and (ii) LSTMs are strictly more powerful since they can learn a counting mechanism (i.e., are k-counter machines). Moreover, it was theoretically shown that Transformers are not well-aligned with the Chomsky hierarchy since they cannot recognize certain regular languages (e.g., periodic finite-state languages), while being able to learn some counter languages (e.g., Shuffle-Dyck and n n -ary Boolean expressions). A different approach proposed a computational model to capture the Transformer operations and used it to show which tasks could conceivably be learned by a Transformer (histograms, sorting, Dyck languages) ( Weiss et al., 2021 ) . However, this approach only upper-bounds the capabilities of a model and does not provide any insight on whether gradient-based methods will find parameters that can solve a task in practice, which is precisely the goal of our work. In that sense, our work complements the above studies by investigating how well gradient-based learning can exploit the inductive biases of common machine learning architectures to recognize languages on different levels of the Chomsky hierarchy.
##### Memory-augmented networks
A popular approach for augmenting neural architectures with external memory is to equip a recurrent network with read and write access to differentiable memory structures, such as deterministic stacks ( Das et al., 1992a ; Das et al., 1992b ; Grefenstette et al., 2015 ; Hao et al., 2018 ; Joulin & Mikolov, 2015 ; Mali et al., 2021 ; Mozer & Das, 1992 ; Stogin et al., 2020 ; Sun et al., 1993 ; Suzgun et al., 2019b ; Yogatama et al., 2018 ) , nondeterministic stacks ( DuSell & Chiang, 2020 ; DuSell & Chiang, 2022 ) , random access memory ( Danihelka et al., 2016 ; Kurach et al., 2016 ) , and memory matrices ( Graves et al., 2014 ; Graves et al., 2016 ; Gülçehre et al., 2018 ; Yang & Rush, 2017 ) . Such memory-augmented networks are capable of recognizing complex languages, including tasks like copying or reversing strings, but they can only perform one computation step per input token. Thus, to solve superlinear tasks (e.g., binary multiplication), memory-augmented networks also need to be able to perform a linear number of steps per token ( Freivalds & Liepins, 2017 ; Kaiser & Sutskever, 2016 ; Price et al., 2016 ) . In a different effort, reinforcement learning has been applied to interact with discrete memory interfaces, making deterministic memory operations amenable to gradient-based training ( Zaremba & Sutskever, 2015 ; Zaremba et al., 2016 ) . Finally, prior work also proposed networks with read-only memory access ( Sukhbaatar et al., 2015 ; Weston et al., 2015 ) or spatiotemporal connections ( Kalchbrenner et al., 2016 ) . We also consider memory-augmented networks and find that memory structures are necessary to generalize on sequence prediction problems higher up the Chomsky hierarchy.
## 3 Background
We now provide the necessary background on how to link sequence prediction and formal language theory, allowing us to associate neural architectures and the Chomsky hierarchy. As we want to evaluate the capability of networks to generalize to sequences of unseen length, we need a way of generating arbitrarily long sequences that all exhibit the same structure. To that end, we will consider sequences as elements of infinite formal languages, which are generated by a grammar.
##### Formal language
A formal language L L is a set of words, where each word is a finite string of symbols drawn from a finite alphabet Σ \Sigma . For example, with a binary alphabet Σ = { 0 , 1 } \Sigma=\{0,1\} we can describe the following infinite languages: A = { 0 n 1 m | n , m > 0 } A=\{0^{n}1^{m}~|~n,m>0\} , B = { w | w is a palindrome } B=\{w~|~w~\mathrm{is~a~palindrome}\} , C = { w w | w is a word } C=\{ww~|~w~\mathrm{is~a~word}\} , and D = { w | w describes a terminating Turing machine } D=\{w~|~w~\mathrm{describes~a~terminating~Turing~machine}\} .
##### Generative grammar
Languages of infinite cardinality can be generated with a finite alphabet and a finite generative grammar. A formal grammar ( Chomsky, 1956 ) is defined by a finite set of terminal symbols, a finite set of non-terminal symbols, a distinctive start symbol, and a finite set of production rules that map from non-terminal symbols to other symbols. The set of all words that can be formed by such a grammar is its corresponding formal language. For example, the binary palindrome language B B can be generated by the set of rules: P → ϵ ∣ 0 ∣ 1 ∣ 0 P 0 ∣ 1 P 1 P\rightarrow\epsilon\mid 0\mid 1\mid 0P0\mid 1P1 , with start and nonterminal symbol P P and terminal symbols { 0 , 1 } \{0,1\} . The Chomsky hierarchy arises from categorizing the allowed relationships between terminals and non-terminals in the grammar (see Table 1 ). For example, B B is not regular, since the right-hand side contains a variable enclosed by two terminal symbols, but context-free, since the left-hand side consists of a single nonterminal symbol.
##### Recognizing a language