归纳逻辑程序设计中的优化问题研究  

ON OPTIMAL PROBLEMS IN INDUCTIVE LOGIC PROGRAMMING

作　　者：叶风[1] 徐晓飞[1] 权光日[1] 陈彬[1] 邱深山[1] 

机构地区：[1]哈尔滨工业大学计算机科学与工程系

出　　处：《计算机研究与发展》1999年第5期560-566,共7页Journal of Computer Research and Development

基　　金：国家"八六三"高技术计划基金

摘　　要：归纳逻辑程序设计的核心问题是如何从背景知识中优选谓词构造满足约束的归纳假设．按Ｏｃａｍ准则，满足约束的最精简归纳假设为优，但迄今归纳逻辑程序设计中精简归纳假设构造的计算复杂性尚未解决．文中以扩张矩阵理论为工具证明了归纳假设构造中的一些主要最优化问题的计算复杂性是ＮＰ困难的，并给出了构造优假设的启发式算法，实验表明该算法产生的归纳假设在结构上具有明显的优越性．The essential issue in inductive logic programming is how to construct inductive hypotheses with optimal predicates selected from background knowledge and constrains satisfied.According to Occam's principle,the simplest inductive hypotheses are the best.The computational complexity of constructing simplest inductive hypotheses,however,has not been fully investigated.Based on extension matrix,the main optimal problems in ILP are proven to be NP hard.A heuristic algorithm is then presented to solve the problems.The experiments show that the algorithm has superiority in the structures of inductive hypotheses produced.

关 键 词：归纳学习 归纳逻辑程序 程序设计 优化 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP18[自动化与计算机技术—计算机科学与技术]