Exact and Approximate Inference in Associative Hierarchical Random Fields using Graph-Cuts

Chris Russell, Lubor Ladicky, Philip Torr, Pushmeet Kohli
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:500-507, 2010.

Abstract

Markov Networks are widely used through out computer vision and machine learning. An important subclass are the Associative Markov Networks which are used in a wide variety of applications. For these networks a good approximate minimum cost solution can be found efficiently using graph cut based move making algorithms such as alpha-expansion. Recently a related model has been proposed, the associative hierarchical network, which provides a natural generalisation of the Associative Markov Network for higher order cliques (i.e. clique size greater than two). This method provides a good model for object class segmentation problem in computer vision. Within this paper we briefly describe the associative hierarchical network and provide a computationally efficient method for approximate inference based on graph cuts. Our method performs well for networks containing hundreds of thousand of variables, and higher order potentials are defined over cliques containing tens of thousands of variables. Due to the size of these problems standard linear programming techniques are inapplicable. We show that our method has a bound of 4 for the solution of general associative hierarchical network with arbitrary clique size noting that few results on bounds exist for the solution of labelling of Markov Networks with higher order cliques.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-russell10a, title = {Exact and Approximate Inference in Associative Hierarchical Random Fields using Graph-Cuts}, author = {Russell, Chris and Ladicky, Lubor and Torr, Philip and Kohli, Pushmeet}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {500--507}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/russell10a/russell10a.pdf}, url = {https://proceedings.mlr.press/r8/russell10a.html}, abstract = {Markov Networks are widely used through out computer vision and machine learning. An important subclass are the Associative Markov Networks which are used in a wide variety of applications. For these networks a good approximate minimum cost solution can be found efficiently using graph cut based move making algorithms such as alpha-expansion. Recently a related model has been proposed, the associative hierarchical network, which provides a natural generalisation of the Associative Markov Network for higher order cliques (i.e. clique size greater than two). This method provides a good model for object class segmentation problem in computer vision. Within this paper we briefly describe the associative hierarchical network and provide a computationally efficient method for approximate inference based on graph cuts. Our method performs well for networks containing hundreds of thousand of variables, and higher order potentials are defined over cliques containing tens of thousands of variables. Due to the size of these problems standard linear programming techniques are inapplicable. We show that our method has a bound of 4 for the solution of general associative hierarchical network with arbitrary clique size noting that few results on bounds exist for the solution of labelling of Markov Networks with higher order cliques.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Exact and Approximate Inference in Associative Hierarchical Random Fields using Graph-Cuts %A Chris Russell %A Lubor Ladicky %A Philip Torr %A Pushmeet Kohli %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-russell10a %I PMLR %P 500--507 %U https://proceedings.mlr.press/r8/russell10a.html %V R8 %X Markov Networks are widely used through out computer vision and machine learning. An important subclass are the Associative Markov Networks which are used in a wide variety of applications. For these networks a good approximate minimum cost solution can be found efficiently using graph cut based move making algorithms such as alpha-expansion. Recently a related model has been proposed, the associative hierarchical network, which provides a natural generalisation of the Associative Markov Network for higher order cliques (i.e. clique size greater than two). This method provides a good model for object class segmentation problem in computer vision. Within this paper we briefly describe the associative hierarchical network and provide a computationally efficient method for approximate inference based on graph cuts. Our method performs well for networks containing hundreds of thousand of variables, and higher order potentials are defined over cliques containing tens of thousands of variables. Due to the size of these problems standard linear programming techniques are inapplicable. We show that our method has a bound of 4 for the solution of general associative hierarchical network with arbitrary clique size noting that few results on bounds exist for the solution of labelling of Markov Networks with higher order cliques. %Z Reissued by PMLR on 04 October 2026.
APA
Russell, C., Ladicky, L., Torr, P. & Kohli, P.. (2010). Exact and Approximate Inference in Associative Hierarchical Random Fields using Graph-Cuts. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:500-507 Available from https://proceedings.mlr.press/r8/russell10a.html. Reissued by PMLR on 04 October 2026.

Related Material