Page 54 - 《软件学报》2025年第8期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(8):3477−3493 [doi: 10.13328/j.cnki.jos.007346] [CSTR: 32375.14.jos.007346] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
基于记忆策略的元解释学习

王 榕 1 , 田 聪 1 , 孙 军 2 , 于 斌 1 , 段振华 1

1
(西安电子科技大学 计算机科学与技术学院, 陕西 西安 710126)
2
(School of Computing and Information Systems, Singapore Management University, Singapore 188065, Singapore)
通信作者: 王榕, E-mail: rwang_bily@stu.xidian.edu.cn

摘 要: 元解释学习 (meta-interpretive learning, MIL) 是一种归纳逻辑程序设计 (inductive logic programming, ILP)
方法, 旨在从一组实例、元规则和其他背景知识中学习一个程序. MIL 采用深度优先和失败驱动策略在程序空间
中搜索适当的子句以生成程序. 事实上, 这种机制不可避免地引发了对相同目标重复证明的问题. 提出一种剪枝策
略, 该策略利用 Prolog 内置的数据库机制来存储未能达成的目标及其对应的错误信息, 从而有效避免冗余的证明
过程. 此后, 这些累积的错误信息能够作为指导, 帮助 MIL 系统在未来的学习过程中进行优化和调整. 证明剪枝算
法的正确性, 并在理论上计算程序空间的缩减比例. 将所提出的方法应用于两个现有的 MIL 系统 Metagol 和
Metagol AI , 从而产生了两个新的 MIL 系统 Metagol F 和 Metagol AI_F . 在 4 个不同任务上的实证结果表明, 所提出的
策略可以显著减少学习相同程序的时间消耗.
关键词: 元解释学习; 冗余证明; 记忆策略; 剪枝算法; 归纳逻辑程序设计
中图法分类号: TP18

中文引用格式: 王榕, 田聪, 孙军, 于斌, 段振华. 基于记忆策略的元解释学习. 软件学报, 2025, 36(8): 3477–3493. http://www.jos.
org.cn/1000-9825/7346.htm
英文引用格式: Wang R, Tian C, Sun J, Yu B, Duan ZH. Meta-interpretive Learning Based on Memory Strategy. Ruan Jian Xue
Bao/Journal of Software, 2025, 36(8): 3477–3493 (in Chinese). http://www.jos.org.cn/1000-9825/7346.htm

Meta-interpretive Learning Based on Memory Strategy
1
1
1
2
WANG Rong , TIAN Cong , SUN Jun , YU Bin , DUAN Zhen-Hua 1
1
(School of Computer Science and Technology, Xidian University, Xi’an 710126, China)
2
(School of Computing and Information Systems, Singapore Management University, Singapore 188065, Singapore)
Abstract: Meta-interpretive learning (MIL) is an approach within inductive logic programming (ILP) that aims to learn a program from a
set of examples, metarules, and other background knowledge. MIL uses a depth-first, failure-driven strategy to explore appropriate clauses
in the program space to generate programs. This mechanism, however, inevitably leads to the problem of repeated proofs for the same
goals. A pruning strategy is proposed, utilizing Prolog’s built-in database mechanism to store failed goals and their corresponding error
information, effectively preventing redundant proof processes. The accumulated error information serves as a guide to help the MIL system
optimize and adjust its learning process in future iterations. The correctness of the pruning algorithm is proved, and the reduction in
program space is calculated theoretically. The proposed method is applied to two existing MIL systems, Metagol and Metagol AI , resulting
in two new MIL systems Metagol F and Metagol AI_F . Empirical results from four different tasks demonstrate that the proposed strategy
significantly reduces the time required to learn the same programs.
Key words: meta-interpretive learning (MIL); redundant proof; memory strategy; pruning algorithm; inductive logic programming (ILP)

* 基金项目: 国家自然科学基金 (62192734)
本文由“形式化方法与应用”专题特约编辑陈明帅研究员、田聪教授、熊英飞副教授推荐.
收稿时间: 2024-08-25; 修改时间: 2024-10-14; 采用时间: 2024-11-26; jos 在线出版时间: 2024-12-10
CNKI 网络首发时间: 2025-04-21