On the Computational Power of RNNs

Introduction

Recent work suggests that recurrent “neural network” models of several types perform better than sequential models in acquiring and processing hierarchical structure. Indeed, recurrent networks have achieved state-of-the-art results in a number of natural language processing tasks, including named-entity recognition , language modeling , sentiment analysis , natural language generation , and beyond.

The hierarchical structure associated with natural languages is often modeled as some variant of context-free languages, whose languages may be defined over an alphabet $\displaystyle\Sigma$. These context-free languages are exactly those that can be recognized by pushdown automata (PDAs). Thus it is natural to ask whether these modern natural language processing tools, including simple recurrent neural networks (RNNs) and other, more advanced recurrent architectures, can learn to recognize these languages.

The computational power of RNNs has been studied extensively using empirical testing. Much of this research , focused on the ability of RNNs to recognize simple context-free languages such as $\displaystyle a^{n}b^{n}$ and $\displaystyle a^{n}b^{m}B^{m}A^{n}$, or context-sensitive languages such as $\displaystyle a^{n}b^{n}c^{n}$. Related works , , focus instead on Dyck languages of balanced parenthesis, which motivates some of our methods. Gated architectures such as the Gated Recurrent Unit (GRU) and Long Short-Term Memory (LSTM) obtain high accuracies on each of these tasks. While simpler RNNs have also been tested, one difficulty is that the standard hyperbolic tangent activation function makes counting difficult. On the other hand, RNNs with ReLU activations were found to perform better, but suffer from what is known as the “exploding gradient problem” and thus are more difficult to train .

Instead of focusing on a single task, many researchers have studied the broader theoretical computational power of recurrent models, where weights are not trained but rather initialized to recognize a desired language. A celebrated result shows that a simple recurrent architecture with 1058 hidden nodes and a saturated-linear activation $\displaystyle\sigma$ is a universal Turing Machine, with:

However, their architecture encodes the whole input in its internal state and the relevant computation is only performed after reading a terminal token. This differs from more common RNN variants that consume tokenized inputs at each time step. Furthermore, the authors admit that were the saturated-linear activation to be replaced with the similar and more common sigmoid or hyperbolic tangent activation functions, their methodology would fail.

More recent work suggests that single-layer RNNs with rectified linear unit (ReLU) activations and softmax outputs can also be simulated as universal Turing Machines, but this approach again suffers from the assumption that the entire input is read before computation occurs.

Motivated by these earlier theoretical results, in this report we seek to show results about the computational power of recurrent architectures actually used in practice - namely, those that read tokens one at a time and that use standard rather than specially chosen activation functions. In particular we will prove that, allowing infinite precision, RNNs with just one hidden layer and ReLU activation are at least as powerful as PDAs, and that GRUs are at least as powerful as deterministic finite automata (DFAs). Furthermore, we show that using infinite edge weights and a non-standard output function, GRUs are also at least as powerful as PDAs.

Simple RNNs

Let a simple RNN be an RNN with the following architecture:

In practice, the inputs and hidden nodes of an RNN are stored as numbers with finite precision. Including this restriction, we show the following result:

Theorem 1.1. For every language $\displaystyle L\subseteq\Sigma^{*}$, $\displaystyle L$ is regular if and only if $\displaystyle L$ is the $\displaystyle S$-language of some finite precision simple RNN.

set of $\displaystyle 2^{mk}$ states $\displaystyle Q=\{q_{h}:h\ \text{is a possible hidden state of the RNN}\}$

transition function $\displaystyle\delta$ where $\displaystyle\delta(q_{h},x)=q_{f(W_{x}x+W_{h}h+b_{h})}$

set of accepting states $\displaystyle F=\{q_{h}|W_{h}h+b_{o}\in S\}$

It’s clear that after reading the first $\displaystyle n$ inputs of a word $\displaystyle w$, the current state of this DFA is $\displaystyle q_{h_{n}}$, which immediately completes the proof of this direction.

For the “only if” direction, suppose we have a DFA $\displaystyle D=(Q,\Sigma,\delta,q_{0},F)$ with corresponding language $\displaystyle L$. We will construct a simple RNN whose inputs are one-hotted symbols from $\displaystyle\Sigma$, with ReLU activation function $\displaystyle f(x)=\text{max}(0,x)$, and with $\displaystyle|Q||\Sigma|$ hidden nodes whose $\displaystyle\{0\}$-language is $\displaystyle L$.

The RNN has three layers: the first layer (input layer) has $\displaystyle|\Sigma|+|Q||\Sigma|$ nodes; the second layer (hidden layer) has $\displaystyle|Q||\Sigma|$ nodes; and the third layer (output layer) has one node. For the $\displaystyle|\Sigma|$ nodes in the input layer associated with the one-hot of the current symbol, label each node with its corresponding symbol from $\displaystyle\Sigma$. Label the $\displaystyle|Q||\Sigma|$ hidden nodes (in both the first and second layers) with all $\displaystyle|Q||\Sigma|$ symbol-state combinations $\displaystyle(x,q)$ for $\displaystyle x\in\Sigma$ and $\displaystyle q\in Q$.

For every $\displaystyle x\in\Sigma$, connect the node in the input layer with label $\displaystyle x$ to all nodes in the hidden layer with labels $\displaystyle(x,q)$ for any $\displaystyle q\in Q$ with edges with weight $\displaystyle 1$. For all $\displaystyle(x,q)\in\Sigma\times Q$, connect the node in the input layer with label $\displaystyle(x,q)$ to all nodes in the hidden layer with labels $\displaystyle(x^{\prime},q^{\prime})$ where $\displaystyle\delta(q,x^{\prime})=q^{\prime}$ with edges also of weight $\displaystyle 1$. Finally, for all $\displaystyle(x,q)\in\Sigma\times Q/F$, connect the node in the hidden layer with label $\displaystyle(x,q)$ to the single node in the output layer with an edge of weight $\displaystyle 1$.

Each of the hidden nodes are initialized to $\displaystyle 0$ except a single hidden node with label $\displaystyle(x,q_{0})$ for a randomly chosen $\displaystyle x\in\Sigma$, which is initialized to $\displaystyle 1$. To complete the description of the RNN, we set $\displaystyle b_{h}=-1$ and $\displaystyle b_{o}=0$. We claim that the following invariant is maintained: after reading some word, suppose the current state of $\displaystyle D$ is $\displaystyle q$. Then after reading the same word, the hidden nodes of the RNN would all be equal to $\displaystyle 0$ except for one node with label $\displaystyle(x,q)$ for some $\displaystyle x\in\Sigma$, which would equal $\displaystyle 1$.

We prove the claim by induction on the length of the inputted word $\displaystyle n$. The base case of $\displaystyle n=0$ is trivial. Now assume that after reading a word of length $\displaystyle n$ the current state of $\displaystyle D$ is $\displaystyle q$, and after reading that same word all hidden nodes of the RNN are equal to $\displaystyle 0$ except one node with label $\displaystyle(x,q)$ for some $\displaystyle x\in\Sigma$, which is equal to $\displaystyle 1$. If the next symbol is $\displaystyle x^{\prime}$, then the current state of $\displaystyle D$ would be $\displaystyle q^{\prime}$ where $\displaystyle\delta(q,x^{\prime})=q^{\prime}$. For the RNN, the input layer will have exactly two $\displaystyle 1$s, namely the node with label $\displaystyle x^{\prime}$ and the node with label $\displaystyle(x,q)$. Since all edges have weight $\displaystyle 1$, that means that before adding $\displaystyle b_{h}$ or applying $\displaystyle f$ the maximum value a node in the hidden layer can take on is $\displaystyle 2$. For this to occur it must be connected to both the nodes in the input layer with value $\displaystyle 1$, and thus by definition its label must be $\displaystyle(x^{\prime},\delta(q,x^{\prime}))=(x^{\prime},q^{\prime})$. By integrality every other node in the hidden layer will take on a value of at most $\displaystyle 1$, so after adding $\displaystyle b_{h}=-1$ and applying $\displaystyle f$ we easily see that the invariant is maintained.

Utilizing this invariant it is clear that upon reading a word $\displaystyle w\in L$ the RNN will output $\displaystyle 0$, and upon reading a word $\displaystyle w\not\in L$ it will output $\displaystyle 1$. Thus $\displaystyle L$ is precisely the $\displaystyle\{0\}$-language of the RNN and the theorem is proven.∎

Discussion 1.2. This result shows that simple RNNs with finite precision are exactly as computationally powerful as DFAs. In terms of reducing the size of the hidden layer constructed in the proof of the “only if” direction, it seems likely that $\displaystyle|Q||\Sigma|$ is optimal since $\displaystyle\delta$ is defined on $\displaystyle|Q||\Sigma|$ inputs and needs to be captured fully by the RNN.

Removing the finite precision stipulation unsurprisingly increases the capabilities of RNNs. It is natural to now ask whether these simple RNNs can recognize more complicated $\displaystyle S$-languages, and indeed the answer is affirmative. Thus we shift our focus to context-free languages. We begin with some preliminaries:

The Dyck language $\displaystyle D_{n}$ consists of all words over the size $\displaystyle 2n$ alphabet $\displaystyle\Sigma=\bigcup\limits_{i=1}^{n}\{(_{i},)_{i}\}$ that correspond to a balanced string of $\displaystyle n$ types of parentheses. We also define the set of proper prefixes

so that any word in $\displaystyle P_{n}$ is the prefix of a word in $\displaystyle D_{n}$ but is itself unbalanced. We proceed with a motivating theorem:

Proof. The interested reader may find a proof in . ∎

Thus it makes sense to focus on constructing sets $\displaystyle S$ and simple RNNs whose $\displaystyle S$-language is $\displaystyle D_{n}$. Indeed, since $\displaystyle D_{n}=g^{-1}(D_{2})$ for some homomorphism $\displaystyle g$, we start by focusing on $\displaystyle D_{2}$, in some sense the “hardest” context-free language.

Consider the word $\displaystyle(_{2}(_{1})_{1}(_{2}(_{1})_{1})_{2})_{2}$. The evolution of the state as the word is read symbol by symbol is given by

This example makes it clear that this notion of state accurately captures all the relevant information about words in $\displaystyle P_{2}\cup D_{2}$.

The difficulty in capturing this notion of state in a RNN is that the constant to multiply $\displaystyle s_{t-1}$ by changes depending on the input (it can be either $\displaystyle 2$ or $\displaystyle 1/2$ in our example above). Thus storing $\displaystyle s_{t}$ in a single hidden node is impossible. Instead, we use two hidden nodes. Below, we generalize from $\displaystyle D_{2}$ to $\displaystyle D_{n}$.

Ignoring the output layer for now, consider the simple RNN defined by

where the inputs $\displaystyle x$ are $\displaystyle 2n\times 1$ one-hots of the symbols in $\displaystyle\Sigma$ (the alphabet of $\displaystyle D_{n}$) in the order $\displaystyle(_{1},(_{2},\dots,(_{n},)_{1},)_{2},\dots,)_{n}$ and the hidden states have dimension $\displaystyle 2\times 1$ where

for all $\displaystyle i\in\{1,2,\dots,n\}$.

This is similar to the state we defined before, though now generalized to $\displaystyle D_{n}$ and also with intentionally present blank space inserted between the digits in base $\displaystyle 2n+1$. We will show the following invariant:

Lemma 1.4. Given an input word $\displaystyle w\in P_{n}\cup D_{n}$, we have $\displaystyle h_{t}=[s_{t}\ \ 0]^{T}$ or $\displaystyle h_{t}=[0\ \ s_{t}]^{T}$ for all $\displaystyle t$.

Proof. We proceed by induction on $\displaystyle t$. The base case of $\displaystyle t=0$ is trivial. Now, suppose $\displaystyle w_{t+1}=(_{i}$ for some $\displaystyle i\in\{1,2,\dots,n\}$ and assume without loss of generality that $\displaystyle h_{t}=[s_{t}\ \ 0]^{T}$. Then

Now, since $\displaystyle w\in P_{n}\cup D_{n}$ we have that $\displaystyle s_{t}\in[0,1)$ for any $\displaystyle t$, which follows immediately from the stack interpretation of the base $\displaystyle 2n+1$ representation of $\displaystyle s_{t}$. Thus $\displaystyle\text{ReLU}(-2n-1+(2n+1)s_{t})=0$ and so

as desired. Alternatively, suppose $\displaystyle w_{t+1}=)_{i}$ for some $\displaystyle i\in\{1,2,\dots,n\}$. Again, assume without loss of generality that $\displaystyle h_{t}=[s_{t}\ \ 0]^{T}$. Then

The fact that $\displaystyle w\in P_{n}\cup D_{n}$ clearly implies that $\displaystyle(2n+1)s_{t}-2i\geq 0$ and so we have that

A pictorial example of this RNN is depicted below for $\displaystyle n=2$:

\displaystyle h_{1,t}\ \<span class="katex-error" title="ParseError: KaTeX parse error: Unexpected character: &#x27;\&#x27; at position 25: …tyle\ h_{2,t}\ \̲" style="color:#cc0000">\displaystyle\ h_{2,t}\ \</span>\displaystyle\ x_{1,t}\ \<span class="katex-error" title="ParseError: KaTeX parse error: Unexpected character: &#x27;\&#x27; at position 25: …tyle\ x_{2,t}\ \̲" style="color:#cc0000">\displaystyle\ x_{2,t}\ \</span>\displaystyle\ x_{3,t}\ \<span class="katex-error" title="ParseError: KaTeX parse error: Unexpected character: &#x27;\&#x27; at position 25: …tyle\ x_{4,t}\ \̲" style="color:#cc0000">\displaystyle\ x_{4,t}\ \</span>\displaystyle h_{1,t-1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="true"><msub><mi>h</mi><mrow><mn>2</mn><mo separator="true">,</mo><mi>t</mi><mo>−</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation encoding="application/x-tex">\displaystyle h_{2,t-1}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9805em;vertical-align:-0.2861em;"></span><span class="mord"><span class="mord mathnormal">h</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span><span class="mpunct mtight">,</span><span class="mord mathnormal mtight">t</span><span class="mbin mtight">−</span><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.2861em;"><span></span></span></span></span></span></span></span></span></span></span>\displaystyle 0.4<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="true"><mn>0.8</mn></mstyle></mrow><annotation encoding="application/x-tex">\displaystyle 0.8</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">0.8</span></span></span></span></span>\displaystyle-5<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="true"><mo>−</mo><mn>5</mn></mstyle></mrow><annotation encoding="application/x-tex">\displaystyle-5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7278em;vertical-align:-0.0833em;"></span><span class="mord">−</span><span class="mord">5</span></span></span></span></span>\displaystyle 0.2<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="true"><mn>0.2</mn></mstyle></mrow><annotation encoding="application/x-tex">\displaystyle 0.2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">0.2</span></span></span></span></span>\displaystyle-5<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="true"><mo>−</mo><mn>5</mn></mstyle></mrow><annotation encoding="application/x-tex">\displaystyle-5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7278em;vertical-align:-0.0833em;"></span><span class="mord">−</span><span class="mord">5</span></span></span></span></span>\displaystyle-2<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="true"><mo>−</mo><mn>4</mn></mstyle></mrow><annotation encoding="application/x-tex">\displaystyle-4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7278em;vertical-align:-0.0833em;"></span><span class="mord">−</span><span class="mord">4</span></span></span></span></span>\displaystyle 5$\displaystyle 5$ Thus we have found an efficient way to store $\displaystyle s_{t}$. Now it’s clear that for any $\displaystyle w=w_{1}w_{2}\dots w_{m}\in P_{n}$ we have $\displaystyle s_{m}>0$ and for any $\displaystyle w=w_{1}w_{2}\dots w_{m}\in D_{n}$ we have $\displaystyle s_{m}=0$, so it is tempting to try and add a simple output layer to this RNN and claim that its $\displaystyle\{0\}$-language is $\displaystyle D_{n}$. However, this is most likely impossible to accomplish.

Indeed, consider the word $\displaystyle w=)_{1}(_{1}$. We have that $\displaystyle s_{2}=0$ for this word, but $\displaystyle w\not\in D_{n}$. Furthermore, consider the word $\displaystyle w=(_{2})_{1}(_{1})_{2}$. We have that $\displaystyle s_{t}\geq 0$ for all $\displaystyle t$ and $\displaystyle s_{4}=0$ for this word, yet $\displaystyle w\not\in D_{n}$. Hence we must be able to flag when an inappropriate closing parenthesis appears in an input and retain that information while reading the rest of the input. To that end, consider the following simple RNN, an example of which can be found in Appendix A.1:

where again the inputs $\displaystyle x$ are $\displaystyle 2n\times 1$ one-hots of the symbols in $\displaystyle\Sigma$ (the alphabet of $\displaystyle D_{n}$) in the order $\displaystyle(_{1},(_{2},\dots,(_{n},)_{1},)_{2},\dots,)_{n}$ and the hidden states have dimension $\displaystyle 6\times 1$ where

Because the last four elements of the first two rows of $\displaystyle W_{h}$ are all equal to $\displaystyle 0$ and otherwise the first two rows of $\displaystyle W_{x}$ and $\displaystyle W_{h}$ are the same as before, it is clear that Lemma 1.4 still applies in some form for the new simple RNN. Indeed, denoting

Corollary 1.5. With respect to a word $\displaystyle w\in P_{n}\cup D_{n}$, we have $\displaystyle[h_{1,t}\ \ h_{2,t}]=[s_{t}\ \ 0]$ or $\displaystyle[h_{1,t}\ \ h_{2,t}]=[0\ \ s_{t}]$ for all $\displaystyle t$.

Lemma 1.6. For any word $\displaystyle w\in P_{n}$, there is a unique $\displaystyle x\in\{)_{1},)_{2},\dots,)_{n}\}$ such that $\displaystyle wx\in P_{n}\cup D_{n}$.

Proof. This immediately follows from the definition of a balanced string. Indeed, if $\displaystyle s$ is the state associated with $\displaystyle w$ then this unique $\displaystyle x$ is given by

Lemma 1.7. Given an input word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in P_{n}\cup D_{n}$, we have that $\displaystyle h_{3,m}=h_{5,m}=0$.

Proof. We first restrict our attention to $\displaystyle h_{3,m}$. Note that

for any $\displaystyle i$, which follows from the definition of $\displaystyle W_{h}$ and $\displaystyle W_{x}$. Then using Corollary 1.5 we find

Now using the inequality in the proof of Lemma 1.6 we immediately obtain $\displaystyle h_{3,m}=0$ as desired.

Considering now $\displaystyle h_{5,m}$ we notice

and doing an analysis similar to that for $\displaystyle h_{3,m}$, we obtain $\displaystyle h_{5,m}=0$ as desired.∎

Applying Lemma 1.6 allows us to make the following statement:

Lemma 1.8. Given a word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in P_{n}$, consider the unique $\displaystyle j\in\{1,2,\dots,n\}$ such that $\displaystyle w)_{j}\in P_{n}\cap D_{n}$. Then with respect to a word $\displaystyle w)_{i}$ with $\displaystyle i>j$, we have $\displaystyle h_{3,m+1}>0$. Similarly, with respect to a word $\displaystyle w)_{i}$ with $\displaystyle i<j$, we have $\displaystyle h_{5,m+1}>0$.

Proof. First suppose $\displaystyle i>j$. As in the proof of Lemma 1.7, we use

where we again use Corollary 1.5 and the fact that $\displaystyle h_{3,m}=0$ from Lemma 1.7. But from the proof of Lemma 1.6, since $\displaystyle w)_{j}\in P_{n}\cup D_{n}$ we know that

and since $\displaystyle i>j$ we have that $\displaystyle 2i>2j+1$ since $\displaystyle i$ and $\displaystyle j$ are integral. Thus $\displaystyle h_{3,m+1}>0$ as desired.

Now assume $\displaystyle i<j$. As in the previous case we obtain

again using Corollary 1.5 and Lemma 1.7. And again using the inequality from the proof of Lemma 1.6 and the fact that $\displaystyle i<j$ we obtain $\displaystyle h_{5,m+1}>0$, completing the proof.∎

Thus we have constructed the desired “flags.” Indeed, hidden nodes $\displaystyle h_{3}$ and $\displaystyle h_{5}$ remain equal to $\displaystyle 0$ while the currently read input lies in $\displaystyle P_{n}\cup D_{n}$, but one of these nodes becomes positive the moment the currently read input does not lie in this set.

However, there are still difficulties. It is possible for $\displaystyle h_{3}$ or $\displaystyle h_{5}$ to become positive and later return to $\displaystyle 0$. Indeed, running the simple RNN on the word $\displaystyle w=(_{2})_{1}(_{1})_{2}(_{2})_{2}$, we compute $\displaystyle h_{1,6}=h_{2,6}=h_{3,6}=h_{5,6}=0$. However, clearly $\displaystyle w\not\in P_{n}\cup D_{n}$. Therefore we need to add architecture that retains the information as to whether the hidden nodes $\displaystyle h_{3}$ or $\displaystyle h_{5}$ ever become positive, and below we show that hidden nodes $\displaystyle h_{4}$ and $\displaystyle h_{6}$ respectively are sufficient.

Lemma 1.9. For any input $\displaystyle w\in\Sigma^{*}$ we have

Proof. From the definition of $\displaystyle W_{x}$ and $\displaystyle W_{h}$ we have

and since $\displaystyle h_{3,t},h_{5,t}\geq 0$ for all $\displaystyle t$ (because of the ReLU) we immediately have the result by induction or direct expansion.∎

We are now ready to combine these lemmas and accomplish our original goal:

Theorem 1.10. The $\displaystyle\{0\}$-language of the simple RNN described earlier in the section is $\displaystyle D_{n}$.

Proof. Consider any input $\displaystyle w=w_{1}w_{2}\dots w_{m}\in\Sigma^{*}$ into the RNN. For the remainder of the proof, remember that $\displaystyle h_{i,t}\geq 0$ for all $\displaystyle i,t$ because of the ReLU activation. We consider three cases:

Case 1: $\displaystyle w\in P_{n}\cup D_{n}$.

In this case by Corollary 1.5 we have $\displaystyle h_{1,m}+h_{2,m}=s_{m}$. Furthermore, by Lemma 1.7 we have $\displaystyle h_{3,m}=h_{5,m}=0$. By combining Lemmas 1.7 and 1.9, we have $\displaystyle h_{4,m}=h_{6,m}=0$. Thus $\displaystyle o_{m}=s_{m}$ which, given that $\displaystyle w\in P_{n}\cup D_{n}$, equals $\displaystyle 0$ precisely when $\displaystyle w\in D_{n}$, by the inequality from the proof of Lemma 1.6.

Case 2: $\displaystyle w\not\in P_{n}\cup D_{n}$ and $\displaystyle w_{1}w_{2}\dots w_{m-1}\in P_{n}\cup D_{n}$.

In this case we clearly must have $\displaystyle w_{m}=)_{i}$ for some $\displaystyle i\in\{1,2,\dots,n\}$ and thus by Lemma 1.8 we have that either $\displaystyle h_{3,m}>0$ or $\displaystyle h_{5,m}>0$, so $\displaystyle o_{m}>0$.

Case 3: $\displaystyle w_{1}w_{2}\dots w_{k}\not\in P_{n}\cup D_{n}$ for some $\displaystyle k\in\{1,2,\dots,m-1\}$.

Suppose $\displaystyle j$ is the minimal index such that $\displaystyle w_{1}w_{2}\dots w_{j}\not\in P_{n}\cup D_{n}$. Then by minimality $\displaystyle w_{1}w_{2}\dots w_{j-1}\in P_{n}\cup D_{n}$ so again by Lemma 1.8 we have that either $\displaystyle h_{3,j}>0$ or $\displaystyle h_{5,j}>0$. But since $\displaystyle j\leq k\leq m-1$ by Lemma 1.9 this means that either $\displaystyle h_{4,m}>0$ or $\displaystyle h_{6,m}>0$, so $\displaystyle o_{m}>0$.

Thus $\displaystyle o_{m}=0$ if and only if $\displaystyle w\in D_{n}$, completing the proof of the theorem.∎

Now recall in the proof of Theorem 1.1 we showed that any regular language $\displaystyle R$ was the $\displaystyle\{0\}$-language of some simple RNN, and moreover that for any input not in $\displaystyle R$ the output of that RNN is positive. This allows us to provide a simple proof of the main theorem of this section:

Theorem 1.11. For any context-free language $\displaystyle L$, suppose we relabel and write $\displaystyle L=D_{n}\cap R$ for some regular language $\displaystyle R$, whose corresponding minimum-size DFA has $\displaystyle r$ states. Then there exists a simple RNN with a hidden layer of size $\displaystyle 6+2nr$ whose $\displaystyle\{0\}$-language is $\displaystyle L$.

Proof. Consider the simple RNN with $\displaystyle R$ as its $\displaystyle\{0\}$-language described in the proof of Theorem 1.1 and the simple RNN with $\displaystyle D_{n}$ as its $\displaystyle\{0\}$-language constructed to prove Theorem 1.10. Merge the $\displaystyle|\Sigma|=2n$ nodes in the input layer corresponding to the input and merge the single output nodes of both RNNs. Stack the two hidden layers, and add no new edges. There were $\displaystyle|\Sigma|r=2nr$ hidden nodes in the first RNN and $\displaystyle 6$ in the second, so altogether the new RNN has $\displaystyle 6+2nr$ hidden nodes.

The output of the new RNN is equal to the summed output of the two original RNNs, and from the proofs of Theorems 1.1 and 1.10 these outputs are always nonnegative. Thus the output of the new RNN is $\displaystyle 0$ if and only if the outputs of both old RNNs were $\displaystyle 0$, immediately proving the theorem.∎

Discussion 1.12. This result shows that simple RNNs with arbitrary precision are at least as computationally powerful as PDAs.

Gated RNNs

In practice, architectures more complicated than the simple RNNs studied above - notably gated RNNs, including the Gated Recurrent Unit (GRU) and Long Short-Term Memory (LSTM) - perform better on many natural language tasks. Thus we are motivated to explore their computational capabilities. Here we focus on the GRU, described by the equations below:

Theorem 2.1. For every language $\displaystyle L\subseteq\Sigma^{*}$, $\displaystyle L$ is regular if and only if $\displaystyle L$ is the $\displaystyle S$-language of some finite precision GRU.

Proof. The “if” direction can be shown in the same manner as in Theorem 1.1. So, here we focus on the “only if” direction. Suppose we have a DFA $\displaystyle D=(Q,\Sigma,\delta,q_{0},F)$ with corresponding language $\displaystyle L$. We will construct a GRU whose inputs are one-hotted symbols from $\displaystyle\Sigma$ with $\displaystyle|Q||\Sigma|$ hidden nodes whose $\displaystyle\{0\}$-language is $\displaystyle L$.

For convenience, for all $\displaystyle x\in\Sigma$ let $\displaystyle e_{x}$ denote the corresponding one-hot vector for $\displaystyle x$. Furthermore, let $\displaystyle N=|\Sigma||Q|$.

First set $\displaystyle W_{z}=W_{h}=0$ and $\displaystyle U_{z}=U_{r}=0$ and $\displaystyle b_{z}=b_{r}=b_{h}=0$, so the simplified GRU is given by:

Now, define an arbitrary bijective map $\displaystyle g:\{1,2,\dots,|Q|\}\rightarrow Q$. Then construct $\displaystyle|Q|$ vectors

where for all $\displaystyle i\in\{1,2,\dots,|Q|\}$ and $\displaystyle k\in\{1,2,\dots,N\}$ we set

Our goal will be to find $\displaystyle W_{r}$ and $\displaystyle U_{h}$ such that if $\displaystyle h_{t-1}=s_{i}$ for some $\displaystyle i$, and $\displaystyle x_{t}$ is the one-hot encoding of some $\displaystyle x\in\Sigma$, then $\displaystyle h_{t}=s_{j}$ where if $\displaystyle g(i)=q$ for some $\displaystyle q\in Q$ then $\displaystyle g(j)=\delta(q,x)$. If this is possible, then we could set $\displaystyle h_{0}=s_{g^{-1}(q_{0})}$ and be able to track the current state of the DFA effectively.

The strategy for accomplishing this is essentially to pick a simple $\displaystyle W_{r}$, and then solve a system of equations to produce the desired $\displaystyle U_{h}$.

For convenience, define the natural map $\displaystyle h:\{1,2,\dots,|\Sigma|\}\rightarrow\Sigma$ where $\displaystyle h(i)=x$ if and only if the $\displaystyle i$th element of $\displaystyle e_{x}$ is equal to $\displaystyle 1$.

for all $\displaystyle k\in\{1,2,\dots,N\}$ and $\displaystyle j\in\{1,2,\dots,|\Sigma|\}$. Now consider the $\displaystyle N$ equations

where $\displaystyle g(j)=\delta(g(i),x)$, for every $\displaystyle i\in\{1,2,\dots,|Q|\}$ and $\displaystyle x\in\Sigma$. Let

for all $\displaystyle i\in\{1,2,\dots,|Q|\}$ and $\displaystyle j\in\{1,2,\dots,|\Sigma|\}$ and $\displaystyle k\in\{1,2,\dots,N\}$. Letting

The $\displaystyle N$ earlier equations can now be combined as a single matrix equation given by

where $\displaystyle C_{j}$ is a $\displaystyle|\Sigma|\times|\Sigma|$ matrix for each $\displaystyle j\in\{1,2,\dots,|\Sigma|\}$. In particular, we have that

Using basic row operations it is easy to see that $\displaystyle\text{det}(C_{j})=0.1^{|\Sigma|}(|\Sigma|+1)$ for all $\displaystyle j$, so

and thus $\displaystyle C^{-1}$ is well-defined. Furthermore, since $\displaystyle s_{i,k}\in\{0,0.25\}$ for each $\displaystyle i,k$, the inputs into all inverse hyperbolic tangents in $\displaystyle B$ lie in $\displaystyle(-1,1)$ and so $\displaystyle B$ is well-defined as well. Thus our expression for $\displaystyle U_{h}$ is well-defined.

Now, given our choices for the $\displaystyle s_{i},W_{r}$, and $\displaystyle U_{h}$, after reading any input $\displaystyle w=w_{1}w_{2}\dots w_{m}$, if $\displaystyle q$ is the current state of the DFA associated with $\displaystyle L$, then $\displaystyle h_{m}=s_{g^{-1}(q)}$. Now because the $\displaystyle s_{i}$ are clearly linearly independent, we can find a $\displaystyle W_{o}$ such that

for all $\displaystyle i\in\{1,2,\dots,Q\}$ and it’s clear that the $\displaystyle\{0\}$-language of the resulting GRU will be $\displaystyle L$, as desired.∎

Discussion 2.2. In the above proof, we are implicitly assuming that the activation functions of the GRU are not actually the sigmoid and hyperbolic tangent functions but rather finite precision analogues for which the equations we solved are all consistent. However, for the remainder of this section we can drop this assumption.

To account for both of these issues, instead of keeping track of the state $\displaystyle s_{t}$ as we read a word, we will instead keep track of the state $\displaystyle s^{\prime}_{t}$ of a word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in\Sigma^{*}$ defined by

for all $\displaystyle i\in\{1,2,\dots,n\}$, for some predetermined sufficiently large $\displaystyle k$. We have the following relationship between $\displaystyle s^{\prime}_{t}$ and $\displaystyle s_{t}$:

Lemma 2.3. For any word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in\Sigma^{*}$ we have $\displaystyle s_{t}=(2n+1)^{kt}s^{\prime}_{t}$ for all $\displaystyle t\in\{1,2,\dots,m\}$.

Proof. Multiplying the recurrence relationship for $\displaystyle s^{\prime}_{t}$ by $\displaystyle(2n+1)^{kt}$ we recover the recurrence relationship for $\displaystyle s_{t}$ in Section 1, implying the desired result.∎

Thus the state $\displaystyle s^{\prime}$ allows us to keep track of the old state $\displaystyle s$ without having to multiply by any constant greater than $\displaystyle 1$. Furthermore, for large $\displaystyle k$, $\displaystyle s^{\prime}$ will be extremely small, allowing us to abuse the fact that $\displaystyle\text{tanh}(x)\sim x$ for small values of $\displaystyle x$. In terms of the stack of digits interpretation of $\displaystyle s$, $\displaystyle s^{\prime}$ is the same except between every pop or push we add $\displaystyle k$ zeros to the top of the stack.

Again we wish to construct a GRU from whose hidden state we can recover $\displaystyle s^{\prime}_{t}$. Ignoring the output layer for now, consider the GRU defined by

where $\displaystyle h_{1,0}\geq 0$ will be determined later, the inputs $\displaystyle x$ are again $\displaystyle 2n\times 1$ one-hots of the symbols in $\displaystyle\Sigma$ in the order $\displaystyle(_{1},(_{2},\dots,(_{n},)_{1},)_{2},\dots,)_{n}$ and the hidden states have dimension $\displaystyle 3\times 1$ where

where $\displaystyle\sigma^{-1}(x)=-\ln(x^{-1}-1)$ is the inverse of the sigmoid function. For sufficiently large $\displaystyle k$, clearly our use of $\displaystyle\sigma^{-1}$ is well-defined. We will show the following invariant:

Lemma 2.4. Given an input word $\displaystyle w\in P_{n}\cup D_{n}$, if $\displaystyle h_{1,0}=0$ then we have $\displaystyle h_{t}\approx[s^{\prime}_{t}\ \ (2n+1)^{-kt}\ \ (2n+1)^{-kt}]^{T}$ for all $\displaystyle t$.

Proof. As in Section 1, let $\displaystyle z_{t}=[z_{1,t}\ \ z_{2,t}\ \ z_{3,t}]^{T}$ and $\displaystyle r_{t}=[r_{1,t}\ \ r_{2,t}\ \ r_{3,t}]^{T}$ and $\displaystyle h_{t}=[h_{1,t}\ \ h_{2,t}\ \ h_{3,t}]^{T}$. First, we will show $\displaystyle h_{2,t}=(2n+1)^{-kt}$ for all $\displaystyle t\in\{1,2,\dots,m\}$ by induction on $\displaystyle t$. The base case is trivial, so note

so by induction $\displaystyle h_{2,t+1}=(2n+1)^{-k(t+1)}$ as desired. Similarly, we obtain $\displaystyle h_{3,t}=(2n+1)^{-kt}$ for all $\displaystyle t$.

Now we restrict our attention to $\displaystyle h_{1,t}$. Note that

and so using the definition of $\displaystyle U_{h}$ we obtain

If we removed the tanh from the above expression, it would simplify to

which is exactly the recurrence relation satisfied by $\displaystyle s^{\prime}_{t}$. Since the expressions inside the hyperbolic tangents are extremely small (on the order of $\displaystyle 2^{-kt}$), this implies that $\displaystyle h_{1,t}$ is a good approximation for $\displaystyle s^{\prime}_{t}$ as desired. This will be formalized in the next lemma.∎

Lemma 2.5. For any input word $\displaystyle w\in P_{n}\cup D_{n}$, if $\displaystyle h_{1,0}=0$ then we have $\displaystyle|(2n+1)^{kt}h_{1,t}-s_{t}|<2(2n+1)^{-2k+7}$ for all $\displaystyle t$.

Proof. Let $\displaystyle\epsilon_{t}=(2n+1)^{kt}h_{1,t}-s_{t}$ for all $\displaystyle t$. Then we easily find that

Now define $\displaystyle\epsilon^{\prime}_{t}$ by the recurrence

with $\displaystyle\epsilon^{\prime}_{0}=\epsilon_{0}=0$. Because $\displaystyle\text{tanh}(x)<x$ for all $\displaystyle x>0$ it is easy to see that $\displaystyle\epsilon^{\prime}_{t}\geq|\epsilon_{t}|$ for all $\displaystyle t$.

Now by a Taylor expansion, $\displaystyle\text{tanh}(x)=x-\frac{x^{3}}{3}+\frac{2x^{5}}{15}+O(x^{7})$, so we have that

for $\displaystyle x>0$. Thus we obtain the bound

Since $\displaystyle 2i<2n+1$ and $\displaystyle(2n+1)^{k+1}-1\geq(2n+1)^{k}$ we also have

Since again $\displaystyle 2i<2n+1$ and $\displaystyle(2n+1)^{k-1}-1\geq(2n+1)^{k-2}$ we also have

Thus if we define $\displaystyle a_{t}$ by the recurrence

with $\displaystyle a_{0}=\epsilon^{\prime}_{0}=0$, then $\displaystyle a_{t}\geq\epsilon^{\prime}_{t}$ for all $\displaystyle t$.

Now we wish to upper bound $\displaystyle a_{t}$. Since $\displaystyle i$ is not present in the recurrence for $\displaystyle a_{t}$, assume without loss of generality that all parenthesis in an input word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in P_{n}\cup D_{n}$ lie in $\displaystyle\{(_{1},)_{1}\}$. Suppose that $\displaystyle)_{1}(_{1}$ was a substring of $\displaystyle w$, so that $\displaystyle w=x)_{1}(_{1}y$. Then we would have

However, for the word $\displaystyle w^{\prime}=x(_{1})_{1}y$ (which would clearly still lie in $\displaystyle P_{n}\cup D_{n}$) we would have

which is larger. Thus to upper bound $\displaystyle a_{t}$ it suffices to consider only words that do not contain the substring $\displaystyle)_{1}(_{1}$, which are words in the form

with $\displaystyle r$ open parentheses followed by $\displaystyle s\leq r$ closing parentheses. Furthermore, adding extra closing parenthesis where suitable clearly increases the final $\displaystyle a_{t}$ so we can assume $\displaystyle s=r$. We can then exactly calculate $\displaystyle a_{2r}$ as

Considering each sum separately we have for sufficiently large $\displaystyle k$ that

And therefore $\displaystyle 2(2n+1)^{-2k+7}$ is an upper bound on $\displaystyle a_{t}$. Thus

Corollary 2.6. For any input word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in P_{n}\cup D_{n}$, if $\displaystyle w_{1}w_{2}\dots w_{t}$ contains $\displaystyle a_{t}$ open parentheses and $\displaystyle b_{t}\leq a_{t}$ closing parentheses then

with $\displaystyle|\epsilon|<2(2n+1)^{-2k+7}$ for all $\displaystyle t$.

Proof. This follows directly from the computations in the proof of Lemma 2.5 and the recurrence for $\displaystyle h_{1,t}$.∎

Now, set $\displaystyle h_{1,0}=3(2n+1)^{-2k+7}$. We then have the following useful analogues of Lemmas 1.7 and 1.8:

Corollary 2.7. For any input word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in P_{n}\cup D_{n}$ we have $\displaystyle h_{1,m}>0$.

Proof. This follows immediately from Corollary 2.6 and the fact that $\displaystyle h_{1,0}>2(2n+1)^{-2k+7}$. ∎

Lemma 2.8. Given a word $\displaystyle w_{1}w_{2}\dots w_{m}\in P_{n}$, consider the unique $\displaystyle j\in\{1,2,\dots,n\}$ such that $\displaystyle w)_{j}\in P_{n}\cup D_{n}$. Then for an input word $\displaystyle w)_{i}$ with $\displaystyle i>j$, we have $\displaystyle h_{1,m+1}<0$.

so multiplying both sides by $\displaystyle(2n+1)^{k(m+1)}$ and using the inequality from the proof of Lemma 2.5 we have

where we used the inequality from the proof of Lemma 1.6 and the fact that $\displaystyle h_{1,0}=3(2n+1)^{-2k+7}$. Therefore

Since $\displaystyle i>j$ we have that $\displaystyle 2j+1-2i\leq-1$ and so for sufficiently large $\displaystyle k$ we then have

With these results in hand, consider the larger GRU, an example of which can be found in Appendix A.2, defined by

where the inputs $\displaystyle x$ are again $\displaystyle 2n\times 1$ one-hots of the symbols in $\displaystyle\Sigma$ in the order $\displaystyle(_{1},(_{2},\dots,(_{n},)_{1},)_{2},\dots,)_{n}$ and the hidden states have dimension $\displaystyle 8\times 1$ where

As before, with respect to a word $\displaystyle w\in\Sigma^{*}$ define $\displaystyle s_{t}$ by

for all $\displaystyle i\in\{1,2,\dots,n\}$ and all $\displaystyle t$. Similarly define $\displaystyle\overline{s}_{t}$ by

For our new GRU, let $\displaystyle h_{t}=[h_{1,t}\ \ h_{2,t}\ \ h_{3,t}\ \ h_{4,t}\ \ h_{5,t}\ \ h_{6,t}\ \ h_{7,t}\ \ h_{8,t}]^{T}$. We then have the following results:

Lemma 2.9. For any input word $\displaystyle w\in\Sigma^{*}$ we have $\displaystyle h_{2,t}=h_{3,t}=h_{6,t}=h_{7,t}=(2n+1)^{-kt}$.

Proof. This follows immediately from the proof of Lemma 2.4.∎

Lemma 2.10. For any input word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in P_{n}\cup D_{n}$, if $\displaystyle w_{1}w_{2}\dots w_{t}$ contains $\displaystyle a_{t}$ open parentheses and $\displaystyle b_{t}\leq a_{t}$ closing parenthesis then

with $\displaystyle|\epsilon_{1}|,|\epsilon_{2}|<2(2n+1)^{-2k+7}$ for all $\displaystyle t$.

Proof. This follows immediately from the proof of Corollary 2.6 and the new $\displaystyle W_{r}$, since $\displaystyle h_{5,t}$ behaves exactly like $\displaystyle h_{1,t}$ if each input $\displaystyle(_{i}$ or $\displaystyle)_{i}$ were $\displaystyle(_{n-i}$ or $\displaystyle)_{n-i}$ respectively, instead. ∎

Lemma 2.11. For any input word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in\Sigma^{*}$ we have $\displaystyle h_{4,m},h_{8,m}\in\{0,1\}$ and $\displaystyle h_{4,m}=h_{8,m}=1$ if and only if $\displaystyle w_{1}w_{2}\dots w_{m-1}\in P_{n}\cup D_{n}$.

Proof. From our chosen $\displaystyle U_{z}$ we see that

Since $\displaystyle h_{4,0}=h_{8,0}=1$ and since the fourth and eighth rows of $\displaystyle U_{h}$ are identically $\displaystyle 0$, the equation

which immediately implies that $\displaystyle h_{4,m},h_{8,m}\in\{0,1\}$. Now, suppose $\displaystyle w_{1}w_{2}\dots w_{m-1}\in P_{n}\cup D_{n}$. Then from Corollary 2.7 and its analogue for $\displaystyle h_{5,t}$ we see that $\displaystyle z_{4,t}=z_{8,t}=1$ for all $\displaystyle t\in\{1,2,\dots,m\}$, so $\displaystyle h_{4,m}=h_{8,m}=1$ as desired.

Otherwise, there exists some minimal $\displaystyle k\in\{0,1,\dots,m-2\}$ such that $\displaystyle w_{1}w_{2}\dots w_{k+1}\not\in P_{n}\cup D_{n}$. Then $\displaystyle w_{k+1}=)_{i}$ for some $\displaystyle i\in\{1,2,\dots,n\}$. Consider the unique $\displaystyle j\neq i$ such that $\displaystyle w_{1}w_{2}\dots w_{k})_{j}\in P_{n}\cup D_{n}$. If $\displaystyle i>j$ then from the proof of Lemma 2.8 we have that $\displaystyle h_{1,k+1}<0$ and so $\displaystyle z_{4,k+2}=0$. Since $\displaystyle k+2\leq m$ this means that $\displaystyle h_{4,m}=0$. If $\displaystyle i<j$ then from the analogue of the proof of Lemma 2.8 for $\displaystyle h_{5,t}$, we obtain $\displaystyle h_{8,m}=0$. This completes the proof. ∎

We are now ready to combine these lemmas to prove an important result, the analogue of Theorem 1.10 for GRUs:

Theorem 2.12. The $\displaystyle(0,(2n+1)^{-1})$-language of the GRU described earlier in the section is $\displaystyle D_{n}$.

Proof. Consider any input word $\displaystyle w=w_{1}w_{2}\dots w_{m}\in\Sigma^{*}$ into the GRU. We consider four cases:

In this case, we clearly have $\displaystyle s_{m}=0$ and $\displaystyle h_{1,m}>0$ from the proof of Corollary 2.7, so by Lemmas 2.9 and 2.10 we have that

with $\displaystyle|\epsilon|<2(2n+1)^{-2k+7}$. Furthermore from Lemma 2.11 we have that $\displaystyle h_{4,m}=h_{8,m}=1$ so since $\displaystyle h_{1,0}=3(2n+1)^{-2k+7}$ we must have

for sufficiently large $\displaystyle k$, as desired.

As in Case 1 we have that $\displaystyle h_{1,m}>0$ and so by Lemmas 2.9 and 2.10 we have that

with $\displaystyle|\epsilon|<2(2n+1)^{-2k+7}$. Furthermore from Lemma 2.11 we have that $\displaystyle h_{4,m}=h_{8,m}=1$ so here

for sufficiently large $\displaystyle k$, since the minimum value of $\displaystyle s_{m}$ is clearly $\displaystyle 2(2n+1)^{-1}$.

Case 3: $\displaystyle w\not\in P_{n}\cup D_{n}$ and $\displaystyle w_{1}w_{2}\dots w_{m-1}\in P_{n}\cup D_{n}$.

Suppose $\displaystyle w_{1}w_{2}\dots w_{m-1})_{j}\in P_{n}\cup D_{n}$ for some unique $\displaystyle j\in\{1,2,\dots,n\}$. If $\displaystyle w_{m}=)_{i}$ for some $\displaystyle i>j$ then from Lemmas 2.9 and 2.10 and the proof of Lemma 2.8 we obtain

for sufficiently large $\displaystyle k$. If instead $\displaystyle i<j$ then the same technique with the inequality $\displaystyle\text{tanh}(x)<x$ can be used to show

if $\displaystyle k$ is sufficiently large. As before using Lemma 2.11 we have that $\displaystyle h_{4,m}=h_{8,m}=1$ and combining these bounds we find that

Case 4: $\displaystyle w_{1}w_{2}\dots w_{k}\not\in P_{n}\cup D_{n}$ for some $\displaystyle k\in\{1,2,\dots,m-1\}$