Top Program Construction and Reduction for polynomial time
  Meta-Interpretive Learning
  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.
