Pattern Recognition and Machine Learning (Information Science and Statistics)

This is the first textbook on pattern recognition to present the Bayesian viewpoint. The book presents approximate inference algorithms that permit fast approximate answers in situations where exact answers are not feasible. It uses graphical models to describe probability distributions when no other books apply graphical models to machine learning. No previous knowledge of pattern recognition or machine learning concepts is assumed. Familiarity with multivariate calculus and basic linear algebra is required, and some experience in the use of probabilities would be helpful though not essential as the book includes a self-contained introduction to basic probability theory. Cover......Page 1 Title Page......Page 5 Preface......Page 9 Acknowledgements......Page 10 Mathematical notation......Page 13 Contents......Page 15 1 Introduction......Page 23 1.1 Example: Polynomial Curve Fitting......Page 26 1.2 Probability Theory......Page 34 1.2.1 Probability densities......Page 39 1.2.2 Expectations and covariances......Page 41 1.2.3 Bayesian probabilities......Page 43 1.2.4 The Gaussian distribution......Page 46 1.2.5 Curve fitting re-visited......Page 50 1.2.6 Bayesian curve fitting......Page 52 1.3 Model Selection......Page 54 1.4 The Curse of Dimensionality......Page 55 1.5 Decision Theory......Page 60 1.5.1 Minimizing the misclassification rate......Page 61 1.5.2 Minimizing the expected loss......Page 63 1.5.4 Inference and decision......Page 64 1.5.5 Loss functions for regression......Page 68 1.6 Information Theory......Page 70 1.6.1 Relative entropy and mutual information......Page 77 Exercises......Page 80 2 Probability Distributions......Page 89 2.1 Binary Variables......Page 90 2.1.1 The beta distribution......Page 93 2.2 Multinomial Variables......Page 96 2.2.1 The Dirichlet distribution......Page 98 2.3 The Gaussian Distribution......Page 100 2.3.1 Conditional Gaussian distributions......Page 107 2.3.2 Marginal Gaussian distributions......Page 110 2.3.3 Bayes’ theorem for Gaussian variables......Page 112 2.3.4 Maximum likelihood for the Gaussian......Page 115 2.3.5 Sequential estimation......Page 116 2.3.6 Bayesian inference for the Gaussian......Page 119 2.3.7 Student’s t-distribution......Page 124 2.3.8 Periodic variables......Page 127 2.3.9 Mixtures of Gaussians......Page 132 2.4 The Exponential Family......Page 135 2.4.1 Maximum likelihood and sufficient statistics......Page 138 2.4.3 Noninformative priors......Page 139 2.5 Nonparametric Methods......Page 142 2.5.1 Kernel density estimators......Page 144 2.5.2 Nearest-neighbour methods......Page 146 Exercises......Page 149 3 Linear Models for Regression......Page 159 3.1 Linear Basis Function Models......Page 160 3.1.1 Maximum likelihood and least squares......Page 162 3.1.3 Sequential learning......Page 165 3.1.4 Regularized least squares......Page 166 3.1.5 Multiple outputs......Page 168 3.2 The Bias-Variance Decomposition......Page 169 3.3.1 Parameter distribution......Page 174 3.3.2 Predictive distribution......Page 178 3.3.3 Equivalent kernel......Page 181 3.4 Bayesian Model Comparison......Page 183 3.5 The Evidence Approximation......Page 187 3.5.1 Evaluation of the evidence function......Page 188 3.5.2 Maximizing the evidence function......Page 190 3.5.3 Effective number of parameters......Page 192 3.6 Limitations of Fixed Basis Functions......Page 194 Exercises......Page 195 4 Linear Models for Classification......Page 201 4.1.1 Two classes......Page 203 4.1.2 Multiple classes......Page 204 4.1.3 Least squares for classification......Page 206 4.1.4 Fisher’s linear discriminant......Page 208 4.1.5 Relation to least squares......Page 211 4.1.6 Fisher’s discriminant for multiple classes......Page 213 4.1.7 The perceptron algorithm......Page 214 4.2 Probabilistic Generative Models......Page 218 4.2.1 Continuous inputs......Page 220 4.2.2 Maximum likelihood solution......Page 222 4.2.4 Exponential family......Page 224 4.3 Probabilistic Discriminative Models......Page 225 4.3.1 Fixed basis functions......Page 226 4.3.2 Logistic regression......Page 227 4.3.3 Iterative reweighted least squares......Page 229 4.3.4 Multiclass logistic regression......Page 231 4.3.5 Probit regression......Page 232 4.3.6 Canonical link functions......Page 234 4.4 The Laplace Approximation......Page 235 4.4.1 Model comparison and BIC......Page 238 4.5.1 Laplace approximation......Page 239 4.5.2 Predictive distribution......Page 240 Exercises......Page 242 5 Neural Networks......Page 247 5.1 Feed-forward Network Functions......Page 249 5.1.1 Weight-space symmetries......Page 253 5.2 Network Training......Page 254 5.2.1 Parameter optimization......Page 258 5.2.2 Local quadratic approximation......Page 259 5.2.3 Use of gradient information......Page 261 5.2.4 Gradient descent optimization......Page 262 5.3 Error Backpropagation......Page 263 5.3.1 Evaluation of error-function derivatives......Page 264 5.3.2 A simple example......Page 267 5.3.3 Efficiency of backpropagation......Page 268 5.3.4 The Jacobian matrix......Page 269 5.4 The Hessian Matrix......Page 271 5.4.1 Diagonal approximation......Page 272 5.4.2 Outer product approximation......Page 273 5.4.4 Finite differences......Page 274 5.4.5 Exact evaluation of the Hessian......Page 275 5.4.6 Fast multiplication by the Hessian......Page 276 5.5 Regularization in Neural Networks......Page 278 5.5.1 Consistent Gaussian priors......Page 279 5.5.2 Early stopping......Page 281 5.5.3 Invariances......Page 283 5.5.4 Tangent propagation......Page 285 5.5.5 Training with transformed data......Page 287 5.5.6 Convolutional networks......Page 289 5.5.7 Soft weight sharing......Page 291 5.6 Mixture Density Networks......Page 294 5.7. Bayesian Neural Networks......Page 299 5.7.1 Posterior parameter distribution......Page 300 5.7.2 Hyperparameter optimization......Page 302 5.7.3 Bayesian neural networks for classification......Page 303 Exercises......Page 306 6 Kernel Methods......Page 313 6.1 Dual Representations......Page 315 6.2 Constructing Kernels......Page 316 6.3 Radial Basis Function Networks......Page 321 6.3.1 Nadaraya-Watson model......Page 323 6.4 Gaussian Processes......Page 325 6.4.1 Linear regression revisited......Page 326 6.4.2 Gaussian processes for regression......Page 328 6.4.3 Learning the hyperparameters......Page 333 6.4.4 Automatic relevance determination......Page 334 6.4.5 Gaussian processes for classification......Page 335 6.4.6 Laplace approximation......Page 337 6.4.7 Connection to neural networks......Page 341 Exercises......Page 342 7 Sparse Kernel Machines......Page 347 7.1 Maximum Margin Classifiers......Page 348 7.1.1 Overlapping class distributions......Page 353 7.1.2 Relation to logistic regression......Page 358 7.1.3 Multiclass SVMs......Page 360 7.1.4 SVMs for regression......Page 361 7.1.5 Computational learning theory......Page 366 7.2.1 RVM for regression......Page 367 7.2.2 Analysis of sparsity......Page 371 7.2.3 RVM for classification......Page 375 Exercises......Page 379 8 Graphical Models......Page 381 8.1 Bayesian Networks......Page 382 8.1.1 Example: Polynomial regression......Page 384 8.1.2 Generative models......Page 387 8.1.3 Discrete variables......Page 388 8.1.4 Linear-Gaussian models......Page 392 8.2 Conditional Independence......Page 394 8.2.1 Three example graphs......Page 395 8.2.2 D-separation......Page 400 8.3.1 Conditional independence properties......Page 405 8.3.2 Factorization properties......Page 406 8.3.3 Illustration: Image de-noising......Page 409 8.3.4 Relation to directed graphs......Page 412 8.4 Inference in Graphical Models......Page 415 8.4.1 Inference on a chain......Page 416 8.4.2 Trees......Page 420 8.4.3 Factor graphs......Page 421 8.4.4 The sum-product algorithm......Page 424 8.4.5 The max-sum algorithm......Page 433 8.4.6 Exact inference in general graphs......Page 438 8.4.7 Loopy belief propagation......Page 439 Exercises......Page 440 9 Mixture Models and EM......Page 445 9.1 K-means Clustering......Page 446 9.1.1 Image segmentation and compression......Page 450 9.2 Mixtures of Gaussians......Page 452 9.2.1 Maximum likelihood......Page 454 9.2.2 EM for Gaussian mixtures......Page 457 9.3 An Alternative View of EM......Page 461 9.3.1 Gaussian mixtures revisited......Page 463 9.3.2 Relation to K-means......Page 465 9.3.3 Mixtures of Bernoulli distributions......Page 466 9.3.4 EM for Bayesian linear regression......Page 470 9.4 The EM Algorithm in General......Page 472 Exercises......Page 477 10 Approximate Inference......Page 483 10.1 Variational Inference......Page 484 10.1.1 Factorized distributions......Page 486 10.1.2 Properties of factorized approximations......Page 488 10.1.3 Example: The univariate Gaussian......Page 492 10.1.4 Model comparison......Page 495 10.2 Illustration: Variational Mixture of Gaussians......Page 496 10.2.1 Variational distribution......Page 497 10.2.2 Variational lower bound......Page 503 10.2.3 Predictive density......Page 504 10.2.4 Determining the number of components......Page 505 10.2.5 Induced factorizations......Page 507 10.3.1 Variational distribution......Page 508 10.3.2 Predictive distribution......Page 510 10.3.3 Lower bound......Page 511 10.4 Exponential Family Distributions......Page 512 10.4.1 Variational message passing......Page 513 10.5 Local Variational Methods......Page 515 10.6.1 Variational posterior distribution......Page 520 10.6.2 Optimizing the variational parameters......Page 522 10.6.3 Inference of hyperparameters......Page 524 10.7 Expectation Propagation......Page 527 10.7.1 Example: The clutter problem......Page 533 10.7.2 Expectation propagation on graphs......Page 535 Exercises......Page 539 11 Sampling Methods......Page 545 11.1.1 Standard distributions......Page 548 11.1.2 Rejection sampling......Page 550 11.1.3 Adaptive rejection sampling......Page 552 11.1.4 Importance sampling......Page 554 11.1.5 Sampling-importance-resampling......Page 556 11.1.6 Sampling and the EM algorithm......Page 558 11.2 Markov Chain Monte Carlo......Page 559 11.2.1 Markov chains......Page 561 11.2.2 The Metropolis-Hastings algorithm......Page 563 11.3 Gibbs Sampling......Page 564 11.4 Slice Sampling......Page 568 11.5.1 Dynamical systems......Page 570 11.5.2 Hybrid Monte Carlo......Page 574 11.6 Estimating the Partition Function......Page 576 Exercises......Page 578 12 Continuous Latent Variables......Page 581 12.1.1 Maximum variance formulation......Page 583 12.1.2 Minimum-error formulation......Page 585 12.1.3 Applications of PCA......Page 587 12.1.4 PCA for high-dimensional data......Page 591 12.2 Probabilistic PCA......Page 592 12.2.1 Maximum likelihood PCA......Page 596 12.2.2 EM algorithm for PCA......Page 599 12.2.3 Bayesian PCA......Page 602 12.2.4 Factor analysis......Page 605 12.3 Kernel PCA......Page 608 12.4.1 Independent component analysis......Page 613 12.4.2 Autoassociative neural networks......Page 614 12.4.3 Modelling nonlinear manifolds......Page 617 Exercises......Page 621 13 Sequential Data......Page 627 13.1 Markov Models......Page 629 13.2 Hidden Markov Models......Page 632 13.2.1 Maximum likelihood for the HMM......Page 637 13.2.2 The forward-backward algorithm......Page 640 13.2.3 The sum-product algorithm for the HMM......Page 647 13.2.4 Scaling factors......Page 649 13.2.5 The Viterbi algorithm......Page 651 13.2.6 Extensions of the hidden Markov model......Page 653 13.3 Linear Dynamical Systems......Page 657 13.3.1 Inference in LDS......Page 660 13.3.2 Learning in LDS......Page 664 13.3.3 Extensions of LDS......Page 666 13.3.4 Particle filters......Page 667 Exercises......Page 668 14 Combining Models......Page 675 14.1 Bayesian Model Averaging......Page 676 14.2 Committees......Page 677 14.3 Boosting......Page 679 14.3.1 Minimizing exponential error......Page 681 14.3.2 Error functions for boosting......Page 683 14.4 Tree-based Models......Page 685 14.5 Conditional Mixture Models......Page 688 14.5.1 Mixtures of linear regression models......Page 689 14.5.2 Mixtures of logistic models......Page 692 14.5.3 Mixtures of experts......Page 694 Exercises......Page 696 Handwritten Digits......Page 699 Oil Flow......Page 700 Old Faithful......Page 703 Synthetic Data......Page 704 Bernoulli......Page 707 Binomial......Page 708 Dirichlet......Page 709 Gaussian......Page 710 Multinomial......Page 712 Student’s t......Page 713 Uniform......Page 714 Wishart......Page 715 Basic Matrix Identities......Page 717 Traces and Determinants......Page 718 Matrix Derivatives......Page 719 Eigenvector Equation......Page 720 Appendix D. Calculus of Variations......Page 725 Appendix E. Lagrange Multipliers......Page 729 A......Page 733 B......Page 734 C......Page 736 D......Page 737 G......Page 738 I......Page 740 K......Page 741 L......Page 742 M......Page 743 N......Page 744 P......Page 745 R......Page 746 S......Page 747 T......Page 748 W......Page 749 Z......Page 750 Index......Page 751 Introduction. Example : Polynomial Curve Fitting ; Probability Theory ; Model Selection ; The Curse Of Dimensionality Decision Theory ; Information Theory -- Probability Distributions. Binary Vehicles ; Multinomial Variables ; The Gaussian Distribution ; The Exponential Family ; Nonparametric Methods -- Linear Models For Regression. Linear Basis Function Models ; The Bias-variance Decomposition ; Bayesian Linear Regression ; Bayesian Model Comparison ; The Evidence Approximation ; Limitations Of Fixed Basis Functions -- Linear Models For Classification. Discriminant Functions ; Probabilistic Generative Models ; Probabilistic Discrimitive Models ; The Laplace Approximation ; Bayesian Logistic Regression -- Neural Networks. Feed-forward Network Functions ; Network Training ; Error Backpropagation ; The Hessian Matrix ; Regularization In Neural Networks ; Mixture Density Networks ; Bayesian Neural Networks. Kernel Methods. Dual Representations ; Constructing Kernals ; Radial Basis Function Networks ; Gaussian Processes -- Sparse Kernel Machines. Maximum Margin Classifiers ; Relevance Vector Machines -- Graphical Models. Bayesian Networks ; Conditional Independence ; Markov Random Fields ; Inference In Graphical Models -- Mixture Models And Em. K-means Clustering ; Mixtures Of Gaussians ; An Alternative View Of Em ; The Em Algorithm In General -- Approximate Inference. Variational Inference ; Illustration : Variational Mixture Of Gaussians ; Variational Linear Regression ; Exponential Family Distributions ; Local Variational Methods ; Variational Logistic Regression ; Expectation Propagation -- Sampling Methods. Basic Sampling Algorithms ; Markov Chain Monte Carlo ; Gibbs Sampling ; Slice Sampling ; The Hybrid Monte Carlo Algorithm ; Estimating The Partition Function. Continuous Latent Variables. Principal Component Analysis ; Probabilistic Pca ; Kernel Pca ; Nonlinear Latent Variable Models -- Sequential Data. Markoc Models ; Hidden Markov Models ; Linear Dynamical Systems -- Combining Models. Bayesian Model Averaging ; Committees ; Boosting ; Tree-based Models ; Conditional Mixture Models -- Data Sets -- Probability Distributions -- Properties Of Matrices -- Calculus Of Variations -- Lagrange Multipliers. Christopher M. Bishop. Includes Bibliographical References (p. 711-728) And Index. The dramatic growth in practical applications for machine learning over the last ten years has been accompanied by many important developments in the underlying algorithms and techniques. For example, Bayesian methods have grown from a specialist niche to become mainstream, while graphical models have emerged as a general framework for describing and applying probabilistic techniques. The practical applicability of Bayesian methods has been greatly enhanced by the development of a range of approximate inference algorithms such as variational Bayes and expectation propagation, while new models based on kernels have had a significant impact on both algorithms and applications. This completely new textbook reflects these recent developments while providing a comprehensive introduction to the fields of pattern recognition and machine learning. It is aimed at advanced undergraduates or first-year PhD students, as well as researchers and practitioners. No previous knowledge of pattern recognition or machine learning concepts is assumed. Familiarity with multivariate calculus and basic linear algebra is required, and some experience in the use of probabilities would be helpful though not essential as the book includes a self-contained introduction to basic probability theory. The book is suitable for courses on machine learning, statistics, computer science, signal processing, computer vision, data mining, and bioinformatics. Extensive support is provided for course instructors, including more than 400 exercises, graded according to difficulty. Example solutions for a subset of the exercises are available from the book web site, while solutions for the remainder can be obtained by instructors from the publisher. The book is supported by a great deal of additional material, and the reader is encouraged to visit the book web site for the latest information. Christopher M. Bishop is Deputy Director of Microsoft Research Cambridge, and holds a Chair in Computer Science at the University of Edinburgh. He is a Fellow of Darwin College Cambridge, a Fellow of the Royal Academy of Engineering, and a Fellow of the Royal Society of Edinburgh. His previous textbook "Neural Networks for Pattern Recognition" has been widely adopted Pattern recognition has its origins in engineering, whereas machine learning grew out of computer science. However, these activities can be viewed as two facets of the same field, and together they have undergone substantial development over the past ten years. In particular, Bayesian methods have grown from a specialist niche to become mainstream, while graphical models have emerged as a general framework for describing and applying probabilistic models. Also, the practical applicability of Bayesian methods has been greatly enhanced through the development of a range of approximate inference algorithms such as variational Bayes and expectation propagation. Similarly, new models based on kernels have had a significant impact on both algorithms and applications. This new textbook reflects these recent developments while providing a comprehensive introduction to the fields of pattern recognition and machine learning. It is aimed at advanced undergraduates or first-year PhD students, as well as researchers and practitioners, and assumes no previous knowledge of pattern recognition or machine learning concepts. Knowledge of multivariate calculus and basic linear algebra is required, and some familiarity with probabilities would be helpful though not essential as the book includes a self-contained introduction to basic probability theory.