Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)
Max Welling, Yee Teh
Belief propagation on cyclic graphs is an efficient algorithm for comput- ing approximate marginal probability distributions over single nodes and neighboring nodes in the graph. In this paper we propose two new al- gorithms for approximating joint probabilities of arbitrary pairs of nodes and prove a number of desirable properties that these estimates fulfill. The first algorithm is a propagation algorithm which is shown to con- verge if belief propagation converges to a stable fixed point. The second algorithm is based on matrix inversion. Experiments compare a number of competing methods.