BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Machine Learning @ CUED
SUMMARY:On the Equivalence of Graph Cuts and Max-product B
elief Propagation - Danny Tarlow (University of To
ronto)
DTSTART;TZID=Europe/London:20100825T140000
DTEND;TZID=Europe/London:20100825T150000
UID:TALK25930AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/25930
DESCRIPTION:(Joint work with Inmar Givoni\, Richard Zemel\, an
d Brendan Frey.)\n\nA common task in computer visi
on is the minimization of pairwise\nsubmodular ene
rgies over binary\nvariables. For such problems\,
both graph cuts and max-product belief\npropagatio
n are applicable.\nGraph cuts is guaranteed to pro
duce optimal solutions\, and empirically\nit does
so very quickly.\nMax-product can be applied in mo
re general settings\, but it is not\nguaranteed to
be optimal even in\nthe binary submodular case\,
and empirically it has been shown to\nproduce subo
ptimal results while\ntaking longer to do so.\n\nB
oth algorithms operate on parametric representatio
ns of an underlying\nenergy function\, and it is\n
known that both algorithms can be viewed as perfor
ming iterative\nreparameterizations of that energy
\nfunction. This suggests that despite the differe
nce in empirical\nperformance\, under a certain vi
ew\,\nthe two algorithms might be similar.\n\nIn t
his talk\, I will present graph cuts and max-produ
ct via this lense\nof reparameterization\, then I\
nwill develop the precise connection between the a
lgorithms\, showing\nthat with proper scheduling a
nd\ndamping\, max-product can be made equivalent t
o graph cuts. The end\nresult is a scheduling alg
orithm\nand damping procedure for max-product that
is guaranteed to be\nefficient and optimal on bin
ary\nsubmodular problems\, even when the graphical
model has loopy structure.
LOCATION:Engineering Department\, CBL Room 438
CONTACT:Peter Orbanz
END:VEVENT
END:VCALENDAR