Learning higher-order logic programs
Learning higher-order logic programs
复制标题
DOI：
10.1007/s10994-019-05862-7
复制
发表时间：
2019-12-03
期刊：
影响因子：
7.5
通讯作者：
Muggleton, Stephen
中科院分区：
文献类型：
--
作者：
Cropper, Andrew;Morel, Rolf;Muggleton, Stephen
归纳逻辑编程的一个关键特征是它学习一阶程序的能力，从本质上讲，一阶程序比命题程序更有表现力。在本文中，我们介绍了学习高阶程序的技巧。具体地说，我们扩展了元解释学习(MIL)，通过允许将高阶定义用作背景知识来支持学习高阶程序。我们的理论结果表明，学习高阶程序而不是一阶程序可以降低表示程序所需的文本复杂性，这反过来又降低了假设空间的大小和样本复杂性。我们在两个新的MIL系统中实现了我们的想法：Prolog系统Metagol(HO)和ASP系统HEXMILho。这两个系统都支持学习高阶程序和高阶谓词发明，如为MAP/3创造函数和为Filter/3创造条件。我们在四个领域(机器人策略、棋局、列表转换和字符串解密)上进行了实验，比较了学习一阶程序和高阶程序。我们的实验结果支持了我们的理论主张，并表明与学习一阶程序相比，学习高阶程序可以显著提高预测精度并减少学习时间。
A key feature of inductive logic programming is its ability to learn first-order programs, which are intrinsically more expressive than propositional programs. In this paper, we introduce techniques to learn higher-order programs. Specifically, we extend meta-interpretive learning (MIL) to support learning higher-order programs by allowing for higher-order definitions to be used as background knowledge. Our theoretical results show that learning higher-order programs, rather than first-order programs, can reduce the textual complexity required to express programs, which in turn reduces the size of the hypothesis space and sample complexity. We implement our idea in two new MIL systems: the Prolog system Metagol(ho) and the ASP system HEXMILho. Both systems support learning higher-order programs and higher-order predicate invention, such as inventing functions for map/3 and conditions for filter/3. We conduct experiments on four domains (robot strategies, chess playing, list transformations, and string decryption) that compare learning first-order and higher-order programs. Our experimental results support our theoretical claims and show that, compared to learning first-order programs, learning higher-order programs can significantly improve predictive accuracies and reduce learning times.