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

3478 软件学报 2025 年第 36 卷第 8 期

[1]
作为符号人工智能 (AI) 的一个分支, 归纳逻辑程序设计 (inductive logic programming, ILP) 专注于从实例和背
景知识中归纳构建逻辑程序 (即一阶子句理论). ILP 系统使用语言偏误来定义程序空间. 因此, 学习程序的过程可以
视为在程序空间内的搜索. Muggleton 等人 [2] 在 2014 年引入了元解释学习 (meta-interpretive learning, MIL), 这是一
[3]
[6]
[4]
种新的 ILP 方法, 相较于早期的 ILP 系统如 FOIL 、Progol 、TILDE 和 [5] Aleph 标志着显著的进步. 其主要区分
在于支持递归概念和谓词发明的学习, 使其与前身系统有所不同.
然而, MIL 通过引入元规则来限制可学习程序的形式, 从而更精确地定义了程序空间. 在 MIL 学习者中, 该方法
采用迭代加深深度优先搜索 (iterative deepening depth-first search, IDDFS) 来导航这个定义好的程序空间. 该方法虽
然创新, 但在搜索庞大的程序空间时带来了挑战, 使得 MIL 变慢且容易生成冗余证明, 这是其固有学习机制导致的结
果. IDDFS 是一种搜索方法, 它不断执行深度限制的深度优先搜索, 逐步增加深度限制, 直到找到目标. 具体来说, MIL
系统通过逐渐增加子句数量来搜索程序空间. 因此, MIL 程序的搜索空间随着程序子句数量的增加呈指数增长. 这种
指数扩展不仅导致巨大的搜索空间, 还由于涉及的计算工作量巨大和大量冗余计算, 严重阻碍了 MIL 的实际应用.
为了减轻元解释学习中广泛搜索空间的挑战, 研究人员采用了几种策略来提高 MIL 的搜索效率. 这些改进包
括分层偏误重构 [7] 、通过减少候选解决方案的元规则集来最小化 [8,9] 、引入多态和精炼类型检查以显著提高元解
释学习的效率 [10] 、修订实例空间和假设空间以提高效率 [11] 以及与神经网络结合 [12,13] . 然而, 这些方法并未从根本
上改变 MIL 的学习机制. 因此, 由迭代深度优先搜索产生的冗余证据问题仍未得到解决. 随着程序子句数量的增
加, 这个问题变得更加严重, 并可能导致系统崩溃, 因为计算需求呈指数增长. 通过引入基于记忆策略的剪枝算法,
我们旨在解决 MIL 搜索效率的挑战. 该算法通过减少冗余证明显著提高了 MIL 系统的计算效率, 从而最小化计
算资源的浪费并节省能源. 这一改进使系统能够更有效地处理复杂的学习任务.
MIL 采用由失败驱动的深度优先遍历搜索. 这种方法将 SLD-树中从给定 Goal 开始的所有路径标记为失败分
支, 直到发现一个可行的程序. 基于此基础, 我们在 MIL 中集成了基于记忆策略的剪枝算法. 该算法旨在捕捉和利
用在学习过程中遇到的目标的错误信息. 借此, 我们在 Prolog 中实现了一个动态数据库, 用于归档所有目标及其
相关的错误信息. 一旦某个目标被认为失败, 那么在尝试证明新的 Goal 之前, 系统会首先评估该 Goal 是否已被记
录在数据库中. 如果发现匹配, 则 MIL 学习者放弃重新评估已知的错误目标, 而是立即进行回溯. 如果该目标是新
的或以前未遇到的, 则将其连同其错误数据一起添加到数据库中以供将来参考. 这确保了在学习过程的范围内, 每
个 Goal 最多只进行一次证明, 从而显著简化了系统的效率.
本文的主要贡献如下.
我们通过一个基于内存的剪枝算法, 标记出一个直接解决方案来提高 MIL 的效率, 从而识别并解决了 MIL
的冗余问题, 这是由其 IDDFS 策略引起的. 我们介绍了剪枝算法并证明了其正确性和有效性, 展示了程序空间在
理论上的减少. 通过将该算法应用于现有的 MIL 系统, 我们展示了其实际价值, 并获得了两个更新的 MIL 系统
(Metagol F 和 Metagol AI_F ), 我们的实验证实了它在减少学习时间方面的有效性.
本文第 1 节介绍元解释学习的预备知识和框架. 第 2 节使用一个激励性的例子来说明 MIL 中的冗余证明问
题. 第 3 节介绍针对 MIL 的修剪算法并证明该方法的正确性. 第 4 节介绍两个改进的 MIL 系统——Metagol F 和
Metagol AI_F . 第 5 节给出了 4 个学习任务的实验结果. 第 6 节回顾相关工作. 最后, 第 7 节总结本文并概述未来的
工作方向.

1 基础知识

本节首先介绍本文使用的逻辑符号以及 MIL 的理论框架.

1.1 逻辑学符号

我们考虑一个具有固定词汇的谓词符号 Π、函数符号 F 和变量 V 的一阶语言. T (F ,V) 表示使用来自 F 的
θ = {v 1 7→ t 1 ,...,v n 7→ t n }, 可以得到
符号和来自 V 的变量构造的项的集合. 通过在一个 n 元谓词 p/n ∈ Π 上应用替换
θ
形式为 p(t 1 ,...,t n ) 的原子, 其中 t i ∈ T (F ,V), 并且 是对 i = 1,...,n 的变量 v i 的项 t i 的赋值. 所有谓词符号的集合
称为谓词签名. 对于一个原子 A, A 及其否定 ¬A 都是文字. 一条子句由有限集合 (可能为空) 的文字表示, 记作