Title | ||
---|---|---|
Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited |
Abstract | ||
---|---|---|
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 $$H^2_2$$H22 has universal Turing expressivity though $$H^2_2$$H22 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 Metagol$$_{D}$$D to PAC-learn minimal cardinality $$H^2_2$$H22 definitions. This result is consistent with our experiments which indicate that Metagol$$_{D}$$D efficiently learns compact $$H^2_2$$H22 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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/s10994-014-5471-y | Machine Learning |
Keywords | Field | DocType |
Induction,Abduction,Meta-interpretation,Predicate invention,Learning recursion | Predicate variable,Programming language,Computer science,Cardinality,Decidability,Theoretical computer science,Prolog,Artificial intelligence,Predicate (mathematical logic),Inductive logic programming,Predicate (grammar),Datalog,Machine learning | Conference |
Volume | Issue | ISSN |
100 | 1 | 0885-6125 |
Citations | PageRank | References |
46 | 1.46 | 32 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stephen Muggleton | 1 | 3915 | 619.54 |
Dianhuan Lin | 2 | 86 | 3.52 |