A Generalization of the Least General Generalization

To appear in Machine Intelligence, 13In this paper, we describe a polynomial time algorithm, called a k-minimal multiple generalization (k-mmg) algorithm, where $ k gep 1$, and its application to inductive learning problems. The algorithm is a natural extension of the least general generalization algorithm developed by Plotkin. Given a finite set of gound terms, the k-mmg algorithm generalizes the examples by at most k terms, while Plotkin\u27s algorithm does by a single term. We apply this algorithm to problems in inductive logic programming. We also show that this method is applicable to a problem of knowledge discovery in databases