1. [4 points] Inference Methods for Discrete Markov Random Fields
For this problem, consider the following Markov Random Field, where each node can be assigned one of the values in {1, 2, 3, 4, 5}:
x1 x3
x2 x4
(a) To conduct MAP inference on this graph using exhaustive search, how many configura- tions must be checked?
Your answer:
(b) Can MAP inference be run on this graph using a dynamic programming algorithm?
Why or why not?
Your answer:
(c) To run MAP inference on this graph using loopy belief propagation, how many messages must be computed?
Your answer:
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 arg maxx1 ,x2 θ1 (x1) + θ2(x2) + θ1,2 (x1, x2). Using
θ1 (x1) =
θ1,2(x1 , x2) =
1 if x1 = 0
2 otherwise θ2(x2) =
−1 otherwise
2 if x1 = 0 & x2 = 1
1 if x2 = 0
2 otherwise
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:
(b) What is the solution (value and argument) to the program in part (a).
Your answer:
(c) Why do we typically not use the integer linear program for reasonably sized MRFs?
Your answer:
