§16.0–16.2Structured Probabilistic Models · The Challenge of Unstructured Modeling

§16.0 A language for distributions over many variables

Part III’s research topics — RBMs, deep belief nets, deep Boltzmann machines, variational autoencoders — are all probabilistic models over thousands of variables. Before we can build them we need a way to write them down. That language is the structured probabilistic model structured probabilistic model (Graphical model) a factorization of a joint distribution described by a graph: nodes = RVs, edges = direct interaction. defined in ch. 3 — open in glossary , also called a graphical model graphical model Synonym for a structured probabilistic model: a distribution described by a graph whose nodes are random variables and whose edges are direct interactions (missing edges = independence assumptions). defined in ch. 16 — open in glossary : a probability distribution described by a graph (graph-theory sense — vertices joined by edges) in which

• each node is a random variable, and
• each edge is a direct interaction between two variables.

We met this idea briefly in §3.14; this chapter is self-contained and develops it in full. The payoff is enormous and worth stating up front: by declaring which variables interact directly, the graph lets us model a distribution with far fewer parameters, estimate it from less data, and store, query, and sample it far more cheaply. The deep-learning community uses these models in its own distinctive way — that is the subject of §16.7 — but the machinery is shared with the wider graphical-models field.

§16.1 Why the naive table is hopeless

The goal of deep learning is to scale machine learning up to AI: to understand high-dimensional data with rich structure — natural images, speech waveforms, documents. A classifier takes such an input and collapses it to a single label, discarding most of the information and freely ignoring large parts of the input (the background of a photo, say). Many other probabilistic tasks are more demanding: they need a complete model of the entire input, with no option to ignore any of it.

Figure 16.1 in the book shows the sampling task on natural images: real CIFAR-10 tiles on top, and below them samples from a structured model — each placed at the grid position of its nearest training image, so you can see the model is synthesizing new pictures rather than memorizing:

The exponential wall

Suppose we model only binary variables — the simplest possible case — and try to store the joint as a lookup table with one probability per outcome. For a small 32×32 pixel RGB image that is $2^{3072}$ possible images: a number over $10^{800}$ times larger than the estimated number of atoms in the universe. In general, for $n$ discrete variables taking $k$ values each, the table needs

$k^{n} \text{ parameters,}$

and this is infeasible on four separate counts:

The deep problem is that the table explicitly models every possible interaction among every subset of variables. Real distributions are far simpler than that: most variables influence each other only indirectly.

The relay race

Three runners — Alice, Bob, Carol — run a relay in that order, each handing off a baton. Model each finishing time as a continuous random variable.

• Alice runs first, so her time $t_0$ depends on no one.
• Bob can’t start until Alice hands off, so $t_1$ depends directly on $t_0$.
• Carol can’t start until Bob hands off, so $t_2$ depends directly on $t_1$.

Does Carol’s time depend on Alice’s? Only indirectly — through Bob. If we already know Bob’s finishing time, learning Alice’s tells us nothing more about Carol’s. So the whole race needs just two direct interactions, Alice→Bob and Bob→Carol; the indirect Alice→Carol link can be left out of the model entirely.

How much does modeling only direct interactions save? Discretize each runner’s time into 100 buckets. The full joint table over $(t_0, t_1, t_2)$ needs $100^3 - 1 = 999{,}999$ values. But storing one small table per direct interaction — 99 values for $t_0$, then $99 \times 100 = 9900$ each for $t_1\mid t_0$ and $t_2\mid t_1$ — comes to just 19,899: a saving of more than 50×. Explore how that gap grows with the number of variables:

§16.2 Two graph languages

Structured probabilistic models come in two broad families, distinguished by whether the edges carry arrows:

Both are just ways of saying which variables interact directly; the direct interactions imply all the indirect ones, and only the direct ones are written down. Next we make each precise — starting with directed models, undirected models, and the partition function.