Abstract
We propose Loop Corrected Belief Propagation (LCBP), a method for improving Belief Propagation (BP) that accounts for the influence of loops in graphical models. By calculating "cavity distributions"—the joint probability of a variable's neighbors when that variable is removed—and enforcing consistency between them, LCBP offers orders-of-magnitude better accuracy than standard methods on loopy graphs and is exact for models containing a single loop.
Introduction
Probabilistic inference, the task of calculating marginal probabilities in complex systems, is a cornerstone of machine learning and statistical physics. Belief Propagation (BP) is the standard algorithm for this task; however, it is only mathematically exact on trees. In graphs with loops (cycles), BP "double-counts" information as it circulates, leading to overconfident or incorrect results. While advanced methods like Generalized Belief Propagation (GBP) exist, they are often difficult to implement or fail to converge under strong interactions. LCBP bridges this gap by providing a robust, accurate framework for loopy real-world networks.
Methodology: The Cavity Approach
LCBP introduces a two-step approach based on the "cavity method" from statistical physics:
- Cavity Initialization: For every variable $i$, a "cavity" is created by temporarily removing $i$ and its connected factors. Standard BP is then run on this modified graph to estimate the joint probability distribution of $i$’s neighbors (its Markov blanket). This process effectively "breaks" the loops passing through that node, capturing the global network's influence on $i$ more accurately.
- Consistency Enforcement: Since cavity distributions are calculated independently, they may initially disagree. LCBP uses a message-passing algorithm to adjust these distributions until they are mutually consistent.
Unlike previous attempts at loop correction that relied on complex cumulant expansions, LCBP uses a simpler consistency requirement that works on arbitrary factor graphs and handles non-binary variables.
Key Results and Performance
The authors evaluated LCBP against benchmarks including Random Regular Graphs, Periodic Square Grids, and the ALARM medical diagnosis network.
- Accuracy Gains: On the ALARM network, LCBP achieved a Maximum Marginal Absolute Deviation (Max MAD) of 0.00054, a nearly 400x improvement over standard BP's 0.203.
- Robustness: In scenarios with high interaction where previous methods (like LCBP-CUM) failed to converge, LCBP remained stable.
- Comparison to GBP: LCBP frequently outperformed the Cluster Variation Method (CVM/GBP), demonstrating that capturing loop structure correctly is often more important than simply increasing cluster size.
Complexity and Limitations
The primary trade-off for LCBP's accuracy is its computational cost. The initialization of cavity distributions is exponential in the size of the Markov blanket (the number of neighbors). This makes the algorithm less suitable for extremely dense graphs where nodes have high connectivity.
Conclusion
LCBP represents a significant advancement in approximate inference for loopy graphical models. By leveraging the cavity method to break loops and enforcing local consistency, it provides a powerful alternative to standard BP and GBP. Future work remains to identify a corresponding free energy functional for the method and to develop more efficient approximations for the cavity distributions in dense networks.
Summary updated