The Challenge of Unstructured Modeling

The size of a lookup table

Take a small colour picture of 32 by 32 pixels. Write each of its 3072 numbers as a bit that is 0 or 1. A probability model for such pictures gives a probability to every possible bit pattern. The simplest model is a lookup table, one stored probability for each pattern. The book asks how far that simple idea can go.

Write the number of variables as and the number of values each variable can take as . A vector of variables is written , and a probability of one full pattern is . The table needs one value for every pattern:

Before you use the calculator, make a guess. How many table entries does the picture model need, with one probability per bit pattern?

The plotted line is the logarithm, to base 10, of the table size. Each extra variable adds the same height, , so the line is straight. The picture needs = 3072 variables with = 2. The table therefore has entries, and the calculator shows 5.81 × 10⁹²⁴, a number with 925 digits. The book states the same count as and calls the table approach not feasible.

The book compares this count with the estimated number of atoms in the universe and says the count is more than 10⁸⁰⁰ times larger. The exact count is computed above. The value 10⁸⁰ for the number of atoms is a commonly quoted estimate that the book does not print.

The table stores numbers, but they are not all free. The probabilities must add up to 1, so the last one is fixed by the others, which leaves one fewer free number. This subtraction is added here for clarity. The book makes the same subtraction in its discrete relay example in Section 16.2.1:

The minus one changes nothing about the scale of the problem. It is a small correction to a very large number.

Four tasks that need the whole input

A classifier takes a rich input and returns a short label, such as the name of the object in a photo. It can ignore most of the input. The background of the photo, for example, rarely matters. Probabilistic models are asked to do more. The book lists four tasks that need the whole input, and each one is harder than classification.

• Density estimation. Give the model an input and it returns the probability . One number comes out, but a single unusual element must still lower the probability, so the model must understand every element.
• Denoising. A damaged input goes in and a clean estimate comes out, one value per element. Even one damaged area shows that the whole input has been read.
• Missing value imputation. Some elements are observed and the others must be filled in or given a distribution. The model has to be able to restore any element, so it needs to know the whole structure.
• Sampling. The model produces new inputs that follow the same distribution. If one element is drawn from the wrong distribution, every sample is wrong.

Figure 16.1 in the book shows a sampling task on small natural images from the CIFAR-10 dataset. The top rows are training images and the bottom rows are samples from a trained model. Each sample appears at the same position in the grid as the training image closest to it in Euclidean distance, so the reader can check whether the model copies its training data. The images cannot be reproduced here, so the demo below runs the same test on a small toy problem. The toy is added here and is not printed in the book.

The toy has 30 training points drawn from two clusters, one near −2 and one near +2. The memorizer returns a training point and adds a little jitter, which is random noise with a chosen spread. The model draws from the two clusters themselves and never returns a training point. Each sample is shown with its distance to the nearest training point, and a copy is a sample at distance zero. With the jitter at 0, the memorizer samples sit exactly on the training data. The model samples are new points. None of them is a copy, although many land near a cluster.

The table and its four costs

The table hits four limits, and the book names each one. The first is memory: for all but very small and , the table does not fit. The second is statistical efficiency: the more parameters a model has, the more data it needs. A table with an astronomical number of entries would overfit any real data set unless extra assumptions link its entries.

The last two limits concern computation. To answer a question about one variable, the table must be summed over all the others. This is the cost of inference. To draw a sample, the naive method adds probabilities in table order until the running total passes a random number . That is the cost of sampling. Both costs grow with the table, so they are as large as the memory.

The left side is the marginal probability of the first variable: the chance that it equals , whatever the other variables do. Read the right side as a sum. Fix the first variable to one value , and add up the table entries that agree with it. The sum runs over the other minus one variables, which gives terms. That is a fraction of the table, not a small piece of it.

The bars are the probabilities of the table entries, listed in table order. The draw is a random number between 0 and 1. The sampler reads entries one by one and stops at the first entry where the running total reaches . A draw that lands in the last entries reads almost the whole table. The average over many draws is the expected cost, and it depends on where the probability sits. With the skew at 0 the mass is spread evenly, so the sampler reads about half the table on average.

The relay race keeps only direct links

The book gives an example that shows where a table wastes information. Alice, Bob and Carol run a relay. Alice runs first, then hands the baton to Bob, who hands it to Carol. Each finishing time is a continuous random variable, which means it can take any value in a range, not only whole numbers. Bob’s time depends on Alice’s, because Bob cannot start before Alice finishes. Carol’s time depends on Bob’s. Carol’s time depends on Alice’s only through Bob.

The book says the model needs only two interactions, Alice on Bob and Bob on Carol, and that the third, indirect one can be left out. To see this with numbers, this page uses a toy version of the race. The toy is added here and is not printed in the book. Each time is a linear function of the one before plus a random delay. Alice’s time is , Bob’s is , and Carol’s is . The numbers and are the couplings, and the delays are and .

The toy has one special property. Carol’s delay is independent of Alice and Bob, so once is known, is determined up to fresh noise that carries nothing about Alice. For this linear Gaussian toy, the partial correlation between Alice and Carol given Bob is therefore exactly zero. This derivation is added here and is not printed in the book.

The ordinary correlations and are not zero. Their formulas, also added here, are:

The demo draws 400 races from the toy, then checks the formulas. The left picture plots Alice’s time against Carol’s. The right picture removes the part explained by Bob and plots what is left. The left picture is a tilted cloud, and the right one is a round cloud, which is what zero partial correlation looks like.

The sample partial correlation is not exactly zero because 400 races are a finite sample. Across repeated samples of 400 races, its spread is about 1 divided by the square root of 400, which is 0.05. The formula for the ordinary correlation of Alice and Carol is not zero, so the two-link model still explains why Alice and Carol move together. The third, indirect link is what the model leaves out, and the partial correlation shows that nothing is lost by leaving it out.

The payoff from few direct links

Structured probabilistic models make the choice of direct links explicit. A link says that two variables interact directly. A missing link is a modelling assumption: the two variables are treated as not interacting directly. Section 16.2 turns this idea into a language of graphs. The rest of this chapter depends on it.

The cost argument is the same in every case. A table over variables with values each needs entries. If each conditional table involves only a few variables, the total is far smaller. The relay race from Section 4 keeps two links instead of three, and the saving grows as the number of runners grows.

• A table over variables with values each has entries. This is too large to store, fit or sum for realistic .
• Classification can ignore most of the input. Density estimation, denoising, imputation and sampling need the whole input.
• Summing a table for a marginal, or scanning it to draw a sample, costs about as much as reading the table.
• When each variable interacts directly with only a few others, far fewer numbers are needed. Leaving out the indirect link in the relay race loses no information once the middle runner is known.

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.1 (pages 559–563), 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.