On the Practical Computational Power of Finite Precision RNNs for Language Recognition

By Gail Weiss, Yoav Goldberg, Eran Yahav. 2018

300 citations recorded by the source corpus.

While Recurrent Neural Networks (RNNs) are famously known to be Turing complete, this relies on infinite precision in the states and unbounded computation time. We consider the case of RNNs with finite precision whose computation time is linear in the input length. Under these limitations, we show that different RNN variants have different computational power. In particular, we show that the LSTM and the Elman-RNN with ReLU activation are strictly stronger than the RNN with a squashing activation and the GRU. This is achieved because LSTMs and ReLU-RNNs can easily implement counting behavior. We show empirically that the LSTM does indeed learn to effectively use the counting mechanism.

Subfields: Artificial Intelligence, Model Architectures, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Model Architectures

In Statistical Learning Theory

Citations in the corpus

Analysis Methods in Neural Language Processing: A Survey (2018, background): “This trend continues today, with research into modern architectures and what formal languages they can learn (Weiss et al., 2018; Bernardy, 2018; Suzgun et al., 2019), or the formal properties they possess (Chen et al., 2018b).”
Do NLP Models Know Numbers? Probing Numeracy in Embeddings (2019, methodology): “Although the natural emergence of comparison algorithms is surprising, previous results show neural models are capable of learning to count and sort synthetic lists of scalar values when given explicit supervision (Weiss et al., 2018; Vinyals et al., 2016).”
On the Turing Completeness of Modern Neural Network Architectures (2019, background): “Most of the early neural architectures proposed for learning algorithms correspond to extensions of RNNs – e.g., Neural Turing Machines (Graves et al., 2014) –, and hence they are Turing complete in the sense of Siegelmann & Sontag.”
Theoretical Limitations of Self-Attention in Neural Sequence Models (2019, background): “Yang et al. (2019) experimentally investigated the power of self-attention to extract word order information, ﬁnding differences between recurrent and self-attention models; however, these were modulated by the training objective.”
Learning to Recombine and Resample Data for Compositional Generalization (2020, background): “In contrast, recurrent neural networks can accurately model a n b n (Weiss et al., 2018; Gers & Schmidhuber, 2001).”
On Evaluating the Generalization of LSTM Models in Formal Languages (2018, background): “Most of the previous studies trained networks on sequences of lengths n ∈ [1, N ], where typical N values were between 10 and 50 (Bodén and Wiles, 2000; Gers and Schmidhuber, 2001), and more recently 100 (Weiss et al., 2018).”
How Attentive are Graph Attention Networks? (2021, methodology): “We thank Gail Weiss for the helpful discussions, thorough feedback, and inspirational paper (Weiss et al., 2018).”
Compositional Generalization for Primitive Substitutions (2019, background): “There has been exploration on compositionality in neural networks for systematic behaviour (Wong and Wang, 2007; Brakel and Frank, 2009), counting ability (Rodriguez and Wiles, 1998; Weiss et al., 2018) and sensitivity to hierarchical structure (Linzen et al., 2016).”
Neural Arithmetic Logic Units (2018, background): “The question of whether and how recurrent networks generalize to sequences longer than they encountered in training has been of enduring interest, especially since well-formed sentences in human languages are apparently unbounded in length, but are learned from a limited sample [9, 19, 28].”
Location Attention for Extrapolation to Longer Sequences (2019, background): “In this paper, we will consider the transformer and transformerXL (relative SE) attention, 3This assumption can depend on the architecture and the inductive bias it provides (Weiss et al., 2018).”
Can Recurrent Neural Networks Learn Nested Recursion? (2018, methodology): “This counting behavior has been studied in depth for various RNNs architectures by Weiss et al. (2018).”
Interpreting and improving natural-language processing (in machines) with natural language-processing (in the brain) (2019, background): “Other approaches have attempted to offer a more theoretical assessment of how recurrent networks propagate information, or what word embeddings can represent (Peng et al. , 2018; Chen et al. , 2017; Weiss et al. , 2018).”
The EOS Decision and Length Extrapolation (2020, background): “success of the low-dimensional GRU may very well be related to its failure to implement counters as efficiently as LSTMs (Weiss et al., 2018)—if the model cannot count well, then it may not learn length attractors.”
Large Language Models (2023, background): “Under realistic assumptions the right complexity class is a finite state machine, which can recognize regular languages [26, 134].”
LSTMs Exploit Linguistic Attributes of Data (2018, background): “Also related is the work of Weiss et al. (2018), who demonstrate that LSTMs are able to count inﬁnitely, since their cell states are unbounded, while GRUs cannot count inﬁnitely since the activations are constrained to a ﬁnite range.”