Machine Learning

This book covers the field of machine learning, which is the study of algorithms that allow computer programs to automatically improve through experience. The book is intended to support upper level undergraduate and introductory level graduate courses in machine learning. From the preface ---------------- The field of machine learning is concerned with the question of how to construct computer programs that automatically improve with experience. In recent years many successful machine learning applications have been developed, ranging from data-mining programs that learn to detect fraudulent credit card transactions, to information-filtering systems that learn users' reading preferences, to autonomous vehicles that learn to drive on public highways. At the same time, there have been important advances in the theory and algorithms that form the foundations of this field. The goal of this textbook is to present the key algorithms and theory that form the core of machine learning. Machine learning draws on concepts and results from many fields, including statistics, artificial intelligence, philosophy, information theory, biology, cognitive science, computational complexity, and control theory. My belief is that the best way to learn about machine learning is to view it from all of these perspectives and to understand the problem settings, algorithms, and assumptions that underlie each. In the past, this has been difficult due to the absence of a broad-based single source introduction to the field. The primary goal of this book is to provide such an introduction. Because of the interdisciplinary nature of the material, this book makes few assumptions about the background of the reader. Instead, it introduces basic concepts from statistics, artificial intelligence, information theory, and other disciplines as the need arises, focusing on just those concepts most relevant to machine learning. The book is intended for both undergraduate and graduate students in fields such as computer science, engineering, statistics, and the social sciences, and as a reference for software professionals and practitioners. Two principles that guided the writing of the book were that it should be accessible to undergraduate students and that it should contain the material I would want my own Ph.D. students to learn before beginning their doctoral research in machine learning. A third principle that guided the writing of this book was that it should present a balance of theory and practice. Machine learning theory attempts to answer questions such as "How does learning performance vary with the number of training examples presented?'' and "Which learning algorithms are most appropriate for various types of learning tasks?" This book includes discussions of these and other theoretical issues, drawing on theoretical constructs from statistics, computational complexity, and Bayesian analysis. The practice of machine learning is covered by presenting the major algorithms in the field, along with illustrative traces of their operation. Online data sets and implementations of several algorithms are available via the World Wide Web at https://cs.cmu.edu/~tom/ mlbook.html. These include neural network code and data for face recognition, decision tree learning' code and data for financial loan analysis, and Bayes classifier code and data for analyzing text documents. Preface Contents Introduction 1.1 Well-Posed learning Problems 1.2 Designing a Learning System 1.2.1 Choosing the training Experience 1.2.2 Choosing the Target Function 1.2.3 Choosing a Representation for the Target Function 1.2.4 Choosing a Function Approximation Algorithm 1.2.5 The Final Design 1.3 Perspectives and Issues in Machine Learning 1.3.1 Issues in Machine Learning 1.4 How to Read This Book 1.5 Summary and Further Reading Exercises References 2 Concept Learning and the General-to-Specific Ordering 2.1 Introduction 2.2 A Concept Learning Task 2.2.1 Notation 2.2.2 The Inductive Learning Hypothesis 2.3 Concept Learning us Search 2.3.1 General -to-Specific Ordering of Hypotheses 2.4 FIND-S: Finding a Maximally Specific Hypothesis 2.5 Version Spaces and the CANDIDATE ELIMINATIONS Algorithm 2.5.1 Representation 2.5.2 The LIST-THEN-ELIMINATE Algorithm 2.5.3 A More Compact Representation for Version Spaces 2.5.4 CANDIDATE-ELIMINATION Learning Algorithm 2.5.5 An Illustrative Example 2.6 Remarks on Version Spaces and CANDIDATE -ELIMIINATION 2.6.1 Will the CANDIDATE -ELIMIINATION Algorithm Converge to the Correct Hypothesis 2.6.2 What Training Example Should the Learner Request Next 2.6.3 How Can Partially Learned Concepts Be Used 2.7 Inductive Bias 2.7.1 A Bused Hypothesis Space 2.7.2 An Unbiased Learner 2.7.3 The Futility of Bias-Free Learning 2.8 Summary and Further Reading Exercises References 3 Decision Tree Learning 3.1 Introduction 3.2 Decision Tree Representation 3.3 Appropriate Problems for Decision Tree Learning 3.4 The Basic Decision Tree Learning Algorithm 3.4.1 Which Attribute Is the Best Classifier 3.4.2 An illustrative Example 3.5 Hypothesis Space Search in Decision Tree Learning 3.6 Inductive Bias in Decision Tree Learning 3.6.1 Restriction Biases and Preference Biases 3.6.2 Why Prefer Short Hypotheses 3.7 Issues in Decision Tree Learning 3.7.1 A voiding overfitting the Data 3.7.2 Incorporating Continuous-Valued Attributes 3.7.3 Alternative Measures for Selecting Attributes 3.7.4 Handling Training Examples with Missing Attribute Values 3.7.5 Handling Attributes with Differing Costs 3.8 Summary and Further Reading Exercises References 4 Artificial Neural Networks 4.1 Introduction 4.1.1 Biological Motivation 4.2 Neural Network Representations 4.3 Appropriate Problems for Neural Network Learning 4.4 Perceptrons 4.4.1 Representational Power of Perceptrons 4.4.2 The Perceptron Training Rule 4.4.3 Gradient Decent and the Delta Rule 4.4.4 Remarks 4.5 Multilayer Networks and the BACKPROPAGA TION Algorithm 4.5.1 A Differentiable Threshold Unit 4.5.2 The BACKPROPAGATION Algorithm 4.5.3 Derivation ofthe BACKPROPAGATION Rule 4.6 Remarks on the BACKPROPAGATION Algorithm 4.6.1 Convergence and Local Minima 4.6.2 Representational Power of Feedforward Networks 4.6.3 Hypothesis Space Search and Inductive Bias 4.6.4 Hidden Layer Representations 4.6.5 Generalization. Overfitting, and Stopping Criterion 4.7 An Illustrative Example: Face Recognition 4.7.1 The Task 4.7.2 Design Choices 4.7.3 Learned Hidden Representations 4.8 Advanced Topics in Artificial Neural Networks 4.8.1 Alternative Error Functions 4.8.2 Alternative Error Minimization Procedures 4.8.3 Recurrent Networks 4.8.4 Dynamically ModifYing Network Structure 4.9 Summary and Further Reading Exercises References 5 Evaluating Hypotheses 5.1 Motivation 5.2 Estimating Hypothesis Accuracy 5.2.1 Sample Error and True Error 5.2.2 Confidence Intervals for Discrete-Valued Hypotheses 5.3 Basics of Sampling Theory 5.3.1 Error Estimation and Estimating Binomial Proportions 5.3.2 The Binomial Distribution 5.3.3 Mean and Variance 5.3.4 Estimators. Bias, and Variance 5.3.5 Confidence Intervals 5.3.6 Two-Sided and One-Sided Bounds 5.4 A General Approach for Deriving Confidence Intervals 5.4.1 Central Limit Theorem 5.5 Difference in Error of Two Hypotheses 5.5.1 Hypothesis Testing 5.6 Comparing Learning Algorithms 5.6.1 Paired r Tests 5.6.2 Practical Considerations 5.7 Summary and Further Reading Exercises References 6 Bayesian Learning 6.1 Introduction 6.2 Bayes Theorem 6.2.1 An Example 6.3 Bayes Theorem and Concept Learning 6.3.1 Brute-Force Bayes Concept Learning 6.3.2 MAP Hypotheses and Consistent Learners 6.4 Maximum Likelihood and Least-Squared Error Hypotheses 6.5 Maximum Likelihood Hypotheses for Predicting Probabilities 6.5.1 Gradient Search to Maximize Likelihood in a Neural Net 6.6 Minimum Description Length Principle 6.7 Bayes Optimal Classifier 6.8 Gibbs Algorithm 6.9 Naive Bayes Classifier 6.9.1 An Illustrative Example 6.10 An Example: Learning to Classify Text 6.10.1 Experimental Results 6.11 Bayesian BeliefNetworks 6.11.1 Conditional Independence 6.11.2 Representation 6.11.3 Inference 6.11.4 Learning Bayesian BeliefNetworks 6.11.5 Gradient Ascent Training of Bayesian Networks 6.11.6 Learning the Structure of Bayesian Networks 6.12 The EM Algorithm 6.12.1 Estimating Means of A Gaussian 6.12.2 General Statement of EM Algorithm 6.12.3 Derivation of the k Means Algorithm 6.13 Summary and Further Reading Exercises References 7 Computational Learning Theory 7.1 Introduction 7.2 Probably Learning an Approximately Correct Hypothesis 7.2.1 The Problem Setting 7.2.2 Error of a Hypothesis 7.2.3 PAC Leamability 7.3 Sample Complexity for Finite Hypothesis Spaces 7.3.1 Agnostic Learning and Inconsistent Hypotheses 7.3.2 Conjunctions of Boolean Literals Are PAC-Learnable 7.3.3 PAC-Learnability of Other Concept Classes 7.4 Sample Complexity for Infinite Hypothesis Spaces 7.4.1 Shattering a Set of Instances 7.4.2 The Vapnik-Chervonenkis Dimension 7.4.3 Sample Complexity and the VC Dimension 7.4.4 VC Dimension for Neural Networks 7.5 The Mistake Bound Model of Learning 7.5.1 Mistake Bound for the Find-S Algorithm 7.5.2 Mistake Bound for the HALVING Algorithm 7.5.3 Optimal Mistake Bounds 7.5.4 WEIGHTED-MAJORITY Algorithm 7.6 Summary and Further Reading Exercises References 8 Instance-Based Learning 8.1 Introduction 8.2 k-NEAREST NEIGHBOR LEARNING 8.2.1 Distance- Weighted NEAREST NEIGHBOR Algorithm 8.2.2 Remark on k-NEAREST NEIGHBOR Algorithm 8.2.3 A Note on Terminology 8.3 Locally Weighted Regression 8.3.1 Locally Weighted Linear Regression 8.3.2 Remarks on Locally Weighted Regression 8.4 Radial Basis Functions 8.5 Case-Based Reasoning 8.6 Remarks on Lazy and Eager Learning 8.7 Summary and Further Reading Exercises References 9 Genetic Algorithms 9.1 Motivation 9.2 Genetic Algorithms 9.2.1 Representing Hypotheses 9.2.2 Genetic Operators 9.2.3 Fitness Function and Selection 9.3 An Illustrative Example 9.3.1 Extensions 9.4 Hypothesis Space Search 9.4.1 Population Evolution and the Schema Theorem 9.5 Genetic Programming 9.5.1 Representing Programs 9.5.2 Illustrative Example 9.5.3 Remarks on Genetic Programming 9.6 Models of Evolution and Learning 9.6.1 Lamarckian Evolution 9.6.2 Baldwin Effect 9.7 Parallelizing Genetic Algorithms 9.8 Summary and Further Reading Exercises References 10 Learning Sets of Rules 10.1 Introduction 10.2 Sequential Covering Algorithms 10.2.1 General to Specific Beam Search 10.2.2 Variations 10.3 Learning Rule Sets: Summary 10.4 learning First-Order Rules 10.4.1 First-Order Horn Clauses 10.4.2 Terminology 10.5 Learning Sets of First-Order Rules: FOIL 10.5.1 Generating Candidate Specializations in FOIL 10.5.2 Guiding the Search in FOIL 10.5.3 Learning Recursive Rule Sets 10.5.4 Summary of FOIL 10.6 Induction as Inverted Deduction 10.7 Inverting Resolution 10.7.1 First-Order Resolution 10.7.2 Inverting Resolution: First-Order Case 10.7.3 Summary of Inverse Resolution 10.7.4 Generalization. 9-Subsumption and Entailment 10.7.5 PROGOL 10.8 Summary and Further Reading Exercises References 11 Analytical learning 11.1 Introduction 11.1.1 Inductive and Analytical Learning Problems 11.2 Learning with Perfect Domain Theories: PROLOG-EBG 11.2.1 An Illustrative Trace 11.3 Remarks on Explanation-Based Learning 11.3.1 Discovering New Features 11.3.2 Deductive Learning 11.3.3 Inductive Bias in Explanation-Based Learning 11.3.4 Knowledge Level learning 11.4 Explanation-Based Learning of Search Control Knowledge 11.5 Summary and Further Reading Exercises References 12 Combining Inductive and Analytical Learning 12.1 Motivation 12.2 Inductive-Analytical Approaches to Learning 12.2.1 The Learning Problem 12.2.2 Hypothesis Space Search 12.3 Using Prior Knowledge to Initialize the Hypothesis 12.3.1 The KBAN'N Algorithm 12.3.2 An Illustrative Example 12.3.3 Remarks 12.4 Using Prior Knowledge to Alter the Search Objective 12.4.1 The T ANGENTPROP Algorithm 12.4.2 An Illustrative Example 12.4.3 Remarks 12.4.4 The EBNN Algorithm 12.4.5 Remarks 12.5 Using Prior Knowledge to Augment Search Operators 12.5.1 The FOCL Algorithm 12.5.2 Remarks 12.6 State ofthe An 12.7 Summary and Further Reading Exercises References 13 Reinforcement Learning 13.1 Introduction 13.2 The Learning Task 13.3 Q Learning 13.3.1 The Q function 13.3.2 An Algorithm for Learning Q 13.3.3 An Illustrative Example 13.3.4 Convergence 13.3.5 Experimentation Strategies 13.3.6 Updating Sequence 13.4 Nondeterministic Rewards and Actions 13.5 Temporal Difference Learning 13.6 Generalizing from Examples 13.7 Relationship to Dynamic Programming 13.8 Summary and Further Reading Exercises References Appendix Notation Indexes Author Index (MISSING) Subject Index

This exciting addition to the McGraw-Hill Series in Computer Science focuses on the concepts and techniques that contribute to the rapidly changing field of machine learning—including probability and statistics, artificial intelligence, and neural networks—unifying them all in a logical and coherent manner. Machine Learning serves as a useful reference tool for software developers and researchers, as well as an outstanding text for college students.