Events Calendar

Speaker

Paul Krogmeier

Abstract

Symbolic languages are fundamental to computing: they help us understand and orchestrate unfamiliar computations in complex domains. Symbolic learning aims to automatically discover concepts expressed in these languages, e.g., formulas or programs, given a few examples, with many applications in programming, testing, and verification of computer systems. Algorithms for symbolic learning are currently ad hoc and come with no guarantees of convergence, and commonly involve manual design of bespoke domain-specific languages (DSLs) and heuristic search techniques that lack theoretical guarantees.

In the first part of my talk, I describe my work on new foundations for symbolic learning, which connects language semantics to uniform learning algorithms via an algorithmic meta-theorem. We show that, by writing specialized language interpreters, we can effectively derive learning algorithms and simultaneously prove new theorems about the decidability of learning. With this connection, I explain how a fundamental technique based on version space algebra, as realized in Excel’s FlashFill, is in fact an instance of a deeper concept related to tree automata. I explain how this connection between interpreters and algorithms uncovers a path to efficient specification and design of symbolic learning algorithms for new domains. I also describe my work on new applications of symbolic learning, including visual discrimination and automated discovery of axioms. In the second part of my talk, I turn to the problem of automating the design of DSLs themselves. I show a meta-theorem on effectively synthesizing DSLs for few-shot learning, where DSL discovery hinges on tuning the DSL's expressive power, succinctly expressing useful domain concepts, and ensuring tractability of learning. Symbolic learning and DSL synthesis together enable systematic automation of language design for many new applications.

Finally, I conclude with plans for collaborations in machine learning, with a focus on integrating symbolic world knowledge and constraints into learned models as well as the design of general-purpose synthesis algorithms with formal guarantees that scale by leveraging the capabilities of large language models.

Bio

Paul Krogmeier is a PhD candidate at the University of Illinois Urbana-Champaign. Paul’s research is focused on algorithms for symbolic learning and the problem of learning symbolic languages and abstractions that capture specific domains. His work on symbolic learning was recognized with distinguished paper awards at POPL 2022 and OOPSLA 2023. He has also published in the areas of program synthesis, program verification, and differential privacy.