Join-graph based cost-shifting schemes
Alexander Ihler, Natalia Flerova, Rina Dechter, Lars Otten
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.
PDF Link: /papers/12/p397-ihler.pdf
AUTHOR = "Alexander Ihler
and Natalia Flerova and Rina Dechter and Lars Otten",
TITLE = "Join-graph based cost-shifting schemes",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "397--406"