Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)
Chen Yanover, Yair Weiss
Loopy belief propagation (BP) has been successfully used in a num- ber of di–cult graphical models to ﬂnd the most probable conﬂgu- ration of the hidden variables. In applications ranging from protein folding to image analysis one would like to ﬂnd not just the best conﬂguration but rather the top M . While this problem has been solved using the junction tree formalism, in many real world prob- lems the clique size in the junction tree is prohibitively large. In this work we address the problem of ﬂnding the M best conﬂgura- tions when exact inference is impossible. We start by developing a new exact inference algorithm for calculat- ing the best conﬂgurations that uses only max-marginals. For ap- proximate inference, we replace the max-marginals with the beliefs calculated using max-product BP and generalized BP. We show em- pirically that the algorithm can accurately and rapidly approximate the M best conﬂgurations in graphs with hundreds of variables.