University of Cambridge > > Cambridge Image Analysis Seminars > Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation

Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation

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

If you have a question about this talk, please contact Dr Jan Lellmann.

We consider energy minimization for undirected graphical models, also known as the MAP -inference problem for Markov random fields. Although combinatorial methods, which return a provably optimal integral solution of the problem, made a significant progress in the past decade, they are still typically unable to cope with large-scale datasets. On the other hand, large scale datasets are often defined on sparse graphs and convex relaxation methods, such as linear programming relaxations then provide good approximations to integral solutions. We propose a novel method of combining combinatorial and convex programming techniques to obtain a global solution of the initial combinatorial problem. Based on the information obtained from the solution of the convex relaxation, our method confines application of the combinatorial solver to a small fraction of the initial graphical model, which allows to optimally solve much larger problems. We demonstrate the efficacy of our approach on a computer vision energy minimization benchmark.

This talk is part of the Cambridge Image Analysis Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


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