A Formal Hierarchy of RNN Architectures
Authors:
- William MerrillWMWilliam Merrill
- Eran YahavEYEran Yahav
Preprint
Abstract
We develop a formal hierarchy of the expressive capacity of RNN architectures. The hierarchy is based on two formal properties: space complexity, which measures the RNN's memory, and rational recurrence, defined as whether the recurrent update can be described by a weighted finite-state machine. We place several RNN variants within this hierarchy. For example, we prove the LSTM is not rational, which formally separates it from the related QRNN (Bradbury et al., 2016). We also show how these models' expressive capacity is expanded by stacking multiple layers or composing them with different pooling functions. Our results build on the theory of "saturated" RNNs (Merrill, 2019). While formally extending these findings to unsaturated RNNs is left to future work, we hypothesize that the practical learnable capacity of unsaturated RNNs obeys a similar hierarchy. Experimental findings from training unsaturated networks on formal languages support this conjecture.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Theoretical Limitations of Self-Attention in Neural Sequence ModelsTransactions of the Association for Computational Linguistics, 2020
- RNN Architecture Learning with Sparse Regularization2019
- Bridging CNNs, RNNs, and Weighted Finite-State Machines2018
- Rational Recurrences2018
- Recurrent Neural Networks as Weighted Language Recognizers2018
- Spectral learning of weighted automataMachine Learning, 2013
- Context-Free Recognition with Weighted AutomataGrammars, 2000
- On the computational power of neural nets1992
- Realizations by stochastic finite automataJournal of Computer and System Sciences, 1971
- Counter machines and counter languagesTheory of Computing Systems, 1968