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

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

与之相比, 本文直接优化 MIL 算法, 通过剪枝减少冗余证明, 以提升复杂任务中的执行效率. 表 12 简要比较了
Aleph、Progol、Metagol、Popper 和 XHAIL 等常见 ILP 系统的核心特性.

表 12 一些 ILP 系统的简化比较

特性 Aleph Progol Metagol Popper XHAIL
假设 一般 确定性 确定性 确定性 确定性
语言偏误 模型 Datalog 元规则 声明 声明
谓词构造 否 否 是 否 否
递归 部分 是 是 是 是
最优 否 否 是 是 否
假设约束 是 是 否 是 是

7 结论与未来工作

本文揭示了元解释学习的一个固有缺陷, 即冗余证明. 在此基础上, 引入了一种基于记忆的裁剪算法来裁剪
MIL 中的冗余证明, 以提高学习效率, 包括缩短学习时间和生成完全相同的程序. 我们还提供了算法的实验评估和
理论分析. 从实验结果可以看出, 程序空间越大, 学习时间减少越显著. 本文的观察结果揭示了在较大程序搜索空
间应用裁剪算法时, 其有效性的显著提升. 这种改进在相同堆栈限制条件下表现为两个重要方面. 首先, 程序搜索
空间的增加会导致学习时间的显著减少. 其次, 由于一个旨在最小化无效推理过程的失败数据库的直接影响, 冗余
推理的次数显著减少. 尽管基于记忆的裁剪算法需要额外的内存来保存失败信息, 但由于现代高级计算机资源的
存在, 几乎没有带来负面影响. 在我们裁剪算法的理论分析中, 证明了在内存无限可用的假设下程序搜索空间的减
少率. 然而, 当将理论期望与实际程序学习时间的减少进行比较时, 发现了由于两个主要因素导致的差异. 首先,
Prolog 操作机制的实际限制, 尤其是堆栈限制, 违背了我们关于无限内存可用性的理论假设. 这种限制本质上限制
了在学习过程中可以有效管理的搜索空间大小. 其次, 裁剪算法的实现涉及大量计算, 因为需要识别失败目标以及
验证和更新数据库的操作. 这些活动会带来额外的时间成本, 而这些在理论模型中未被考虑. 总体而言, 内存成本
对本文裁剪算法的影响是可以接受的. 在我们的实验中, 裁剪算法的额外内存使用没有引起任何“内存不足”错误,
相反, 在机器人服务员任务的一阶和高阶实验中, 分别有 12% 和 24% 的超时案例通过提出的裁剪算法得以解决.
在不久的将来, 我们将专注于几个领域以进一步优化所提算法. 首先, 将研究更高效的数据结构和存储方法,
以提高算法的性能和计算效率. 这可能需要使用更高级的编程工具和框架来优化内存管理和数据组织. 其次, 计划
探索将元解释学习与其他机器学习技术 (如神经网络) 结合, 以实现更复杂和复杂的程序合成任务. 我们预计这些
措施不仅能优化现有算法, 还能显著扩展其实际适用性.

References:
[1] Muggleton S, De Raedt L. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 1994, 19–20:
629–679. [doi: 10.1016/0743-1066(94)90035-3]
[2] Muggleton SH, Lin DH, Pahlavi N, Tamaddoni-Nezhad A. Meta-interpretive learning: Application to grammatical inference. Machine
Learning, 2014, 94(1): 25–49. [doi: 10.1007/s10994-013-5358-3]
[3] Quinlan JR, Cameron-Jones RM. FOIL: A midterm report. In: Proc. of the 1993 European Conf. Machine Learning. Vienna: Springer,
1993. 1–20. [doi: 10.1007/3-540-56602-3_124]
[4] Muggleton S. Inverse entailment and Progol. New Generation Computing, 1995, 13(3–4): 245–286. [doi: 10.1007/bf03037227]
[5] Blockeel H, De Raedt L. Top-down induction of first-order logical decision trees. Artificial Intelligence, 1998, 101(1–2): 285–297. [doi:
10.1016/s0004-3702(98)00034-4]
[6] Srinivasan A. The Aleph Manual. 2001. https://www.cs.ox.ac.uk/activities/programinduction/Aleph/aleph.html
[7] Lin DH, Dechter E, Ellis K, et al. Bias reformulation for one-shot function induction. In: Proc. of the 21st European Conf. on Artificial
Intelligence. Prague: IOS Press, 2014. 525–530.