Improved Dynamic Schedules for Belief Propagation

Charles Sutton, Andrew McCallum

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Belief propagation and its variants are popular methods for approximate inference, but their running time and even their convergence depend greatly on the schedule used to send the messages. Recently, dynamic update schedules have been shown to converge much faster on hard networks than static schedules, namely the residual BP schedule of Elidan et al. [2006]. But that RBP algorithm wastes message updates: many messages are computed solely to determine their priority, and are never actually performed. In this paper, we show that estimating the residual, rather than calculating it directly, leads to significant decreases in the number of messages required for convergence, and in the total running time. The residual is estimated using an upper bound based on recent work on message errors in BP. On both synthetic and real-world networks, this dramatically decreases the running time of BP, in some cases by a factor of five, without affecting the quality of the solution.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Third Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-07)
Place of PublicationCorvallis, Oregon
PublisherAUAI Press
Number of pages8
ISBN (Print)0-9749039-3-0
Publication statusPublished - 2007


Dive into the research topics of 'Improved Dynamic Schedules for Belief Propagation'. Together they form a unique fingerprint.

Cite this