Elamur Research⌕
☰
home / papers / 2020 / RNNs can generate bounded hierarchical languages with optimal memory

RNNs can generate bounded hierarchical languages with optimal memory

Paper · 2020 · John Hewitt, Michael Hahn, Surya Ganguli et al.

Summary

RNN language models capture natural-language syntax well in practice, but the theory behind this has been thin. The authors address this by studying Dyck-(k,m): strings of correctly nested brackets of k kinds where no more than m brackets are open at once. The language models two traits of human syntax: long-range nested dependencies and the limited embedding depth people actually use. Under realistic assumptions, the paper treats RNNs as generators rather than acceptors. Each hidden unit holds a constant number of bits. The authors give explicit Simple RNN and LSTM constructions in which the hidden state acts as a bounded stack. Bracket identities are stored in compact binary codes, so each symbol can be read off linearly. These networks need only O(m log k) hidden units, an exponential saving over earlier constructions. A communication-complexity argument shows that no generator can do asymptotically better, so the result is tight. A small learning study shows that LSTMs sized by this theory learn the languages and generalize to longer strings. Together, these results help explain why RNNs handle syntax well.

Key points

  • The Simple RNN construction uses 6m⌈log k⌉ − 2m hidden units. The LSTM version relies only on its gates and needs about half as many (3m⌈log k⌉ − m). Earlier generic constructions needed roughly k^(m/2) units.
  • The lower bound is Ω(m log k) hidden units and holds even for models with unlimited computation. RNNs are therefore memory-optimal up to constant factors.
  • In experiments, LSTMs were trained with k ∈ {2, 8, 32, 128} and m ∈ {3, 5}. Training lengths were capped at 84 (m=3) and 180 (m=5), and test strings were up to twice as long.
  • With 20 million training tokens, all configurations reached bracket-closing error below 10⁻⁴. This held even though most possible stack states never appeared in training.
  • The code is public on GitHub (john-hewitt/dyckkm-constructions and dyckkm-learning), and the experiments can be run on CodaLab.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States434 works · 314,419 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

Cite

Cite as John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang and Christopher D. Manning. 2020. RNNs can generate bounded hierarchical languages with optimal memory. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.emnlp-main.156

@inproceedings{hewitt2020rnns,
  title = {{RNNs can generate bounded hierarchical languages with optimal memory}},
  author = {John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang and Christopher D. Manning},
  booktitle = {Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2020},
  doi = {10.18653/v1/2020.emnlp-main.156},
  url = {https://doi.org/10.18653/v1/2020.emnlp-main.156}
}

References

45 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Noam Chomsky. 1956. Three models for the description of language. IRE Transactions on information theory, 2(3):113–124. find
  2. Noam Chomsky. 1959. On certain formal properties of grammars. Information and Control, 2(2):137 – 167. find
  3. Noam Chomsky and Marcel P Schützenberger. 1959. The algebraic theory of context-free languages. In Studies in Logic and the Foundations of Mathematics, volume 26, pages 118–161. Elsevier. find
  4. Jeffrey L Elman. 1990. Finding structure in time. Cognitive science, 14(2):179–211. find
  5. C. Lee Giles, Guo-Zheng Sun, Hsing-Hen Chen, Yee-Chun Lee, and Dong Chen. 1990. Higher order recurrent networks and grammatical inference. In D. S. Touretzky, editor, Advances in Neural Information Processing Systems 2, pages 380–387. Morgan-Kaufmann. find
  6. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. 2015. Learning to transduce with unbounded memory. In Advances in neural information processing systems, pages 1828– 1836. find
  7. Kristina Gulordava, Piotr Bojanowski, Edouard Grave, Tal Linzen, and Marco Baroni. 2018. Colorless green recurrent networks dream hierarchically. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume…
  8. Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn. 2018. Context-free transductions with neural stacks. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 306–315, Brussels, Belgium. As… find
  9. John Hewitt and Christopher D. Manning. 2019. A structural probe for finding syntax in word representations. In North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL). Association for Computational Linguistics.
  10. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find
  11. Bill G Horne and Don R Hush. 1994. Bounds on the complexity of recurrent neural network implementations of finite state machines. In Advances in neural information processing systems, pages 359–366. find
  12. Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. 2017. Quantized neural networks: Training neural networks with low precision weights and activations. The Journal of Machine Learning Research, 18(1):6869–6898. find
  13. Piotr Indyk. 1995. Optimal simulation of automata by neural nets. In Annual Symposium on Theoretical Aspects of Computer Science, pages 337–348. Springer. find
  14. Lifeng Jin, Finale Doshi-Velez, Timothy Miller, William Schuler, and Lane Schwartz. 2018. Depth-bounding is effective: Improvements and evaluation of unsupervised PCFG induction. arXiv preprint arXiv:1809.03112. find
  15. Aravind K Joshi, K Vijay Shanker, and David Weir. 1990. The convergence of mildly context-sensitive grammar formalisms. Technical Reports (CIS), page 539. find
  16. Armand Joulin and Tomas Mikolov. 2015. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in neural information processing systems, pages 190–198. find
  17. Fred Karlsson. 2007. Constraints on multiple center-embedding of clauses. Journal of Linguistics, 43(2):365–392. find
  18. Andrej Karpathy, Justin Johnson, and Li Fei-Fei. 2015. Visualizing and understanding recurrent networks. arXiv preprint arXiv:1506.02078.
  19. Urvashi Khandelwal, He He, Peng Qi, and Dan Jurafsky. 2018. Sharp nearby, fuzzy far away: How neural language models use context. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 284–294, Melbourne, Australia. Association for C… find
  20. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.
  21. Samuel A Korsky and Robert C Berwick. 2019. On the computational power of rnns. arXiv preprint arXiv:1906.06349. — [arXiv:1906.06349](https://arxiv.org/abs/1906.06349) find
  22. Adhiguna Kuncoro, Chris Dyer, John Hale, Dani Yogatama, Stephen Clark, and Phil Blunsom. 2018. LSTMs can learn syntax-sensitive dependencies well, but modeling structure makes them better. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pape…
  23. Yair Lakretz, German Kruszewski, Theo Desbordes, Dieuwke Hupkes, Stanislas Dehaene, and Marco Baroni. 2019. The emergence of number and syntax units in LSTM language models. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human La…
  24. Y C Lee, G Doolen, H H Chen, G Z Sun, T Maxwell, H Y Lee, and C L Giles. 1986. Machine learning using a higher order correlation network. Phys. D, 2(1–3):276–306. find
  25. Omer Levy, Kenton Lee, Nicholas FitzGerald, and Luke Zettlemoyer. 2018. Long short-term memory as a dynamically computed element-wise weighted sum. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), Melbourne, Australia. Association f… find
  26. Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016. Assessing the ability of LSTMs to learn syntax-sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521– 535.
  27. Rebecca Marvin and Tal Linzen. 2018. Targeted syntactic evaluation of language models. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1192–1202. find
  28. William Merrill. 2019. Sequential neural networks as automata. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 1–13, Florence. Association for Computational Linguistics. find
  29. William. Merrill. 2020. On the linguistic capacity of real-time counter automata. ArXiv, abs/2004.06866. — [arXiv:2004.06866](https://arxiv.org/abs/2004.06866) find
  30. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A Smith, and Eran Yahav. 2020. A formal hierarchy of rnn architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Seattle, USA. Association for Computational Lingu… find
  31. George A. Miller and Noam Chomsky. 1963. Finitary models of language users. In R. Duncan Luce, Robert R. Bush, and Eugene Galanter, editors, Handbook of mathematical psychology, pages 419–491. John Wiley and Sons, Inc., New York and London. find
  32. Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pages 8024–8035.
  33. Guillaume Rabusseau, Tianyu Li, and Doina Precup. 2019. Connecting weighted automata and recurrent neural networks through spectral learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1630–1639. find
  34. Philip Resnik. 1992. Left-corner parsing and psychological plausibility. In Proceedings of the 14th conference on Computational linguistics-Volume 1, pages 191–197. Association for Computational Linguistics. find
  35. Marten van Schijndel and Tal Linzen. 2018. Modeling garden path effects without explicit hierarchical syntax. In Tim Rogers, Marina Rau, Jerry Zhu, and Chuck Kalish, editors, Proceedings of the 40th Annual Conference of the Cognitive Science Society, pages 2600–2605. Cognitive Science Society, Austi… find
  36. Luzi Sennhauser and Robert Berwick. 2018. Evaluating the ability of LSTMs to learn context-free grammars. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 115–124, Brussels, Belgium. Association for Computational Linguistics. find
  37. Ravid Shwartz-Ziv and Naftali Tishby. 2017. Opening the black box of deep neural networks via information. arXiv preprint arXiv:1703.00810. — [arXiv:1703.00810](https://arxiv.org/abs/1703.00810) find
  38. Hava T. Siegelmann and Eduardo D. Sontag. 1992. On the computational power of neural nets. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT ’92, page 440–449, New York, NY, USA. Association for Computing Machinery. find
  39. Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. 2019. LSTM networks can perform dynamic counting. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 44–54, Florence. Association for Computational Linguistics.
  40. Mirac Suzgun, Yonatan Belinkov, and Stuart M Shieber. 2018. On evaluating the generalization of lstm models in formal languages. arXiv preprint arXiv:1811.01001. find
  41. Christian W Omlin and C Lee Giles. 1996. Constructing deterministic finite-state automata in recurrent neural networks. Journal of the ACM (JACM), 43(6):937–972. find
  42. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. On the practical computational power of finite precision rnns for language recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 740–745. Association for Computational L…
  43. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016. Google’s ne… find
  44. Xiang Yu, Ngoc Thang Vu, and Jonas Kuhn. 2019. Learning the Dyck language with attention-based Seq2Seq models. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 138–146, Florence, Italy. Association for Computational Linguistics. find
  45. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. 2017. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hewitt-2020-rnns-can-generate-bounded-hierarchical/