An Alternating Direction Method for Dual MAP LP Relaxation
Abstract
Maximum a-posteriori (MAP) estimation is an important task in many applications of probabilistic graphical models. Although finding an exact solution is generally intractable, approximations based on linear programming (LP) relaxation often provide good approximate solutions. In this paper we present an algorithm for solving the LP relaxation optimization problem. In order to overcome the lack of strict convexity, we apply an augmented Lagrangian method to the dual LP. The algorithm, based on the alternating direction method of multipliers (ADMM), is guaranteed to converge to the global optimum of the LP relaxation objective. Our experimental results show that this algorithm is competitive with other state-of-the-art algorithms for approximate MAP estimation.
Cite
Text
Meshi and Globerson. "An Alternating Direction Method for Dual MAP LP Relaxation." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2011. doi:10.1007/978-3-642-23783-6_30Markdown
[Meshi and Globerson. "An Alternating Direction Method for Dual MAP LP Relaxation." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2011.](https://mlanthology.org/ecmlpkdd/2011/meshi2011ecmlpkdd-alternating/) doi:10.1007/978-3-642-23783-6_30BibTeX
@inproceedings{meshi2011ecmlpkdd-alternating,
title = {{An Alternating Direction Method for Dual MAP LP Relaxation}},
author = {Meshi, Ofer and Globerson, Amir},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2011},
pages = {470-483},
doi = {10.1007/978-3-642-23783-6_30},
url = {https://mlanthology.org/ecmlpkdd/2011/meshi2011ecmlpkdd-alternating/}
}