Incremental region selection for mini-bucket elimination bounds

Sholeh Forouzan, Alexander Ihler
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:139-148, 2015.

Abstract

Region choice is a key issue for many approximate inference bounds. Mini-bucket elimination avoids the space and time complexity of exact inference by using a top-down partitioning approach that mimics the construction of a junction tree and aims to minimize the number of regions subject to a bound on their size; however, these methods rarely take into account functions’ values. In contrast, message passing algorithms often use “cluster pursuit” methods to select regions, a bottom-up approach in which a predefined set of clusters (such as triplets) is scored and incrementally added. In this work, we develop a hybrid approach that balances the advantages of both perspectives, providing larger regions chosen in an intelligent, energy-based way. Our method is applicable to bounds on a variety of inference tasks, and we demonstrate its power empirically on a broad array of problem types.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-forouzan15a, title = {Incremental region selection for mini-bucket elimination bounds}, author = {Forouzan, Sholeh and Ihler, Alexander}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {139--148}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/forouzan15a/forouzan15a.pdf}, url = {https://proceedings.mlr.press/r13/forouzan15a.html}, abstract = {Region choice is a key issue for many approximate inference bounds. Mini-bucket elimination avoids the space and time complexity of exact inference by using a top-down partitioning approach that mimics the construction of a junction tree and aims to minimize the number of regions subject to a bound on their size; however, these methods rarely take into account functions’ values. In contrast, message passing algorithms often use “cluster pursuit” methods to select regions, a bottom-up approach in which a predefined set of clusters (such as triplets) is scored and incrementally added. In this work, we develop a hybrid approach that balances the advantages of both perspectives, providing larger regions chosen in an intelligent, energy-based way. Our method is applicable to bounds on a variety of inference tasks, and we demonstrate its power empirically on a broad array of problem types.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Incremental region selection for mini-bucket elimination bounds %A Sholeh Forouzan %A Alexander Ihler %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-forouzan15a %I PMLR %P 139--148 %U https://proceedings.mlr.press/r13/forouzan15a.html %V R13 %X Region choice is a key issue for many approximate inference bounds. Mini-bucket elimination avoids the space and time complexity of exact inference by using a top-down partitioning approach that mimics the construction of a junction tree and aims to minimize the number of regions subject to a bound on their size; however, these methods rarely take into account functions’ values. In contrast, message passing algorithms often use “cluster pursuit” methods to select regions, a bottom-up approach in which a predefined set of clusters (such as triplets) is scored and incrementally added. In this work, we develop a hybrid approach that balances the advantages of both perspectives, providing larger regions chosen in an intelligent, energy-based way. Our method is applicable to bounds on a variety of inference tasks, and we demonstrate its power empirically on a broad array of problem types. %Z Reissued by PMLR on 04 October 2026.
APA
Forouzan, S. & Ihler, A.. (2015). Incremental region selection for mini-bucket elimination bounds. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:139-148 Available from https://proceedings.mlr.press/r13/forouzan15a.html. Reissued by PMLR on 04 October 2026.

Related Material