This monograph is a contribution to the study of the identification problem: the problem of identifying an item from a known class us ing positive and negative examples. This problem is considered to be an important component of the process of inductive learning, and as such has been studied extensively. In the overview we shall explain the objectives of this work and its place in the overall fabric of learning research. Context. Learning occurs in many forms; the only form we are treat ing here is inductive learning, roughly characterized as the process of forming general concepts from specific examples. Computer Science has found three basic approaches to this problem: * Select a specific learning task, possibly part of a larger task, and construct a computer program to solve that task . * Study cognitive models of learning in humans and extrapolate from them general principles to explain learning behavior. Then construct machine programs to test and illustrate these models. xi Xll PREFACE * Formulate a mathematical theory to capture key features of the induction process. This work belongs to the third category. The various studies of learning utilize training examples (data) in different ways. The three principal ones are: * Similarity-based (or empirical) learning, in which a collection of examples is used to select an explanation from a class of possible rules.

This monograph is a contribution to the study of the identification problem: the problem of identifying an item from a known class us ing positive and negative examples. This problem is considered to be an important component of the process of inductive learning, and as such has been studied extensively. In the overview we shall explain the objectives of this work and its place in the overall fabric of learning research. Context. Learning occurs in many forms; the only form we are treat ing here is inductive learning, roughly characterized as the process of forming general concepts from specific examples. Computer Science has found three basic approaches to this problem: * Select a specific learning task, possibly part of a larger task, and construct a computer program to solve that task . * Study cognitive models of learning in humans and extrapolate from them general principles to explain learning behavior. Then construct machine programs to test and illustrate these models. xi Xll PREFACE * Formulate a mathematical theory to capture key features of the induction process. This work belongs to the third category. The various studies of learning utilize training examples (data) in different ways. The three principal ones are: * Similarity-based (or empirical) learning, in which a collection of examples is used to select an explanation from a class of possible rules.