Computer Science – Information Theory
Scientific paper
2010-09-13
Computer Science
Information Theory
30 pages, 10 figures
Scientific paper
Belief propagation is known to perform extremely well in many practical statistical inference and learning problems using graphical models, even in the presence of multiple loops. The use of the belief propagation algorithm on graphical models with loops is referred to as Loopy Belief Propagation (LBP). Various sufficient conditions for convergence of LBP have been presented; however, general necessary conditions for its convergence to a unique fixed point remain unknown. Because the approximation of beliefs to true marginal probabilities has been shown to relate to the convergence of LBP, several methods have been explored whose aim is to obtain distance bounds on beliefs when LBP fails to converge. In this paper, we derive uniform and non-uniform error bounds on LBP, which are tighter than existing ones in literature, and use these bounds to study the dynamic behavior of the sum-product algorithm. We subsequently use these bounds to derive sufficient conditions for the convergence of the sum-product algorithm, and analyze the relation between convergence of LBP and sparsity and walk-summability of graphical models. We finally use the bounds derived to investigate the accuracy of LBP, as well as the scheduling priority in asynchronous LBP.
Schonfeld Dan
Shi Xiangqiong
Tuninetti Daniela
No associations
LandOfFree
Message Error Analysis of Loopy Belief Propagation for the Sum-Product Algorithm 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 Message Error Analysis of Loopy Belief Propagation for the Sum-Product Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Message Error Analysis of Loopy Belief Propagation for the Sum-Product Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-337206