Correctness of belief propagation in Gaussian graphical models of arbitrary topology
|MERL Report: ||TR99-33: Yair Weiss, William T. Freeman
Local "belief propagation" rules of the sort proposed by Pearl (1988) 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.