Iterative Join-Graph Propagation

Abstract

The paper presents an iterative version of join-tree clustering that applies the message passing of join-tree clustering algorithm to join-graphs rather than to join-trees, iteratively. It is inspired by the success of Pearl's belief propagation algorithm as an iterative approximation scheme on one hand, and by a recently introduced mini-clustering i. success as an anytime approximation method, on the other. The proposed Iterative Join-graph Propagation IJGP belongs to the class of generalized belief propagation methods, recently proposed using analogy with algorithms in statistical physics. Empirical evaluation of this approach on a number of problem classes demonstrates that even the most time-efficient variant is almost always superior to IBP and MC i, and is sometimes more accurate by as much as several orders of magnitude.

Appears in Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI2002)

References in corpus (2)

• Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation
• A Scheme for Approximating Probabilistic Inference

Cited by in corpus (10)

• Tightening LP Relaxations for MAP using Message Passing
• Approximate Inference Algorithms for Hybrid Bayesian Networks with Discrete Constraints
• Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks
• A Variational Approach for Approximating Bayesian Networks by Edge Deletion
• Modeling Transportation Routines using Hybrid Dynamic Mixed Networks
• A Simple Insight into Iterative Belief Propagation's Success
• Systematic vs. Non-systematic Algorithms for Solving the MPE Task
• Generalized Belief Propagation on Tree Robust Structured Region Graphs
• Approximating the Partition Function by Deleting and then Correcting for Model Edges
• Dual Decomposition from the Perspective of Relax, Compensate and then Recover