Model Theory and Machine Learning

We study a connection between model theory and machine learning by way of common combinatorial properties. In various settings of machine learning, combinatorial properties of the concept class being learned dictate whether the class is learnable, and if so, how long or how much data is required. In model theory, combinatorial properties can give rise to dividing lines, which create classes of theories in which a structure theory can be developed to varying degrees. Model theory and machine learning share several common combinatorial properties. The first known connection was between PAC learning and NIP theories by way of VC dimension, which led to subsequent interaction between the two fields. In this thesis, we describe a broad connection between stability and several forms of exact learning. The key combinatorial property is Littlestone dimension. This property has been known to both model theory and machine learning for decades (although by a different name in model theory), although it had not been previously pointed out that the connection existed. Finite Littlestone dimension classifies online learning, in which a learner classifies sequentially presented data. Finite Littlestone dimension also classifies stable theories, a model-theoretic class in which a rich structure theory has been developed. We extend this connection to query learning, in which the learner attempts to identify the target concept by guessing it exactly and receiving feedback to its guesses. We also consider compression schemes, where sets must be encoded by a bounded number of its elements and reconstructed by one of several reconstruction functions. The boundary between finite and infinite Littlestone dimension that corresponds to learnability and non-learnability has many similarities to the boundary between finite and infinite VC dimension. In both settings, one can define a counting function called the shatter function, and the relevant dimension controls the growth rate of this function. In particular, the appropriate Sauer-Shelah Lemma gives a polynomial bound if the relevant dimension is finite, while the function is exponential if the relevant dimension is infinite. We develop a framework for proving bounds in a uniform way and apply it in similar settings.