Description
Questions
1. (30 points) Derive the EM algorithm for estimating a mixture of multinomial
distributions. The probability mass function of a multinomial distribution for
class Ci
is
P(x = (x1, . . . , xn)|Ci) = P(x = (x1, . . . , xn)|pi1, · · · , pin)
=
m!
x1! · · · xn!
p
x1
i1
· · · p
xn
in
where Pn
j=1 pij = 1 and Pn
j=1 xj = m. The mixture density of K multinomial
distributions is
P(x) = X
K
i=1
P(x|Ci)P(Ci) = X
K
i=1
πi
m!
x1! · · · xn!
p
x1
i1
· · · p
xn
in ,
where PK
i=1 πi = 1 and assuming Pn
j=1 xj = m for all K distributions. Define
the complete log-likelihood function and derive the EM equations including the
expectation for the responsibility γ(z
t
i
) (z
t
i
is the binary indicator of sample t
in cluster i) and maximum likelihood learning for {πi
, pi1, · · · , pin}i=1,…,K.
2. In this question, we will implement the EM algorithm to estimate a mixture of
Gaussian distributions for image compression. (Please read the Instructions
section below before you start programming)
(a) (20 points) Implement the EM algorithm to estimate a mixture of k
Gaussian distributions and run it on the image file “stadium.bmp”. Cluster the pixels into k = {4, 8, 12} clusters and plot the compressed images
for each value of k as described below. (Note: your program might fail if
Σ is singular; in this case, restart your EM again. We will fix the problem
in part (d)).
1
Instructor: Rui Kuang (kuang@cs.umn.edu). TA: Rachit Jas (jas00001@umn.edu) and Tianci
Song (song0309@umn.edu)
1
(b) (10 points) Run your EM implementation on the “stadium.bmp” image
for k = {4, 8, 12} and plot the expected complete log-likelihood function
Q(Φ|Φ
l
) after each E-step and M-step of the EM algorithm in one curve
for each value of k. Use different colors to plot the log-likelihood after the
E-step and M-step in the curve. Briefly explain the results.
(c) (10 points) Try to run your EM implementation on the image “goldy.bmp”
with k = 7 and report your observation (Hint: If your algorithm falls here,
don’t panic. Continue to the rest part.). Next, use the k-means function
in cluster module of sklearn package 2
to cluster the pixels with k = 7.
Plot the compressed image given by kmeans. Explain why kmeans and
EM behaved differently on the image.
(d) (20 points) Next, implement an improved version of EM to handle singular covariance matrix. In the likelihood function, we can add the following regularization term, −
λ
2Σ
k
i=1Σ
d
j=1(Σ−1
i
)jj , where (Σ−1
i
)jj is the (j, j)-th
entry of matrix Σ−1
i
and λ > 0. This regularization term encourages the
diagonal of Σ−1
i
to be small such that Σi
is not singular. After adding
this regularization term, the expectation step is unchanged and in the
maximization step, the maximum likelihood learning of µis and πis are
also unchanged. Derive the maximum likelihood learning of Σis using the
following result,
∂(−
λ
2Σ
k
i=1Σ
d
j=1(Σ−1
i
)jj )
∂Σ
−1
i
= −
λI
2
(hint: modify the derivation on slide 32 in parametric.pdf to solve the
problem).
(e) (10 points). Implement the new model and test the new model on
“goldy.bmp”. Explain your observations.
Instructions
• Solutions to all questions must be presented in a report which includes results,
explanations, all images and plots.
• All programming questions must be written in Python, no other programming
languages will be accepted. And numpy, scipy, skimage, sklearn and matplotlib
can be relied on to implement the algorithm (Note that you are only allowed to
2https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html
2
use KMeans function in cluster module of sklearn package in this homework).
The code must be able to be executed from either terminal or PyCharm console
on the cselabs machines. Each function must take the inputs in the order
specified and print/display the required output to either terminal or PyCharm
console. For each part, you can submit additional files/functions (as needed)
which will be used by the main functions specified below. Put comments in
your code so that one can follow the key parts and steps. Please follow the
rules strictly. If we cannot run your code, you will receive no credit.
• Question 2:
– hw3 Q2 a driver script which 1) uses kmeans to display a compressed
image 2) runs your standard EM implementation finishing by outputting
your own error message explaining why it fails 3) runs your improved
EM implementation to display the compressed image. For loading the
“goldy.bmp” image, you can use the following code:
from skimage import io
img = io.imread(’./stadium.bmp’)
img = img/255
– EMG(image.bmp: file path to an image, k: scalar value of the number
of clusters, flag: a binary indicator variable). Function EMG implements
the standard EM algorithm if flag is 0, while implements the improved
EM algorithm if flag is 1. The function must print to either terminal or
PyCharm console and return in variables the following for a single image
and value of k: (1) h: a n × k matrix where n is the number of pixels,
(2) m: a k × d matrix where d = 3 denotes the RGB values, and (3) Q:
a column vector of expected complete log-likelihood values. The outputs
{h, m, Q} are defined in Section 7.4 of the textbook. The function must
also display: (1) a single compressed color image for a single value of
k and (2) a single plot for the expected complete log-likelihood function
value vs iteration number for a single value of k.
– You can use the imread() function in io module of skimage package 3
to
convert the image into a 3D matrix in Python. You will then need to
convert the 3D matrix into a 2D matrix with d = 3 columns, in which
each row are the three RGB values of a pixel. You can use the reshape()
function in numpy package to do this 4
.
3https://scikit-image.org/docs/dev/api/skimage.io.html
4https://docs.scipy.org/doc/numpy/reference/generated/numpy.reshape.html
3
– To decide the membership of each pixel x
t
, you can select argmax
i
h
t
i
.
– To visualize the compression, use the mean estimated from Ci as the color
of pixels in Ci
.
– To compute the component densities, p(x
t
|Φ), you may use the multivariate normal() function in stats module in scipy package 5
.
– In your EM implementation, you can use the function KMeans() in cluster
module of sklearn package to find the initial clusters, however you can only
run kmeans for at most 3 iterations.
– Your program must be efficient and finish running for a single image and
value of k in at most a couple of minutes. You can set a maximum number
of iterations for the EM algorithm however use no less than 100 iterations.
Submission
• Things to submit:
1. hw3 sol.pdf: A PDF document which contains the report with solutions
to all questions.
2. EMG.py: Code for Question 2.
3. Any other files, except the data, which are necessary for your code.
• Submit: All materials must be zipped in one file, and submitted electronically
via canvas.
5https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.stats.multivariate normal.html
4
