TR99-38

Correctness of belief propagation in Gaussian graphical models of arbitrary topology


    •  Yair Weiss, William T. Freeman, "Correctness of belief propagation in Gaussian graphical models of arbitrary topology", Tech. Rep. TR99-38, Mitsubishi Electric Research Laboratories, Cambridge, MA, October 1999.
      BibTeX Download PDF
      • @techreport{MERL_TR99-38,
      • author = {Yair Weiss and William T. Freeman},
      • title = {Correctness of belief propagation in Gaussian graphical models of arbitrary topology},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR99-38},
      • month = oct,
      • year = 1999,
      • url = {http://www.merl.com/publications/TR99-38/}
      • }
  • Research Area:

    Computer Vision


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.