Join-graph based cost-shifting schemes
This work addresses inference challenges in graphical models for AI and machine learning applications, representing an incremental improvement by balancing existing methods.
The paper tackled the problem of bounding MPE queries in graphical models by developing hybrid algorithms that combine minibucket elimination and message-passing updates for linear programming relaxations, resulting in a heuristic that guided a Branch and Bound search to win first place in the PASCAL2 inference challenge.
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.