Compress, then reconstruct

An autoencoder is a network trained so that its output matches its input. It has two halves. An encoder $g$ maps an input $x \in \mathbb{R}^n$ to a code $z \in \mathbb{R}^m$; a decoder $h$ maps the code back to a reconstruction $\hat x \in \mathbb{R}^n$:

$$z = g(x), \qquad \hat x = h(z), \qquad \mathcal{L} = \mathbb{E}_x\, \lVert x - h(g(x)) \rVert_2^2 .$$

The input is its own target, so no labels are needed. The identity function would solve the problem perfectly and teach us nothing. The interesting part is always the constraint that stops the network from copying: a code narrower than the input, a penalty on the code, noise added to the input. Whatever the constraint forces the code to keep is what the autoencoder learns about the data.These first four pieces cover autoencoders in general; piece 4 of Part I gives a shorter tour. Pieces 5 to 8 specialise to the sparse autoencoders used in interpretability, and pieces 9 to 13 review the evidence on them.

A short history

Autoencoders are as old as backpropagation. The 1986 paper that popularised it included the encoder problem: pass eight one-hot patterns through three hidden units and reproduce them at the output. The network learned something close to a three-bit binary code.Rumelhart, Hinton and Williams, Learning internal representations by error propagation, 1986. Within a few years it was shown that an autoencoder trained with squared error and a narrow code layer learns, at best, what the singular value decomposition already gives.Bourlard and Kamp, Biological Cybernetics, 1988; Baldi and Hornik, Neural Networks, 1989. Deep autoencoders returned in 2006, when layer-wise pretraining made it possible to train them and they produced better low-dimensional codes than PCA.Hinton and Salakhutdinov, Reducing the dimensionality of data with neural networks, Science, 2006. Since then the idea has been reused many times, in denoising, anomaly detection, pretraining, and the variational autoencoder, which made it a generative model (piece 3).

The linear case is PCA

Take the smallest example: two numbers in, one number in the middle, and everything linear. Assume the data are centred. The encoder projects onto a unit vector $u$ and the decoder puts the result back along the same line:

$$z = u^\top x, \qquad \hat x = u\, z = u u^\top x .$$

The error is what the projection leaves out:

$$\mathbb{E}\,\lVert x - u u^\top x\rVert^2 \;=\; \mathbb{E}\lVert x\rVert^2 - u^\top \Sigma\, u, \qquad \Sigma = \mathbb{E}[x x^\top].$$

Minimising the error is maximising $u^\top \Sigma u$ over unit vectors, and the answer is the top eigenvector of the covariance: the first principal component.

Set the direction to 10° and turn it. The error curve has a single minimum, at the first principal component, and a single maximum, at right angles to it. Now reduce the elongation of the data from 3.0 toward 1 and the curve flattens. When the cloud is round, every direction keeps the same share and no single code is better than another.

A low-rank factorisation of the data

The derivation above tied the decoder to the encoder. Drop that assumption and look at the whole dataset at once. Stack the $N$ centred examples as the columns of a matrix $X \in \mathbb{R}^{n\times N}$. A linear autoencoder with encoder $W_{\mathrm{enc}} \in \mathbb{R}^{m\times n}$ and decoder $W_{\mathrm{dec}} \in \mathbb{R}^{n\times m}$ minimises

$$\mathcal{L} = \frac1N \big\lVert X - W_{\mathrm{dec}} W_{\mathrm{enc}} X \big\rVert_F^2 .$$

Name the codes of all the examples $Z = W_{\mathrm{enc}} X \in \mathbb{R}^{m\times N}$. The reconstruction is then $W_{\mathrm{dec}} Z$: an $n\times N$ matrix written as the product of an $n\times m$ and an $m\times N$ factor, so its rank is at most $m$. Training a linear autoencoder is fitting a rank-$m$ factorisation $X \approx W_{\mathrm{dec}} Z$, with one extra condition: the right factor must be a linear function of the data, $Z = W_{\mathrm{enc}}X$.

How good can a rank-$m$ approximation be? Write the singular value decomposition $X = U\Sigma V^\top$, with singular values $\sigma_1 \ge \sigma_2 \ge \dots$ The Eckart–Young theorem says that no matrix of rank at most $m$ comes closer to $X$ in Frobenius norm than the truncated SVD, which keeps the top $m$ terms:Eckart and Young, Psychometrika, 1936.

$$X_m = U_m \Sigma_m V_m^\top, \qquad \lVert X - X_m\rVert_F^2 = \sum_{i \gt m} \sigma_i^2 .$$

The extra condition costs nothing, because the truncated SVD is itself of the autoencoder’s form: $X_m = U_m U_m^\top X$. Take $W_{\mathrm{enc}} = U_m^\top$ and $W_{\mathrm{dec}} = U_m$, and the code is $Z = U_m^\top X$. So the best linear autoencoder is the best rank-$m$ factorisation of the data. The columns of $U$ are the eigenvectors of $XX^\top/N$, which is why this is also PCA. Conversely, when $\sigma_m \gt \sigma_{m+1}$, every optimum has $W_{\mathrm{dec}}W_{\mathrm{enc}} = U_mU_m^\top$, the projection onto the top-$m$ singular subspace. Baldi and Hornik showed that the error surface has no spurious local minima: every other critical point is a saddle, so gradient descent gets there.

The figure trains an untied linear autoencoder by plain gradient descent on a $6\times 40$ data matrix with 2 strong directions plus noise, with a code of size 2, and draws every matrix in the factorisation.

Three things to watch:

• The product converges to the SVD. The loss falls onto the Eckart–Young floor, and the last two maps become indistinguishable. In the margin, the angle between the decoder’s column space and the top singular subspace goes to zero. $\lVert W_{\mathrm{dec}}W_{\mathrm{enc}} - U_mU_m^\top\rVert$ falls toward zero more slowly, because the parts of the encoder that point along the weak noise directions get only weak gradients.
• The factors do not. Press draw again. The product ends up the same every time, but $W_{\mathrm{dec}}$ and $Z$ come out different. The margin shows $W_{\mathrm{dec}}$ in the SVD’s own basis, $U_m^\top W_{\mathrm{dec}}$. It is a rotation (or reflection), and a different one on each run. This is the subject of the next piece. Gradient descent from a small start keeps the encoder and decoder balanced, $W_{\mathrm{enc}}W_{\mathrm{enc}}^\top \approx W_{\mathrm{dec}}^\top W_{\mathrm{dec}}$, which is why the freedom left over is a rotation rather than an arbitrary invertible matrix.Du, Hu and Lee, Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced, NeurIPS 2018.
• Directions are learned one at a time. From a small start, the loss falls in steps: the strongest singular direction is learned first, and weaker ones later, at a pace set by their singular values.Saxe, McClelland and Ganguli, Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, ICLR 2014. Make the code wider than the number of strong directions, say $m = 4$ with 2 strong directions. Variance explained climbs past 98% almost at once, against a best possible of about 99.5%, but the angle in the margin stays large: the extra columns are left to pick out directions in the noise, which are weak and nearly tied, so they are learned slowly and are barely determined anyway.

Beyond linear

With nonlinear encoders and decoders, an autoencoder can follow curved structure that no single linear subspace captures: a spiral, or the manifold of images of handwritten digits. This is what made deep autoencoders useful for dimensionality reduction.

The figure trains a real one in your browser, on 16×16 images.The images, the network and the training loop come from the companion app autoencoders, where the same models can be tuned at length and scored on a hidden test set. The default images each show one dot at a random place, so two numbers, its $x$ and $y$, describe every image. The code has 2 numbers. The dashed line is PCA with the same number of components, the best any linear code can do.

Two things to try.

• Make it linear. Set the activation to linear. The network is then a product of matrices, a linear autoencoder, and it ends on PCA’s number: about 84% unexplained against PCA’s 83%. Depth does not help; a product of linear maps is still linear.
• Put the ReLUs back. The autoencoder leaves about 27% unexplained. PCA’s two components can only add two fixed images in proportion, which smears a dot across the frame. The nonlinear decoder can draw a dot at $(x, y)$. The gap is smaller on images with more kinds of variation (try Shapes or Digits), but it stays on the autoencoder’s side.

All of this concerns a code that is narrower than the input. The autoencoders used in interpretability go the other way: their code is many times wider than the input. Before getting there we need a problem that even the linear case already has. Next: which axes does the code actually use?