Directed Acyclic Graph (DAG)
Definition
A graph in which edges have a direction (from parent to child node) and no path can return to a node it has already visited. The acyclic constraint ensures the conditional independence structure is well-defined and that probability inference algorithms can terminate.
- Edge property
- Directed, parent to child
- Structural rule
- No cycles
- Purpose
- Well-defined conditional independence
- Field
- Bayesian networks for evidence evaluation
Common questions
Why does the acyclic constraint matter for evidence evaluation?+
It ensures probability updates can propagate through the network without circular reasoning, so inference algorithms are guaranteed to converge to a well-defined posterior instead of looping indefinitely between mutually dependent nodes.
What happens if an analyst builds a Bayesian network with a cycle by mistake?+
Standard inference algorithms either fail to run or produce undefined results, because a cycle means a node's probability would depend on itself through the loop, so the network has to be restructured before it can be used for calculation.
Related terms
- Belief Propagation
- An algorithm for computing marginal and posterior probabilities in a Bayesian network by passing messages between neighbouring nodes. Exact on tree-structured networks;...
- 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...
- 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...