Sampling from Graphical Models

Sampling a family tree

Imagine simulating a family from a model. The model says how each person depends on their parents. You draw the grandparents first, then their children, then the grandchildren. Every draw then has the parents it needs, and nobody is drawn before the people they depend on.

A graphical model with arrows writes this idea in one formula. The arrows point from parent to child. The joint distribution of all the variables is the product of one local conditional per variable, each given that variable’s parents :

Each factor is a small table: the chance of one variable given its parents. A variable with no parents has a factor that is its own distribution, so every product starts from a factor that needs nothing else. The book’s sampling method rests on this formula.

The sequence of presses is an ordering of the people. An ordering is valid when every person comes after both of their parents. The book calls the procedure that draws variables in such an order ancestral sampling, and the next section gives the formal condition.

When a demo draws a person before a parent, the sample is spoiled. In the formula above, the factor for the child would need a value for the parent that does not exist yet.

Topological order

A topological ordering lists every variable once, so that each parent comes before its children. The book states the condition for a directed graph as follows. Here the variables are ordered by their index, so the condition is written with indices:

Ancestral sampling draws the variables in such an order. Each factor of Equation 16.1 is then read after the variables it depends on, and that is why the order must be topological. For some graphs several orders are valid, and ancestral sampling works with any of them.

Read the readout after each swap. A backward arrow means a child is listed before one of its parents. The demo lists those arrows, so the fix is visible.

Ancestral sampling, step by step

Take three binary variables in a chain: influences , and influences . Each variable copies the one before it with chance , and the first variable is 1 with chance . The chain factorizes as in Equation 16.2 of Section 16.2, which is the book’s relay race with its finishing times t₀, t₁, t₂ renamed , and . The binary copy rule in the next paragraph is added here for the demo and is not in the book:

Ancestral sampling draws from its distribution, then from its conditional given , then from its conditional given . The book writes the general procedure in the same order. This display is the book’s description, and the equation number is not printed there:

The sampler needs one uniform random number between 0 and 1 for each variable. A variable becomes 1 when is below its chance of being 1, and 0 otherwise. The demo below runs that rule and shows the random numbers it used.

The bars show the exact probability of each pattern, read from the factorization. The violet bars show how often the sampler produced each pattern. With enough draws the two sets of bars agree. In the readout, the exact chance of the pattern 1, 1, 1 is times squared, because copies with chance , and copies with the same chance.

When the shortcut breaks

Ancestral sampling draws the whole model from the top. A question often comes with evidence: some variables are observed, and the rest must be drawn given those values. The book notes that the shortcut works when the observed variables come earlier in the order than the variables still to be drawn. When they come later, the conditionals needed are posterior distributions. These are usually not explicitly stored in the model.

In the chain, comes last. Observing and drawing is therefore the hard direction. The book’s remark applies here: the conditional needed is the posterior, not the factor the model stores. Bayes’ rule gives it, and this derivation is added here and is not printed in the book:

The two bars show the answer. The ancestral draw of must use the second bar, not the first, once a value of is known. With three variables this is a short sum over the eight patterns. In a large model the sum has far more terms, and the book says that inferring these posteriors can be costly. In such models, ancestral sampling is no longer efficient.

Gibbs sampling around a loop

An undirected model has no arrows, so no variable comes first. Ancestral sampling cannot start. The book says that every variable interacts with every other variable and that there is no clear beginning point. For undirected models the book’s conceptually simplest approach is Gibbs sampling: visit each variable in turn, and draw it from its conditional given all the others. The separation properties of the graph mean that only the neighbours matter:

The loop below has four spins, one for each index . Each spin equals +1 or −1, and it is linked to its two neighbours on the ring. Lower energy means a more likely state. This energy is the standard one for such a loop, and it is added here and not printed in the book. Aligned neighbours lower the energy when is positive, and a positive favours +1 on every spin:

Because each spin takes only two values, its conditional has a closed form. This is also added here. The conditional depends only on the sum of the two neighbouring spins , which is the book’s neighbour rule written out for this loop:

The chain starts with every spin at −1. With a positive field, the typical state has most spins at +1, so the estimate starts low and climbs. The book states the core fact: after one pass through the variables, the state is still not a fair sample from the distribution. Repeated passes are needed, and the process converges only in the limit. The burn-in slider discards the early sweeps that still remember the starting state.

The readout gives the exact value by adding all 16 states, which is possible here because the loop is small. For a large model that sum has far too many terms to add up, which is why the book samples instead and treats undirected sampling as a multi-pass process.

The cost of a fair sample

Compare what each method spends on one sample. Ancestral sampling of a directed model draws each variable once in order, so one sample costs draws. Gibbs sampling makes one draw per variable in every sweep. A chain that needs sweeps before its state is useful therefore costs draws. The cost formula is added here and is not printed in the book:

The book does not give a formula for the number of sweeps and states that it is hard to decide when a chain is accurate enough. The demo below treats as a setting you choose, so you can see how fast the cost grows with the number of variables.

On a logarithmic scale, the two lines have the same shape and differ by a fixed vertical gap of the logarithm of . Doubling the sweeps doubles the Gibbs cost, while ancestral sampling pays only for the variables. This matches the book’s remark that ancestral sampling is generally very fast and convenient, provided each conditional is easy to sample.

• A directed model over variables can be sampled by drawing each variable after its parents, in any topological order. Each draw uses its local conditional from Equation 16.1.
• Ancestral sampling breaks when observed variables come before the variables to be drawn. The sampler then needs posterior distributions, which are usually not stored and can be costly to infer.
• Undirected models have no first variable. Gibbs sampling draws each variable from its conditional given its neighbours, and repeated sweeps are needed before the state is a fair sample.
• Each Gibbs sweep costs draws, so a kept sample of a Gibbs chain costs about times as much as an ancestral sample.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 16.3 (pages 580–581), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.