A Compendium of Machine Learning I: Symbolic Learning

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