Inverse subsumption for complete explanatory induction

作     者：Yamamoto, Yoshitaka Inoue, Katsumi Iwanuma, Koji 

作者机构：Univ Yamanashi Kofu Yamanashi 4008510 Japan Res Org Informat & Syst Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan 

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

年 卷 期：2012年第86卷第1期

页      面：115-139页

核心收录：

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

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

主　　题：Inverse entailment Inverse subsumption Learning from entailment Explanatory induction Inductive logic programming 

摘      要：Modern explanatory inductive logic programming methods like Progol, Residue procedure, CF-induction, HAIL and Imparo use the principle of inverse entailment (IE). Those IE-based methods commonly compute a hypothesis in two steps: by first constructing an intermediate theory and next by generalizing its negation into the hypothesis with the inverse of the entailment relation. Inverse entailment ensures the completeness of generalization. On the other hand, it imposes many non-deterministic generalization operators that cause the search space to be very large. For this reason, most of those methods use the inverse relation of subsumption, instead of entailment. However, it is not clear how this logical reduction affects the completeness of generalization. In this paper, we investigate whether or not inverse subsumption can be embedded in a complete induction procedure;and if it can, how it is to be realized. Our main result is a new form of inverse subsumption that ensures the completeness of generalization. Consequently, inverse entailment can be reduced to inverse subsumption without losing the completeness for finding hypotheses in explanatory induction.