Lunch at 12:30pm, (in-person) talk at 1pm, in 148 Fitzpatrick

Title: Understanding RNNs and Transformers using Formal Languages

Abstract: The success of deep neural networks in natural language processing has sparked an interest in understanding how it is that large networks solve the tasks that they are trained to solve. According to Doshi-Velez and Kim (2017), “the need for interpretability stems from an incompleteness in the problem formulation”—our lack of formal understanding of natural language makes it difficult to verify in a systematic way that deep networks behave and generalize as intended. In this talk, I show how formal language theory can help us understand neural networks by circumventing the issue of incompleteness. To that end, I present three case studies in which formal languages offer natural notions of generalization in neural networks. First, I analyze the expressive power of hard-attention transformers (Hahn, 2020), showing that this formalized version of the transformer only accepts formal languages in the complexity class AC^0. Next, I present experiments done on the neural stack architecture (Grefenstette et al., 2015), and show that it can learn to behave like a pushdown automaton, but only in limited cases. Finally, I show how LSTMs designed to imitate automata can serve as controlled test cases for black-box interpretability methods.

Bio: Sophie Hao is a faculty fellow at NYU, and she recently completed her PhD at Yale University. Her research is on interpretability and explainability for NLP, with the aim of understanding what it means for a deep neural network to be “interpreted by” or “explained to” a human audience.