一个不受常量序限制的归纳逻辑程序设计算法

摘要

文章分析了FOIL（first－orderinductivelearner）递归谓词学习算法理论上的不足以及由此导致的应用范围的局限，并通过两个例子给予详细说明．为了克服这一缺陷，文章引入了反映递归规则集R与实例空间E本质关系的实例图H（R．E）和实例序的概念，奠定了算法的理论基础．在此基础上，给出了基于实例图的FOILPlus算法．算法通过对悬例、悬弧的操作把握住实例序，自然而然地防止了病态递归规则的产生，从而保证了FOILPlus可以不受常量序限制地完成学习任务；同时，算法的时空复杂度较之FOIL算法没有增加．FOILPlus算法已经编程实现，并用它尝试了两个FOIL学习失败的递归任务，都获得了成功．