Machine Learning II (2007/2008)

5/23 Generalized Belief Propagation

This is a coding day for generalized belief propagation. The idea is that by coding up an algorithm one understands the ins and outs of an algorithm a lot more than just reading or hearing about it. The day will start with a two hour lecture at the usual 11am-1pm time, introducing the algorithm (generalized belief propagation) and also describing a toolkit that I have written for MATLAB that will allow you much easier (thus if you would like to use this toolkit you'll have to use MATLAB, though potentially you can use C, but that will be a pain). The rest of the day will involve coding up of the algorithm in pairs.

Generalized belief propagation is a generalization of the very popular loopy belief propagation algorithm, introduced by Yedidia et al, bringing the Kikuchi approximation of the log partition function from the statistical physics literature to bear on the problem. It has been found to work much better than other approximate inference algorithms (when it does work).

Reading material:

  • handwritten lecture notes.
  • tech report. Yedidia, J.S.; Freeman, W.T.; Weiss, Y., "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms", IEEE Transactions on Information Theory, ISSN; 0018-9448, Vol. 51, Issue 7, pp. 2282-2312, July 2005.


  • Easy BP v0. MATLAB package written by Yee Whye to make writing message passing code in MATLAB easier.
  • Generalized Arithmetic Operators for MATLAB. Does the same thing as the above package, without normalization handling. It used to be that MATLAB cannot handle multidmensional arrays beyond 10 dimensions or so (it crashes intermittently due to some memory bug), which is the reason I originally wrote the above package. Now it seems to be able to handle such high dimensional arrays. I am not sure if this GENOPS package handles high dimensional arrays, but it is worth a try. It is more transparent than the table class of Easy BP, since it simply overloads methods in the double class.
  • Generalized Operators for MATLAB. Same as above, but implemented in m files rather than mex overloading double class methods. Slower, but may be easier to get working.