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

王榕 等: 基于记忆策略的元解释学习 3485

∑ ∑ ∑ ∑
n n−l k 1 n n k−1 l t 1 n
t
标减少的 MIL 搜索空间比例为 l=1 n k=1 = − 和 k=1 n l=1 = − . 当 t > n 时, 方程的极限接近
∑
∑
n
n
k=1 t k t −1 t −1 k=1 t k t −1 t −1
1
.
mp j+1 −1
t , 在修剪掉所
n
证明: 根据推论 1, 在修剪掉所有常量化目标的情况下, MIL 搜索空间中的程序数目为 ∑ ∑ n−l k
k=1
l=1
有非常量化目标的情况下, MIL 搜索空间中的程序数目为 ∑ n ∑ k−1 l t , 而不修剪情况下的 MIL 搜索空间中的程序
k=1 l=1
n
∑ ∑ n−l k
∑ n k l=1 k=1 t
数目为 t . 因此, 通过修剪常量化目标和非常量化目标减少的 MIL 搜索空间比例分别为 ∑ =
k=1 n t k
k=1
∑ n ∑
1 n k=1 k−1 l t 1 n 1 n 1 ( )
l=1
− 和 ∑ = − . 因此, 当 t > n 时, − 极限值接近于 t = mp j+1 .
t −1 t −1 n t k t −1 t −1 t −1 t −1 t −1
n
n
n
k=1
根据定理 2, 假设内存无限可用, 在程序空间非常大且 mp j+1 > n 的情况下, 提出的剪枝算法理论上可以将程序
1
空间相对于其原始大小减少到 (其中 t = mp j+1 ). 这个理论框架说明了剪枝算法通过最小化冗余计算来提高
t −1
MIL 效率的潜力. 然而, 这种无限内存的假设与实际计算环境有所偏离, 尤其是在 MIL 系统中实施该策略时.
在 MIL 系统中实际应用此剪枝策略面临主要挑战. Prolog 是一种使用搜索和回溯的编程语言, 通常使用固定
的堆栈限制来防止内存溢出, 这与理论模型中假设的内存无限不同. 这个堆栈限制通常设置为默认值, 但也可以自
定义, 是一个重要的操作约束. 因此, 由于操作复杂性和假设与可用内存资源之间的固有不匹配, 剪枝算法的实际
应用可能无法实现理论上的计算时间减少, 导致理论期望与实际性能之间的差异.
另一个导致学习时间实际减少与程序空间理论减少之间差异的重要原因在于剪枝算法本身所需的计算工作.
算法需要大量计算, 包括检查和更新失败目标. 虽然这些步骤对于识别和消除搜索空间中的冗余路径至关重要, 从
而在理论上提高了学习效率, 但它们也增加了 MIL 系统所需的总计算时间. 修剪相关计算所花费的额外时间可能
部分抵消预期的效率提升, 从而导致预期理论效益与实际观察结果之间的差异.

4 算法实现
在本节中, 我们将本文法应用于两个 MIL 系统 Metagol 和 Metagol AI [21] , 从而得到两个新的 MIL 系统 Metagol F
和 Metagol AI_F . 需要注意的是, Metagol 是一个一阶 MIL 系统, 而 Metagol AI [22] 是一个通过引入解释背景知识来支
持抽象 (abstraction) 和发明 (invention) 的高阶 MIL 系统.

4.1 Metagol F
Metagol F 结合 Metagol 与提出的剪枝算法. 它首先尝试通过 (call(Atom)) 将一个 Atom 证明为目标. 一旦失败,
Metagol F 尝试通过原始谓词证明 Atom. 如果再次失败, Metagol F 尝试将目标与一个元规则的头部匹配, 保存元替换,
然后证明主体目标. 在这种情况下, Metagol F 将首先尝试使用现有的假设来证明目标. 如果失败, Metagol F 将尝试创
建一个新的假设 (即新子句). 请注意, 由于一阶程序的表达能力有限, 该程序可能需要多个具有相同头部的子句.
Prolog 允许对同一谓词进行多重定义, 表示在不同场景下的不同实现. 虽然这增强了编程语言的灵活性, 但可能导致
我们的剪枝算法出现冲突, 因为这些子句具有相同的头部但潜在的不同子节点. 为解决这个问题, 我们在一阶系统
Metagol F 中添加了一个额外的修剪条件 (即失败数据库查询). 为了使用新的假设来证明一个 Atom, 我们首先从
Atom 中提取失败信息, 然后检查失败信息是否已经存在于失败数据库中. 如果是这样, Atom 将被立即识别为失败,
MIL 学习器将尝试沿另一分支回溯. 如果不是, 我们将 Atom 的失败信息添加到失败数据库中, 然后尝试证明 Atom.

4.2 Metagol AI_F
Metagol AI_ 引入了解释的背景知识以支持抽象和发明. 例如, 代码 2 中所示的高阶谓词 map/3 有助于学习比一
F
阶谓词更紧凑的程序. 与 Metagol AI_ 相比, 扩展的 Metagol F 系统还尝试将目标与解释的背景知识中的子句头进行匹配.
F
代码 2. 解释的背景知识 map/3.
background(([map, [], [], F]:−[])).
background(([map, [A|As], [B|Bs], F]:−[[F, A, B], [map, As, Bs, F]])).