The operation of belief propagation is simple (you may derive the definition by its operation). At each iteration of the algorithm messages are passed from message nodes to check nodes, and from check nodes back to message nodes. The messages from message nodes V to check nodes C are estimate based on the observed value of the V and some of the messages passed from the neighboring check nodes C to that message node. An important perspective is that the message that is sent from a V to a C must not take into account the message sent in the previous round from C to V. The same is apply for messages passed from C to V.
More formal definition is given
http://www.tsc.uc3m.es/~fernando/BP_LDPC.pdf
https://www.cs.cmu.edu/~venkatg/pubs/papers/ldpc.pdf
There is extensive literature on belief propagation algorithm, also known as sum product algorithm. Generally, it is one kind of (approximate) Bayesian inference method which computes the marginal probability efficiently using the generalized distributive law and dynamic programming idea. Belief propagation is deeply related to factor graph, which is a bipartite graph model that encodes the factorization of a joint distribution function. It is widely used in information theory and computer scince.
For the exact definition, the following materials are greatly referred (of courese, much more good refrences are not listed here):
[1] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inf. Theory,vol.47, no.2, pp. 498–519, Feb. 2001.
[2] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausble Inference. San Mateo, CA,USA:MorganKaufmann, 1988.
[3] M. J. Wainwright and M. I. Jordan, “Graphical models, exponential families, and variational inference,” Found. Trends Mach. Learn., vol. 1, no. 1–2, pp. 1–305, 2008.
[4] C. M. Bishop, Pattern Recognition and Machine Learning.New York, NY, USA: Springer, 2006.
[5] T. Richardson and R. Urbanke, Modern coding theory. Cambridge University Press, 2008.
[6] D. Koller and N. Friedman, Probabilistic Graphical Models: Principles and Techniques. USA: MIT Press, 2009.
As the name said, it is belief propagation. So, on the Tanner Graph, the nodes exchange by means of messages the value of their "Belief" so that any other node will have its own Belief + the beliefs of the nodes it has connections with. This will increase the amount of information available at each node.
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling