Since the late 1990s 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 metalogical
substitutions with respect to a modified Prolog meta-interpreter which acts as the learning
engine. New predicate symbols are introduced as constants representing existentially
quantified higher-order variables. The approach demonstrates that predicate invention can be
treated as a form of higher-order logical reasoning. 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 H2
2 has universal
Turing expressivity though H2
2 is decidable given a finite signature. Additionally we
show that Knuth–Bendix ordering of the hypothesis space together with logarithmic clause
bounding allows our MIL implementation MetagolD to PAC-learn minimal cardinality H2
2
definitions. This result is consistent with our experiments which indicate that MetagolD
efficiently learns compact H2
2 definitions involving predicate invention for learning robotic
strategies, the East–West train challenge and NELL. Additionally higher-order concepts were
learned in the NELL language learning domain. The Metagol code and datasets described in
this paper have been made publicly available on a website to allow reproduction of results in
this paper.