Macro-Operators in Multirelational Learning: A Search-Space Reduction Technique

Abstract

Refinement operators are frequently used in the area of multirelational learning (Inductive Logic Programming, ILP) in order to search systematically through a generality order on clauses for a correct theory. Only the clauses reachable by a finite number of applications of a refinement operator are considered by a learning system using this refinement operator; ie. the refinement operator determines the search space of the system. For efficiency reasons, we would like a refinement operator to compute the smallest set of clauses necessary to find a correct theory. In this paper we present a formal method based on macro-operators to reduce the search space defined by a downward refinement operator (ñ) while finding the same theory as the original operator. Basically we define a refinement operator which adds to a clause not only single-literals but also automatically created sequences of literals (macro-operators). This in turn allows us to discard clauses which do not belong to a correct theory. Experimental results show that this technique significantly reduces the search-space and thus accelerates the learning process.