6.438  Algorithms for Estimation & Inference

Dear class,

Please make a note of the following 3 important points regarding Problem Set 9:

(1) In Problem 9.1, there is a typo.  The compatibility functions over variables taking on the same value should be 10, not 1.  Similarly the compatibility functions for the pairs of random variables taking on opposite values should be 1, not 10.  That is,

\psi_{x,y}(0,0) = \psi_{x,y}(1,1) = 10  for all x and y in {a,b,c}
\psi_{x,y}(1,0) = \psi_{x,y}(0,1) = 1 for all x and y in {a,b,c}.

(2)  Loopy belief propagation will be covered in Thursday's lecture.  However, if you would like to get started on this part of the problem set, the following statement will prove sufficient for the questions asked.  Recall that our "simple to program" BP scheme (in which messages are initialized to 1 and all nodes continually pass and receive messages) did not rely on any type of leaf-to-root or root-to-leaf processing.  Therefore, this scheme can be run on graphs with loops.  Whether or not the resulting marginals calculated by this "loopy BP" correspond to the correct node marginals will be discussed more on Thursday, but is irrelevant for the problem set.

(3)  To give you a little more time to complete the problem set, we have extended the problem set due date by one day, i.e., to FRIDAY, DECEMBER 5th, the last day allowable by the Institute.    Please turn your problem set in at recitation.

Thanks,
6.438 staff