Generalized Belief Propagation
Published 1 January 2000
Jonathan S. Yedidia, William T. Freeman, Yair Weiss
Citations906
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that BP can only converge to a stationary point of an approximate free energy, known as the Bethe free energy in statistical physics, and generalized belief propagation (GBP) versions of these Kikuchi approximations are derived.
Abstract
Belief propagation (BP) was only supposed to work for tree-like networks but works surprisingly well in many applications involving networks with loops, including turbo codes. However, there has been little understanding of the algorithm or the nature of the solutions it finds for general graphs. We show that
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
16,927 Citations1988Judea Pearl
The author provides a coherent explication of probability as a language for reasoning with partial belief and offers a unifying perspective on other AI approaches to uncertainty, such as the Dempster-Shafer formalism, truth maintenance systems, and nonmonotonic logic.
Machine LearningAn Introduction to Variational Methods for Graphical Models
3,775 Citations1999Michael I. Jordan, Zoubin Ghahramani +2 more
This paper presents a tutorial introduction to the use of variational methods for inference and learning in graphical models (Bayesian networks and Markov random fields), and describes a general framework for generating variational transformations based on convex duality.
arXiv (Cornell University)Loopy Belief Propagation for Approximate Inference: An Empirical Study
1,468 Citations2013Kevin P. Murphy, Yair Weiss +1 more
IEEE Journal on Selected Areas in CommunicationsTurbo decoding as an instance of Pearl's "belief propagation" algorithm
905 Citations1998Robert J. McEliece, David Mackay +1 more
It is shown that Pearl's algorithm can be used to routinely derive previously known iterative, but suboptimal, decoding algorithms for a number of other error-control systems, including Gallager's low-density parity-check codes, serially concatenated codes, and product codes.
Computers & Mathematics with ApplicationsGraphical models for machine learning and digital communication
465 Citations1999
Learning low-level vision
353 Citations1999William T. Freeman, Egon Pasztor
Europhysics Letters (EPL)Belief propagation <i>vs.</i> TAP for decoding corrupted messages
157 Citations1998Yoshiyuki Kabashima, David Saad
It is shown that for K>=3 and unbiased messages the iterative solution is sensitive to the initial conditions and is likely to provide erroneous solutions; and that it is generally beneficial to use Nishimori's temperature, especially in the case of biased messages.
IEEE Transactions on Information TheoryThe geometry of turbo-decoding dynamics
139 Citations2000Thomas Richardson
The geometric perspective clearly indicates the relationship between turbo-decoding and maximum-likelihood decoding, and analysis of the geometry leads to new results concerning existence of fixed points, condition for uniqueness, conditions for stability, and proximity to maximum- likelihood decoding.