HAIL: Hybrid Abductive-Inductive Learning

Abstract

The learning system Progol5 and the inference method of Bottom Generalisation are firmly established within Inductive Logic Programming (ILP). But despite their success, these approaches are known to be incomplete, and are restricted to finding hypotheses within the semantics of Plotkin's relative subsumption. This paper reveals a previously unsuspected incompleteness of Progol5 with respect to Bottom Generalisation and proposes a new approach that is shown to overcome this particular incompleteness and to further generalise Progol. This new approach is called Hybrid Abductive Inductive Learning (HAIL) because it integrates the ILP principles of Progol5 with Abductive Logic Programming (ALP). A proof procedure is described that, unlike Progol5, is able to hypothesise multiple clauses in response to a single positive example and finds hypotheses outside Plotkin's relative subsumption. A semantics is presented which extends that of Bottom Generalisation and includes the hypotheses constructed by HAIL