Solving Markov Random Fields using Semi Definite Programming

Philip H. S. Torr
Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, PMLR R4:292-299, 2003.

Abstract

This paper explores a new generic method for matching, when there are conditional dependencies between the matches. It allows different sorts of features to be matched in the same global optimization framework. The method is based on a binary Markov random field model which is defined on the product space of matches, and is shown to be equivalent to $0-1$ quadratic programming, and the MAXCUT graph problem. In general these problem are $N P$ complete. However our approach takes inspiration from the celebrated result of Goemans and Williamson (1995) that finds a polynomial time 0.879 approximation to several $N P$ complete, using semidefinite programming. The method is demonstrated for the problem of curve matching.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR4-torr03a, title = {Solving Markov Random Fields using Semi Definite Programming}, author = {Torr, Philip H. S.}, booktitle = {Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics}, pages = {292--299}, year = {2003}, editor = {Bishop, Christopher M. and Frey, Brendan J.}, volume = {R4}, series = {Proceedings of Machine Learning Research}, month = {03--06 Jan}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/r4/torr03a/torr03a.pdf}, url = {https://proceedings.mlr.press/r4/torr03a.html}, abstract = {This paper explores a new generic method for matching, when there are conditional dependencies between the matches. It allows different sorts of features to be matched in the same global optimization framework. The method is based on a binary Markov random field model which is defined on the product space of matches, and is shown to be equivalent to $0-1$ quadratic programming, and the MAXCUT graph problem. In general these problem are $N P$ complete. However our approach takes inspiration from the celebrated result of Goemans and Williamson (1995) that finds a polynomial time 0.879 approximation to several $N P$ complete, using semidefinite programming. The method is demonstrated for the problem of curve matching.}, note = {Reissued by PMLR on 01 April 2021.} }
Endnote
%0 Conference Paper %T Solving Markov Random Fields using Semi Definite Programming %A Philip H. S. Torr %B Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2003 %E Christopher M. Bishop %E Brendan J. Frey %F pmlr-vR4-torr03a %I PMLR %P 292--299 %U https://proceedings.mlr.press/r4/torr03a.html %V R4 %X This paper explores a new generic method for matching, when there are conditional dependencies between the matches. It allows different sorts of features to be matched in the same global optimization framework. The method is based on a binary Markov random field model which is defined on the product space of matches, and is shown to be equivalent to $0-1$ quadratic programming, and the MAXCUT graph problem. In general these problem are $N P$ complete. However our approach takes inspiration from the celebrated result of Goemans and Williamson (1995) that finds a polynomial time 0.879 approximation to several $N P$ complete, using semidefinite programming. The method is demonstrated for the problem of curve matching. %Z Reissued by PMLR on 01 April 2021.
APA
Torr, P.H.S.. (2003). Solving Markov Random Fields using Semi Definite Programming. Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R4:292-299 Available from https://proceedings.mlr.press/r4/torr03a.html. Reissued by PMLR on 01 April 2021.

Related Material