/Efficient MAP approximation for dense energy functions

Efficient MAP approximation for dense energy functions

Marius Leordeanu and Martial Hebert
Conference Paper, International Conference on Machine Learning 2006, May, 2006

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


We present an efficient method for maximizing energy functions with first and second order potentials, suitable for MAP labeling estimation problems that arise in undirected graphical models. Our approach is to relax the integer constraints on the solution in two steps. First we efficiently obtain the relaxed global optimum following a procedure similar to the iterative power method for finding the largest eigenvector of a matrix. Next, we map the relaxed optimum on a simplex and show that the new energy obtained has a certain optimal bound. Starting from this energy we follow an efficient coordinate ascent procedure that is guaranteed to increase the energy at every step and converge to a solution that obeys the initial integral constraints. We also present a sufficient condition for ascent procedures that guarantees the increase in energy at every step.

BibTeX Reference
author = {Marius Leordeanu and Martial Hebert},
title = {Efficient MAP approximation for dense energy functions},
booktitle = {International Conference on Machine Learning 2006},
year = {2006},
month = {May},