PGM 2004/05 - Programming Ex2

Don't forget to read the exercise guidelines

In this exercise you will build an approximate inference program for an undirected network with loops. You will implement several inference methods: Gibbs sampling, Mean-field inference and Loopy Belief Propagation. You will compare the solution of these methods to the exact inference solution.

We will explore the problem of inference on a wrap-around grid undirected network where each unobserved node X in the grid has a corresponding observed node Y:

• Assume all nodes are binary valued and that all Y's are observed. There are N unobserved nodes. A grid structure is defined via an adjacency matrix (Grid_MAT). For example, 3x3 grid is a 3x3 grid matrix where N=9 (you are given also the matrices for 5x5 and 7x7 grids).

• The undirected graph is defined via a NxN cell matrix where each cell is a 2x2 Psi(i,j) matrix representing the interaction between node i and node j. In addition, a 2xN Psi(i,i) vector represents the local potentials for each node (Local_MAT).
  Psi(i,j) is defined in the canonical form. That is, given an NxN matrix lambda(i,j) (Lambda_MAT):

  Psi(i,j) = [ exp(lambda(i,j)/2) exp(-lambda(i,j)/2); exp(-lambda(i,j)/2) exp(lambda(i,j)/2) ]

  
  Note that Psi(i,j) are defined for all i and j, but we will use only the potentials for the i,j who are connected, as defined by the grid file.

• We will evaluate only marginal probabilities of individual X nodes given the evidence. Thus, all inference methods will return a 2xN matrix (Bel_MAT) with the probabilities for the two values for each variable.
• For example, for the 3x3 grid you have:
  • The structure of the grid (3x3grid)
  • The belief obtained using exact inference for all three difficulties (3x3easy.mat 3x3medium.mat 3x3hard.mat) so you can compare your results.
  • lambdas to build the easy (lambda =0.05 for all i,j) and medium (lambda=2 for all i,j) problems.
  • The lambda mat you use to build the Psi(i,j)'s in the hard problem (3x3lambda.mat)
  To load this matrices print load(matname) in your matlab shell.

Part 1: Tasks

• Compare the three approximate inference methods to the exact solution (3x3easy.mat) for the relatively easy problem defined by the local potential matrix (3x3local.mat) and using lambda(i,j)=0.05 on the 3x3 grid.
• Repear your evaluation for the "medium" problem where lambda(i,j)=2 and the "hard" problem (3x3lambda.mat).
• Repeat your evaluation for larger grids using the corresponding 5x5 and 7x7 files.
• Look at the different Lambda matrices and try to characterize easy vs. difficult problems.
• Summarize your evaluation of each inference method.

Important: Don't forget to discuss all of the experiments in the evaluation file. You are expected to show insight and understanding of what is going on and not merely report results.

Part 2: Code

• [Bel_MAT] = MeanField(Grid_MAT,Lambda_MAT,Local_MAT)
• [Bel_MAT] = Gibbs(Grid_MAT,Lambda_MAT,Local_MAT,StartX,BurningTime,SamplingInterval,N)

  You should implement Gibbs in the following way:

  • StartX is a vector with the initial assignment for the variables X.
  • In a single time step, you sequentially go over the X's and sample each one thus generating a new assignment where all the X's have been resampled.
  • You repeat this until the Burning time and then take a single sample after each
  • Altogether you should generate N samples and return the beliefs evaluated from those samples

• [Bel_MAT] = Loopy(Grid_MAT,Lambda_MAT,Local_MAT,Strategy)

  You should implement the following strategies:

  1. Sequential updating (Strategy=1) where beliefs are updated one at a time and the new beliefs are used for subsequent updates.
  2. Parallel updateing (Strategy=2) where all beliefs are updated using the current beliefs

  Note:In order to avoid explosion of numbers, normalize each message so that it sums 1.0. Explain why this does not interfere with the calculation of the marginals

Submission

Please make sure the .m file names match the method names and are EXACTLY as specified. Also, make sure your login appears at the top of each file in a matlab comment