On the Choice of Regions for Generalized Belief Propagation
This addresses a key bottleneck in GBP for AI and machine learning practitioners, offering a more systematic approach to region selection, though it is incremental as it builds on existing region graph theory.
The paper tackles the problem of selecting clusters (regions) for generalized belief propagation (GBP) in approximate inference, proposing a sequential algorithm that adds regions based on weakly irreducible criteria and region-width constraints, with experiments showing it performs close to optimally.
Generalized belief propagation (GBP) has proven to be a promising technique for approximate inference tasks in AI and machine learning. However, the choice of a good set of clusters to be used in GBP has remained more of an art then a science until this day. This paper proposes a sequential approach to adding new clusters of nodes and their interactions (i.e. "regions") to the approximation. We first review and analyze the recently introduced region graphs and find that three kinds of operations ("split", "merge" and "death") leave the free energy and (under some conditions) the fixed points of GBP invariant. This leads to the notion of "weakly irreducible" regions as the natural candidates to be added to the approximation. Computational complexity of the GBP algorithm is controlled by restricting attention to regions with small "region-width". Combining the above with an efficient (i.e. local in the graph) measure to predict the improved accuracy of GBP leads to the sequential "region pursuit" algorithm for adding new regions bottom-up to the region graph. Experiments show that this algorithm can indeed perform close to optimally.