Using a Generalization Hierarchy to Learn from Examples

Abstract

OTIS (OpporTunistic Induction System) is an induction system that learns concepts from positive and negative examples by searching through the space of possible concept descriptions (the hypothesis space). An agenda controls search by scheduling tasks for generating concept descriptions via specialization, generalization, internal disjunction, and constructive induction. To aid the search, OTIS maintains a generalization hierarchy of the relations, attributes, and values that make up the description language. The hierarchy also classifies each concept description created and each training example, showing which descriptions are specializations of other descriptions and which training examples are described by each description. This paper describes the OTIS induction system, focusing on the generalization hierarchy and its benefits.