BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Global MAP-Optimality by Shrinking the Combinatorial Search Area w
 ith Convex Relaxation - Bogdan Savchynskyy\, University of Heidelberg
DTSTART:20140521T140000Z
DTEND:20140521T150000Z
UID:TALK52499@talks.cam.ac.uk
CONTACT:Dr Jan Lellmann
DESCRIPTION:We consider energy minimization for undirected graphical model
 s\, also known as the MAP-inference problem for Markov random fields. Alth
 ough\ncombinatorial methods\, which return a provably optimal integral sol
 ution of the problem\, made a significant progress in the past decade\, th
 ey are still typically unable to cope with large-scale datasets. On the ot
 her hand\, large scale datasets are often defined on sparse graphs and con
 vex relaxation methods\, such as linear programming relaxations then provi
 de good approximations to integral solutions. We propose a novel method of
  combining combinatorial and convex programming techniques to obtain a glo
 bal solution of the initial combinatorial problem. Based on the informatio
 n obtained from the solution of the convex\nrelaxation\, our method confin
 es application of the combinatorial solver to a small fraction of the init
 ial graphical model\, which allows to optimally solve much larger problems
 . We demonstrate the efficacy of our approach on a computer vision energy 
 minimization benchmark. 
LOCATION:MR 5\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR