Dynamic tree block coordinate ascent

D. Tarlow, D. Batra, P. Kohli, V. Kolmogorov, in:, Omnipress, 2011, pp. 113–120.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published
Author
; ; ;
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.
Publishing Year
Date Published
2011-01-01
Page
113 - 120
Conference
ICML: International Conference on Machine Learning
IST-REx-ID

Cite this

Tarlow D, Batra D, Kohli P, Kolmogorov V. Dynamic tree block coordinate ascent. In: Omnipress; 2011:113-120.
Tarlow, D., Batra, D., Kohli, P., & Kolmogorov, V. (2011). Dynamic tree block coordinate ascent (pp. 113–120). Presented at the ICML: International Conference on Machine Learning, Omnipress.
Tarlow, Daniel, Druv Batra, Pushmeet Kohli, and Vladimir Kolmogorov. “Dynamic Tree Block Coordinate Ascent,” 113–20. Omnipress, 2011.
D. Tarlow, D. Batra, P. Kohli, and V. Kolmogorov, “Dynamic tree block coordinate ascent,” presented at the ICML: International Conference on Machine Learning, 2011, pp. 113–120.
Tarlow D, Batra D, Kohli P, Kolmogorov V. 2011. Dynamic tree block coordinate ascent. ICML: International Conference on Machine Learning 113–120.
Tarlow, Daniel, et al. Dynamic Tree Block Coordinate Ascent. Omnipress, 2011, pp. 113–20.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar