Source-linked AI summary
On the Practical Computational Power of Finite Precision RNNs for Language Recognition
Gail Weiss, Yoav Goldberg, Eran Yahav
TL;DR
The paper studies how finite precision and input-bound computation affect the language-recognition power of different RNN architectures. It compares their ability to implement counting and reports theoretical distinctions alongside experiments showing that LSTMs learn counting behavior more effectively than GRUs.
Problem
Finite precision and linear-time computation constrain the computational power of RNNs, raising whether different architectures retain distinct language-recognition capabilities.
Method
The paper analyzes RNN variants through simplified k-counter-machine constructions and tests whether trained LSTMs and GRUs learn counting on formal languages.
Results
LSTMs can implement unbounded counting and are more powerful than IBFP-SRNNs and IBFP-GRUs, while experiments show LSTMs learn counting dimensions and GRUs do not.
Takeaways & Limitations
Counting behavior provides a supported basis for distinguishing architectures, with LSTMs recognizing the tested counting languages using the hypothesized control structure.
Takeaways & Limitations
The paper leaves the practicality of discovering and maintaining stable behavior across architectures for future work.
Abstract
from arXiv · showhide
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.
1 Introduction
Under finite-precision, input-bound computation, RNN architectures need not have equivalent computational power. The paper argues that LSTMs and ReLU-RNNs can count, unlike squashing RNNs and GRUs, and reports learned counting behavior in LSTMs.
- 1 Introduction: Finite-precision, input-bound RNNs are studied as a practical regime distinct from Turing-complete infinite-precision constructions.The restriction uses computation linear in input length and finite-precision states.
- 1 Introduction: LSTMs can perform unbounded counting, whereas GRUs and squashing-activation SRNNs remain finite-state under these restrictions.The paper characterizes LSTMs as similar to k-counter machines and GRUs as finite-state.
- 1 Introduction: ReLU-RNNs with an MLP classifier have computational power similar to k-counter machines.This places ReLU-RNNs above squashing-activation SRNNs in the paper’s comparison.
- 1 Introduction: LSTMs learned explicit counting dimensions when trained to recognize anbn and anbncn, unlike the GRUs.The experiments use 10-dimensional LSTM and GRU networks and inspect their activations.
- 1 Introduction: Unbounded counting may matter for processing linearized parse trees, where brackets and nesting levels must be counted.The paper notes that prior work in this setting used LSTMs rather than GRUs.
2 The RNN Models
The paper formalizes RNN recognizers as recurrent state updates followed by a classifier, then compares SRNN, ReLU, GRU, and LSTM variants through their update mechanisms and finite-state capabilities.
- 2 The RNN Models: An RNN processes embedded input symbols recurrently from an initial state, and a classifier maps the final state to acceptance or rejection.The classifier may be log-linear or a multilayer perceptron.
- 2 The RNN Models: A squashing-activation Elman-RNN applies an affine transformation followed by a tanh nonlinearity.The paper notes that tanh can be replaced by another squashing function without reducing the established computational power.
- 2 The RNN Models: The IRNN replaces tanh with a non-squashing ReLU activation.Its computational power with infinite precision had been studied previously.
- 2 The RNN Models: The GRU and LSTM can simulate SRNN computation by fixing their gates to suitable constant values.For the GRU, z_t = 0 and r_t = 1; for the LSTM, i_t = 1, o_t = 1, and f_t = 0.
- 2 The RNN Models: All of the considered RNN variants can recognize finite-state languages.The result provides a common baseline before comparing power beyond finite state.
3 Power of Counting
The paper uses real-time counter machines to characterize computational power beyond finite-state recognition. Its simplified SKCM model extends finite-state automata with input-dependent counter operations and zero tests.
- 3 Power of Counting: Real-time k-counter machines recognize anbn and anbncn, but cannot recognize the specified palindrome language.This produces a hierarchy that cuts across the traditional Chomsky hierarchy.
- 3 Power of Counting: An SKCM is a finite-state automaton extended with k counters that can be incremented, decremented, ignored, or compared to zero.Operations and transitions may depend on the input, and acceptance decisions can inspect counter zero-ness.
4 RNNs as SKCMs
In the input-bound finite-precision setting, LSTMs and ReLU RNNs can implement counter-like computation, whereas GRUs and squashing-activation SRNNs cannot implement unbounded counting.
- LSTM: LSTMs designate memory-cell dimensions as counters, supporting increment, decrement, reset, and zero comparison.The counter direction is selected from the input and state, while output exposure makes comparison to zero straightforward.
- SRNN: Finite-precision SRNNs with squashing activations cannot designate unbounded counting dimensions.Tanh-based counting is theoretically unbounded only with infinite precision and is practically unstable beyond a narrow range.
- IRNN: Finite-precision ReLU RNNs can perform input-conditioned unbounded counting by representing each counter with two dimensions.One dimension handles incrementing, the other decrementing, and their difference supports zero comparison.
- GRU: Finite-precision GRUs remain finite-state because tanh and gate interpolation restrict hidden values to -1 through 1.They may count to a training-bound m, but do not generalize reliably beyond it and require precise, unsaturated gate settings.
- Summary: Overall, LSTM and IRNN are at least as strong as SKCMs and strictly stronger than squashing SRNNs and GRUs.The comparison follows from their ability, or inability, to implement dedicated unbounded counting dimensions.
5 Experimental Results
Experiments test whether trained LSTMs and GRUs learn the theoretically predicted counting behavior on a^nb^n and a^nb^nc^n. LSTMs learn clearer counting-based solutions, generalize farther, and outperform GRUs on perturbed test sets, though their counters accumulate error.
- LSTM results: LSTM networks generalize to much higher n than seen during training, although not indefinitely.For a^nb^n, the LSTM generalizes well up to n = 256; for a^nb^nc^n, it recognizes well until n = 100.
- LSTM results: Trained LSTMs use per-dimension counting mechanisms, with two counting dimensions clearly identified for a^nb^nc^n.The activation patterns support the canonical two-counter solution, despite increasingly imprecise counting on longer sequences.
- GRU results: GRUs lack clear counting dimensions and often fail to generalize correctly even within the training domain.On a^nb^n, the GRU begins accepting incorrect count offsets and stops accepting the target language for n > 198.
- Setup: LSTMs are trained to recognize a^nb^n and a^nb^nc^n, with training samples reaching n = 100 and n = 50, respectively.The experiments use 10-dimensional, one-layer LSTM and GRU networks.
- Comparison: The LSTM achieves 100% and 98.6% accuracy on a^nb^n and a^nb^nc^n, versus 87.0% and 86.9% for the GRU.These results come from random test sets with independently perturbed counts.
- Conclusion: The experiments support the theoretical distinction: LSTMs learn practical counting behavior more robustly than GRUs.The paper also notes similar empirical observations in prior work.
6 Conclusions
The paper concludes that finite-precision LSTMs can model real-time simplified k-counter machines in theory and practice, making them more powerful than finite-precision SRNNs and GRUs. It also identifies practical stability and learnability as an open question.
- IBFP-LSTMs can model a real-time SKCM both theoretically and in practice.
- IBFP-SRNNs and IBFP-GRUs cannot implement unbounded counting and are therefore restricted to recognizing regular languages.
- IBFP-IRNNs can perform input-dependent counting and are more powerful than IBFP-SRNNs.
- The practicality of discovering and maintaining stable counting behavior remains open for future work.
A Simplified K-Counter Machines
An SKCM is a finite-state machine augmented with counters that update from input symbols and whose transitions and acceptance decisions observe only whether counters are zero.
- Each counter can be incremented, decremented, reset, or left unchanged through pointwise operations.
- An SKCM consists of a finite alphabet, finite state set, initial state, k counters, transition and update functions, and accepting masked configurations.
- The machine starts in an initial state with all counters set to zero.
- In the formal definition, counter updates depend only on input symbols, although the paper notes that practical LSTMs can use state-input combinations.
- Transitions and acceptance inspect counters only through their zero-ness, not their exact nonzero values.
A.1 Computational Power of SKCMs
SKCMs recognize some context-free and context-sensitive counting languages but cannot recognize palindromes, because their reachable configurations grow polynomially rather than exponentially with input length.
- SKCMs recognize anbn and anbncn but not the context-free language of palindromes.
- anbn: The anbn construction uses one counter, increments on a, decrements on b, and accepts only after an equal count without returning from the b phase to the a phase.
- anbncn: The anbncn construction uses two counters to track the a-to-b and b-to-c count relationships, accepting when both counters are zero in the final state.
- Palindromes: A palindrome recognizer would require a unique configuration for every prefix over {a, b}, requiring exponentially many configurations.
- Palindromes: An SKCM with k counters has |Q| · (2n + 1)^k possible configurations on inputs of length n, which is polynomial in n.
- Palindromes: By the pigeonhole principle, two distinct prefixes eventually reach the same configuration and therefore cannot be distinguished after appending a suitable suffix.
B Impossibility of Counting in Binary
The paper proves that single-layer squashing-activation RNNs cannot reliably implement binary counters that increase, or increase and decrease, even with certain helper dimensions.
- Binary Interpretation: A binary counter interprets positive hidden values as 1 and negative values as 0, producing a binary number from selected state dimensions.
- Binary Counting: Binary counting permits the interpreted value to increase, decrease, reset to 0, or remain unchanged on each transition.
- Consistently Increasing Counter: The proof targets a single-layer SRNN whose hidden state consistently increments a binary counter on one input symbol.
- Consistently Increasing Counter: For a three-dimensional counter, linear affine updates and nonlinear carry behavior impose contradictory sign constraints, ruling out consistent binary incrementing.
- Limitations: Parallel positive and negative counters could represent decreases, but finite training provides no basis for generalizing binary carry behavior to unseen dimensions.
- Consistently Increasing Counter: The argument extends to larger counters by padding, but does not automatically cover additional non-counting helper dimensions.
- Bi-Directional Counter: Even with helper dimensions, no SRNN can implement a binary counter that increases on one token and decreases on another for n ≥ 3.
- Bi-Directional Counter: The bidirectional construction yields opposing constraints on the same bias difference, producing a contradiction and ruling out such an SRNN.