https://web.stanford.edu/~montanar/RESEARCH/BOOK/partD.pdf

University of Michigan - Ann Arbor

Belief Propagation is an iterative message passing algorithm used within graphs or trees. In Bayesian Networks, bayesian likelihoods are calculated at certain nodes and passed up or down the network.

* If the message is passed downward (e.g. from parent to child), the child can update its beliefs using conditional probabilities.
* If the message is passed upward (e.g. from child to parent), the parent can update its beliefs by multiplying them by a likelihood ratio.

Belief Propagation in Bayesian Networks

Belief Propagation

1. Evidence to child nodes is introduced (red circles in bottom nodes). The new information is passed to intermediate nodes who update their belief.
2. The update is passed up to the parent node (as well as down to uninstantiated child nodes)
3. Crucially, the belief update is passed back down to intermediate nodes, updating their conditional probabilities.
4. The final step updates the conditional probabilities of the child nodes based on the belief passed down.


Image Example: Belief Propogation in Tree

No matter in what order the messages are sent out, an equilibrium needs to be eventually reached which should represent exactly the same state that can also be reached by textbook methods with much more computation.

Challenge of belief propagation

Given the example of diagnostic test, likelihood ratio measures how much more likely the positive test is in the diseased people than in the general population. It is given by
$$
P(T|D) / P(T)
$$
where $D$ denotes desease, and $T$ stands for test.

Bayes' theorem can then be rewritten as 
(Updated probability of $D$ ) $=P(D | T)=$ (likelihood ratio) $\times$ (prior probability of $D$ ).

Learn Before

Related