1 Introduction 2 Overview of Supervised Learning 2.1 Introduction 2.2 Variable Types and Terminology 2.3 Two Simple Approaches to Prediction: Least Squares and Nearest Neighbors 2.3.1 Linear Models and Least Squares 2.3.2 Nearest-Neighbor Methods 2.3.3 From Least Squares to Nearest Neighbors 2.4 Statistical Decision Theory 2.5 Local Methods in High Dimensions 2.6 Statistical Models, Supervised Learning and Function Approximation 2.6.1 A Statistical Model for the Joint Distribution Pr(X, Y ) 2.6.2 Supervised Learning 2.6.3 Function Approximation 2.7 Structured Regression Models 2.7.1 Difficulty of the Problem 2.8 Classes of Restricted Estimators 2.8.1 Roughness Penalty and Bayesian Methods 2.8.2 Kernel Methods and Local Regression 2.8.3 Basis Functions and Dictionary Methods 2.9 Model Selection and the Bias–Variance Tradeoff Bibliographic Notes Exercises 3 Linear Methods for Regression 3.1 Introduction 3.2 Linear Regression Models and Least Squares 3.2.1 Example: Prostate Cancer 3.2.2 The Gauss–Markov Theorem 3.2.3 Multiple Regression from Simple Univariate Regression 3.2.4 Multiple Outputs 3.3 Subset Selection 3.3.1 Best-Subset Selection 3.3.2 Forward- and Backward-Stepwise Selection 3.3.3 Forward-Stagewise Regression 3.3.4 Prostate Cancer Data Example (Continued) 3.4 Shrinkage Methods 3.4.1 Ridge Regression 3.4.2 The Lasso 3.4.3 Discussion: Subset Selection, Ridge Regression and the Lasso 3.4.4 Least Angle Regression 3.5 Methods Using Derived Input Directions 3.5.1 Principal Components Regression 3.5.2 Partial Least Squares 3.6 Discussion: A Comparison of the Selection and Shrinkage Methods 3.7 Multiple Outcome Shrinkage and Selection 3.8 More on the Lasso and Related Path Algorithms 3.8.1 Incremental Forward Stagewise Regression 3.8.2 Piecewise-Linear Path Algorithms 3.8.3 The Dantzig Selector 3.8.4 The Grouped Lasso 3.8.5 Further Properties of the Lasso 3.8.6 Pathwise Coordinate Optimization 3.9 Computational Considerations Bibliographic Notes Exercises 4 Linear Methods for Classification 4.1 Introduction 4.2 Linear Regression of an Indicator Matrix 4.3 Linear Discriminant Analysis 4.3.1 Regularized Discriminant Analysis 4.3.2 Computations for LDA 4.3.3 Reduced-Rank Linear Discriminant Analysis 4.4 Logistic Regression 4.4.1 Fitting Logistic Regression Models 4.4.2 Example: South African Heart Disease 4.4.3 Quadratic Approximations and Inference 4.4.4 L1 Regularized Logistic Regression 4.4.5 Logistic Regression or LDA? 4.5 Separating Hyperplanes 4.5.1 Rosenblatt’s Perceptron Learning Algorithm . 4.5.2 Optimal Separating Hyperplanes Bibliographic Notes Exercises 5 Basis Expansions and Regularization 5.1 Introduction 5.2 Piecewise Polynomials and Splines 5.2.1 Natural Cubic Splines 5.2.2 Example: South African Heart Disease (Continued) 5.2.3 Example: Phoneme Recognition 5.3 Filtering and Feature Extraction 5.4 Smoothing Splines 5.4.1 Degrees of Freedom and Smoother Matrices 5.5 Automatic Selection of the Smoothing Parameters 5.5.1 Fixing the Degrees of Freedom 5.5.2 The Bias–Variance Tradeoff 5.6 Nonparametric Logistic Regression 5.7 Multidimensional Splines 5.8 Regularization and Reproducing Kernel Hilbert Spaces 5.8.1 Spaces of Functions Generated by Kernels 5.8.2 Examples of RKHS 5.9 Wavelet Smoothing 5.9.1 Wavelet Bases and the Wavelet Transform 5.9.2 Adaptive Wavelet Filtering Bibliographic Notes Exercises Appendix: Computational Considerations for Splines Appendix: B-splines Appendix: Computations for Smoothing Splines 6 Kernel Smoothing Methods 6.1 One-Dimensional Kernel Smoothers 6.1.1 Local Linear Regression 6.1.2 Local Polynomial Regression 6.2 Selecting the Width of the Kernel 6.3 Local Regression in IRp 6.4 Structured Local Regression Models in IRp 6.4.1 Structured Kernels 6.4.2 Structured Regression Functions 6.5 Local Likelihood and Other Models 6.6 Kernel Density Estimation and Classification 6.6.1 Kernel Density Estimation 6.6.2 Kernel Density Classification 6.6.3 The Naive Bayes Classifier 6.7 Radial Basis Functions and Kernels 6.8 Mixture Models for Density Estimation and Classification 6.9 Computational Considerations Bibliographic Notes Exercises 7 Model Assessment and Selection 7.1 Introduction 7.2 Bias, Variance and Model Complexity 7.3 The Bias–Variance Decomposition 223 7.3.1 Example: Bias–Variance Tradeoff 7.4 Optimism of the Training Error Rate 7.5 Estimates of In-Sample Prediction Error 7.6 The Effective Number of Parameters 7.7 The Bayesian Approach and BIC 7.8 Minimum Description Length 7.9 Vapnik–Chervonenkis Dimension 7.9.1 Example (Continued) 7.10 Cross-Validation 7.10.1 K-Fold Cross-Validation 7.10.2 The Wrong and Right Way to Do Cross-validation 7.10.3 Does Cross-Validation Really Work? 7.11 Bootstrap Methods 7.11.1 Example (Continued) 7.12 Conditional or Expected Test Error? Bibliographic Notes Exercises 8 Model Inference and Averaging 8.1 Introduction 8.2 The Bootstrap and Maximum Likelihood Methods 8.2.1 A Smoothing Example 8.2.2 Maximum Likelihood Inference 8.2.3 Bootstrap versus Maximum Likelihood 8.3 Bayesian Methods 8.4 Relationship Between the Bootstrap and Bayesian Inference 8.5 The EM Algorithm 8.5.1 Two-Component Mixture Model 8.5.2 The EM Algorithm in General 8.5.3 EM as a Maximization–Maximization Procedure 8.6 MCMC for Sampling from the Posterior 8.7 Bagging 8.7.1 Example: Trees with Simulated Data 8.8 Model Averaging and Stacking 8.9 Stochastic Search: Bumping Bibliographic Notes Exercises 9 Additive Models, Trees, and Related Methods 9.1 Generalized Additive Models 9.1.1 Fitting Additive Models 9.1.2 Example: Additive Logistic Regression 9.1.3 Summary 9.2 Tree-Based Methods 9.2.1 Background 9.2.2 Regression Trees 9.2.3 Classification Trees 9.2.4 Other Issues 9.2.5 Spam Example (Continued) 9.3 PRIM: Bump Hunting 9.3.1 Spam Example (Continued) 9.4 MARS: Multivariate Adaptive Regression Splines 9.4.1 Spam Example (Continued) 9.4.2 Example (Simulated Data) 9.4.3 Other Issues 9.5 Hierarchical Mixtures of Experts 9.6 Missing Data 9.7 Computational Considerations Bibliographic Notes Exercises 10 Boosting and Additive Trees 10.1 Boosting Methods 10.1.1 Outline of This Chapter 10.2 Boosting Fits an Additive Model 10.3 Forward Stagewise Additive Modeling 10.4 Exponential Loss and AdaBoost 10.5 Why Exponential Loss? 10.6 Loss Functions and Robustness 10.7 “Off-the-Shelf” Procedures for Data Mining 10.8 Example: Spam Data 10.9 Boosting Trees 10.10 Numerical Optimization via Gradient Boosting 10.10.1 Steepest Descent 10.10.2 Gradient Boosting 10.10.3 Implementations of Gradient Boosting 10.11 Right-Sized Trees for Boosting 10.12 Regularization 10.12.1 Shrinkage 10.12.2 Subsampling 10.13 Interpretation 10.13.1 Relative Importance of Predictor Variables 10.13.2 Partial Dependence Plots 10.14 Illustrations 10.14.1 California Housing 10.14.2 New Zealand Fish 10.14.3 Demographics Data Bibliographic Notes Exercises 11 Neural Networks 11.1 Introduction 11.2 Projection Pursuit Regression 11.3 Neural Networks 11.4 Fitting Neural Networks 11.5 Some Issues in Training Neural Networks 11.5.1 Starting Values 11.5.2 Overfitting 11.5.3 Scaling of the Inputs 11.5.4 Number of Hidden Units and Layers 11.5.5 Multiple Minima 11.6 Example: Simulated Data 11.7 Example: ZIP Code Data 11.8 Discussion 11.9 Bayesian Neural Nets and the NIPS 2003 Challenge 11.9.1 Bayes, Boosting and Bagging 11.9.2 Performance Comparisons 11.10 Computational Considerations Bibliographic Notes Exercises 12 Support Vector Machines and Flexible Discriminants 12.1 Introduction 12.2 The Support Vector Classifier 12.2.1 Computing the Support Vector Classifier 12.2.2 Mixture Example (Continued) 12.3 Support Vector Machines and Kernels 12.3.1 Computing the SVM for Classification 12.3.2 The SVM as a Penalization Method 12.3.3 Function Estimation and Reproducing Kernels 12.3.4 SVMs and the Curse of Dimensionality 12.3.5 A Path Algorithm for the SVM Classifier 12.3.6 Support Vector Machines for Regression 12.3.7 Regression and Kernels 12.3.8 Discussion 12.4 Generalizing Linear Discriminant Analysis 12.5 Flexible Discriminant Analysis 12.5.1 Computing the FDA Estimates 12.6 Penalized Discriminant Analysis 12.7 Mixture Discriminant Analysis 12.7.1 Example: Waveform Data Bibliographic Notes Exercises 13 Prototype Methods and Nearest-Neighbors 13.1 Introduction 13.2 Prototype Methods 13.2.1 K-means Clustering 13.2.2 Learning Vector Quantization 13.2.3 Gaussian Mixtures 13.3 k-Nearest-Neighbor Classifiers 13.3.1 Example: A Comparative Study 13.3.2 Example: k-Nearest-Neighbors and Image Scene Classification 13.3.3 Invariant Metrics and Tangent Distance 13.4 Adaptive Nearest-Neighbor Methods 13.4.1 Example 13.4.2 Global Dimension Reduction for Nearest-Neighbors 13.5 Computational Considerations Bibliographic Notes Exercises 14 Unsupervised Learning 14.1 Introduction 14.2 Association Rules 14.2.1 Market Basket Analysis 14.2.2 The Apriori Algorithm 14.2.3 Example: Market Basket Analysis 14.2.4 Unsupervised as Supervised Learning 14.2.5 Generalized Association Rules 14.2.6 Choice of Supervised Learning Method 14.2.7 Example: Market Basket Analysis (Continued) 14.3 Cluster Analysis 14.3.1 Proximity Matrices 14.3.2 Dissimilarities Based on Attributes 14.3.3 Object Dissimilarity 14.3.4 Clustering Algorithms 14.3.5 Combinatorial Algorithms 14.3.6 K-means 14.3.7 Gaussian Mixtures as Soft K-means Clustering 14.3.8 Example: Human Tumor Microarray Data 14.3.9 Vector Quantization 14.3.10 K-medoids 14.3.11 Practical Issues 14.3.12 Hierarchical Clustering 14.4 Self-Organizing Maps 14.5 Principal Components, Curves and Surfaces 14.5.1 Principal Components 14.5.2 Principal Curves and Surfaces 14.5.3 Spectral Clustering 14.5.4 Kernel Principal Components 14.5.5 Sparse Principal Components 14.6 Non-negative Matrix Factorization 14.6.1 Archetypal Analysis 14.7 Independent Component Analysis and Exploratory Projection Pursuit 14.7.1 Latent Variables and Factor Analysis 14.7.2 Independent Component Analysis 14.7.3 Exploratory Projection Pursuit 14.7.4 A Direct Approach to ICA 14.8 Multidimensional Scaling 14.9 Nonlinear Dimension Reduction and Local Multidimensional Scaling 14.10 The Google PageRank Algorithm Bibliographic Notes Exercises 15 Random Forests 15.1 Introduction 15.2 Definition of Random Forests 15.3 Details of Random Forests 15.3.1 Out of Bag Samples 15.3.2 Variable Importance 15.3.3 Proximity Plots 15.3.4 Random Forests and Overfitting 15.4 Analysis of Random Forests 15.4.1 Variance and the De-Correlation Effect 15.4.2 Bias 15.4.3 Adaptive Nearest Neighbors Bibliographic Notes Exercises 16 Ensemble Learning 16.1 Introduction 16.2 Boosting and Regularization Paths 16.2.1 Penalized Regression 16.2.2 The “Bet on Sparsity” Principle 16.2.3 Regularization Paths, Over-fitting and Margins 16.3 Learning Ensembles 16.3.1 Learning a Good Ensemble 16.3.2 Rule Ensembles Bibliographic Notes Exercises 17 Undirected Graphical Models 17.1 Introduction 17.2 Markov Graphs and Their Properties 17.3 Undirected Graphical Models for Continuous Variables 17.3.1 Estimation of the Parameters when the Graph Structure is Known 17.3.2 Estimation of the Graph Structure 17.4 Undirected Graphical Models for Discrete Variables 17.4.1 Estimation of the Parameters when the Graph Structure is Known 17.4.2 Hidden Nodes 17.4.3 Estimation of the Graph Structure 17.4.4 Restricted Boltzmann Machines Exercises 18 High-Dimensional Problems: p ≫ N 18.1 When p is Much Bigger than N 18.2 Diagonal Linear Discriminant Analysis and Nearest Shrunken Centroids 18.3 Linear Classifiers with Quadratic Regularization 18.3.1 Regularized Discriminant Analysis 18.3.2 Logistic Regression with Quadratic Regularization 18.3.3 The Support Vector Classifier 18.3.4 Feature Selection 18.3.5 Computational Shortcuts When p ≫ N 18.4 Linear Classifiers with L1 Regularization 18.4.1 Application of Lasso to Protein Mass Spectroscopy 18.4.2 The Fused Lasso for Functional Data 18.5 Classification When Features are Unavailable 18.5.1 Example: String Kernels and Protein Classification 18.5.2 Classification and Other Models Using Inner-Product Kernels and Pairwise Distances . 18.5.3 Example: Abstracts Classification 18.6 High-Dimensional Regression: Supervised Principal Components 18.6.1 Connection to Latent-Variable Modeling 18.6.2 Relationship with Partial Least Squares 18.6.3 Pre-Conditioning for Feature Selection 18.7 Feature Assessment and the Multiple-Testing Problem 18.7.1 The False Discovery Rate 18.7.2 Asymmetric Cutpoints and the SAM Procedure 18.7.3 A Bayesian Interpretation of the FDR 18.8 Bibliographic Notes Exercises