Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited
Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited
复制标题
DOI：
10.1007/s10994-014-5471-y
复制
发表时间：
2015-07-01
期刊：
影响因子：
7.5
通讯作者：
Tamaddoni-Nezhad, Alireza
中科院分区：
文献类型：
--
作者：
Muggleton, Stephen H.;Lin, Dianhuan;Tamaddoni-Nezhad, Alireza
自 20 世纪 90 年代末以来，由于难以制定有效的搜索机制，谓词发明在归纳逻辑编程中尚未得到充分探索。然而，最近的一篇论文表明，通过相对于作为学习引擎的修改后的 Prolog 元解释器的元逻辑替换，谓词发明和递归学习都可以有效地实现常规语法和上下文无关语法。引入新的谓词符号作为表示存在量化的高阶变量的常量。该方法表明谓词发明可以被视为高阶逻辑推理的一种形式。在本文中，我们将元解释学习（MIL）的方法概括为学习高阶二元数据记录程序的方法。我们证明，具有无限签名的高阶二元数据记录类具有通用图灵表达性，尽管在给定有限签名的情况下是可判定的。此外，我们还表明，假设空间的 Knuth-Bendix 排序与对数子句边界一起允许我们的 MIL 实现 Metagol 来 PAC 学习最小基数定义。这个结果与我们的实验一致，表明 Metagol 有效地学习了紧凑的定义，涉及用于学习机器人策略、东西方训练挑战和 NELL 的谓词发明。此外，在 NELL 语言学习领域还学习了更高阶的概念。本文中描述的 Metagol 代码和数据集已在网站上公开提供，以便复制本文中的结果。
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 has universal Turing expressivity though 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 to PAC-learn minimal cardinality definitions. This result is consistent with our experiments which indicate that Metagol efficiently learns compact 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.