---
title: "Meta-Interpretive Learning of Higher-Order Dyadic Datalog: Predicate Invention revisited"
authors:
  - "Stephen H. Muggleton"
  - "Dianhuan Lin"
doi: ""
url: "https://ijcai.org/proceedings/2013/231"
pdf: "https://ijcai.org/proceedings/2013/0231.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "1551-1556"
track: ""
keywords:
---

# Meta-Interpretive Learning of Higher-Order Dyadic Datalog: Predicate Invention revisited

Stephen H. Muggleton, Dianhuan Lin

*Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, pages 1551-1556.

## Abstract

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 H22 has universal Turing expressivity though 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 Dyadic MIL implementation MetagolD to PAC-learn minimal cardinality H22 definitions. This result is consistent with our experiments which indicate that MetagolD efficiently learns compact H22 definitions involving predicate invention for robotic strategies and higher-order concepts in the NELL language learning domain.