Loopy Belief Propagation for Approximate Inference: An Empirical Study

Abstract

Recently, researchers have demonstrated that loopy belief propagation - the use of Pearls polytree algorithm IN a Bayesian network WITH loops OF error- correcting codes.The most dramatic instance OF this IS the near Shannon - limit performance OF Turbo Codes codes whose decoding algorithm IS equivalent TO loopy belief propagation IN a chain - structured Bayesian network. IN this paper we ask : IS there something special about the error - correcting code context, OR does loopy propagation WORK AS an approximate inference schemeIN a more general setting? We compare the marginals computed using loopy propagation TO the exact ones IN four Bayesian network architectures, including two real - world networks : ALARM AND QMR.We find that the loopy beliefs often converge AND WHEN they do, they give a good approximation TO the correct marginals.However,ON the QMR network, the loopy beliefs oscillated AND had no obvious relationship TO the correct posteriors. We present SOME initial investigations INTO the cause OF these oscillations, AND show that SOME simple methods OF preventing them lead TO the wrong results.

Appears in Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI1999)

Cited by in corpus (64)

• Expectation Propagation for approximate Bayesian inference
• Determinantal point processes for machine learning
• Complexity Results and Approximation Strategies for MAP Explanations
• Counting Belief Propagation
• Discriminative Probabilistic Models for Relational Data
• The Factored Frontier Algorithm for Approximate Inference in DBNs
• Convergent message passing algorithms - a unifying view
• Loopy Belief Propagation as a Basis for Communication in Sensor Networks
• Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation
• MAP Complexity Results and Approximation Methods
• Conditional Restricted Boltzmann Machines for Structured Output Prediction
• An Importance Sampling Algorithm Based on Evidence Pre-propagation
• Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization
• Kernel Belief Propagation
• Bayesian Information Extraction Network
• Convergent Message-Passing Algorithms for Inference over General Graphs with Convex Free Energies
• Convexifying the Bethe Free Energy
• Template Based Inference in Symmetric Relational Markov Random Fields
• Bound Propagation
• Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation
• A Variational Approach for Approximating Bayesian Networks by Edge Deletion
• On Bayesian Network Approximation by Edge Deletion
• Tropical Land Use Land Cover Mapping in Pará (Brazil) using Discriminative Markov Random Fields and Multi-temporal TerraSAR-X Data
• Coupled-Oscillator Associative Memory Array Operation
• Autotagging music with conditional restricted Boltzmann machines
• Recognition Networks for Approximate Inference in BN20 Networks
• Probabilistic Arc Consistency: A Connection between Constraint Reasoning and Probabilistic Reasoning
• Loopy Belief Propagation, Bethe Free Energy and Graph Zeta Function
• Approximation by Quantization
• Exploiting Structure in Cooperative Bayesian Games
• Expectation Propogation for approximate inference in dynamic Bayesian networks
• Approximate inference on planar graphs using Loop Calculus and Belief Propagation
• Discrete geometric analysis of message passing algorithm on graphs
• Bounds on the Bethe Free Energy for Gaussian Networks
• Gaussian Belief Propagation for Solving Systems of Linear Equations: Theory and Application
• Bayesian Hypothesis Test using Nonparametric Belief Propagation for Noisy Sparse Recovery
• Generalized Belief Propagation on Tree Robust Structured Region Graphs
• The Lazy Flipper: MAP Inference in Higher-Order Graphical Models by Depth-limited Exhaustive Search
• Asynchronous Dynamic Bayesian Networks
• Visual Semantic Information Pursuit: A Survey
• Loopy Belief Propagation in Bayesian Networks : origin and possibilistic perspectives
• Graphical Models as Block-Tree Graphs
• MIMO Detection for High-Order QAM Based on a Gaussian Tree Approximation
• Belief Propagation in Conditional RBMs for Structured Prediction
• Using Deep Neural Network Approximate Bayesian Network
• On Budgeted Influence Maximization in Social Networks
• Network infection source identification under the SIRI model
• Tackling Graphical NLP problems with Graph Recurrent Networks
• Survey Propagation Revisited
• Bayesian Image Restoration for Poisson Corrupted Image using a Latent Variational Method with Gaussian MRF
• Revisiting Algebra and Complexity of Inference in Graphical Models
• Contrastive Feature Induction for Efficient Structure Learning of Conditional Random Fields
• CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem
• Multi-way Particle Swarm Fusion
• Swipe Mosaics from Video
• Learning Large-Scale Topological Maps Using Sum-Product Networks
• Graphical-model Based Multiple Testing under Dependence, with Applications to Genome-wide Association Studies
• "Ideal Parent" Structure Learning for Continuous Variable Networks
• Inference by Minimizing Size, Divergence, or their Sum
• Cutset Sampling with Likelihood Weighting
• Distributed Anytime MAP Inference
• Tree-based iterated local search for Markov random fields with applications in image analysis
• The Hilbert Space of Probability Mass Functions and Applications on Probabilistic Inference
• Propositional and Relational Bayesian Networks Associated with Imprecise and Qualitative Probabilistic Assesments