Neural Networks and the Chomsky Hierarchy β part 4/6
Cleaned-text code points [45622, 61277). Bibliography omitted here; source.md includes it.
A vanilla CNN, consisting of 5 convolutional layers with 32 channels each and a final MLP that produces the task output(s). We compute 2D convolutions over the time and (one-hot encoding) channel dimension. That is, the first kernel will consider the entire one-hot encoding at once for every time step. For all other kernel dimensions (time and filters), we sweep over the values { 3 , 5 , 7 , 11 } \{3,5,7,11\} .
### A.3 Tasks
Here, we describe our tasks (listed in Table A.1 ) in more detail. As mentioned in Section 4 , all tasks consist of an input sequence π β L I \bm{x}\in L_{I} from which the models have to predict the target sequence π β L O \bm{y}\in L_{O} . We append | π | |\bm{y}| empty tokens β
\varnothing to the input sequence, such that the models can process the entire input sequence before having to produce the output (i.e., they know the input length before having to produce the output). Note that half of our tasks have an output length of 1 and are thus just standard classification tasks with the set of classes being the alphabet of the output language. The networks still see one empty token β
\varnothing at the end of the input string to signify that the input phase has finished and that the output must be computed. We do not consider NDCF tasks since the distinction between DCF and NDCF is fairly technical and does not fundamentally change the type of memory structure required (i.e., a stack).
##### Even Pairs ( R )
Given a binary sequence, e.g., π = a β a β b β b β a \bm{x}=aabba , compute if the number of a β b ab s and b β a ba s is even. For a β a β b β b β a aabba , we have one a β b ab and b β a ba , meaning that the total number is 2 and thus even, i.e., π = b \bm{y}=b (where we arbitrarily equate odd with a a and even with b b ). This task is equivalent to computing whether the first and last character of the string are equal. Therefore, the task is regular since we can solve it with a 2-state finite-state machine that looks at the first bit of the sequence and compares it with the last one.
##### Modular Arithmetic (Simple) ( R )
Given a sequence of numbers in { 0 , 1 , 2 , 3 , 4 } \{0,1,2,3,4\} and operations in { + , β , β
} \{+,-,\cdot\} , compute the result modulo 5. For example, π = 1 + 2 β 4 \bm{x}=1+2-4 evaluates to π = 4 \bm{y}=4 . Note that the length of the input sequences must be of odd. Therefore, if we sample an even length during the training/evaluation process, we return an input sequence of this length plus 1. This task is regular since we can solve it with a 5-state finite-state machine, which transitions for each new operation with the state being equal to the current result.
##### Parity Check ( R )
Given a binary string, e.g., a β a β a β b β b β a aaabba , compute if the number of b b s is even. The sequence π = a β a β a β b β b β a \bm{x}=aaabba contains 2 b b s, which is even, i.e., π = b \bm{y}=b (where we arbitrarily equate odd with a a and even with b b ). This task is regular since we can solve it with a 2-state finite-state machine, which transitions every time it sees a token different from its current state.
##### Cycle Navigation ( R )
Given a sequence of movements on a cycle of length 5, compute the end position. The movements are STAY , INCREASE , DECREASE and are represented as { 0 , 1 , 2 } \{0,1,2\} . The agent always starts at position 0. For example, 010211 010211 means the agent stops at position 0 + 0 + 1 + 0 β 1 + 1 + 1 0+0+1+0-1+1+1 = 2 2 , and the output class is 2 2 . This task is regular since we can solve it with a 5-state finite-state machine, similar to Modular Arithmetic (Simple) ( R ), as the task can be converted into a sum modulo 5.
##### Modular Arithmetic ( DCF )
Given a sequence of numbers in { 0 , 1 , 2 , 3 , 4 } \{0,1,2,3,4\} , brackets, and operations in { + , β , β
} \{+,-,\cdot\} , compute the result modulo 5. For example, the sequence π = β ( 1 β 2 ) β
( 4 β 3 β
( β 2 ) ) \bm{x}=-(1-2)\cdot(4-3\cdot(-2)) evaluates to π = 0 \bm{y}=0 . Note that we do not have the same problem of odd lengths as in Modular Arithmetic (Simple) ( R ), since we can use substrings of the form ( β z ) (-z) with z β { 0 , 1 , 2 , 3 , 4 } z\in\{0,1,2,3,4\} , which have length 4 and thus can be used to produce input strings of even length. The task is DCF since we can solve it with a 5-state finite-state machine and an external stack. That is, similar to the Modular Arithmetic (Simple) ( R ) task, the finite-state machine transitions for each new operation, with the state being equal to the current result. Moreover, the stack is used to handle brackets: The machine pushes if the current input token is an opening bracket, pops if it is a closing bracket, and uses no-ops to let the finite-state machine work otherwise.
##### Reverse String ( DCF )
Given a binary string, e.g., π = a β a β b β b β a \bm{x}=aabba , compute its reverse, i.e., π = a β b β b β a β a \bm{y}=abbaa . The task is DCF since we can solve it by pushing the tokens of the input sequence on a stack until the first empty token β
\varnothing appears and then popping the tokens from the stack, outputting the values one by one. This task cannot be solved with a finite-state machine since the number of possible outputs is infinite.
##### Solve Equation ( DCF )
Given an equation consisting of numbers in { 0 , 1 , 2 , 3 , 4 } \{0,1,2,3,4\} , brackets, operations in { + , β , β
} \{+,-,\cdot\} , and an unknown variable z z , compute the value of z z such that the equation holds modulo 5. For example, π = β ( z β 2 ) β
( 4 β 3 β
( β 2 ) ) = 0 \bm{x}=-(z-2)\cdot(4-3\cdot(-2))=0 modulo 5 holds for z = 1 z=1 , i.e., π = 1 \bm{y}=1 . This task is DCF since we can solve it by simulating all possible values of x x in a nondeterministic finite-state machine and producing each result using the same algorithm as in Modular Arithmetic ( DCF ). Note that a nondeterministic finite-state machine can be simulated with a deterministic one, implying that this task is DCF and not NDCF .
##### Stack Manipulation ( DCF )
Given a binary string representing a stackβs content (given bottom-to-top) and a sequence of push a a , push b b , or pop actions, execute the actions on the stack and return the final stack content (in a top-to-bottom manner, i.e., as if popping the resulting stack). For example, executing the sequence pop push a a pop on the stack a β b β b β a β a abbaa , i.e., π = a β b β b β a β a β pop β push a β pop \bm{x}=abbaa~\textsc{pop}{}~\textsc{push $a$}{}~\textsc{pop}{} , results in π = a β b β b β a \bm{y}=abba . If a pop action is called on an empty stack, the action is ignored. This task requires stack manipulation by design and is therefore DCF .
##### Binary Addition ( CS )
Given two binary numbers, e.g., 10010 10010 and 101 101 , compute their sum in base 2, i.e., π = 10111 \bm{y}=10111 for π = 10010 + 101 \bm{x}=10010+101 . The inputs and outputs are given in little-endian representation. The task is CS since it exhibits cross-serial dependencies because the two numbers are provided one after the other (and not bit-by-bit at the same time).
##### Binary Multiplication ( CS )
Given two binary numbers, e.g., 100 100 and 10110 10110 , compute their product in base 2, i.e., π = 1011000 \bm{y}=1011000 for π = 100 β 10110 \bm{x}=100*10110 . The inputs and outputs are given in little-endian representation. The task is CS since it exhibits cross-serial dependencies because the two numbers are provided one after the other (and not bit-by-bit at the same time).
##### Compute Sqrt ( CS )
Given a binary number, e.g., 101001 101001 , compute the floor of its square root, i.e., π = β 101001 β = 101 \bm{y}=\lfloor\sqrt{101001}\rfloor=101 . The inputs and outputs are given in little-endian representation. This task is CS since the digit-by-digit algorithms to compute the integer square root require many sequence manipulations, including binary multiplications, which is a CS task.
##### Duplicate String ( CS )
Given a binary string, e.g., π = a β b β a β a β b \bm{x}=abaab , output the string twice, i.e., π = a β b β a β a β b β a β b β a β a β b \bm{y}=abaababaab . This task is CS since it corresponds to the well-known language { w β w | w β is β a β word } \{ww~|~w~\mathrm{is~a~word}\} (cf. Section 3 ), which is CS .
##### Missing Duplicate ( CS )
The input is a binary string of the form w β w ww where w w is itself a binary string. One token in this string has been hidden, and the network must find out which one it is, by looking at the value at the same position but on the other side of the string. For instance, if π = a β b β _ β a β b β a \bm{x}=ab\_aba (i.e., w = a β b β a w=aba ), then π = a \bm{y}=a . This task is CS since it requires on the recognition of the well-known language { w β w | w β is β a β word } \{ww~|~w~\mathrm{is~a~word}\} (cf. Section 3 ), which is CS .
##### Odds First ( CS )
Given a binary string t 1 β β¦ β t n t_{1}...t_{n} , output t 1 β t 3 β t 5 β β¦ β t 2 β t 4 β t 6 β β¦ t_{1}t_{3}t_{5}...t_{2}t_{4}t_{6}... . For example, the output corresponding to π = a β a β a β b β a β a \bm{x}=aaabaa is π = a β a β a β a β b β a \bm{y}=aaaaba . The task is CS because it exhibits cross-serial dependencies (the output is the interleaved input).
##### Bucket Sort ( CS )
Given a string over an alphabet of fixed size (5 in our case), return the sorted string. Since the alphabet has a fixed size, the task can be solved via bucket sort, which only requires a finite amount of counters (i.e., 5 counters in our case). For example, the output corresponding to π = 421302214 \bm{x}=421302214 is π = 011222344 \bm{y}=011222344 . The task is CS because it requires multiple counters that keep track of the number of occurrences for every token.
### A.4 Problem setup
We now provide the full formalization of our problem setup (described in Section 4 ). Algorithm 1 illustrates our training procedure. We train on sequences of length β βΌ π° β‘ ( 1 , N ) \ell\sim\mathcal{U}(1,N) , with N = 40 N=40 (using batches of size 128). For testing, we consider sequences of length sampled from π° β‘ ( N + 1 , M ) \mathcal{U}(N+1,M) , with M = 500 M=500 . In general, we report the score, which we define as the per-sequence accuracy A A (see Section 4 ) averaged over all sequences of unseen length, i.e., score := 1 M β N β β β = N + 1 M A β‘ ( π , π ) \mathrm{score}:=\frac{1}{M-N}\sum_{\ell=N+1}^{M}A(\bm{x},\bm{y}) . We use the Adam optimizer ( Kingma & Ba, 2015 ) with default hyperparameters for 1 000 000 1\,000\,000 steps, which we have found to be sufficient to achieve a near-optimal training performance for all tasks and architectures. As described in Algorithm 1 , we augment our input sequences π \bm{x} with m m empty tokens β
\varnothing , where m m is the length of the corresponding target sequence π \bm{y} , so that the networks only need to start outputting after they have consumed the entire input sequence. Moreover, we add computational tokens (which are different from the empty tokens β
\varnothing ) to the input sequence π \bm{x} for the Tape-RNN to enable it to perform memory operations without having to output the result. In general, we run all experiments with 10 different random seeds (used for network parameter initialization) and three learning rates ( 1 Γ 10 β 4 1\text{\times}{10}^{-4} , 3 Γ 10 β 4 3\text{\times}{10}^{-4} and 5 Γ 10 β 4 5\text{\times}{10}^{-4} ), and we report the result obtained by the hyperparameters with the maximum score (means and standard deviations in Appendix B ). However, for Transformers, NDStack-RNNs, and Tape-RNNs we sweep over additional hyperparameters: For Transformers we consider five different positional encodings, for the NDStack-RNN we optionally read from internal states of the nondeterministic stack (one of the improvements proposed by DuSell & Chiang (2022) ) and sweep over 2 and 4 symbols, and for the Tape-RNN we consider various numbers of computation tokens (0, β \ell , or 2 β β 2\ell ), and various numbers of tapes (1 and 4).
### A.5 Computational resources
We implemented our evaluation suite in JAX ( Bradbury et al., 2018 ) using the DeepMind JAX ecosystem ( Babuschkin et al., 2020 ; Hessel et al., 2020 ; Hennigan et al., 2020 ) . We make all of our code publicly available at https://github.com/deepmind/neural_networks_chomsky_hierarchy . We ran each task-architecture-hyperparameter triplet on a single TPU on our internal cluster. For RNNs, Stack-RNNs, LSTMs and Stack-LSTMs, the hyperparameters we have used are learning rates and seeds, which gives 15 β ( tasks ) β
4 β ( models ) β
3 β ( learning β rates ) β
10 β ( seeds ) = 1800 15~(\mathrm{tasks})\cdot 4~(\mathrm{models})\cdot 3~(\mathrm{learning~rates})\cdot 10~(\mathrm{seeds})=1800 TPU-units. For Tape-RNNs, the hyperparameters we have used are the learning rate, the number of computation steps tokens, the number of tapes, and the random seeds, which yields 15 β ( tasks ) β
3 β ( learning β rates ) β
3 β ( computation β steps ) β
2 β ( tapes ) β
10 β ( seeds ) = 2700 15~(\mathrm{tasks})\cdot 3~(\mathrm{learning~rates})\cdot 3~(\mathrm{computation~steps})\cdot 2~(\mathrm{tapes})\cdot 10~(\mathrm{seeds})=2700 TPU-units. For Transformers (encoder and autoregressive), the hyperparameters we have used are the learning rate, the positional encodings, and the random seeds, which gives 15 β ( tasks ) β
2 β ( models ) β
5 β ( positional β encodings ) β
3 β ( learning β rates ) β
10 β ( seeds ) = 4500 15~(\mathrm{tasks})\cdot 2~(\mathrm{models})\cdot 5~(\mathrm{positional~encodings})\cdot 3~(\mathrm{learning~rates})\cdot 10~(\mathrm{seeds})=4500 TPU-units. For the NDStack-RNN, the hyperparameters we have used are the learning rate, the number of stack symbols, and the random seeds, which gives 15 β ( tasks ) β
2 β ( number β of β symbols ) β
3 β ( learning β rates ) β
10 β ( seeds ) = 900 15~(\mathrm{tasks})\cdot 2~(\mathrm{number~of~symbols})\cdot 3~(\mathrm{learning~rates})\cdot 10~(\mathrm{seeds})=900 TPU-units. Moreover, we used an additional 300 300 TPU-units for the phase transition experiment ( Section B.2 ). For the CNN experiment, we used 15 β ( tasks ) β
4 β ( kernel β sizes ) β
3 β ( learning β rates ) β
10 β ( seeds ) = 1800 15~(\mathrm{tasks})\cdot 4~(\mathrm{kernel~sizes})\cdot 3~(\mathrm{learning~rates})\cdot 10~(\mathrm{seeds})=1800 TPU-units. For the scaling laws experiment, we used 15 β ( tasks ) β
3 β ( training β steps ) β
5 β ( num β layers ) β
3 β ( learning β rates ) β
10 β ( seeds ) = 6750 15~(\mathrm{tasks})\cdot 3~(\mathrm{training~steps})\cdot 5~(\mathrm{num~layers})\cdot 3~(\mathrm{learning~rates})\cdot 10~(\mathrm{seeds})=6750 TPU-units. Finally, for the autoregresive experiments (excluding the autoregressive Transformer), we used 8 β ( tasks ) β
3 β ( learning β rates ) β
10 β ( seeds ) = 240 8~(\mathrm{tasks})\cdot 3~(\mathrm{learning~rates})\cdot 10~(\mathrm{seeds})=240 TPU-units for the RNNs, Stack-RNNs, and LSTMs, i.e., 720 720 TPU-units, and 8 β ( tasks ) β
3 β ( computation β steps ) β
2 β ( tapes ) β
3 β ( learning β rates ) β
10 β ( seeds ) = 1440 8~(\mathrm{tasks})\cdot 3~(\mathrm{computation~steps})\cdot 2~(\mathrm{tapes})\cdot 3~(\mathrm{learning~rates})\cdot 10~(\mathrm{seeds})=1440 TPU-units for the Tape-RNNs. Thus, in total we used 20 910 20\,910 TPU-units. We report all the running times, for each task and architecture, in Table A.2 . Note that we aggregated the results over the hyperparameters, which explains the high standard deviation for Transformers (five different positional encodings) and Tape-RNN (three different numbers of computation steps tokens, two different numbers of tapes).