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

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

…
:−f2([1,1,0,−1,−1],Var).
:−f2([1,1,0,−1,−1],Var),
f2(Var,[−1,−1,0,1,1]).
:−f1([1,1,0,−1,−1],Var), :−f1([1,1,0,−1,−1],Var).
:−f1(Var,[−1,−1,0,1,1]).
:−f1(Var,[−1,−1,0,1,1]).
:−f2(Var,[−1,−1,0,1,1]).
…
?−f([1,1,0,−1,−1],
[−1,−1,0,1,1]). :r2([1,1,0,−1,−1],[1,1,−1,−1,0]).
:−r2([1,1,0,−1,−1],[1,1,−1,−1,0]), :−r1([1,1,−1,−1,0],Var),
f2([1,1,−1,−1,0],[−1,−1,0,1,1]). r1(Var,[−1,−1,0,1,1]).
…
:−l1([1,1,−1,−1,0],
[1,1,−1,0,−1]). :−r1([1,1,−1,0,−1]),[1,1,−1,−1,0]).
:−f2([1,1,−1,−1,0],[−1,−1,0,1,1]).
:−r1([1,1,−1,0,−1],[1,1,−1,−1,0]),
r1([1,1,−1,−1,0],Var). :−r1([1,1,−1,−1,0],Var).
:−l1([1,1,−1,−1,0],[1,1,−1,0,−1]),
f1([1,1,−1,0,−1],[−1,−1,0,1,1]).
:−f1([1,1,−1,0,−1], :−l2([1,1,−1,0,−1]),[1,0,−1,1,−1]).
[−1,−1,0,1,1]).
:−l2([1,1,−1,0,−1],[1,0,−1,1,−1]),
l2([1,0,−1,1,−1],Var).
:−l2([1,0,−1,1,−1]),Var).

…
f ([1,1,0,−1,−1],[−1,−1,0,1,1]) 的 SLD-树的示意图
图 4 当 N = 3, M = 2 时, 目标

… …
… :−f2([1,1,0,−1,−1],Var).
:−f1([1,1,0,−1,−1],Var).
?−f3([1,1,0,−1,−1],Var).
:−f1([1,1,0,−1,−1],Var),
?−f([1,1,0,−1,−1],
[−1,−1,0,1,1]). :−f3([1,1,0,−1,−1],Var), :−f2([1,1,0,−1,−1],Var), f1(Var,[−1,−1,0,1,1])
f3(Var,[−1,−1,0,1,1]). f2(Var,Var).
:−f1(Var,[−1,−1,0,1,1]).
:r1(Var, [−1,−1,0,1,1]).
:−f2(Var,Var).
…
… …
…
图 5 当 N = 4, M = 3 时, 目标 f ([1,1,0,−1,−1],[−1,−1,0,1,1]) 的 SLD-树示意图

3 元解释学习剪枝算法

如算法 1 所示, 为了在元解释学习 (meta-interpretive learning, MIL) 中实现剪枝, 我们的方法利用了保存失败
目标能划定搜索空间中不可行区域的洞察. 通过记录这些失败, 算法避免了冗余探索, 而是专注于有前景的区域,
从而提高搜索效率. 这个原理是我们基于记忆的剪枝算法开发的基础, 通过将 SLD-树中的节点分类为常量化目标
和非常量化目标, 为更高效的 MIL 过程奠定了基础.
算法 1. MIL 剪枝算法.

N
输入: 实例集 E, 背景知识 BK, 元规则集 MS , 数据库 DB, 谓词集 Sig, 最大子句数 , 最大发明谓词数 M = N −1;
输出: 程序 H.