Learning Symbolic Concepts and Domain-specific Languages

Event Date: March 4, 2024
Location: 1:30 pm
Contact Name: PGSC 105
Priority: No
School or Program: Electrical and Computer Engineering
College Calendar: Hide
Paul Krogmeier
University of Illinois Urbana-Champaign


Symbolic languages are fundamental to computing: they help us understand and orchestrate unfamiliar concepts and computations in complex domains. Symbolic learning aims to synthesize logical formulas and programs expressed in these languages given a few examples, with a plethora of applications in automation for programming, testing, and verification of computer systems. Effective algorithms for symbolic learning use domain- and language-specific heuristics, which makes them hard to build and limits application of symbolic learning in new domains. 
In this talk I will discuss my work on foundations of symbolic learning, which connects language semantics to uniform learning algorithms via an algorithmic meta-theorem. With this connection, I will explain how a fundamental technique based on version space algebra, as realized in program synthesizers from industry, e.g., Microsoft Excel's FlashFill, is in fact an instance of a deeper concept related to tree automata. By simply writing specialized language interpreters, we are able to effectively describe learning algorithms and simultaneously prove new theorems about the decidability of learning problems for several well-studied symbolic languages in computer science. I will discuss how this connection between interpreters and algorithms uncovers a path to efficient specification and design of symbolic learning algorithms for new domains. I will also discuss my work on learning logical formulas, and its application to robust visual discrimination and automatic discovery of axiomatizations. 
Finally, I will discuss my work on learning domain-specific languages (DSLs) for few-shot learning, which explores the problem of constructing DSLs that adequately balance expressive power, succinctness, and tractability for effective learning. I will conclude with some ideas for practically realizing an effective translation from interpreters to learning algorithms and some interesting applications of symbolic learning to music, math, and machine learning. 


Paul Krogmeier is a PhD candidate at the University of Illinois Urbana-Champaign. Paul's research focuses on algorithms for symbolic learning and the problem of learning symbolic languages 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. 


Xiaokang Qiu, xkqiu@purdue.edu

2024-03-04 08:00:00 2024-03-04 17:00:00 America/Indiana/Indianapolis Learning Symbolic Concepts and Domain-specific Languages Paul Krogmeier University of Illinois Urbana-Champaign 1:30 pm