Light PhD Seminar: Measuring complexity: from learning theory to mathematical logic

Title: Measuring complexity: from learning theory to mathematical logic

Abstract: 

What does the term "learning" in "machine learning" mean beyond vague anthropomorphic analogies? Learning theory addresses this question by developing a rigorous mathematical framework that defines learning and characterizes the learnability of many kinds of concept classes. This approach not only provides a unifying language and theoretical foundations to several machine learning techniques, but also guides the development of novel learning algorithms.

In this talk, we introduce the Probably Approximately Correct (PAC) learning framework and demonstrate that the PAC-learnability of concept classes is characterized by their Vapnik-Chervonenkis (VC) dimension, a combinatorial complexity measure. In a second part, we reveal how similar combinatorial tools were independently developed in model theory to describe the complexity of first-order theories. Leveraging this shared toolbox, we close the talk by pointing out surprising connections between the fields of learning theory and mathematical logic.

The talk doesn't assume any previous knowledge on learning theory or model theory.