4.7 Article

Top program construction and reduction for polynomial time Meta-Interpretive learning

Journal

MACHINE LEARNING
Volume 110, Issue 4, Pages 755-778

Publisher

SPRINGER
DOI: 10.1007/s10994-020-05945-w

Keywords

Inductive logic programming; Meta interpretive learning; Machine learning; Top program construction

Funding

  1. UK's EPSRC
  2. UK's EPSRC Human-Like Computing Network
  3. EPSRC [EP/P006272/1] Funding Source: UKRI

Ask authors/readers for more resources

The paper introduces a method for Meta-Interpretive Learners to construct a Top program instead of searching for correct hypotheses, showing that the algorithm can construct a correct Top program in polynomial time and improve predictive accuracy in large hypothesis spaces or in the presence of classification noise.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available