A Formal Hierarchy of RNN Architectures (2020)

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. We provide empirical results to support this conjecture. Experimental findings from training unsaturated networks on formal languages support this conjecture.

## introduction while neural networks are central to the performance of today's strongest nlp systems, theoretical understanding of the formal properties of different kinds of networks is still limited. it is established, for example, that the elman (1990) rnn is turing-complete, given infinite precision and computation time @xcite @xcite . but tightening these unrealistic assumptions has serious implications for expressive power @xcite , leaving a significant gap between classical theory and practice, which theorems in this paper attempt to address. recently, @xcite introduced rational rnns, a subclass of rnns whose internal state can be computed by independent weighted finite automata (wfas). intuitively, such models have a computationally simpler recurrent update than conventional models like long short-term memory networks (lstms; @xcite . empirically, rational rnns like the quasirecurrent neural network @xcite and unigram rational rnn @xcite perform comparably to the lstm, with a smaller computational budget. still, the underlying simplicity of rational models raises the question of whether their expressive power is fundamentally limited compared to other rnns. in a separate line of work, @xcite introduced the saturated rnn 1 as a formal model for analyzing the capacity of rnns. a saturated rnn is a simplified network where all activation functions have been replaced by step functions. the saturated network may be seen intuitively as a "stable" version of its original rnn, in which the in-ternal activations act discretely. a growing body of work-including this paper-finds that the saturated theory predicts differences in practical learnable capacity for various rnn architectures @xcite @xcite . we compare the expressive power of rational and non-rational rnns, distinguishing between state expressiveness (what kind and amount of information the rnn states can capture) and language expressiveness (what languages can be recognized when the state is passed to a classifier). to do this, we build on the theory of saturated rnns. state expressiveness we introduce a unified hierarchy (figure 1 ) of the functions expressible by the states of rational and non-rational rnn encoders. the hierarchy is defined by two formal properties: space complexity, which is a measure of network memory, foot_1 and rational recurrence, whether the internal structure of the rnn can be described by wfas. the hierarchy reveals concrete differences between lstms and qrnns, and further separates both from a class containing convolutional neural networks (cnns, @xcite , elman rnns, and gated recurrent units (gru; @xcite . we provide the first formal proof that lstms can encode functions that rational recurrences cannot. on the other hand, we show that the saturated elman rnn and gru are rational recurrences with constant space complexity, whereas the qrnn has unbounded space complexity. we also show that an unrestricted wfa has rich expressive power beyond any saturated rnn we consider-including the lstm. this difference potentially opens the door to more expressive rnns incorporating the computational efficiency of rational recurrences. language expressiveness when applied to classification tasks like language recognition, rnns are typically combined with a "decoder": additional layer(s) that map their hidden states to a prediction. thus, despite differences in state expressiveness, rational rnns might be able to achieve comparable empirical performance to non-rational rnns on nlp tasks. in this work, we consider the setup in which the decoders only view the final hidden state of the rnn. 3 we demonstrate that a sufficiently strong decoder can overcome some of the differences in state expressiveness between different models. for example, an lstm can recognize a n b n with a single decoding layer, whereas a qrnn provably cannot until the decoder has two layers. however, we also construct a language that an lstm can recognize without a decoder, but a qrnn cannot recognize with any decoder. thus, no decoder can fully compensate for the weakness of the qrnn compared to the lstm. experiments finally, we conduct experiments on formal languages, justifying that our theorems correctly predict which languages unsaturated recognizers trained by gradient descent can learn. thus, we view our hierarchy as a useful formal tool for understanding the relative capabilities of different rnn architectures. roadmap we present the formal devices for our analysis of rnns in section 2. in section 3 we develop our hierarchy of state expressiveness for single-layer rnns. in section 4, we shift to study rnns as language recognizers. finally, in section 5, we provide empirical results evaluating the relevance of our predictions for unsaturated rnns. ## building blocks in this work, we analyze rnns using formal models from automata theory-in particular, wfas and counter automata. in this section, we first define the basic notion of an encoder studied in this paper, and then introduce more specialized formal concepts: wfas, counter machines (cms), space complexity, and, finally, various rnn architectures. ## state expressiveness we now turn to presenting our results. in this section, we develop a hierarchy of single-layer rnns based on their state expressiveness. a set-theoretic view of the hierarchy is shown in figure 2 . let r be the set of rational series. the hierarchy relates θ(log n) space to the following sets: the different rnns are divided between the intersections of these classes. in subsection 3.1, we prove that the s-lstm, already established to have θ(log n) space, is not rr. in subsection 3.2, we demonstrate that encoders with restricted counting ability (e.g., qrnns) are rr, and in subsection 3.3, we show the same for all encoders with finite state (cnns, s-rnns, and s-grus). in subsection 3.4, we demonstrate that none of these rnns are rr-hard. in appendix f, we extend this analysis from rnns to self attention. ## language expressiveness having explored the set of functions expressible internally by different saturated rnn encoders, we turn to the languages recognizable when using them with a decoder. we consider the following setup: we say that a language l is decided by an encoder-decoder pair e, d if d(e(x)) = 1 for every sequence @xmath0. we explore which languages can be decided by different encoder-decoder pairings. some related results can be found in @xcite , who study the expressive power of wfas in relation to cfgs under a slightly different definition of language recognition. ## experiments in subsection 4.3, we showed that different saturated rnns vary in their ability to recognize a n b n and a n b n σ * . we now test empirically whether these predictions carry over to the learnable capacity of unsaturated rnns. 11 we compare the qrnn and lstm when coupled with a linear decoder d 1 . we also train a 2-layer qrnn ("qrnn2") and a 1-layer qrnn with a d 2 decoder ("qrnn+"). we train on strings of length 64, and evaluate generalization on longer strings. we also compare to a baseline that always predicts the majority class. the results are shown in figure 6 . we provide further experimental details in appendix e. ## conclusion we develop a hierarchy of saturated rnn encoders, considering two angles: space complexity and rational recurrence. based on the hierarchy, we formally distinguish the state expressiveness of the non-rational s-lstm and its rational counterpart, the s-qrnn. we show further distinctions in state expressiveness based on encoder space complexity. moreover, the hierarchy translates to differences in language recognition capabilities. strengthening the decoder alleviates some, but not all, of these differences. we present two languages, both recognizable by an lstm. we show that one can be recognized by an s-qrnn only with the help of a decoder, and that the other cannot be recognized by an s-qrnn with the help of any decoder. while this means existing rational rnns are fundamentally limited compared to lstms, we find that it is not necessarily being rationally recurrent that limits them: in fact, we prove that a wfa can perfectly encode its input-something no saturated rnn can do. we conclude with an analysis that shows that an rnn architecture's strength must also take into account its space complexity. these results further our understanding of the inner working of nlp systems. we hope they will guide the development of more expressive rational rnns.