MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts

M. Pawan Kumar, Daphne Koller
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:313-320, 2009.

Abstract

We consider the task of obtaining the maximum a posteriori estimate of discrete pairwise random fields with arbitrary unary potentials and semimetric pairwise potentials. For this problem, we propose an accurate hierarchical move making strategy where each move is computed efficiently by solving an st-MINCUT problem. Unlike previous move making approaches, e.g. the widely used a-expansion algorithm, our method obtains the guarantees of the standard linear programming (LP) relaxation for the important special case of metric labeling. Unlike the existing LP relaxation solvers, e.g. interior-point algorithms or tree-reweighted message passing, our method is significantly faster as it uses only the efficient st-MINCUT algorithm in its design. Using both synthetic and real data experiments, we show that our technique outperforms several commonly used algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-kumar09a, title = {{MAP} Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts}, author = {Kumar, M. Pawan and Koller, Daphne}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {313--320}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/kumar09a/kumar09a.pdf}, url = {https://proceedings.mlr.press/r7/kumar09a.html}, abstract = {We consider the task of obtaining the maximum a posteriori estimate of discrete pairwise random fields with arbitrary unary potentials and semimetric pairwise potentials. For this problem, we propose an accurate hierarchical move making strategy where each move is computed efficiently by solving an st-MINCUT problem. Unlike previous move making approaches, e.g. the widely used a-expansion algorithm, our method obtains the guarantees of the standard linear programming (LP) relaxation for the important special case of metric labeling. Unlike the existing LP relaxation solvers, e.g. interior-point algorithms or tree-reweighted message passing, our method is significantly faster as it uses only the efficient st-MINCUT algorithm in its design. Using both synthetic and real data experiments, we show that our technique outperforms several commonly used algorithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts %A M. Pawan Kumar %A Daphne Koller %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-kumar09a %I PMLR %P 313--320 %U https://proceedings.mlr.press/r7/kumar09a.html %V R7 %X We consider the task of obtaining the maximum a posteriori estimate of discrete pairwise random fields with arbitrary unary potentials and semimetric pairwise potentials. For this problem, we propose an accurate hierarchical move making strategy where each move is computed efficiently by solving an st-MINCUT problem. Unlike previous move making approaches, e.g. the widely used a-expansion algorithm, our method obtains the guarantees of the standard linear programming (LP) relaxation for the important special case of metric labeling. Unlike the existing LP relaxation solvers, e.g. interior-point algorithms or tree-reweighted message passing, our method is significantly faster as it uses only the efficient st-MINCUT algorithm in its design. Using both synthetic and real data experiments, we show that our technique outperforms several commonly used algorithms. %Z Reissued by PMLR on 04 October 2026.
APA
Kumar, M.P. & Koller, D.. (2009). MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:313-320 Available from https://proceedings.mlr.press/r7/kumar09a.html. Reissued by PMLR on 04 October 2026.

Related Material