Correctness of local probability in graphical models with loops.

Area of Science:

• Artificial Intelligence
• Computer Science
• Probability Theory

Background:

• Graphical models like Bayesian and Markov networks use graphs to represent joint distributions.
• Local propagation rules ensure correct posterior probabilities in singly connected graphs.
• Empirical success of local propagation on graphs with loops lacks theoretical explanation.

Purpose of the Study:

• To provide a theoretical understanding of local propagation performance on graphical models with loops.
• To analyze the relationship between computed and correct marginals in loopy graphs.
• To explore the implications for maximum a posteriori (MAP) assignments and error-correcting codes.

Main Methods:

• Derivation of an analytical relationship for single-loop graphical models.
• Analysis of local propagation convergence and optimality conditions.
• Simulation of graphical models with multiple loops.

Main Results:

• An analytical relationship is derived for single-loop graphical models, linking computed and true marginals.
• A class of loopy graphical models is identified where local propagation yields provably optimal MAP assignments.
• Methods are presented for nodes to correct marginals using local message information.

Conclusions:

• Local propagation can achieve optimal MAP assignments in certain loopy graphical models, despite inaccurate marginals.
• The findings offer insights into the performance of turbo codes and similar error-correcting codes.
• The study extends theoretical understanding to graphical models with multiple loops.