Neural Computation · 2000 · 470 citations · 25 references
Natural SciencesMathematicsBayesian Data AnalysisStatistical ModelingStochastic ModelingBayesian InferenceBayesian ModelingBayesian StatisticsDirected Acyclic GraphsGraph TheoryProbabilistic ModelingBayesian Graphical ModelsBayesian NetworksBelief PropagationGraphical ModelsMarkov Network ModelsPosterior Model ProbabilitiesTurbo Codes
Graphical models encode joint distributions, and while local propagation is guaranteed to converge on singly connected graphs, its empirical success on loopy graphs lacks theoretical explanation. The authors aim to derive an analytical relationship between local propagation outputs and true marginals for single-loop graphical models. They demonstrate how nodes can use local message information to correct marginals and extend the analysis to multi-loop graphs with supporting simulations. The analysis identifies a class of loopy models where local propagation yields provably optimal MAP assignments despite incorrect marginals, and discusses implications for turbo codes.
Graphical models, such as Bayesian networks and Markov networks, represent joint distributions over a set of variables by means of a graph. When the graph is singly connected, local propagation rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities. Recently a number of researchers have empirically demonstrated good performance of these same local propagation schemes on graphs with loops, but a theoretical understanding of this performance has yet to be achieved. For graphical models with a single loop, we derive an analytical relationship between the probabilities computed using local propagation and the correct marginals. Using this relationship we show a category of graphical models with loops for which local propagation gives rise to provably optimal maximum a posteriori assignments (although the computed marginals will be incorrect). We also show how nodes can use local information in the messages they receive in order to correct their computed marginals. We discuss how these results can be extended to graphical models with multiple loops and show simulation results suggesting that some properties of propagation on single-loop graphs may hold for a larger class of graphs. Specifically we discuss the implication of our results for understanding a class of recently proposed error-correcting codes known as turbo codes.
25
Low-density parity-check codes
Robert G. Gallager · IEEE Transactions on Information Theory · 1962 · 10.6K citations · Full text