A Survey of Neural Networks and Formal Languages ¹¹1This work was partially supported by DARPA Safedocs Program award HR001119C0075 for which SRI is the prime contractor and Dartmouth is a subcontractor.

We use $\mathcal{L}(M)$ to denote the language accepted by some machine $M$, and language classes such as the set of all regular languages, REGULAR, will be set in capitalized, bold text. We will assume knowledge of basic formal language theory, however we will define some possibly less common classes of languages. The first such language is a strictly $k$-local language. Fittingly, these are languages with very structured, local behavior of size $k$.

In contrast to Convolutional Neural Networks, Recurrent Neural Networks (RNNs) were specifically designed with sequential data in mind, and as such have been one of the most ubiquitous paradigms in fields centered around highly sequential like natural language processing. Roughly speaking, for each token $\textbf{x}_{t}$ in the input RNNs compute a state $\textbf{h}_{t}$ using the preceding state and the new token, i.e., $\textbf{h}_{t}=f(\textbf{x}_{t},\textbf{h}_{t-1})$ for some nonlinear function $f$. One of the simplest realizations of an RNN is the Simple Recurrent Neural Network (SRNN) [3], essentially just applies an affine transformation to $\textbf{x}_{t}$, $\textbf{h}_{t-1}$, before a non-linear function. The full SRNN network is defined by these update rules,

	$\displaystyle\textbf{h}_{t}=f_{h}(\textbf{W}\textbf{x}_{t}+\textbf{U}\textbf{h}_{t-1}+b_{h})$		(4)
	$\displaystyle\textbf{y}_{t}=f_{y}(\textbf{W}^{y}\textbf{h}_{t}+b_{y}).$		(5)

Although powerful, these networks have issues such as being highly susceptible to vanishing gradients [10], which motivated the development of more complex networks such as the Long Short Term Memory (LSTM) [10], or the Gated Recurrent Unit (GRU) [1]. LSTMs improve SRNNs by using more complicated rules to decide how information passes between states. Intuitively, LSTMs add “input”, “ouput”, and “forget” gates, $\textbf{i}_{t},\textbf{o}_{t},\textbf{f}_{t}$, which control how values move between memory cells – the fundamental units of the LSTM. Memory cells have state $\textbf{c}_{t}$, and input activation $\tilde{\textbf{c}}_{t}$. The input gate and output gates control how values come into and how the value affects the activation of a cell, meanwhile, the forget gate controls the extent to which a value remains in a cell. Compactly, an LSTM is given by the following update rules,

	$\displaystyle\textbf{f}_{t}=\sigma(\textbf{W}^{f}\textbf{x}_{t}+\textbf{U}^{f}\textbf{h}_{t-1}+b^{f})$		(6)
	$\displaystyle\textbf{i}_{t}=\sigma(\textbf{W}^{i}\textbf{x}_{t}+\textbf{U}^{i}\textbf{h}_{t-1}+b^{i})$		(7)
	$\displaystyle\textbf{o}_{t}=\sigma(\textbf{W}^{o}\textbf{x}_{t}+\textbf{U}^{o}\textbf{h}_{t-1}+b^{o})$		(8)
	$\displaystyle\tilde{\textbf{c}}_{t}=\tanh(\textbf{W}^{\tilde{c}}\textbf{x}_{t}+\textbf{U}^{\tilde{c}}\textbf{h}_{t-1}+b^{\tilde{c}})$		(9)
	$\displaystyle\textbf{c}_{t}=\textbf{f}_{t}\odot\textbf{c}_{t-1}+\textbf{i}_{t}\odot\tilde{\textbf{c}}_{t}$		(10)
	$\displaystyle\textbf{h}_{t}=\textbf{o}_{t}\odot\tanh(\textbf{c}_{t}),$		(11)

where $\odot$ is element-wise multiplication. A more modern variation of the LSTM is that of the GRU, which employs only two gating mechanisms making it faster, and simpler to implement. GRUs have a similar motivation to LSTMS, but rather than using “input”, “output”, and “forget” gates, the GRU has a “reset” gate and an “update” gate. The “update” gate, $\textbf{z}_{t}$ determines the balance of old memory and new memory used in updating the new state, while the “reset” gate $\textbf{r}_{t}$ controls how much influence the input versus the previous state has on the new state. Mathematically, the GRU is defined as follows,

	$\displaystyle\textbf{z}_{t}=\sigma(\textbf{W}^{z}\textbf{x}_{t}+\textbf{U}^{z}\textbf{h}_{t-1}+b^{z})$		(12)
	$\displaystyle\textbf{r}_{t}=\sigma(\textbf{W}^{r}\textbf{x}_{t}+\textbf{U}^{r}\textbf{h}_{t-1}+b^{r})$		(13)
	$\displaystyle\textbf{h}_{t}=\textbf{z}_{t}\odot\textbf{h}_{t-1}+(1-\textbf{z}_{t})\odot\tanh\left(\textbf{W}^{h}\textbf{x}_{t}+\textbf{U}^{h}(\textbf{r}_{t}\odot\textbf{h}_{t-1})+b^{h}\right).$		(14)

Despite being newer and quite similar in design, we will see that GRUs are not just less powerful than LSTMs, but only equally as powerful as SRNNs.

In [23], Weiss et al. show how a LSTM can emulate an SKCM. To summarize their construction: the choice to increment ($+1$) or decrement ($-1$) is made in $\tilde{\textbf{c}}_{t}$ via the $\tanh$ function which naturally makes this decision as a function of the input token and previous state. A cell, $\textbf{c}_{t}$, can maintain the counter when $\textbf{i}_{t}=1$ and $\textbf{f}_{t}=1$. For comparison operations, the counter is completely visible in $h_{t}$. Extending this, Merrill [15] shows that, asymptotically, $\mathcal{L}(\textsf{IBFP-LSTM})\subseteq\textbf{CL}$. Together these results give us the theorem below.

Transformer Networks [22] are a new, and increasingly popular architecture designed with the goal of improving machine translation. One practical advantage of Transformers, is they are far more parallelizable than RNNs, and learn long term dependencies more efficiently. Introduced by Vaswani et al., in their paper “Attention Is All You Need” [22], Transformers completely forgo classical recurrent connections for the notion of attention. Attention is a mechanism which enables a network to selectively recall a specific encoder state based on observed information. This process is modeled as a database-esque retrieval process involving a query $\textbf{q}\in\mathds{R}^{\ell}$, a $n\times\ell$ matrix of key vectors K, and a $n\times d$, matrix of value vectors V. However, unlike a traditional database retrieval, this process is “soft” meaning that for a given query we do not get the exact value back, but instead a sum of the values weighted by how similar each key is to the query. The compact notation expressing this idea is simply,

$$\textsf{attention}(\textbf{q},\textbf{K},\textbf{V})=\textsf{softmax}(\textbf{q}\textbf{K}^{\top})\textbf{V}.$$

Transformers use multiple attention heads in parallel, while simultaneously linearly projecting the queries, keys, and values with different, learned transformations. This enables them to leverage different trends across different embeddings. Then at the end, the output from each transformation is concatenated. This defines the notion of multihead attention [22],

	$\displaystyle\textbf{a}_{i}=\textsf{attention}(\textbf{W}^{q_{i}}\textbf{q},\textbf{W}^{K_{i}}\textbf{K},\textbf{W}^{V_{i}}\textbf{V})$		(15)
	$\displaystyle\textsf{multihead}(\textbf{q},\textbf{K},\textbf{V})=\textbf{a}_{1}||\cdots||\textbf{a}_{n}.$		(16)

Finally, the Transformer network studied in [15], is a variant adapted for language processing tasks [16], defined by,

	$\displaystyle\textbf{q}_{t},\textbf{k}_{t},\textbf{v}_{t}=\textbf{W}^{q_{t}}\textbf{x}_{t},\textbf{W}^{k_{t}}\textbf{x}_{t},\textbf{W}^{v_{t}}\textbf{x}_{t}$
	$\displaystyle\textbf{h}_{t}=\sigma(\textbf{W}^{h}\textsf{multihead}(\textbf{q},\textbf{K},\textbf{V})).$

Surprisingly, despite many transformers taking the spotlight in many top-performing natural language processing architectures, they are very weak asymptotically. A glaring flaw of the transformer architecture, is their positional invariance. Vaswani et al. incorporate a trick to augment the network with positional encodings to fix this, however they use periodic functions, which repeat asymptotically [22]. As such, in this setting Transformer Networks have quite limited power.

All of the previously described networks maintain bizarre implicit representations of the data, which always seem impede their formal capacity under the IBFP assumptions. One might wonder, what if we just used constructs from formal language theory explicitly as part of the model? This question motivates the idea of Memory Augmented Neural Networks (MANNs) which integrate explicit memory constructs such as stacks or tapes into neural network architectures. A drawback, is that implementing these constructs in a fully differentiable fashion, adds a considerable number of new hyperparameters to optimize and to analyse. For this reason, the literature including both formal and empirical focused work on the power of MANNs is relatively sparse compared to the other methods. However, as we will see these models have been used to perform interesting formal language focused tasks, and have very high representational power.

Recently, there have been a few proposals on ways to augment networks with differentiable stacks, the most relevent of which are [8] [13], and [20]. Grefenstette et al. empirically demonstrated that memory augmented LSTMs had superior performance over vanilla LSTMs on certain transduction tasks [8]. Meanwhile Joulin et al. [13] studied the ability of MANNs to learn variations of languages such as $a^{n}b^{n}$, however (unsurprisingly given theorem 3) they did not observe any superior performance in the augmented network over LSTMs. Lastly, [20] studied the ability for MANNs to learn $\mathcal{D}_{>1}$ languages. Due to its relevance to our work, and its relative similarity to the stack model described in [13], we will introduce Suzgun et al.’s Stack-RNN, and remark on the expressiveness of a more abstract variant.

The aptly named Stack-RNN [20] integrates a differentiable stack into a recurrent neural network by the following update rules.

	$\displaystyle\tilde{\textbf{h}}_{t-1}=\textbf{h}_{t-1}+\textbf{W}_{sh}\textbf{s}^{(0)}_{t-1}$		(17)
	$\displaystyle\textbf{h}_{t}=\tanh(\textbf{W}^{x}\textbf{x}_{t}+\textbf{U}^{h}\tilde{\textbf{h}}_{t-1}+b^{h})$		(18)
	$\displaystyle\textbf{y}_{t}=\sigma(\textbf{W}^{y}\textbf{h}_{t}+b^{y})$		(19)
	$\displaystyle\textbf{a}_{t}=\textsf{softmax}\left(\textbf{W}^{a}\textbf{h}_{t}\right)$		(20)
	$\displaystyle\textbf{n}_{t}=\sigma(\textbf{W}^{n}\textbf{h}_{t})$		(21)
	$\displaystyle\textbf{s}^{(0)}_{t}=\textbf{a}^{(0)}_{t}\textbf{n}_{t}+\textbf{a}^{(1)}_{t}\textbf{s}^{(1)}_{t-1}$		(22)
	$\displaystyle\textbf{s}^{(i)}_{t}=\textbf{a}^{(0)}_{t}\textbf{s}^{(i-1)}_{t-1}+\textbf{a}^{(1)}_{t}\textbf{s}^{(i+1)}_{t-1}$		(23)

The stack is maintained as $\textbf{s}_{t}=\textbf{s}^{(0)}_{t}\textbf{s}^{(1)}_{t}\cdots\textbf{s}^{(k)}_{t}$. The vector $\textbf{a}_{t}=[\textbf{a}_{t}^{(0)}\textbf{a}_{t}^{(1)}]$ encodes the PUSH and POP operations. For example, if $\textbf{a}_{t}^{(0)}=1$ (PUSH) then all the stack elements $\textbf{s}_{t}^{(i)}$ are pushed down (Eq. 23), and the topmost element is changed to the new value $\textbf{n}_{t}$. Likewise, if $\textbf{a}_{t}^{(1)}=1$ (POP), then each stack element is shifted down. Moreover, the hidden state (Eq. 17, 18) equations have been adapted to take into consideration the topmost stack element.

Unsurprisingly, Neural Stacks have been quite successful at certain formal language tasks, and similar abstract models which implement stack interfaces, as studied in [15], are known to inherit a great deal of expressive power from the addition of a stack. Suzgun et al. show that Neural Stacks can learn $\mathcal{D}_{1}$, $\mathcal{D}_{2}$, $\mathcal{D}_{3}$, and even $\mathcal{D}_{6}$ languages with 99%-100% accuracy (often closer to 100%) on both training and test sets [20]. Merrill [15], shows that for his abstract, definition of a neural stack the following holds.

Overall, MANNs certainly show a great deal of promise and potential to learn complex formal languages. However, due to their relative novelty they are far less understood, and less mature than other models we discussed in this paper. As such, there is certainly a great deal of room for future work leveraging these architectures.