caa a22 4500 605478201 CHVBK 20210128100404.0 cr unu---uuuuu 210128e20150701xx s 000 0 eng 10.1007/s10994-014-5471-y doi (NATIONALLICENCE)springer-10.1007/s10994-014-5471-y Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited [Elektronische Daten] [Stephen Muggleton, Dianhuan Lin, Alireza Tamaddoni-Nezhad] 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$$ H 2 2 has universal Turing expressivity though $$H^2_2$$ H 2 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 Metagol $$_{D}$$ D to PAC-learn minimal cardinality $$H^2_2$$ H 2 2 definitions. This result is consistent with our experiments which indicate that Metagol $$_{D}$$ D efficiently learns compact $$H^2_2$$ H 2 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. The Author(s), 2015 Induction nationallicence Abduction nationallicence Meta-interpretation nationallicence Predicate invention nationallicence Learning recursion nationallicence Muggleton Stephen Department of Computing, Imperial College London, London, UK aut Lin Dianhuan Department of Computing, Imperial College London, London, UK aut Tamaddoni-Nezhad Alireza Department of Computing, Imperial College London, London, UK aut Machine Learning Springer US; http://www.springer-ny.com 100/1(2015-07-01), 49-73 0885-6125 100:1<49 2015 100 10994 https://doi.org/10.1007/s10994-014-5471-y text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10994-014-5471-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Muggleton Stephen Department of Computing, Imperial College London, London, UK aut NATIONALLICENCE 700 1- Lin Dianhuan Department of Computing, Imperial College London, London, UK aut NATIONALLICENCE 700 1- Tamaddoni-Nezhad Alireza Department of Computing, Imperial College London, London, UK aut NATIONALLICENCE 773 0- Machine Learning Springer US; http://www.springer-ny.com 100/1(2015-07-01), 49-73 0885-6125 100:1<49 2015 100 10994