Challenges Motivating Deep Learning

Why simple algorithms stall

Pick a restaurant by the ratings of its nearest neighbors on a short street, and the rule works. Give each restaurant twenty features, such as cuisine, price, noise and lighting. Your nearest remembered place is no longer close. The method did not get worse. The space around each new point got emptier.

Generalizing means answering well on inputs the learner never saw during training. Simple learners stall on tasks such as speech and object recognition.

In the demo, is a smooth function of inputs, and the learner has examples. The vertical axis is the error on fresh points divided by the error of always answering the average, so the dashed line at 1 means no better than the average.

Each added input dimension pushes the error up. With the error is about 0.3 in 5 dimensions, 0.8 in 12 and 1.3 in 20, where the learner is worse than the average because it copies a neighbor that is not really close. The excess shrinks when you raise , but more data alone barely helps.

The curse of dimensionality

This is the curse of dimensionality: the configurations of the variables grow exponentially with their number.

Cell counting

Say you tell apart values of each variable and split the input space into cells. One variable gives cells, two give and three give . For variables the count is

So a learner that treats every cell separately needs about examples, at least one per cell.

The drawings grow from to to cells. The counter goes much further: ten values per variable and 100 variables give a one followed by 100 zeros, far beyond the atoms usually estimated for the observable universe (a standard rough figure, not a number from the book).

Most cells hold no example

The book calls this a statistical challenge: the number of configurations is far larger than the number of training examples. A cell-by-cell learner answers from the examples in its own cell, and most high-dimensional cells are empty. The demo shows this in two dimensions. Switch between the tasks and watch which cells have an answer.

With 40 examples and 36 cells most cells have a point. Raise to 14, which makes 196 cells, and most of the square turns hatched. The learner did not get worse where it has data. It has too many cells for the data it has.

The chance of an empty cell

The black dots are direct simulations, and they sit on the formula.

The curve is close to 1 for a few dimensions and then drops inside a narrow band. The edge sits near the dimension where first exceeds . Ten times more data moves the edge by only , about one dimension for . The curse is not solved by waiting for more data.

Local constancy and smoothness regularization

To generalize, a learner needs a prior belief about the kind of function it should learn. The most widely used one is the smoothness prior, also called local constancy: the function should not change much within a small region. It says that a known answer is probably right nearby. In symbols, the learner looks for a function with

for most configurations and small changes .

Many simple algorithms depend on this prior alone, and that is why they do not scale to AI-level tasks.

Nearest neighbors: the extreme case

Nearest-neighbour predictions are constant on each region of points that share the same nearest training points. These regions form a Voronoi diagram. Drag the points, click an empty spot to add one, and raise .

For the number of regions cannot be more than the number of points, and in this demo it equals that number. Each example informs only the neighborhood around it. With or more, the count can exceed the number of points, but those regions are cut out by the same few points and add no information of their own.

Local kernels: template matching

Kernel methods interpolate between nearby training answers. A local kernel is large when two inputs are alike and falls off as they separate. It acts as a template matcher. The two formulas below are added here; the book states only the idea.

A narrow kernel copies one example and a wide one averages many. The readout shows how far a small change moves the answer, as Equation 5.103 requires.

Decision trees

A tree cuts the input space into one region per leaf, each with its own parameters. To distinguish regions takes about examples, since each region needs its own data.

The target is a smooth wave. With 60 examples the error on the fresh grid falls from 0.25 with one leaf to about 0.14 with 12 and 0.12 with 30. Beyond that it stops improving, while the error on the training points keeps falling to zero. The tree starts to fit the noise of its own training set. Local methods like these have limits, and much of the motivation for deep learning comes from them.

Non-local generalization

The book now asks whether a complicated function with many more regions than training examples can be learned at all. Its example is a checkerboard. A learner that uses only smoothness knows the color of a new point only when the point falls in a square that holds an example. Every other square is a guess.

The demo shows the left learner, nearest neighbors with no extra assumption, and the right learner, which is told that the pattern repeats every two squares. The readout gives the accuracy of both on test points.

With 24 examples the local learner is only a little above chance, while the periodic learner reaches about 90 percent on a 6 by 6 board. The assumption is the price: a learner with periodicity built in is useless on a target that is not periodic. The book notes that ordinary neural networks avoid such task-specific assumptions.

Dependencies between regions

The key insight is that regions can be defined from examples when assumptions link the regions. The learner then generalizes non-locally.

A simple picture is a world with independent yes-or-no factors, such as red or gray, car or truck. There are combinations.

The factored model is added here to make the idea concrete. It is not printed in the book.

The factored learner's error falls to zero near examples in the typical sample, while the local learner stays high. The dashed line marks . Press the new-contributions button a few times: some samples are unlucky and need a few more examples. This near-threshold behavior is a toy result from this demo, not a theorem of the book.

Manifold learning

A manifold is a connected region that looks flat up close. Stand on the Earth and the surface looks like a plane, but it is a sphere in three dimensions. Along a manifold you can walk to a neighboring point, and the number of directions you can walk is the local dimension.

In machine learning the word is used loosely: a connected set of points that a few degrees of freedom describe well, inside a higher-dimensional space.

Locally flat

Walk along the surface of a sphere of radius . The straight line between the ends is the chord, and for short walks it is almost the same length as the arc.

For a 100 km walk the difference is about one meter, one part in a hundred thousand. A flat map is accurate at that scale. This example is added here and is not printed in the book.

A manifold in a higher-dimensional space

The book's second picture is data that lie near a one-dimensional curve in the plane, like a twisted string. The solid gray line is the underlying manifold. The demo measures the local dimension by looking at the points inside a circle. If they stretch along one direction, the local dimension is one. If they spread in two, it is two.

Drag the center of the circle to move the neighborhood. A small radius on the string gives one direction, and a large radius takes in the bends. A figure eight is one-dimensional almost everywhere and two-dimensional at its crossing, so its local dimension changes from place to place.

Evidence for the manifold hypothesis

Many problems look hopeless if the learner must handle interesting variation across the whole of . The manifold hypothesis assumes that most of that space holds invalid inputs, and that the interesting inputs lie near a collection of manifolds. The book says it may not always be correct or useful, but for images, sounds and text it is at least approximately correct. It offers two kinds of evidence.

First observation: real data are concentrated

Uniform noise essentially never looks like a photograph, and random letters almost never form English. The book's Figure 5.12 shows uniformly sampled pixels as the static of a television with no signal. Real inputs occupy a tiny share of all possible inputs.

The demo makes this exact in a miniature world of by pixel images. Two of the grid lines in each direction fix a rectangle, so the structured count is , out of . This example is added here and is not printed in the book.

At 3 by 3 pixels about 7 percent of images are structured. At 5 by 5 only about 7 in a million are. Beyond about 11 by 11, a uniform draw would not show a structured image, even at a billion draws a second for the age of the universe.

The structured family did not shrink, and the same holds for text: uniform letters give nothing like English among the strings.

Second observation: transformations

Concentration alone does not show that data lie on manifolds. The examples must also connect through transformations: dim or brighten the lights, move or rotate an object, and each continuous change traces a path through image space. This module does not reproduce the experiments in the literature that support the hypothesis.

The distance grows as the bar turns away from the reference, levels off near 90 degrees and returns to zero at 180, where the bar is the same bar turned over. This picture is added here and is not printed in the book. The dashed line is the distance between two noise images, which is larger than any bar in the family.

Coordinates on the manifold

When data lie on a low-dimensional manifold, the natural description is a set of coordinates on it. A road is a one-dimensional manifold, and an address number along it replaces three space coordinates.

In symbols, a point comes from manifold coordinates through a map . This formulation is added here and is not printed in the book:

Here is the input dimension and the number of coordinates.

The unrolled sheet

Two points on neighboring turns of a rolled sheet can be close in space yet far apart along it. This device is added here and is not printed in the book. Such coordinates are hard to find from data.

Click two points to choose them. As you unroll, the straight-line distance grows until it matches the distance along the sheet. A learner that trusts straight-line neighbors would merge points from different turns.

The book's Figure 5.13 shows faces that vary along two rotation angles, and Figure 20.6 later illustrates learning such coordinates. The demo below builds a toy of that setting.

Each image has 24 by 24 pixels, but two numbers explain all the variation.

What to take away

• Configurations of variables grow like , so most regions stay empty (Section 2).
• The smoothness prior of Equation 5.103 needs about as many examples as regions (Section 3).
• Assumptions that link regions allow regions from examples (Section 4).
• Real data concentrate near low-dimensional manifolds (Sections 5 and 6).
• Manifold coordinates describe data with few numbers (Section 7).

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 5.11 (pages 155–165), 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.