Join-graph based cost-shifting schemes

Alexander T. Ihler, Natalia Flerova, Rina Dechter, Lars Otten
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:395-404, 2012.

Abstract

We develop several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: minibucket elimination and message-passing updates for linear programming relaxations. Both methods are quite similar, and offer useful perspectives for the other; our hybrid approaches attempt to balance the advantages of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a Branch and Bound search guided by the heuristic function calculated by one of our new algorithms has recently won first place in the PASCAL2 inference challenge.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-ihler12a, title = {Join-graph based cost-shifting schemes}, author = {Ihler, Alexander T. and Flerova, Natalia and Dechter, Rina and Otten, Lars}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {395--404}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/ihler12a/ihler12a.pdf}, url = {https://proceedings.mlr.press/r10/ihler12a.html}, abstract = {We develop several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: minibucket elimination and message-passing updates for linear programming relaxations. Both methods are quite similar, and offer useful perspectives for the other; our hybrid approaches attempt to balance the advantages of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a Branch and Bound search guided by the heuristic function calculated by one of our new algorithms has recently won first place in the PASCAL2 inference challenge.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Join-graph based cost-shifting schemes %A Alexander T. Ihler %A Natalia Flerova %A Rina Dechter %A Lars Otten %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-ihler12a %I PMLR %P 395--404 %U https://proceedings.mlr.press/r10/ihler12a.html %V R10 %X We develop several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: minibucket elimination and message-passing updates for linear programming relaxations. Both methods are quite similar, and offer useful perspectives for the other; our hybrid approaches attempt to balance the advantages of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a Branch and Bound search guided by the heuristic function calculated by one of our new algorithms has recently won first place in the PASCAL2 inference challenge. %Z Reissued by PMLR on 04 October 2026.
APA
Ihler, A.T., Flerova, N., Dechter, R. & Otten, L.. (2012). Join-graph based cost-shifting schemes. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:395-404 Available from https://proceedings.mlr.press/r10/ihler12a.html. Reissued by PMLR on 04 October 2026.

Related Material