Back to Search
Start Over
RNNs can generate bounded hierarchical languages with optimal memory
- Source :
- EMNLP (1), Scopus-Elsevier
- Publication Year :
- 2020
- Publisher :
- Association for Computational Linguistics, 2020.
-
Abstract
- 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.<br />Comment: EMNLP2020 + appendix typo fixes
- Subjects :
- FOS: Computer and information sciences
Discrete mathematics
Computer Science - Computation and Language
Reduction (recursion theory)
Computer science
Computation
05 social sciences
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
010501 environmental sciences
01 natural sciences
Syntax
050105 experimental psychology
Exponential function
Recurrent neural network
Bounded function
Nesting (computing)
0501 psychology and cognitive sciences
Computation and Language (cs.CL)
Natural language
0105 earth and related environmental sciences
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)
- Accession number :
- edsair.doi.dedup.....f5710b69420dcea64ac23f21dfc97de5