CSE 250A FINAL EXAM
FALL QUARTER 2021
1. d-separation (5 pts)
For the belief network shown below, indicate whether the following statements of marginal or con-ditional independence are true (T) or false (F). No further explanation is required.
2. Inference in a small network
Consider the belief network shown below, whose shaded nodes are observed. In this problem you will be guided through an efficient computation of the posterior probability P(F|A, C, D, G). You are expected to perform these computations efficiently—that is, by exploiting the structure of the DAG and not marginalizing over more variables than necessary.
(a) Node B (3 pts)
Consider just the part of the belief network shown above. Show how to compute the posterior probability P(B|A, D) in terms of the conditional probability tables (CPTs) for these nodes. Briefly justify each step of your solution.
(b) Node E (2 pts)
Consider just the part of the belief network shown above. Show how to compute the pos-terior probability P(E|A, C, D) in terms of your answer from part (a) and the CPTs of the belief network. Briefly justify each step of your solution.
Note: for this problem you may assume that P(B|A, D) from part (a) is given. Thus you can answer this question even if you skipped or missed part (a).
(c) Node G (2 pts)
Consider just the part of the belief network shown above. Show how to compute the condi-tional probability P(G|A, C, D, F) in terms of your answer from part (b) and the CPTs of the belief network. Briefly justify each step of your solution.
Note: for this problem you may assume that P(E|A, C, D) from part (b) is given. Thus you can answer this question even if you skipped or missed part (b).
(d) Node F (3 pts)
Show how to compute the posterior probability P(F|A, C, D, G) in terms of your answer from parts (a,b,c) and the CPTs of the belief network. Briefly justify each step of your solu-tion.
Note: for this problem you may assume that P(G|A, C, D, F) from part (c) is given. Thus you can answer this question even if you skipped or missed part (c).
3. Inference in an extended network
Consider the belief network of discrete random variables shown below, where Xt ∈ {1, 2, ..., n} and Yt∈ {1, 2, ..., n} form parallel chains, and Zt∈ {1, 2, ..., m} is the child of Xt and Yt at time t.
(a) Polytree? (1 pt)
Is this belief network a polytree? Justify your answer by stating the definition of a polytree, then explaining how the network either satisfies or violates your definition.
(b) Inference (4 pts)
Consider how to efficiently compute the marginal probability P(Z1, Z2, . . . , ZT ). What is the computational complexity of this inference?
Answer this question by clustering the nodes in this DAG (wisely) to obtain a more familiar belief network. Then, based on this clustering, give a precise answer, noting how the com-plexity of inference depends on the cardinalities n and m, as well as the sequence length T. (For instance, is the dependence constant, linear, polynomial, or exponential?)
Note: you are not asked nor expected to derive an algorithm for this inference, only to deduce its computational complexity.
4. Inference in a bipartite network
(a) Polytree? (1 pt)
Consider the above belief network of binary random variables. Is the network a polytree? Explain (in one sentence) why or why not.
(b) Marginal probability (3 pts)
Show how to compute the marginal probability P(y1, y2, . . . , yn) in terms of the conditional probability tables (CPTs) of the belief network—that is, in terms of the prior probabili-ties P(xi) and the conditional probabilities P(yj |x1, x2, . . . , xm).
(c) Scaling (2 pts)
How does your computation of the marginal probability P(y1, y2, . . . , yn) from part (b) scale in terms of the numbers of root notes (m) and second-layer nodes (n)? Be precise in your answer (i.e., linearly, polynomially, exponentially), and briefly justify your reasoning.
(d) Normalization (2 pts)
As shorthand, let µi = P(Xi = 1) denote the prior probability of each root node to be equal to one. The distribution over root nodes in the network can be written as:
Prove that this distribution is normalized—namely, that the sum 
is equal to unity. This calculation, though seemingly uninteresting, is designed to prepare you for part (f), where you will prove a nontrivial result about noisy-OR networks.
(e) Noisy-OR (2 pts)
Suppose that noisy-OR conditional probability tables are used at the nodes in the second layer of the network. In particular, let
where ρij is the noisy-OR parameter attached to the edge in the belief network that connects node Xi to node Yj . Consider the marginal probability
P(Y1 =0, Y2 =0, . . . , Yn =0)
of all-zero observations. By specializing your result2 from part (b) to noisy-OR networks, express this marginal probability in terms of the parameters µi = P(Xi =1) and ρij.
(f*) Efficient inference (4 pts)
Polynomial-time inference is generally not possible in loopy belief networks. In this noisy OR network, however, it is possible to compute the marginal probability
P(Y1 =0, Y2 =0, . . . , Yn =0)
of all-zero observations in time linear in the number of edges of the network—that is, in time O(mn). To do so, fully simplify your expression from part (e), now explicitly perform-ing the sum over the network’s unobserved nodes.
Hint: consider how you proved the result in part (d), which also involved a seemingly expo-nential sum over the same nodes.