Counting Belief Propagation

Abstract

A major benefit of graphical models is that most knowledge is captured in the model structure. Many models, however, produce inference problems with a lot of symmetries not reflected in the graphical structure and hence not exploitable by efficient inference techniques such as belief propagation (BP). In this paper, we present a new and simple BP algorithm, called counting BP, that exploits such additional symmetries. Starting from a given factor graph, counting BP first constructs a compressed factor graph of clusternodes and clusterfactors, corresponding to sets of nodes and factors that are indistinguishable given the evidence. Then it runs a modified BP algorithm on the compressed graph that is equivalent to running BP on the original factor graph. Our experiments show that counting BP is applicable to a variety of important AI tasks such as (dynamic) relational models and boolean model counting, and that significant efficiency gains are obtainable, often by orders of magnitude.

Appears in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI2009)

References in corpus (4)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• Tractable Inference for Complex Stochastic Processes
• The Factored Frontier Algorithm for Approximate Inference in DBNs
• Template Based Inference in Symmetric Relational Markov Random Fields

Cited by in corpus (26)

• Probabilistic Theorem Proving
• Hinge-Loss Markov Random Fields and Probabilistic Soft Logic
• Equivariance Through Parameter-Sharing
• Representation Learning for Dynamic Graphs: A Survey
• Lifted Variable Elimination: Decoupling the Operators from the Constraint Language
• kLog: A Language for Logical and Relational Learning with Kernels
• Markov Chains on Orbits of Permutation Groups
• Quantum Enhanced Inference in Markov Logic Networks
• Towards Completely Lifted Search-based Probabilistic Inference
• Detecting Parameter Symmetries in Probabilistic Models
• First-Order Decomposition Trees
• Contextual Symmetries in Probabilistic Graphical Models
• Generating and Sampling Orbits for Lifted Probabilistic Inference
• Lifted Tree-Reweighted Variational Inference
• Symmetry-Aware Marginal Density Estimation
• Sequential Lifted Bayesian Filtering in Multiset Rewriting Systems
• Block Belief Propagation for Parameter Learning in Markov Random Fields
• Lifted Variable Elimination: A Novel Operator and Completeness Results
• Block-Value Symmetries in Probabilistic Graphical Models
• Reasoning Under the Principle of Maximum Entropy for Modal Logics K45, KD45, and S5
• Lifted Hybrid Variational Inference
• Stochastic Belief Propagation: A Low-Complexity Alternative to the Sum-Product Algorithm
• Lifted Region-Based Belief Propagation
• Probabilistic Event Calculus for Event Recognition
• Lifted Message Passing for the Generalized Belief Propagation
• Lifted Marginal MAP Inference