Using Graphs to Describe Model Structure

A graph as a list of direct links

Section 16.1 showed that a table over many variables is too large. A structured probabilistic model fixes this by drawing a graph. A graph has nodes, one per random variable, and edges between nodes. Each edge says that two variables interact directly. Two variables with no edge between them can still influence each other indirectly, through a path of edges, but the model does not store that interaction separately.

Think of a map of direct flights. Two cities can be connected by a trip with several stops, but the map only draws the flights that exist. The book uses the same idea for probability: keep the direct interactions, and let the indirect ones follow from them.

The book describes two families of graphs. Directed models use arrows, and undirected models use plain lines. Both use the graph to decide which factors or conditional tables a model needs. Predict first: the relay race of Section 16.1 has three runners, and the book keeps two links out of three. With 100 values per runner, how many times fewer numbers does the two-link model need than the full table?

The bars are on a logarithmic scale, because the full table is many times larger than the other two at this size. The relay chain is the relay model of Section 16.1 with three variables, each with values. Count it directly. Alice’s time needs numbers, because the probabilities must add up to 1. Each conditional table has rows, one for each value of its parent, and each row needs numbers for the same reason. So each conditional needs numbers. The total is:

This count is added here and is not printed in the book. The book gives the numbers for : 99 for Alice and 9,900 for each conditional, a total of 19,899. Compare this with numbers for the full table over the same three variables.

The shift model, the third bar, comes from another assumption in Section 16.2.1. Suppose Bob always runs the same, so his finishing time is Alice’s time plus a fixed running time. Then each conditional needs only numbers, and the whole model needs numbers. This shift count is added here.

Directed models and their arrows

A directed graphical model, also called a Bayesian network or belief network, uses a graph with arrows and no cycles. An arrow from to another variable means that the second variable’s distribution is defined given the first. The variables that point into a node are its parents, written . Each node has one local conditional, , and the joint distribution is their product:

Read the product as a recipe. Start from the roots, which have no parents, and give each node a table that depends only on its parents. The graph is directed and acyclic, so the recipe never asks for a value before it is known.

The book applies this to the relay race in Figure 16.2. Alice’s time has no parents. Bob’s time depends on , and Carol’s time depends on only. The joint is therefore:

Each factor is a conditional table, and the arrows say which conditionals are needed. The model has no table for , because Carol does not depend directly on Alice. That absence is the structure.

Each node with 2 values needs one number for each configuration of its parents, because the probability of is set separately for each configuration. A node with parents therefore needs numbers. The total is the sum over nodes, a count added here and not printed in the book:

For binary variables this sum is exact. A root needs one number, and with every arrow allowed the count is , the same as the full table for four variables. Fewer arrows mean fewer numbers. The demo above is set to the chain 1 to 2 to 3 to 4, which is the directed analogue of Figure 16.2. (The demo is built for binary variables, which keeps the count to the powers of 2 shown here.)

Undirected models and cliques

Some interactions have no direction. The book’s example is health. You, your roommate and your colleague can pass a cold to one another. The roommate and the colleague do not know each other, so they can infect each other only through you. Two edges are enough: roommate to you, and you to colleague. The graph has no arrows, and the model is an undirected graphical model, also called a Markov random field or a Markov network.

An undirected model has no conditional tables. It has a clique for each fully connected subset of nodes, and each clique has a non-negative factor, also called a clique potential, . A factor scores how much the variables of its clique like each joint state. The unnormalized distribution is the product of the factors:

The factor for the clique of you and your colleague can be a table. The book’s values are shown below. Here state 1 means healthy and state 0 means sick. Both healthy has the highest value, and the state where only one of you is sick has the lowest, because it is rare. Both sick has a higher value than one sick, but a lower value than both healthy.

The table has four numbers because the clique has two binary variables. The book does not normalize it. This page shows only the factor for the clique of you and your colleague. The book’s full model also has a factor for you and your roommate, which is not drawn here. So every probability on this page is for this one factor alone, not for the full model. Dividing each value by the total, as the next section explains, turns this factor into a probability over the four states. The demo does this division for you.

The book requires each factor to be non-negative, and it notes that multiplying the factors does not by itself guarantee a valid probability distribution. Only the normalized product is a probability distribution, and the normalization is the subject of Section 4.

The partition function

Divide the unnormalized distribution by its total to get a probability. The total is the partition function, written , a name borrowed from statistical physics. It is a sum over all states for discrete variables, and an integral for continuous ones:

Here is the number that makes add up to 1. The book writes as a function of the factor parameters, because changing the factors changes the total. Since the sum runs over every joint state, is usually intractable for deep models. The book notes this, and Chapter 18 covers approximations.

The demo below builds a chain of binary variables. This chain example is added here and is not printed in the book. Each neighbouring pair has a factor equal to when the two values agree and 1 when they differ. Brute force adds up terms. A transfer matrix uses the chain structure to reach the same answer in steps, each a product with a 2 by 2 matrix. The two must agree, and they do.

The book notes that must exist before a distribution can be defined. A factor can fail to define one. In the book’s example, a single continuous variable with factor gives an integral that diverges. The next demo uses a factor instead. The partition function exists only when .

When the area under the curve is finite, and the value is . This identity is added here and is not printed in the book. When the factor does not shrink as grows, so no finite partition function exists. The book’s other point is that the domain matters. For a vector with bias parameters and factors , the answer depends on where each lives. On the real line the integral diverges. On each variable is independent with . On the one-hot vectors , and the distribution is the softmax of .

Energy-based models

A convenient way to make every factor positive is to write it as an exponential. An energy-based model defines the unnormalized distribution through an energy function :

The exponential is always positive, so no state can get probability exactly 0. The learner can pick any energy function, and the training problem becomes unconstrained. Lower energy means higher probability. Any distribution of this form is called a Boltzmann distribution.

The energy adds up over cliques. Because , each clique’s factor becomes one term of the energy. Take a graph of six nodes with five cliques, the pairs (a,b), (b,c), (a,d), (b,e) and (e,f). Its energy is then:

Each term acts as an expert that checks a soft constraint on a few variables. Multiplying the probabilities multiplies the experts, which is why the book calls this a product of experts. The minus sign in equation 16.7 does not change what a model can express, because the learner can choose the sign of . The sign is kept for compatibility with physics.

The demo applies equation 16.7 and divides by the sum of all four unnormalized values, which is for this four-state model. Lowering one energy raises that state’s share of the total, and the others lose share.

The free energy of equation 16.8 is what a model with hidden variables uses, because it removes the hidden variables by summing them out. Taking logs of equation 16.7 gives , so the energy is the negative log of the unnormalized probability.

The book calls restricted Boltzmann machines undirected models in Section 16.2.6, which is one well-known member of this family.

Separation and d-separation

A graph shows direct edges. We also want the independences that the graph implies, meaning which sets of variables are conditionally independent given others. An observed variable is one whose value is known. The question is whether observing some nodes blocks every path between two others.

For an undirected graph, a path is active when none of its interior nodes is observed. Two sets of nodes are separated given a third set when every path between them is blocked. This is the separation of undirected models. A chain of three nodes is active while its middle node is unobserved, and blocked once the middle node is observed.

Directed graphs need more care. A node with two arrows pointing into it is a collider. The book’s rule for directed paths is as follows.

• Chains and forks. A path through a node that is a chain (one arrow in, one out) or a fork (arrows out of it) is active only if that node is unobserved.
• Colliders. A path through a collider is active only if the collider or one of its descendants is observed. A descendant is any node reachable by following arrows forward. This is the explaining away effect: observing a collider makes its parents dependent.
• d-separation. Two sets are d-separated given a third set when every path between them is blocked by these rules. The “d” stands for dependence.

The demo applies these rules to every simple path. Click a node, or tick its box, to observe it. Choose a pair of nodes. Then the demo lists the first active path, or states that every path is blocked.

Two checks from the book’s figures are worth testing. In Figure 16.9, observing separates a from e, since is a chain node on the path. Observing the descendant activates the collider at c, so a and b are not separated given d. In Figure 16.7, observing separates a from c, but a and d stay connected through their direct edge.

Separation gives a sufficient test: if two sets are separated, they are conditionally independent. A graph can still miss independences that hold only for particular values of the variables.

From directed to undirected and back

Every probability distribution can be represented by a directed model or by an undirected model, using a complete graph with every edge present. A useful graph has to leave edges out, though, and each kind of graph encodes some independences that the other cannot. A directed model can express one pattern that an undirected graph cannot: two parents of a common child. The book calls this an immorality. The two parents are not connected, yet they become dependent once the child is observed.

To turn a directed graph into an undirected one, make a moralized graph. Keep every edge without its arrow. Then join every pair of parents of a common child with a new edge. This is the step that marries the parents. The moralized graph keeps all the dependences but may add edges, so it can lose some independences.

The demo shows the basic case. A chain stays a chain when it is moralized. The immorality, with a and b both pointing into c, becomes a dashed edge between a and b. That edge says a and b are dependent even when c is unobserved, which the directed graph does not say.

The reverse direction needs more work. An undirected loop of length four or more with no chord cannot be turned into a directed graph without losing some independences. A chord joins two non-consecutive nodes of the loop. Adding chords gives a chordal, or triangulated, graph. Then the arrows are chosen by an ordering: every edge points from the earlier node to the later one, which cannot create a cycle.

Factor graphs and the summary

An undirected graph has an ambiguity. A triangle of three nodes may come from one factor over all three, or from three factors over pairs. Both versions have the same graph, but they are different models. A factor graph removes the ambiguity by drawing each factor as its own node. It is bipartite: circles stand for variables, squares for factors, and an edge joins a variable to a factor when that variable is an argument of the factor. Edges never join two factors or two variables.

The same triangle can be drawn as one big square, or as three pair squares. The book states that the three-pair version is asymptotically cheaper. The demo below compares the number of entries for binary variables. The claim is about scaling, so the comparison is shown for growing clique sizes.

At three variables the single factor needs 8 numbers and the three pairs need 12, so the single factor is smaller. The pairs win from six variables on, where 64 numbers compete with 60. The book’s claim concerns growing clique sizes, and this crossover is where the effect first shows in these counts.

Summary

• A graph draws only the direct interactions. Indirect ones follow from the paths.
• A directed model uses arrows and one conditional table per node, and its count is the sum over nodes of 2 to the power of the number of parents.
• An undirected model uses cliques and factors. Its distribution is the normalized product of the factors, and the normalizer is the partition function, which is often intractable.
• An energy-based model writes each factor as an exponential of a negative energy, so every state has a positive probability.
• Separation, and for directed graphs d-separation, read the independences from the graph. Colliders behave differently from chains and forks.
• Moralization turns a directed graph into an undirected one by marrying parents, and triangulation with chords makes the reverse possible.
• A factor graph draws every factor as its own node, which removes the ambiguity of undirected cliques.

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.2 (pages 563–580), 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.