|
|
|
|
On the Choice of Regions for Generalized Belief Propagation
Max Welling
Abstract:
Generalized belief propagation (GBP) has proven to be a promising technique for ap- proximate 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 approxi- mation. We first review and analyze the re- cently introduced region graphs and find that three kinds of operations ("split", "merge" and "death") leave the free energy and (un- der 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. Com- putational complexity of the GBP algorithm is controlled by restricting attention to re- gions with small "region-width". Combining the above with an efficient (i.e. local in the graph) measure to predict the improved ac- curacy of GBP leads to the sequential "re- gion pursuit" algorithm for adding new re- gions bottom-up to the region graph. Exper- iments show that this algorithm can indeed perform close to optimally.
Keywords: null
Pages: 585-592
PS Link:
PDF Link: /papers/04/p585-welling.pdf
BibTex:
@INPROCEEDINGS{Welling04,
AUTHOR = "Max Welling
",
TITLE = "On the Choice of Regions for Generalized Belief Propagation",
BOOKTITLE = "Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-04)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2004",
PAGES = "585--592"
}
|
|
