Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
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"
}


hosted by DSL   •   site info   •   help