An Efficient Subsumption Algorithm for Inductive Logic Programming

Abstract

In this paper we investigate the efficiency of θ-subsumption (⊢θ), the basic provability relation in ILP. As D ⊢θ C is NP-complete even if we restrict ourselves to linked Horn clauses and fix C to contain only a small constant number of literals, we investigate in several restrictions of D. We first adapt the notion of determinate clauses used in ILP and show that θ-subsumption is decidable in polynomial time if D is determinate with respect to C. Secondly, we adapt the notion of k-local Horn clauses and show that θ-subsumption is efficiently computable for some reasonably small k. We then show how these results can be combined, to give an efficient reasoning procedure for determinate k-local Horn clauses, an ILP-problem recently suggested to be polynomial predictable by Cohen (1993) by a simple counting argument. We finally outline how the θ-reduction algorithm, an essential part of every lgg ILP-learning algorithm, can be improved by these ideas.