Meta-Interpretive Learning of Higher-Order Dyadic Datalog: Predicate Invention Revisited / 1551
Stephen Muggleton, Dianhuan Lin

In recent years Predicate Invention has been under-explored within Inductive Logic Programming due to difficulties in formulating efficient search mechanisms. However, a recent paper demonstrated that both predicate invention and the learning of recursion can be efficiently implemented for regular and context-free grammars, by way of abduction with respect to a meta-interpreter. New predicate symbols are introduced as constants representing existentially quantified higher-order variables. In this paper we generalise the approach of Meta-Interpretive Learning (MIL) to that of learning higher-order dyadic datalog programs. We show that with an infinite signature the higher-order dyadic datalog class H²₂ has universal Turing expressivity though H²₂ is decidable given a finite signature. Additionally we show that Knuth-Bendix ordering of the hypothesis space together with logarithmic clause bounding allows our Dyadic MIL implementation Metagol_D to PAC-learn minimal cardinality H²₂ definitions. This result is consistent with our experiments which indicate that Metagol_D efficiently learns compact H²₂ definitions involving predicate invention for robotic strategies and higher-order concepts in the NELL language learning domain.