Advantages of Structured Modeling

Leaving edges out

A model over binary variables stored as a full table needs free numbers, one for each pattern of values except one, since the probabilities must add to 1. Every number in that table is a parameter that has to be stored and, from data, estimated. The book’s main mechanism for saving them is simple: leave interactions out. A graph gives a rule for which variables depend on which. Every missing edge is a claim that two variables do not interact directly.

Here is how to count a graph. Each variable depends on at most earlier variables, its parents . A binary variable with parents needs free numbers, one for each setting of its parents. Adding the counts gives the model’s total. This formula is added here as an explanation and is not printed in the book:

Now predict the count for the simplest graph with arrows: a chain, where each variable has exactly one parent, the one before it. Take ten binary variables.

The chart is on a logarithmic scale, so the full table is a steep line. The graph line grows much more slowly while stays small. With = 1 the graph count is , which is 19 for ten variables, the same as the prediction. Each extra variable adds two numbers, while the full table roughly doubles. The count depends on which edges are left out, not only on how many variables there are.

The demo counts the graph by giving each variable as many parents as allowed, taken from the variables before it. When is or more, every earlier variable is a parent, and the graph is the full table again.

Cheaper representation and inference

The book says that structured models cut the cost of representing a distribution, and also of learning and inference. Representation is the count of free numbers from the last section. Learning needs data to estimate those numbers, so fewer numbers generally means fewer examples are needed. Inference asks for a probability, such as the chance that one variable is 1. From a full table you get it by adding up every setting of all the others.

A chain turns that sum into a short pass from left to right. Let be the variable reached so far. Its forward message is the list of two probabilities for the values of , found after summing out every variable to its left. The forward step updates the message one variable at a time. This recursion is added here as an explanation and is not printed in the book:

The brute-force method adds up every setting of the other variables. For the last variable of binary variables, that is terms. The forward pass uses four multiplications per step, and there are minus one steps. Both methods give the same probability:

The chain in the demo has random transition chances drawn from a fixed seed. Press New random chain to draw another. For up to 14 the brute-force sum is run in full, and the two answers are compared. Above that the sum is too large to run in a page, so only its size is shown. The gap is the saving the book means: the forward pass grows in step with , while the brute-force sum doubles with each new variable.

Faster sampling in directed models

The book says that sampling is also accelerated in directed models, while undirected models are harder. The reason is the ordering from Section 16.3. Ancestral sampling visits each variable once, in an order where every parent comes first. One pass therefore gives one exact sample, with no burn-in and no question of whether the chain has converged:

A Gibbs sampler on an undirected graph starts from a state that may be far from typical. Its early sweeps are often discarded as burn-in, and it is hard to know when the samples are good enough, as the end of Section 16.3 explained. Ancestral sampling has none of this. The cost of an exact sample is fixed in advance.

The demo below uses a chain of eight binary variables, added here for the demo and not printed in the book. The first variable is 1 with chance 0.7, and each variable copies its parent with chance . Every press draws samples in order, and the estimate of the probability that the last variable is 1 is compared with the exact answer, which the forward pass from Section 2 gives.

Each sample costs exactly draws, here 8, so the number of draws grows only in step with the samples you ask for. The estimate settles down as the samples accumulate, and no burn-in period needs to be thrown away.

Separating structure from algorithms

The book describes a less quantifiable benefit: structured models let us separate representation from learning and inference. A model’s graph describes what depends on what. An algorithm describes how to learn or sample. Once they are separate, we can design an algorithm for a broad class of graphs, and we can design a graph for the relationships we believe are in the data. Any algorithm that accepts a class of graphs can then be paired with any graph in that class.

The book says that combining these algorithms and structures gives a Cartesian product of different possibilities. In the table below that means every structure meets every algorithm, and only some of the pairs work. The book adds that it would be much more difficult to design end-to-end algorithms for every possible situation. The demo below pairs four structures with three algorithms. A pair works when the algorithm’s requirement is met by the structure.

The table is a small Cartesian product. Gibbs sampling works on every structure, but it needs many sweeps. Ancestral sampling and the forward pass need arrows with an order, and the forward pass as written here also needs a chain. Changing either the structure or the algorithm changes the answer, which is why the two choices can be made separately.

The assumption behind a missing edge

The book states the rule plainly: anywhere there is not an edge, the model specifies the assumption that we do not need to model a direct interaction. A missing edge is therefore a claim, and the claim can be wrong. Here the claim between and says that they are independent once is known. The demo uses a true distribution with a strength on a direct link between and . The best chain that leaves that link out is built from the true pairs of neighbours:

The divergence measures how far the chain model is from the truth. It is zero when the missing link is truly absent, and it grows as the link gets stronger:

At = 0 the true distribution is itself a chain, so the chain model is exact and the divergence is zero. The divergence grows with the strength, which is the size of the interaction the missing edge ignores. So leaving an edge out is a good trade only when the interaction it ignores is weak. The strong links are the ones the graph should keep.

• A graph with at most parents per variable needs far fewer free numbers than the full table, , when is small. The count is the sum over the variables of 2 to the power of each one’s parent count.
• Structure lowers the cost of representation, learning and inference. A chain turns the brute-force sum of terms into a forward pass of multiplications.
• Ancestral sampling draws each variable once in a topological order, so one exact sample in a directed model costs draws, with no burn-in.
• Structures and algorithms can be chosen separately, which the book describes as a Cartesian product of possibilities.
• Each missing edge is an assumption. Its cost is the divergence , which is zero only when the assumption is true.

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.4 (pages 582), 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.