Elamur Research⌕
☰
home / papers / 2020 / On the Ability and Limitations of Transformers to Recognize Formal Languages

On the Ability and Limitations of Transformers to Recognize Formal Languages

Paper · 2020 · Satwik Bhattamishra, Kabir Ahuja and Navin Goyal

Summary

This EMNLP 2020 study asks which formal languages Transformers can actually learn in practice, compared with LSTMs. LSTMs are already known to handle regular languages and to behave like counter automata. The authors first give a theoretical construction showing that self-attention can indirectly emulate counter operations. This lets an encoder-only Transformer (BERT/GPT-style, with positional masking) recognize a subclass of counter languages, including Dyck-1, Shuffle-Dyck and n-ary Boolean Expressions. They then train models on more than 25 carefully chosen formal languages. They test generalization to longer strings, visualize internal representations, and vary positional encodings and depth.

On the counter subclass, Transformers generalize well, and their learned representations track the proposed construction. On regular languages, however, they lag clearly behind LSTMs. Performance drops on languages requiring periodicity or modular counting, and on star-free languages of higher dot-depth. This matters because it exposes concrete weaknesses of self-attention on inputs of practical size. It also highlights how much the architecture depends on positional encoding.

Key points

  • Coverage: over 25 formal languages in total, including over 15 regular ones. Counter languages tested include Dyck-1, Shuffle-k (Shuffle-Dyck), BoolExp-n, aⁿbⁿ and aⁿbⁿcⁿ.
  • Regular languages: results fit the hypothesis that Transformers handle star-free languages of dot-depth 1. They struggle with higher dot-depths and with non-star-free languages.
  • Need for positional encoding: without positional encoding, softmax aggregation makes outputs identical on runs of a single symbol. Such a model therefore provably cannot recognize (aa)* or even short Parity strings, whatever its size.
  • Custom encodings: a cos(nπ) positional encoding solves (aa)* but fails on (aaaa)*. Trainable fixed-length embeddings learned a cos(nπ)-like pattern but cannot extrapolate to longer inputs.
  • Relation to prior theory: the work contrasts with Hahn (2020), whose impossibility results for Parity and Dyck-2 concern very long inputs and expressivity only. Here the focus is on learnability at practical lengths.

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

🏢MicrosoftRedmond · United States240 works · 123,537 citations🏢Microsoft ResearchBengaluru · India9 works · 3,523 citations

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksComputational Theory and Mathematics · 116 works

Cite

Cite as Satwik Bhattamishra, Kabir Ahuja and Navin Goyal. 2020. On the Ability and Limitations of Transformers to Recognize Formal Languages. 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.576 · arXiv 2009.11264

@inproceedings{bhattamishra2020ability,
  title = {{On the Ability and Limitations of Transformers to Recognize Formal Languages}},
  author = {Satwik Bhattamishra, Kabir Ahuja and Navin Goyal},
  booktitle = {Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2020},
  doi = {10.18653/v1/2020.emnlp-main.576},
  eprint = {2009.11264},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/2020.emnlp-main.576}
}

References

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

  1. Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09286. find
  2. Rina Cohen and Janusz Brzozowski. 1971. Dot-depth of star-free events. Journal of Computer and System Sciences, 5:1–16. find
  3. Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. 2019. Transformer-XL: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978–2988, Florence, Italy. Assoc… find
  4. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,…
  5. Volker Diekert and Paul Gastin. 2008. First-order definable languages. In Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], volume 2 of Texts in Logic and Games, pages 261– 306. Amsterdam University Press. find
  6. Patrick C Fischer, Albert R Meyer, and Arnold L Rosenberg. 1968. Counter machines and counter languages. Mathematical systems theory, 2(3):265– 283. find
  7. Isabel Papadimitriou and Dan Jurafsky. 2020. Pretraining on non-linguistic structure as a tool for analyzing learning bias in language models. arXiv preprint arXiv:2004.14601. — [arXiv:2004.14601](https://arxiv.org/abs/2004.14601) find
  8. 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
  9. Jorge Pérez, Javier Marinković, and Pablo Barceló. 2019. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations. find
  10. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171. find
  11. Jean-ric Pin. 2017. The dot-depth hierarchy, 45 years later. In The Role of Theory in Computer Science, pages 177–201. find
  12. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find
  13. Gerhard Jäger and James Rogers. 2012. Formal language theory: refining the chomsky hierarchy. Philosophical Transactions of the Royal Society B: Biological Sciences, 367(1598):1956–1970. find
  14. John F Kolen and Stefan C Kremer. 2001. A field guide to dynamical recurrent networks. John Wiley & Sons. find
  15. 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
  16. Xuanqing Liu, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2020. Learning to encode position for transformer with continuous dynamical model. arXiv preprint arXiv:2003.09229. — [arXiv:2003.09229](https://arxiv.org/abs/2003.09229) find
  17. Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692. find
  18. Robert McNaughton and Seymour A. Papert. 1971. Counter-Free Automata (M.I.T. Research Monograph No. 65). The MIT Press. find
  19. 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
  20. William Merrill. 2020. On the linguistic capacity of real-time counter automata. arXiv preprint arXiv:2004.06866. — [arXiv:2004.06866](https://arxiv.org/abs/2004.06866) find
  21. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018. Improving language understanding by generative pre-training. URL https://s3-us-west-2.amazonaws. com/openai-assets/researchcovers/languageunsupervised/language understanding paper. pdf. ↗
  22. Emily Reif, Ann Yuan, Martin Wattenberg, Fernanda B Viegas, Andy Coenen, Adam Pearce, and Been Kim. 2019. Visualizing and measuring the geometry of bert. In Advances in Neural Information Processing Systems, pages 8592–8600.
  23. Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2020. A primer in bertology: What we know about how bert works. arXiv preprint arXiv:2002.12327.
  24. 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
  25. Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Shirui Pan, and C. Zhang. 2018. Disan: Directional self-attention network for rnn/cnn-free language understanding. In AAAI. find
  26. 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, Brussels, Belgium. Association for Computational Linguistics. find
  27. Howard Straubing. 1994. Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser Verlag, CHE. find
  28. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A Smith, and Eran Yahav. 2020. A formal hierarchy of rnn architectures. arXiv preprint arXiv:2004.08500. find
  29. Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. 2019a. 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. find
  30. Joshua J. Michalenko, Ameesh Shah, Abhinav Verma, Swarat Chaudhuri, and Ankit B. Patel. 2019. Finite automata can be linearly decoded from language-recognizing RNNs. In International Conference on Learning Representations. find
  31. Mirac Suzgun, Yonatan Belinkov, and Stuart M. Shieber. 2019b. On evaluating the generalization of LSTM models in formal languages. In Proceedings of the Society for Computation in Linguistics (SCiL) 2019, pages 277–286. find
  32. Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. 2019. Transformer dissection: An unified understanding for transformer’s attention via the lens of kernel. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and… find
  33. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. 2020. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations. find
  34. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in neural information processing systems, pages 5998–6008.
  35. Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. 2019. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5797–5808, Florence, I…
  36. Qinglong Wang, Kaixuan Zhang, Alexander G. Ororbia II, Xinyu Xing, Xue Liu, and C. Lee Giles. 2018a. A comparative study of rule extraction for recurrent neural networks. CoRR, abs/1801.05420v2. — [arXiv:1801.05420](https://arxiv.org/abs/1801.05420) find
  37. Qinglong Wang, Kaixuan Zhang, II Ororbia, G Alexander, Xinyu Xing, Xue Liu, and C Lee Giles. 2018b. A comparative study of rule extraction for recurrent neural networks. arXiv preprint arXiv:1801.05420. — [arXiv:1801.05420](https://arxiv.org/abs/1801.05420) find
  38. Alex Warstadt, Yu Cao, Ioana Grosu, Wei Peng, Hagen Blix, Yining Nie, Anna Alsop, Shikha Bordia, Haokun Liu, Alicia Parrish, Sheng-Fu Wang, Jason Phang, Anhad Mohananey, Phu Mon Htut, Paloma Jeretic, and Samuel R. Bowman. 2019. Investigating BERT’s knowledge of language: Five analysis methods with N…
  39. 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, Melbourne, Australia. Associati…
  40. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2019. Learning deterministic weighted automata with queries and counterexamples. In H. Wallach, H. Larochelle, A. Beygelzimer, F. AlcheBuc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8560–8571. Curran Associ… find
  41. Baosong Yang, Longyue Wang, Derek F. Wong, Lidia S. Chao, and Zhaopeng Tu. 2019. Assessing find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bhattamishra-2020-ability-limitations-transformers-recognize-formal/