Summary Pattern Recognition and Machine Learning notes

Solutions to
“Pattern Recognition and Machine Learning”
by Bishop

tommyod @ github

Finished May 2, 2019.
Last updated June 27, 2019.

Abstract

This document contains solutions to selected exercises from the book “Pattern
Recognition and Machine Learning” by Christopher M. Bishop.
Written in 2006, PRML is one of the most popular books in the field of machine
learning. It’s clearly written, never boring and exposes the reader to details without
being terse or dry. At the time of writing, the book has close to 36 000 citations
according to Google.
While short chapter summaries are included in this document, they are not in-
tended to substitute the book in any way. The summaries will largely be meaningless
without the book, which I recommend buying if you’re interested in the subject. The
solutions and notes were typeset in LATEX to facilitate my own learning process.
I hope you find my solutions helpful if you are stuck. Remember to make an
attempt at solving the problems yourself before peeking. More likely than not,
the solutions can be improved by a reader such as yourself. If you would like to
contribute, please submit a pull request at https://github.com/tommyod/lml/.
Several similar projects exist: there’s an official solution manual, a repository
with many solutions at https://github.com/GoldenCheese/PRML-Solution-Manual
and a detailed errata located at https://github.com/yousuketakada/prml_errata.




Figure 1: The front cover of [Bishop, 2006].




1

,Contents
1 Chapter summaries 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Linear Models for Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Linear Models for Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Kernel methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Sparse Kernel Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.8 Graphical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9 Mixture Models and EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.10 Approximate Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.11 Sampling Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.12 Continuous Latent Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.13 Sequential Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.14 Combining Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2 Exercises 31
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3 Linear Models for Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.4 Linear Models for Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5 Neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.6 Kernel methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.7 Sparse Kernel Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.8 Graphical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.9 Mixture Models and EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.10 Approximate Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.11 Sampling Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
2.12 Continuous Latent Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.13 Sequential Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86




2

,1 Chapter summaries
Notation

Scalar data is given by x = (x1 , . . . , xN )T , where N is the number of samples. Vector
data is given by X, which has dimensions N × M , where N is the number of data points
(rows) and M is the dimensionality of the feature space (columns).


Mathematics

Some useful mathematics is summarized here, also see the book appendix.
• The gamma function Γ(x) satisfies Γ(x) = (x − 1)Γ(x − 1), and is given by
Z ∞
Γ(x) = ux−1 e−u du.
0

It’s a “continuous factorial,” which is proved by integration by parts and induction.
• The Jensen inequality states that, for convex functions
!
X X
f λj xj ≤ λj f (xj ),
j j
P
where j λj = 1 and λj ≥ 0 for every j.


1.1 Introduction

Probability

The joint probability is given by p(x, y), which is short notation for p(X = xi ∩Y = yj ).
• The sum rule is X Z
p(x) = p(x, y) = p(x, y) dy.
y

– Applying the sum rule as above is called “marginalizing out y.”
• The product rule is
p(x, y) = p(x|y)p(y).
– Computing p(x|y) is called “conditioning on y.”
• Let w be parameters and D be data. Bayes theorem is given by
p(D|w)p(w) likelihood × prior
p(w|D) = ⇔ posterior = .
p(D) evidence

– Frequentist: data D generated from a fixed w.
– Bayesian: data D fixed, find best w given this data.

3

, • Frequentists generally quantify the properties of data driven quantities in light of
the fixed model parameters, while Bayesians generally quantify the properties of
unknown model parameters in light of observed data. See [VanderPlas, 2014].


Expectation and covariance

Let x be distributed with density p(x), then
• The expectation of a function f (x) defined over x with probability density p(x) is
X Z
E[f ] = f (xj )p(xj ) = f (x)p(x) dx
j


• The variance of f (x) is

var[f ] = E (f − E[f ])2 = E[f 2 ] − E[f ]2
 


• The covariance of x and y given by

cov[x, y] = Ex,y [(x − E[x])(y − E[y])]

• The covariance matrix Σ has entries σij corresponding to the covariance of variables
i and j. Thus Σ = I means no covariance. (Note that real data may have no
covariance and still be dependent, i.e. have predictive power, xj = f (xk ) where f is
non-linear. See “Anscombe’s quartet” on Wikipedia.)


Polynomial fitting
PM j
Let y(x, w) = j=1 wj x be a polynomial. We wish to fit this polynomial to values
x = (x1 , . . . , xN ) and t = (t1 , . . . , tN ) i.e. a degree M polynomial fitting N data points.
• The maximum likelihood solution is to minimize
N
X
E(w, x) ∝ [y(xn , w) − tn ]2 .
n=1


• Regularization adds a weight-dependent error so that E(w,
e x) = E(w, x) + E(w).
For instance, Ridge minimizes the 2-norm:
N
X
E(w,
e x) ∝ [y(xn , w) − tn ]2 + λ kwk22
n=1

While LASSO (Least Absolute Shrinkage and Selection Operator) minimizes and
error with the 1-norm. Both are examples of Tikhonov regularization.



4