Join-graph propagation algorithms

DOI10.1613/JAIR.2842MaRDI QIDQ3563087zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Robert Mateescu, Vibhav Gogate, K. Kask, Rina Dechter

Publication date 31 May 2010

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3489

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes.

Recommendations

• Join tree propagation with prioritized messages
• Convex combination belief propagation
• An empirical study of Bayesian network inference with simple propagation
• On Directed and Undirected Propagation Algorithms for Bayesian Networks
• scientific article; zbMATH DE number 1553119

Cited in

(13)

• Approximate structure learning for large Bayesian networks
• Efficient learning of bounded-treewidth Bayesian networks from complete and incomplete data sets
• Importance sampling-based estimation over AND/OR search spaces for graphical models
• Solution sampling with random table constraints
• Sufficient and necessary conditions for solution finding in valuation-based systems
• Improving probabilistic inference in graphical models with determinism and cycles
• Unifying tree decompositions for reasoning in graphical models
• Join tree propagation with prioritized messages
• scientific article; zbMATH DE number 2000820 (Why is no real title available?)
• scientific article; zbMATH DE number 1553119 (Why is no real title available?)
• Improved high dimensional discrete Bayesian network inference using triplet region construction
• SampleSearch: importance sampling in presence of determinism
• Markov conditions and factorization in logical credal networks

This page was built for publication: Join-graph propagation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3563087)