Incremental Version-Space Merging: A General Framework for Concept Learning
Published on 31. July 1990
Book
Hardback
XVI, 116 pages
978-0-7923-9119-7 (ISBN)
Description
One of the most enjoyable experiences in science is hearing a simple but novel idea which instantly rings true, and whose consequences then begin to unfold in unforeseen directions. For me, this book presents such an idea and several of its ramifications. This book is concerned with machine learning. It focuses on a ques tion that is central to understanding how computers might learn: "how can a computer acquire the definition of some general concept by abstracting from specific training instances of the concept?" Although this question of how to automatically generalize from examples has been considered by many researchers over several decades, it remains only partly answered. The approach developed in this book, based on Haym Hirsh's Ph.D. dis sertation, leads to an algorithm which efficiently and exhaustively searches a space of hypotheses (possible generalizations of the data) to find all maxi mally consistent hypotheses, even in the presence of certain types of incon sistencies in the data. More generally, it provides a framework for integrat ing different types of constraints (e.g., training examples, prior knowledge) which allow the learner to reduce the set of hypotheses under consideration.
More details
Series
Edition
1990 ed.
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Research
Illustrations
XVI, 116 p.
Dimensions
Height: 241 mm
Width: 160 mm
Thickness: 13 mm
Weight
377 gr
ISBN-13
978-0-7923-9119-7 (9780792391197)
DOI
10.1007/978-1-4613-1557-5
Schweitzer Classification
Other editions
Additional editions
E-Book
12/2012
Springer
€96.29
Available for download
Book
09/2011
Springer
€106.99
Shipment within 15-20 days
Content
1 Overview.- 1.1 Background: Version Spaces and the Candidate-Elimination Algorithm.- 1.2 Contributions.- 1.3 Reader's Guide.- 2 Incremental Version-Space Merging.- 2.1 Generalizing Version Spaces.- 2.2 Version-Space Merging.- 2.3 Incremental Version-Space Merging.- 3 The Candidate-Elimination Algorithm: Emulation and Extensions.- 3.1 Learning Example.- 3.2 The Candidate-Elimination Algorithm.- 3.3 Candidate-Elimination Algorithm Emulation.- 3.4 Formal Proof of Equivalence.- 3.5 Ambiguous Training Data.- 3.6 Summary.- 4 Learning from Data with Bounded Inconsistency.- 4.1 Bounded Inconsistency.- 4.2 The Approach.- 4.3 Searching the Version Space.- 4.4 Example.- 4.5 Comparison to Related Work.- 4.6 Discussion.- 4.7 Formal Results.- 4.8 Summary.- 5 Combining Empirical and Analytical Learning.- 5.1 Explanation-Based Generalization.- 5.2 Combining EBG with Incremental Version-Space Merging.- 5.3 Examples.- 5.4 Perspectives.- 5.5 Constraints on the Concept Description Language.- 5.6 Related Work.- 5.7 Summary.- 6 Incremental Batch Learning.- 6.1 RL.- 6.2 The Approach.- 6.3 Example.- 6.4 Summary.- 7 Computational Complexity.- 7.1 Version-Space Formation.- 7.2 Version-Space Merging.- 7.3 Incremental Version-Space Merging.- 7.4 Summary.- 8 Theoretical Underpinnings.- 8.1 Terminology and Notation.- 8.2 Generalizing Version Spaces.- 8.3 Version-Space Intersections.- 8.4 Version-Space Unions.- 8.5 Summary.- 9 Conclusions.- 9.1 Results.- 9.2 Analysis.- 9.3 Open Problems.- 9.4 Summary.- A IVSM Program Listing.