Elamur Research⌕
☰
home / papers / 2020 / How Can Self-Attention Networks Recognize Dyck-n Languages?

How Can Self-Attention Networks Recognize Dyck-n Languages?

Paper · 2020 · Javid Ebrahimi, Dhruv Gelda and Wei Zhang

Summary

The paper asks whether self-attention (SA) networks, essentially Transformer encoders without recurrence, can learn the Dyck-n (D n) languages of balanced strings with n bracket types. Earlier theoretical and empirical work had suggested this is hard for them. The authors frame recognition as next-symbol transduction: at every position the model must predict the full set of valid next brackets. This is a multi-label task trained with binary cross-entropy. They compare SA with and without a prepended starting symbol T (SA+ and SA−) and unidirectional LSTM baselines, all of similar size. Training data come from a PCFG following Suzgun et al. (2019), and test sequences are longer than any seen in training. The starting symbol strongly improves SA's generalization to longer and deeper strings. Second-layer attention maps in SA+ behave like a stack: each closing bracket attends to the most recent unmatched opening bracket, or to T when the stack is empty. SA+ is roughly on par with LSTMs. The authors argue this shows hierarchy can be learned without recursion, by learning to look up the correct head token.

Key points

  • Setup:
    • SA models have 2 layers, 4 heads and d = 256; the LSTMs use 320-dimensional states.
    • All models have about 1.6M parameters and are trained with Adam and no dropout.
    • Data for D1–D4: 32k training strings of length 2–50, 3.2k validation strings of length 52–74, and 10k test strings split between lengths 76–100 and 102–126.
  • D2 at lengths 102–126:
    • SA− essentially fails (0.006%).
    • SA+ reaches 58.82%.
    • LSTM− is better here at 73.20%, the only comparison SA+ loses to LSTM−.
  • Other D n results:
    • SA+ scores about 93% on lengths 76–100 for D2–D4.
    • On the longest bin it improves with more bracket types (66.88% for D3, 72.38% for D4), whereas LSTM accuracy declines as n grows.
  • Starting symbol: Adding T helps SA but slightly hurts LSTMs.
  • Stack compatibility:
    • The authors define a compatibility metric that checks whether attention matches a stack-based recognizer.
    • SA+ is perfectly compatible on training-range lengths, while SA− on D2 is near zero.
    • For SA+, accuracy and compatibility correlate at about 90% or higher (Pearson) across lengths 50–100.

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

🏢VisaFoster City · United States2 works · 106 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 Javid Ebrahimi, Dhruv Gelda and Wei Zhang. 2020. How Can Self-Attention Networks Recognize Dyck-n Languages?. Findings of the Association for Computational Linguistics: EMNLP 2020.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.findings-emnlp.384 · arXiv 2010.04303

@inproceedings{ebrahimi2020how,
  title = {{How Can Self-Attention Networks Recognize Dyck-n Languages?}},
  author = {Javid Ebrahimi, Dhruv Gelda and Wei Zhang},
  booktitle = {Findings of the Association for Computational Linguistics: EMNLP 2020},
  year = {2020},
  doi = {10.18653/v1/2020.findings-emnlp.384},
  eprint = {2010.04303},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/2020.findings-emnlp.384}
}

References

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

  1. Jean-Philippe Bernardy. 2018. Can recurrent neural networks learn nested recursion? LiLT (Linguistic Issues in Language Technology), 16(1). find
  2. Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. 2015. A large annotated corpus for learning natural language inference. In EMNLP.
  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. 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
  5. Jeffrey L Elman. 1990. Finding structure in time. Cognitive science, 14(2):179–211. find
  6. 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
  7. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171. find
  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. find
  9. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find
  10. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. 2020. Transformers are rnns: Fast autoregressive transformers with linear attention. In ICML. find
  11. Eugene Kharitonov and Rahma Chaabouni. 2020. What they do when in doubt: a study of inductive biases in seq2seq learners. arXiv preprint arXiv:2006.14953. — [arXiv:2006.14953](https://arxiv.org/abs/2006.14953) find
  12. Diederik P Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In ICLR.
  13. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A Smith, and Eran Yahav. 2020. A formal hierarchy of rnn architectures. In ACL. find
  14. 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
  15. Jorge Pérez, Javier Marinković, and Pablo Barceló. 2019. On the turing completeness of modern neural network architectures. In ICLR. find
  16. 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. find
  17. Yikang Shen, Shawn Tan, Arian Hosseini, Zhouhan Lin, Alessandro Sordoni, and Aaron C Courville. 2019. Ordered memory. In NeurIPS. find
  18. 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, pages 440–449. find
  19. Natalia Skachkova, Thomas Alexander 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.
  20. 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
  21. 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
  22. Ke M Tran, Arianna Bisazza, and Christof Monz. 2018. The importance of being recurrent for modeling hierarchical structure. In EMNLP. find
  23. 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 NeurIPS.
  24. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. On the practical computational power of finite precision rnns for language recognition. In ACL.
  25. 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. find
  26. Nikita Nangia and Samuel Bowman. 2018. Listops: A diagnostic dataset for latent tree learning. In Proceedings of the 2018 NAACL: Student Research Workshop. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ebrahimi-2020-how-can-self-attention-networks/