Directed Models · Undirected Models · The Partition Function

§16.2.1 Directed models — one arrow, one conditional

A directed graphical model — also called a belief network or Bayesian network (Pearl, 1985) — uses directed edges. An arrow from $a$ to $b$ means we define $b$ ‘s distribution conditionally on $a$ : $a$ appears on the right of the conditioning bar. The relay race is the natural example — Bob’s time is defined given Alice’s, Carol’s given Bob’s:

Fig 16.2 — the relay race as a directed model. Click a node to see every factor it appears in: its own conditional, plus the conditionals it parents.

p(t_0, t_1, t_2) =

p(t_0)

p(t_1 \mid t_0)

p(t_2 \mid t_1)

click a node to see which factors mention it

Formally, a directed model is a directed acyclic graph $\mathcal{G}$ plus one local conditional per node, and the joint is their product:

The directed factorization (eq 16.1)

p(\boldsymbol{x}) = \prod_i p\!\left(\mathrm{x}_i \mid Pa_{\mathcal{G}}(\mathrm{x}_i)\right)

$p(\mathrm{x}_i \mid Pa_{\mathcal{G}}(\mathrm{x}_i))$	the local conditional of node i given its PARENTS — a small table (or formula) attached to that node	one factor per node
$Pa_{\mathcal{G}}(\mathrm{x}_i)$	the parents of xᵢ: the nodes with an arrow INTO xᵢ. Few parents → few parameters	subset of nodes
$\prod_i$	the joint is exactly the product of these local conditionals — nothing else to specify	over all n nodes

For the relay race this reads $p(t_0, t_1, t_2) = p(t_0)\,p(t_1 \mid t_0)\,p(t_2 \mid t_1)$ — no $t_0$ term inside $t_2$ ‘s factor, because Carol depends on Alice only through Bob.

The cost win, formally. Discretize each time into 100 buckets. The full joint table needs $100^3 - 1 = 999{,}999$ values; the three conditional tables need $99 + 9900 + 9900 = 19{,}899$ — a 50× saving. In general a full table is $O(k^n)$ while a directed model is $O(k^m)$ , where $m$ is the most variables in any single conditional. As long as $m \ll n$ the savings are dramatic. (Slide it yourself in the ParamBlowupLab of §16.1.) Restricting the graph further — e.g. to a tree — additionally makes marginals and conditionals efficient to compute.

The graph encodes independence — nothing else

The graph says only which variables are conditionally independent. Other simplifying assumptions live inside the conditional’s definition. Suppose Bob’s personal running time is independent of Alice — then $t_1$ is just $t_0$ plus Bob’s own time, an $O(k)$ formula instead of an $O(k^2)$ table. Yet we still need the $t_0 \to t_1$ arrow, because $t_1$ is Bob’s absolute finish time, which does depend on when Alice handed off. The directed syntax constrains only which variables a conditional may take as arguments — never how you define it.

§16.2.2 Undirected models — affinities, not conditionals

When interactions have no natural direction, use an undirected model , also called a Markov random field (MRF) or Markov network (Kindermann, 1980). Its edges carry no arrows and no conditional distributions. Consider three people’s health: you ( $h_y$ ), your roommate ( $h_r$ ), your coworker ( $h_c$ ). You can infect either of them and be infected by either — symmetric, so no arrows. But your roommate and coworker never meet, so there is no direct edge between them; they influence each other only through you:

Fig 16.3 — the cold-spreading undirected model. Roommate and coworker connect only through you; click a node to see which clique factors involve it.

\tilde{p}(h_r, h_y, h_c) =

\phi_{r,y}(h_r, h_y)

\phi_{y,c}(h_y, h_c)

click a node to see which factors mention it

For each clique (a set of mutually connected nodes) a non-negative factor $\phi(C)$ — a clique potential — scores how much its variables “like” being in each joint state. Their product is an unnormalized distribution:

The undirected factorization (eq 16.3)

\tilde{p}(\boldsymbol{x}) = \prod_{C \in \mathcal{G}} \phi(C)

$\phi(C)$	the clique potential: a NON-NEGATIVE affinity for each joint state of the clique C — higher = more likely. Not a probability	table over clique states
$\tilde{p}(\boldsymbol{x})$	the UNNORMALIZED probability (note the tilde) — a product of affinities; efficient to evaluate when every clique is small	scalar ≥ 0
$\prod_{C \in \mathcal{G}}$	product over cliques. Unlike a Bayesian net, nothing guarantees this product already sums to 1 — that is what Z fixes	over all cliques

The $\phi$ for the you-and-coworker clique might look like this (state $1$ = healthy, $0$ = sick):

A clique potential φ(h_y, h_c) — affinities, not probabilities. Click a cell for why that state is more or less likely.
	joint state	φ (affinity)
both healthy (h_y=1, h_c=1)	h_y = 1, h_c = 1	10
both sick (h_y=0, h_c=0)	h_y = 0, h_c = 0	2
only you sick (h_y=0, h_c=1)	h_y = 0, h_c = 1	1
only coworker sick (h_y=1, h_c=0)	h_y = 1, h_c = 0	1

Dotted-underlined cells have explanations — click one.

Reading the factorization off a graph is just a matter of listing its cliques. Click through the classic six-node example — every node lights up the factors it belongs to:

Fig 16.4 — reading factorization from an undirected graph. The pairwise cliques give p(a,…,f) = (1/Z)·φ_{a,b}φ_{b,c}φ_{a,d}φ_{b,e}φ_{e,f}.

\tfrac{1}{Z}

\phi_{a,b}

\phi_{b,c}

\phi_{a,d}

\phi_{b,e}

\phi_{e,f}

click a node to see which factors mention it

§16.2.3 The partition function

The product of clique potentials is non-negative but need not sum to $1$ . To get a valid distribution we divide by the partition function $Z$ :

Normalizing an undirected model (eqs 16.4–16.5)

p(\boldsymbol{x}) = \frac{1}{Z}\,\tilde{p}(\boldsymbol{x}), \qquad Z = \int \tilde{p}(\boldsymbol{x})\, d\boldsymbol{x}

$Z$	the partition function: the sum (discrete) or integral (continuous) of p̃ over EVERY joint state — the constant that makes p integrate to 1	scalar
$\frac{1}{Z}\tilde{p}(\boldsymbol{x})$	the normalized, valid distribution — a Gibbs distribution	sums/integrates to 1
$\int \cdots d\boldsymbol{x}$	sum over all kⁿ discrete states, or integral over the continuous domain — usually INTRACTABLE, which is why chapter 18 exists	over the whole domain

Normalizing a product of clique potentials this way yields what is called a Gibbs distribution . Because $Z$ sums over every joint assignment of $\boldsymbol{x}$ , it is generally intractable in deep learning — confronting it is the entire subject of chapter 18.

Worked example — when Z does not even exist

Take a single scalar $x \in \mathbb{R}$ with clique potential $\phi(x) = x^2$ . Then $Z = \int_{-\infty}^{\infty} x^2\, dx = \infty$ : the integral diverges, so no probability distribution corresponds to this $\phi$ . Choosing $\phi(x;\beta) = \exp(-\beta x^2)$ instead, $Z$ is finite only for $\beta > 0$ (giving a Gaussian); every other $\beta$ makes $\phi$ impossible to normalize. With undirected models you are not guaranteed a valid distribution for free — you must check that $Z$ exists.

This is the deep difference from directed models, which are built out of probability distributions from the start. Undirected models are defined loosely by $\phi$ functions and normalized afterward, so the domain of the variables dramatically changes what a given set of $\phi$ ‘s even means. Take the single factor $\phi(x_i) = \exp(b_i x_i)$ and switch its domain:

One clique potential φ(xᵢ)=exp(bᵢxᵢ), three domains. Over ℝ the partition function diverges (no distribution); over {0,1}ⁿ it factorizes into independent sigmoids; over one-hot basis vectors it becomes a softmax where the biases compete. Same φ — the domain decides everything.

Each xᵢ is independent: p(x) factorizes into n separate Bernoullis, p(xᵢ=1) = σ(bᵢ). Raising one bias moves only its own bar.

φ(xᵢ) = exp(bᵢ·xᵢ)

b₁ = 0.80b₂ = 0.20b₃ = -0.50

One set of factors, three domains, three completely different objects — the lesson of the partition function: with undirected models you must know the variables' domain before a set of φ's even means anything.

Directed vs undirected, in one line

A directed model is a product of conditional probabilities — valid by construction, normalized locally. An undirected model is a product of affinities — valid only after the global division by $Z$ , which may be intractable or nonexistent. Directed models make sampling easy; undirected models make it easy to express symmetric, cyclic interactions. Next we meet the most convenient way to guarantee $\tilde{p} > 0$ — energy-based models — and how to read (in)dependence off a graph.

Check yourself — directed, undirected & the partition function

1.In a directed model, what does the arrow a → b assert?

2.A full joint table over n discrete variables with k values costs O(kⁿ). What does a directed model cost, and when does it help?

3.How does a clique potential φ(C) in an undirected model differ from a conditional probability in a directed model?

4.Why can computing the partition function Z be impossible even in principle?

5.Predict the outcome — in PartitionDomainLab you keep φ(xᵢ)=exp(bᵢxᵢ) fixed and switch the domain from {0,1}ⁿ to the one-hot basis. What changes?

5 questions