| 本文已被：浏览 1674次 下载 1865次 |
码上扫一扫！ |
|
|
| 基于记忆策略的元解释学习 |
|
王榕1, 田聪1, 孙军2, 于斌1, 段振华1
|
|
1.西安电子科技大学 计算机科学与技术学院, 陕西 西安 710126;2.School of Computing and Information Systems, Singapore Management University, Singapore 188065, Singapore
|
|
| 摘要: |
| 元解释学习(meta-interpretive learning, MIL)是一种归纳逻辑程序设计(inductive logic programming, ILP)方法, 旨在从一组实例、元规则和其他背景知识中学习一个程序. MIL采用深度优先和失败驱动策略在程序空间中搜索适当的子句以生成程序. 事实上, 这种机制不可避免地引发了对相同目标重复证明的问题. 提出一种剪枝策略, 该策略利用Prolog内置的数据库机制来存储未能达成的目标及其对应的错误信息, 从而有效避免冗余的证明过程. 此后, 这些累积的错误信息能够作为指导, 帮助MIL系统在未来的学习过程中进行优化和调整. 证明剪枝算法的正确性, 并在理论上计算程序空间的缩减比例. 将所提出的方法应用于两个现有的MIL系统Metagol和MetagolAI, 从而产生了两个新的MIL系统MetagolF和MetagolAI_F. 在4个不同任务上的实证结果表明, 所提出的策略可以显著减少学习相同程序的时间消耗. |
| 关键词: 元解释学习 冗余证明 记忆策略 剪枝算法 归纳逻辑程序设计 |
| DOI：10.13328/j.cnki.jos.007346 |
| 分类号: |
| 基金项目:国家自然科学基金(62192734) |
|
| Meta-interpretive Learning Based on Memory Strategy |
|
WANG Rong1, TIAN Cong1, SUN Jun2, YU Bin1, DUAN Zhen-Hua1
|
|
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 MetagolAI, resulting in two new MIL systems MetagolF and MetagolAI_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) |
