Recurrent neural networks empirically generate natural language with high syntactic fidelity. However, their success is not well-understood theoretically. We provide theoretical insight into this success, proving in a finite-precision setting that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. We introduce Dyck-($k$,$m$), the language of well-nested brackets (of $k$ types) and $m$-bounded nesting depth, reflecting the bounded memory needs and long-distance dependencies of natural language syntax. The best known results use $O(k^{\frac{m}{2}})$ memory (hidden units) to generate these languages. We prove that an RNN with $O(m \log k)$ hidden units suffices, an exponential reduction in memory, by an explicit construction. Finally, we show that no algorithm, even with unbounded computation, can suffice with $o(m \log k)$ hidden units.

本文提供了理论洞见，证明在有限精度设置中，递归神经网络可以有效地生成有界分层语言，反映了自然语言句法的脚手架，最优秀的结果使用O(k^（m/2））存储器（隐藏单元）来生成这些语言，但我们证明了具有O(m log k)隐藏单元的RNN足以生成这些语言，这是存储器的指数降低；最后，我们表明没有算法，即使有无限的计算，也不能足以在o(m log k)隐藏单元中发挥作用。

RNNs可以生成具有优化内存的有界层次语言