Let B be a network, E = e an observation, and X1, . . . , Xk be some ordering (not necessarily topological) of the unobserved variables in B. Consider a sampling algorithm that, for each X1, . . . , Xk in order, randomly selects a value xi[m] for Xi using some distribution Q(Xi|x1[m], . . . , xi−1[m], e).
a. Write the formula for the importance weights in normalized importance sampling using this sampling process.
b. Using your answer in part 1, define an improved likelihood weighting algorithm that samples variables in the network in topological order, but, for a variable Xi with parents Ui, samples Xi using a distribution that uses both x−i[m] and the evidence in Xi’s Markov blanket.
c. Does your approach from part 2 generate samples from the posterior distribution P(X1, . . . , Xk | e)? Explain.