CS 446: Machine Learning Homework 7 (Solution)

$ 20.99
Category:

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.

Be the first to review “CS 446: Machine Learning Homework 7 (Solution)”

Your email address will not be published. Required fields are marked *