HOP-MAP: Efficient Message Passing with High Order Potentials
Daniel Tarlow, Inmar E. Givoni, Richard S. Zemel · International Conference on Artificial Intelligence and Statistics · 2010
There is a growing interest in building probabilistic models with high order potentials (HOPs), or interactions, among discrete variables. Message passing inference in such models generally takes time exponential in the size of the interaction, but in some cases maximum a posteriori (MAP) inference can be carried out eciently. We build upon such results, introducing two new classes, including composite HOPs that allow us to exibly combine tractable HOPs using simple logical switching rules. We present ecient message update algorithms for the new HOPs, and we improve upon the eciency of message updates for a general class of existing HOPs. Importantly, we present both new and existing HOPs in a common representation; performing inference with any combination of these HOPs requires no change of representations or new derivations.