Description

1. [4 points] Inference Methods for Discrete Markov Random Fields

(a) To conduct MAP inference on this graph using exhaustive search, how many configurations must be checked?
Your answer: 54 configurations must be checked.
(b) Can MAP inference be run on this graph using a dynamic programming algorithm? Why or why not?
Your answer: No we cannot. Because in this case the graph is a ’loopy graph’ and dynamic programming approach can only be used in ’tree’ structure. So we cannot use a dynamic programming algorithm.
(c) To run MAP inference on this graph using loopy belief propagation, how many messages must be computed?
Your answer: If we perform loopy belief propagation on this graph, 40 (8 × 5 = 40) messages have to be computed.
2. [7 points] ILP Inference formulation in Discrete Markov Random Fields
(a) Suppose we have two variables x1 ∈ {0,1} and x2 ∈ {0,1} and their local evidence functions θ1(x1) and θ2(x2) as well as a pairwise function θ1,2(x1,x2). Using this setup, inference solves argmaxx1,x2 θ1(x1) + θ2(x2) + θ1,2(x1,x2). Using
1 if x1 = 01 if x2 = 0
2( 2) =
2 otherwise2 otherwise
1 otherwise
2 if x1 = 0 & x2 = 1
what is the integer linear programming formulation of the inference task? Make the cost function and constraints explicit for the given problem, i.e., do not use a general formulation.
Your answer: In this case we only care about whether xi = 0 or xi 6= 0, where i=1

or i=2 so I use notation 0 to indicate the condition that the value of x is not 0. Then we can get:
| |
 1(1)   1(1)   1(1)   2 
 b2(0)   θ2(0)   b2(0)   1 
 b2(1)   θ2(1)   b2(1)   2  max     =   −1 b1,b2,b12b1,1(0,0) θ1,1(0,0) b1,1(0,0) 
       
b1,2(1,0) θ1,2(1,0) b1,2(1,0) −1
       
b1,2(0,1) θ1,2(0,1) b1,2(0,1)  2  b1,2(1,1) θ1,2(1,1) b1,2(1,1) −1
subject to: br(xr) ∈{0,1} ∀r,xr;

(b) What is the solution (value and argument) to the program in part (a).
Your answer: x1 = 0,x2 = 1, then the maximum of the function is 5 = 1 + 2 + 2.
(c) Why do we typically not use the integer linear program for reasonably sized MRFs?
Your answer: Integer Linear Programming is very slow for larger problems.
2