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.

本研究开发了一种表达式能力的RNN体系结构的形式化层次结构，这个层次结构基于空间复杂性和有理复发的形式属性。该研究将几种RNN变体放置在该层次结构中，并证明了LSTM不是合理的。我们还展示了通过堆叠多个图层或将它们与不同的池函数组合来扩展这些模型的表现力。我们的结果建立在“饱和”的RNN的理论基础之上。我们假设未饱和的RNN的实际可学习能力符合类似的层次结构，并通过对形式语言训练未饱和的网络的实验结果支持此假设。

RNN架构的正式层次结构