Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS 542: Machine Learning
Problem Set 5
1. (40 points) Written Problems
(a) (10 points, Page 1 & 2) Bishop 8.3
(b) (10 points, Page 3 & 4) Bishop 8.4
(c) (10 points, Page 5) Bishop 8.11
(d) (10 points, Page 6) Bishop 8.14
2. (60 points) Programming
(a) (30 points)
(a) Clean image (to restore) (b) Noise contaminated image (c) MRF
The goal of this problem is to recover the clean image (a) from a noisy input (b). Of
course, we cannot recover (a) exactly since information has been lost in the noise. The
graphical model we use is a pairwise MRF as shown in (c). A pixel has four neighbors.
We are going to use Markov Random Frields (MRFs) to model the distribution of natural images and restore the clean image given an noisy input image.
Observed image yi ∈ {−1, +1}, and i = 1, · · · , D indexes pixels in the lattice. The
5-1
original noise free image is xi ∈ {−1, +1}. The noisy image yi
is obtained by randomly
flipping the sign of pixels with some probability.
There are two types of cliques in this MRF. For {xi
, yi}, we define the energy function as
−ηxiyi (η > 0). Lower energy is achieved when xi and yi have the same sign and a higher
energy when they have the opposite sign. For a pair of variables {xi
, xj} where i and
j are indices of neighboring pixels, we want the energy to be lower when the same sign
than when they have opposite sign. So the energy function is −βxixj (β > 0). Lastly,
we have an energy term hxi
for each pixel i to bias the model towards one particular
sign (either + or −).
The final energy function for the model takes the form
E(x, y) = h
X
i
xi − β
X
{i,j}
xixj − η
X
i
xiyi
which defines a joint distribution over x and y given by
p(x, y) = 1
Z
exp{−E(x, y)}
Now implement Coordinate-descent algorithm as below on this:
1. Initialize {xi} (xi = yi)
2. Loop over {xi}. For each xi
, fix the neighborhood and see whether −xi would
decrease the energy. If so, then flip xi
; otherwise, continue.
3. Stop when no changes can be made for x.
Now make some initial guess for the parameters h, β, η so that the above algorithm
converges and then adjust them till you can get up to 96% recovery or better. Record
your parameter values and the number of iterations when you acheived this recovery.
Save the recovered image and submit it along with your code. The clean image and
noisy image are included: Bayes.png, Bayes-noise.png
(b) (30 points)
The goal of this problem is to once again recover the clean image (a) from a noisy
input (b), now in the famous picture of Lena, which is used to benchmark many image
processing algorithms. Of course, we cannot recover (a) exactly since information has
been lost in the noise. The graphical model we use is a pairwise MRF as shown in (c).
A pixel has four neighbors.