INDIGO Home University of Illinois at Urbana-Champaign logo uic building uic pavilion uic student center

Bayesian Networks: Performance Analysis of Loopy Belief Propagation

Show simple item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF Shi_Xiangqiong.pdf (4MB) (no description provided) PDF
Title: Bayesian Networks: Performance Analysis of Loopy Belief Propagation
Author(s): Shi, Xiangqiong
Advisor(s): Schonfeld, Dan; Tuninetti, Daniela
Contributor(s): Tuninetti, Daniela; Devroye, Natasha; Yau, Stephen; Wang, Junhui
Department / Program: Electrical and Computer Engineering
Graduate Major: Electrical and Computer Engineering
Degree Granting Institution: University of Illinois at Chicago
Degree: PhD, Doctor of Philosophy
Genre: Doctoral
Subject(s): Graphical Model Bayesian Networks Loopy Belief Propagation Sum-Product Max-Product Image Segmentation
Abstract: Loopy belief propagation (LBP) is a probability inference algorithm on Graphical Models. It has been successfully applied in low-density parity-check codes, turbo codes, computer vision problems such as stereo matching, image segmentation and image impainting. Belief propagation was first proposed by Judea Pearl in 1982 for tree-structured graphs, and was extended to poly-trees in 1983, and later applied to general graphs with empirical success. Since LBP ignores the loopy structure of graphs and blindly propagates messages, many researchers have focused in analyzing its performance of convergence and accuracy, and presented variations of message passing algorithm. In this thesis, we focus on the performance analysis of LBP with respect to error bound and convergence. We present novel results that show the relationship between the performance of LBP and the strength of potential functions as well as topology structure of graphical models. Specifically, we first present lower-bound and upper-bound on multiplicative message errors. Then we present uniform and non-uniform distance bound on beliefs, which can improve an existing accuracy bound between beliefs and true marginals. Thereafter, we present our non-uniform sufficient convergence condition for LBP, which is shown to be better than existing conditions. We also show our error bound is related with the rate of convergence of LBP. Furthermore, we analyze fixed points of completely uniform binary graph, and present tight distance bound between beliefs. Finally, we implement LBP algorithm for an image segmentation application, and show how the segmentation performance is affected by some parameters in potential functions.
Issue Date: 2012-12-07
Genre: thesis
Rights Information: Copyright 2011 Xiangqiong Shi
Date Available in INDIGO: 2014-04-15
Date Deposited: 2011-08

This item appears in the following Collection(s)

Show simple item record


Country Code Views
United States of America 304
China 120
Russian Federation 17
Japan 13
United Kingdom 8


My Account


Access Key