In this episode, we talk to Shunyu Yao about recent insights into how transformers can represent hierarchical structure in language. Bounded-depth hierarchical structure is thought to be a key feature of natural languages, motivating Shunyu and his coauthors to show that transformers can efficiently represent bounded-depth Dyck languages, which can be thought of as a formal model of the structure of natural languages. We went on to discuss some of the intuitive ideas that emerge from the proofs, connections to RNNs, and insights about positional encodings that may have practical implications. More broadly, we also touched on the role of formal languages and other theoretical tools in modern NLP.

Papers discussed in this episode:

- Self-Attention Networks Can Process Bounded Hierarchical Languages (https://arxiv.org/abs/2105.11115)
- Theoretical Limitations of Self-Attention in Neural Sequence Models (https://arxiv.org/abs/1906.06755)
- RNNs can generate bounded hierarchical languages with optimal memory (https://arxiv.org/abs/2010.07515)
- On the Practical Computational Power of Finite Precision RNNs for Language Recognition (https://arxiv.org/abs/1805.04908)

Shunyu Yao's webpage: https://ysymyth.github.io/

The hosts for this episode are William Merrill and Matt Gardner.

129 - Transformers and Hierarchical Structure, with Shunyu Yao

**The podcast is currently on hiatus. For more active NLP content, check out the Holistic Intelligence Podcast linked below.**

Welcome to the NLP highlights podcast, where we invite researchers to talk about their work in various areas in natural language processing. All views expressed belong to the hosts/guests, and do not represent their employers.

129 - Transformers and Hierarchical Structure, with Shunyu Yao

NLP Highlights