Section 1
Why a joint distribution needs structure
How to use this pageCommit to a guess before the demo answers it. Click any colored symbol to read what it is. Each challenge is solved by moving a control or clicking the graph, and it is worth 8 XP.
variables and their number, the data the joint distribution, the main object factors and conditionals, the model energies and dependence checks the normalizing constant
Predict first. A model has 10 binary variables. How many free numbers does a table for the full joint distribution need?
Think of a recipe card. Each step uses only a few ingredients, so the rest of the pantry does not matter for that step. A model of many variables works the same way: each pixel of an image, or each word of a sentence, interacts directly with only a few neighbors.
A single table for the whole joint distribution ignores that fact. With binary variables it needs free numbers, which the book calls very inefficient, computationally and statistically.
How many numbers must be stored?
one table for the whole jointfactored, each variable with at most k parentsyour n
At the starting setting, 30 binary variables need over a billion numbers in one table and about 220 in the factored model. The vertical axis is logarithmic, so one gridline is a factor of a thousand.
Challenge +8 XPMake the factored model need at least as many numbers as the full table. Lower and raise until the two counts meet.
If is at least , each variable may depend on every earlier one, which is the chain rule of probability and saves nothing. The saving comes from leaving dependencies out.
The remedy is to split the distribution into factors over a few variables each, and multiply them. Each factor’s parameter count is exponential in the variables it contains, so the cost depends on the largest factor. If every variable has at most parents, the count is a sum of small tables, added here and not printed in the book.
Going deeper: where the factored count comes from
This count is added here and is not printed in the book. Each variable has a conditional table with one free number for each setting of its at most parents among the earlier variables, so at most free numbers. The other number in each setting is fixed by the sum to 1. Summing over the variables gives:
Click any coloured symbol to see what it means.
Each new variable adds a table that stops growing once it has earlier neighbors. The full table keeps doubling.
Factorizing a joint distribution
Predict first. Take three binary variables , and . Suppose influences , and influences . Once is known, does the factor for still need ?
Once is known, tells you nothing more about . That is conditional independence, and it is written as
Click any coloured symbol to see what it means.
The joint distribution then splits into a product of distributions over two variables each, Equation 3.52. Set the five numbers of this chain in the demo below.
Click any coloured symbol to see what it means.
Each factor is a distribution of one variable given the one before it. The third factor has no in it, which is where the independence was used. The general chain rule would have there.
A chain a to b to c
joint probability of the eight states
The eight lines multiply one factor per variable, and their total is 1. The second box checks the independence: for each value of , the chance that equals 1 is the same whether is 0 or 1. Without conditioning, and are dependent, because reaches through .
Challenge +8 XPMake and independent without conditioning: the mutual information in the readout must fall below 0.0005 nats. Hint: the two b sliders decide how much a reaches b.
Going deeper: why the chain gives conditional independence
This derivation is added here and is not printed in the book. Divide the joint by the marginal of , then use Equation 3.52 and Bayes’ rule from Section 3.11:
Click any coloured symbol to see what it means.
The last line has no on the right of the bar in the second factor, which is exactly what conditional independence means.
Count the parameters. The chain needs five numbers, and an unrestricted table over three binary variables needs seven.
Section 3
Directed models
Predict first. A graph has arrows and , and nothing is observed. Are and independent?
A graph has nodes, one per random variable, joined by edges. An edge means the distribution can represent a direct interaction between its two ends. A graph that describes a factorization is a structured probabilistic model, or graphical model.
In a directed model the edges are arrows. The graph gives one factor for every variable : its conditional distribution given its parents, the nodes with an arrow into it, written . This is Equation 3.53:
Click any coloured symbol to see what it means.
Figure 3.7 is a directed graph over five variables, with the factorization of Equation 3.54:
Click any coloured symbol to see what it means.
Directed graph editor: click a node, then another, to add, remove or reverse an arrow
Click any coloured symbol to see what it means.
Compare the formula with Equation 3.54 for Figure 3.7. It has 11 free numbers, against 31 for an unrestricted table. The last line of the readout multiplies random tables over all 32 states and adds the results. The total is 1 for any graph and any numbers, so a product of conditional distributions is always a valid distribution.
Check it on the chain: gives no parents, the parent , and the parent . That reproduces Equation 3.52.
Challenge +8 XPSwitch to Ask mode and click two nodes that interact only indirectly: no arrow joins them, but a path does.
An edge means direct interaction. A path made of several edges means indirect interaction. A directed graph must have no directed cycle, and the editor refuses an arrow that would close one.
Section 4
Undirected models and the partition function
In an undirected model the edges are plain lines, so no factor can be a conditional distribution. Each clique, a set of nodes that are all connected to each other, gets a factor . A single edge is a clique of two nodes, and a triangle of edges is a clique of three.
Predict first. Can a clique factor be larger than 1?
Factors are non-negative, and their product need not add up to 1. Divide by the normalizing constant , the sum of the product over all states (Equation 3.55):
Click any coloured symbol to see what it means.
Written out, the constant is
Click any coloured symbol to see what it means.
Figure 3.8 has the factorization of Equation 3.56, with maximal cliques , and :
Click any coloured symbol to see what it means.
Build it below. The editor shades a patch behind each maximal clique, a clique that no other node can join, and fills the cliques with random positive factors.
Undirected graph editor: click two nodes to add or remove an edge
Click any coloured symbol to see what it means.
With Figure 3.8 loaded, the shaded triangle is , and the two bars are and . Table sizes grow fast with clique size: a factor over three binary variables has eight entries. Add every edge and there is one clique of five variables and a table of 32 numbers, with no saving.
This point is added here and is not printed in the book: a factor for a smaller clique can be absorbed into a larger one, so keeping only the maximal cliques loses nothing.
Challenge +8 XPAdd edges until the graph has a clique of four nodes. The shaded patch must cover four variables. Hint: two new edges are enough.
The value of is found here by brute force over 32 states, which is easy for five variables. For binary variables the sum has terms, so a model with 100 variables cannot be summed exactly. The book returns to this in Chapter 18, on confronting the partition function.
Section 5
One distribution, two descriptions
Predict first. Take the chain from Section 2 and reverse its arrows, so that the chain runs . Does the backward chain describe the same distribution as the forward chain?
Directed and undirected graphs are languages for describing distributions, not two exclusive families. Whether a graph is directed or undirected is a property of one description, and any distribution can be described both ways. The demo writes the chain three ways and compares them on every state.
Three descriptions of the same chain
directed, forwardundirecteddirected, backward
- Directed, forward: the starting point, factorized along the arrows.
- Undirected: two factors, and , normalized by .
- Directed, backward: the arrows reversed, with tables from conditional probability and Bayes’ rule.
The three bars coincide up to rounding error. Not every description is interchangeable, though: a collider, two arrows meeting at one node, expresses an independence that no undirected graph over the same three nodes can express. The book calls this an immorality (Section 16.2.6).
Section 6
The energy-based form
Predict first. In an energy-based model the unnormalized probability of a state is , where is the energy of the state. If the energy of a state is very large, what happens to its probability?
A convenient way to keep every factor strictly positive is to write the unnormalized probability as the exponential of a negative number, the energy. This is an energy-based model. Equation 16.7 in Section 16.2.4 gives the form:
Click any coloured symbol to see what it means.
No energy gives a probability of exactly zero, because the exponential of any real number is positive. The book adds that for some models constrained optimization is still needed to make sure that exists. Each clique is one term of the energy.
Experts on the cliques of Figure 3.8: a negative strength prefers disagreement
probability of each statethe state chosen by the checkboxes
Every state keeps a positive probability, however large the strengths. Each expert reacts only to the variables in its own clique. The readout also shows that the product of the three factors equals exp of minus the total energy. This particular energy is chosen for illustration and is not from the book.
Challenge +8 XPSet the strengths so that c and e disagree with probability at least 0.9, as the readout reports it. The strength on (c, e) is the main lever.
Going deeper: why the energy terms add up
The book states this identity in Section 16.2.4. The exponential turns each sum in the energy into a product of factors, so the energy form and the factor form are the same model:
Click any coloured symbol to see what it means.
Click any coloured symbol to see what it means.
The minus sign serves no purpose in machine learning. It is kept for compatibility with physics, where low energy means a likely state. A distribution of this form is a Boltzmann distribution, a name that the book uses in Section 16.2.4.
Separation and d-separation
Predict first. An undirected graph has the edges to and to . You observe . Are and separated?
The edges show which variables interact directly. What you often need is which variables interact indirectly, and when observing some variables switches that interaction on or off. The book treats this in Section 16.2.5.
In an undirected graph, a path is active if it passes through no observed variable. If an active path joins two variables, they are not separated. If every path contains an observed variable, or there is no path at all, they are separated, and the graph implies they are independent given the observed variables.
Separation explorer: click nodes to observe them, then pick two variables
an active pathinactive pathsshaded node = observed
In a directed graph the same idea is called d-separation, where the d stands for dependence. Whether a path is active depends on the role of each middle variable. Four roles are possible for a path of length two, and the explorer shows the first three below.
- Chain : observing blocks the path. Example, written for this page: rain makes the grass wet, and wet grass makes the path slippery.
- Common cause : observing blocks the path. Example, written for this page: hot weather raises both ice cream sales and sunburn.
Predict first. In the collider , you observe . Are and now dependent?
Collider : two causes of a common effect. The path is inactive while is unobserved, and it becomes active when is observed.
Challenge +8 XPIn the Collider tab, observe the middle node so that the two causes are not separated. Read the reason in the path list.
Example, written for this page: a burglary and an earthquake can each set off an alarm. They are independent until you hear the alarm. Then learning that an earthquake happened makes a burglary less likely. This is explaining away.
A longer path is active only if every variable along it passes its test. The explorer applies these rules and computes the conditional mutual information , which is 0 exactly when the two variables are conditionally independent given the observed ones.
Predict first. In the Figure 16.9 graph, and both point into , and points to and . They are separated given nothing. Once is also observed, are they still separated?
Try the examples the book reads off Figure 16.9, in its tab. and are separated given nothing, but not given , and not given . and , and also and , are separated given . In the Figure 16.7 tab, observing separates from , but and stay connected through their own edge.
Going deeper: the four cases of a path of length two
These four cases are the ones that the book lists in its Figure 16.8. They are taken from Section 16.2.5 and are not printed on pages 75 to 79.
- Chain: is active until is observed.
- Common cause: is active until is observed.
- Collider: is inactive until or one of its descendants is observed.
- Collider with a descendant: the same rule, with the descendant of observed.
The explaining away effect in the collider case is the book’s example with a colleague who is not at work: sickness and holidays are independent, until the absence is observed.
The book adds a warning. Separation reports only the independences implied by the graph, and a graph never implies a false independence.
Predict first. A graph with an edge between every pair of nodes is a legitimate description of any distribution. How many independences does it imply?
A graph may still fail to show a true one. Some independences hold only for particular values of the variables, and no graph can draw them. The book’s example has three binary variables: when is 0, and are independent, but when is 1, equals .
Challenge +8 XPIn the Figure 16.7 (undirected) tab, shade the single node that separates from .
What to take away
- A joint distribution is wasteful as one table. Factors over a few variables save parameters exponentially.
- A directed model has one conditional per variable, given its parents, and no directed cycle.
- An undirected model has one non-negative factor per clique and a normalizing constant , often intractable.
- An edge means direct interaction. A path of several edges means indirect interaction.
- Directed or undirected is a property of a description, not of a distribution.
- Observing a chain or common-cause node blocks a path. Observing a collider, or its descendant, opens it.
Final quizCheck 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 3.14 (pages 75–79), 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.