LMSS @ Cornell Tech: Ryan Cotterell (ETH Zurich)

Learning Machines Seminar Series What: LMSS: Ryan Cotterell (ETH Zurich) When: Thursday, September 18, 1:30-2:45 pm Where: Bloomberg 081, Bloomberg Center, Cornell Tech (map) The series is organized by Associate Professor Yoav Artzi and sponsored by Bloomberg. Pizza will be served at 1:15 p.m. "The Underlying Logic of Language Models" The formal basis of the theory of computation lies in the study of languages, subsets of Σ*, the set of all strings over an alphabet Σ. Models of computation can be taxonomized into the languages they can decide, i.e., which languages a model can determine membership in. For instance, finite-state automata can decide membership in the regular languages. Language models are probabilistic generalizations of formal languages, where the notion of a set is relaxed into one of a probability distribution over Σ*. Recently, language models parameterized using recurrent neural networks, transformers, and state-space models have achieved enormous success in natural language processing. Similar to how theorists have taxonomized models of deterministic computation, researchers have sought to taxonomize the expressivity of language models based on various architectures in terms of the distributions over strings they can represent. This tutorial presents a self-contained overview of the formal methods used to taxonomize the expressivity of language models, which encompass formal languages and automata theory, various forms of formal logic, circuit complexity, and programming languages such as RASP. For example, we illustrate how transformers, under varying assumptions, can be characterized by various fragments of formal logic. BIO Ryan Cotterell has been an assistant professor of computer science at ETH Zürich since 2020. Previously, he was a lecturer at the University of Cambridge. His PhD is from Johns Hopkins University, where he was advised by Jason Eisner. His research interests include natural language processing, computational linguistics, and machine learning. He has published at natural language processing venues (ACL, NAACL, EMNLP) venues as well as machine learning venues (NeurIPS, ICML, ICLR). He has additionally won various paper awards, including the overall best paper at ACL 2017.