Preface xi
Organization â" How to Use This Book xii
Acknowledgments xiv
About the Companion Website xiv
1 Introduction â" Examples from Real Life 1
2 The Problem of Learning 3
2.1 Domain 3
2.2 Range 4
2.3 Data 4
2.4 Loss 5
2.5 Risk 8
2.6 The Reality of the Unknown Function 12
2.7 Training and Selection of Models 12
2.8 Purposes of Learning 14
2.9 Notation 14
3 Regression 15
3.1 General Framework 16
3.2 Loss 17
3.3 Estimating the Model Parameters 17
3.4 Properties of Fitted Values 19
3.5 Estimating the Variance 22
3.6 A Normality Assumption 23
3.7 Computation 25
3.8 Categorical Features 26
3.9 Feature Expansions, Interactions, and Transformations 28
3.10 Penalized Regression: Model Transformation for Risk Reduction 31
3.11 Variations in Linear Regression 37
3.12 Nonlinear Regression 39
3.13 Nonparametric Regression 42
4 Classification 45
4.1 The Bayes Classifier 46
4.2 Introduction to Classifiers 47
4.3 Mitigating Biases in Software, Biases in Data, and Zero Probabilities 49
4.3.1 Mitigating Biases in Software by Adjusting Loss and Prior Probabilities 50
4.3.2 Mitigating Biases in Data by Adjusting Loss or Prior Probabilities 51
4.3.3 Mitigating Effects of Zero-One Probability Estimates 52
4.4 Class Boundaries 53
4.5 A Running Example 54
4.6 Likelihood Methods 55
4.6.1 Quadratic Discriminant Analysis 56
4.6.2 Linear Discriminant Analysis 58
4.6.3 Gaussian Mixture Models 60
4.6.4 Kernel Density Estimation 61
4.6.5 Histograms 65
4.6.6 The Naive Bayes Classifier 68
4.7 Prototype Methods 69
4.7.1 k-Nearest-Neighbor 69
4.7.2 Condensed k-Nearest-Neighbor 72
4.7.3 Nearest-Cluster 73
4.7.4 Learning Vector Quantization 73
4.8 Logistic Regression 76
4.8.1 The Logistic Regression Model 76
4.8.2 Adjusting the Marginal or Prior Distribution of Classes 79
4.8.3 Class Boundaries, Hyperplanes, and Geometry 81
4.9 Neural Networks 81
4.9.1 Activation Functions 81
4.9.2 Neurons 82
4.9.3 Single-Hidden-Layer Neural Networks 84
4.9.4 Multi-Hidden-Layer Neural Networks 90
4.9.5 Adjusting the Marginal or Prior Distribution of Classes 91
4.9.6 Logistic Regression and Zero-Hidden-Layer Neural Networks 91
4.10 Classification Trees 93
4.10.1 Classification of Data by Leaves (Terminal Nodes) 93
4.10.2 Impurity of Nodes and Trees 94
4.10.3 Growing Trees 95
4.10.4 Pruning Trees 98
4.10.5 Regression Trees 99
4.11 Support Vector Machines 100
4.11.1 A Geometric Definition of âGoodâ 100
4.11.2 Support Vector Machine Classifiers for Linearly Separable Data 101
4.11.3 The Central Role of Inner Products 103
4.11.4 Support Vector Machine Classifiers for Data Not Linearly Separable 104
4.11.5 Slack Variables as Hinge Loss 105
4.11.6 Multiple Classes, General Loss, and Non-uniform Class Prior 107
4.11.7 Approximation of the Bayes Classifier 109
4.11.8 Inner Products via Kernel Functions 110
4.12 Postscript: Example Problem Revisited 119
5 Bias-Variance Trade-Off 121
5.1 Squared-Error Loss 121
5.2 General Loss 125
6 Combining Classifiers 131
6.1 Ensembles 131
6.2 Ensemble Design 136
6.3 Bootstrap Aggregation (Bagging) 138
6.4 Random Forests 141
6.5 Boosting and Arcing 142
6.6 Classification by Regression Ensemble 147
6.7 Gradient Boosting 151
6.8 Stacking and Mixture of Experts 156
6.9 Postscript: Example Problem Revisited 160
7 Risk Estimation and Model Selection 163
7.1 Risk Estimation via Training Data 164
7.2 Risk Estimation via Validation or Test Data 164
7.2.1 Training, Validation, and Test Data Sets 164
7.2.2 Training, Validation, and Test Estimates of Risk 165
7.2.3 Application â" Precision of Validation and Test Estimates of Risk 166
7.2.4 Application â" Comparing a Modelâs Risk to a Target Value 166
7.2.5 Application â" Comparing the Difference of Modelsâ Risks to a Target Value 168
7.3 Cross-Validation 169
7.4 Improvements on Cross-Validation 171
7.5 Out-of-Bag Risk Estimation 172
7.6 Akaikeâs Information Criterion 173
7.7 Schwartzâs Bayesian Information Criterion 174
7.8 Rissanenâs Minimum Description Length Criterion 175
7.9 R 2 and Adjusted R 2 175
7.10 Stepwise Model Selection 177
7.11 Occamâs Razor 177
7.12 Size of Validation and Test Data Sets 178
7.12.1 Measures of Performance for Hypothesis Tests About Risk 178
7.12.2 Size of Training, Validation, and Test Data Sets 178
7.12.3 Example Construction of Training, Validation, and Test Data Sets 180
7.12.4 Example Use of Training and Validation Data Sets 183
7.12.5 Example Use of Test Data Sets 186
8 Consistency 187
8.1 Convergence of Sequences of Random Variables 187
8.2 Consistency for Parameter Estimation 188
8.3 Consistency for Prediction 188
8.4 There Are Consistent and Universally Consistent Classifiers 189
8.5 Convergence to Asymptopia Is Not Uniform and May Be Slow 191
9 Clustering 193
9.1 Gaussian Mixture Models 194
9.2 k-Means 194
9.3 Clustering by Mode-Hunting in a Density Estimate 195
9.4 Using Classifiers to Cluster 196
9.5 Dissimilarity 196
9.6 k-Medoids 197
9.7 k-Modes and k-Prototypes 197
9.8 Agglomerative Hierarchical Clustering 198
9.9 Divisive Hierarchical Clustering 199
9.10 How Many Clusters Are There? Interpretation of Clustering 200
9.11 An Impossibility Theorem 201
10 Optimization 203
10.1 Quasi-Newton Methods 204
10.1.1 The Newtonâ"Raphson Method for Finding Zeros 204
10.1.2 The Newtonâ"Raphson Method for Optimization 205
10.1.3 Gradient Descent 205
10.1.4 The Broydenâ"Fletcherâ"Goldfarbâ"Shanno Algorithm 205
10.1.5 Modifications to Quasi-Newton Methods 206
10.2 The Nelderâ"Mead Algorithm 207
10.3 Simulated Annealing 207
10.4 Genetic Algorithms 209
10.5 Particle Swarm Optimization 210
10.6 General Remarks on Optimization 211
10.6.1 Imperfectly Known Objective Functions 211
10.6.2 Objective Functions That Are Sums 212
10.6.3 Optimization from Multiple Starting Points 212
10.7 Solving Least-Squares Problems via Quasi-Newton Methods 213
10.8 Gradient Computation for Neural Networks via Backpropagation 214
10.9 Handling Missing Data via the Expectation-Maximization Algorithm 219
10.9.1 The General Algorithm 219
10.9.2 EM Climbs the Marginal Likelihood of the Observations 220
10.9.3 Example â" Fitting a Gaussian Mixture Model via EM 222
10.9.4 Example â" The Expectation Step 223
10.9.5 Example â" The Maximization Step 224
10.10 Fitting Support Vector Machines via Sequential Minimal Optimization 224
10.10.1 Primal and Dual Forms of the Linear SVM Optimization Problem 225
10.10.2 Slaterâs Condition and the Karushâ"Kuhnâ"Tucker Conditions 226
10.10.3 Generalization to Kernel Support Vector Machines 228
10.10.4 Computation of the Intercept 229
10.10.5 Solving the Dual Problem via Sequential Minimal Optimization 229
10.10.6 Step 1 â" Choosing a Pair of Coordinates to Optimize 230
10.10.7 Step 2 â" Constrained Optimization of a Pair of Coordinates 231
11 High-Dimensional Data 235
11.1 The Curse of Dimensionality 236
11.2 Two Running Examples 242
11.2.1 Example 1: Equilateral Simplex 242
11.2.2 Example 2: Text 242
11.3 Reducing Dimension While Preserving Information 243
11.3.1 The Geometry of Means and Covariances of Real Features 245
11.3.2 Principal Component Analysis 246
11.3.3 Working in âDissimilarity Spaceâ 248
11.3.4 Linear Multidimensional Scaling 248
11.3.5 The Singular Value Decomposition and Low-Rank Approximation 250
11.3.6 Stress-Minimizing Multidimensional Scaling 252
11.3.7 Projection Pursuit 252
11.3.8 Feature Selection 253
11.3.9 Clustering 254
11.3.10 Manifold Learning 254
11.3.11 Autoencoders 257
11.4 Model Regularization 261
11.4.1 Duality and the Geometry of Parameter Penalization 262
11.4.2 Parameter Penalization as Prior Information 263
12 Communication with Clients 267
12.1 Binary Classification and Hypothesis Testing 267
12.2 Terminology for Binary Decisions 269
12.3 Receiver Operating Characteristic (ROC) Curves 271
12.4 One-Dimensional Measures of Performance 273
12.5 Confusion Matrices 276
12.6 Pairwise Model Comparison 277
12.7 Multiple Testing 277
12.7.1 Control the Familywise Error 278
12.7.2 Control the False Discovery Rate 278
12.8 Expert Systems 279
12.9 Ethics in Machine Learning 280
12.9.1 Philosophical Foundations 280
12.9.2 Clear Goals 281
12.9.3 Good Practice 281
12.9.4 Machine Learning Might Not Be the Answer, and Thatâs OK 282
12.9.5 Documentation 282
13 Current Challenges in Machine Learning 283
13.1 Streaming Data 283
13.2 Distributed Data 283
13.3 Semi-Supervised Learning 283
13.4 Active Learning 284
13.5 Feature Construction via Deep Neural Networks 284
13.6 Transfer Learning 284
13.7 Interpretability and Protection of Complex Models 285
14 R and Python Source Code 287
14.1 Authorâs Biases 288
14.2 Packages and Code 288
14.3 The Running Example (Section 4.5) 289
14.4 The Bayes Classifier (Section 4.1) 292
14.5 Quadratic Discriminant Analysis (Section 4.6.1) 294
14.6 Linear Discriminant Analysis (Section 4.6.2) 296
14.7 Gaussian Mixture Models (Section 4.6.3) 297
14.8 Kernel Density Estimation (Section 4.6.4) 300
14.9 Histograms (Section 4.6.5) 304
14.10 The Naive Bayes Classifier (Section 4.6.6) 309
14.11 k-Nearest-Neighbor (Section 4.7.1) 312
14.12 Learning Vector Quantization (Section 4.7.4) 314
14.13 Logistic Regression (Section 4.8) 317
14.14 Neural Networks (Section 4.9) 319
14.15 Classification Trees (Section 4.10) 324
14.16 Support Vector Machines (Section 4.11) 332
14.17 Bootstrap Aggregation (Bagging) (Section 6.3) 341
14.18 Random Forests (Section 6.4) 343
14.19 Boosting by Reweighting (Section 6.5) 345
14.20 Boosting by Sampling (Arcing) (Section 6.5) 346
14.21 Gradient Boosted Trees (Section 6.7) 347
Appendix-A: List of Symbols 351
Appendix-B: The Condition Number of a Matrix with Respect to a Norm 353
Appendix-C: Converting Between Normal Parameters and Level-Curve Ellipsoids 357
Appendix-D: The Geometry of Linear Functions and Linear Classifiers 359
Appendix-E: Training Data and Fitted Parameters 367
Appendix-F: Solutions to Selected Exercises 371
Bibliography 399
Index 413
