Introduction to Machine Learning

Introduction to Machine Learning

---

Alex Smola and S.V.N. Vishwanathan Yahoo! Labs Santa Clara –and– Departments of Statistics and Computer Science Purdue University –and– College of Engineering and Computer Science Australian National University

---

Contents Preface page 1 1 Introduction 3 1.1 A Taste of Machine Learning 3 1.1.1 Applications 3 1.1.2 Data 7 1.1.3 Problems 9 1.2 Probability Theory 12 1.2.1 Random Variables 12 1.2.2 Distributions 13 1.2.3 Mean and Variance 15 1.2.4 Marginalization, Independence, Conditioning, and Bayes Rule 16 1.3 Basic Algorithms 20 1.3.1 Naive Bayes 22 1.3.2 Nearest Neighbor Estimators 24 1.3.3 A Simple Classifier 27 1.3.4 Perceptron 29 1.3.5 K-Means 32 2 Density Estimation 37 2.1 Limit Theorems 37 2.1.1 Fundamental Laws 38 2.1.2 The Characteristic Function 42 2.1.3 Tail Bounds 45 2.1.4 An Example 48 2.2 Parzen Windows 51 2.2.1 Discrete Density Estimation 51 2.2.2 Smoothing Kernel 52 2.2.3 Parameter Estimation 54 2.2.4 Silverman’s Rule 57 2.2.5 Watson-Nadaraya Estimator 59 2.3 Exponential Families 60 2.3.1 Basics 60 v vi 0 Contents 2.3.2 Examples 62 2.4 Estimation 66 2.4.1 Maximum Likelihood Estimation 66 2.4.2 Bias, Variance and Consistency 68 2.4.3 A Bayesian Approach 71 2.4.4 An Example 75 2.5 Sampling 77 2.5.1 Inverse Transformation 78 2.5.2 Rejection Sampler 82 3 Optimization 91 3.1 Preliminaries 91 3.1.1 Convex Sets 92 3.1.2 Convex Functions 92 3.1.3 Subgradients 96 3.1.4 Strongly Convex Functions 97 3.1.5 Convex Functions with Lipschitz Continous Gradient 98 3.1.6 Fenchel Duality 98 3.1.7 Bregman Divergence 100 3.2 Unconstrained Smooth Convex Minimization 102 3.2.1 Minimizing a One-Dimensional Convex Function 102 3.2.2 Coordinate Descent 104 3.2.3 Gradient Descent 104 3.2.4 Mirror Descent 108 3.2.5 Conjugate Gradient 111 3.2.6 Higher Order Methods 115 3.2.7 Bundle Methods 121 3.3 Constrained Optimization 125 3.3.1 Projection Based Methods 125 3.3.2 Lagrange Duality 127 3.3.3 Linear and Quadratic Programs 131 3.4 Stochastic Optimization 135 3.4.1 Stochastic Gradient Descent 136 3.5 Nonconvex Optimization 137 3.5.1 Concave-Convex Procedure 137 3.6 Some Practical Advice 139 4 Online Learning and Boosting 143 4.1 Halving Algorithm 143 4.2 Weighted Majority 144 Contents vii 5 Conditional Densities 149 5.1 Logistic Regression 150 5.2 Regression 151 5.2.1 Conditionally Normal Models 151 5.2.2 Posterior Distribution 151 5.2.3 Heteroscedastic Estimation 151 5.3 Multiclass Classification 151 5.3.1 Conditionally Multinomial Models 151 5.4 What is a CRF? 152 5.4.1 Linear Chain CRFs 152 5.4.2 Higher Order CRFs 152 5.4.3 Kernelized CRFs 152 5.5 Optimization Strategies 152 5.5.1 Getting Started 152 5.5.2 Optimization Algorithms 152 5.5.3 Handling Higher order CRFs 152 5.6 Hidden Markov Models 153 5.7 Further Reading 153 5.7.1 Optimization 153 6 Kernels and Function Spaces 155 6.1 The Basics 155 6.1.1 Examples 156 6.2 Kernels 161 6.2.1 Feature Maps 161 6.2.2 The Kernel Trick 161 6.2.3 Examples of Kernels 161 6.3 Algorithms 161 6.3.1 Kernel Perceptron 161 6.3.2 Trivial Classifier 161 6.3.3 Kernel Principal Component Analysis 161 6.4 Reproducing Kernel Hilbert Spaces 161 6.4.1 Hilbert Spaces 163 6.4.2 Theoretical Properties 163 6.4.3 Regularization 163 6.5 Banach Spaces 164 6.5.1 Properties 164 6.5.2 Norms and Convex Sets 164 7 Linear Models 165 7.1 Support Vector Classification 165 viii 0 Contents 7.1.1 A Regularized Risk Minimization Viewpoint 170 7.1.2 An Exponential Family Interpretation 170 7.1.3 Specialized Algorithms for Training SVMs 172 7.2 Extensions 177 7.2.1 The ν trick 177 7.2.2 Squared Hinge Loss 179 7.2.3 Ramp Loss 180 7.3 Support Vector Regression 181 7.3.1 Incorporating General Loss Functions 184 7.3.2 Incorporating the ν Trick 186 7.4 Novelty Detection 186 7.5 Margins and Probability 189 7.6 Beyond Binary Classification 189 7.6.1 Multiclass Classification 190 7.6.2 Multilabel Classification 191 7.6.3 Ordinal Regression and Ranking 192 7.7 Large Margin Classifiers with Structure 193 7.7.1 Margin 193 7.7.2 Penalized Margin 193 7.7.3 Nonconvex Losses 193 7.8 Applications 193 7.8.1 Sequence Annotation 193 7.8.2 Matching 193 7.8.3 Ranking 193 7.8.4 Shortest Path Planning 193 7.8.5 Image Annotation 193 7.8.6 Contingency Table Loss 193 7.9 Optimization 193 7.9.1 Column Generation 193 7.9.2 Bundle Methods 193 7.9.3 Overrelaxation in the Dual 193 7.10 CRFs vs Structured Large Margin Models 194 7.10.1 Loss Function 194 7.10.2 Dual Connections 194 7.10.3 Optimization 194 Appendix 1 Linear Algebra and Functional Analysis 197 Appendix 2 Conjugate Distributions 201 Appendix 3 Loss Functions 203 Bibliography 221

---