Model Theory Seminar - James Freitag - Machine learning and model theory
Speaker: James Freitag (University of Illinois at Chicago)
Title: Machine learning and model theory
Abstract: In the 1990s, Laskowski observed that an important dividing line in model theory (stability/instability) and machine learning (learnability/nonlearnability in the PAC model) are both governed by boundedness of VC dimension. There are many structural dividing lines in model theory, and over the past several years Chase and I have shown that several of these correspond to the dividing line between learnability and nonlearnability in prominent models of machine learning. We then apply techniques from model theory to design new efficient algorithms in these settings. In this talk, we will focus on applications in Angluin's model of query learning, but we will also mention a number of other settings. This talk will not require any background from learning theory, and it will be understandable without any background in model theory.