Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
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.
Pages: 397-406
PS Link:
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)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "397--406"

hosted by DSL   •   site info   •   help