| Correctness of belief propagation in Gaussian graphical models of arbitrary topology |
| Date: | October 1999 |
| Author: | arbitrary topology, Yair Weiss, William T. Freeman |
| Where Published: | Advances in Neural Information Processing Systems 12}, edited by S. A. Solla, T. K. Leen, and K-R. Muller, 2000 |
Local "belief propagation" rules of the sort proposed by Pearl [12] are guaranteed to converge to the correct posterior probabilities in singly connected graphical models. Recently, a number of researchers have empirically demonstrated good performance of "loopy belief propagation" -- using these same rules on graphs with loops. Perhaps the most dramatic instance is the near Shannon-limit performance of "Turbo codes," whose decoding algorithm is equivalent to loopy belief propagation. These results motivate using the powerful belief propagation algorithm in a broader class of networks, and help clarify the empirical performance results. |
|
