EE512 Graphical Models University of WashingtonSpring 2006 Dept. of Electrical EngineeringHomework 2: Due Friday, April 14, 2006, 5:00pmProf: Jeff A. Bilmes <[email protected]> TA: Chris Bartels <[email protected]>Problem 1. Consequences of independenceYou are given a distribution on N+1 variables, X1:Nand C. The following conditional independence (CI) assumptionshold: Xi⊥⊥Xj|C for all i 6= j, and Xi⊥⊥Xjfor all i 6= j. Clearly, one such (uninteresting) distribution familysatisfying this set of CI constraints is the one where all N + 1 variables are mutually independent. Your problem isto (1) determine if any other distributions exist (either a family or a particular instance) that satisfy these constraints.This means either a) prove that no such distribution exists, or b) if it does (they do) exist, characterize it (them) as fullyas possible. (2) If you have found such distribution(s), can it (they) be described either by Bayesian networks (BNs),Markov random fields (MRFs), or factor graphs?Problem 2. Independence and factorizationIn class, we defined conditional independence X⊥⊥Y |Z if it is the case thatf(x, y|z) = f (x|z)f (y|z)for all x, y and for all z where fZ(z) > 0.Using this, (1) prove that X⊥⊥Y |Z if and only if there exists functions g and h such thatf(x, y, z) = g(x, z)h(y, z)for all x and y and for all z with fZ(z) > 0. (note that because of this equivalence, conditional independence is oftendefined in this way).(2) Must the functions g and h be unique in your proof? Explain why or why not.Problem 3 Bayes Ballx1x3x4x5x2Figure 2: Using Bayes ball, show X1⊥⊥X2Many people do not like d-separation and think that it is easier to use the Bayes Ball procedure/algorithm to determineconditional independence statements in BNs. Others prefer d-separation.Using the Bayes-ball procedure outlined in class and described more and described in the text (and in Shachter’s paperon the web), show that X1⊥⊥X2in the following graph. This means that you must show there is no way for a ball tobounce from X1to X2. This also means you must consider the possibility that the ball bounces below X3and thenback.1After you’ve solved this problem, indicate if you prefer Bayes Ball or d-separation (this part is of course not graded,results will be tallied and presented to the class when the HW is graded).Problem 4. MoralizationIn class, we defined the moralization step as a step that we must perform to convert from a BN into an MRF beforewe perform (variable) elimination. We stated that moralization was crucial because 1) it keeps the purely graphicalelimination procedure from doing something that does not corresponds to summation in directed models (i.e., sothat we don’t break apart or factorize p(c|πc) in invalid ways in general), and 2) it keeps the MRF from expressingconditional independent properties that the Bayesian network (BN) would not state, but at the cost of loosing some ofthe independence statements that the BN does state.Regarding conditional independence:1a) give an example of what a BN would state that the moralization step looses.1b) give an example of what an MRF would state that would be wrong w.r.t. the BN if moralization was not done.1c) Prove that after Moralization, no CI statements of a BN are violated by the MRF resulting from the moralized BN.I.e., here you need to prove that the MRF obtained by the moralized BN makes no additional conditional independencestatement that is not stated by the original BN.Problem 5. V-structures and independenceThis problem is on V-structures, where we have that A → B ← C meaning that A⊥⊥C but it is not the case thatA⊥⊥C|B.3a) Come up with a V-structure parameterization such that A⊥⊥C|B. Clearly express your parameterization in termsof numeric values contained in conditional probability tables and for these numeric values, prove that the CI statementholds.3b) If possible, come up with a V-structure parameterization but where it is such that A is not independent of C, againproviding numeric values in the tables. If it is not possible, prove this is the case.3c) Come up with a V-structure parameterization such that it is not the case that A⊥⊥C|B in general, but for somevalues of B (say bi) we have that A⊥⊥C|B = bi. Again, clearly express your parameterization in terms of tables, andprove that the CI statement holds.Problem 6:Prove that Bayesian networks that contain no V-structures and over N variables X1:Nrepresent exactly the samefamily of distributions as MRFs over N variables X1:N, where the structures of the BN and MRF are the same, butwhere the arrow directions are dropped to go from BN to MRF.Problem 7: TreesIn class, we gave the statement that trees are maximally cycle-free, and that trees are minimally connected. Explain inyour own words what this statement means.Problem 8:Come up with and draw two MRFs over N variables, where N >= 10, where each node is connected to at least 3other nodes. In one of the cases, your MRF must have a decomposition tree, and draw this tree. In the second case,prove that your graph does not have a decomposition