Description
1. Fitting a Na¨ıve Bayes Model, 40 pts. In this question, we’ll fit a Na¨ıve Bayes model
to the MNIST digits using maximum likelihood. The starter code will download the dataset
and parse it for you: Each training sample (t
(i)
, x
(i)
) is composed of a vectorized binary image
x
(i) ∈ {0, 1}
784, and 1-of-10 encoded class label t
(i)
, i.e., t
(i)
c = 1 means image i belongs to class c.
For p(c |π) = πc and p(xj = 1 | c, θ,π) = θjc, Na¨ıve Bayes defines the joint probability of the
each data point x and its class label c as follows:
p(x, c | θ,π) = p(c | θ,π)p(x | c, θ,π) = p(c |π)
Y
784
j=1
p(xj | c, θjc).
Here, θ is a matrix of probabilities for each pixel and each class, so its dimensions are 784 × 10
(Note that in the lecture, we simplified notation and didn’t write the probabilities conditioned on
the parameters, i.e. p(c|π) is written as p(c) in lecture slides).
For binary data, we can write the Bernoulli likelihood as
p(xj | c, θjc) = θ
xj
jc (1 − θjc)
(1−xj )
(1.1) ,
which is just a way of expressing p(xj = 1|c, θjc) = θjc and p(xj = 0|c, θjc) = 1 − θjc in a
compact form. For the prior p(t |π), we use a categorical distribution (generalization of Bernoulli
distribution to multi-class case),
p(tc = 1 |π) = p(c |π) = πc or equivalently p(t |π) = Π9
j=0π
tj
j where X
9
i=0
πi = 1,
where p(c |π) and p(t |π) can be used interchangeably. You will fit the parameters θ and π using
MLE and MAP techniques, and both cases below, your fitting procedure can be written as a few
simple matrix multiplication operations.
(a) First, derive the maximum likelihood estimator (MLE) for the class-conditional pixel probabilities θ and the prior π. Hint-1: We saw in lecture that MLE can be thought of as ‘ratio
1
of counts’ for the data, so what should ˆθjc be counting? Derivations should be rigorous.
Hint-2: Similar to the binary case, when calculating the MLE for πj for j = 0, 1, …, 8, write
p(t
(i)
|π) = Π9
j=0π
t
(i)
j
j
and in the log-likelihood replace π9 = 1 − Σ
8
j=0πj , and then take
derivatives w.r.t. πj . This will give you the ratio ˆπj/πˆ9 for j = 0, 1, .., 8. You know that ˆπj ’s
sum up to 1.
(b) Derive the log-likelihood log p(t|x, θ,π) for a single training image.
(c) Fit the parameters θ and π using the training set with MLE, and try to report the average
log-likelihood per data point 1
N Σ
N
i=1 log p(t
(i)
|x
(i)
, θˆ,πˆ), using Equation (1.1). What goes
wrong? (it’s okay if you can’t compute the average log-likelihood here).
(d) Plot the MLE estimator θˆ as 10 separate greyscale images, one for each class.
(e) Derive the Maximum A posteriori Probability (MAP) estimator for the class-conditional
pixel probabilities θ, using a Beta(3, 3) prior on each θjc. Hint: it has a simple final form,
and you can ignore the Beta normalizing constant.
(f) Fit the parameters θ and π using the training set with MAP estimators from previous part,
and report both the average log-likelihood per data point, 1
N Σ
N
i=1 log p(t
(i)
|x
(i)
, θˆ,πˆ), and
the accuracy on both the training and test set. The accuracy is defined as the fraction of
examples where the true class is correctly predicted using ˆc = argmaxc
log p(tc = 1|x, θˆ,πˆ).
(g) Plot the MAP estimator θˆ as 10 separate greyscale images, one for each class.
2. Generating from a Na¨ıve Bayes Model, 30 pts. Defining a joint probability distribution over the data lets us generate new data, and also lets us answer all sorts of queries about
the data. This is why these models are called Generative Models. We will use the Na¨ıve Bayes
model trained in previous question to generate data.
(a) True or false: Given this model’s assumptions, any two pixels xi and xj where i 6= j are
independent given c.
(b) True or false: Given this model’s assumptions, any two pixels xi and xj where i 6= j are
independent after marginalizing over c.
(c) Using the parameters fit using MAP in Question 1, produce random image samples from the
model. That is, randomly sample and plot 10 binary images from the marginal distribution
p(x|θˆ,πˆ). Hint: To sample from p(x | θˆ,πˆ), first sample random variable c from p(c |πˆ) using
np.random.choice, then depending on the value of c, sample xj from p(xj | c, ˆθjc) for j =
1, …, 784 using np.random.binomial(1,..). These functions can take matrix probabilities
as input, so your solution to this part should be a few lines of code.
(d) (Optional – 0 pts) One of the advantages of generative models is that they can handle
missing data, or be used to answer different sorts of questions about the model. Derive
p(xbottom|xtop, θ,π), the marginal distribution of a single pixel in the bottom half of an
image given the top half, conditioned on your fit parameters. Hint: you’ll have to marginalize
over c.
(e) (Optional – 0 pts) For 20 images from the training set, plot the top half the image concatenated with the marginal distribution over each pixel in the bottom half. i.e. the bottom half
of the image should use grayscale to represent the marginal probability of each pixel being
1 (darker for values close to 1).
2
3. Principal Component Analysis, 30 pts. Using the numpy datafile digits.npy and
the utils.py dataloading helper code, you will find 6 sets of 16 × 16 greyscale images in vector
format (the pixel intensities are between 0 and 1 and were read into the vectors in a raster-scan
manner). The images contain handwritten 2’s and 3’s, scanned from postal envelopes. train2
and train3 contain examples of 2’s and 3’s respectively to be used for training. There are 300
examples of each digit, stored as 300 × 256 matrices. Note that each data vector is a row of
data matrices returned by load_data function. valid2 and valid3 contain data to be used for
validation (100 examples of each digit) and test2 and test3 contain test data to be used for final
evaluation only (200 examples of each digit).
Apply the PCA algorithm to the 600 x 256 digit images (computing all 256 of the eigenvalues
and eigenvectors, don’t forget to center the data). Then you should plot the (sorted) eigenvalues
as a descending curve. This plot shows the spectrum of the data, and roughly tells you how much
variance is contained along each eigenvector direction. Then view the first 3 eigen-images (reshape
each of the first 3 eigenvectors and use imagesc to see these as images) as well as the mean of
data. This part is for you to gain some intuition about how PCA works. You do not need to write
this part up!
(a) For each image in the validation set, subtract the mean of training data and project it
into the low-dimensional space spanned by the first K principal components of training
data. After projection, use a 1-NN classifier on K dimensional features (the code vectors) to
classify the digit in the low-dimensional space. You need to implement the classifier yourself.
You will do the classification under different K values to see the effect of K. Here, let K
= 2, 5, 10, 20, 30, and under each K, classify the validation digits using 1-NN. Plot the
results, where the plot should show the curve of validation set classification error rates versus
number of eigenvectors you keep, i.e., K.
(b) If you wanted to choose a particular model from your experiments as the best, which model
(number of eigenvectors) would you select? Why?
(c) Report the performance of your final classifier over the test data.
3
