Elamur Research⌕
☰
home / papers / 2022 / Neural Networks and the Chomsky Hierarchy

Neural Networks and the Chomsky Hierarchy

Summary

The authors investigate whether the theory of computation, specifically the Chomsky hierarchy, can predict where the ability of neural networks to generalize out of distribution ends. They test length generalization: a model is trained on short sequences and tested on considerably longer ones. The DeepMind team assembled 15 synthetic tasks and assigned them to levels of the hierarchy: regular, deterministic context-free, and context-sensitive. In total, 20,910 models were trained. Among them are RNN, LSTM and Transformer, as well as networks with differentiable structured memory: Stack-RNN and Tape-RNN. It turned out that a task's level in the hierarchy is a good predictor of whether an architecture can handle it. RNN and Transformer failed to generalize on non-regular tasks. LSTM mastered regular languages and languages that require a counter. Only models with a stack or a memory tape generalized on context-free and context-sensitive tasks. In some cases a network fit the training examples perfectly, yet additional data and parameters still did not enable it to generalize. The work is significant in that it demonstrates structural limits of scaling. It also highlights the role of memory as an inductive bias.

Key points

  • Scale of the experiment: 20,910 models, 15 tasks. The tasks are divided into levels R, DCF and CS, and include Parity Check, Reverse String, Binary Multiplication and Bucket Sort.
  • The benchmark for testing length generalization is open-sourced: github.com/deepmind/neural_networks_chomsky_hierarchy.
  • The architectures map onto the hierarchy as follows: RNN and Transformer do not go beyond the regular level, LSTM reaches the level of counter languages, and Stack-RNN and Tape-RNN rise to DCF and CS.
  • In the autoregressive setting, Stack-RNN achieves 100.0% on Stack Manipulation and 99.3% on Reverse String. A plain RNN scores only about 57–62% on the same tasks.
  • A Transformer with relative positional encodings was tested separately: from 5 to 25 layers and from 100,000 to 10,000,000 training steps. For the most part, neither a larger model nor longer training improved length generalization. The authors interpret this as a hard limit for scaling laws.

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

Fields: AI & machine learning

Cite

Cite as Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness and Pedro A. Ortega. 2022. Neural Networks and the Chomsky Hierarchy. arXiv:2207.02098.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2207.02098 · arXiv 2207.02098

@misc{deletang2022neural,
  title = {{Neural Networks and the Chomsky Hierarchy}},
  author = {Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness and Pedro A. Ortega},
  year = {2022},
  doi = {10.48550/arxiv.2207.02098},
  eprint = {2207.02098},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2207.02098}
}

References

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

  1. Joshua Ackerman and George Cybenko. A survey of neural networks and formal languages. CoRR, 2020. find
  2. Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay V. Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. CoRR, 2022. our card
  3. Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Claudio Fantacci, Jonathan Godwin, Chris Jones, Tom Hennigan, Matteo Hessel, Steven Kapturowski, Thomas Keck, Iurii Kemaev, Michael King, Lena Martens, Vl… find
  4. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In 3rd International Conference on Learning Representations, 2015. our card
  5. Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Logical extrapolation without overthinking. CoRR, 2022. find
  6. Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Alle… our card
  7. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020. find
  8. Mikael Bodén and Janet Wiles. Context-free and context-sensitive dynamics in recurrent neural networks. Connect. Sci., 2000. find
  9. Mikael Bodén and Janet Wiles. On learning context-free and context-sensitive languages. IEEE Trans. Neural Networks, 2002. find
  10. James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github.com/google/jax . ↗
  11. Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. Recurrent neural networks as weighted language recognizers. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2018. find
  12. David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention, 2022. URL https://arxiv.org/abs/2202.12172 . ↗
  13. Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Pro… find
  14. Noam Chomsky. Three models for the description of language. IRE Trans. Inf. Theory, 1956. find
  15. Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoc Viet Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Conference of the Association for Computational Linguistics, 2019. find
  16. Ivo Danihelka, Greg Wayne, Benigno Uria, Nal Kalchbrenner, and Alex Graves. Associative long short-term memory. In Proceedings of the 33nd International Conference on Machine Learning, 2016. find
  17. Sreerupa Das, C. Lee Giles, and Guo-Zheng Sun. Learning context-free grammars: Capabilities and limitations of a recurrent neural network with an external stack memory. In Fourteenth Annual Conference of the Cognitive Science Society, 1992a. find
  18. Sreerupa Das, C. Lee Giles, and Guo-Zheng Sun. Using prior knowledge in a NNPDA to learn context-free languages. In Advances in Neural Information Processing Systems 5, 1992b. find
  19. A. Philip Dawid. Present position and potential developments: Some personal views: Statistical theory: The prequential approach. Journal of the Royal Statistical Society. Series A (General), 1984. find
  20. Brian DuSell and David Chiang. Learning context-free languages with nondeterministic stack rnns. In Proceedings of the 24th Conference on Computational Natural Language Learning, 2020. find
  21. Brian DuSell and David Chiang. Learning hierarchical structures with differentiable nondeterministic stacks. In The Tenth International Conference on Learning Representations, 2022. find
  22. Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize dyck-n languages? In Findings of the Association for Computational Linguistics, 2020. find
  23. Jeffrey L. Elman. Finding structure in time. Cogn. Sci., 1990. find
  24. Karlis Freivalds and Renars Liepins. Improving the neural GPU architecture for algorithm learning. CoRR, 2017. find
  25. Felix A. Gers and Jürgen Schmidhuber. LSTM recurrent networks learn simple context-free and context-sensitive languages. IEEE Trans. Neural Networks, 2001. find
  26. C. Lee Giles, Clifford B. Miller, Dong Chen, Hsing-Hen Chen, Guo-Zheng Sun, and Yee-Chun Lee. Learning and extracting finite state automata with second-order recurrent neural networks. Neural Comput., 1992. find
  27. David E. Goldberg. Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley, 1989. find
  28. Faustino J. Gomez, Jürgen Schmidhuber, and Risto Miikkulainen. Accelerated neural evolution through cooperatively coevolved synapses. J. Mach. Learn. Res., 2008. find
  29. Alex Graves. Adaptive computation time for recurrent neural networks. CoRR, 2016. find
  30. Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. CoRR, 2014. find
  31. Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwinska, Sergio Gomez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John P. Agapiou, Adrià Puigdomènech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield… find
  32. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In Advances in Neural Information Processing Systems 28, 2015. find
  33. Çaglar Gülçehre, Sarath Chandar, Kyunghyun Cho, and Yoshua Bengio. Dynamic neural turing machine with continuous and discrete addressing schemes. Neural Comput., 2018. find
  34. Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 2020. find
  35. Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn. Context-free transductions with neural stacks. In Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, 2018. find
  36. Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. CoRR, 2022. find
  37. Tom Hennigan, Trevor Cai, Tamara Norman, and Igor Babuschkin. Haiku: Sonnet for JAX, 2020. URL http://github.com/deepmind/dm-haiku . ↗
  38. Matteo Hessel, David Budden, Fabio Viola, Mihaela Rosca, Eren Sezener, and Tom Hennigan. Optax: composable gradient transformation and optimisation, in jax!, 2020. URL http://github.com/ deepmind/optax . ↗
  39. Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 1997. find
  40. John H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, 1992. find
  41. Steffen Hölldobler, Yvonne Kalinke, and Helko Lehmann. Designing a counter: Another case study of dynamics and activation landscapes in recurrent networks. In Advances in Artificial Intelligence, 21st Annual German Conference on Artificial Intelligence, 1997. find
  42. Armand Joulin and Tomás Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in Neural Information Processing Systems 28, 2015. find
  43. Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. In 4th International Conference on Learning Representations, 2016. find
  44. Nal Kalchbrenner, Ivo Danihelka, and Alex Graves. Grid long short-term memory. In 4th International Conference on Learning Representations, 2016. find
  45. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, 2020. our card
  46. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, 2015. find
  47. Samuel A. Korsky and Robert C. Berwick. On the computational power of rnns. CoRR, 2019. find
  48. Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever. Neural random-access machines. In 4th International Conference on Learning Representations, 2016. find
  49. Percy Liang, Michael I. Jordan, and Dan Klein. Learning dependency-based compositional semantics. Comput. Linguistics, 2013. find
  50. Ankur Arjun Mali, Alexander Ororbia, Daniel Kifer, and C. Lee Giles. Recognizing long grammatical sequences using recurrent networks augmented with an external differentiable stack. In Proceedings of the 15th International Conference on Grammatical Inference, 2021. find
  51. William Merrill. Sequential neural networks as automata. CoRR, 2019. find
  52. William Merrill and Ashish Sabharwal. Log-precision transformers are constant-depth uniform threshold circuits. CoRR, 2022. find
  53. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. A formal hierarchy of RNN architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020. find
  54. Marvin L. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, Inc., 1967. find
  55. Tom M. Mitchell. The need for biases in learning generalizations. Technical report, Rutgers University, 1980. find
  56. Michael Mozer and Sreerupa Das. A connectionist symbol manipulator that discovers the structure of context-free languages. In Advances in Neural Information Processing Systems 5, 1992. find
  57. Peter Nordin. Evolutionary program induction of binary machine code and its applications. PhD thesis, Dortmund University of Technology, 1997. find
  58. Jorge Pérez, Javier Marinkovic, and Pablo Barceló. On the turing completeness of modern neural network architectures. In 7th International Conference on Learning Representations, 2019. find
  59. Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. J. Mach. Learn. Res., 2021. find
  60. Jordan B. Pollack. The induction of dynamical recognizers. Mach. Learn., 1991. find
  61. Alethea Power, Yuri Burda, Harrison Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. CoRR, 2022. find
  62. Ofir Press, Noah A. Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. CoRR, 2021. find
  63. Eric Price, Wojciech Zaremba, and Ilya Sutskever. Extensions and limitations of the neural GPU. CoRR, 2016. find
  64. Elaine Rich. Automata, Computability and Complexity. Prentice-Hall, 2007. find
  65. Paul Rodriguez and Janet Wiles. Recurrent neural networks can learn to implement symbol-sensitive counting. In Advances in Neural Information Processing Systems 10, 1997. find
  66. John E. Savage. Models of computation - exploring the power of computing. Addison-Wesley, 1998. find
  67. Luzi Sennhauser and Robert C. Berwick. Evaluating the ability of lstms to learn context-free grammars. In Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, 2018. find
  68. Hava T. Siegelmann and Eduardo D. Sontag. Analog computation via neural networks. Theor. Comput. Sci., 1994. find
  69. Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, 1997. find
  70. Natalia Skachkova, Thomas Alexander Trost, and Dietrich Klakow. Closing brackets with recurrent neural networks. In Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, 2018. find
  71. Ray J. Solomonoff. A formal theory of inductive inference. part I. Inf. Control., 1964a. find
  72. Ray J. Solomonoff. A formal theory of inductive inference. part II. Inf. Control., 1964b. find
  73. Ray J. Solomonoff. Algorithmic probability: Theory and applications. In Information Theory and Statistical Learning. Springer US, 2009. find
  74. Ray J. Solomonoff. Algorithmic probability, heuristic programming and agi. In Proceedings of the 3d Conference on Artificial General Intelligence, 2010. find
  75. Mark Steijvers and Peter Grünwald. A recurrent network that performs a context-sensitive prediction task. In Eighteenth Annual Conference of the Cognitive Science Society, 1996. find
  76. John Stogin, Ankur Arjun Mali, and C. Lee Giles. Provably stable interpretable encodings of context free grammars in rnns with a differentiable stack. CoRR, 2020. find
  77. Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, 2021. our card
  78. Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. In Advances in Neural Information Processing Systems 28, 2015. find
  79. G. Z. Sun, C. L. Giles, H. H. Chen, and Y. C. Lee. The neural network pushdown automaton: model, stack and learning simulations. Technical report, University of Maryland, 1993. find
  80. Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems 27, 2014. find
  81. Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M. Shieber. LSTM networks can perform dynamic counting. CoRR, 2019a. find
  82. Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M. Shieber. Memory-augmented recurrent neural networks can learn generalized dyck languages. CoRR, 2019b. find
  83. Vladimir Vapnik. Statistical learning theory. Wiley, 1998. find
  84. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30, 2017. our card
  85. Gail Weiss, Yoav Goldberg, and Eran Yahav. 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, 2018. our card
  86. Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In Proceedings of the 38th International Conference on Machine Learning, 2021. find
  87. Jason Weston, Sumit Chopra, and Antoine Bordes. Memory networks. In 3rd International Conference on Learning Representations, 2015. find
  88. Janet Wiles and Jeff Elman. Learning to count without a counter: A case study of dynamics and activation landscapes in recurrent networks. In Seventeenth Annual Conference of the Cognitive Science Society, 1995. find
  89. Mark Wineberg and Franz Oppacher. A representation scheme to perform program induction in a canonical genetic algorithm. In Parallel Problem Solving from Nature - PPSN III, International Conference on Evolutionary Computation, 1994. find
  90. Greg Yang and Alexander M. Rush. Lie-access neural turing machines. In 5th International Conference on Learning Representations, 2017. find
  91. Dani Yogatama, Yishu Miao, Gábor Melis, Wang Ling, Adhiguna Kuncoro, Chris Dyer, and Phil Blunsom. Memory architectures in recurrent neural network language models. In 6th International Conference on Learning Representations, 2018. find
  92. Wojciech Zaremba and Ilya Sutskever. Reinforcement learning neural turing machines. CoRR, 2015. find
  93. Wojciech Zaremba, Tomás Mikolov, Armand Joulin, and Rob Fergus. Learning simple algorithms from examples. In Proceedings of the 33nd International Conference on Machine Learning, 2016. find
  94. Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with LEGO: a synthetic reasoning task. CoRR, 2022. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/deletang-2022-neural-networks-chomsky-hierarchy/