Converting Graphs · Factor Graphs · Sampling · Advantages

§16.2.6 Converting between directed and undirected graphs

No probabilistic model is inherently directed or undirected — a model is just more easily described one way or the other. We commonly call RBMs undirected and sparse coding directed, but either language can represent any distribution: in the worst case a complete graph does it (a directed complete graph orders the variables and gives each all its predecessors as parents; an undirected complete graph is one clique over everything). Such graphs are useless precisely because they imply no independences. The whole game is to pick the graph that implies as many true independences as possible — and directed and undirected graphs can each express independences the other cannot.

A directed model can hold an immorality — two unconnected parents of a shared child — which no undirected graph captures. To go directed → undirected we moralize : “marry” the co-parents with an edge, then drop the arrows. An undirected model can hold a chordless loop of length > 3, which no directed model captures; to go undirected → directed we triangulate (add chords) and orient the edges without creating a cycle. Step through both:

Converting between graph languages (figs 16.11–16.12). Steps 1–3 moralize a directed immorality; steps 4–6 triangulate and orient an undirected 4-loop.

11 · A directed immorality

a and b are both parents of c, with no edge between them. The V-structure encodes a ⊥ b (they are independent a priori) — an independence no undirected graph can reproduce exactly.

step 1 / 6

§16.2.7 Factor graphs

Standard undirected notation is ambiguous: a clique of three connected nodes might carry one factor over all three, or three pairwise factors — the graph looks identical, yet the two cost very differently to represent and compute. A factor graph removes the ambiguity by drawing the factors explicitly. It is bipartite: round nodes are variables, square nodes are factors $\phi$ , and an edge joins a variable to a factor iff that variable is one of the factor’s arguments (never variable–variable or factor–factor):

Fig 16.13 — one undirected triangle (left), two factor graphs that both realize it. Center: a single factor f₁ over all three variables. Right: three pairwise factors f₁, f₂, f₃ — asymptotically cheaper, though the plain undirected graph cannot tell the two apart.

§16.3 Sampling from graphical models

Directed models support a simple, fast procedure: ancestral sampling .

Ancestral sampling (directed models)

1Sort the variables into a topological order $x_1, \ldots, x_n$ ⓘ
2for $i = 1$ to $n$ :
3sample $x_i \sim P(x_i \mid Pa_{\mathcal{G}}(x_i))$ ⓘ
4return $x_1, \ldots, x_n$ ⓘ

Ancestral sampling is fast and convenient, but it has two limits: it works only for directed models, and it cannot easily draw conditional samples unless the conditioning variables happen to come first in the ordering (otherwise you would need the model’s posterior, which is usually not available). Undirected models have no such parents-first order, so we fall back on Gibbs sampling : repeatedly resample each variable given its neighbors. Crucially, one sweep is not a fair sample — only after many sweeps does the chain approach $p(\boldsymbol{x})$ , and asymptotically at that. Compare the two:

Ancestral vs Gibbs sampling. Ancestral fills the directed chain once, parents-first, and is immediately a fair sample. Gibbs sweeps the undirected loop over and over; the "approach to p(x)" meter climbs but never quite completes — convergence is only asymptotic (chapter 17).

sampled 0 / 3 nodes

Each node is drawn from p(xᵢ | parents) — and its parents are already sampled, so a single sweep yields an exactsample. Fast and convenient, but works only for directed models.

§16.4 Advantages of structured modeling

Why structure pays. Click a row for the detail.
	Benefit	Where it comes from
Cheaper representation	fewer parameters to store	omitted edges = interactions we choose not to model
Cheaper learning	less data, less compute to fit	small factors ⇒ few parameters ⇒ statistically efficient
Cheaper inference	faster marginals/conditionals	the graph localizes the computation
Faster sampling (directed)	ancestral sampling in one pass	topological order + easy local conditionals
Separates knowledge from inference	modular design & debugging	representation of knowledge ⟂ learning/inference

Dotted-underlined cells have explanations — click one.

The mechanism behind every row is the same: graphical models convey information by leaving edges out. Every absent edge is a declared assumption that a direct interaction is unnecessary — and that is what buys the cheaper representation, learning, inference, and (for directed models) sampling. Next: how deep learning captures dependencies with latent variables, the intractability of inference, and the RBM.

Check yourself — conversions, factor graphs & sampling

1.To convert a directed model with an immorality (a → c ← b, no a–b edge) into an undirected model, what must you do, and what is lost?

2.Why can't the undirected 4-loop a–b–c–d–a be converted to a directed model as-is?

3.What ambiguity does a factor graph resolve?

4.Predict the outcome — in SamplingLab you run ancestral sampling on the directed chain, then switch to Gibbs on the undirected loop and click 'sweep' once. What does each show?

5.What is the single underlying mechanism behind ALL the advantages of structured modeling?

5 questions