首页 | 本学科首页   官方微博 | 高级检索  
     

一个不受常量序限制的归纳逻辑程序设计算法
引用本文:张润琦 陈小平. 一个不受常量序限制的归纳逻辑程序设计算法[J]. 软件学报, 1999, 10(8): 868-876
作者姓名:张润琦 陈小平
作者单位:中国科技大学少年班系!合肥,230026,中国科技大学计算机科学系!合肥,230027,E-mail:gqliu@mail.ustc.edu.cn,中国科技大学计算机科学系!合肥,230027,E-mail:gqliu@mail.ustc.edu.cn
摘    要:文章分析了FOIL(first-orderinductivelearner)递归谓词学习算法理论上的不足以及由此导致的应用范围的局限,并通过两个例子给予详细说明.为了克服这一缺陷,文章引入了反映递归规则集R与实例空间E本质关系的实例图H(R.E)和实例序的概念,奠定了算法的理论基础.在此基础上,给出了基于实例图的FOILPlus算法.算法通过对悬例、悬弧的操作把握住实例序,自然而然地防止了病态递归规则的产生,从而保证了FOILPlus可以不受常量序限制地完成学习任务;同时,算法的时空复杂度较之FOIL算法没有增加.FOILPlus算法已经编程实现,并用它尝试了两个FOIL学习失败的递归任务,都获得了成功.

关 键 词:归纳逻辑程序设计  FOIL(first-orderinductivelearner)  递归  实例图  实例序  悬例  悬弧  FOILPlus

An ILP Algorithm Without Restriction of Constant Ordering
ZHANG Run-qi, CHEN Xiao-ping, LIU Gui-quan. An ILP Algorithm Without Restriction of Constant Ordering[J]. Journal of Software, 1999, 10(8): 868-876
Authors:ZHANG Run-qi   CHEN Xiao-ping   LIU Gui-quan
Affiliation:ZHANG Run-qi; CHEN Xiao-ping; LIU Gui-quan 1(Department of the Spercial Class for the Gifted Young University of Science and Technology of China Hefei 230026) 2(Department of Computer Science University of Science and Technology of China Hefei 230027)
Abstract: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.
Keywords:ILP (inductive logic programming)   FOIL (first-order inductive learner)   recursive   instance graph   instance order   hung example   hung arc   FOILPlus
本文献已被 CNKI 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号