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

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

An ILP Algorithm Without Restriction of Constant Ordering

In this paper, the shortcomings in theory and limitation in applications of FOIL (first-order induc-tive learner) are analyzed. To overcome these difficulties, instance graph H(R,E) and instance order are intro-duced to clarify the relationship between the set R of recursive rules and the instance space E. Based on these concepts, a new ILP (inductive logic programming) algorithm, FOILPlus, is put forward, which prevents the generation of harmful recursive rules by utilizing hung example and hung arc to hold Instance Graph. The algo-rithm can complete learning tasks without the restriction of constant ordering, and does not substantially raise the computational complexity compared with FOIL. FOILPlus has been implemented, and experiments show that it does complete two learning tasks which FOIL fails.