Reference: [Alex Smola 2010] Introduction To Machine Learning

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 Classier 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 Classication 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 Classier 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 Classication 165