A re-definition of least generalizations, and construction modes as a new declarative bias for ILP. Erdem, E. Technical Report BU-CEIS-9718, Bilkent University, 1997. N abstract bibtex The classical definition of the concept of least generalization of a clause set C is that it is a _single_ clause. Since such a unique clause is sometimes over-general, we re-define this concept 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 some over-generality criterion. We give an algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. The criterion for over-generality is problem-specific. We introduce a new such criterion: two clauses are compatible, i.e., their classical least generalization is not over-general, if this least generalization is admissible wrt a construction mode capturing the required dataflow of each involved relation. We design a language for expressing such construction modes, and we define a powerful admissibility criterion. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility (our over-generality criterion): 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.

@techreport{ErdFle98,
author = {Esra Erdem},
title = {A re-definition of least generalizations, and construction modes as a new declarative bias for {ILP}},
institution = {Bilkent University},
year = {1997},
number = {BU-CEIS-9718},
urlN = {ErdFle98.pdf},
abstract = {The classical definition of the concept of least generalization of a clause
set C is that it is a _single_ clause. Since such a unique clause is
sometimes over-general, we re-define this concept 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 some over-generality criterion. We give
an algorithm for computing this re-defined concept, providing thus a new
approach to disjunctive concept learning.
The criterion for over-generality is problem-specific. We introduce a new
such criterion: two clauses are compatible, i.e., their classical least
generalization is not over-general, if this least generalization is
admissible wrt a construction mode capturing the required dataflow of each
involved relation. We design a language for expressing such construction
modes, and we define a powerful admissibility criterion. We also prove a
few theorems relating the problem-independent concept of compatibility with
the problem-specific concept of admissibility (our over-generality
criterion): 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.},
}