On the Choice of Regions for Generalized Belief Propagation
  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.
