CS 188Fall 2019 Section Handout 8 Solutions1 Variable EliminationUsing the same Bayes Net (shown below), we want to compute P(Y | +z). All variables have binary domains.Assume we run variable elimination to compute the answer to this query, with the following variable eliminationordering: X, T , U , V , W .Complete the following description of the factors generated in this process:After inserting evidence, we have the following factors to start out with:P (T ), P (U |T ), P (V |T ), P (W |T ), P (X|T ), P (Y |V, W ), P (+z|X)(a) When eliminating X we generate a new factor f1as follows, which leaves us with the factors:f1(+z|T ) =XxP (x|T )P (+z|x) P (T ), P (U|T ), P (V |T ), P (W |T ), P (Y |V, W ), f1(+z|T )(b) When eliminating T we generate a new factor f2as follows, which leaves us with the factors:f2(U, V, W, +z) =XtP (t)P (U|t)P (V |t)P (W |t)f1(+z|t) P (Y |V, W ), f2(U, V, W, +z)(c) When eliminating U we generate a new factor f3as follows, which leaves us with the factors:f3(V, W, +z) =Xuf2(u, V, W, +z) P (Y |V, W ), f3(V, W, +z)Note that U could have just been deleted from the original graph, becausePuP (U |t) = 1. We can see this inthe graph: we can remove any leaf node that is not a query variable or an evidence variable.1(d) When eliminating V we generate a new factor f4as follows, which leaves us with the factors:f4(W, Y, +z) =Xvf3(v, W, +z)P (Y |v, W ) f4(W, Y, +z)(e) When eliminating W we generate a new factor f5as follows, which leaves us with the factors:f5(Y, +z) =Xwf4(w, Y, +z) f5(Y, +z)(f) How would you obtain P (Y | +z) from the factors left above:Simply renormalize f5(Y, +z) to obtain P (Y | +z). Concretely,P (y | +z) =f5(y, +z)Py0f5(y0, +z)(g) What is the size of the largest factor that gets generated during the above process?f2(U, V, W, +z). This contains 3 unconditioned variables, so it will have 23= 8 probability entries (U, V, W arebinary variables, and we only need to store the probability for +z for each possible setting of these variables).(m) Does there exist a better elimination ordering (one which generates smaller largest factors)?Yes. One such ordering is X, U , T , V , W . All factors generated with this ordering contain at most 2 uncondi-tioned variables, so the tables will have at most 22= 4 probability entries (as all variables are binary).2Q2. Bayes Nets(a) For the following graphs, explicitly state the minimum size set of edges that must be removed such thatthe corresponding independence relations are guaranteed to be true.Marked the removed edges with an ‘X’ on the graphs.B CDFEA(i) ADB CDEFA(ii) AD, (EF OR AB)(b) You’re performing variable elimination over a Bayes Net with variables A, B, C, D, E. So far, you’vefinished joining over (but not summing out) C, when you realize you’ve lost the original Bayes Net!Your current factors are f(A), f(B), f(B, D), f(A, B, C, D, E). Note: these are factors, NOT joint distri-butions. You don’t know which variables are conditioned or unconditioned.(i) What’s the smallest number of edges that could have been in the original Bayes Net? Draw out onesuch Bayes Net below.Number of edges = 5The original Bayes net must have had 5 factors, 1 for each node. f(A) and f(B) must have correspondedto nodes A and B, and indicate that neither A nor B have any parents. f(B, D), then, must correspondto node D, and indicates that D has only B as a parent. Since there is only one factor left, f(A, B,C, D, E), for the nodes C and E, those two nodes must have been joined while you were joining C.This implies two things: 1) E must have had C as a parent, and 2) every other node must have beena parent of either C or E.The below figure is one possible solution that uses the fewest possible edges to satisfy the above.B C D E A 3(ii) What’s the largest number of edges that could have been in the original Bayes Net? Draw out onesuch Bayes Net below.Number of edges = 8The constraints are the same as outlined in part i). To maximize the number of edges, we make eachof A, B, and D a parent of both C and E, as opposed to a parent of one of them.The below figure is the only possible solution.B C D E A