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.

Inhalt

I Identification in the Limit from Indifferent Teachers.- 1 The Identification Problem.- 1.1 Learning from Indifferent Teachers.- 1.2 A Working Assumption.- 1.3 Convergence.- 1.4 A General Strategy.- 1.5 Examples from Existing Research.- 1.6 Basic Definitions.- 1.7 A General Algorithm.- 1.8 Additional Comments.- 2 Identification by Refinement.- 2.1 Order Homomorphisms.- 2.2 Refinements.- 2.2.1 Introduction.- 2.2.2 Upward and Downward Refinements.- 2.2.3 Summary.- 2.3 Identification by Refinement.- 2.4 Conclusion.- 3 How to Work With Refinements.- 3.1 Introduction.- 3.2 Three Useful Properties.- 3.3 Normal Forms and Monotonic Operations.- 3.4 Universal Refinements.- 3.4.1 Abstract Formulation.- 3.4.2 A Refinement for Clause-Form Sentences.- 3.4.3 Inductive Bias.- 3.5 Conclusions.- 3.6 Appendix to Chapter 3.- 3.6.1 Summary of Logic Notation and Terminology.- 3.6.2 Proof of Theorem 3.32.- 3.6.3 Refinement Properties of Figure 3.2.- II Probabilistic Identification from Random Examples.- 4 Probabilistic Approximate Identification.- 4.1 Probabilistic Identification in the Limit.- 4.2 The Model of Valiant.- 4.2.1 Pac-Identification.- 4.2.2 Identifying Normal-Form Expressions.- 4.2.3 Related Results about Valiant's Model.- 4.3 Using the Partial Order.- 4.4 Summary.- 5 Identification from Noisy Examples.- 5.1 Introduction.- 5.2 Prior Research Results.- 5.3 The Classification Noise Process.- 5.4 Pac-Identification.- 5.4.1 Finite Classes.- 5.4.2 Infinite Classes.- 5.4.3 Estimating the Noise Rate ?.- 5.5 Probabilistic Identification in the Limit.- 5.6 Identifying Normal-Form Expressions.- 5.7 Other Models of Noise.- 5.8 Appendix to Chapter 5.- 6 Conclusions.