A Fast and Exact Energy Minimization Algorithm for Cycle MRFs

Huayan Wang, Koller Daphne
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):190-198, 2013.

Abstract

The presence of cycles gives rise to the difficulty in performing inference for MRFs. Handling cycles efficiently would greatly enhance our ability to tackle general MRFs. In particular, for dual decomposition of energy minimization (MAP inference), using cycle subproblems leads to a much tighter relaxation than using trees, but solving the cycle subproblems turns out to be the bottleneck. In this paper, we present a fast and exact algorithm for energy minimization in cycle MRFs, which can be used as a subroutine in tackling general MRFs. Our method builds on junction-tree message passing, with a large portion of the message entries pruned for efficiency. The pruning conditions fully exploit the structure of a cycle. Experimental results show that our algorithm is more than an order of magnitude faster than other state-of-the-art fast inference methods, and it performs consistently well in several different real problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-wang13f, title = {A Fast and Exact Energy Minimization Algorithm for Cycle MRFs}, author = {Wang, Huayan and Daphne, Koller}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {190--198}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/wang13f.pdf}, url = {https://proceedings.mlr.press/v28/wang13f.html}, abstract = {The presence of cycles gives rise to the difficulty in performing inference for MRFs. Handling cycles efficiently would greatly enhance our ability to tackle general MRFs. In particular, for dual decomposition of energy minimization (MAP inference), using cycle subproblems leads to a much tighter relaxation than using trees, but solving the cycle subproblems turns out to be the bottleneck. In this paper, we present a fast and exact algorithm for energy minimization in cycle MRFs, which can be used as a subroutine in tackling general MRFs. Our method builds on junction-tree message passing, with a large portion of the message entries pruned for efficiency. The pruning conditions fully exploit the structure of a cycle. Experimental results show that our algorithm is more than an order of magnitude faster than other state-of-the-art fast inference methods, and it performs consistently well in several different real problems.} }
Endnote
%0 Conference Paper %T A Fast and Exact Energy Minimization Algorithm for Cycle MRFs %A Huayan Wang %A Koller Daphne %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-wang13f %I PMLR %P 190--198 %U https://proceedings.mlr.press/v28/wang13f.html %V 28 %N 3 %X The presence of cycles gives rise to the difficulty in performing inference for MRFs. Handling cycles efficiently would greatly enhance our ability to tackle general MRFs. In particular, for dual decomposition of energy minimization (MAP inference), using cycle subproblems leads to a much tighter relaxation than using trees, but solving the cycle subproblems turns out to be the bottleneck. In this paper, we present a fast and exact algorithm for energy minimization in cycle MRFs, which can be used as a subroutine in tackling general MRFs. Our method builds on junction-tree message passing, with a large portion of the message entries pruned for efficiency. The pruning conditions fully exploit the structure of a cycle. Experimental results show that our algorithm is more than an order of magnitude faster than other state-of-the-art fast inference methods, and it performs consistently well in several different real problems.
RIS
TY - CPAPER TI - A Fast and Exact Energy Minimization Algorithm for Cycle MRFs AU - Huayan Wang AU - Koller Daphne BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-wang13f PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 190 EP - 198 L1 - http://proceedings.mlr.press/v28/wang13f.pdf UR - https://proceedings.mlr.press/v28/wang13f.html AB - The presence of cycles gives rise to the difficulty in performing inference for MRFs. Handling cycles efficiently would greatly enhance our ability to tackle general MRFs. In particular, for dual decomposition of energy minimization (MAP inference), using cycle subproblems leads to a much tighter relaxation than using trees, but solving the cycle subproblems turns out to be the bottleneck. In this paper, we present a fast and exact algorithm for energy minimization in cycle MRFs, which can be used as a subroutine in tackling general MRFs. Our method builds on junction-tree message passing, with a large portion of the message entries pruned for efficiency. The pruning conditions fully exploit the structure of a cycle. Experimental results show that our algorithm is more than an order of magnitude faster than other state-of-the-art fast inference methods, and it performs consistently well in several different real problems. ER -
APA
Wang, H. & Daphne, K.. (2013). A Fast and Exact Energy Minimization Algorithm for Cycle MRFs. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):190-198 Available from https://proceedings.mlr.press/v28/wang13f.html.

Related Material