Consider a fully persistent dbn over n state variables x

Question

Problem

1. Consider a fully persistent DBN over n state variables X. Show that any clique tree over X^(t), X^(t+1) that we can construct for performing the belief-state propagation step has induced width at least n + 1.

2. Recall that a hidden Markov model! Factorial factorial HMM factorial HMM is a DBN over X₁, . . . , X_n, O such that the only parent of X^'_i in the 2-TBN is X_i, and the parents of O' are X'₁, . . . , X'_n. (Typically, some structured model is used to encode this CPD compactly.) Consider the problem of using a structured variational approximation (as in section 11.5) to perform inference over the unrolled network for a fixed number T of time slices.

a. Consider a space of approximate distributions Q composed of disjoint clusters {X⁽⁰⁾_i , . . . , X^(T)_i} for i = 1, . . . , n. Show the variational update equations, describe the use of inference to compute the messages, and analyze the computational complexity of the resulting algorithm.

b. Consider a space of approximate distributions Q composed of disjoint clusters {X⁽¹⁾₁ , . . . , X^(t)_n} for t = 1 . . . , T. Show the variational update equations, describe the use of inference to compute the messages, and analyze the computational complexity of the resulting algorithm.

c. Discuss the circumstances when you would use one approximation over the other.