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
Reviews
There are no reviews yet.