Pattern Recognition and Machine Learning (Solutions to the Exercises: Tutors’ Edition)

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