Machine learning is a relatively new branch of artificial intelligence. The field has undergone a significant period of growth in the 1990s, with many new areas of research and development being explored. In this text, the authors take a broad brush view of the field in an attempt to bring together many of the results that have been achieved, presenting a general taxonomy of the field and the various key representative algorithms.
Table of Contents:
Introduction
1 Definitions, Paradigms, Taxonomies
1.1 What Is Machine Learning?
1.2 Paradigms
1.3 Taxonomies
1.4 Representation of Acquired Concepts
1.5 Background Knowledge
1.6 Comparison of Techniques
1.7 Knowledge-Level vs. Symbol-Level
1.8 Theoretical and Empirical Evaluation
Symbolic Empirical Learning
2 Introduction to SEL
3 Learning From Examples
3.1 Description Languages
3.2 Learning As Search
3.3 Single vs. Multiple-concept Learning
3.4 Incremental vs. Batch Learning
3.5 The Importance of Inductive Bias
3.6 The Single Representation Trick
3.7 The Need for Constructive Induction
3.8 The Problem of Noisy Data
3.9 Source of Instances
4 Decision Trees
4.1 Decision Trees as Concept Classifiers
4.2 Representational Restrictions
4.3 The TDIDT Family Tree
4.4 Evaluation of the TDIDT Method
4.5 CLs-Concept Learning System
4.5.1 General CLS Algorithm
4.6 ID3
4.6.1 Windowing
4.6.2 Problems with ID3
4.6.3 Noise, Missing Values, and Pruning
4.7 Related Systems and Recent Work
4.7.1 ACLS
4. 7.2 ASSISTANT
4.7.3 C4 , C4.5
4.7.4 CART
4.7.5 FRINGE
4.7.6 M5
4.7.7 MARS
4.7.8 PLSl
4.7.9 Conditional Rule Generation (CRG)
4.7.10 Decision Graphs
4.8 Alternative Test Selection Heuristics
4.9 Inclusion of Background Knowledge
4.10 Discovery of New Features
4.11 Incremental Processing of Examples
4.12 Continuous-Valued Attributes
5 Version Spaces
5.1 Basic Version Space Algorithm
5.2 Discussion of the Version Space Method
5.3 Representational Restrictions
6 Covering Algorithms
6.1 The AQ Star Methodology
6.1.1 Simplified Star Algorithm
6.1.2 Problem Background Knowledge
6.1.3 Generalization Rules
6.2 AQll
6.2.1 AQ15
6.2.2 AQTT-15 and POSEIDON
6.3 INDUCE
6.3.1 The INDUCE Algorithm
6.4 RIGEL
6.5 Discussion of AQ-Based Methods
6.6 Least Generalization
6.6.1 Plotkin
6.6.2 Algorithm for Least Generalization
6.7 DLG
6.7.1 The DLG Algorithm
6.7.2 Discussion of DLG
6.8 Other Least Generalization Systems
6.9 Other Covering Systems
6.9.1 CN 2
6.9.2 Decision Lists
6.10 Clustering and Numerical Systems
7 Inductive Logic Programming
7.1 FOIL
7.1.1 The FOIL Algorithm
7.1.2 Limitations and Discussion
7.2 GOLEM
7.2.1 The GoLEM Algorithm.
7.3 Other Recent ILP Systems
8 Inductive Bias
9 Conceptual Clustering
9.1 CLUSTER/2
9.1.1 The CLUSTER/2 Algorithm
9.1.2 CLUSTER/S
9.2 COBWEB
9.2.1 Category Utility
9.2.2 Representation of Concepts
9.2.3 Operators
9.2.4 The COBWEB Algorithm
9.2.5 Discussion of COBWEB
9.2.6 Related Systems
9.3 UNIMEM
9. 3.1 The UNIMEM Algorithm
9.3.2 RE SEARCHER
9.4 WITT
9.5 Other Conceptual Clustering Systems
10 Machine Discovery
10.1 AM
10.1.1 The Architecture of AM
10.1.2 Discussion of AM
10.2 EURISKO
10.3 BACON
10.3.1 Summary of the BACON Programs
10.3.2 Detecting Trends and Constants
10.3.3 BACON'S Rule-Space Operators
10.3.4 Intrinsic Properties and Common Divisors
10.3.5 Discussion of the BACON Method
10.3.6 Related Discovery Systems
10.4 ABACUS
10.5 PHINEAS
10.6 Other Discovery Systems
Appendix: Other SEL Topics
Analytical Learning
11 Introduction to EBL
11.1 EBL and Human Learning
11.2 Bias and Domain Knowledge
11.3 Imperfect Domain Theory
11.4 The Utility Problem
11.5 Operationality
11.6 Operationality and Generality
11.7 Representations and Learning
12 Composite Rules
12.1 EEG-Explanation-Based Generalization
12.1.1 The EBG Algorithm
12.1.2 MEBG-Multiple Example EBG
12.2 EGGS
12.2.1 The EGGS Algorithm
12.3 GENESIS
12.4 BAGGER 2
12.5 Equivalence of Algorithms
12.6 Other Macro-Operator Systems
13 Search Control Knowledge
13.1 LEX2
13.1.1 METALEX
13.2 PRODIGY
13.3 SOAR
13.4 Other Search Control Systems
Appendix: Other EBL Topics
Exemplars, Case-Based Reasoning, and Analogy
14 Exemplar-Based Learning
14.1 IBL
14.1.1 The lBL Algorithms
14.1.2 Similarity Function
14.2 PROTOS
14.2.1 PROTOS Classification Algorithm
15 Case-Based Reasoning
15,l JUDGE
15.2 CHEF
Appendix: Other Exemplar, Case-Based Topics
16 Learning by Analogy
16.1 Diagrammatic View
16.2 The Analogy Process
16.3 Modes of Analogy
16.3.1 Proportional Analogy
16,3.2 Predictive Analogy
16,3.3 Interpretive Analogy
16.4 COPYCAT
16.5 ANALOGY
16.6 Derivational Analogy
16. 7 Structure Mapping Theory
16.8 PUPS
16.9 Purpose-Directed Analogy
Appendix: Other Analogy Topics
Integrated Learning Systems
17 Introduction to Integrated Systems
18 Overly General or Overly Specific Theories
18.1 IOE
18.1.1 Semantic Bias
18.1.2 Discussion of the Method
18.1.3 Vapnik-Chervonenkis Dimension
18.2 Jou
18,2.1 The Jou Algorithm
18.3 Incremental Version Space Merging
18.3.1 The IVSM Algorithm
18.3.2 An Example of the IVSM Method
18.3.3 Discussion of the IVSM Method
18.4 Other Systems for Overly General Theories
18.5 Overly Specific Domain Theories
18.6 Learning by Failing to Explain
18.7 SIERRA
18.8 Other Systems for Overly Specific Theories
19 Systems for General Theory Revision
19.1 ML-SMART
19.1.1 The ML-SMART Algorithm
19.1.2 Discussion of the Method
19.2 FoCL
19.3 EITHER
19.3.1 An Example of EITHER
19.3.2 Theory for Data Interpretation
19.3.3 Discussion of the Method
19.4 FORTE
19.4.1 Inverse Resolution
19.5 OCCAM
19.6 Other Systems for Theory Revision
19.7 Abduction
19.8 Leaming Apprentice Systems
19.8.1 LEAP
19.8.2 DISCIPLE
19.8.3 ODYSSEUS
19.8.4 CLINT-CIA
19.9 Knowledge Acquisition Systems
Appendix: Other Integrated System Topics
Formal Analysis-Theory
20 Machine Learning Theory
20.1 Gold
20.2 Valiant
20.3 Blumer Bound
20.4 Bias
20.5 DeMorgan's Rules
20.6 Valiant's Algorithm fork-CNF
20.7 Vapnik-Chervonenkis Dimension
20.8 Example PAC Analysis
20.9 Structural Domains and Leamability
20.1 0 Average-Case Analysis
Appendix: Other Formal T heory Topics
Appendices
A Glossary
