Dynamic tree block coordinate ascent Conference Paper

Author(s): Tarlow, Daniel; Batra, Druv; Kohli, Pushmeet; Kolmogorov, Vladimir
Title: Dynamic tree block coordinate ascent
Abstract: This paper proposes a novel Linear Programming (LP) based algorithm, called Dynamic Tree-Block Coordinate Ascent (DT-BCA), for performing maximum a posteriori (MAP) inference in probabilistic graphical models. Unlike traditional message passing algorithms, which operate uniformly on the whole factor graph, our method dynamically chooses regions of the factor graph on which to focus message-passing efforts. We propose two criteria for selecting regions, including an efficiently computable upper-bound on the increase in the objective possible by passing messages in any particular region. This bound is derived from the theory of primal-dual methods from combinatorial optimization, and the forest that maximizes the bounds can be chosen efficiently using a maximum-spanning-tree-like algorithm. Experimental results show that our dynamic schedules significantly speed up state-of-the-art LP-based message-passing algorithms on a wide variety of real-world problems.
Keywords: Dynamic schedule; Dynamic trees; Factor graphs; Maximum a posteriori; Message passing algorithm; Primal-dual methods; Probabilistic graphical models; Real-world problem
Conference Title: ICML: International Conference on Machine Learning
Conference Dates: June 28 - July 2, 2011
Conference Location: Bellevue, WA, USA
Publisher: Omnipress  
Date Published: 2011-01-01
Start Page: 113
End Page: 120
Open access: no
IST Austria Authors
Related IST Austria Work