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 (193)

• Expectation Propagation for approximate Bayesian inference
• Deep Unsupervised Learning using Nonequilibrium Thermodynamics
• Determinantal point processes for machine learning
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Optimal control as a graphical model inference problem
• SybilBelief: A Semi-supervised Learning Approach for Structure-based Sybil Detection
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• Slice-to-volume medical image registration: a survey
• Complexity Results and Approximation Strategies for MAP Explanations
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Counting Belief Propagation
• Low-Complexity Detection/Equalization in Large-Dimension MIMO-ISI Channels Using Graphical Models
• 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
• Probabilistic Logic Neural Networks for Reasoning
• Conditional Restricted Boltzmann Machines for Structured Output Prediction
• An Importance Sampling Algorithm Based on Evidence Pre-propagation
• Neural Collective Entity Linking
• Survey on Models and Techniques for Root-Cause Analysis
• Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Kernel Belief Propagation
• Parametric Bilinear Generalized Approximate Message Passing
• Uncertainty-Aware Organ Classification for Surgical Data Science Applications in Laparoscopy
• Bayesian Information Extraction Network
• Networking - A Statistical Physics Perspective
• The continuous Bernoulli: fixing a pervasive error in variational autoencoders
• Convergent Message-Passing Algorithms for Inference over General Graphs with Convex Free Energies
• Convexifying the Bethe Free Energy
• Deep Coordination Graphs
• SybilFrame: A Defense-in-Depth Framework for Structure-Based Sybil Detection
• Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation
• Template Based Inference in Symmetric Relational Markov Random Fields
• Sentence-State LSTM for Text Representation
• Phase recovery from a Bayesian point of view: the variational approach
• Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
• Feedback Message Passing for Inference in Gaussian Graphical Models
• A Graph-to-Sequence Model for AMR-to-Text Generation
• Improving Entity Linking by Modeling Latent Relations between Mentions
• Amortized Variational Inference: A Systematic Review
• Bound Propagation
• One Policy to Control Them All: Shared Modular Policies for Agent-Agnostic Control
• Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation
• Advances in Variational Inference
• Receiver Architectures for MIMO-OFDM Based on a Combined VMP-SP Algorithm
• Latent Tree Models and Approximate Inference in Bayesian Networks
• A Variational Approach for Approximating Bayesian Networks by Edge Deletion
• Marginal Likelihoods for Distributed Parameter Estimation of Gaussian Graphical Models
• False News On Social Media: A Data-Driven Survey
• A visual introduction to Gaussian Belief Propagation
• 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
• Optimization With Parity Constraints: From Binary Codes to Discrete Integration
• Coupled-Oscillator Associative Memory Array Operation
• Autotagging music with conditional restricted Boltzmann machines
• Recurrent Relational Networks
• Recognition Networks for Approximate Inference in BN20 Networks
• Probabilistic Arc Consistency: A Connection between Constraint Reasoning and Probabilistic Reasoning
• A Probabilistic Framework for Location Inference from Social Media
• DSDNet: Deep Structured self-Driving Network
• Analyzing Differentiable Fuzzy Logic Operators
• Remote Homology Detection in Proteins Using Graphical Models
• Variational Particle Approximations
• Network Classification in Temporal Networks Using Motifs
• Gaussian Process Random Fields
• Multi-marginal optimal transport and probabilistic graphical models
• Deep Probabilistic Logic: A Unifying Framework for Indirect Supervision
• Loopy Belief Propagation, Bethe Free Energy and Graph Zeta Function
• Hierarchical Saliency Detection on Extended CSSD
• Approximation by Quantization
• Properties of Bethe Free Energies and Message Passing in Gaussian Models
• Pair-Linking for Collective Entity Disambiguation: Two Could Be Better Than All
• Expectation Propogation for approximate inference in dynamic Bayesian networks
• Predicting Infectiousness for Proactive Contact Tracing
• Exploiting Structure in Cooperative Bayesian Games
• Scalable Anytime Planning for Multi-Agent MDPs
• Bayesian Structured Prediction Using Gaussian Processes
• Discrete geometric analysis of message passing algorithm on graphs
• Approximate inference on planar graphs using Loop Calculus and Belief Propagation
• Exact and approximate inference in graphical models: variable elimination and beyond
• AIDA: An Active Inference-based Design Agent for Audio Processing Algorithms
• Gaussian Belief Propagation for Solving Systems of Linear Equations: Theory and Application
• Amortized Bethe Free Energy Minimization for Learning MRFs
• Bounds on the Bethe Free Energy for Gaussian Networks
• FSPN: A New Class of Probabilistic Graphical Model
• Graphical model approximations of random finite set filters
• Approximate Knowledge Compilation by Online Collapsed Importance Sampling
• Modular non-repeating codes for DNA storage
• Approximation-Aware Dependency Parsing by Belief Propagation
• Bayesian Hypothesis Test using Nonparametric Belief Propagation for Noisy Sparse Recovery
• The Variational Garrote
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• A Homological Approach to Belief Propagation and Bethe Approximations
• The Nonlinearity Coefficient - A Practical Guide to Neural Architecture Design
• Low Resource Multi-Task Sequence Tagging -- Revisiting Dynamic Conditional Random Fields
• Asynchronous Dynamic Bayesian Networks
• Generalized Belief Propagation on Tree Robust Structured Region Graphs
• Towards Zero-resource Cross-lingual Entity Linking
• Rethinking Dialogue State Tracking with Reasoning
• Review of Video Predictive Understanding: Early Action Recognition and Future Action Prediction
• The Lazy Flipper: MAP Inference in Higher-Order Graphical Models by Depth-limited Exhaustive Search
• Structured Message Passing
• Graphical Models as Block-Tree Graphs
• Truth Discovery to Resolve Object Conflicts in Linked Data
• Continuous Graph Flow
• Removal of Data Incest in Multi-agent Social Learning in Social Networks
• Convergence and Accuracy Analysis for A Distributed Static State Estimator based on Gaussian Belief Propagation
• Comparative Analysis of the Hidden Markov Model and LSTM: A Simulative Approach
• Non-Sentential Utterances in Dialogue: Experiments in Classification and Interpretation
• An Integer Linear Programming Framework for Mining Constraints from Data
• A Novel Factor Graph-Based Optimization Technique for Stereo Correspondence Estimation
• Visual Semantic Information Pursuit: A Survey
• Loopy Belief Propagation in Bayesian Networks : origin and possibilistic perspectives
• Graph Belief Propagation Networks
• Graph polynomials and approximation of partition functions with Loopy Belief Propagation
• MIMO Detection for High-Order QAM Based on a Gaussian Tree Approximation
• Network infection source identification under the SIRI model
• Federated Edge Learning with Misaligned Over-The-Air Computation
• Robust Spammer Detection by Nash Reinforcement Learning
• Neuralizing Efficient Higher-order Belief Propagation
• Approximating the Bethe partition function
• Using Deep Neural Network Approximate Bayesian Network
• Streaming Probabilistic Deep Tensor Factorization
• On Budgeted Influence Maximization in Social Networks
• Local Conditioning: Exact Message Passing for Cyclic Undirected Distributed Networks
• Probabilistic Discriminative Learning with Layered Graphical Models
• Joint Multitask Learning for Community Question Answering Using Task-Specific Embeddings
• Tackling Graphical NLP problems with Graph Recurrent Networks
• Gaussian Mixture Reduction for Time-Constrained Approximate Inference in Hybrid Bayesian Networks
• Fixed Points of Belief Propagation -- An Analysis via Polynomial Homotopy Continuation
• Variational hybridization and transformation for large inaccurate noisy-or networks
• A Smoother Way to Train Structured Prediction Models
• Belief Propagation in Conditional RBMs for Structured Prediction
• Truncating the loop series expansion for Belief Propagation
• Survey Propagation Revisited
• Conditional Expectation Propagation
• Message-Passing Algorithms and Homology
• Knowledge Efficient Deep Learning for Natural Language Processing
• Estimation for High-Dimensional Multi-Layer Generalized Linear Model -- Part I: The Exact MMSE Estimator
• Differentiable Nonparametric Belief Propagation
• Combining Probabilistic Logic and Deep Learning for Self-Supervised Learning
• Zero-Shot Scene Graph Relation Prediction through Commonsense Knowledge Integration
• pRSL: Interpretable Multi-label Stacking by Learning Probabilistic Rules
• Improved Algorithm for the Network Alignment Problem with Application to Binary Diffing
• Automating Model Comparison in Factor Graphs
• Learning Markov Random Fields for Combinatorial Structures via Sampling through Lovász Local Lemma
• Constraining Linear-chain CRFs to Regular Languages
• Towards Efficient Discrete Integration via Adaptive Quantile Queries
• Learning Features of Network Structures Using Graphlets
• Universal Marginalizer for Amortised Inference and Embedding of Generative Models
• Pull Message Passing for Nonparametric Belief Propagation
• Region Based Approximation for High Dimensional Bayesian Network Models
• Anytime Belief Propagation Using Sparse Domains
• The Complexity of Approximating a Bethe Equilibrium
• Pseudo-Bayesian Robust PCA: Algorithms and Analyses
• Variational Inference with Agent-Based Models
• A Bayesian algorithm for distributed network localization using distance and direction data
• Best-Choice Edge Grafting for Efficient Structure Learning of Markov Random Fields
• Mathematical Programs for Belief Propagation and Consensus
• Fast and Differentiable Message Passing on Pairwise Markov Random Fields
• Convex Combination Belief Propagation Algorithms
• Learning Energy-Based Approximate Inference Networks for Structured Applications in NLP
• Equivariant Neural Network for Factor Graphs
• Self-supervised self-supervision by combining deep learning and probabilistic logic
• Detecting Domain Polarity-Changes of Words in a Sentiment Lexicon
• Interactive Sensing in Social Networks
• Incremental inference of collective graphical models
• Deriving Latent Social Impulses to Determine Longevous Videos
• An Exploration of Arbitrary-Order Sequence Labeling via Energy-Based Inference Networks
• Propositional and Relational Bayesian Networks Associated with Imprecise and Qualitative Probabilistic Assesments
• Joint Mapping and Calibration via Differentiable Sensor Fusion
• Learning Large-Scale Topological Maps Using Sum-Product Networks
• Swipe Mosaics from Video
• Multi-way Particle Swarm Fusion
• CSMA using the Bethe Approximation: Scheduling and Utility Maximization
• CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem
• Contrastive Feature Induction for Efficient Structure Learning of Conditional Random Fields
• Revisiting Algebra and Complexity of Inference in Graphical Models
• Bayesian Image Restoration for Poisson Corrupted Image using a Latent Variational Method with Gaussian MRF
• Graphical-model Based Multiple Testing under Dependence, with Applications to Genome-wide Association Studies
• The Hilbert Space of Probability Mass Functions and Applications on Probabilistic Inference
• Lifted Graphical Models: A Survey
• Tree-based iterated local search for Markov random fields with applications in image analysis
• Distributed Anytime MAP Inference
• Inference by Minimizing Size, Divergence, or their Sum
• Cutset Sampling with Likelihood Weighting
• "Ideal Parent" Structure Learning for Continuous Variable Networks
• Recognizing Extended Spatiotemporal Expressions by Actively Trained Average Perceptron Ensembles
• Probabilistic Bag-Of-Hyperlinks Model for Entity Linking