University of Cambridge > Talks.cam > Machine Learning @ CUED > On the Equivalence of Graph Cuts and Max-product Belief Propagation

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

On the Equivalence of Graph Cuts and Max-product Belief Propagation

Download to your calendar using vCal

If you have a question about this talk, please contact Peter Orbanz .

(Joint work with Inmar Givoni, Richard Zemel, and Brendan Frey.)

A common task in computer vision is the minimization of pairwise submodular energies over binary variables. For such problems, both graph cuts and max-product belief propagation are applicable. Graph cuts is guaranteed to produce optimal solutions, and empirically it does so very quickly. Max-product can be applied in more general settings, but it is not guaranteed to be optimal even in the binary submodular case, and empirically it has been shown to produce suboptimal results while taking longer to do so.

Both algorithms operate on parametric representations of an underlying energy function, and it is known that both algorithms can be viewed as performing iterative reparameterizations of that energy function. This suggests that despite the difference in empirical performance, under a certain view, the two algorithms might be similar.

In this talk, I will present graph cuts and max-product via this lense of reparameterization, then I will develop the precise connection between the algorithms, showing that with proper scheduling and damping, max-product can be made equivalent to graph cuts. The end result is a scheduling algorithm and damping procedure for max-product that is guaranteed to be efficient and optimal on binary submodular problems, even when the graphical model has loopy structure.

This talk is part of the Machine Learning @ CUED series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Cambridge Public Policy Webinar & FW11, Computer Laboratory, William Gates Building. seodahisi

Other talks

Synthesizing Diverse Policies for Multi-Agent Coordination title abstract tbc From lab to clinic: an introduction to translational research BSU Seminar: "Response Adaptivity Across Clinical Trials In Portfolios of Biomedical Innovations" Group Work Differences between Robin and Neumann eigenvalues
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity