Neural Networks and the Chomsky Hierarchy — part 2/6

Cleaned-text code points [14220, 29740). Bibliography omitted here; source.md includes it.

An automaton recognizes a language if it accepts all strings in the language and no others. For example, a (deterministic) finite-state automaton finite-state automaton (FSA) can be defined as a 5-tuple ( Q , Σ , δ , q 0 , F ) (Q,\Sigma,\delta,q_{0},F) , consisting of a finite set of states Q Q , the finite alphabet Σ \Sigma , a transition function δ : Q × Σ → Q \delta:Q\times\Sigma\rightarrow Q , an initial state q 0 ∈ Q q_{0}\in Q , and a set of accept states F ⊆ Q F\subseteq Q . Thus, an FSA accepts a string w = a 1 ​ a 2 ​ … ​ a n w=a_{1}a_{2}\ldots a_{n} over the alphabet Σ \Sigma if there exists a sequence of states r 0 , r 1 , … , r n ∈ Q r_{0},r_{1},\ldots,r_{n}\in Q such that r 0 = q 0 r_{0}=q_{0} , r i + 1 = δ ⁡ ( r i , a i + 1 ) r_{i+1}=\delta(r_{i},a_{i+1}) for i = 0 , … , n − 1 i=0,\ldots,n-1 , and r n ∈ F r_{n}\in F . More complex automata, such as the push-down automaton (PDA) , additionally have access to an external memory structure. The Chomsky hierarchy classifies languages based on the automaton that can recognize it (see Table 1 ). All automata in the hierarchy have a finite state controller at their core, with increasingly flexible memory structures. Language classes generated by higher grammar types subsume languages generated by those lower in the hierarchy, e.g., all regular languages are CF , all CF languages are CS , etc. For technical reasons, we differentiate deterministic context-free (DCF) and nondeterministic context-free (NDCF) languages, since nondeterministic push-down automata (PDAs) can recognize some CF languages that deterministic PDA s cannot. We also consider (real-time) counter languages, which are recognized by finite automata with one or more (infinite) counters (or, equivalently, a PDA with one or more stacks and a single stack symbol). Counter languages are a proper superset of regular languages and a proper subset of CS languages (see Fig. 1 ).

##### Transduction vs. recognition

In practice, learning to recognize a formal language by training a classifier on words and non-words is hard because there is, in general, no formal construction for generating a sufficient but finite set of negative examples. For this reason, we consider language transduction tasks, where the inputs and outputs form two individual formal languages, and the goal is to learn a deterministic function that maps a word from one language to the other. Concretely, a deterministic finite transducer, defined as a 6-tuple ( Q , Σ I , Σ O , δ , q 0 , F ) (Q,\Sigma_{I},\Sigma_{O},\delta,q_{0},F) , differs from a finite-state automaton in that its transition function δ : Q × ( Σ I ∪ { ∅ } ) → ( Σ O ∪ { ∅ } ) × Q \delta:Q\times(\Sigma_{I}\cup\{\varnothing\})\rightarrow(\Sigma_{O}\cup\{\varnothing\})\times Q can output a symbol from the output alphabet Σ O \Sigma_{O} (or the dummy token ∅ \varnothing ) at every step. Thus, a transducer maps w I = a 1 ​ a 2 ​ … ​ a n w_{I}=a_{1}a_{2}\ldots a_{n} to w O = b 1 ​ b 2 ​ … ​ b n w_{O}=b_{1}b_{2}\ldots b_{n} if there exists a sequence of states r 0 , r 1 , … , r n ∈ Q r_{0},r_{1},\ldots,r_{n}\in Q such that r 0 = q 0 r_{0}=q_{0} , ( b i + 1 , r i + 1 ) = δ ⁡ ( r i , a i + 1 ) (b_{i+1},r_{i+1})=\delta(r_{i},a_{i+1}) for i = 0 , … , n − 1 i=0,\ldots,n-1 , and r n ∈ F r_{n}\in F . The transducer outputs b 1 = … = b k = ∅ b_{1}=\ldots=b_{k}=\varnothing while reading input word w I ′ = a 1 ​ … ​ a k ∈ Σ I w^{\prime}_{I}=a_{1}\ldots a_{k}\in\Sigma_{I} and outputs w O ′ = b k + 1 ​ … ​ b n ∈ Σ O w^{\prime}_{O}=b_{k+1}\ldots b_{n}\in\Sigma_{O} while reading dummy tokens a k + 1 = … = a n = ∅ a_{k+1}=\ldots=a_{n}=\varnothing . Transducers therefore define a deterministic function f : Σ I ∗ → Σ O ∗ f:\Sigma_{I}^{\ast}\rightarrow\Sigma_{O}^{\ast} , given by f ⁡ ( w I ′ ) = w O ′ f(w^{\prime}_{I})=w^{\prime}_{O} , between two formal languages, which is precisely what we want to learn. Thus, strictly speaking, we do not consider a hierarchy over formal languages but over language transduction tasks. Importantly, the machines required are identical to those in the Chomsky hierarchy, i.e., FSA s, PDA s, LBA s, and TM s (see Table 1 ), except that they can now also output values at each transition (i.e., the memory augmentations stay the same). We further discuss the transition from recognition to transduction, as well as prior approaches, in Section A.1 .

## 4 Methods

##### Problem setup

For each task we define input and output languages L I L_{I} and L O L_{O} , with their corresponding alphabets Σ I \Sigma_{I} and Σ O \Sigma_{O} . The goal of a task is to learn the deterministic function f f that maps words 𝒙 ∈ L I \bm{x}\in L_{I} to words 𝒚 ∈ L O \bm{y}\in L_{O} , i.e., language transduction. To that end, we consider models p θ ( ⋅ | 𝒙 ) p_{\theta}(\cdot|\bm{x}) as conditional distributions over next possible sequence continuations (with parameters θ \theta ). We one-hot encode the tokens in both languages L I L_{I} and L O L_{O} as vectors of length | Σ I | |\Sigma_{I}| and | Σ O | |\Sigma_{O}| , respectively, denoting the corresponding j j th entries of the i i th one-hot tokens x i ​ j x_{ij} and y i ​ j y_{ij} . We use gradient-based training to minimize the average cross-entropy loss, where C ( 𝒙 , 𝒚 ) := − 1 | 𝒚 | ∑ i y i T log p θ ( ⋅ | 𝒙 ) C(\bm{x},\bm{y}):=-\frac{1}{|\bm{y}|}\sum_{i}y_{i}^{T}\log p_{\theta}(\cdot|\bm{x}) denotes the per-example loss (see Algorithm 1 ). Note that we do not use auto-regressive models, but rather append | 𝒚 | |\bm{y}| empty dummy tokens to the input. Thus, the model will know when the input sequence 𝒙 \bm{x} has terminated by reading the first empty token. We compute the per-sequence accuracy as the percentage of correctly predicted tokens, i.e., A ( 𝒙 , 𝒚 ) := 1 | 𝒚 | ∑ i 𝟙 [ ( arg ​ max j y ij ) = ( arg ​ max j p θ ( ⋅ | 𝐱 ) j ) ] A(\bm{x},\bm{y}):=\frac{1}{|\bm{y}|}\sum_{i}\mathds{1}\left[(\argmax_{j}y_{ij})=(\argmax_{j}p_{\theta}(\cdot|\bm{x})_{j})\right] . Moreover, we compute the overall performance score as the per-sequence accuracy averaged over all sequences of unseen length. We run our experiments over 10 different network parameter initialization seeds and report the maximum score instead of the average, as this better indicates if an architecture is capable of learning the right algorithm at all (we provide the means and variances in Appendix B ).

##### Tasks

For each level of the Chomsky hierarchy, we define various sequence prediction tasks ranging from modular arithmetic ( R ) to binary addition ( CS ). We place the most emphasis on CS tasks as they are currently out of reach for state-of-the-art models and thus provide an ideal benchmark to guide future research on architecture design. We list the tasks in Table 2 and provide a full formalization in Table A.1 . Although seemingly simple, these tasks are well-known examples in the theory of computation and concisely demonstrate the key properties of the grammars in the Chomsky hierarchy, i.e., counting, repetition, long-distance dependencies, and hierarchy. Note that the levels of our tasks are independent of the levels of L I L_{I} or L O L_{O} but correspond to the automata that can solve the corresponding transduction tasks. For example, for the Reverse String task, L I = L O = { a , b } ∗ L_{I}=L_{O}=\{a,b\}^{*} , which are both regular . However, learning the function f f that maps w ∈ L I w\in L_{I} to r ​ e ​ v ​ e ​ r ​ s ​ e ​ ( w ) ∈ L O reverse(w)\in L_{O} requires a deterministic push-down transducer, thus rendering the task deterministic context-free .

##### Architectures

We consider a wide range of neural network architectures, including both state-of-the-art and memory-augmented models (full details in Section A.2 ). Our goal is to have at least one model per level of the Chomsky hierarchy. To that end, we use a standard RNN as a controller and augment it with two kinds of differentiable memory structures: a deterministic stack and a bounded tape. The stack and tape have elements in ℝ d \mathbb{R}^{d} with d = 8 d=8 , and we ensure that the stack and tape sizes are large enough to simulate infinite memory during training and testing. The Stack-RNN ( Joulin & Mikolov, 2015 ) can perform any linear combination of push , pop , and no-op operations on the stack. The Tape-RNN, which is inspired by the Baby-NTM ( Suzgun et al., 2019b ) , can perform any linear combination of write-left , write-right , write-stay , jump-right , jump-left (details in Appendix A ). In addition to these memory-augmented models, we also evaluate LSTMs ( Hochreiter & Schmidhuber, 1997 ) and Transformers ( Vaswani et al., 2017 ) . We compute the Transformer output from the encoder only model that overlooks the whole input sequence. We consider five different positional encodings: none, classical sin \sin / cos \cos ( Vaswani et al., 2017 ) , the rotary positional encodings (RoPE) ( Su et al., 2021 ) , ALiBi ( Press et al., 2021 ) , and the relative positional encodings of Transformer-XL ( Dai et al., 2019 ) . The latter two have been shown to allow extrapolation to longer sequences on some language modeling tasks. All models receive the tokens 𝒙 \bm{x} as an input and are expected to produce the output 𝒚 \bm{y} (i.e., we do not feed the output back to the input unlike sequence-to-sequence models ( Sutskever et al., 2014 ) ). We study CNNs, Stack-LSTMs, NDStack-RNNs ( DuSell & Chiang, 2020 ; DuSell & Chiang, 2022 ) , and autoregressive versions of our models in Appendix B .

##### Data generation

Instead of using fixed-size datasets, we define training and test distributions from which we continually sample sequences. We define the maximum training sequence length as the training range N N , with N = 40 N=40 . Every mini-batch is generated by first sampling a length ℓ \ell from the uniform distribution 𝒰 ⁡ ( 1 , N ) \mathcal{U}(1,N) and then sampling sequences of length ℓ \ell from the task’s generative grammar. For testing, we sample the sequence length ℓ \ell from 𝒰 ⁡ ( N + 1 , M ) \mathcal{U}(N+1,M) , with M = 500 M=500 .

We provide an open-source implementation of our models, tasks, and training and evaluation suite at https://github.com/deepmind/neural_networks_chomsky_hierarchy .

## 5 Results

In this section, we provide the results of our empirical evaluation. In Section 5.1 we relate the networks to the Chomsky hierarchy, in Section 5.2 we analyze the algorithms learned by the networks, and in Sections 5.3 and 5.4 we discuss the performance of LSTMs and Transformers in more detail.

### 5.1 Main result

We evaluate all architectures (defined in Section 4 ) on all tasks (defined in Table A.1 ) and show the generalization accuracy averaged over the segment 𝒰 ⁡ ( N + 1 , M ) \mathcal{U}(N+1,M) (as described in Section 4 ) in Table 2 . Furthermore, Fig. 2 displays the accuracy per sequence length for the best-performing model per architecture on three sample tasks (see Appendix B for the remaining tasks). As the test sequences have not been seen during training, we can gauge whether the architectures can learn the “correct” algorithm. We observe that the networks generally match the computational models associated with the Chomsky hierarchy: RNNs can solve tasks up to the regular level, Stack-RNNs up to the DCF level, and Tape-RNNs up to the CS level. However, the match is not perfect, as some architectures cannot solve tasks at their supposed level, e.g., Stack-RNN cannot solve Solve Equation ( DCF ) and the Tape-RNN cannot solve the (challenging) Binary Multiplication ( CS ) and Compute Sqrt ( CS ) tasks. This may be due to shortcomings in the architecture, the training protocol, or the particular difficulty of the tasks. For example, Solve Equation ( DCF ) is context-free but requires a nondeterministic FSA controller because it has to compute multiple modular arithmetic expressions for the different values of the unknown variable x x and compare their results to the actual solution of the equation, which is only provided at the end of the input sequence. Similarly, Binary Multiplication ( CS ) is a context-sensitive task but has a quadratic complexity, which is infeasible for the architectures we investigate. Conversely, some architectures show non-trivial performance on tasks beyond their supposed level, such as the Stack-RNN on Bucket Sort ( CS ) (more details in Appendix B ). Finally, we observe that Transformers and LSTMs are not well-aligned with the Chomsky hierarchy: Transformers fail on regular tasks, while LSTMs can solve (counting) tasks more difficult than regular . We discuss both cases in detail below ( Sections 5.3 and 5.4 ).

### 5.2 Analysis of learned program structure

To provide further evidence supporting the claim that some of the networks are able to learn the right algorithm, we now provide an analysis of solutions learned by some of our networks on our tasks, by investigating internal state representations and memory-update dynamics.

##### Regular tasks

According to the Chomsky hierarchy, we expect networks that solve regular tasks to simulate a finite-state automaton . We investigate this hypothesis by analyzing the internal states of the RNN controller and checking whether they are finite (or form a finite number of clusters). Figure 3(a) shows a scatter plot of a PCA projection of the internal RNN states when trained on Parity Check ( R ). We observe that the states form four clusters, each representing one of the four values of the tuple (subsequence result, last token seen). In principle, one can solve this task with only two states, corresponding to the subsequence result: If the state is 1 and the input token is 1, move to state 0, otherwise stay in state 1, and finally output the state itself. However, due to the problem symmetry, the network also learns to compute the parity of the number of zeros in the string, therefore adding another two states to the computation. We also investigate whether and how Stack-RNNs use their stack for this task, which is unnecessary, in principle. Indeed, the Stack-RNNs only use no-op or pop (which is equivalent to no-op in the absence of push ) actions, indicating that the RNN controller uses only a finite-state automaton and does not rely on the stack (see Section B.3 for more details).

##### Deterministic context-free tasks

On DCF tasks, we anticipate Stack-RNNs to use their stack. Indeed, on Reverse String ( DCF ), the networks learn the expected algorithm: push until an empty token appears, and then pop until the stack is empty. Moreover, the internal state of the controller seems to be largely guided by the last input token and not the last state (details in Section B.3 ). On Modular Arithmetic ( DCF ), which requires a stack to remember past results when entering a new bracket, the networks use the stack exactly as expected. Figure 3(b) shows that the Stack-RNN learns to solve this task by: (i) pushing the last result when a bracket is opened, (ii) not operating on the stack and only using its internal controller when a number or an operator is seen, and (iii) popping the last result from the stack when a bracket is closed. The top plot reports the probability of each action given an input, and the bottom plot shows the stack evolution along the sequence. On the bottom plot, the x-axis is the timestep and the y-axis is the cell position in the stack (top of the stack on the bottom). Each cell is colored according to the first principal component of its actual content.

##### Context-sensitive tasks