Inverse subsumption for complete explanatory induction

摘要

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.