Truncating the loop series expansion for Belief Propagation

Details Truncating the loop series expansion for Belief Propagation Truncating the loop series expansion for Belief Propagation

2006-12-21

arxiv.org/abs/cs/0612109v2

The Journal of Machine Learning Research, 8(Sep):1987--2016, 2007

Computer Science

Artificial Intelligence

31 pages, 12 figures, submitted to Journal of Machine Learning Research

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Truncating the loop series expansion for Belief Propagation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Truncating the loop series expansion for Belief Propagation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Truncating the loop series expansion for Belief Propagation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-21861