A new heuristic to use least generalizations in ILP. Erdem, E. 1999. Unpublished draft
A new heuristic to use least generalizations in ILP [pdf]N  abstract   bibtex   
The classical least generalization of a set C of clauses is a single clause. Such a unique clause is sometimes too general wrt some over-generality criterion, and this undesired situation may lead to memorization of the clauses in C at the end of learning process. Current ILP systems apply some heuristic algorithms to refine this situation where the classical definition of least generalization is used as an operator in a search space throughout the learning. Our approach to this problem is different: we use the classical least generalization of C in a more declarative way to narrow the search-space at the very beginning of the learning algorithm, that is, we define the concept of least generalization of a set C of clauses in a different way as being a minimal-sized set of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to the over-generality criterion admissibility. We give an efficient algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility: these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result.

Downloads: 0