Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Accuracy Bounds for Belief Propagation
Alexander Ihler
The belief propagation (BP) algorithm is widely applied to perform approximate infer- ence on arbitrary graphical models, in part due to its excellent empirical properties and performance. However, little is known theo- retically about when this algorithm will per- form well. Using recent analysis of conver- gence and stability properties in BP and new results on approximations in binary systems, we derive a bound on the error in BP's es- timates for pairwise Markov random fields over discrete{valued random variables. Our bound is relatively simple to compute, and compares favorably with a previous method of bounding the accuracy of BP.
Pages: 183-190
PS Link:
PDF Link: /papers/07/p183-ihler.pdf
AUTHOR = "Alexander Ihler ",
TITLE = "Accuracy Bounds for Belief Propagation",
BOOKTITLE = "Proceedings of the Twenty-Third Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-07)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2007",
PAGES = "183--190"

hosted by DSL   •   site info   •   help