Tree-based reparameterization framework for analysis of sum-product and related algorithms

We present a tree-based reparameterization (TRP) framework that provides a new conceptual view of a large class of algorithms for computing approximate marginals in graphs with cycles. This class includes the belief propagation (BP) or sum-product algorithm as well as variations and extensions of BP. Algorithms in this class can be formulated as a sequence of reparameterization updates, each of which entails refactorizing a portion of the distribution corresponding to an acyclic subgraph (i.e., a tree, or more generally, a hypertree). The ultimate goal is to obtain an alternative but equivalent factorization using functions that represent (exact or approximate) marginal distributions on cliques of the graph. Our framework highlights an important property of the sum-product algorithm and the larger class of reparameterization algorithms: the original distribution on the graph with cycles is not changed. The perspective of tree-based updates gives rise to a simple and intuitive characterization of the fixed points in terms of tree consistency. We develop interpretations of these results in terms of information geometry. The invariance of the distribution, in conjunction with the fixed-point characterization, enables us to derive an exact expression for the difference between the true marginals on an arbitrary graph with cycles, and the approximations provided by belief propagation. More broadly, our analysis applies to any algorithm that minimizes the Bethe free energy. We also develop bounds on the approximation error, which illuminate the conditions that govern their accuracy. Finally, we show how the reparameterization perspective extends naturally to generalizations of BP (e.g., Kikuchi (1951) approximations and variants) via the notion of hypertree reparameterization.

• Publication year

  2003

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2003-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2003.810642
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Elements of Information Theory

  2005cited by this paper
• Constructing free-energy approximations and generalized belief propagation algorithms

  2005cited by this paper
• Embedded trees: estimation of Gaussian Processes on graphs with cycles

  2004cited by this paper
• Tree consistency and bounds on the performance of the max-product algorithm and its generalizations

  2004cited by this paper
• Belief Propagation on Partially Ordered Sets

  2003influential reference
• Understanding belief propagation and its generalizations

  2003influential reference
• A new class of upper bounds on the log partition function

  2002cited by this paper
• Loopy Belief Propogation and Gibbs Measures

  2002cited by this paper
• Belief Propagation and Statistical Physics

  2002influential reference
• Stochastic processes on graphs with cycles: geometric and variational approaches

  2002influential reference
• An analysis of belief propagation on the turbo decoding graph with Gaussian densities

  2001cited by this paper
• Thesis Supervisor Accepted by.......................................................................

  2001cited by this paper
• Algebraic Graph Theory

  2001cited by this paper
• A Tighter Bound for Graphical Models

  2001cited by this paper
• Iterative Decoding of Tail-Biting Trellises and Connections with Symbolic Dynamics

  2001cited by this paper
• Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation

  2001cited by this paper
• A Double-Loop Algorithm to Minimize the Bethe and Kikuchi Free Energies

  2001cited by this paper
• The geometry of turbo-decoding dynamics

  2000influential reference
• Tree-Based Modeling and Estimation of Gaussian Processes on Graphs with Cycles

  2000cited by this paper
• The generalized distributive law

  2000cited by this paper
• Generalized Belief Propagation

  2000influential reference
• Correctness of Local Probability Propagation in Graphical Models with Loops

  2000influential reference
• Statistical Decision Rules and Optimal Inference

  2000cited by this paper
• An Analysis of Turbo Decoding with Gaussian Densities

  1999cited by this paper
• Learning Low-Level Vision

  1999cited by this paper
• Loopy Belief Propagation for Approximate Inference: An Empirical Study

  1999cited by this paper
• Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology

  1999cited by this paper
• Turbo Decoding as an Instance of Pearl's "Belief Propagation" Algorithm

  1998cited by this paper
• Iterative Decoding of Compound Codes by Probability Propagation in Graphical Models

  1998influential reference
• Tailbiting MAP Decoders

  1998cited by this paper
• Iterative decoding on graphs with a single cycle

  1998cited by this paper
• Parallel Optimization: Theory, Algorithms, and Applications

  1997cited by this paper
• Parallel Optimization:theory

  1997influential reference
• Recursive Algorithms for Approximating Probabilities in Graphical Models

  1996cited by this paper
• Tree Approximations to Markov Random Fields

  1995cited by this paper
• Cluster variation method and image restoration problem

  1995cited by this paper
• Learning with Graphical Models

  1994cited by this paper
• Information geometry of Boltzmann machines

  1992cited by this paper
• Modeling and estimation of multiresolution stochastic processes

  1992cited by this paper
• The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks

  1990cited by this paper
• Local computations with probabilities on graphical structures and their application to expert systems

  1990cited by this paper
• Solving Models in Statistical Mechanics

  1989cited by this paper
• Probabilistic reasoning in intelligent systems

  1988influential reference
• Differential geometry in statistical inference

  1987cited by this paper
• Enumerative Combinatorics

  1986cited by this paper
• Differential geometry of statistical inference

  1983cited by this paper
• Differential Geometry of Curved Exponential Families-Curvatures and Information Loss

  1982cited by this paper
• Exactly solved models in statistical mechanics

  1982influential reference
• Graphs, Networks, and Algorithms

  1980cited by this paper
• $I$-Divergence Geometry of Probability Distributions and Minimization Problems

  1975cited by this paper
• Spatial Interaction and the Statistical Analysis of Lattice Systems

  1974cited by this paper
• A THEOREM ABOUT RANDOM FIELDS

  1973cited by this paper
• Generalized Iterative Scaling for Log-Linear Models

  1972cited by this paper
• Information And Exponential Families

  1970cited by this paper
• Low-density parity-check codes

  1962cited by this paper
• Theory of Cooperative Phenomena

  1952cited by this paper
• A Theory of Cooperative Phenomena

  1951cited by this paper
• and as an in

  year unknowncited by this paper

• Adapting cluster graphs for inference of continuous trait evolution on phylogenetic networks

  2025cites this paper
• Leveraging graphical model techniques to study evolution on phylogenetic networks

  2024cites this paper
• How does the brain compute with probabilities?

  2024cites this paper
• Tree-structured Markov random fields with Poisson marginal distributions

  2024cites this paper
• Circular Belief Propagation for Approximate Probabilistic Inference

  2024cites this paper
• Number of Eulerian orientations for Benjamini--Schramm convergent graph sequences

  2024cites this paper
• Gauging tensor networks with belief propagation

  2023cites this paper
• Modeling Large-Scale Joint Distributions and Inference by Randomized Assignment

  2023cites this paper
• Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networks

  2022cites this paper
• Learning Dynamics and Structure of Complex Systems Using Graph Neural Networks

  2022cites this paper
• Fixing the Bethe approximation: How structural modifications in a graph improve belief propagation

  2022cites this paper
• Iterative Detection and Decoding for Cell-Free Massive Multiuser MIMO with LDPC Codes

  2022cites this paper
• Understanding the Behavior of Belief Propagation

  2022cites this paper
• Generalization of graph network inferences in higher-order graphical models

  2021cites this paper
• Generalization of graph network inferences in higher-order probabilistic graphical models

  2021cites this paper
• Evaluations of Tutte polynomials of regular graphs

  2021cites this paper
• Convergence behavior of belief propagation: estimating regions of attraction via Lyapunov functions

  2021cites this paper
• Modules or Mean-Fields?

  2020cites this paper
• Optimizing communication and computational costs based on the edge participation probability and the evolved variational message passing algorithm in wireless sensor networks

  2020cites this paper
• Message Scheduling for Performant, Many-Core Belief Propagation

  2019cites this paper
• Graph Structured Prediction Energy Networks

  2019cites this paper
• Convergence Analysis of a New Distributed Algorithm for Networked Estimation

  2019cites this paper
• Graph Structured Prediction Energy Net Algorithms

  2019cites this paper
• Preprint Known position : [ 6 , 5 ] Position : ? Position : ? Position : ? Position : ?

  2019cites this paper
• Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms, Second Edition

  2019cites this paper
• Structured Mean-field Variational Inference and Learning in Winner-take-all Spiking Neural Networks

  2019cites this paper
• Policy Message Passing: A New Algorithm for Probabilistic Graph Inference

  2019cites this paper
• One-Shot Inference in Markov Random Fields

  2019cites this paper
• Continuous Graph Flow for Flexible Density Estimation

  2019cites this paper
• Filling Gaps in Incomplete Satellite Images with Compressable Spatio-Temporal Random Fields

  2019cites this paper
• Iteration Continuous Graph Flow Time ( Continuous ) Discrete neural message passing 1 2 K ... ... Message functions Node Continuous dynamics

  2019cites this paper
• Counting degree-constrained subgraphs and orientations

  2019cites this paper
• ICLR 2020 Function set : Agent ? ? ? ? Graph states input Agent ? ? ? ?

  2019cites this paper
• Context-Aware Recognition of Drivable Terrain with Automated Parameters Estimation

  2018cites this paper
• Learning Data Dependency with Communication Cost

  2018cites this paper
• On the Use of Extrinsic Probabilities in the Computation of Non-Bayesian Cramér–Rao Bounds for Coded Linearly Modulated Signals

  2018cites this paper
• Local Conditioning: Exact Message Passing for Cyclic Undirected Distributed Networks

  2018cites this paper
• Inference in Probabilistic Graphical Models by Graph Neural Networks

  2018cites this paper
• Optimizing Communication Costs based on the Evolved Variational Message Passing Algorithm using an Enhanced Version of Junction Tree in Wireless Networks

  2018cites this paper
• Planar Ising-Spin Models in Probabilistic Machine Learning

  2018cites this paper
• Bounding Inference: Decomposition Bounds

  2018cites this paper
• Gauges, loops, and polynomials for partition functions of graphical models

  2018cites this paper
• Belief Propagation in Conditional RBMs for Structured Prediction

  2017cites this paper
• Exploiting probabilistic relationships between action concepts for complex event classification

  2017cites this paper
• Free Energy Approximations for CSMA Networks

  2017cites this paper
• Gauging variational inference

  2017cites this paper
• Cooperative network localization using hybrid range and angle measurements

  2017cites this paper
• Latent Parameter Estimation in Fusion Networks Using Separable Likelihoods

  2017cites this paper
• Neuro-Inspired Energy-Efficient Computing Platforms

  2017cites this paper
• Sparsity, redundancy and robustness in artificial neural networks for learning and memory. (Parcimonie, redondance et robustesse dans les réseaux de neurones artificiels pour l'apprentissage et la mémoire)

  2017cites this paper
• A Bayesian Algorithm for Distributed Network Localization Using Distance and Direction Data

  2017cites this paper
• Multicuts and Perturb & MAP for Probabilistic Graph Clustering

  2016cites this paper
• Co-Optimization of Power and Reserves in Dynamic T&D Power Markets With Nondispatchable Renewable Generation and Distributed Energy Resources

  2016cites this paper
• and Its Generalizations

  2016cites this paper
• Constraining the Connectivity of Sparse Neural Associative Memories

  2016cites this paper
• Bayesian compressive sensing framework for spectrum reconstruction in Rayleigh fading channels

  2016cites this paper
• Learning and Inference in Latent Variable Graphical Models

  2016cites this paper
• Multiple testing under dependence via graphical models

  2016cites this paper
• Enhanced convergence rate of inequality constraint shadow prices in PMP algorithm cleared distribution power markets

  2016cites this paper
• Inference by Reparameterization in Neural Population Codes

  2016cites this paper
• Future Energy System Dispatch and Control – Development of Decentralized Control Algorithms

  2016cites this paper
• Detekcja obiektów z wykorzystaniem probabilistycznych modeli grafowych

  2016cites this paper
• Probabilistic graphical models for mobile pedestrian localization in 3D environments

  2016influential citation
• Polynomial algorithm for exact calculation of partition function for binary spin model on planar graphs

  2016cites this paper
• Improving probabilistic inference in graphical models with determinism and cycles

  2016cites this paper
• UPGMpp: a Software Library for Contextual Object Recognition

  2015influential citation
• Informed Scheduling by Stochastic Residual Belief Propagation in Distributed Wireless Networks

  2015influential citation
• Theoretical guarantees and complexity reduction in information planning

  2015cites this paper
• Parallel finite element technique using Gaussian belief propagation

  2015cites this paper
• Using Constraint Satisfaction Techniques and Variational Methods for Probabilistic Reasoning

  2015cites this paper
• Energy-Efficient and Robust In-Network Inference in Wireless Sensor Networks

  2015cites this paper
• Statistical physics of loopy interactions: Independent-loop approximation and beyond

  2015cites this paper
• Dual Decomposition from the Perspective of Relax, Compensate and then Recover

  2015cites this paper
• Asynchronous decoding of LDPC codes over BEC

  2015cites this paper
• Fully Connected Deep Structured Networks

  2015cites this paper
• Co-occurrence rate networks: towards separate training for undirected graphical models

  2015influential citation
• Generalized belief propagation for estimating the partition function of the 2D Ising model

  2015cites this paper
• Graphical Models and Message-Passing Algorithms: Some Introductory Lectures

  2015cites this paper
• Bethe Learning of Conditional Random Fields via MAP Decoding

  2015influential citation
• Conditional Random Fields for Pattern Recognition Applied to Structured Data

  2015cites this paper
• Modeling Spatial Extremes via Ensemble-of-Trees of Pairwise Copulas

  2014cites this paper
• Knowledge-Aided Reweighted Belief Propagation LDPC Decoding using Regular and Irregular Designs

  2014influential citation
• Energy-efficient information inference in wireless sensor networks based on graphical modeling

  2014cites this paper
• Bottom-Up Approaches to Approximate Inference and Learning in Discrete Graphical Models

  2014influential citation
• Lifted Tree-Reweighted Variational Inference

  2014cites this paper
• Visualization of graphical information fusion results

  2014cites this paper
• Reasoning and Decisions in Probabilistic Graphical Models - A Unified Framework

  2014cites this paper
• Probabilistic graphical models: distributed inference and learning models with small feedback vertex sets

  2014cites this paper
• Short-length Low-density Parity-check Codes: Construction and Decoding Algorithms

  2014cites this paper
• Distribution network electricity market clearing: Parallelized PMP algorithms with minimal coordination

  2014cites this paper
• Statistical Methods for Genome-wide Association Studies and Personalized Medicine

  2014cites this paper
• Structured Variational Methods for Distributed Inference in Networked Systems: Design and Analysis

  2013cites this paper
• A nonparametric belief propagation method for uncertainty quantification with applications to flow in random porous media

  2013cites this paper
• Recursive FMP for distributed inference in Gaussian graphical models

  2013cites this paper
• Loop Calculus For Nonbinary Alphabets Using Concepts From Information Geometry

  2013cites this paper
• Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms

  2013cites this paper
• New Understanding of the Bethe Approximation and the Replica Method

  2013influential citation
• Graphical-model Based Multiple Testing under Dependence, with Applications to Genome-wide Association Studies

  2012cites this paper
• Variational Approximate Inference Methods for Graphical Models

  2012cites this paper
• Neurally inspired models of belief-propagation in arbitrary graphical models

  2012cites this paper