Content
Summary
Directed graphical models (DGMs) factorize joint distributions into conditional probabilities to reduce parameter complexity from to . Key examples include Naive Bayes, Hidden Markov Models, and medical diagnosis networks, each leveraging specific structural assumptions like conditional independence or tree topologies.
Intuition
DGMs provide a compact representation of joint probability distributions by encoding conditional independence assumptions. This structure significantly reduces the number of parameters required compared to unconstrained models. For instance, while a general model requires parameters, a DGM scales as if each node has parents. This efficiency allows for practical modeling of complex systems like medical diagnoses or sequence data, where direct estimation of full joint distributions is infeasible.
Key equations
General factorization of joint distribution over a DAG G, where x_{pa(t)} are the parents of node t.
Joint distribution for a Naive Bayes classifier with D features, assuming conditional independence of features given class y.
Joint distribution for a second-order Markov chain of length T.
Joint distribution for a bipartite medical diagnosis network (like QMR) with hidden diseases h and visible symptoms v.
Conditional probability for a symptom v_t given its parent diseases, modeled using logistic regression in a sigmoid belief net.
Derivation
- Start with the general joint distribution p(x_{1:V}).
- Apply the chain rule of probability to factorize the joint distribution.
- Introduce the Directed Acyclic Graph (DAG) structure G to encode conditional independence assumptions.
- Simplify the factorization to p(x_t | x_{pa(t)}), where x_{pa(t)} are the parents of node t.
- Verify that the number of parameters scales as O(V K^F) rather than O(K^V), ensuring efficiency.
Worked example
Consider a medical diagnosis network (QMR) with a symptom v_t having 10 disease parents. If we use a full Conditional Probability Table (CPT), how many parameters are needed? Compare this to using a noisy-OR model.
- Identify that a full CPT requires a parameter for every combination of parent states.
- Assume binary diseases: 2^10 = 1024 combinations.
- A full CPT would require approximately 1024 parameters for this single symptom.
- In contrast, a noisy-OR model uses individual parent parameters and a leak node.
- This reduces the parameter count to roughly 10 (one per parent) plus the leak parameter.
- Conclusion: Noisy-OR is significantly more parameter-efficient for high fan-in nodes.
Answer Using a full CPT requires ~1024 parameters, while a noisy-OR model requires only ~11 parameters, demonstrating the efficiency gain for high fan-in nodes.
Common mistakes
- Assuming the factorization p(x|G) holds without verifying that the conditional independence assumptions encoded in the DAG G are correct.
- Using full conditional probability tables (CPTs) for symptoms in medical diagnosis networks with many disease parents, which requires too many parameters.
- Believing that higher-order Markov models are always better for capturing long-range correlations, ignoring the exponential blowup in parameters.