[Solved] EECS491 Assignment3-MRFs and Images Denoising

Exercise 1. MRFs and Images DenoisingIn 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 isbased on the presentation in Bishop in chapter 8.3, which is available online.As discussed in class, energy function for this MRF iswhere 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 noisypixels, i.e. the pixel could randomly change from black ( ) to white ( ) or vice-versa.The corresponding joint probability distribution over the variables is1.1 Derive the equation that specifies the change in the energy equation when one variable changes state.1.2 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 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 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 itconverges. Choose images that arent 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 havethe static plots too in case the dynamic plot has portability issues.1.5 Experiment with different settings of the energy equation parameters and explain your results in terms of their effect on the energy equation.1.6 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 Representation2.1 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 functionsthemselves, only which arguments they take. What are the potential functions in terms of the Bayes net?2.2 Now specify the Bayes net as a factor graph. Again write the expression for the joint probability, but using factor functions.2.3 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 jointprobability.Exercise 3. The Sum Product AlgorithmConsider the following factor graph.3.1 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 answersshould be in terms of local factors and other messages.3.2 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 Explore the consequences of applying the sum-product algorithm to this graph. Can the algorithm still be applied?ExplorationLike in previous assignments, in this exercise you are meant to do creative exploration. You dont need to write a book chapter, but the intention is for you to go beyond whats been covered above or explore newtopic 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 willcover 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 andmodifications 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 aconcept you dont understand or found interesting. Like before, you dont do an excessive amount of work. This isnt a project. Aim for something worth about 20 points, i.e. about half as much work has exercise1 but more than exercise 2. See the rubric below for grading criteria.Exploration Grading RubricExploration 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 ofzero for an element is possible if it is missing entirely.Substandard (+1) Basic (+2) Good (+3) Excellent (+5)PedagogicalValueNo clear statement of idea or concept beingexplored or explained; lack of motivatingquestions.Simple problem with adequate motivation; stillcould 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 conceptualdifficulties or misconceptions.Novelty ofIdeasCopies existing problem or makes only a trivialmodification; lack of citation(s) for source ofinspiration.Concepts are similar to those covered in theassignment but with some modifications of anexisting exericse.Ideas have clear pedagogical motivation; creates different typeof problem or exercise to explore related or foundationalconcepts more deeply.Applies a technique or explores concept not covered in theassignment or not discussed at length in lecture.Clarity ofExplanationLittle or confusing explanation; figures lacklabels or useful captions; no explanation ofmotivations.Explanations are present, but unclear,unfocused, wordy or contain too much technicaldetail.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 varietyof backgrounds.Depth ofExplorationContent is obvious or closely imitatesassignment problems. Uses existing problem for different data.Applies a variation of a technique to solve a problem with aninteresting motivation; explores a concept in a series of relatedproblems.Applies several concepts or techniques; has clear focus ofinquiry that is approached from multiple directions.E(x, y) = hixi ijne(i)xixj ixiyixi ne(i) i yi= 1 = +1p(x, y) = exp[E(x, y)] 1ZE(x, y)In [1]: using TikzPictures# manual layout: straightforward, predictableg = TikzPicture(L % latex/TikZ code% define stylestikzstyle{every node} = [draw, circle, minimum size=7mm]tikzset{>=latex}% add nodesforeach
/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}
ode (
) at (x,y) {
};% draw linksforeach 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 predictableg = TikzPicture(Lgraph [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 stylestikzstyle{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 nodesforeach v/x/y in {a/1/2, b/3/2, c/3/1, d/5/1}
ode (v) at (x,y) {v};% factor nodesforeach
/x/y/pos in {1/2/2/above, 2/4/1/above}
ode [factor, label=pos:$f_
$] (f
) at (x,y) {};% edgesforeach 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 stylestikzstyle{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 nodesforeach v/x/y in {a/1/2, b/3/2, c/3/1, d/5/1}
ode (v) at (x,y) {v};% factor nodesforeach
/x/y/pos in {1/2/2/above, 2/4/1/above}
ode [factor, label=pos:$f_
$] (f
) at (x,y) {};% edgesforeach 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 [ ]