Description
Exercise 1. MRFs and Images Denoising (40 points)
In this problem, you will implement the image de-noising example using a Markov Random Field (MRF). This material on MRFs is covered in the textbook (Barber) in chapter 4.2.5. The lecture and this problem is
based on the presentation in Bishop in chapter 8.3, which is available online.
As discussed in class, energy function for this MRF is
where the binary variables represent the unknown, noise-free image pixels, which are binary, i.e. black or white, and indicates the neighbords of node . The variables represent the observed noisy
pixels, i.e. the pixel could randomly change from black ( ) to white ( ) or vice-versa.
The corresponding joint probability distribution over the variables is
1.1 (5 pts) Derive the equation that specifies the change in the energy equation when one variable changes state.
1.2 (10 pts) Write a program to iteratively (or in random order) update the state variables to minimize the energy (maximize the probability). Explain the design of your code.
1.3 (5 pts) Show that your update algorithm minimizes the energy function and converges by plotting the energy vs the number of passes through the set of pixels.
1.4 (5 pts) Illustrate the model by showing the state of the denoised image at the points: at the start before updating, when it is about 50% converged in terms of energy minimization, and at the end when it
converges. Choose images that aren’t too high resolution so that the individual pixels are visible as squaures. You may also do a live plot in a notebook to show it updating continuously, but make sure you have
the static plots too in case the dynamic plot has portability issues.
1.5 (5 pts) Experiment with different settings of the energy equation parameters and explain your results in terms of their effect on the energy equation.
1.6 (10 pts) Generalize the energy equation so that the model better captures different structure. Explain your rationale behind this new model (i.e. terms in the equation). Illustrate it with denoising examples
(other types of images) with are not well-handled by the previous model.
Exercise 2. Graphical Representation (15 points)
2.1 (5 pts) For the Bayesian network show above, draw the corresponding Markov Random Field (MRF), and write out the joint probability using potential functions. You do not need to specify the functions
themselves, only which arguments they take. What are the potential functions in terms of the Bayes net?
2.2 (5 pts) Now specify the Bayes net as a factor graph. Again write the expression for the joint probability, but using factor functions.
2.3 (5 pts) Express the following Bayes net (from the sprinkler example) in two different factor graphs. For each network, write the factors as a function of the conditional probabilties and specify the joint
probability.
Exercise 3. The Sum Product Algorithm (20 pts)
Consider the following factor graph.
3.1 (5 pts) Apply the sum-product algorithm to compute the all messages when none of the variables are known. In your answers, you do not need to substitute in the values of other messages, i.e. your answers
should be in terms of local factors and other messages.
3.2 (5 pts) Compute the marginal probability , expressing it in terms of the messages you derived in the previous question.
3.3 (5 pts) Verify that the marginal is the correct expression substituting in the message definitions.
Now consider adding a loop to the graph.
3.4 (5 pts) Explore the consequences of applying the sum-product algorithm to this graph. Can the algorithm still be applied?
Exploration (20 points)
Like in previous assignments, in this exercise you are meant to do creative exploration. You don’t need to write a book chapter, but the intention is for you to go beyond what’s been covered above or explore new
topic altogether.
One suggestion: Select a probabilistic programming package and work through and explain in your own words an example of interest to you from the documentation or tutorial. Many of the simple tutorials will
cover models similar to what we have discussed in class. Be sure your explanation is from your own perspective and understanding; do not simply copy the tutorial. You should add your own unique variations and
modifications to better present the ideas or other things you found interesting. The purpose of this exercise is simply to make you aware of some of the modern tools that are available for probabilistic modeling.
There are several packages available to choose from and they are all under active development as this is an active field of research. In python, popular packages are PyMC3 and TensorFlow Probability. In Julia,
popular packages are Gen and Turing. There are many other choices, so feel free to choose something else if you find it interesting.
Alternatively, you can select a topic from the readings (Barber chapters 4, 5, and 27; Murphy chapters 19, 20, and 23; or Bishop Chapter 8) and write your own exercise. It should aim to teach or explore a
concept you don’t understand or found interesting. Like before, you don’t do an excessive amount of work. This isn’t a project. Aim for something worth about 20 points, i.e. about half as much work has exercise
1 but more than exercise 2. See the rubric below for grading criteria.
Exploration Grading Rubric
Exploration problems will be graded according the elements in the table below. The scores in the column headers indicate the number of points possible for each rubric element (given in the rows). A score of
zero for an element is possible if it is missing entirely.
Substandard (+1) Basic (+2) Good (+3) Excellent (+5)
Pedagogical
Value
No clear statement of idea or concept being
explored or explained; lack of motivating
questions.
Simple problem with adequate motivation; still
could be a useful addition to an assignment.
Good choice of problem with effective illustrations of concept(s).
Demonstrates a deeper level of understanding.
Problem also illustrates or clarifies common conceptual
difficulties or misconceptions.
Novelty of
Ideas
Copies existing problem or makes only a trivial
modification; lack of citation(s) for source of
inspiration.
Concepts are similar to those covered in the
assignment but with some modifications of an
existing exericse.
Ideas have clear pedagogical motivation; creates different type
of problem or exercise to explore related or foundational
concepts more deeply.
Applies a technique or explores concept not covered in the
assignment or not discussed at length in lecture.
Clarity of
Explanation
Little or confusing explanation; figures lack
labels or useful captions; no explanation of
motivations.
Explanations are present, but unclear,
unfocused, wordy or contain too much technical
detail.
Clear and concise explanations of key ideas and motivations.
Also clear and concise, but includes illustrative figures;
could be read and understood by students from a variety
of backgrounds.
Depth of
Exploration
Content is obvious or closely imitates
assignment problems. Uses existing problem for different data.
Applies a variation of a technique to solve a problem with an
interesting motivation; explores a concept in a series of related
problems.
Applies several concepts or techniques; has clear focus of
inquiry that is approached from multiple directions.
E(x, y) = h∑
i
xi − β∑
i
∑
j∈ne(i)
xixj − η∑
i
xiyi
xi ne(i) i yi
= −1 = +1
p(x, y) = exp[−E(x, y)] 1
Z
E(x, y)
In [1]: using TikzPictures
# manual layout: straightforward, predictable
g = TikzPicture(L””” % latex/TikZ code
% define styles
\tikzstyle{every node} = [draw, circle, minimum size=7mm]
\tikzset{>=latex}
% add nodes
\foreach \n/\x/\y in {a/1.5/3, b/2.5/3, c/1/2, d/2/2, e/3/2, f/1/1, g/2/1, h/3/1}
\node (\n) at (\x,\y) {\n};
% draw links
\foreach \from/\to in {a/c, a/d, b/d, b/e, c/f, d/g, d/h}
\draw [->] (\from) — (\to);
“””, options=”thick, scale=1.2, transform shape”)
Out[1]:
In [2]: # automatic layout: usually more concise and compact but not always predictable
g = TikzPicture(L”””
\graph [simple, grow down, branch right, edges={>=latex},
nodes={draw, circle, minimum size=7mm} ] {
{S,R} -> {T,J}, R -> T
};
“””, options=”thick, scale=1.2, transform shape”,
preamble=”\\usetikzlibrary{graphs}”)
Out[2]:
In [3]: g = TikzPicture(L”””
% define node styles
\tikzstyle{every node} = [draw, circle, minimum size=7mm]
\tikzstyle{every label} = [draw=none, inner sep=0pt]
\tikzstyle{factor} = [draw, rectangle, scale=0.4, fill=black!25]
% (Aside: Why can we add blank lines here, but not in the first graph??)
% variable nodes
\foreach \v/\x/\y in {a/1/2, b/3/2, c/3/1, d/5/1}
\node (\v) at (\x,\y) {\v};
% factor nodes
\foreach \n/\x/\y/\pos in {1/2/2/above, 2/4/1/above}
\node [factor, label=\pos:$f_\n$] (f\n) at (\x,\y) {};
% edges
\foreach \from/\to in {a/f1, f1/b, f1/c, c/f2, f2/d}
\draw (\from) — (\to);
“””, options=”thick, scale=1.2, transform shape”)
Out[3]:
p(c)
In [4]: g = TikzPicture(L”””
% define node styles
\tikzstyle{every node} = [draw, circle, minimum size=7mm]
\tikzstyle{every label} = [draw=none, inner sep=0pt]
\tikzstyle{factor} = [draw, rectangle, scale=0.4, fill=black!25]
% (Aside: Why can we add spaces here, but not above??)
% variable nodes
\foreach \v/\x/\y in {a/1/2, b/3/2, c/3/1, d/5/1}
\node (\v) at (\x,\y) {\v};
% factor nodes
\foreach \n/\x/\y/\pos in {1/2/2/above, 2/4/1/above}
\node [factor, label=\pos:$f_\n$] (f\n) at (\x,\y) {};
% edges
\foreach \from/\to in {a/f1, f1/b, b/f2, f1/c, c/f2, f2/d}
\draw (\from) — (\to);
“””, options=”thick, scale=1.2, transform shape”)
Out[4]:
In [ ]:
