Preface xiii
1 Introduction: Classification Learning Features and Applications 1
1.1 Scope 1
1.2 Why Machine Learning? 2
1.3 Some Applications 3
1.3.1 Image Recognition 3
1.3.2 Speech Recognition 3
1.3.3 Medical Diagnosis 4
1.3.4 Statistical Arbitrage 4
1.4 Measurements Features and Feature Vectors 4
1.5 The Need for Probability 5
1.6 Supervised Learning 5
1.7 Summary 6
1.8 Appendix: Induction 6
1.9 Questions 7
1.10 References 8
2 Probability 10
2.1 Probability of Some Basic Events 10
2.2 Probabilities of Compound Events 12
2.3 Conditional Probability 13
2.4 Drawing Without Replacement 14
2.5 A Classic Birthday Problem 15
2.6 Random Variables 15
2.7 Expected Value 16
2.8 Variance 17
2.9 Summary 19
2.10 Appendix: Interpretations of Probability 19
2.11 Questions 20
2.12 References 21
3 Probability Densities 23
3.1 An Example in Two Dimensions 23
3.2 Random Numbers in [01] 23
3.3 Density Functions 24
3.4 Probability Densities in Higher Dimensions 27
3.5 Joint and Conditional Densities 27
3.6 Expected Value and Variance 28
3.7 Laws of Large Numbers 29
3.8 Summary 30
3.9 Appendix: Measurability 30
3.10 Questions 32
3.11 References 32
4 The Pattern Recognition Problem 34
4.1 A Simple Example 34
4.2 Decision Rules 35
4.3 Success Criterion 37
4.4 The Best Classifier: Bayes Decision Rule 37
4.5 Continuous Features and Densities 38
4.6 Summary 39
4.7 Appendix: Uncountably Many 39
4.8 Questions 40
4.9 References 41
5 The Optimal Bayes Decision Rule 43
5.1 Bayes Theorem 43
5.2 Bayes Decision Rule 44
5.3 Optimality and Some Comments 45
5.4 An Example 47
5.5 Bayes Theorem and Decision Rule with Densities 48
5.6 Summary 49
5.7 Appendix: Defining Conditional Probability 50
5.8 Questions 50
5.9 References 53
6 Learning from Examples 55
6.1 Lack of Knowledge of Distributions 55
6.2 Training Data 56
6.3 Assumptions on the Training Data 57
6.4 A Brute Force Approach to Learning 59
6.5 Curse of Dimensionality Inductive Bias and No Free Lunch 60
6.6 Summary 61
6.7 Appendix: What Sort of Learning? 62
6.8 Questions 63
6.9 References 64
7 The Nearest Neighbor Rule 65
7.1 The Nearest Neighbor Rule 65
7.2 Performance of the Nearest Neighbor Rule 66
7.3 Intuition and Proof Sketch of Performance 67
7.4 Using more Neighbors 69
7.5 Summary 70
7.6 Appendix: When People use Nearest Neighbor Reasoning 70
7.6.1 Who Is a Bachelor? 70
7.6.2 Legal Reasoning 71
7.6.3 Moral Reasoning 71
7.7 Questions 72
7.8 References 73
8 Kernel Rules 74
8.1 Motivation 74
8.2 A Variation on Nearest Neighbor Rules 75
8.3 Kernel Rules 76
8.4 Universal Consistency of Kernel Rules 79
8.5 Potential Functions 80
8.6 More General Kernels 81
8.7 Summary 82
8.8 Appendix: Kernels Similarity and Features 82
8.9 Questions 83
8.10 References 84
9 Neural Networks: Perceptrons 86
9.1 Multilayer Feedforward Networks 86
9.2 Neural Networks for Learning and Classification 87
9.3 Perceptrons 89
9.3.1 Threshold 90
9.4 Learning Rule for Perceptrons 90
9.5 Representational Capabilities of Perceptrons 92
9.6 Summary 94
9.7 Appendix: Models of Mind 95
9.8 Questions 96
9.9 References 97
10 Multilayer Networks 99
10.1 Representation Capabilities of Multilayer Networks 99
10.2 Learning and Sigmoidal Outputs 101
10.3 Training Error and Weight Space 104
10.4 Error Minimization by Gradient Descent 105
10.5 Backpropagation 106
10.6 Derivation of Backpropagation Equations 109
10.6.1 Derivation for a Single Unit 110
10.6.2 Derivation for a Network 111
10.7 Summary 113
10.8 Appendix: Gradient Descent and Reasoning toward Reflective Equilibrium 113
10.9 Questions 114
10.10 References 115
11 PAC Learning 116
11.1 Class of Decision Rules 117
11.2 Best Rule from a Class 118
11.3 Probably Approximately Correct Criterion 119
11.4 PAC Learning 120
11.5 Summary 122
11.6 Appendix: Identifying Indiscernibles 122
11.7 Questions 123
11.8 References 123
12 VC Dimension 125
12.1 Approximation and Estimation Errors 125
12.2 Shattering 126
12.3 VC Dimension 127
12.4 Learning Result 128
12.5 Some Examples 129
12.6 Application to Neural Nets 132
12.7 Summary 133
12.8 Appendix: VC Dimension and Popper Dimension 133
12.9 Questions 134
12.10 References 135
13 Infinite VC Dimension 137
13.1 A Hierarchy of Classes and Modified PAC Criterion 138
13.2 Misfit Versus Complexity Trade-Off 138
13.3 Learning Results 139
13.4 Inductive Bias and Simplicity 140
13.5 Summary 141
13.6 Appendix: Uniform Convergence and Universal Consistency 141
13.7 Questions 142
13.8 References 143
14 The Function Estimation Problem 144
14.1 Estimation 144
14.2 Success Criterion 145
14.3 Best Estimator: Regression Function 146
14.4 Learning in Function Estimation 146
14.5 Summary 147
14.6 Appendix: Regression Toward the Mean 147
14.7 Questions 148
14.8 References 149
15 Learning Function Estimation 150
15.1 Review of the Function Estimation/Regression Problem 150
15.2 Nearest Neighbor Rules 151
15.3 Kernel Methods 151
15.4 Neural Network Learning 152
15.5 Estimation with a Fixed Class of Functions 153
15.6 Shattering Pseudo-Dimension and Learning 154
15.7 Conclusion 156
15.8 Appendix: Accuracy Precision Bias and Variance in Estimation 156
15.9 Questions 157
15.10 References 158
16 Simplicity 160
16.1 Simplicity in Science 160
16.1.1 Explicit Appeals to Simplicity 160
16.1.2 Is the World Simple? 161
16.1.3 Mistaken Appeals to Simplicity 161
16.1.4 Implicit Appeals to Simplicity 161
16.2 Ordering Hypotheses 162
16.2.1 Two Kinds of Simplicity Orderings 162
16.3 Two Examples 163
16.3.1 Curve Fitting 163
16.3.2 Enumerative Induction 164
16.4 Simplicity as Simplicity of Representation 165
16.4.1 Fix on a Particular System of Representation? 166
16.4.2 Are Fewer Parameters Simpler? 167
16.5 Pragmatic Theory of Simplicity 167
16.6 Simplicity and Global Indeterminacy 168
16.7 Summary 169
16.8 Appendix: Basic Science and Statistical Learning Theory 169
16.9 Questions 170
16.10 References 170
17 Support Vector Machines 172
17.1 Mapping the Feature Vectors 173
17.2 Maximizing the Margin 175
17.3 Optimization and Support Vectors 177
17.4 Implementation and Connection to Kernel Methods 179
17.5 Details of the Optimization Problem 180
17.5.1 Rewriting Separation Conditions 180
17.5.2 Equation for Margin 181
17.5.3 Slack Variables for Nonseparable Examples 181
17.5.4 Reformulation and Solution of Optimization 182
17.6 Summary 183
17.7 Appendix: Computation 184
17.8 Questions 185
17.9 References 186
18 Boosting 187
18.1 Weak Learning Rules 187
18.2 Combining Classifiers 188
18.3 Distribution on the Training Examples 189
18.4 The Adaboost Algorithm 190
18.5 Performance on Training Data 191
18.6 Generalization Performance 192
18.7 Summary 194
18.8 Appendix: Ensemble Methods 194
18.9 Questions 195
18.10 References 196
Bibliography 197
Author Index 203
Subject Index 207
