Exercise 20.4 - Inference in 2D lattice MRFs

For question (a), we consider only two options:

• Eliminate by column, i.e., eliminate $m$ variables each round.
• Eliminate by row, i.e., eliminate $n$ variables each round.

Let ${\left\{X_{i,j}\right\}}_{i=1,j=1}^{m,n}$ denotes the collection of all hidden variables. Note that the local evidence ${\left\{Y_{i,j}\right\}}_{i=1,j=1}^{m,n}$ can be absorbed into the local energy, what being broken is only the normalization condition. It is easy to see that the bottleneck in computing $p(\mathbf{\text{𝐗}}|\mathbf{\text{𝐘}})$ is the evidence:

The order by which we eliminate all hidden variables determines the efficiency of the overall algorithm.

For the first option, we begin by cancelling the last row, ${\left\{X_{i,n}\right\}}_{i=1}^m$, this step involves altogether:

terms. In which are $(m-1)$ edges within this column, $m$ edges with the $(n-1)$-th column and $m$ local evidence. To perform the integral, let us assume that a sampling-based paradigm is adopted, and each variable in $X_{i,n}$ and $X_{i,n-1}$ is sampled for $K$ times. This elimination ends up with a table with $K^m$ entries. Hence the integral is performed under complexity:

This procedure shall be iterated along the MRF for $n$ times, results in the overall complexity of:

Symmetrically, that for the second option is:

For question (b), with $m\ll n$, we should adopt the first method.

For question (c), since $m=n$, either method will do. We can adopt the Viterbi algorithm for HMM in this case, using a table of size $2^{2n}$ to save the propogated information (as dynamic programming).