Join-Graph Propagation Algorithms
This work addresses the need for more accurate and efficient inference algorithms in probabilistic graphical models, which is crucial for applications in AI and machine learning, though it appears incremental as it builds on existing Generalized Belief Propagation frameworks.
The paper tackles the problem of improving approximate inference in graphical models by introducing Iterative Join-Graph Propagation (IJGP), a method that combines iteration and bounded inference. It shows empirically that IJGP surpasses the performance of mini-clustering, belief propagation, and other state-of-the-art algorithms on several network classes.
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.