Supervisor

Suitable for

Abstract

Abstract: The goal of program synthesis/induction is to develop machines that can write programs for us. For instance, given examples of unsorted/sorted lists, the goal is to induce a sorting algorithm. This project focuses on inductive logic programming (ILP) [1,2], a form of machine learning based on mathematical logic. Given examples and background knowledge (BK), the goal of ILP is to induce a logic program (a set of logical rules) that with the BK generalises the examples. The goal of this project is to develop techniques to learn programs by debugging faulty programs. The project is based on a generate/test/constrain loop approach to ILP [3], where the constrain stage derives constraints from faulty programs to guide future generate stages. This project will to modify recent work [4] to apply to a Datalog setting, where we can extract more information from faulty programs, such as identifying unsatisfiable pairs of literals. This project is a mix of theory, implementation, and experimentation.

Prerequisites: First-order logic, and preferably logic programming concepts (Prolog and/or Answer Set Programming), or at least an interest to learn about them.

[1] Andrew Cropper, Sebastijan Dumancic: Inductive logic programming at 30: a new introduction. CoRR abs/2008.07912 (2020) [2] Andrew Cropper, Sebastijan Dumancic, Stephen H. Muggleton: Turning 30: New Ideas in Inductive Logic Programming. IJCAI 2020: 4833-4839 [3] Andrew Cropper, Rolf Morel: Learning programs by learning from failures. Mach. Learn. 110(4): 801-856 (2021) [4] Rolf Morel, Andrew Cropper: Learning Logic Programs by Explaining Failures. CoRR abs/2102.12551 (2021)