Finding the M Most Probable Configurations using Loopy Belief Propagation

Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)

Bibtex Metadata Paper


Chen Yanover, Yair Weiss


Loopy belief propagation (BP) has been successfully used in a num- ber of di–cult graphical models to flnd the most probable conflgu- ration of the hidden variables. In applications ranging from protein folding to image analysis one would like to flnd not just the best conflguration 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 flnding the M best conflgura- tions when exact inference is impossible. We start by developing a new exact inference algorithm for calculat- ing the best conflgurations 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 conflgurations in graphs with hundreds of variables.