Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Export

@article{citeulike:465818, abstract = {Graphical models, such as Bayesian networks and Markov random fields, represent statistical dependencies of variables by a graph. Local "belief propagation" rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities in singly connected graphs. Recently, good performance has been obtained by using these same rules on graphs with loops, a method we refer to as loopy belief propagation. Perhaps the most dramatic instance is the near Shannon-limit performance of "Turbo codes," whose decoding algorithm is equivalent to loopy propagation. Except for the case of graphs with a single loop, there has been little theoretical understanding of loopy propagation. Here we analyze belief propagation in networks with arbitrary topologies when the nodes in the graph describe jointly gaussian random variables. We give an analytical formula relating the true posterior probabilities with those calculated using loopy propagation. We give sufficient conditions for convergence and show that when belief propagation converges, it gives the correct posterior means for all graph topologies, not just networks with a single loop. These results motivate using the powerful belief propagation algorithm in a broader class of networks and help clarify the empirical performance results.}, address = {Computer Science Division, University of California, Berkeley CA 94720-1776, USA.}, author = {Weiss, Y. and Freeman, W. T.}, citeulike-article-id = {465818}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1121128.1121129}, citeulike-linkout-1 = {http://dx.doi.org/10.1162/089976601750541769}, citeulike-linkout-2 = {http://neco.mitpress.org/cgi/content/abstract/13/10/2173}, citeulike-linkout-3 = {http://view.ncbi.nlm.nih.gov/pubmed/11570995}, citeulike-linkout-4 = {http://www.hubmed.org/display.cgi?uids=11570995}, doi = {10.1162/089976601750541769}, issn = {0899-7667}, journal = {Neural Comput}, keywords = {bayes\_nets, belief\_propagation, graphical\_models, markov\_random\_fields, proofs}, month = {October}, number = {10}, pages = {2173--2200}, posted-at = {2008-10-06 14:55:26}, priority = {0}, title = {Correctness of belief propagation in Gaussian graphical models of arbitrary topology.}, url = {http://dx.doi.org/10.1162/089976601750541769}, volume = {13}, year = {2001} }

TY - JOUR ID - citeulike:465818 L3 - citeulike-article-id:465818 N2 - Graphical models, such as Bayesian networks and Markov random fields, represent statistical dependencies of variables by a graph. Local "belief propagation" rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities in singly connected graphs. Recently, good performance has been obtained by using these same rules on graphs with loops, a method we refer to as loopy belief propagation. Perhaps the most dramatic instance is the near Shannon-limit performance of "Turbo codes," whose decoding algorithm is equivalent to loopy propagation. Except for the case of graphs with a single loop, there has been little theoretical understanding of loopy propagation. Here we analyze belief propagation in networks with arbitrary topologies when the nodes in the graph describe jointly gaussian random variables. We give an analytical formula relating the true posterior probabilities with those calculated using loopy propagation. We give sufficient conditions for convergence and show that when belief propagation converges, it gives the correct posterior means for all graph topologies, not just networks with a single loop. These results motivate using the powerful belief propagation algorithm in a broader class of networks and help clarify the empirical performance results. IS - 10 JF - Neural Comput SN - 0899-7667 AD - Computer Science Division, University of California, Berkeley CA 94720-1776, USA. EP - 2200 TI - Correctness of belief propagation in Gaussian graphical models of arbitrary topology. VL - 13 SP - 2173 KW - bayes_nets KW - belief_propagation KW - graphical_models KW - markov_random_fields KW - proofs AU - Weiss, Y AU - Freeman, WT PY - 2001/10// UR - http://dx.doi.org/10.1162/089976601750541769 ER -