A Generalized Loop Correction Method for Approximate Inference in Graphical Models

Belief Propagation (BP) is one of the most popular methods for inference in probabilis-tic graphical models. BP is guaranteed to return the correct answer for tree structures, but can be incorrect or non-convergent for loopy graphical models. Recently, several new approximate inference algorithms based on cavity distribution have been proposed. These methods can account for the effect of loops by incorporating the dependency be-tween BP messages. Alternatively, region-based approximations (that lead to methods such as Generalized Belief Propagation) im-prove upon BP by considering interactions within small clusters of variables, thus tak-ing small loops within these clusters into ac-count. This paper introduces an approach, Generalized Loop Correction (GLC), that benefits from both of these types of loop cor-rection. We show how GLC relates to these two families of inference methods, then pro-vide empirical evidence that GLC works ef-fectively in general, and can be significantly more accurate than both correction schemes. 1