# Top Program Construction and Reduction for polynomial time Meta-Interpretive Learning

arXiv: https://arxiv.org/abs/2101.05050 · HTML: https://mlsanity.com/paper/2101.05050/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 50 references that are in the map.
- First posted on arXiv 13 Jan 2021.

## Builds on (most cited first, 3 of 3)

- [Learning Explanatory Rules from Noisy Data](https://mlsanity.com/paper/1711.04574/) (2017)
- [Learning Relational Representations with Auto-encoding Logic Programs](https://mlsanity.com/paper/1903.12577/) (2019)
- [Exploiting Answer Set Programming with External Sources for Meta-Interpretive Learning](https://mlsanity.com/paper/1805.00068/) (2018)

## Built on by (most cited first, 6 of 6)

- [Inductive logic programming at 30](https://mlsanity.com/paper/2102.10556/) (2021)
- [Learning MDL logic programs from noisy data](https://mlsanity.com/paper/2308.09393/) (2023)
- [Learning logic programs by combining programs](https://mlsanity.com/paper/2206.01614/) (2022)
- [Meta-Interpretive Learning as Metarule Specialisation](https://mlsanity.com/paper/2106.07464/) (2021)
- [Self-Supervised Inductive Logic Programming](https://mlsanity.com/paper/2507.16405/) (2025)
- [Continual learning and refinement of causal models through dynamic predicate invention](https://mlsanity.com/paper/2602.17217/) (2026)

## Abstract (arXiv)

Meta-Interpretive Learners, like most ILP systems, learn by searching for a correct hypothesis in the hypothesis space, the powerset of all constructible clauses. We show how this exponentially-growing search can be replaced by the construction of a Top program: the set of clauses in all correct hypotheses that is itself a correct hypothesis. We give an algorithm for Top program construction and show that it constructs a correct Top program in polynomial time and from a finite number of examples. We implement our algorithm in Prolog as the basis of a new MIL system, Louise, that constructs a Top program and then reduces it by removing redundant clauses. We compare Louise to the state-of-the-art search-based MIL system Metagol in experiments on grid world navigation, graph connectedness and grammar learning datasets and find that Louise improves on Metagol's predictive accuracy when the hypothesis space and the target theory are both large, or when the hypothesis space does not include a correct hypothesis because of "classification noise" in the form of mislabelled examples. When the hypothesis space or the target theory are small, Louise and Metagol perform equally well.