Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited
File(s)
Accepted version
Author(s)
Muggleton, SH
Lin, D
Tamaddoni Nezhad, A
Type
Conference Paper
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 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.
Date Issued
2015-03-12
Date Acceptance
2014-10-10
ISSN
1573-0565
Publisher
Springer Verlag (Germany)
Start Page
49
End Page
73
Journal / Book Title
Machine Learning
Volume
100
Issue
1
Sponsor
Syngenta Ltd
Royal Academy Of Engineering
Grant Number
PO 8700334511
Robert Barrett
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science
Induction
Abduction
Meta-interpretation
Predicate invention
Learning recursion
INDUCTION
0801 Artificial Intelligence And Image Processing
1702 Cognitive Science
Artificial Intelligence & Image Processing
Publication Status
Published