CS 179: Introduction to Graphical Models: Spring 2022

Homework 4

The submission for this homework should be a single PDF file containing all of the relevant code, figures, and any text explaining your results. When coding your answers, try to write functions to encapsulate and reuse code, instead of copying and pasting the same code multiple times. This will not only reduce your programming efforts, but also make it easier for us to understand and give credit for your work. Show and explain the reasoning behind your work!

Problem 1 (adapted from R. Dechter)   (40 points)

Consider the Bayesian network shown below.

(a)    (8 points) Draw the Markov random field (undirected graph) corresponding to this model and factorization.

(b)    (8 points) Compute the marginal probability p(F ) by eliminating variables in the order [A, B, C , D, E, G ] (here meaning, A first, then B, then C, etc.) Report which functions are combined at each step (e.g., in each bucket of bucket elimination), and show the scope (arguments of) and table corresponding to the function produced (Ai ). What is the induced width of this order (the largest scope of a function produced during the computation)?

Note: you may checkyour answer easily using the  GraphModel.eliminate function, but please compute the intermediate functions manually. It is OK to use Factor  objects to simplify the arithmetic aspects.

(c)   (8 points) Without actually computing the tables, what is the induced width of the ordering [D, G, E, F, B, C ,A]? (D first, then G, etc.)

(d)    (8 points) Suppose that we observe evidence D = 0, C = 1. First, simplify the graphical model by assigning the values of these variables (this will remove those nodes from the graph); what is the new Markov random field (undirected graph) associated with this conditional model?

(e)    (8 points) Now, compute the probability of evidence p(D = 0, C = 1) by eliminating (summing out) the other variables. Select a good order and compute the intermediate functions manually as in part (b); you do not need to output the tables themselves for this part, just the scopes and the final probability. What was the induced width of the order you selected for this problem? Again, you can check your result easily using the   and eliminate  functions; see lecture and slides for examples.

A  

Problem 2: Hidden Markov Model   (36 points)

Consider a four-state 4-state finite state machine, with states Yt  e {0, 1, 2, 3}, with state transition diagram shown at right. We always start (at time t = 0) in state Y0 = 0. In this problem, we will compute marginal probabilities and posterior marginal probabilities.

0.4

0.3

0.5

0.5

(a)    (8 points) Create (as a numpy array) the transition matrix T associated with this state transition diagram. For consistency in solutions, please make the first axis correspond to the current time t, and the second axis to the next time (t + 1), i.e., T[a,b]  = p(Yt+1 = blYt  = a). Print the array T . To verify your answer, also calculate by hand and using T the values of

(1) p(Y2 = 0lY0 = 0)

(2) p(Y2 = 2lY0 = 0)

(note: at time 2), and show the answers using T and by hand are equal.

(b)    (8 points) Our observations Xt  will be deterministic given the current state Yt , with Xt  = 0 when Yt  e {0, 2} and Xt  = 1 when Yt  e {1, 3}, i.e., Xt  indicates whether we are in an odd-numbered state.  Create (as a

(c)    (12 points) Compute the following probability distributions, either by hand or using your arrays:

(1) p(Y1 )

(2) p(Y1 lX1 = 0)

(3) p(Y2 )

(4) p(Y2 lX1 = 0,X2 = 1)

(5) p(Y2 lX1 = 0,X2 = 0)

(6) p(Y3 lX1 = 0,X2 = 0,X3 = 1)

(Note: since Y0 = 0, observing X0 has no effect on these computations and must be X0 = 0.)

(d)    (8 points) What is the distribution of states far in the future, e.g., p(Y100 )?

Problem 3: Viterbi   (24 points)

In this problem, we will use the same model as Problem 2, but compute the most likely state sequence, i.e., the (arg) maximum over the Y variables, in Python.

Write a python function or script that takes in the d x d transition probability matrix T , where T [i, j] is the probability of transitioning from state i to state j; a d x dn observation probability matrix O (where O[i, k] is the probability of observing value k when in state i), an initial state distribution vector p0 (Y0 ), and an observation sequence X  = [X0 , . . . ,XT-1 ], where Xt   e {0, . . . dn - 1}, and computes the most likely state sequence Y  = [Y0 , . . . , YT-1 ] given X using dynamic programming (for HMMs, called the Viterbi algorithm). You may use either

and X0 = 0.)

You can use the following test cases to help debug:

For your solution, provide a listing of your function, and your predictions on a few more test cases: