Elamur Research⌕
☰
home / papers / 2021 / Self-Attention Networks Can Process Bounded Hierarchical Languages

Self-Attention Networks Can Process Bounded Hierarchical Languages

Paper · 2021 · Shunyu Yao, Binghui Peng, Christos Papadimitriou et al.

Summary

Earlier theoretical work (Hahn, 2020; Bhattamishra et al., 2020a) showed that self-attention networks cannot handle Dyck k, the language of well-nested brackets of k types that captures the core of all context-free languages. This seemed to conflict with the strong performance of Transformers on natural-language syntax. Yao et al. argue that human language uses only shallow recursion, so a more realistic target is Dyck k,D, where nesting depth is capped at D.

They give two explicit constructions. The first is a hard-attention recognizer with D + 1 layers, in which matching innermost brackets cancel out layer after layer. The second is a two-layer soft-attention generator that first computes each token's depth and then locates the latest unclosed open bracket. Both need only O(log k) memory per token per layer. The proofs rely on positional encodings that make comparing positions easy.

Experiments show that a Transformer with a scalar pos/n encoding extrapolates almost perfectly to longer strings and uses less memory than an LSTM. The work reconciles negative theory with empirical practice and highlights the role of positional encodings.

Key points

  • Memory bounds: the Transformer construction needs O(log k) memory with O(log n) precision. Finite-precision recurrent networks require Ω(D log k) (Hewitt et al., 2020).
  • Positional encodings on Dyck 8,10: test inputs had positions 700–1400, beyond the training lengths. Only the scalar POS/N encoding (i/6000) stayed near-perfect, even with 10 layers, while COS and LEARN failed to generalize.
  • Transformer vs. LSTM memory: a two-layer Transformer passed 90% test accuracy at d_model = 20, versus 40 for a one-layer LSTM. For 95% accuracy, the figures were 30 versus 50.
  • Broader language sweep (k ∈ {2, 8, 32, 128}, D ∈ {3, 5, 10, 15}):
    • The Transformer scored above 99.9% on validation and above 94% on test.
    • The LSTM fell below 80% for (32, 15), (128, 10) and (128, 15).
  • WikiText-103 test and code: RoBERTa models were trained from scratch for 150 epochs. POS/N ended with a slightly higher validation MLM loss than LEARN (1.55 vs. 1.31). Code is available at github.com/princeton-nlp/dyck-transformer.

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

🎓Columbia UniversityNew York · United States263 works · 57,820 citations🎓Princeton UniversityPrinceton · United States137 works · 53,849 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 worksComputational Theory and Mathematics · 496 works

Cite

Cite as Shunyu Yao, Binghui Peng, Christos Papadimitriou and Karthik Narasimhan. 2021. Self-Attention Networks Can Process Bounded Hierarchical Languages. arXiv:2105.11115.

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

@misc{yao2021self,
  title = {{Self-Attention Networks Can Process Bounded Hierarchical Languages}},
  author = {Shunyu Yao, Binghui Peng, Christos Papadimitriou and Karthik Narasimhan},
  year = {2021},
  doi = {10.48550/arxiv.2105.11115},
  eprint = {2105.11115},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2105.11115}
}

References

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

  1. Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. 2016. Layer normalization. arXiv preprint arXiv:1607.06450.
  2. Jean-Phillipe Bernardy. 2018. Can recurrent neural networks learn nested recursion? In Linguistic Issues in Language Technology, Volume 16, 2018. CSLI Publications. find
  3. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020a. On the ability of self-attention networks to recognize counter languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096–7116. find
  4. Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020b. On the computational power of transformers and its implications in sequence modeling. In Proceedings of the 24th Conference on Computational Natural Language Learning, pages 455–475, Online. Association for Computational Linguistics. find
  5. Jonathan R Brennan and John T Hale. 2019. Hierarchical structure guides rapid linguistic predictions during naturalistic listening. PloS one, 14(1):e0207741. find
  6. Mia Xu Chen, Orhan Firat, Ankur Bapna, Melvin Johnson, Wolfgang Macherey, George Foster, Llion Jones, Mike Schuster, Noam Shazeer, Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Zhifeng Chen, Yonghui Wu, and Macduff Hughes. 2018. The best of both worlds: Combining recent advances in ne…
  7. Noam Chomsky. 1956. Three models for the description of language. IRE Transactions on information theory, 2(3):113–124. find
  8. 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
  9. 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. Citeseer. find
  10. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. 2019. Universal transformers. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. find
  11. Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. 2020. How can self-attention networks recognize Dyck-n languages? In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 4301– 4306, Online. Association for Computational Linguistics.
  12. Jeffrey L Elman. 1990. Finding structure in time. Cognitive science, 14(2):179–211. find
  13. Stefan L Frank, Rens Bod, and Morten H Christiansen. 2012. How hierarchical is language use? Proceedings of the Royal Society B: Biological Sciences, 279(1747):4522–4531. find
  14. Stefan L Frank and Morten H Christiansen. 2018. Hierarchical and sequential processing of language: A response to: Ding, melloni, tian, and poeppel (2017). rule-based and word-level statistics-based processing of language: insights from neuroscience. language, cognition and neuroscience. Language, C… find
  15. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171. find
  16. Jie Hao, Xing Wang, Baosong Yang, Longyue Wang, Jinfeng Zhang, and Zhaopeng Tu. 2019. Modeling recurrence for transformer. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Paper… find
  17. Marc D Hauser, Noam Chomsky, and W Tecumseh Fitch. 2002. The faculty of language: what is it, who has it, and how did it evolve? science, 298(5598):1569–1579. find
  18. Han He and Jinho D Choi. 2019. Establishing strong baselines for the new decade: Sequence tagging, syntactic and semantic parsing with bert. arXiv preprint arXiv:1908.04943. — [arXiv:1908.04943](https://arxiv.org/abs/1908.04943) find
  19. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770–778. IEEE Computer Society.
  20. John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning. 2020. RNNs can generate bounded hierarchical languages with optimal memory. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1978–2010, Online. Association for C…
  21. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find
  22. Lifeng Jin, Finale Doshi-Velez, Timothy Miller, William Schuler, and Lane Schwartz. 2018. Unsupervised grammar induction with depth-bounded PCFG. Transactions of the Association for Computational Linguistics, 6:211–224.
  23. Jorge Pérez, Javier Marinkovic, and Pablo Barceló. 2019. On the turing completeness of modern neural network architectures. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. find
  24. Fred Karlsson. 2007. Constraints on multiple center-embedding of clauses. Journal of Linguistics, pages 365–392. find
  25. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9. find
  26. Guolin Ke, Di He, and Tie-Yan Liu. 2021. Rethinking the positional encoding in language pre-training. In International Conference on Learning Representations, (ICLR 2021). find
  27. 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
  28. Stephen C Levinson. 2014. Pragmatics as the origin of recursion. In Language and recursion, pages 3–13. Springer. find
  29. Yongjie Lin, Yi Chern Tan, and Robert Frank. 2019. Open sesame: Getting inside BERT’s linguistic knowledge. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 241–253, Florence, Italy. Association for Computational Linguistics.
  30. Christopher D Manning, Kevin Clark, John Hewitt, Urvashi Khandelwal, and Omer Levy. 2020. Emergent linguistic structure in artificial neural networks trained by self-supervision. Proceedings of the National Academy of Sciences, 117(48):30046–30054. find
  31. Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2017. Pointer sentinel mixture models. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. Open-Review.net.
  32. 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, pages 443–459, Online. Association for Computational Linguistics. find
  33. Matthew J Nelson, Imen El Karoui, Kristof Giber, Xiaofang Yang, Laurent Cohen, Hilda Koopman, Sydney S Cash, Lionel Naccache, John T Hale, Christophe Pallier, et al. 2017. Neurophysiological dynamics of phrase-structure building during sentence processing. Proceedings of the National Academy of Scie… find
  34. Isabel Papadimitriou and Dan Jurafsky. 2020. Learning Music Helps You Read: Using transfer to study linguistic structure in language models. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6829–6839, Online. Association for Computational Lingu… find
  35. Ali Rahimi and Benjamin Recht. 2007. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages 11… 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. Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 464–468, New…
  38. Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Shirui Pan, and Chengqi Zhang. 2018. Disan: Directional self-attention network for rnn/cnn-free language understanding. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Arti…
  39. Vighnesh Leonardo Shiv and Chris Quirk. 2019. Novel positional encodings to enable tree-based transformers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 12058–… find
  40. Mark Steijvers and Peter Grünwald. 1996. A recurrent network that performs a context-sensitive prediction task. In Proceedings of the 18th annual conference of the cognitive science society, pages 335–339. find
  41. Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M Shieber. 2019. Memory-augmented recurrent neural networks can learn generalized dyck languages. arXiv preprint arXiv:1911.03329. — [arXiv:1911.03329](https://arxiv.org/abs/1911.03329) find
  42. Ian Tenney, Dipanjan Das, and Ellie Pavlick. 2019. BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4593– 4601, Florence, Italy. Association for Computational Linguistics.
  43. Ke Tran, Arianna Bisazza, and Christof Monz. 2018. The importance of being recurrent for modeling hierarchical structure. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4731–4736, Brussels, Belgium. Association for Computational Linguistics.
  44. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017,…
  45. Benyou Wang, Donghao Zhao, Christina Lioma, Qiuchi Li, Peng Zhang, and Jakob Grue Simonsen. 2020. Encoding word order in complex embeddings. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. find
  46. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pier-ric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019. Huggingface’s transformers: State-of-the-art natural language processing. arXiv preprint arXiv:1910.03771.
  47. Baosong Yang, Longyue Wang, Derek F. Wong, Lidia S. Chao, and Zhaopeng Tu. 2019. Assessing the ability of self-attention networks to learn word order. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3635–3644, Florence, Italy. Association for Computa… find
  48. 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
  49. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. 2020. Are transformers universal approximators of sequence-to-sequence functions? In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net…
  50. Yu Zhang, Houquan Zhou, and Zhenghua Li. 2020. Fast and accurate neural CRF constituency parsing. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 4046–4053. ijcai.org. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yao-2021-self-attention-networks-process-bounded/