A Course in Machine Learning

CIML is a set of introductory materials that covers most major aspects of modern machine learning (supervised learning, unsupervised learning, large margin methods, probabilistic modeling, learning theory, etc.). It's focus is on broad applications with a rigorous backbone. A subset can be used for an undergraduate course; a graduate course could probably cover the entire material and then some. About this Book 6 How to Use this Book 6 Why Another Textbook? 6 Organization and Auxilary Material 7 Acknowledgements 7 Decision Trees 8 What Does it Mean to Learn? 8 Some Canonical Learning Problems 10 The Decision Tree Model of Learning 10 Formalizing the Learning Problem 14 Chapter Summary and Outlook 17 Further Reading 18 Limits of Learning 19 Data Generating Distributions 19 Inductive Bias: What We Know Before the Data Arrives 20 Not Everything is Learnable 21 Underfitting and Overfitting 22 Separation of Training and Test Data 24 Models, Parameters and Hyperparameters 25 Real World Applications of Machine Learning 27 Further Reading 28 Geometry and Nearest Neighbors 29 From Data to Feature Vectors 29 K-Nearest Neighbors 31 Decision Boundaries 34 K-Means Clustering 35 Warning: High Dimensions are Scary 37 Further Reading 40 The Perceptron 41 Bio-inspired Learning 41 Error-Driven Updating: The Perceptron Algorithm 42 Geometric Intrepretation 45 Interpreting Perceptron Weights 47 Perceptron Convergence and Linear Separability 48 Improved Generalization: Voting and Averaging 51 Limitations of the Perceptron 53 Further Reading 54 Practical Issues 55 The Importance of Good Features 55 Irrelevant and Redundant Features 56 Feature Pruning and Normalization 58 Combinatorial Feature Explosion 61 Evaluating Model Performance 62 Cross Validation 64 Hypothesis Testing and Statistical Significance 67 Debugging Learning Algorithms 69 Bias/Variance Trade-off 71 Further Reading 72 Beyond Binary Classification 73 Learning with Imbalanced Data 73 Multiclass Classification 77 Ranking 81 Further Reading 86 Linear Models 87 The Optimization Framework for Linear Models 87 Convex Surrogate Loss Functions 89 Weight Regularization 91 Optimization with Gradient Descent 93 From Gradients to Subgradients 96 Closed-form Optimization for Squared Loss 97 Support Vector Machines 100 Further Reading 103 Bias and Fairness 104 Train/Test Mismatch 104 Unsupervised Adaptation 106 Supervised Adaptation 108 Fairness and Data Bias 110 How Badly can it Go? 112 Further Reading 115 Probabilistic Modeling 116 Classification by Density Estimation 116 Statistical Estimation 117 Naive Bayes Models 120 Prediction 121 Generative Stories 123 Conditional Models 124 Regularization via Priors 126 Further Reading 128 Neural Networks 129 Bio-inspired Multi-Layer Networks 129 The Back-propagation Algorithm 132 Initialization and Convergence of Neural Networks 135 Beyond Two Layers 136 Breadth versus Depth 138 Basis Functions 139 Further Reading 140 Kernel Methods 141 From Feature Combinations to Kernels 141 Kernelized Perceptron 142 Kernelized K-means 144 What Makes a Kernel 145 Support Vector Machines 148 Understanding Support Vector Machines 151 Further Reading 153 Learning Theory 154 The Role of Theory 154 Induction is Impossible 155 Probably Approximately Correct Learning 156 PAC Learning of Conjunctions 157 Occam's Razor: Simple Solutions Generalize 160 Complexity of Infinite Hypothesis Spaces 161 Further Reading 163 Ensemble Methods 164 Voting Multiple Classifiers 164 Boosting Weak Learners 166 Random Ensembles 169 Further Reading 170 Efficient Learning 171 What Does it Mean to be Fast? 171 Stochastic Optimization 172 Sparse Regularization 174 Feature Hashing 176 Further Reading 177 Unsupervised Learning 178 K-Means Clustering, Revisited 178 Linear Dimensionality Reduction 182 Autoencoders 185 Further Reading 185 Expectation Maximization 186 Grading an Exam without an Answer Key 186 Clustering with a Mixture of Gaussians 189 The Expectation Maximization Framework 191 Further Reading 194 Structured Prediction 195 Multiclass Perceptron 196 Structured Perceptron 198 Argmax for Sequences 199 Structured Support Vector Machines 202 Loss-Augmented Argmax 205 Argmax in General 206 Dynamic Programming for Sequences 208 Further Reading 211 Imitation Learning 212 Imitation Learning by Classification 213 Failure Analysis 215 Dataset Aggregation 216 Expensive Algorithms as Experts 218 Structured Prediction via Imitation Learning 219 Further Reading 221 Code and Datasets 222 Bibliography 223 Index 225