Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Graph Cuts is a Max-Product Algorithm
Daniel Tarlow, Inmar Givoni, Richard Zemel, Brendan Frey
The maximum a posteriori (MAP) configuration of binary variable models with submodular graph-structured energy functions can be found efficiently and exactly by graph cuts. Max-product belief propagation (MP) has been shown to be suboptimal on this class of energy functions by a canonical counterexample where MP converges to a suboptimal fixed point (Kulesza & Pereira, 2008). In this work, we show that under a particular scheduling and damping scheme, MP is equivalent to graph cuts, and thus optimal. We explain the apparent contradiction by showing that with proper scheduling and damping, MP always converges to an optimal fixed point. Thus, the canonical counterexample only shows the suboptimality of MP with a particular suboptimal choice of schedule and damping. With proper choices, MP is optimal.
Pages: 671-680
PS Link:
PDF Link: /papers/11/p671-tarlow.pdf
AUTHOR = "Daniel Tarlow and Inmar Givoni and Richard Zemel and Brendan Frey",
TITLE = "Graph Cuts is a Max-Product Algorithm",
BOOKTITLE = "Proceedings of the Twenty-Seventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-11)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2011",
PAGES = "671--680"

hosted by DSL   •   site info   •   help