Linear Response for Approximate Inference

Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)

Bibtex Metadata Paper


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.