Learning Manifolds with Autoencoders

Data near a manifold

Real data rarely fill the space they live in. A handwritten nine is one image of 784 pixel values, but all the nines form a thin, curved set inside that huge space. A is such a set: a smooth, curved shape that the data lie on or close to. Its is the number of coordinates that name a point on it. An ant walking on a crumpled sheet of paper needs two numbers to say where it is, even though the paper floats in three-dimensional space. The sheet is the manifold, and the two numbers are its coordinates.

The book opens with this idea: data concentrate around a low-dimensional manifold. Methods that exploit this only loosely learn a function that behaves well on the manifold and may behave oddly away from it. An autoencoder aims further and learns the structure of the manifold itself.

The curve is the manifold, and each dot sits a little off it. The spread sets how far off, so a larger spread makes the data look more like a cloud. The dashed line joins the probe to its nearest point on the curve, and its length is the distance. Autoencoder training should bring points like the probe back onto the curve, which is why the probe is a useful target.

Every autoencoder training procedure balances two forces. The first asks the code to keep enough information that the input can be recovered through the decoder. This force applies to training examples only, because an input that is unlikely under the data need not be reconstructed well. The second force is a constraint or penalty that makes the encoder less sensitive to its input. Neither force works alone. Copying the input satisfies the first force without learning anything, and ignoring the input satisfies the second. Together they make the code represent only the variations that the data actually have.

If the data concentrate near a low-dimensional manifold, this compromise gives the code a local coordinate system. Only movements along the manifold change , and movements away from it leave the code almost unchanged.

Tangent planes

Stand on a curve at one point. The directions in which you can move and stay on the curve form a line, and that line is the tangent at the point. On a surface, the same idea gives a tangent plane, a flat plane that touches the surface at the point. A -dimensional manifold has independent directions at each point, and the book collects them as basis vectors of the tangent plane.

Figure 14.6 in the book shows a digit that moves up and down. Each position of the digit is one image, so the moving digit traces a curve in image space. At one position, the tangent direction shows how each pixel changes as the digit moves: some pixels brighten, some darken, and some stay the same.

This page uses a smaller picture. A bump of brightness sits in 16 pixels, and its centre is the position on the manifold. The tangent vector is the rate of change of the image with respect to . This definition is added here for the demo and is not printed in the book:

The tangent is the best straight-line guess for the next image. A straight step of size along it misses the true image by a small amount. The demo measures that miss, which is the length of the difference between the true image and the straight step:

Two facts from the demo matter. First, the tangent length barely changes as the bump moves, from 0.71 to 0.74 across the range, so the bump keeps its shape and only its location changes. Second, the miss grows with the square of the step. Halve the step and the miss falls by about four times, because the straight line is correct to first order and the error comes from the curvature of the path. A small step is therefore a good linear guess.

Reconstruction flat at the data

Figure 14.7 in the book is a one-dimensional toy. The data are three points on a line, and the manifold is just those three points. The book gives no positions, so the demo places them at 0.25, 0.5 and 0.75 (added here). The best reconstruction function crosses the identity line exactly at each data point, and it is flat there. Between two points it rises quickly near their midpoint, because a corrupted input in the gap must be carried back onto one of the neighbouring points. Arrows below the plot point from each input toward its nearest data point. That arrow is the residual .

A reconstruction with this shape makes the output insensitive to small changes near each data point, and it is sensitive only in the gaps. This is the compromise of Section 1 in one picture: flat around the manifold, steep between the parts of the manifold that the data cannot reach.

To rebuild the figure, the demo needs a smooth reconstruction with the same shape. A kernel-weighted average does the job. Each output is an average of the three data points, and each point gets a weight that falls off with the distance from the input. The kernel width sets how fast the weights fall off. This formula is added here and is not printed in the book:

When is very small, the nearest data point gets all the weight and the average becomes a staircase. When is large, the average is smooth and nearly constant. The demo below moves between those extremes and computes the slope at each data point.

The demo reports the slope of the reconstruction at the data points and in the gap between two of them. The slope at the data points is close to zero for small widths, and the slope in the gap is large. The book notes that the denoising autoencoder explicitly tries to make the derivative of its reconstruction small around the data points, and that the contractive autoencoder does the same for the encoder. The derivative may be large between points, where corrupted inputs must be carried back onto the manifold.

Neighbour graphs and local pancakes

Before autoencoders, most manifold learning used the nearest-neighbour graph. It has one node per training example, with edges to the examples near it. Each node gets a tangent plane that spans the difference vectors to its neighbours, as Figure 14.8 shows with faces. Once the local planes are known, a global coordinate system follows from an optimisation or a linear system. Figure 14.9 tiles a manifold with locally flat Gaussian patches, called pancakes, which have a very small spread away from the surface and a large spread along it.

The book calls the representation of a training example its embedding, a short vector with fewer coordinates than the input space. Non-parametric methods learn an embedding for each training example directly. A more general mapping, called an encoder, gives an embedding for any input, including inputs that were never in the training set.

These methods have a fundamental difficulty, which the book attributes to Bengio and Monperrus (2005). They can only generalise a shape by interpolating between neighbouring examples. A manifold with many peaks, troughs and twists needs a very large number of examples to cover each variation. A variation with no nearby example is not represented at all.

The demo builds the graph on a wavy curve and estimates each node's tangent from its neighbours. The estimate is a local PCA: the direction of greatest spread of the node and its neighbours, read from their covariance . The formula is added here and is not printed in the book. Here is the set of neighbours of node , and is the angle of the estimated tangent:

The error depends on the node. Some nodes are within a degree of the true tangent, and others are off by ten degrees or more, because the neighbourhood of a node can be lopsided or can span a bend. In the demo, 23 of the 30 nodes have a larger error with four neighbours than with two. A wider neighbourhood spans more of the bend, so its principal direction can tilt away from the tangent. This is a property of the estimate, not a claim from the book.

The second demo shows the coverage problem. A curve with more wiggles is longer and bends more, so the same radius around each example covers less of it. Each example here owns a pancake along the curve, and the coverage is the share of the curve within a fixed radius of 0.10 of some example. The examples come in a fixed order, so raising only adds points.

Why manifolds grow complicated

The book ends the argument with translation. Watch one pixel as an image slides past it. Its brightness rises and falls, and it makes one peak or trough for every bright bump or dark valley in the image. So the more intricate the picture, the more intricate the manifold made by sliding it. This motivates distributed representations and deep learning for capturing manifold structure.

The demo uses a one-dimensional template of 64 pixels, with bright bumps spaced around a circle. It counts the peaks and troughs that one chosen pixel sees as the template shifts through one full cycle. A real digit is two-dimensional, so its count is harder to follow by eye, but the same argument applies.

The count is exact in this toy. Every peak and trough of the template passes the chosen pixel once during a full cycle, so the pixel sees the same number of extremes as the template has. Each extra bump adds two extremes to the curve that every pixel traces.

• A manifold is a low-dimensional curved set near which the data lie, and its tangent vectors give the directions in which it can move locally.
• A reconstruction that is flat at the data and steep between them captures the manifold, because it is insensitive to directions off the manifold.
• Neighbour graphs estimate tangents from nearby examples, but they need many examples to cover a twisty manifold.
• Translation makes a manifold as complicated as the template it moves, which motivates distributed representations and deep learning.

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 14.6 (pages 515–520), 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.