Abstract:

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.