Machine Learning A Probabilistic Approach David Barber http://www.idiap.ch/ barber ∼ c David Barber 2001, 2002,2003,2004,2006 (cid:13) Contents 1 Introduction 2 1.1 Machine Learning. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Unsupervised Learning. . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Supervised Learning . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Supervised Learning Approaches . . . . . . . . . . . . . . . . . . . 4 I Machine Learning : More Traditional Approaches 8 2 Generalisation 9 2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Supervised Learning . . . . . . . . . . . . . . . . . . . . . . 9 2.1.2 Training Error . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.3 Test Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.4 Validation Data. . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.5 Dodgy Joe and Lucky Jim . . . . . . . . . . . . . . . . . . . 11 2.1.6 Regularisation . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 Nearest Neighbour Classification 15 3.1 Nearest Neighbour . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.1 Problems with Nearest Neighbours . . . . . . . . . . . . . . 17 3.2 K Nearest Neighbours . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Handwritten digit Example . . . . . . . . . . . . . . . . . . . . . . 18 3.4 A Probabilistic Intepretation . . . . . . . . . . . . . . . . . . . . . 19 1 Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006 2 (cid:13) 4 Linear Dimension Reduction 21 4.1 Principal Components Analysis . . . . . . . . . . . . . . . . . . . . 21 4.1.1 Example : Reducing the dimension of digits . . . . . . . . . 24 4.1.2 PCA and Nearest Neighbours . . . . . . . . . . . . . . . . . 24 4.1.3 Mega Dimensional Data . . . . . . . . . . . . . . . . . . . . 25 4.1.4 PCA is good because it is a poor compressor! . . . . . . . . 25 4.2 Deriving the Optimal Linear Reconstruction . . . . . . . . . . . . . 26 4.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Linear Discriminant Analysis 32 5.1 Unsupervised Dimension Reduction. . . . . . . . . . . . . . . . . . 32 5.1.1 Using PCA for visualisation . . . . . . . . . . . . . . . . . . 32 5.2 Fishers Linear Discriminant . . . . . . . . . . . . . . . . . . . . . . 32 5.2.1 One dimensional projection . . . . . . . . . . . . . . . . . . 33 5.3 Canonical Variates . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.3.1 Using Canonical variates on the Digits Data . . . . . . . . . 35 6 Linear Parameter Models 36 6.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.1.1 Regressionand PCA . . . . . . . . . . . . . . . . . . . . . . 37 6.2 Linear Parameter Models (Generalised Linear Models) . . . . . . . 37 6.2.1 Training LPMs . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.2.2 Regularisationand numerical stability . . . . . . . . . . . . 39 6.2.3 Higher Dimensional Outputs . . . . . . . . . . . . . . . . . 39 6.2.4 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.3 Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.4 The curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . 40 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 7 Layered Neural Networks 42 7.1 Sequential Layered Processing . . . . . . . . . . . . . . . . . . . . . 42 7.2 The Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7.3 Multilayer Perceptrons . . . . . . . . . . . . . . . . . . . . . . . . . 43 7.3.1 Understanding Neural Networks . . . . . . . . . . . . . . . 44 7.4 Training multi-layered perceptrons . . . . . . . . . . . . . . . . . . 46 Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006 3 (cid:13) 7.4.1 Single Hidden Layer . . . . . . . . . . . . . . . . . . . . . . 47 7.4.2 Back Propagation . . . . . . . . . . . . . . . . . . . . . . . 48 7.4.3 Training ensembles of networks . . . . . . . . . . . . . . . . 48 7.5 Adaptive Basis Function Networks . . . . . . . . . . . . . . . . . . 49 7.5.1 Adaptive Basis Functions . . . . . . . . . . . . . . . . . . . 49 7.6 Training Adaptive Basis Functions . . . . . . . . . . . . . . . . . . 50 7.6.1 Non-local Basis Functions . . . . . . . . . . . . . . . . . . . 51 7.7 Committees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.8 Summary and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . 53 8 Autoencoders 54 8.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 8.1.1 Linear Dimension Reduction (PCA) . . . . . . . . . . . . . 54 8.1.2 Manifolds : The need for non-linearity . . . . . . . . . . . . 54 8.2 Non-linear Dimension Reduction . . . . . . . . . . . . . . . . . . . 55 8.2.1 Training Autoencoders . . . . . . . . . . . . . . . . . . . . . 55 8.3 Uses of Autoencoders . . . . . . . . . . . . . . . . . . . . . . . . . 56 8.3.1 A Visualisation example . . . . . . . . . . . . . . . . . . . . 57 9 Data Visualisation 58 9.1 Classical Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 9.1.1 Finding the optimal points . . . . . . . . . . . . . . . . . . 59 9.1.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 60 9.2 Sammon Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 9.3 A word of warning . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 II Inference and Learning in Probabilistic Models 63 10 Introducing Graphical Models 64 10.1 Belief Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 10.1.1 Tracey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 10.2 A word on notation. . . . . . . . . . . . . . . . . . . . . . . . . . . 67 10.3 Example : Was it the Burglar? . . . . . . . . . . . . . . . . . . . . 67 10.4 Belief Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 10.4.1 Conditional Independence . . . . . . . . . . . . . . . . . . . 70 10.4.2 Intuition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006 4 (cid:13) 10.4.3 d-Separation . . . . . . . . . . . . . . . . . . . . . . . . . . 71 10.5 Graphical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 10.5.1 Markov Random Fields . . . . . . . . . . . . . . . . . . . . 75 10.5.2 Expressiveness of Graphical Models . . . . . . . . . . . . . 76 10.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 11 Inference in Belief Networks 80 11.1 Inference. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 11.2 Variable Elimination in a simple chain . . . . . . . . . . . . . . . . 80 11.3 Bucket Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 11.4 Belief Propagtion: Inference in Singly Connected Graphs . . . . . 84 11.4.1 Undirected Belief Propagation . . . . . . . . . . . . . . . . 85 11.4.2 Directed Belief Propagation . . . . . . . . . . . . . . . . . . 86 11.4.3 Example : Directed Belief Propagation. . . . . . . . . . . . 89 11.5 Belief Revision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 11.6 The Generalised Distributive Law. . . . . . . . . . . . . . . . . . . 92 11.7 Inference in Multiply-Connected Graphs . . . . . . . . . . . . . . . 93 11.7.1 Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . . 94 11.8 Cluster Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 11.9 KL divergence approach to marginalisation on Trees . . . . . . . . 97 11.10Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 11.11Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 12 The Junction Tree Algorithm 107 12.1 Absorption and Marginal Consistency . . . . . . . . . . . . . . . . 107 12.2 Junction Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 12.3 Constructing Junction Trees for Singly-Connected Distributions . . 111 12.4 Junction Trees for Multiply-Connected Distributions . . . . . . . . 113 12.5 Triangulation Algorithms . . . . . . . . . . . . . . . . . . . . . . . 115 12.6 Finding a JT from a Triangulated Graph . . . . . . . . . . . . . . 116 12.7 The Junction Tree Algorithm . . . . . . . . . . . . . . . . . . . . . 116 12.7.1 Finding the Most Likely State . . . . . . . . . . . . . . . . 117 12.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 12.9 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006 5 (cid:13) 13 Variational Learning and EM 121 13.1 Maximum Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . . 121 13.1.1 Missing Data/Variables . . . . . . . . . . . . . . . . . . . . 124 13.2 Variational Learning and Expectation Maximisation . . . . . . . . 125 13.3 Optimising the Likelihood by Gradient methods . . . . . . . . . . 133 13.4 Iterated ProportionalFitting . . . . . . . . . . . . . . . . . . . . . 134 13.5 BayesianMethods and ML-II . . . . . . . . . . . . . . . . . . . . . 135 13.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 13.7 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 III Probabilistic models in Machine Learning 139 14 Introduction to Bayesian Methods 140 14.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 14.2 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 15 Bayesian Regression 152 15.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 15.2 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 16 Logistic Regression 156 16.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 16.1.1 Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 16.1.2 Gradient Ascent . . . . . . . . . . . . . . . . . . . . . . . . 159 16.1.3 Avoiding Overconfident Classification . . . . . . . . . . . . 162 16.1.4 Logistic Regression and PCA ? . . . . . . . . . . . . . . . . 162 16.1.5 An Example : Classifying Handwritten Digits . . . . . . . . 163 16.2 The Kernel Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 16.3 Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 16.3.1 Mixtures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 16.3.2 Mixture of Experts . . . . . . . . . . . . . . . . . . . . . . . 166 16.3.3 A ‘Bayesian’ approach to setting the regularisationparameter167 16.3.4 Evidence Procedure . . . . . . . . . . . . . . . . . . . . . . 168 16.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 16.5 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006 6 (cid:13) 17 Naive Bayes 173 17.1 Why Naive Bayes? . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 17.2 Understanding Conditional Independence . . . . . . . . . . . . . . 173 17.3 Are they Scottish? . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 17.3.1 Further Issues. . . . . . . . . . . . . . . . . . . . . . . . . . 175 17.3.2 Text Classification . . . . . . . . . . . . . . . . . . . . . . . 176 17.4 Pitfalls with Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . 176 17.5 Estimation using Maximum Likelihood : Bernoulli Process. . . . . 177 17.5.1 Classification Boundary . . . . . . . . . . . . . . . . . . . . 178 17.6 Naive Bayes : The multinomial case . . . . . . . . . . . . . . . . . 178 17.6.1 Dirichlet Prior . . . . . . . . . . . . . . . . . . . . . . . . . 179 17.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 17.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 18 Mixture Models : Discrete Hidden Variables 183 18.1 Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 18.2 Gaussian Mixture Models . . . . . . . . . . . . . . . . . . . . . . . 185 18.3 K Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 18.3.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 190 18.3.2 Uses of K Means . . . . . . . . . . . . . . . . . . . . . . . . 191 18.4 Classification using Mixture Models . . . . . . . . . . . . . . . . . 191 18.5 Mixture of Multi-nomials . . . . . . . . . . . . . . . . . . . . . . . 192 18.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 18.7 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 19 Factor Analysis and PPCA 197 19.1 Linear Subspace Methods . . . . . . . . . . . . . . . . . . . . . . . 197 19.2 A Toy Comparision of FA and PPCA . . . . . . . . . . . . . . . . 202 19.3 Non-linear Subspace Methods . . . . . . . . . . . . . . . . . . . . . 204 19.3.1 Non linear Factor Analysis . . . . . . . . . . . . . . . . . . 204 19.4 Probabilistic PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 19.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 19.6 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006 7 (cid:13) 20 Dynamic Bayesian Networks : Discrete Hidden Variables 210 20.1 The Importance of Time . . . . . . . . . . . . . . . . . . . . . . . . 210 20.1.1 Paralleland Sequential Inference . . . . . . . . . . . . . . . 214 20.1.2 Rauch Tung Striebel and the α γ recursions. . . . . . . . 217 − 20.1.3 Viterbi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 20.2 Applications of HMMs . . . . . . . . . . . . . . . . . . . . . . . . . 223 20.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 20.4 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 21 Dynamic Continuous Hiddens : Linear Dynamical Systems 229 21.1 Inference. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 21.1.1 The Forward Pass : The Kalman Filter . . . . . . . . . . . 230 21.1.2 The Kalman Smoother : The Rauch-Tung-Striebel Smoother 231 21.1.3 The Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . 233 21.2 EM Algorithm for Learning . . . . . . . . . . . . . . . . . . . . . . 233 21.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 21.4 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 22 Switching Linear Dynamical Systems 237 22.1 Expectation Correction . . . . . . . . . . . . . . . . . . . . . . . . 238 22.1.1 ForwardPass (Filtering) . . . . . . . . . . . . . . . . . . . . 238 22.1.2 Collapsing Gaussians . . . . . . . . . . . . . . . . . . . . . . 240 22.1.3 BackwardPass (Smoothing) . . . . . . . . . . . . . . . . . . 241 22.1.4 Remarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 22.1.5 Using Mixtures in the BackwardPass . . . . . . . . . . . . 245 22.2 Relation to other methods . . . . . . . . . . . . . . . . . . . . . . . 246 23 Gaussian Processes 250 23.1 The Bayesianapproach to Regression. . . . . . . . . . . . . . . . . 250 23.1.1 ParameterisedModels . . . . . . . . . . . . . . . . . . . . . 251 23.1.2 Making Predictions. . . . . . . . . . . . . . . . . . . . . . . 251 23.1.3 Model Selection. . . . . . . . . . . . . . . . . . . . . . . . . 251 23.2 Generalised Linear Models . . . . . . . . . . . . . . . . . . . . . . . 251 23.2.1 Understanding the Prior . . . . . . . . . . . . . . . . . . . . 252 23.2.2 Sampling the function space prior . . . . . . . . . . . . . . 252 23.2.3 Understanding the Posterior. . . . . . . . . . . . . . . . . . 253 Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006 8 (cid:13) 23.2.4 Understanding Model Selection Issues . . . . . . . . . . . . 253 23.3 Gaussian Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 23.3.1 Specifying the Prior . . . . . . . . . . . . . . . . . . . . . . 254 23.3.2 Making Predictions. . . . . . . . . . . . . . . . . . . . . . . 255 23.3.3 Model Selection. . . . . . . . . . . . . . . . . . . . . . . . . 256 23.3.4 Classification problems. . . . . . . . . . . . . . . . . . . . . 256 23.4 Gaussian Processes for Classification . . . . . . . . . . . . . . . . . 257 23.4.1 Maximizing P(y ,y t) . . . . . . . . . . . . . . . . . . . . . 258 ∗ | 23.4.2 Parameterizingthe covariance function. . . . . . . . . . . . 259 23.4.3 Integration over the hyperparameters . . . . . . . . . . . . 259 23.5 Multiple classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 23.5.1 Finding the mode of the distribution . . . . . . . . . . . . . 261 23.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 IV Approximate Inference Methods 264 24 Sampling 265 24.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 24.2 Markov Chain Monte Carlo (MCMC) . . . . . . . . . . . . . . . . 269 A Basic Concepts in Probability 283 A.1 What does random mean? . . . . . . . . . . . . . . . . . . . . . . . 283 A.2 What is Probability? . . . . . . . . . . . . . . . . . . . . . . . . . . 283 A.3 Rules of Probability . . . . . . . . . . . . . . . . . . . . . . . . . . 284 B Graph Terminology: 286 B.1 Graphs : Basic Concepts and Definitions . . . . . . . . . . . . . . . 286 B.2 Basic Concepts and Definitions . . . . . . . . . . . . . . . . . . . . 286 B.2.1 Undirected Graphs . . . . . . . . . . . . . . . . . . . . . . . 287 B.2.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . 289 C Some Standard Distributions: 291 D Bounds on Convex Functions 292 D.1 Kullback Leibler Divergence KL(q p) . . . . . . . . . . . . . . . . 292 || D.1.1 Jensen vs Variational Jensen . . . . . . . . . . . . . . . . . 293 Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006 9 (cid:13) E Positive Definite Matrices and Kernel Functions: 294 F Approximating Integrals: 298 G Inference with Gaussian Random Variables 299 G.1 Gaussian Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . 300 G.2 Gaussian Propagation . . . . . . . . . . . . . . . . . . . . . . . . . 300