Elamur Research⌕
☰
home / papers / 2019 / LSTM Networks Can Perform Dynamic Counting

LSTM Networks Can Perform Dynamic Counting

Paper · 2019 · Mirac Suzgun, Yonatan Belinkov, Stuart Shieber et al.

Summary

The paper asks whether recurrent networks with finite precision can do more than the simple one-turn counting that earlier work found in LSTMs trained on aⁿbⁿ and aⁿbⁿcⁿ. Specifically, it tests whether they can emulate k-counter automata whose counters may change direction any number of times, which the authors call dynamic counting. The authors compare small single-layer Elman-RNNs, GRUs and LSTMs on four synthetic tasks: Dyck-1, two shuffle languages built from disjoint Dyck-1 bracket pairs (Shuffle-2 and Shuffle-6), and Dyck-2. At each step, a model must predict the set of characters that may legally come next. A sequence counts as recognized only if every prediction is correct. LSTMs mastered Dyck-1 and the shuffle languages and generalized to sequences beyond the training range. Inspecting their cell states showed units behaving as explicit counters. No architecture learned Dyck-2, which requires a stack. The work therefore gives empirical support to the theory of Weiss et al. (2018) and maps out what gated RNNs can and cannot represent hierarchically.

Key points

  • Training setup. Inputs are one-hot and targets are k-hot. Training minimizes mean-squared error with sigmoid outputs thresholded at 0.5, using Adam (α = 0.001). Each experiment was repeated ten times with no embeddings or dropout.
  • Model sizes. All networks are tiny. They use 3 hidden units for Dyck-1, 4 for Dyck-2, 4 for Shuffle-2 and 8 for Shuffle-6.
  • Minimal LSTMs. A one-unit LSTM recognizes Dyck-1 by incrementing on "(" and decrementing on ")". A two-unit LSTM handles Shuffle-2.
  • Counters in Shuffle-6. In a Shuffle-6 LSTM, six of the eight cell units track the nesting depth of each bracket type, which amounts to emulating a DCA₆. Some units also counted sequence length.
  • Dyck-2 failure. Dyck-2 training data consisted of 10,000 sequences of length 2–50, sampled from a PCFG with p = 1/2 and q = 1/4. All models failed on this language. The last-closing-bracket task of Skachkova et al. (2018) was solved perfectly, but only through counting tricks rather than genuine recognition of the language.

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

🎓Harvard UniversityCambridge · United States112 works · 42,023 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 Mirac Suzgun, Yonatan Belinkov, Stuart Shieber and Sebastian Gehrmann. 2019. LSTM Networks Can Perform Dynamic Counting. Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/w19-3905 · arXiv 1906.03648

@inproceedings{suzgun2019lstm,
  title = {{LSTM Networks Can Perform Dynamic Counting}},
  author = {Mirac Suzgun, Yonatan Belinkov, Stuart Shieber and Sebastian Gehrmann},
  booktitle = {Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges},
  year = {2019},
  doi = {10.18653/v1/w19-3905},
  eprint = {1906.03648},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/w19-3905}
}

References

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

  1. networks learn nested recursion? LiLT (Linguistic Issues in Language Technology), 16(1). find
  2. Anthony Bau, Yonatan Belinkov, Hassan Sajjad, Nadir Durrani, Fahim Dalvi, and James Glass. 2019. Identifying and controlling important neurons in neural machine translation. In International Conference on Learning Representations. find
  3. Mikael Bodén and Janet Wiles. 2000. Context-free and context-sensitive dynamics in recurrent neural networks. Connection Science, 12(3-4):197–210. find
  4. Mikael Bodén, Janet Wiles, Bradley Tonkes, and Alan Blair. 1999. Learning to predict a context-free lan-Jean-Philippe Bernardy. 2018. Can recurrent neural Sepp Hochreiter. 1998. The vanishing gradient problem during learning recurrent neural nets and problem solutions. International Journal of Unce… find
  5. Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning phrase representations using RNN encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078.
  6. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long Short-Term Memory. Neural computation, 9(8):1735–1780. find
  7. Noam Chomsky and Marcel P Schützenberger. 1963. The algebraic theory of context-free languages. In Studies in Logic and the Foundations of Mathematics, volume 35, pages 118–161. Elsevier. find
  8. 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
  9. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.
  10. Fahim Dalvi, Nadir Durrani, Hassan Sajjad, Yonatan Belinkov, D. Anthony Bau, and James Glass. 2019. What is one grain of sand in the desert? analyzing individual neurons in deep NLP models. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. find
  11. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. 2014. Recognizing well-parenthesized expressions in the streaming model. SIAM Journal on Computing, 43(6):1880–1905. find
  12. Sreerupa Das, C Lee Giles, and Guo-Zheng Sun. 1992. Learning context-free grammars: Capabilities and limitations of a recurrent neural network with an external stack memory. In Proceedings of The Fourteenth Annual Conference of Cognitive Science Society. Indiana University, page 14. find
  13. Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černockỳ, and Sanjeev Khudanpur. 2010. Recurrent neural network based language model. In Eleventh annual conference of the international speech communication association. find
  14. Tristan Deleu and Joseph Dureau. 2016. Learning operations on a stack with Neural Turing Machines. arXiv preprint arXiv:1612.00827. — [arXiv:1612.00827](https://arxiv.org/abs/1612.00827) find
  15. Marvin Lee Minsky. 1967. Computation: Finite and Infinite Machines. Prentice-Hall Englewood Cliffs. find
  16. Jeffrey L Elman. 1990. Finding structure in time. Cognitive science, 14(2):179–211. find
  17. Paul Rodriguez. 2001. Simple recurrent networks learn context-free and context-sensitive languages by counting. Neural computation, 13(9):2093– 2118. find
  18. Patrick C Fischer, Albert R Meyer, and Arnold L Rosenberg. 1968. Counter machines and counter languages. Mathematical systems theory, 2(3):265– 283. find
  19. Paul Rodriguez and Janet Wiles. 1998. Recurrent neural networks can learn to implement symbol-sensitive counting. In Advances in Neural Information Processing Systems, pages 87–93. find
  20. Felix A Gers and E Schmidhuber. 2001. LSTM recurrent networks learn simple context-free and context-sensitive languages. IEEE Transactions on Neural Networks, 12(6):1333–1340. find
  21. 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. find
  22. Seymour Ginsburg and Edwin H Spanier. 1966. Finite-turn pushdown automata. SIAM Journal on Control, 4(3):429–453. find
  23. Xing Shi, Kevin Knight, and Deniz Yuret. 2016. Why neural translations are the right length. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2278–2282. find
  24. Alex Graves, Greg Wayne, and Ivo Danihelka. 2014. Neural Turing Machines. arXiv preprint arXiv:1410.5401. find
  25. Hava T Siegelmann and Eduardo D Sontag. 1995. On the computational power of neural nets. Journal of computer and system sciences, 50(1):132–150. find
  26. 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
  27. Natalia Skachkova, Thomas Trost, and Dietrich Klakow. 2018. Closing brackets with recurrent neural networks. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 232–239.
  28. Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn. 2018. Context-free transductions with neural stacks. arXiv preprint arXiv:1809.02836. find
  29. Mark Steijvers. 1996. A recurrent network that performs a context-sensitive prediction task. find
  30. Mirac Suzgun, Yonatan Belinkov, and Stuart M Shieber. 2019. On evaluating the generalization of LSTM models in formal languages. Proceedings of the Society for Computation in Linguistics (SCiL), pages 277–286. find
  31. Bradley Tonkes and Janet Wiles. 1997. Learning a context-free task with a recurrent neural network: An analysis of stability. In In Proceedings of the Fourth Biennial Conference of the Australasian Cognitive Science Society. Citeseer. find
  32. Leslie Valiant. 1973. Decision Procedures for Families of Deterministic Pushdown Automata. Ph.D. thesis, University of Warwick. find
  33. Leslie G Valiant. 1974. The equivalence problem for deterministic finite-turn pushdown automata. Information and Control, 25(2):123–133. find
  34. Leslie G Valiant. 1975. Regularity and related problems for deterministic pushdown automata. Journal of the ACM (JACM), 22(1):1–10. find
  35. Leslie G Valiant and Michael S Paterson. 1975. Deterministic one-counter automata. Journal of Computer and System Sciences, 10(3):340–350. find
  36. 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.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/suzgun-2019-lstm-networks-can-perform-dynamic/