Chapter 12 · I.12

Problems

A chapter that uses mathematics has to teach that mathematics by making the reader compute. A chapter that only displays equations has failed, however correct the equations are.

M3Load-bearing

5/5 problems5/4 variants10/10 exercisesquota met, and enforced

The contract

5 worked problems, minimum.
4 distinct variants, and no variant more than half of them.
10 exercises, every one with a published solution.
At least one numeric problem — present.
At least one symbolic problem — present.
At least one limit or counterexample problem — present.
At least one complexity or shape problem — present.
At least one ▲▲▲ problem — present.

Numerical instantiationSymbolic derivationLimiting caseConstructed failureDimensional algebra

Problem I.12.B01

Keep one coordinate, then repair each half

numeric▲△△

Exact values where possible; six decimal places otherwise.

STATEMENT

Run a width-one linear autoencoder by hand on four points. Then improve the decoder alone, and after it the encoder alone, using their closed forms.

GIVEN

The data are $(1,2)$ , $(2.2,0.4)$ , $(-1,-2)$ and $(-2.2,-0.4)$ . They are centred, with

\begin{aligned} \mat S&=\begin{bmatrix}2.92&1.44\\1.44&2.08\end{bmatrix},\\ \operatorname{tr}\mat S&=5. \end{aligned}

The autoencoder starts at $\mat E=(1,\,0)$ and $\mat D=(1,\,0)^{\mathsf T}$ : it keeps the first coordinate and writes it back.

FIND

The four codes, the reconstructions and the loss. The best decoder for this encoder and its loss. The best encoder for that decoder and its loss. Where the sequence goes if the two repairs are alternated.

STRATEGY

Evaluate (I.12.1) directly, then apply the two lines of (I.12.3) in turn. After a decoder repair the loss is $\operatorname{tr}\mat S-\operatorname{tr}(\mat D\mat E\mat S)$ .

SOLUTION

The starting point. The codes are the first coordinates: $1$ , $2.2$ , $-1$ and $-2.2$ . Each reconstruction is $(z,0)$ , so each error is the square of the second coordinate: $4$ , $0.16$ , $4$ and $0.16$ . The loss is their mean, $2.08$ . That is $S_{22}$ , the variance of the coordinate that was dropped.

Repair the decoder. With $\mat E=(1,0)$ the code variance is $\mat E\mat S\mat E^{\mathsf T}=2.92$ and $\mat S\mat E^{\mathsf T}=(2.92,\,1.44)^{\mathsf T}$ . The first line of (I.12.3) gives

\begin{aligned} \mat D&=\frac{1}{2.92}\begin{bmatrix}2.92\\1.44\end{bmatrix}\\[2pt] &=\begin{bmatrix}1\\0.493151\end{bmatrix}. \end{aligned}

The decoder now predicts the second coordinate from the first by regression. The loss falls to

\begin{aligned} 5-\frac{2.92^2+1.44^2}{2.92} &=5-\frac{10.6}{2.92}\\ &=1.369863. \end{aligned}

Repair the encoder. For this decoder $\mat D^{\mathsf T}\mat D=1.243198$ , and the second line of (I.12.3) gives

\begin{aligned} \mat E&=\frac{\mat D^{\mathsf T}}{1.243198}\\ &=(0.804377,\;0.396679). \end{aligned}

The autoencoder is now the projection onto the direction of $\mat D$ . By (I.12.4) its loss is $5$ minus the variance along that direction, which is $1.101887$ .

Alternate. Two more repairs give $1.026137$ and $1.006577$ , and the sequence converges to $1$ .

The reason is visible in the two formulas. The decoder repair sets $\mat D$ proportional to $\mat S\mat E^{\mathsf T}$ , and the encoder repair sets $\mat E$ proportional to $\mat D^{\mathsf T}$ . One full sweep therefore multiplies the direction by $\mat S$ , which is the power method. The starting direction $(1,0)$ equals $0.8\,\vec u_1-0.6\,\vec u_2$ for the eigenvectors $\vec u_1=(0.8,0.6)$ and $\vec u_2=(-0.6,0.8)$ of $\mat S$ , with eigenvalues $4$ and $1$ . Each sweep divides the tangent of the angle to $\vec u_1$ by $4$ : it is $0.75$ , then $0.1875$ , then $0.046875$ . A projection at angle $\varphi$ to $\vec u_1$ has loss $1+3\sin^2\varphi$ , which reproduces $1.101887$ and $1.006577$ .

Answer

Codes $(1,\,2.2,\,-1,\,-2.2)$ and loss $2.08$ . Best decoder $(1,\,0.493151)^{\mathsf T}$ with loss $1.369863$ . Best encoder $(0.804377,\,0.396679)$ with loss $1.101887$ . Then $1.026137$ , $1.006577$ , and the limit $1$ , the smaller eigenvalue of $\mat S$ .

Check — sanity

The losses decrease at every step, because each repair is an exact minimisation over one matrix with the other held fixed. None falls below $1$ , the bound of I.12.T1.

Check — numeric · i-12-autoencoders-checks.py

The complete reproduction script uses only the Python standard library. From a checkout of the repository, run:

python3 scripts/snippets/i-12-autoencoders-checks.py

It checks all fifteen problems of the chapter and the numbers quoted in its four propositions. Its first line reports the losses above. Before that it confirms that $\mat S$ has eigenvalues $4$ and $1$ with the stated eigenvectors, and later that the gradients of (I.12.2) match central finite differences for untied and for tied weights.

Executed in CI. The digits above are the digits it printed.

Where this breaks

Start the encoder at $\vec u_2^{\mathsf T}=(-0.6,\,0.8)$ . Then $\mat S\mat E^{\mathsf T}$ is a multiple of $\vec u_2$ , the repaired decoder is $\vec u_2$ again, and the alternation never moves. The loss stays at $4$ . This is the saddle of I.12.T2, and an exact start on it is the only way to remain there.

Variation

Keep the second coordinate instead, $\mat E=(0,1)$ and $\mat D=(0,1)^{\mathsf T}$ . The loss is $S_{11}=2.92$ , worse than before because the first coordinate has the larger variance. One decoder repair gives $\mat D=(0.692308,\,1)^{\mathsf T}$ and a loss of $5-6.4/2.08=1.923077$ .

Problem I.12.B02

The minimum of a linear autoencoder, step by step

symbolic▲▲▲

Exact values where possible; six decimal places otherwise.

STATEMENT

Prove that the smallest loss of a linear autoencoder is the sum of the discarded eigenvalues, find every pair of matrices that attains it, and evaluate the result on four points.

GIVEN

Centred data with covariance $\mat S=\sum_{i=1}^d\lambda_i\vec u_i\vec u_i^{\mathsf T}$ , where $\lambda_1\geq\cdots\geq\lambda_d>0$ and the $\vec u_i$ are orthonormal. The loss is the first line of (I.12.2), with $\mat E\in\R^{k\times d}$ , $\mat D\in\R^{d\times k}$ and $k<d$ . Assume $\lambda_k>\lambda_{k+1}$ . For the numbers, use the four points of I.12.B01 with $k=1$ .

FIND

(a) The best encoder for a fixed decoder, and the end-to-end map it gives. (b) The loss of that map in terms of an orthonormal basis. (c) The lower bound and the condition for equality. (d) All minimising pairs. (e) The eigenvalues, the optimal map, its loss and two different factorisations for the four points. (f) The other stationary projection and a path that leaves it downhill.

STRATEGY

Reduce pairs of matrices to subspaces by solving for the encoder. Then write the retained variance as a weighted sum of eigenvalues and bound the weights.

SOLUTION

(a) Fix $\mat D$ with independent columns. For one input, the derivative of $\|\vec x-\mat D\vec z\|^2$ with respect to $\vec z$ is $-2\mat D^{\mathsf T}(\vec x-\mat D\vec z)$ . It vanishes at

\vec z=(\mat D^{\mathsf T}\mat D)^{-1}\mat D^{\mathsf T}\vec x,

which is the unique minimum because $\mat D^{\mathsf T}\mat D$ is positive definite. The same matrix serves every input, so $\mat E=(\mat D^{\mathsf T}\mat D)^{-1}\mat D^{\mathsf T}$ and

\mat D\mat E=\mat D(\mat D^{\mathsf T}\mat D)^{-1}\mat D^{\mathsf T}=\mat P.

Direct multiplication gives $\mat P^2=\mat P$ and $\mat P^{\mathsf T}=\mat P$ : the orthogonal projection onto the columns of $\mat D$ . No other encoder gives any input a better code, so no encoder has a smaller loss than $\mat P$ . Because $\lambda_d>0$ the data span every direction, and a different encoder gives some of them a strictly worse one.

(b) Choose $\mat Q\in\R^{d\times k}$ with orthonormal columns spanning the same subspace. Then $\mat P=\mat Q\mat Q^{\mathsf T}$ , and $\mat I-\mat P$ is symmetric with $(\mat I-\mat P)^2=\mat I-\mat P$ . Moving one factor around the trace,

\begin{aligned} \mathcal L(\mat P) &=\operatorname{tr}\big((\mat I-\mat P)\mat S(\mat I-\mat P)\big)\\ &=\operatorname{tr}\big(\mat S(\mat I-\mat P)\big)\\ &=\operatorname{tr}\mat S-\operatorname{tr}(\mat Q^{\mathsf T}\mat S\mat Q). \end{aligned}

This is (I.12.4).

(c) Substitute the eigendecomposition:

\begin{aligned} \operatorname{tr}(\mat Q^{\mathsf T}\mat S\mat Q) &=\sum_{i=1}^d\lambda_i c_i,\\ c_i&=\|\mat Q^{\mathsf T}\vec u_i\|^2. \end{aligned}

Since $\mat Q\mat Q^{\mathsf T}$ is a projection and $\vec u_i$ a unit vector, $0\leq c_i\leq1$ . Since the $\vec u_i$ are an orthonormal basis, $\sum_ic_i=\operatorname{tr}(\mat Q^{\mathsf T}\mat Q)=k$ . Therefore $\sum_{i\leq k}(1-c_i)=\sum_{i>k}c_i$ , and

\begin{aligned} &\sum_{i\leq k}\lambda_i-\sum_{i=1}^d\lambda_ic_i\\ &\;=\sum_{i\leq k}\lambda_i(1-c_i) -\sum_{i>k}\lambda_ic_i\\ &\;\geq\lambda_k\sum_{i\leq k}(1-c_i)\\ &\;\quad-\lambda_{k+1}\sum_{i>k}c_i\\ &\;=(\lambda_k-\lambda_{k+1})\sum_{i>k}c_i\\ &\;\geq0. \end{aligned}

So the retained variance is at most $\lambda_1+\cdots+\lambda_k$ , and

\mathcal L\geq\sum_{i>k}\lambda_i.

Because $\lambda_k>\lambda_{k+1}$ , equality requires $c_i=0$ for every $i>k$ , hence $c_i=1$ for every $i\leq k$ . A unit vector whose projection has length one lies in the subspace. The subspace is therefore the span of $\vec u_1,\ldots,\vec u_k$ , and $\mat P=\mat U_k\mat U_k^{\mathsf T}$ .

(d) A decoder attains the bound exactly when its columns span that subspace, that is, $\mat D=\mat U_k\mat G$ with $\mat G=\mat U_k^{\mathsf T}\mat D$ invertible. By (a) the encoder must then be

\begin{aligned} \mat E&=(\mat G^{\mathsf T}\mat G)^{-1}\mat G^{\mathsf T}\mat U_k^{\mathsf T}\\ &=\mat G^{-1}\mat U_k^{\mathsf T}. \end{aligned}

Every invertible $\mat G$ gives a minimiser, and these are all of them. This is (I.12.5).

A decoder of rank below $k$ spans fewer than $k$ dimensions. Its retained variance is at most $\lambda_1+\cdots+\lambda_{k-1}$ , which is strictly less because $\lambda_k>0$ .

(e) For the four points, $\mat S$ has trace $5$ and determinant $2.92\cdot2.08-1.44^2=4$ , so its eigenvalues solve $\lambda^2-5\lambda+4=0$ : they are $4$ and $1$ . Solving $(\mat S-4\mat I)\vec u=\vec 0$ gives $\vec u_1=(0.8,0.6)$ , and then $\vec u_2=(-0.6,0.8)$ . With $k=1$ ,

\begin{aligned} \mat D\mat E&=\vec u_1\vec u_1^{\mathsf T} =\begin{bmatrix}0.64&0.48\\0.48&0.36\end{bmatrix},\\ \mathcal L&=\lambda_2=1. \end{aligned}

For the point $(1,2)$ the code under $\mat G=1$ is $0.8+1.2=2$ , the reconstruction is $(1.6,1.2)$ and the residual is $(-0.6,0.8)$ , of squared length $1$ . The same holds at every corner.

Two factorisations of the same map: $\mat G=1$ gives $\mat D=(0.8,0.6)^{\mathsf T}$ and $\mat E=(0.8,\,0.6)$ . $\mat G=1/5$ gives $\mat D=(0.16,0.12)^{\mathsf T}$ and $\mat E=(4,\,3)$ .

(f) Setting $\mat D=\vec u_2$ and $\mat E=\vec u_2^{\mathsf T}$ makes both gradients of (I.12.2) vanish, with loss $\lambda_1=4$ . Rotate the direction to $\cos\theta\,\vec u_2+\sin\theta\,\vec u_1$ . By (b) the loss is $5-(\cos^2\theta+4\sin^2\theta)=4-3\sin^2\theta$ . At $\theta=0.1$ it is $3.970100$ . The point is stationary and is not a minimum.

Answer

The minimum is $\sum_{i>k}\lambda_i$ , attained exactly by $\mat D=\mat U_k\mat G$ , $\mat E=\mat G^{-1}\mat U_k^{\mathsf T}$ for invertible $\mat G$ . For the four points the eigenvalues are $4$ and $1$ , the optimal map is $\begin{bmatrix}0.64&0.48\\0.48&0.36\end{bmatrix}$ and the loss is $1$ . The projection onto $\vec u_2$ is a saddle with loss $4$ .

Check — sanity

The optimal map has trace $1$ , the dimension of the subspace, and squares to itself: its first entry is $0.64^2+0.48^2=0.64$ . The retained variance $4$ and the loss $1$ add to the total $5$ .

Where this breaks

With $\lambda_k=\lambda_{k+1}$ the last step fails: weight can move between the tied directions without changing the sum, and the optimal subspace is not unique (I.12.X05). With a zero eigenvalue the encoder is determined only on the directions in which the data vary. With uncentred data $\mat S$ is not a covariance and the subspace found is a different one (I.12.X03).

Variation

The script scans $3600$ directions and confirms that the loss of the projection onto each lies between $1$ and $4$ , the two eigenvalues. For $k=d$ the bound is an empty sum: the loss is $0$ and the map is the identity (I.12.X04).

Problem I.12.B03

How much noise, how much shrinkage

limit▲▲△

Exact values where possible; six decimal places otherwise.

STATEMENT

Find the linear map that best removes noise of variance $\sigma^2$ from four points, with and without a bottleneck, and follow it as the noise goes to zero and to infinity.

GIVEN

The four points of I.12.B01, with eigenvalues $\lambda=(4,1)$ and eigenvectors $\vec u_1=(0.8,0.6)$ , $\vec u_2=(-0.6,0.8)$ . The input is corrupted as $\tilde{\vec x}=\vec x+\vec\varepsilon$ , where $\vec\varepsilon$ is independent of $\vec x$ with mean zero and covariance $\sigma^2\mat I$ . The loss is $\E\|\mat M\tilde{\vec x}-\vec x\|^2$ .

FIND

(a) The optimal gain on each principal direction and the loss it leaves. (b) The optimal map and its loss at $\sigma^2=1$ . (c) The same when $\mat M$ must have rank one. (d) The limits $\sigma^2\to0$ and $\sigma^2\to\infty$ , with values at $\sigma^2=0.01$ and $100$ . (e) A check of (I.12.8) for Gaussian data.

STRATEGY

Use the decomposition in (I.12.7). The optimal map shares the eigenvectors of $\mat S$ , so the problem separates into one scalar problem per direction.

SOLUTION

(a) By (I.12.7) the loss is the clean reconstruction loss of $\mat M$ plus $\sigma^2\|\mat M\|_F^2$ , and its minimiser $\mat S(\mat S+\sigma^2\mat I)^{-1}$ has the eigenvectors of $\mat S$ . Write $\mat M=\sum_ig_i\vec u_i\vec u_i^{\mathsf T}$ . The loss becomes $\sum_i\big[(1-g_i)^2\lambda_i+\sigma^2g_i^2\big]$ . Each term is a parabola in its own $g_i$ , with derivative $-2(1-g_i)\lambda_i+2\sigma^2g_i$ :

\begin{aligned} g_i&=\frac{\lambda_i}{\lambda_i+\sigma^2},\\ \text{loss}_i&=\frac{\lambda_i\,\sigma^2}{\lambda_i+\sigma^2}. \end{aligned}

A direction is kept at exactly one half when the noise variance equals its own.

(b) At $\sigma^2=1$ the gains are $4/5$ and $1/2$ . The two projections are

\begin{aligned} \vec u_1\vec u_1^{\mathsf T}&=\begin{bmatrix}0.64&0.48\\0.48&0.36\end{bmatrix},\\[2pt] \vec u_2\vec u_2^{\mathsf T}&=\begin{bmatrix}0.36&-0.48\\-0.48&0.64\end{bmatrix}, \end{aligned}

\begin{aligned} \mat M^\star&=0.8\,\vec u_1\vec u_1^{\mathsf T}+0.5\,\vec u_2\vec u_2^{\mathsf T}\\[2pt] &=\begin{bmatrix}0.692&0.144\\0.144&0.608\end{bmatrix}. \end{aligned}

The loss is $4/5+1/2=1.3$ .

(c) A rank-one map keeps one direction. Keeping direction $i$ costs $\lambda_i\sigma^2/(\lambda_i+\sigma^2)$ there and the full $\lambda_j$ on the other. Keeping $\vec u_1$ costs $0.8+1=1.8$ ; keeping $\vec u_2$ costs $0.5+4=4.5$ . So the best rank-one map is $0.8\,\vec u_1\vec u_1^{\mathsf T}$ , with loss $1.8$ .

The bottleneck chooses the direction, as in I.12.T1. The noise then shrinks what is kept.

(d) As $\sigma^2\to0$ each gain tends to $1$ , the map tends to the identity and the loss to $0$ . Without noise, nothing stops the copy. As $\sigma^2\to\infty$ each gain behaves like $\lambda_i/\sigma^2$ and tends to $0$ ; the map outputs the mean, and the loss tends to $\operatorname{tr}\mat S=5$ .

$\sigma^2$	$0.01$	$1$	$100$
$g_1$	$0.997506$	$0.8$	$0.038462$
$g_2$	$0.990099$	$0.5$	$0.009901$
loss	$0.019876$	$1.3$	$4.836253$

(e) If $\vec x$ is Gaussian with mean zero and covariance $\mat S$ , then $\tilde{\vec x}$ is Gaussian with covariance $\mat S+\sigma^2\mat I$ and score $-(\mat S+\sigma^2\mat I)^{-1}\tilde{\vec x}$ . Then (I.12.8) gives

\begin{aligned} &\tilde{\vec x}-\sigma^2(\mat S+\sigma^2\mat I)^{-1}\tilde{\vec x}\\ &\;\;=\mat S(\mat S+\sigma^2\mat I)^{-1}\tilde{\vec x}, \end{aligned}

which is the map of (a). For Gaussian data the best denoiser is linear, and the two results are one.

Answer

Gains $\lambda_i/(\lambda_i+\sigma^2)$ with loss $\sum_i\lambda_i\sigma^2/(\lambda_i+\sigma^2)$ . At $\sigma^2=1$ : $\mat M^\star=\begin{bmatrix}0.692&0.144\\0.144&0.608\end{bmatrix}$ with loss $1.3$ , or $0.8\,\vec u_1\vec u_1^{\mathsf T}$ with loss $1.8$ at rank one. The map tends to the identity as $\sigma^2\to0$ and to zero as $\sigma^2\to\infty$ .

Check — sanity

At $\sigma^2=1$ , copying the corrupted input costs $\sigma^2\|\mat I\|_F^2=2$ and outputting the mean costs $\operatorname{tr}\mat S=5$ . The optimum, $1.3$ , is below both. Every gain lies strictly between $0$ and $1$ .

Where this breaks

Noise with a general covariance $\mat N$ gives $\mat S(\mat S+\mat N)^{-1}$ , which shares eigenvectors with $\mat S$ only if the two matrices commute. And for data that are not Gaussian the best denoiser is not linear at all: I.12.X08 finds a $\tanh$ .

Variation

At $\sigma^2=4$ the gains are $(0.5,\;0.2)$ and the loss is $2+0.8=2.8$ . The script also confirms the decomposition of (I.12.7) exactly, by averaging over the four points and four noise vectors $(\pm\sigma\sqrt2,0)$ , $(0,\pm\sigma\sqrt2)$ , whose covariance is $\sigma^2\mat I$ .

Problem I.12.B04

A width-one code that memorises

counterexample▲▲△

Exact values where possible; six decimal places otherwise.

STATEMENT

Show that a narrow code does not, by itself, stop an autoencoder from memorising its training set.

GIVEN

The training set is the four points $(1,2)$ , $(2.2,0.4)$ , $(-1,-2)$ and $(-2.2,-0.4)$ , the corners of a rectangle. The encoder keeps the first coordinate, $z=x_1$ . The decoder returns $g(z)=(z,\,g_2(z))$ . Its second output is piecewise linear, with $\operatorname{relu}(a)=\max(a,0)$ :

\begin{aligned} g_2(z)=&-\tfrac43z-\tfrac{10}3\\ &+\tfrac{10}3\operatorname{relu}(z+1)\\ &-\tfrac{10}3\operatorname{relu}(z-1). \end{aligned}

For comparison, the principal-axis autoencoder of I.12.B02 projects onto $\vec u_1=(0.8,0.6)$ . The held-out set is the midpoints of the rectangle’s four sides: $(-0.6,0.8)$ , $(0.6,-0.8)$ , $(1.6,1.2)$ and $(-1.6,-1.2)$ .

FIND

The training loss of both autoencoders, their mean error on the held-out points, the decoding of the code $z=5$ , and what went wrong.

STRATEGY

Write the decoder’s second coordinate on each of its three linear pieces. Then evaluate both models point by point.

SOLUTION

The decoder, piece by piece. The two ReLU terms switch on at $z=-1$ and $z=1$ , so the second output is

\begin{aligned} z\leq-1&:\quad g_2=-\tfrac43z-\tfrac{10}3,\\[2pt] |z|\leq1&:\quad g_2=2z,\\[2pt] z\geq1&:\quad g_2=-\tfrac43z+\tfrac{10}3. \end{aligned}

Training points. The codes are $1$ , $2.2$ , $-1$ and $-2.2$ , and $g_2$ returns $2$ , $0.4$ , $-2$ and $-0.4$ . Every training point is reconstructed exactly, so the training loss is $0$ . The principal axis gives each corner an error of $1$ , so its training loss is $1$ .

Held-out points. At $(-0.6,0.8)$ the code is $-0.6$ and the decoder returns $(-0.6,-1.2)$ : squared error $(0.8+1.2)^2=4$ . At $(0.6,-0.8)$ it returns $(0.6,1.2)$ : error $4$ again. At $(1.6,1.2)$ and $(-1.6,-1.2)$ it is exact. The mean is $2$ .

The principal axis gives the first two points the code $0$ and the reconstruction $(0,0)$ , with error $1$ each. The other two lie on the axis, with error $0$ . The mean is $0.5$ .

	training loss	held-out mean
width-one code, two ReLU kinks	$0$	$2$
principal axis	$1$	$0.5$

Away from the data. The code $5$ decodes to $(5,\,-\tfrac{20}3+\tfrac{10}3)=(5,\,-3.333333)$ . The training codes lie between $-2.2$ and $2.2$ ; nothing constrained the decoder beyond them.

What went wrong. The reconstruction surface is a zigzag through the corners in order of their first coordinate: $(-2.2,-0.4)\to(-1,-2)\to(1,2)\to(2.2,0.4)$ . Its middle piece crosses the rectangle from one corner to the opposite one. The code is one number, as narrow as a code can be, and the surface is one-dimensional as it must be. But a curve with two kinks has three straight pieces, enough to meet four points. The bottleneck bounded the dimension of the surface and left its shape free.

Answer

Training loss $0$ against $1$ . Held-out mean error $2$ against $0.5$ , with $4$ against $1$ at $(-0.6,0.8)$ . The code $5$ decodes to $(5,-3.333333)$ . The decoder had enough freedom to pass through every training point.

Check — sanity

The decoder is continuous: at $z=-1$ both neighbouring pieces give $-2$ , and at $z=1$ both give $2$ . Its first output is the code itself, so only the second coordinate can be wrong.

Where this breaks

The construction needs the training points to have distinct codes. Two inputs that share a code share a reconstruction, whatever the decoder, so they cannot both be memorised. A curve with $n-2$ kinks passes through $n$ points with distinct codes; with more training points than that, the same decoder can no longer fit them all.

Variation

Add the four midpoints to the training set. The zigzag now has a loss of $1$ on the eight points, since it errs by $4$ on two of them, while the principal axis has $0.75$ . More data repaired what a narrower code could not.

Problem I.12.B05

Count the code before calling it a bottleneck

shape▲▲△

Exact integers.

STATEMENT

Track shapes and parameters through a dense and a convolutional autoencoder for the same image, and find the two places where the convolutional one goes wrong.

GIVEN

One input is a $1\times28\times28$ image, $784$ numbers.

The dense autoencoder has layer widths $784$ , $128$ , $32$ , $128$ , $784$ , with a bias on every layer.

The convolutional encoder is two layers with $3\times3$ kernels, stride $2$ and padding $1$ , taking $1$ channel to $8$ and then $8$ to $16$ . The decoder is two transposed convolutions with the same kernel, stride and padding, taking $16$ channels to $8$ and then $8$ to $1$ . All four layers have biases.

FIND

(a) The dense parameter count, untied and with tied weights. (b) The spatial sizes through the convolutional encoder, and how many numbers its code holds. (c) The decoder’s output size with output padding $0$ and with $1$ . (d) The convolutional parameter count. (e) The code channel counts for which the convolutional code is narrower than its input.

STRATEGY

Count each dense layer as inputs times outputs plus outputs. Use (I.11.4) for the encoder’s sizes and (I.11.5) for the decoder’s.

SOLUTION

(a) The four dense layers hold

\begin{aligned} 784\cdot128+128&=100{,}480,\\ 128\cdot32+32&=4{,}128,\\ 32\cdot128+128&=4{,}224,\\ 128\cdot784+784&=101{,}136, \end{aligned}

for a total of $209{,}968$ . With tied weights the two decoder matrices are transposes of the encoder’s. The weights are then $100{,}352+4{,}096=104{,}448$ and the four bias vectors add $1{,}072$ , for $105{,}520$ . The code is $32$ numbers, $24.5$ times fewer than the input.

(b) By (I.11.4), with no dilation,

\begin{aligned} \left\lfloor\frac{28+2-3}{2}\right\rfloor+1&=14,\\[2pt] \left\lfloor\frac{14+2-3}{2}\right\rfloor+1&=7. \end{aligned}

The code has shape $16\times7\times7$ and holds $784$ numbers, exactly as many as the input. This is the first fault. Each layer halved the height and the width and the picture looks like an hourglass, but the channel count grew as fast as the grid shrank. By count, nothing forces this code to discard anything.

(c) By (I.11.5) a transposed layer returns $(n-1)\cdot2-2+2+o+1=2n-1+o$ for output padding $o$ . With $o=0$ the sizes run $7\to13\to25$ . The reconstruction is $25\times25$ , with $625$ numbers, and cannot be compared with a $28\times28$ target. This is the second fault. With $o=1$ they run $7\to14\to28$ .

The ambiguity is real. Under the encoder’s stride-two layer an input of size $27$ and one of size $28$ both give $14$ . The transposed layer cannot know which it is undoing, and output padding tells it.

(d) A transposed convolution stores its weight with shape $(C_{\mathrm{in}},C_{\mathrm{out}},k_h,k_w)$ and one bias per output channel. The four layers hold

\begin{aligned} 8\cdot1\cdot9+8&=80,\\ 16\cdot8\cdot9+16&=1{,}168,\\ 16\cdot8\cdot9+8&=1{,}160,\\ 8\cdot1\cdot9+1&=73, \end{aligned}

a total of $2{,}481$ , against $209{,}968$ for the dense stack.

(e) A code of $C$ channels on the $7\times7$ grid holds $49C$ numbers. It is narrower than the input when $49C<784$ , that is, $C<16$ . With $C=4$ the code holds $196$ numbers, a quarter of the input.

Answer

(a) $209{,}968$ untied and $105{,}520$ tied. (b) $28\to14\to7$ ; the code holds $784$ numbers. (c) $7\to13\to25$ without output padding and $7\to14\to28$ with it. (d) $2{,}481$ . (e) Fewer than $16$ code channels.

Check — sanity

The tied count is half the untied weights plus all the biases: $208{,}896/2+1{,}072=105{,}520$ . The transposed sizes $14$ and $28$ are the encoder’s sizes read backwards.

Where this breaks

A count of numbers is a necessary check and not a sufficient one. A code with fewer numbers than the input can still memorise (I.12.B04), and shared, local weights restrict a convolutional autoencoder in ways the count does not show. The count catches only the case where no restriction was imposed at all.

Variation

With $4\times4$ kernels, stride $2$ and padding $1$ , the encoder still gives $\lfloor(28+2-4)/2\rfloor+1=14$ , and the transposed layer returns $(7-1)\cdot2-2+3+0+1=14$ with no output padding. An even input size is then recovered without the extra argument.

Exercises

Every one has a published solution. A hidden solution is a solution; a missing one is an abandonment.

I.12.X01A code has no unitsnumeric▲△△

A width-one linear autoencoder has $\mat E=(0.8,\,0.6)$ and $\mat D=(0.8,\,0.6)^{\mathsf T}$ . Encode and reconstruct the new input $(2,-1)$ , and find its squared error. Repeat with $\mat E'=(4,\,3)$ and $\mat D'=(0.16,\,0.12)^{\mathsf T}$ . What do the two codes have in common, and what do they not?

Hint

Compute $\mat D\mat E$ and $\mat D'\mat E'$ before computing anything else.

Solution

The code is $0.8\cdot2+0.6\cdot(-1)=1$ . The reconstruction is $(0.8,\,0.6)$ and the residual is $(1.2,\,-1.6)$ , with squared length $1.44+2.56=4$ .

With the second pair the code is $4\cdot2+3\cdot(-1)=5$ , and the reconstruction is $(0.16\cdot5,\;0.12\cdot5)=(0.8,\,0.6)$ again. Both products equal

\begin{bmatrix}0.64&0.48\\0.48&0.36\end{bmatrix},

so the two autoencoders are the same function of the input and have the same loss on every dataset. They are the cases $\mat G=1$ and $\mat G=1/5$ of (I.12.5).

The codes share their ordering and their ratios: one is five times the other for every input. They do not share a scale. A code’s magnitude, and with more than one code unit its axes and the angles between them, are set by the factorisation that training happened to reach and not by the data.

The input $(2,-1)$ is $\vec u_1-2\vec u_2$ in the eigenvectors $\vec u_1=(0.8,0.6)$ and $\vec u_2=(-0.6,0.8)$ . The error $4$ is the square of its discarded component.

I.12.X02The encoder waits for the decodergradient▲△△

For the four points of I.12.B01, $\mat S=\begin{bmatrix}2.92&1.44\\1.44&2.08\end{bmatrix}$ . At $\mat E=(1,\,0)$ and $\mat D=(1,\,0)^{\mathsf T}$ , evaluate both gradients of (I.12.2). Take one step of gradient descent with step size $0.1$ and find the new loss. Then evaluate both gradients at $\mat E=\mat 0$ , $\mat D=\mat 0$ .

Hint

Form $(\mat I-\mat D\mat E)\mat S$ once and use it in both gradients.

Solution

Here $\mat I-\mat D\mat E=\begin{bmatrix}0&0\\0&1\end{bmatrix}$ , so

(\mat I-\mat D\mat E)\mat S=\begin{bmatrix}0&0\\1.44&2.08\end{bmatrix}.

Multiplying on the right by $\mat E^{\mathsf T}=(1,0)^{\mathsf T}$ and on the left by $\mat D^{\mathsf T}=(1,\,0)$ :

\begin{aligned} \nabla_{\mat D}\mathcal L&=-2\begin{bmatrix}0\\1.44\end{bmatrix} =\begin{bmatrix}0\\-2.88\end{bmatrix},\\ \nabla_{\mat E}\mathcal L&=-2\,(0,\;0)=(0,\;0). \end{aligned}

The decoder is told to raise its second weight: the residual, which lives in the second coordinate, is correlated with the code. The encoder is told nothing. Its gradient passes through $\mat D^{\mathsf T}$ , and the decoder does not yet write to the coordinate where the error is.

After the step, $\mat D=(1,\,0.288)^{\mathsf T}$ and $\mat E$ is unchanged. The residual map is $\begin{bmatrix}0&0\\-0.288&1\end{bmatrix}$ and the loss is

\begin{aligned} &0.288^2\cdot2.92-2\cdot0.288\cdot1.44+2.08\\ &\;\;=1.492756, \end{aligned}

down from $2.08$ . On the next step the encoder’s gradient is no longer zero.

At $\mat E=\mat 0$ and $\mat D=\mat 0$ , each gradient has a zero matrix as a factor, so both vanish. The loss is $\operatorname{tr}\mat S=5$ and gradient descent never leaves. An autoencoder needs a nonzero initialisation in both halves.

I.12.X04As wide as the input, and nothing learnedcounterexample▲△△

A linear autoencoder with $d=k=2$ has

\mat E=\begin{bmatrix}2&1\\1&1\end{bmatrix},\qquad \mat D=\begin{bmatrix}1&-1\\-1&2\end{bmatrix}.

Find its loss on the four points of I.12.B01, the code of $(1,2)$ , and its reconstruction of $(100,-7)$ , a point nowhere near the data. What has it learned about the data?

Hint

Multiply $\mat D\mat E$ .

Solution

The product is

\mat D\mat E=\begin{bmatrix}2-1&1-1\\-2+2&-1+2\end{bmatrix} =\begin{bmatrix}1&0\\0&1\end{bmatrix}.

Every input is reconstructed exactly, so the loss is $0$ on the four points and on any other dataset. The code of $(1,2)$ is $(2+2,\;1+2)=(4,3)$ , and $(100,-7)$ is returned as $(100,-7)$ .

It has learned nothing about the data. The loss is at its smallest possible value, yet the same pair of matrices would have been optimal for any four points. Any invertible $\mat E$ with $\mat D=\mat E^{-1}$ does the same, a family with four free numbers.

The code is the input in another basis. A linear classifier on the code can do exactly what it could do on the input, no more and no less.

This is the case $k=d$ of (I.12.5): the sum of discarded eigenvalues is empty. A reconstruction loss of zero is evidence that an autoencoder compresses only when something prevents this solution.

I.12.X03Centre the data, or the code spends itself on the meannumeric▲▲△

Three inputs are $(10,-1)$ , $(10,0)$ and $(10,1)$ . A width-one linear autoencoder without biases is trained on them as they are. Find the direction it keeps, the three codes and the loss. Then subtract the mean first and repeat. Which result is the principal subspace?

Hint

Without centring, the matrix in (I.12.2) is the second-moment matrix $\frac1n\mat X^{\mathsf T}\mat X$ and not the covariance. Apply I.12.T1 to whichever matrix the loss contains.

Solution

As they are. The second-moment matrix is

\frac13\mat X^{\mathsf T}\mat X =\begin{bmatrix}100&0\\0&2/3\end{bmatrix}.

The algebra of I.12.T1 applies to this matrix. Its largest eigenvalue is $100$ , with eigenvector $(1,0)$ , so the autoencoder keeps the first coordinate. All three codes are $10$ . Every input is reconstructed as $(10,0)$ and the loss is the other eigenvalue, $2/3=0.666667$ .

The code is the same number for every example. It carries no information about which example it came from.

Centred. The mean is $(10,0)$ , and the centred inputs are $(0,-1)$ , $(0,0)$ and $(0,1)$ . The covariance is $\begin{bmatrix}0&0\\0&2/3\end{bmatrix}$ . Its largest eigenvalue is $2/3$ , with eigenvector $(0,1)$ . The codes are $-1$ , $0$ and $1$ , and the loss is the other eigenvalue, $0$ .

The second result is the principal subspace: the direction along which the data vary. The first is the direction in which the data are large. The two matrices differ by $\vec\mu\vec\mu^{\mathsf T}$ for the mean $\vec\mu$ , and when the mean is long compared with the spread, that term dominates and the leading direction is close to $\vec\mu$ itself.

An autoencoder with a bias in the decoder can learn the mean and escape this. Without one, centre the data first.

I.12.X05A flat spectrum cannot be compressedlimit▲▲△

A covariance in eight dimensions has eigenvalues $\lambda_i=2^{8-i}$ , that is, $128,64,\ldots,2,1$ .

(a) Find the loss of the best width- $k$ linear autoencoder for $k=1,2,4,7$ , and the fraction of the total variance each leaves unexplained.

(b) Find the smallest $k$ that leaves under one per cent.

(d) For $\lambda_i=\rho^{\,i-1}$ with $0<\rho<1$ and $d\to\infty$ , find the unexplained fraction as a function of $k$ . What happens as $\rho\to1$ ?

(e) In the flat case, which subspace is optimal?

Hint

By (I.12.5) the loss is the sum of the eigenvalues after the $k$ -th. Both spectra are geometric series.

Solution

(a) The total is $2^8-1=255$ , and $\sum_{i>k}2^{8-i}=2^{8-k}-1$ .

$k$	loss	fraction unexplained
$1$	$127$	$0.498039$
$2$	$63$	$0.247059$
$4$	$15$	$0.058824$
$7$	$1$	$0.003922$

Each extra code unit roughly halves what is left.

(b) At $k=6$ the loss is $3$ and the fraction is $3/255=0.011765$ , just over. At $k=7$ it is $0.003922$ . So $k=7$ .

(c) With every eigenvalue equal to $1$ the loss is $8-k$ and the fraction is $1-k/8$ . It is under one per cent only at $k=8$ , where the code is as wide as the input. Nothing can be compressed.

(d) The tail is $\sum_{i>k}\rho^{\,i-1}=\rho^k/(1-\rho)$ and the total is $1/(1-\rho)$ , so the unexplained fraction is exactly $\rho^k$ . Each code unit removes the fraction $1-\rho$ of what remains. To reach a fraction $\epsilon$ needs $k=\ln\epsilon/\ln\rho$ , which grows like $\ln(1/\epsilon)/(1-\rho)$ as $\rho\to1$ . A spectrum that decays slowly needs a wide code, and in the limit of no decay no finite width suffices.

(e) Every one. In the proof of I.12.T1 the retained variance is $\sum_i\lambda_ic_i$ with weights that total $k$ . When all $\lambda_i$ are equal this is $k$ whatever the weights, so every $k$ -dimensional subspace has the same loss. The uniqueness in I.12.T1 required $\lambda_k>\lambda_{k+1}$ , and here that fails at every $k$ . Training will return some subspace, fixed by the initialisation and not by the data.

A linear code compresses exactly to the extent that the spectrum is uneven. Isotropic noise has a flat spectrum, and no linear code compresses it.

I.12.X07A penalty on the code can be scaled awaycounterexample▲▲△

On the four points of I.12.B01, a width-one linear autoencoder has $\mat E=(0.8,\,0.6)/c$ and $\mat D=c\,(0.8,\,0.6)^{\mathsf T}$ for a constant $c>0$ . Its objective is the reconstruction loss plus $\beta$ times the mean of $|z|$ over the data, with $\beta=0.5$ .

(a) Evaluate the objective at $c=1$ , $10$ and $1000$ . What is its infimum, and is it attained?

(b) Now hold the decoder at $(0.8,\,0.6)^{\mathsf T}$ and let each input take whichever code is best for it. Find that code for a corner of the rectangle, and the objective.

Hint

Each corner has a score of $\pm2$ along $(0.8,0.6)$ and $\pm1$ along $(-0.6,0.8)$ . Use (I.12.9) for (b).

Solution

(a) The product $\mat D\mat E$ does not depend on $c$ . It is the projection onto $(0.8,0.6)$ , with reconstruction loss $1$ . The codes are $\pm2/c$ , with mean absolute value $2/c$ . So the objective is

1+\frac{0.5\cdot2}{c}=1+\frac1c,

which is $2$ , $1.1$ and $1.001$ at the three values of $c$ .

Its infimum is $1$ , the unpenalised loss, and no finite $c$ attains it. Along the way the encoder shrinks towards zero and the decoder grows without bound. Nothing about the function computed has changed. The penalty has selected for large decoder weights and done nothing else.

(b) With a unit-norm decoder the error of one input splits along the two eigenvectors. For a corner with scores $a=\pm2$ and $b=\pm1$ , a code $z$ gives

(a-z)^2+b^2+\beta|z|.

By (I.12.9) the best code is $\operatorname{sign}(a)\,(|a|-\beta/2)=\pm1.75$ . The objective is

0.25^2+1+0.5\cdot1.75=1.9375,

against $2$ for the unshortened code $\pm2$ . The penalty now trades something real: codes an eighth shorter, and a reconstruction error of $1.0625$ where it was $1$ .

(c) The code is zero when $\beta/2\geq|a|=2$ , that is, $\beta\geq4$ . The unit is then never active, the reconstruction is the origin for every input, and the reconstruction loss is the total variance, $5$ .

The fix. Hold each decoder column at unit norm, or weight $|z_j|$ by the norm of its column, so that the product of the two scales is what is penalised. A penalty on the encoder’s Jacobian has the same weakness, and tied weights remove it there.

I.12.X08The best denoiser returns a conditional meanprobability▲▲△

A scalar input is $+1$ or $-1$ with probability one half each. It is corrupted to $\tilde x=x+\varepsilon$ with $\varepsilon$ drawn from $\mathcal N(0,\sigma^2)$ .

(a) Find the best denoiser under squared error, $\E[x\mid\tilde x]$ .

(b) Evaluate it at $\tilde x=0.5$ for $\sigma^2=1$ and for $\sigma^2=0.25$ , and at $\tilde x=0$ .

(d) The output at $\tilde x=0$ is not a possible input. What does that say about reconstructions trained with squared error?

Hint

Use Bayes’ rule (Bayes' rule 0.PR.04) for the two posterior probabilities. The Gaussian normalising constants cancel in their ratio.

Solution

(a) The two likelihoods are proportional to $e^{-(\tilde x-1)^2/2\sigma^2}$ and $e^{-(\tilde x+1)^2/2\sigma^2}$ , and the priors are equal. Their ratio is $e^{2\tilde x/\sigma^2}$ , so the posterior probabilities are

p_\pm=\frac{e^{\pm\tilde x/\sigma^2}} {e^{\tilde x/\sigma^2}+e^{-\tilde x/\sigma^2}}.

The conditional mean is $p_+-p_-$ :

\E[x\mid\tilde x]=\tanh\!\big(\tilde x/\sigma^2\big).

(b) At $\tilde x=0.5$ : $\tanh(0.5)=0.462117$ for $\sigma^2=1$ and $\tanh(2)=0.964028$ for $\sigma^2=0.25$ . At $\tilde x=0$ it is $0$ for any $\sigma^2$ .

With less noise the same observation is stronger evidence, and the denoiser commits to the nearer input. As $\sigma^2\to0$ it becomes the sign of $\tilde x$ . As $\sigma^2\to\infty$ it flattens to the prior mean, $0$ .

(c) The noised density is proportional to the sum of the two likelihoods. Differentiating its logarithm,

\begin{aligned} &\frac{d}{d\tilde x}\log p_\sigma(\tilde x)\\ &\;\;=\frac{-(\tilde x-1)\,p_+-(\tilde x+1)\,p_-}{\sigma^2}\\ &\;\;=\frac{\tanh(\tilde x/\sigma^2)-\tilde x}{\sigma^2}. \end{aligned}

So $\tilde x+\sigma^2$ times the score is $\tanh(\tilde x/\sigma^2)$ , as (I.12.8) requires. The displacement of the denoiser points towards the nearer of the two inputs, where the noised density is higher. The script checks this with a numerical derivative at all three points of (b).

(d) At $\tilde x=0$ the two inputs are equally likely. The value that minimises the expected squared error is their mean, $0$ , even though the input is never $0$ . Squared error rewards the average of the plausible answers and not any one of them.

For images, the average of several sharp reconstructions that differ slightly is a blurred one. An autoencoder trained with squared error on inputs it cannot resolve returns that average. More training does not sharpen it, because the average is the optimum.

I.12.X10An anomaly on the surface scores zerocounterexample▲▲△

The best width-one linear autoencoder for the four points $(1,2)$ , $(2.2,0.4)$ , $(-1,-2)$ and $(-2.2,-0.4)$ projects onto $\vec u_1=(0.8,0.6)$ . Its squared reconstruction error is used as an anomaly score, and any input scoring above $1.5$ is flagged.

(a) Find the scores of the four training points.

(b) Find the scores of $(8,6)$ and of $(-1.2,1.6)$ , and the distance from each to its nearest training point.

(d) What does the score measure, and what would be needed to flag the other one?

Hint

Write each new point in the eigenvectors $\vec u_1=(0.8,0.6)$ and $\vec u_2=(-0.6,0.8)$ . The score is the square of the $\vec u_2$ component.

Solution

(a) Each training point has a component of $\pm1$ along $\vec u_2$ , so every score is $1$ . The threshold of $1.5$ passes all of them.

(b) The point $(8,6)$ is $10\,\vec u_1$ . It lies on the principal axis and its score is $0$ . Its nearest training points are $(1,2)$ and $(2.2,0.4)$ , each at distance $\sqrt{65}=8.062258$ .

The point $(-1.2,1.6)$ is $2\,\vec u_2$ . Its score is $4$ . Its nearest training points are $(1,2)$ and $(-2.2,-0.4)$ , each at distance $\sqrt5=2.236068$ .

(c) Only $(-1.2,1.6)$ is flagged. The point $(8,6)$ passes with the lowest score of any input seen so far, lower than every training point, though it is more than three times as far from the data as the point that was flagged.

(d) The score is the squared distance from the reconstruction surface, here a line. It says nothing about where along the line an input falls. The line extends without end, and the data occupy a short stretch of it.

To flag $(8,6)$ one must know which codes are usual. Its code is $10$ , where the training codes are $\pm2$ . Reconstruction error does not look at the code, and (I.12.1) defines no distribution over codes against which $10$ could be judged improbable. A threshold on the size of the code would catch this case and would be a second detector, added by hand.

The failure grows with the quality of the model. A decoder that generalises well reconstructs inputs it was never shown, and each of them scores as normal.

I.12.X06Weight decay fixes the axessymbolic▲▲▲

Add the penalty $\gamma(\|\mat E\|_F^2+\|\mat D\|_F^2)$ , with $\gamma>0$ , to the loss of (I.12.2).

(a) Write the two stationarity conditions and prove that $\mat D^{\mathsf T}\mat D=\mat E\mat E^{\mathsf T}$ at every stationary point.

(b) Let $\mat D=\mat U_k\mat C$ and $\mat E=\mat D^{\mathsf T}$ with $\mat C=\operatorname{diag}(c_1,\ldots,c_k)$ . Show that this pair is stationary when $c_i^2=1-\gamma/\lambda_i$ , and find the end-to-end map.

(c) For the four points, with $k=2$ and $\gamma=0.5$ , find the gains, the decoder and the value of the objective. Compare it with the identity.

(d) Explain why the principal axes can be read from this decoder and not from an unpenalised one.

(e) What happens to a direction with $\lambda_i\leq\gamma$ ?

Hint

For (b), use $\mat S\mat U_k=\mat U_k\mat\Lambda_k$ and $\mat U_k^{\mathsf T}\mat U_k=\mat I$ , where $\mat\Lambda_k=\operatorname{diag}(\lambda_1,\ldots,\lambda_k)$ .

Solution

(a) The penalty adds $2\gamma\mat D$ and $2\gamma\mat E$ to the gradients of (I.12.2). Setting both to zero:

\begin{aligned} (\mat I-\mat D\mat E)\,\mat S\,\mat E^{\mathsf T}&=\gamma\mat D,\\ \mat D^{\mathsf T}(\mat I-\mat D\mat E)\,\mat S&=\gamma\mat E. \end{aligned}

Multiply the first on the left by $\mat D^{\mathsf T}$ and the second on the right by $\mat E^{\mathsf T}$ . Both left-hand sides become $\mat D^{\mathsf T}(\mat I-\mat D\mat E)\mat S\mat E^{\mathsf T}$ , so $\gamma\mat D^{\mathsf T}\mat D=\gamma\mat E\mat E^{\mathsf T}$ . Divide by $\gamma$ .

(b) Here $\mat D\mat E=\mat U_k\mat C^2\mat U_k^{\mathsf T}$ . Using the hint,

\begin{aligned} &(\mat I-\mat D\mat E)\,\mat S\,\mat E^{\mathsf T}\\ &\;\;=(\mat I-\mat U_k\mat C^2\mat U_k^{\mathsf T})\,\mat U_k\mat\Lambda_k\mat C\\ &\;\;=\mat U_k(\mat I-\mat C^2)\mat\Lambda_k\mat C. \end{aligned}

This equals $\gamma\mat D=\gamma\mat U_k\mat C$ when $(1-c_i^2)\lambda_i=\gamma$ for every $i$ , that is, $c_i^2=1-\gamma/\lambda_i$ . Since $\mat D\mat E$ and $\mat S$ are both symmetric and share eigenvectors, they commute, and the second condition is the transpose of the first. The end-to-end map is

\mat D\mat E=\mat U_k\operatorname{diag}(1-\gamma/\lambda_i)\, \mat U_k^{\mathsf T}.

Replacing $\mat D$ by $\mat D\mat O^{\mathsf T}$ and $\mat E$ by $\mat O\mat E$ for an orthogonal $\mat O$ changes neither condition nor either norm. That gives the family (I.12.6).

(c) The gains are $1-0.5/4=0.875$ and $1-0.5/1=0.5$ , so $c=(0.935414,\;0.707107)$ . The decoder’s columns are

\begin{aligned} 0.935414\begin{bmatrix}0.8\\0.6\end{bmatrix} &=\begin{bmatrix}0.748331\\0.561249\end{bmatrix},\\[2pt] 0.707107\begin{bmatrix}-0.6\\0.8\end{bmatrix} &=\begin{bmatrix}-0.424264\\0.565685\end{bmatrix}. \end{aligned}

The reconstruction term is $\sum_i(1-g_i)^2\lambda_i=0.0625+0.25=0.3125$ . The penalty is $\gamma\cdot2\sum_ic_i^2=0.5\cdot2\cdot1.375=1.375$ . The objective is $1.6875$ . The identity, $\mat E=\mat D=\mat I$ , reconstructs exactly and pays $0.5\cdot4=2$ . With weight decay, copying is no longer the best answer even at full width.

(d) The expression $\mat D=\mat U_k\mat C\mat O^{\mathsf T}$ is a singular value decomposition of the decoder: left singular vectors $\vec u_i$ , singular values $c_i$ . When the $\lambda_i$ are distinct, so are the $c_i$ , and the left singular vectors are determined up to sign and come out in order of $\lambda_i$ . The unknown rotation $\mat O$ sits on the right and does not disturb them.

Without the penalty the decoder is $\mat U_k\mat G$ for an arbitrary invertible $\mat G$ . Its left singular vectors are $\mat U_k$ times those of $\mat G$ , which can be any orthonormal basis of the subspace.

(e) In this family the contribution of one direction to the objective is $(1-c^2)^2\lambda+2\gamma c^2$ . Its derivative with respect to $c^2$ is $-2(1-c^2)\lambda+2\gamma$ , which is non-negative for all $c^2\geq0$ when $\lambda\leq\gamma$ . The best choice is then $c=0$ : the direction is not learned at all. Weight decay sets a floor on the variance a direction needs before it is worth representing.

For the four points with $\gamma=1$ , the second direction has $\lambda_2=\gamma$ and is dropped. The first has gain $0.75$ , the decoder is $\sqrt{0.75}\,\vec u_1=(0.692820,\;0.519615)$ , and the objective is $0.25+1+1.5=2.75$ .

The script checks the stationarity of (c) to machine precision, confirms that sixteen small perturbations all raise the objective, and confirms that rotating the code leaves it unchanged.

I.12.X09A circle does not pass through a width-one codeproof▲▲▲

The data are the unit circle in the plane, and the code has width one.

(a) Prove that every continuous encoder gives some pair of antipodal points the same code.

(b) Deduce that, whatever the decoder, some point of the circle is reconstructed at distance at least $1$ from itself.

(c) Encoding a point by its angle in $(-\pi,\pi]$ and decoding $z$ to $(\cos z,\sin z)$ reconstructs every point exactly. Why does this not contradict (b)? For the inputs at $+175^\circ$ and $-175^\circ$ , find the distance between them, the distance between their codes, and the distance from either to the decoding of the code halfway between.

(d) How wide a code allows an autoencoder for the circle that is both continuous and exact?

Hint

Write the encoder as a function $F$ of the angle and study $h(\theta)=F(\theta)-F(\theta+\pi)$ .

Solution

(a) Let $F(\theta)$ be the code of the point at angle $\theta$ . It is continuous, and $F(\theta+2\pi)=F(\theta)$ because the two angles name one point. Define $h(\theta)=F(\theta)-F(\theta+\pi)$ . Then

\begin{aligned} h(\theta+\pi)&=F(\theta+\pi)-F(\theta+2\pi)\\ &=-h(\theta). \end{aligned}

If $h(0)=0$ the points at angles $0$ and $\pi$ share a code. Otherwise $h(0)$ and $h(\pi)$ have opposite signs, and by the intermediate value theorem $h(\theta^\star)=0$ for some $\theta^\star$ between them. The points at $\theta^\star$ and $\theta^\star+\pi$ are antipodal and share a code. $\blacksquare$

(b) Call those points $\vec p$ and $-\vec p$ . A decoder sees one code, so it returns one point $\vec a$ for both. By the triangle inequality,

\begin{aligned} &\|\vec a-\vec p\|+\|\vec a+\vec p\|\\ &\;\;\geq\|(\vec a+\vec p)-(\vec a-\vec p)\|\\ &\;\;=2\|\vec p\|=2. \end{aligned}

The larger of the two distances is at least $1$ . $\blacksquare$

(c) The angle is not a continuous function on the circle. Crossing the negative horizontal axis, it jumps from $\pi$ to $-\pi$ . Part (a) needed continuity and does not apply.

The two inputs are $10^\circ$ apart on the circle, at distance $2\sin5^\circ=0.174311$ . Their codes are $\pm3.054326$ , which are $6.108652$ apart. The code halfway between is $0$ , which decodes to $(1,0)$ , the point $175^\circ$ around from either input and at distance $2\sin87.5^\circ=1.998096$ from it.

The exact autoencoder has put two neighbours at opposite ends of its code and the far side of the circle between them.

(d) Width two. Take the encoder and the decoder to be the identity on the plane. Both are continuous and every point of the circle is reconstructed exactly.

The circle has one degree of freedom and needs two code numbers. A closed curve cannot be laid along a line without cutting it somewhere, and (a) and (b) are that fact stated for encoders. The width a code needs depends on the shape of the data as well as on its dimension.

As a check, the script takes $F(\theta)=\cos\theta+0.3\sin2\theta+0.2\sin\theta$ , for which $h(\theta)=2\cos\theta+0.4\sin\theta$ , and finds the shared code by bisection at $\theta^\star=\pi-\arctan5=1.768192$ .