Problem
Suppose we wish to perform exact inference over a chain Markov Random Field given byX1 X2 ... Xn. Assume that each variableXihas|V al(Xi)|=d.
(a) Derive anO(n3d3) algorithm for computing marginalsP(Xi, Xj) over alln2variable pairs Xi,Xj.
(b) Since we are computing marginals for all variable pairs, we can store computations done for the previous pairs and use them to save time for the computations of the remaining pairs. The key recursive relationship that makes thisXwork is the following equation (fori
P(Xi, Xj) =P(Xi, Xj1)P(Xj|Xj1) (1) Xj1
Prove that the equation above holds.
(c) Construct a dynamic programming algorithm that computes marginals over alln2variable pairs based on the recursive relation in (1), and achieves a running time that is asymptotically faster thanO(n3d3). Describe the time complexity of your algorithm in terms ofnandd. Note: Make sure to clearly specify how each of the probabilitiesPyou use are computed.