Consider doing inference in an m x n lattice Bayes net, as shown in Figure S13.43. The

Question:

Consider doing inference in an m x n lattice Bayes net, as shown in Figure S13.43. The network consists of mn binary variables V_i,j , and you have observed that V_m,n = _+vm,n.

You wish to calculate P(V_1,1 | + _vm,n) using variable elimination. To maximize computational efficiency, you wish to use a variable elimination ordering for which the size of the largest generated factor is as small as possible.

a. First consider the special case where m = 4 and n = 5. What is the optimal elimination order?

b. Now consider the general case (assume m > 2 and n > 2). What is the size of the largest factor generated under the most efficient elimination ordering?

Figure S13.43