How do they prove that RNNs with arbitrary precision are as powerful as a pushdown automata?
They prove that for any context-free language L
there exists an RNN whose {0}-language is L.
Recent neural network architectures such as the basic recurrent neural network (RNN) and Gated Recurrent Unit (GRU) have gained prominence as end-to-end learning architectures for natural language processing tasks. But what is the computational power of such systems? We prove that finite precision RNNs with one hidden layer and ReLU activation and finite precision GRUs are exactly as computationally powerful as deterministic finite automata. Allowing arbitrary precision, we prove that RNNs with one hidden layer and ReLU activation are at least as computationally powerful as pushdown automata. If we also allow infinite precision, infinite edge weights, and nonlinear output activation functions, we prove that GRUs are at least as computationally powerful as pushdown automata. All results are shown constructively.
Recent work [1] 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 [2], language modeling [3], sentiment analysis [4], natural language generation [5], 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 INLINEFORM0 . 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 [8], [9] focused on the ability of RNNs to recognize simple context-free languages such as INLINEFORM0 and INLINEFORM1 , or context-sensitive languages such as INLINEFORM2 . Related works [10], [11], [12] 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 [8]. 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 [6] shows that a simple recurrent architecture with 1058 hidden nodes and a saturated-linear activation INLINEFORM0 is a universal Turing Machine, with: INLINEFORM1  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 [7] 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.