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

Add to your list(s) Download to your calendar using vCal

• Danny Tarlow (University of Toronto)
• Wednesday 25 August 2010, 14:00-15:00
• Engineering Department, CBL Room 438.

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:

• Seminar
• All Talks (aka the CURE list)
• Biology
• CBL important
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge Neuroscience Seminars
• Cambridge talks
• Chris Davis' list
• Creating transparent intact animal organs for high-resolution 3D deep-tissue imaging
• Engineering Department, CBL Room 438
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• Joint Machine Learning Seminars
• Life Science
• Life Sciences
• ML
• Machine Learning @ CUED
• Machine Learning Summary
• Neuroscience
• Neuroscience Seminars
• Neuroscience Seminars
• Required lists for MLG
• Simon Baker's List
• Stem Cells & Regenerative Medicine
• Trust & Technology Initiative - interesting events
• bld31
• dh539
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list

Note that ex-directory lists are not shown.