A Generalization of the Least General Generalization

In this chapter, we present a polynomial time algorithm, called a k-minimal multiple generalization (k-mmg) algorithm, where k 1, and its application to inductive learning problems. The algorithm is a natural extension of the least general generalization algorithm developed by Plotkin and Reynolds. Given a finite set of ground first-order terms, the k-mmg algorithm generalizes the examples by at most k first-order terms, while Plotkin's algorithm does by a single first-order term. We apply the k-mmg algorithm to several learning problems in inductive logic programming, and knowledge discovery in databases. 1 Introduction Inductive inference is a process to guess or identify an unknown general rule from its examples. An inference algorithm receives finite examples and produces a generalization of them as a hypothesis. This paper concerns with inference only from positive examples. For example, recently, a number of studies are aimed at knowledge discovery in databases (Piatetsky-Sha..