Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Approximate inference on planar graphs using Loop Calculus and Belief Propagation
Vicenc Gomez, Hilbert Kappen, Michael Chertkov
We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop calculus (Chertkov and Chernyak, 2006b) allows to express the exact partition function Z of a graphical model as a finite sum of terms that can be evaluated once the belief propagation (BP) solution is known. In general, full summation over all correction terms is intractable. We develop an algorithm for the approach presented in Chertkov et al. (2008) which represents an efficient truncation scheme on planar graphs and a new representation of the series in terms of Pfaffians of matrices. We analyze in detail both the loop series and the Pfaffian series for models with binary variables and pairwise interactions, and show that the first term of the Pfaffian series can provide very accurate approximations. The algorithm outperforms previous truncation schemes of the loop series and is competitive with other state-of-the-art methods for approximate inference.
Keywords: null
Pages: 195-202
PS Link:
PDF Link: /papers/09/p195-gomez.pdf
AUTHOR = "Vicenc Gomez and Hilbert Kappen and Michael Chertkov",
TITLE = "Approximate inference on planar graphs using Loop Calculus and Belief Propagation",
BOOKTITLE = "Proceedings of the Twenty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-09)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2009",
PAGES = "195--202"

hosted by DSL   •   site info   •   help