Tree-structured approximations by expectation propagation

Tom Minka and Yuan Qi, NIPS 2003

Approximation structure plays an important role in inference on loopy graphs. As a tractable structure, tree approximations have been utilized in the variational method of Ghahramani & Jordan (1997) and the sequential projection method of Frey et al. (2000). However, belief propagation represents each factor of the graph with a product of single-node messages. In this paper, belief propagation is extended to represent factors with tree approximations, by way of the expectation propagation framework. That is, each factor sends a "message" to all pairs of nodes in a tree structure. The result is more accurate inferences and more frequent convergence than ordinary belief propagation, at a lower cost than variational trees or double-loop algorithms.

paper (with corrections) . poster

The potentials for the graphs used in the paper are available.

This is the example 4-node complete graph:
Each line of this file is a potential. The first two columns give the domain and the last four give the values. The Matlab file read_pots.m will read this into BNT.

Here is the data used to make figure 3:
This is in Matlab MAT format.  The readme file describes the contents.

Tom Minka
Last modified: Tue Feb 06 13:37:15 GMT 2007