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

  Browse A-Z

Log in

Cambridge users (raven)details Other usersdetails No account?details

Information on

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

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

Add to your list(s) 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

CUUEG Spanish Researchers in the United Kingdom (SRUK) Museum of Archaeology & Anthropology

Other talks

Scale and anisotropic effects in necking of metallic tensile specimens Cohomology of the moduli space of curves Systems for Big Data Applications: Revolutionising personal computing Babraham Lecture - Deciphering the gene regulation network in human germline cells at single-cell & single base resolution EMERGING EPIGENETICS: DETECTING & MODIFYING EPIGENETICS MARKS Developing an optimisation algorithm to supervise active learning in drug discovery Towards bulk extension of near-horizon geometries Disease Migration Graded linearisations for linear algebraic group actions Protein Folding, Evolution and Interactions Symposium Cambridge - Corporate Finance Theory Symposium September 2017 - Day 2 St Catharine’s Political Economy Seminar - ‘Bank Credit Rating Changes, Capital Structure Adjustments and Lending’ by Claudia Girardone
 

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