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

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

In the context of Bayes' theorem and diagnostic testing, the likelihood ratio measures how much more likely a positive test is in diseased individuals than in the general population. It is given by the formula $$P(T|D) / P(T)$$, where $$D$$ denotes the disease and $$T$$ stands for the test. Using this ratio, Bayes' theorem can be rewritten as: $$\text{Updated probability of } D = P(D|T) = \text{Likelihood ratio} \times \text{Prior probability of } D$$.

Learn Before

Related