A POLYNOMIAL APPROACH TO THE CONSTRUCTIVE INDUCTION OF STRUCTURAL KNOWLEDGE

The representation formalism as well as the representation language is of great importance for the success of machine learning. The represen tation formalism should be expressive, efficient, useful, and applicab le. First-order logic needs to be restricted in order to be efficient for inductive and deductive reasoning. In the field of knowledge repre sentation, term subsumption formalisms have been developed which are e fficient arid expressive. In this article, a learning algorithm, KLUST ER, is described that represents concept definitions in this formalism . KLUSTER enhances the representation language if this is necessary fo r the discrimination of concepts. Hence, KLUSTER is a constructive ind uction program. KLUSTER builds the most specific generalization and a most general discrimination in polynomial time. It embeds these concep t learning problems into the overall task of learning a hierarchy of c oncepts.