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.
Sophie Hao is a Faculty Fellow (i.e., a postdoc without a supervisor) in Data Science at New York University. Her research is on interpretability and explanability for natural language processing, with the aim of understanding what it means for a deep neural network to be ‘interpreted by’ or ‘explained to’ a human audience. She recently completed her PhD in Linguistics and Computer Science with Prof. Robert Frank and Prof. Dana Angluin at Yale University.