Improved Dynamic Schedules for Belief Propagation
This work addresses a computational bottleneck for practitioners using belief propagation in approximate inference, offering incremental improvements over existing dynamic schedules.
The paper tackles the inefficiency of dynamic update schedules in belief propagation by proposing to estimate message residuals instead of calculating them directly, which reduces the number of messages needed for convergence and cuts running time by up to a factor of five without compromising solution quality.
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.