Finding the M Most Probable Configurations Using Loopy Belief Propagation

Abstract

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.