Efficient and Exact MAP-MRF Inference using Branch and Bound

Min Sun, Murali Telaprolu, Honglak Lee, Silvio Savarese
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1134-1142, 2012.

Abstract

We propose two novel Branch-and-Bound (BB) methods to efficiently solve exact MAP-MRF inference on problems with a large number of states (per variable) H. By organizing the data in a suitable structure, the time complexity of our best method for evaluating the bound at each branch is reduced from O(H^2) to O(H). This permits searching for the MAP solution in O(BH+Q) instead of O(BH^2) (without using the data structure), where B is the number of branches and Q is the one-time cost to build the data structure which is proportional to H^2. Our analysis on synthetic data shows that, given a limited time budget, our method solves problems that are characterized by a much larger number of states when compared to state-of-the-art exact inference algorithms (e.g., Marinescu and Dechter (2007); Sontag et al. (2008)) and other baseline BB methods. We further show that our method is well suited for computer vision and computational biology problems where the state space (per variable) is large. In particular, our approach is an order of magnitude faster on average than Sontag et al.’s Cluster Pursuit (CP) on human pose estimation problems. Moreover, given a time budget of up to 20 minutes, our method consistently solves more protein design problems than CP does. Finally, we successfully explore different branching strategies and ways to utilize domain knowledge of the problem to significantly reduce the empirical inference time.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-sun12, title = {Efficient and Exact MAP-MRF Inference using Branch and Bound}, author = {Sun, Min and Telaprolu, Murali and Lee, Honglak and Savarese, Silvio}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1134--1142}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/sun12/sun12.pdf}, url = {https://proceedings.mlr.press/v22/sun12.html}, abstract = {We propose two novel Branch-and-Bound (BB) methods to efficiently solve exact MAP-MRF inference on problems with a large number of states (per variable) H. By organizing the data in a suitable structure, the time complexity of our best method for evaluating the bound at each branch is reduced from O(H^2) to O(H). This permits searching for the MAP solution in O(BH+Q) instead of O(BH^2) (without using the data structure), where B is the number of branches and Q is the one-time cost to build the data structure which is proportional to H^2. Our analysis on synthetic data shows that, given a limited time budget, our method solves problems that are characterized by a much larger number of states when compared to state-of-the-art exact inference algorithms (e.g., Marinescu and Dechter (2007); Sontag et al. (2008)) and other baseline BB methods. We further show that our method is well suited for computer vision and computational biology problems where the state space (per variable) is large. In particular, our approach is an order of magnitude faster on average than Sontag et al.’s Cluster Pursuit (CP) on human pose estimation problems. Moreover, given a time budget of up to 20 minutes, our method consistently solves more protein design problems than CP does. Finally, we successfully explore different branching strategies and ways to utilize domain knowledge of the problem to significantly reduce the empirical inference time.} }
Endnote
%0 Conference Paper %T Efficient and Exact MAP-MRF Inference using Branch and Bound %A Min Sun %A Murali Telaprolu %A Honglak Lee %A Silvio Savarese %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-sun12 %I PMLR %P 1134--1142 %U https://proceedings.mlr.press/v22/sun12.html %V 22 %X We propose two novel Branch-and-Bound (BB) methods to efficiently solve exact MAP-MRF inference on problems with a large number of states (per variable) H. By organizing the data in a suitable structure, the time complexity of our best method for evaluating the bound at each branch is reduced from O(H^2) to O(H). This permits searching for the MAP solution in O(BH+Q) instead of O(BH^2) (without using the data structure), where B is the number of branches and Q is the one-time cost to build the data structure which is proportional to H^2. Our analysis on synthetic data shows that, given a limited time budget, our method solves problems that are characterized by a much larger number of states when compared to state-of-the-art exact inference algorithms (e.g., Marinescu and Dechter (2007); Sontag et al. (2008)) and other baseline BB methods. We further show that our method is well suited for computer vision and computational biology problems where the state space (per variable) is large. In particular, our approach is an order of magnitude faster on average than Sontag et al.’s Cluster Pursuit (CP) on human pose estimation problems. Moreover, given a time budget of up to 20 minutes, our method consistently solves more protein design problems than CP does. Finally, we successfully explore different branching strategies and ways to utilize domain knowledge of the problem to significantly reduce the empirical inference time.
RIS
TY - CPAPER TI - Efficient and Exact MAP-MRF Inference using Branch and Bound AU - Min Sun AU - Murali Telaprolu AU - Honglak Lee AU - Silvio Savarese BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-sun12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 1134 EP - 1142 L1 - http://proceedings.mlr.press/v22/sun12/sun12.pdf UR - https://proceedings.mlr.press/v22/sun12.html AB - We propose two novel Branch-and-Bound (BB) methods to efficiently solve exact MAP-MRF inference on problems with a large number of states (per variable) H. By organizing the data in a suitable structure, the time complexity of our best method for evaluating the bound at each branch is reduced from O(H^2) to O(H). This permits searching for the MAP solution in O(BH+Q) instead of O(BH^2) (without using the data structure), where B is the number of branches and Q is the one-time cost to build the data structure which is proportional to H^2. Our analysis on synthetic data shows that, given a limited time budget, our method solves problems that are characterized by a much larger number of states when compared to state-of-the-art exact inference algorithms (e.g., Marinescu and Dechter (2007); Sontag et al. (2008)) and other baseline BB methods. We further show that our method is well suited for computer vision and computational biology problems where the state space (per variable) is large. In particular, our approach is an order of magnitude faster on average than Sontag et al.’s Cluster Pursuit (CP) on human pose estimation problems. Moreover, given a time budget of up to 20 minutes, our method consistently solves more protein design problems than CP does. Finally, we successfully explore different branching strategies and ways to utilize domain knowledge of the problem to significantly reduce the empirical inference time. ER -
APA
Sun, M., Telaprolu, M., Lee, H. & Savarese, S.. (2012). Efficient and Exact MAP-MRF Inference using Branch and Bound. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:1134-1142 Available from https://proceedings.mlr.press/v22/sun12.html.

Related Material