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

ON OPTIMAL PROBLEMS IN INDUCTIVE LOGIC PROGRAMMING

归纳逻辑程序设计的核心问题是如何从背景知识中优选谓词构造满足约束的归纳假设．按Ｏｃａｍ准则，满足约束的最精简归纳假设为优，但迄今归纳逻辑程序设计中精简归纳假设构造的计算复杂性尚未解决．文中以扩张矩阵理论为工具证明了归纳假设构造中的一些主要最优化问题的计算复杂性是ＮＰ困难的，并给出了构造优假设的启发式算法，实验表明该算法产生的归纳假设在结构上具有明显的优越性．

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.