Belief Propagation
Definition
An algorithm for computing marginal and posterior probabilities in a Bayesian network by passing messages between neighbouring nodes. Exact on tree-structured networks; approximate methods such as loopy belief propagation or Monte Carlo sampling are needed for networks with cycles.
- Purpose
- Computes marginal and posterior probabilities in a Bayesian network
- Mechanism
- Message passing between neighbouring nodes
- Exact on
- Tree-structured networks
- Approximate variants
- Loopy belief propagation, Monte Carlo sampling
Common questions
Why does belief propagation stop being exact once a network has cycles?+
Messages can circulate repeatedly around a loop and reinforce each other, so the same evidence gets counted more than once. On a tree there is only one path between any two nodes, which prevents that double-counting and keeps the computed probabilities exact.
Why use belief propagation for forensic evidence networks instead of computing probabilities directly?+
A Bayesian network combining several dependent pieces of evidence can have a probability table too large to enumerate directly. Belief propagation updates beliefs locally through the network's structure, making it computationally practical to combine many evidence nodes that a full joint calculation could not handle.
Related terms
- Conditional Probability Table (CPT)
- A table that specifies the probability distribution of a node given every combination of states of its parent nodes. Every non-root node...
- D-Separation
- A graphical criterion that determines whether two sets of nodes in a Bayesian network are conditionally independent given a third set. If...
- Directed Acyclic Graph (DAG)
- A graph in which edges have a direction (from parent to child node) and no path can return to a node it...
- Mixture Likelihood Ratio
- The ratio of the probability of observing a mixed DNA profile if the person of interest is a contributor to the probability...
- Sensitivity Analysis
- A technique for assessing how much the posterior probabilities in a Bayesian network change when the values in the conditional probability tables...