Learning efficient logic programs
Learning efficient logic programs
复制标题
学习高效的逻辑程序
DOI：
10.1007/s10994-018-5712-6
复制
发表时间：
2018
期刊：
影响因子：
7.5
通讯作者：
Cropper A
中科院分区：
文献类型：
--
作者：
Cropper A
当机器从数据中学习程序时，我们理想地希望学习高效而不是低效的程序。然而，现有的归纳逻辑编程（ILP）技术不能区分程序的效率，例如置换排序（n！）合并排序为了解决这个问题，我们引入Metaopt，迭代学习成本较低的逻辑程序的ILP系统，每一次进一步限制的假设空间。我们证明了足够大数量的例子，Metaopt收敛于最小成本的程序，我们的实验表明，在实践中只需要少量的例子。为了学习最小的时间复杂度的程序，包括非确定性的程序，我们引入了一个成本函数costtree，它测量当一个程序被给定一个目标时搜索的SLD树的大小。我们在编程难题、机器人策略和现实世界的字符串转换问题上的实验表明，Metaopt学习最小成本程序。据我们所知，Metaopt是第一种机器学习方法，在给定足够数量的训练示例的情况下，可以保证学习最小成本逻辑程序，包括最小时间复杂度程序。
When machine learning programs from data, we ideally want to learn efficient rather than inefficient programs. However, existing inductive logic programming (ILP) techniques cannot distinguish between the efficiencies of programs, such as permutation sort (n!) and merge sort. To address this limitation, we introduce Metaopt, an ILP system which iteratively learns lower cost logic programs, each time further restricting the hypothesis space. We prove that given sufficiently large numbers of examples, Metaopt converges on minimal cost programs, and our experiments show that in practice only small numbers of examples are needed. To learn minimal time-complexity programs, including non-deterministic programs, we introduce a cost function calledtree costwhich measures the size of the SLD-tree searched when a program is given a goal. Our experiments on programming puzzles, robot strategies, and real-world string transformation problems show that Metaopt learns minimal cost programs. To our knowledge, Metaopt is the first machine learning approach that, given sufficient numbers of training examples, is guaranteed to learn minimal cost logic programs, including minimal time-complexity programs.
登录
查看更多内容
DOI：
--
发表时间：
2016
期刊：
International Joint Conference on Artificial Intelligence
影响因子：
--
作者：
Andrew Cropper;S. Muggleton
通讯作者：
S. Muggleton
DOI：
10.1007/978-3-662-44923-3
发表时间：
2014-09
期刊：
--
影响因子：
--
作者：
Gerson Zaverucha;V. S. Costa;A. Paes
通讯作者：
Gerson Zaverucha;V. S. Costa;A. Paes
关于归纳概括的进一步说明
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
G. Plotkin
通讯作者：
G. Plotkin
影响因子：
7.5
作者：
R. Otero
通讯作者：
R. Otero
DOI：
10.1016/0004-3702(83)90009-7
发表时间：
1983
期刊：
Artif. Intell.
影响因子：
--
作者：
E. Kant
通讯作者：
E. Kant