BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On the Equivalence of Graph Cuts and Max-product Belief Propagatio
 n - Danny Tarlow (University of Toronto)
DTSTART:20100825T130000Z
DTEND:20100825T140000Z
UID:TALK25930@talks.cam.ac.uk
CONTACT:Peter Orbanz
DESCRIPTION:(Joint work with Inmar Givoni\, Richard Zemel\, and Brendan Fr
 ey.)\n\nA common task in computer vision is the minimization of pairwise\n
 submodular energies over binary\nvariables. For such problems\, both graph
  cuts and max-product belief\npropagation are applicable.\nGraph cuts is g
 uaranteed to produce optimal solutions\, and empirically\nit does so very 
 quickly.\nMax-product can be applied in more general settings\, but it is 
 not\nguaranteed to be optimal even in\nthe binary submodular case\, and em
 pirically it has been shown to\nproduce suboptimal results while\ntaking l
 onger to do so.\n\nBoth algorithms operate on parametric representations o
 f an underlying\nenergy function\, and it is\nknown that both algorithms c
 an be viewed as performing iterative\nreparameterizations of that energy\n
 function. This suggests that despite the difference in empirical\nperforma
 nce\, under a certain view\,\nthe two algorithms might be similar.\n\nIn t
 his talk\, I will present graph cuts and max-product via this lense\nof re
 parameterization\, then I\nwill develop the precise connection between the
  algorithms\, showing\nthat with proper scheduling and\ndamping\, max-prod
 uct can be made equivalent to graph cuts.  The end\nresult is a scheduling
  algorithm\nand damping procedure for max-product that is guaranteed to be
 \nefficient and optimal on binary\nsubmodular problems\, even when the gra
 phical model has loopy structure.
LOCATION:Engineering Department\, CBL Room 438
END:VEVENT
END:VCALENDAR