D-CIS Publication Database

Publication

Type of publication:Article
Entered by:MN
TitleApproximate inference on planar graphs using Loop Calculus and Belief Propagation
Bibtex cite ID
Journal Journal of Machine Leaning Research
Year published 2009
Month December
ISSN 1533-7928
Keywords approximate inference,belief propagation
Abstract
We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop cal- culus (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 prop- agation (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 trunca- tion scheme on planar graphs and a new rep- resentation of the series in terms of Pfaffians of matrices. We analyze in detail both the loop series and the Pfaffian series for mod- els with binary variables and pairwise in- teractions, 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.
Authors
Gómez, Vicenç
Kappen, Hilbert J.
Chertkov, Michael
Topics
=SEE CLASSIFICATION DIFFERENCE FROM OTHERS=
BibTeXBibTeX
RISRIS
Attachments
 
Total mark: 5