Title: Learning to program by debugging
Suitability: MSc
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. This project is a mix of theory, implementation, and experimentation.
Prerequisites: First-order logic and logic programming concepts (Prolog/Datalog/Answer Set Programming). Familiarity with Python would also help.
[1] Inductive logic programming at 30: a new introduction. A. Cropper and S. Dumančić.
[2] Turning 30: new ideas in inductive logic programming. A. Cropper, S. Dumančić, and S.H. Muggleton. IJCAI 2020
Title: Learning to play inductive games
Suitability: Part B, Part C, MSc
Abstract: Inductive games, such as Zendo and Eleusis, involve a player using inductive reasoning to discover an unknown set of rules. The goal of this project is to apply state-of-the-art inductive logic programming (ILP) [1,2] to these games. ILP is 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 challenge is to adapt or revise the existing approaches to these games. The work is mostly implementation and experimentation.
Prerequisites: first-order logic and logic programming, ideally Prolog and answer set programming (or an interest in learning about it). Familiarity with Python would also help.
[1] Inductive logic programming at 30: a new introduction. A. Cropper and S. Dumančić.
[2] Turning 30: new ideas in inductive logic programming. A. Cropper, S. Dumančić, and S.H. Muggleton. IJCAI 2020
Title: Efficiently learning efficient programs
Suitability: 4th/MSc
Abstract: Inductive logic programming (ILP) [1] is a form of machine learning based on mathematical logic. Given examples and background knowledge (BK), the goal of ILP is to induce a hypothesis (a set of logical rules) that with the BK generalises (logically entails) the examples. Metaopt [2] is an ILP system that learns efficient logic programs from examples. For instance, given input/output examples of unsorted/sorted lists Metaopt learns quicksort rather than bubblesort. Metaopt works by iteratively finding more efficient hypotheses. However, in the worst-case, Metaopt needs to consider every hypothesis. The goal of this project is to improve Metaopt's search procedure. This work is a mix of theory, implementation, and experimentation.
Prerequisites: logic programming, specifically Prolog. Familiarity with Python would also help.
[1] Inductive logic programming at 30: a new introduction. A. Cropper and S. Dumančić.
[2] Learning efficient logic programs A. Cropper and S.H. Muggleton Machine learning 2019
Title: Learning programs by decomposing examples
Suitability: MSc
Abstract: Inductive logic programming (ILP) [1,2] is a form of machine learning based on mathematical logic. Given examples and background knowledge (BK), the goal of ILP is to induce a hypothesis (a set of logical rules) that with the BK generalises (logically entails) the examples. A major problem in ILP is learning large programs. The goal of this project is to overcome this limitation by exploring methods to decompose problems into smaller problems. The project is a mix of theory, implementation, and experimentation.
Prerequisites: First-order logic, and preferably logic programming concepts (e.g. Prolog), or at least an interest to learn about them. Familiarity with Python would also help.
[1] Inductive logic programming at 30: a new introduction. A. Cropper and S. Dumančić.
[2] Turning 30: new ideas in inductive logic programming. A. Cropper, S. Dumančić, and S.H. Muggleton. IJCAI 2020
Title: What's relevant when automatically building programs?
Suitability: MSc
Abstract: Inductive logic programming (ILP) [1,2] is a form of machine learning based on mathematical logic. Given examples and background knowledge (BK), the goal of ILP is to induce a hypothesis (a set of logical rules) that with the BK generalises (logically entails) the examples. One major problem is deciding appropriate BK. Given too little BK, the problem is unsolvable as there is insufficient information to induce a hypothesis. Given too much BK, the problem becomes intractable as the search space is too large. The goal of this project is to improve ILP by trying to first identify relevant BK. The project is a mix of theory, implementation, and experimentation..
Prerequisites: logic programming, specifically Prolog. Familiarity with Python would also help.
[1] Inductive logic programming at 30: a new introduction. A. Cropper and S. Dumančić.
[2] Turning 30: new ideas in inductive logic programming. A. Cropper, S. Dumančić, and S.H. Muggleton. IJCAI 2020
Title: Learning programs with long chains of reasoning
Suitability: Part C, MSc
Abstract: A major challenge in inductive logic programming (ILP) [1] is learning large programs with deep reasoning (i.e. requires long chains of inference). A recent paper [2] addressed this limitation by replacing traditional entailment approaches in ILP with example-dependent loss functions to help guide the search. The approach is called Brute and uses a best-first search, guided by an example-dependent loss function, to incrementally build programs. The approach has two key limitations (i) it is a brute force approach that tries every possible program, and (ii) it only uses a best-first search. The goal of this project is to address these two limitations by (i) replacing the brute-force approach with a powerful learning from failures [3] search technique, and (ii) using other search algorithms, such as A*.
Prerequisites: Familiarity with Python is very useful. Logic programming (preferably Datalog/Prolog/answer set programming) would help a lot.
[1] Inductive logic programming at 30: a new introduction. A. Cropper and S. Dumančić.
[2] Andrew Cropper, Sebastijan Dumancic: Learning Large Logic Programs By Going Beyond Entailment. IJCAI 2020: 2073-2079
[3] Andrew Cropper, Rolf Morel:
Learning programs by learning from failures. Mach. Learn. 110(4): 801-856 (2021)
Title: Learning to solve Bongard problems
Suitability: Part B, Part C, MSc
Abstract: The Bongard problems are a style of pattern recognition problems. There are always 12 images. Six positive examples and six negative examples. The goal is to induce a rule (or a set of rules) to explain the pattern. See [3] for a light introduction. The goal of this project is to apply state-of-the-art inductive logic programming (ILP) [1,2] to Bongard problems. ILP is 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 challenge is to adapt or revise the existing approaches to these problems. The work is mostly implementation and experimentation.
Prerequisites: logic programming (preferably Datalog/Prolog/answer set programming). Familiarity with Python would also help.
[1] Inductive logic programming at 30: a new introduction. A. Cropper and S. Dumančić.
[2] Turning 30: new ideas in inductive logic programming. A. Cropper, S. Dumančić, and S.H. Muggleton. IJCAI 2020
Title: Learning programs with new objects
Suitability: MSc
Abstract: Scientists often posit the existence of unknown objects to explain empirical observations. However, existing machine learning approaches struggle to perform similar reasoning. To address this limitation, the goal of this project is to develop an inductive logic programming (ILP) system [1,2] that can invent new objects to explain observations. The project is a mix of theory, implementation, and experimentation.
Prerequisites: This project requires knowledge of logic programming, specifically Datalog or answer set programming.
[1] Inductive logic programming at 30: a new introduction. A. Cropper and S. Dumančić.
[2] Turning 30: new ideas in inductive logic programming. A. Cropper, S. Dumančić, and S.H. Muggleton. IJCAI 2020
Title: Optimal inverse entailment
Suitability: MSc
Abstract: Inductive logic programming (ILP) [1,2] is 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. Inverse entailment (IE) [3] is a powerful ILP technique that greatly reduces the hypothesis search complexity. However, IE approaches (i) learn overly large and complex programs, (ii) struggle to learn recursive programs, and (iii) require several parameters from the user, which makes them cumbersome to use. The goal of this project is to develop provably optimal IE techniques. The idea is to harness the latest advances in SAT and ASP solvers. The work is a mix of theory, implementation, and experimentation.
Prerequisites: This project requires knowledge of logic programming, specifically both answer set programming and Prolog.