Consider two fundamentally different ways to describe a relationship between variables:

Scenario 1 — Causation: "Smoking causes lung cancer." There's a clear direction here: smoking comes first (causally), and lung cancer may follow as an effect. If we wanted to reason about this relationship, we'd naturally think in terms of "if you smoke, what's the probability of cancer?"—a conditional probability flowing from cause to effect.

Scenario 2 — Correlation: "Neighboring pixels in an image tend to have similar colors." Here, there's no direction. Pixels don't cause each other—they simply co-occur with similar values. The relationship is symmetric: knowing pixel A tells you about pixel B, and knowing pixel B tells you about pixel A.

These two scenarios motivate the two major families of probabilistic graphical models:

• Directed graphical models (Bayesian Networks) for asymmetric, causal, or generative relationships
• Undirected graphical models (Markov Random Fields) for symmetric, correlational relationships

Understanding when and how to use each is essential for modeling real-world phenomena correctly.

A Bayesian Network (also called a Belief Network, Bayes Net, or Directed Graphical Model) represents a joint probability distribution using a directed acyclic graph (DAG).

Formal Definition:

A Bayesian Network consists of:

1. A directed acyclic graph $G = (V, E)$ where:

   • $V = {X_1, X_2, \ldots, X_n}$ are random variables (nodes)
   • $E$ are directed edges (arrows) representing direct dependencies
   • The graph has no directed cycles (you cannot follow arrows and return to the starting node)

2. A set of conditional probability distributions (CPDs) ${P(X_i | \text{Pa}(X_i))}$ where:

   • $\text{Pa}(X_i)$ denotes the parents of node $X_i$ — nodes with edges pointing to $X_i$
   • Each $P(X_i | \text{Pa}(X_i))$ specifies the probability of $X_i$ given its parents

The Chain Rule Factorization:

The joint distribution factorizes as:

$$P(X_1, X_2, \ldots, X_n) = \prod_{i=1}^{n} P(X_i | \text{Pa}(X_i))$$

Each variable is conditionally distributed given only its parents. This is the local Markov property of Bayesian networks.

Key properties of Bayesian Networks:

1. Acyclicity requirement: The graph must be a DAG. Cycles would create circular dependencies where a variable depends on itself—mathematically undefined.

2. Automatic normalization: Since each factor is a conditional probability distribution, the product is automatically a valid probability distribution (sums to 1). No separate normalization constant needed.

3. Causal interpretation: Arrows often (but not always) represent causal influence. If we draw an arrow from A to B, we're asserting that A directly influences B's probability.

4. Generative semantics: We can sample from the joint by following topological order—sample parents before children.

5. Compact CPDs: Each conditional probability table has at most $O(k^{|\text{Pa}(X_i)|})$ parameters where $k$ is the number of values per variable. Keeping parent sets small yields compact models.

A Markov Random Field (MRF), also called a Markov Network or Undirected Graphical Model, represents a joint distribution using an undirected graph.

Formal Definition:

A Markov Random Field consists of:

1. An undirected graph $G = (V, E)$ where:

   • $V = {X_1, X_2, \ldots, X_n}$ are random variables (nodes)
   • $E$ are undirected edges representing direct correlations

2. A set of potential functions ${\phi_c(X_c)}$ defined over cliques of the graph:

   • A clique is a fully-connected subset of nodes (every pair is connected by an edge)
   • A maximal clique is a clique that cannot be extended by adding another node
   • $\phi_c : \text{Val}(X_c) \to \mathbb{R}^+$ maps configurations to non-negative real values

The Gibbs Distribution Factorization:

$$P(X_1, X_2, \ldots, X_n) = \frac{1}{Z} \prod_{c \in \mathcal{C}} \phi_c(X_c)$$

Where:

• $\mathcal{C}$ is the set of cliques
• $\phi_c(X_c)$ are potential functions (not probabilities!)
• $Z = \sum_{X} \prod_{c \in \mathcal{C}} \phi_c(X_c)$ is the partition function ensuring normalization

Key properties of Markov Random Fields:

1. Symmetric relationships: Edges have no direction, representing mutual influence. If A and B are neighbors, A influences B and B influences A equally.

2. Potential functions, not probabilities: The factors $\phi_c$ are not conditional probabilities—they're just non-negative compatibility scores. They don't need to sum to 1.

3. Partition function required: Because potentials aren't normalized, we need the partition function $Z$ to convert the product to a proper probability. Computing $Z$ is often the hardest part.

4. Energy-based interpretation: Defining $E(X) = -\sum_c \log \phi_c(X_c)$, we get the Boltzmann distribution: $P(X) = \frac{1}{Z} e^{-E(X)}$. Low energy = high probability.

5. Clique decomposition: The Hammersley-Clifford theorem (covered in the next module) proves that any positive distribution satisfying the Markov properties of a graph can be factorized this way.

Let's directly compare how the two model families factorize the joint distribution:

Bayesian Network (Directed):

$$P(X_1, \ldots, X_n) = \prod_{i=1}^{n} P(X_i | \text{Pa}(X_i))$$

• Each factor is a conditional probability distribution
• Factors are associated with nodes (one per node)
• Parents are the conditioning set
• Product is automatically normalized

Markov Random Field (Undirected):

$$P(X_1, \ldots, X_n) = \frac{1}{Z} \prod_{c \in \mathcal{C}} \phi_c(X_c)$$

• Each factor is an unnormalized potential function
• Factors are associated with cliques (fully-connected subsets)
• Requires partition function $Z$ for normalization
• More flexibility in factor design, but harder to normalize

A concrete example:

Consider three variables: A, B, C with A connected to B and B connected to C.

As a Bayesian Network (A → B → C): $$P(A, B, C) = P(A) \cdot P(B|A) \cdot P(C|B)$$

• 3 factors: $P(A)$, $P(B|A)$, $P(C|B)$
• Interpretation: A causes B, B causes C
• Implies: $A \perp!!!\perp C | B$ (A and C are independent given B)

As a Markov Random Field (A — B — C): $$P(A, B, C) = \frac{1}{Z} \phi_{AB}(A, B) \cdot \phi_{BC}(B, C)$$

• 2 clique factors: $\phi_{AB}$, $\phi_{BC}$
• Interpretation: A and B are correlated, B and C are correlated
• Also implies: $A \perp!!!\perp C | B$

Both encode the same conditional independence, but with different semantics. The BN has a causal/temporal ordering; the MRF is symmetric.

A crucial question: Can every distribution representable by one family be represented by the other? The answer is nuanced.

Definition: I-map (Independence Map)

A graph $G$ is an I-map for a distribution $P$ if the conditional independencies implied by $G$ are a subset of the conditional independencies that hold in $P$. In other words, $G$ doesn't assert any independence that $P$ violates.

Key results:

1. Some independencies can only be expressed in directed models (Example: "Explaining away" pattern)

2. Some independencies can only be expressed in undirected models (Example: Four-way symmetric constraint)

3. Neither family is strictly more powerful than the other

Let's examine specific cases where each family has an advantage:

Case 1: V-Structure (Explaining Away) — Only Directed Models

Consider two independent causes that share a common effect:

    A       B
     \     /
      ↓   ↓
        C

• A: Battery dead
• B: Fuel empty
• C: Car won't start

In this structure:

• Marginally: $A \perp!!!\perp B$ (battery and fuel status are independent)
• Given C: $A ot\perp!!!\perp B | C$ (if car won't start and battery is fine, fuel is more likely empty)

This is the famous explaining away phenomenon. Learning that the car won't start makes the two causes dependent—if one is ruled out, the other becomes more likely.

Why undirected graphs can't capture this:

To express $A \perp!!!\perp B$ (marginal independence), an undirected graph would have no edge between A and B. But without an edge, A and B remain independent even given C. Undirected graphs cannot express: "independent marginally, dependent given a common descendant."

Case 2: Diamond Structure — Only Undirected Models

Consider four variables in a cycle:

    A — B
    |   |
    C — D

Independencies we want:

• $A \perp!!!\perp D | {B, C}$
• $B \perp!!!\perp C | {A, D}$

An undirected graph with exactly these edges captures these independencies via graph separation.

Why directed graphs struggle:

To make this a DAG, we must add directions. Any acyclic orientation forces additional conditional independencies (through d-separation rules we'll cover later) that may not hold in the true distribution. Alternatively, we'd need to add edges to be a valid I-map, losing the precise independence structure.

The bottom line:

Neither family dominates. The choice depends on:

• Which independence structure matches your domain
• Whether causal/generative semantics are appropriate
• Computational considerations (e.g., partition function)

Choosing between directed and undirected models is one of the most important modeling decisions. Here's a principled framework for making this choice:

Use Bayesian Networks when:

Classic Bayesian Network applications:

• Medical diagnosis (diseases cause symptoms)
• Fault diagnosis (root causes produce observable errors)
• Genetic inheritance (parent genes influence child genes)
• Speech recognition (HMMs: hidden states produce observations)
• Document modeling (LDA: topics generate words)

Classic MRF applications:

• Image segmentation (neighboring pixels tend to have same label)
• Stereo vision (disparity should be smooth across space)
• Image denoising (recover clean image from noisy observations)
• Statistical physics (Ising model for magnetic systems)
• Sequence labeling with CRFs (POS tagging, NER)

The choice between directed and undirected models has significant computational implications:

Bayesian Networks — Computational Advantages:

1. No partition function: Factors are CPDs that automatically normalize. No need to compute the intractable sum $Z$.

2. Easy sampling: To generate a sample:

   • Order nodes topologically
   • For each node, sample from $P(X_i | \text{Pa}(X_i))$ using already-sampled parent values
   • This is ancestral sampling — simple and exact.

3. Local likelihood: The likelihood of data decomposes: $\log P(D) = \sum_i \log P(X_i | \text{Pa}(X_i))$. Each term can be optimized separately.

4. Parameter estimation: Maximum likelihood estimates for CPDs are just empirical conditional frequencies—easy to compute.

Markov Random Fields — Computational Challenges:

1. Partition function: Computing $Z = \sum_X \prod_c \phi_c(X_c)$ is #P-complete in general. For $n$ binary variables, it's $O(2^n)$.

2. Difficult sampling: No natural ordering for ancestral sampling. Must use MCMC (Gibbs sampling, Metropolis-Hastings).

3. Coupled likelihood: The log-likelihood $\log P(X) = \sum_c \log \phi_c(X_c) - \log Z$. The $\log Z$ term couples all parameters—can't optimize locally.

4. Gradient estimation: The gradient of log-likelihood involves expectations under the model: $ abla \log P(D) = E_{data}[ abla \log \phi] - E_{model}[ abla \log \phi]$. The second term requires sampling from the model.

When MRFs are still worth it:

• Discriminative models (CRFs): Condition on observed features, so $Z$ only sums over labels, not features. Much more tractable.
• Loopy belief propagation: Approximate inference that works well in practice even without theoretical guarantees.
• Variational methods: Convert intractable $Z$ to optimization problem.
• Special structure: Trees and low-treewidth graphs allow exact inference.

In practice, the directed/undirected dichotomy is often too restrictive. Several representations extend beyond this basic division:

Factor Graphs:

A factor graph is a bipartite graph with two types of nodes:

• Variable nodes (circles): Represent random variables
• Factor nodes (squares): Represent factors/potentials

Edges connect factor nodes to the variables they depend on.

$$P(X) = \frac{1}{Z} \prod_{a} f_a(X_{\mathcal{N}(a)})$$

Where $\mathcal{N}(a)$ denotes the neighbors of factor $a$.

Advantages of factor graphs:

• Unify directed and undirected representations
• Make factor structure explicit (helpful for inference algorithms)
• Can represent higher-order factors directly
• Foundation for modern probabilistic programming languages

Chain Graphs:

A chain graph allows both directed and undirected edges, with the constraint that you can partition nodes into ordered 'chain components' where:

• Edges between components are directed
• Edges within components are undirected

This models situations like:

• Manufacturer → Retailer1 — Retailer2 → Consumer (Retailers are peers who influence each other, but there's a supply chain direction)

Conditional Random Fields (CRFs):

CRFs are undirected models conditioned on observations:

$$P(Y | X) = \frac{1}{Z(X)} \prod_{c} \phi_c(Y_c, X)$$

Note that:

• The partition function $Z(X)$ depends on the input $X$
• We don't model $P(X)$ at all—just the conditional $P(Y|X)$
• This is discriminative, not generative

CRFs combine the flexibility of undirected models with the computational benefits of conditioning.

Hybrid Approaches:

Modern systems often combine:

• Neural networks to learn feature representations
• Graphical model structure to capture dependencies
• Examples: Neural CRFs, structured prediction networks, graph neural networks

Let's consolidate the essential insights from this deep dive into directed and undirected graphical models:

What's next:

Now that we understand the two major families of graphical models, we need to formalize the mathematical foundation that makes them work: conditional independence. The next page will give you a rigorous understanding of what conditional independence means, how it enables factorization, and how to read independence properties directly from graph structure.