Polynomial Approach to the Constructive Induction of Structural Knowledge

摘要

The representation formalism as well as the representation language is of greatimportance for the success of machine learning. The representation formalism should be expressive, efficient, useful, and applicable. First-order logic needs to be restricted in order to be efficient for inductive and deductive reasoning. In the field of knowledge representation term subsumption formalisms have been developed which are efficient and expressive. In the paper, a learning algorithm, KLUSTER, is described which represents concept definitions in the formaliism. KLUSTER enhances the representation language if this is necessary for the discrimination of concepts. Hence, KLUSTER is a constructive induction program. KLUSTER builds the most specific generalization and a most general discrimination in polynomial time. It embeds these concept learning problems into the overall task of learning a hierarchy of concepts. (Copyright (c) GMD 1992.)