|
|
|
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.
Software:
- 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.
|