Inductive equivalence in clausal logic and nonmonotonic logic programming

作     者：Sakama, Chiaki Inoue, Katsumi 

作者机构：Wakayama Univ Dept Comp & Commun Sci Wakayama 6408510 Japan Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan 

出 版 物：《MACHINE LEARNING》 (机器学习)

年 卷 期：2011年第83卷第1期

页      面：1-29页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Grants-in-Aid for Scientific Research [20500134  20240016] Funding Source: KAKEN 

主　　题：Inductive equivalence Inductive logic programming Nonmonotonic logic programs 

摘      要：This paper provides a logical framework for comparing inductive capabilities among agents having different background theories. A background theory is called inductively equivalent to another background theory if the two theories induce the same hypotheses for any observation. Conditions of inductive equivalence change depending on the logic of representation languages and the logic of induction or inductive logic programming (ILP). In this paper, we consider clausal logic and nonmonotonic logic programs as representation languages for background theories. Then we investigate conditions of inductive equivalence in four different frameworks of induction, cautious induction , brave induction , learning from satisfiability , and descriptive induction . We observe that several induction algorithms in Horn ILP systems require weaker conditions of equivalence under restricted problem settings. We address that inductive equivalence can be used for verification and evaluation of induction algorithms, and argue problems for optimizing background theories in ILP.