D-CIS Publication Database


Type of publication:Techreport
Entered by:JOSM
TitleTruncating the loop series expansion for BP
Bibtex cite ID
Year published 2006
Month December
Institution SNN Nijmegen, Foundation for Neural Networks
URL http://arxiv.org/abs/cs/0612109v2
Keywords belief propagation
Recently, M. Chertkov and V.Y. Chernyak derived an exact expression for the partition sum (normalization constant) corresponding to a graphical model, which is an expansion around the Belief Propagation solution. By adding correction terms to the BP free energy, one for each "generalized loop" in the factor graph, the exact partition sum is obtained. However, the usually enormous number of generalized loops generally prohibits summation over all correction terms. In this article we introduce Truncated Loop Series BP (TLSBP), a particular way of truncating the loop series of M. Chertkov and V.Y. Chernyak by considering generalized loops as compositions of simple loops. We analyze the performance of TLSBP in different scenarios, including the Ising model, regular random graphs and on Promedas, a large probabilistic medical diagnostic system. We show that TLSBP often improves upon the accuracy of the BP solution, at the expense of increased computation time. We also show that the performance of TLSBP strongly depends on the degree of interaction between the variables. For weak interactions, truncating the series leads to significant improvements, whereas for strong interactions it can be ineffective, even if a high number of terms is considered.
Gómez, Vicenç
Mooij, Joris
Kappen, Hilbert J.
Total mark: 5