Learning Logically Defined Hypotheses - Martin Grohe, RWTH Aachen University

Explore a declarative framework for machine learning in this 45-minute lecture by Martin Grohe from RWTH Aachen University, presented at the Alan Turing Institute. Dive into the concept of logically defined hypotheses, examining both positive and negative learnability results for hypothesis classes defined in first-order and monadic second-order logic. Discover how this theoretical framework could potentially serve as a foundation for declarative approaches to machine learning in logic-oriented fields such as database systems and automated verification. Gain insights into the combination of formal reasoning offered by logic and the power of learning, as part of a workshop aimed at bringing together expertise from various areas to explore the opportunities presented by this intersection.

Intro
Outline
Declarative ML
Idea of Model-Theoretic Framework
Example 1 (cont d)
Example 2
Formal Framework For simplicity, we only consider Boolean classification problems
Learning as Minimisation
Remarks on VC-Dimension and PAC-Learning
Computation Model
Complexity Considerations
Proof
Strings as Background Structures
Learning with Local Access
Monadic Second-Order Logic
Building an Index
Factorisation Trees as Index Data Structures
Learning MSO
Pre-Processing
Learning Phase 1
Open Problems