Learning from data : a short course

This book, together with specially prepared online material freely accessible to our readers, provides a complete introduction to Machine Learning, the technology that enables computational systems to adaptively improve their performance with experience accumulated from the observed data. Such techniques are widely applied in engineering, science, finance, and commerce. This book is designed for a short course on machine learning. It is a short course, not a hurried course. From over a decade of teaching this material, we have distilled what we believe to be the core topics that every student of the subject should know. In addition, our readers are given free access to online e-Chapters that we update with the current trends in Machine Learning, such as deep learning and support vector machines. We chose the title `learning from data' that faithfully describes what the subject is about, and made it a point to cover the topics in a story-like fashion. Our hope is that the reader can learn all the fundamentals of the subject by reading the book cover to cover. Learning from data has distinct theoretical and practical tracks. In this book, we balance the theoretical and the practical, the mathematical and the heuristic. Theory that establishes the conceptual framework for learning is included, and so are heuristics that impact the performance of real learning systems. What we have emphasized are the necessary fundamentals that give any student of learning from data a solid foundation. The authors are professors at California Institute of Technology (Caltech), Rensselaer Polytechnic Institute (RPI), and National Taiwan University (NTU), where this book is the text for their popular courses on machine learning. The authors also consult extensively with financial and commercial companies on machine learning applications, and have led winning teams in machine learning competitions. 1. The Learning Problem 1.1 Problem Setup 1.1.1 Components of Learning 1.1.2 A Simple Learning Model 1.1.3 Learning versus Design 1.2 Types of Learning 1.2.1 Supervised Learning 1.2.2 Reinforcement Learning 1.2.3 Unsupervised Learning 1.2.4 Other Views of Learning 1.3 Is Learning Feasible? 1.3.1 Outside the Data Set 1.3.2 Probability to the Rescue 1.3.3 Feasibility of Learning 1.4 Error and Noise 1.4.1 Error Measures 1.4.2 Noisy Targets 1.5 Problems 2. Training versus Testing 2.1 Theory of Generalization 2.1.1 Effective Number of Hypotheses 2.1.2 Bounding the Growth Function 2.1.3 The VC Dimension 2.1.4 The VC Generalization Bound 2.2 Interpreting the Generalization Bound 2.2.1 Sample Complexity 2.2.2 Penalty for Model Complexity 2.2.3 The Test Set 2.2.4 Other Target Types 2.3 Approximation-Generalization Tradeoff 2.3.1 Bias and Variance 2.3.2 The Learning Curve 2.4 Problems 3. The Linear Model 3.1 Linear Classification 3.1.1 Non-Separable Data 3.2 Linear Regression 3.2.1 The Algorithm 3.2.2 Generalization Issues 3.3 Logistic Regression 3.3.1 Predicting a Probability 3.3.2 Gradient Descent 3.4 Nonlinear Transformation 3.4.1 The Z Space 3.4.2 Computation and Generalization 3.5 Problems 4. Overfitting 4.1 When Does Overfitting Occur? 4.1.1 A Case Study: Overfitting with Polynomials 4.1.2 Catalysts for Overfitting 4.2 Regularization 4.2.1 A Soft Order Constraint 4.2.2 Weight Decay and Augmented Error 4.2.3 Choosing a Regularizer: Pill or Poison? 4.3 Validation 4.3.1 The Validation Set 4.3.2 Model Selection 4.3.3 Cross Validation 4.3.4 Theory Versus Practice 4.4 Problems 5. Three Learning Principles 5.1 Occam's Razor 5.2 Sampling Bias 5.3 Data Snooping 5.4 Problems 6. Similarity-Based Methods 6.1 Similarity 6.1.1 Similarity Measures 6.2 Nearest Neighbor 6.2.1 Nearest Neighbor is 2-Optimal 6.2.2 k-Nearest Neighbors (k-NN) 6.2.3 Improving the Efficiency of Nearest Neighbor 6.2.4 Nearest Neighbor is Nonparametric 6.2.5 Multiclass Data 6.2.6 Nearest Neighbor Regression 6.3 Radial Basis Functions 6.3.1 Radial Basis Function Networks 6.3.2 Fitting the Data 6.3.3 Unsupervised k-Means Clustering 6.3.4 Justifications and Extensions of RBFs 6.4 Probability Density Estimation 6.4.1 Gaussian Mixture Models (GMMs) 6.5 Problems 7. Neural Networks 7.1 The Multi-layer Perceptron (MLP) 7.2 Neural Networks 7.2.1 Notation 7.2.2 Forward Propagation 7.2.3 Backpropagation Algorithm 7.2.4 Regression for Classification 7.3 Approximation versus Generalization 7.4 Regularization and Validation 7.4.1 Weight Based Complexity Penalties 7.4.2 Early Stopping 7.4.3 Experiments With Digits Data 7.5 Beefing Up Gradient Descent 7.5.1 Choosing the Learning Rate η 7.5.2 Conjugate Gradient Minimization 7.6 Deep Learning: Networks with Many Layers 7.6.1 A Greedy Deep Learning Algorithm 7.7 Problems 8. Support Vector Machines 8.1 The Optimal Hyperplane 8.1.1 Finding the Fattest Separating Hyperplane 8.1.2 Is a Fat Separator Better? 8.1.3 Non-Separable Data 8.2 Dual Formulation of the SVM 8.2.1 Lagrange Dual for a QP-Problem 8.2.2 Dual of the Hard-Margin SVM 8.2.3 Recovering the SVM from the Dual Solution 8.3 Kernel Trick for SVM 8.3.1 Kernel Trick via Dual SVM 8.3.2 Choice of Kernels 8.4 Soft-margin SVM 8.5 Problems 9. Learning Aides 9.1 Input Preprocessing 9.2 Dimension Reduction and Feature Selection 9.2.1 Principal Components Analysis (PCA) 9.2.2 Nonlinear Dimension Reduction 9.3 Hints And Invariances 9.3.1 Virtual Examples 9.3.2 Hints Versus Regularization 9.4 Data Cleaning 9.4.1 Using a Simpler Model to Identify Noisy Data 9.4.2 Computing a Validation Leverage Score 9.5 More on Validation 9.5.1 Rademacher Penalties 9.5.2 The Permutation and Bootstrap Penalties 9.5.3 Rademacher Generalization Bound 9.5.4 Out-of-Sample Error Estimates for Regression 9.6 Problems Epilogue Further Reading Appendix A - Proof of the VC Bound A.1 Relating Generalization Error to In-Sample Deviations A.2 Bounding Worst Case Deviation Using the Growth Function A.3 Bounding the Deviation between In-Sample Errors e-Appendix B - Linear Algebra B.1 Basic Properties of Vectors and Matrices B.2 SVD and Pseudo-Inverse B.3 Symmetric Matrices B.3.1 Positive Semi-Definite Matrices B.4 Trace and Determinant B.4.1 Inverse and Determinant Identities B.5 Inner Products, Metrix and Vector Norms B.5.1 Linear Hyperplanes and Quadratic Forms B.6 Vector and Matrix Calculus B.6.1 Multidimensional Integration B.6.2 Matrix Derivatives e-Appendix C - The E-M Algorithm C.1 Derivation of the E-M Algorithm C.2 Problems 1. The Learning Problem 1.1 Problem Setup 1.1.1 Components of Learning 1.1.2 A Simple Learning Model 1.1.3 Learning versus Design 1.2 Types of Learning 1.2.1 Supervised Learning 1.2.2 Reinforcement Learning 1.2.3 Unsupervised Learning 1.2.4 Other Views of Learning 1.3 Is Learning Feasible? 1.3.1 Outside the Data Set 1.3.2 Probability to the Rescue 1.3.3 Feasibility of Learning 1.4 Error and Noise 1.4.1 Error Measures 1.4.2 Noisy Targets 1.5 Problems 2. Training versus Testing 2.1 Theory of Generalization 2.1.1 Effective Number of Hypotheses 2.1.2 Bounding the Growth Function 2.1.3 The VC Dimension 2.1.4 The VC Generalization Bound 2.2 Interpreting the Generalization Bound 2.2.1 Sample Complexity 2.2.2 Penalty for Model Complexity 2.2.3 The Test Set 2.2.4 Other Target Types 2.3 Approximation-Generalization Tradeoff 2.3.1 Bias and Variance 2.3.2 The Learning Curve 2.4 Problems 3. The Linear Model 3.1 Linear Classification 3.1.1 Non-Separable Data 3.2 Linear Regression 3.2.1 The Algorithm 3.2.2 Generalization Issues 3.3 Logistic Regression 3.3.1 Predicting a Probability 3.3.2 Gradient Descent 3.4 Nonlinear Transformation 3.4.1 The Z Space 3.4.2 Computation and Generalization 3.5 Problems 4. Overfitting 4.1 When Does Overfitting Occur? 4.1.1 A Case Study: Overfitting with Polynomials 4.1.2 Catalysts for Overfitting 4.2 Regularization 4.2.1 A Soft Order Constraint 4.2.2 Weight Decay and Augmented Error 4.2.3 Choosing a Regularizer: Pill or Poison? 4.3 Validation 4.3.1 The Validation Set 4.3.2 Model Selection 4.3.3 Cross Validation 4.3.4 Theory Versus Practice 4.4 Problems 5. Three Learning Principles 5.1 Occam's Razor 5.2 Sampling Bias 5.3 Data Snooping 5.4 Problems 6. Similarity-Based Methods 6.1 Similarity 6.1.1 Similarity Measures 6.2 Nearest Neighbor 6.2.1 Nearest Neighbor is 2-Optimal 6.2.2 k-Nearest Neighbors (k-NN) 6.2.3 Improving the Efficiency of Nearest Neighbor 6.2.4 Nearest Neighbor is Nonparametric 6.2.5 Multiclass Data 6.2.6 Nearest Neighbor Regression 6.3 Radial Basis Functions 6.3.1 Radial Basis Function Networks 6.3.2 Fitting the Data 6.3.3 Unsupervised k-Means Clustering 6.3.4 Justifications and Extensions of RBFs 6.4 Probability Density Estimation 6.4.1 Gaussian Mixture Models (GMMs) 6.5 Problems 7. Neural Networks 7.1 The Multi-layer Perceptron (MLP) 7.2 Neural Networks 7.2.1 Notation 7.2.2 Forward Propagation 7.2.3 Backpropagation Algorithm 7.2.4 Regression for Classification 7.3 Approximation versus Generalization 7.4 Regularization and Validation 7.4.1 Weight Based Complexity Penalties 7.4.2 Early Stopping 7.4.3 Experiments With Digits Data 7.5 Beefing Up Gradient Descent 7.5.1 Choosing the Learning Rate η 7.5.2 Conjugate Gradient Minimization 7.6 Deep Learning: Networks with Many Layers 7.6.1 A Greedy Deep Learning Algorithm 7.7 Problems 8. Support Vector Machines 8.1 The Optimal Hyperplane 8.1.1 Finding the Fattest Separating Hyperplane 8.1.2 Is a Fat Separator Better? 8.1.3 Non-Separable Data 8.2 Dual Formulation of the SVM 8.2.1 Lagrange Dual for a QP-Problem 8.2.2 Dual of the Hard-Margin SVM 8.2.3 Recovering the SVM from the Dual Solution 8.3 Kernel Trick for SVM 8.3.1 Kernel Trick via Dual SVM 8.3.2 Choice of Kernels 8.4 Soft-margin SVM 8.5 Problems 9. Learning Aides 9.1 Input Preprocessing 9.2 Dimension Reduction and Feature Selection 9.2.1 Principal Components Analysis (PCA) 9.2.2 Nonlinear Dimension Reduction 9.3 Hints And Invariances 9.3.1 Virtual Examples 9.3.2 Hints Versus Regularization 9.4 Data Cleaning 9.4.1 Using a Simpler Model to Identify Noisy Data 9.4.2 Computing a Validation Leverage Score 9.5 More on Validation 9.5.1 Rademacher Penalties 9.5.2 The Permutation and Bootstrap Penalties 9.5.3 Rademacher Generalization Bound 9.5.4 Out-of-Sample Error Estimates for Regression 9.6 Problems Epilogue Further Reading Appendix A - Proof of the VC Bound A.1 Relating Generalization Error to In-Sample Deviations A.2 Bounding Worst Case Deviation Using the Growth Function A.3 Bounding the Deviation between In-Sample Errors e-Appendix B - Linear Algebra B.1 Basic Properties of Vectors and Matrices B.2 SVD and Pseudo-Inverse B.3 Symmetric Matrices B.3.1 Positive Semi-Definite Matrices B.4 Trace and Determinant B.4.1 Inverse and Determinant Identities B.5 Inner Products, Metrix and Vector Norms B.5.1 Linear Hyperplanes and Quadratic Forms B.6 Vector and Matrix Calculus B.6.1 Multidimensional Integration B.6.2 Matrix Derivatives e-Appendix C - The E-M Algorithm C.1 Derivation of the E-M Algorithm C.2 Problems Cover Preface Contents 1 The Learning Problem 1.1 Problem Setup 1.2 Types of Learning 1.3 Is Learning Feasible? 1.4 Error and Noise 1.5 Problems 2 Training versus Testing 2.1 Theory of Generalization 2.2 Interpreting the Generalization Bound 2.3 Approximation-Generalization Tradeoff 2.4 Problems 3 The Linear Model 3.1 Linear Classification 3.2 Linear Regression 3.3 Logistic Regression 3.4 Nonlinear Transformation 3.5 Problems 4 Overfitting 4.1 When Does Overfitting Occur? 4.2 Regularization 4.3 Validation 4.4 Problems 5 Three Learning Principles 5.1 Occam's Razor 5.2 Sampling Bias 5.3 Data Snooping 5.4 Problems Epilogue Further Reading Appendix A.1 Relating Generalization Error to In-Sample Deviations A.2 Bounding Worst Case Deviation Using the Growth Function A.3 Bounding the Deviation between In-Sample Errors Notation Index Machine learning allows computational systems to adaptively improve their performance with experience accumulated from the observed data. Its techniques are widely applied in engineering, science, finance, and commerce. This book is designed for a short course on machine learning. It is a short course, not a hurried course. From over a decade of teaching this material, we have distilled what we believe to be the core topics that every student of the subject should know. We chose the title `learning from data' that faithfully describes what the subject is about, and made it a point to cover the topics in a story-like fashion. Our hope is that the reader can learn all the fundamentals of the subject by reading the book cover to cover. ---- Learning from data has distinct theoretical and practical tracks. In this book, we balance the theoretical and the practical, the mathematical and the heuristic. Our criterion for inclusion is relevance. Theory that establishes the conceptual framework for learning is included, and so are heuristics that impact the performance of real learning systems. ---- Learning from data is a very dynamic field. Some of the hot techniques and theories at times become just fads, and others gain traction and become part of the field. What we have emphasized in this book are the necessary fundamentals that give any student of learning from data a solid foundation, and enable him or her to venture out and explore further techniques and theories, or perhaps to contribute their own. ---- The authors are professors at California Institute of Technology (Caltech), Rensselaer Polytechnic Institute (RPI), and National Taiwan University (NTU), where this book is the main text for their popular courses on machine learning. The authors also consult extensively with financial and commercial companies on machine learning applications, and have led winning teams in machine learning competitions. 1. The Learning Problem -- 2. Training Versus Testing -- 3. The Linear Model -- 4. Overfitting -- 5. Three Learning Principles -- Epilogue -- Further Reading -- Appendix : Proof Of The Vc Bound -- Notation. Yaser S. Abu-mostafa, Malik Magdon-ismail, Hsuan-tien Lin. Includes Bibliographical References (p. 183-186) And Index.