The Week 6 tutorial, made interactive. Each question starts with the one idea from the lectures you need, then walks to the official answer in small steps.
State some relations between autoencoders and PCA.
An autoencoder squeezes through a bottleneck with , then reconstructs it: encoder , decoder , often with tied weights .
The slide on data compression states the link outright: special case — , linear and mean squared error: reduces to Principal Component Analysis.
Claim. Let the columns of be centred. Consider a -unit autoencoder with linear encoder and linear decoder , trained under mean squared error: Every minimiser satisfies , the orthogonal projector onto the first principal components of . The reconstructions therefore lie in the PCA subspace of dimension . The hidden basis need not be the principal axes: any invertible gives the same reconstructions.
The argument has four steps. A fifth step shows that linearity is necessary. The figure and the scatter plot above follow the current step.
Questions 2, 3 and 4 all rest on one small mechanic: every node multiplies the gradient handed down to it by a derivative it works out on its own.
A node received going forward and emitted . Coming back, something above hands it , where is whatever loss the network is being trained on; it already knows . Multiply, and it can hand down.
The lecture's weight update is that rule with the names left off. With and ,
is the upstream gradient at the output, the local gradient of that output with respect to , and the downstream gradient the update consumes. One node, one multiplication.
Break the expression into pieces whose derivatives are obvious — and — then run values forwards and gradients backwards. Read as the loss.
With the rule in hand the common gates need no derivation — their backward behaviour is in their names.
Local gradient on every input, so the upstream gradient arrives unchanged.
Local gradient on each input is the other input's value — swapped and scaled.
A value used twice collects both gradients. Hence +=.
Local gradient on the winner and on the loser — all of it down one branch.
One consequence of the swap: scale your inputs by 1000 and the gradients on the weights meeting them grow by 1000 too. That is why pre-processing changes how a network trains.
A node need not be one arithmetic operation. Any piece with a clean local gradient makes a good gate.
Same either way, but one gate reuses a number the forward pass already produced. That is the one in two of Question 4's four lines: is a sigmoid gate.
What is the complexity of the back-propagation algorithm for an autoencoder with layers and nodes per layer?
Both passes through the network are matrix arithmetic. Forward, a layer turns the activation reaching it into a pre-activation ; backward, the chain rule pushes the error signal back through the same weights, . Fully connected layers of nodes each mean every is .
If that backward recursion is not yet familiar, the primer above builds it one node at a time.
So which order of growth is it?
Assume you initialise all weights in a neural net to the same value, and you do the same for the bias terms. Is this a good idea? Justify your answer.
The weight update depends only on quantities the unit itself sees: . In the primer's terms that gradient is upstream local — and two units in the same layer share the input, so if they also share their weights, both factors match.
Two hidden units, the same input , the same gradient arriving from the output unit. Watch what each unit's gradient is built from.
Fill in the following derivative equations for and , using the notation defined below — no new notation is needed. Tap a blank, then tap the expression that belongs in it.
An autoencoder is a neural network designed to learn feature representations in an unsupervised manner. Unlike a standard multi-layer network, an autoencoder has the same number of nodes in its output layer as its input layer, and is trained to reconstruct its own input — that is, to minimise the reconstruction error.
Suppose the input is a set of -dimensional unlabelled data , and the autoencoder has hidden units in its second layer .
Before the general case, walk the notation once on the smallest autoencoder that still has all the parts — inputs, hidden units. Forward first, then backward.
The chain rule is the whole algorithm: if and then . Every line below is one application of it, and the sums appear wherever a quantity influences the loss through more than one path.
In the language of the primer: each line builds one downstream gradient as upstream local. Every blank is one of those two factors.
One convention throughout: a box is a quantity and an arrow is something done to it. Green runs up — the forward pass, with and sitting on arrows exactly as does. Red runs down and carries one local gradient per arrow. The two boxes on the right are what the question is after; the numbered badges mark the four hops it asks you to write down.
All six steps, written out once
Each line is one hop of the diagram: the gradient already carried to a quantity, times that hop's local derivative.
Question 4 asks for these six facts bundled into four lines: line 1 is step 1, line 2 is steps 2 and 3 together, line 3 is step 6, and line 4 is steps 4 and 5 together.
Now put those six facts into the four lines the question prints, in its own notation. Tap a blank, then tap the expression that belongs in it.
The sums above are what an index-by-index derivation gives you. Written with whole vectors and matrices the same six steps carry no sums at all — which is how the code is written, and how the shapes stay checkable. Here is elementwise multiplication, and and act elementwise.
One example, as column vectors: .
All examples at once, stacked as rows: . holds the hidden activations, one row per example — the letter is already the number of hidden units.
is the Frobenius norm — the sum of squares of every entry — so is still the total over all examples. Stacking examples as rows is what removes the transposes from the forward pass, and the two weight gradients come out already summed over the batch — which is exactly .
Line for line against the six steps: is steps 1 and 2 in one go; is step 3, with the outer product doing the work of the free indices and ; is steps 4 and 5, the matrix–vector product doing the work of the sum over ; and is step 6. Every gradient has the shape of what it differentiates — is , just like — which is the quickest check that no transpose has gone missing.
The lecture turns reconstruction error into a yes/no decision on five samples. Step through it — the arithmetic is the whole method.
Train the autoencoder on normal data only, so it learns to reconstruct normal data well and nothing else. Record and of the reconstruction error on the training data. Then flag a test point when
An anomaly is something the autoencoder has never learned to compress, so it reconstructs badly and produces a high error.
| Sample | error | verdict |
|---|
Only three training points are used so the arithmetic is easy to follow. In practice and come from thousands of examples, which is what makes them worth trusting.
The rule is a common technique used for anomaly detection. Describe the intuition of this rule for anomaly detection. How is our result affected if we use other values of (e.g. or )?
For a roughly normal distribution, holds about 68% of the mass, about 95%, and about 99.7% — the figure in the solutions. Reconstruction-error thresholding uses the upper tail only: too little error is never suspicious.
Question 6 asks you to swap a problem for a different-looking problem with the same answer. That swap has a name and a recipe, and both are easier to see on something you can already solve in your head. So here it is on with not allowed below 1 — answer , obviously — and then on the real thing.
A constraint is a rule you are not allowed to break. Rather than forbidding it, put a price on breaking it and let the variable go wherever it likes — if the price is high enough, it will not want to break the rule anyway.
That price is the Lagrange multiplier, written . Everything else is working out what the price should be.
The rule is . Rewrite it as how much room you have left, a quantity that must not go negative:
Now drop the rule and subtract times that room from what you are minimising:
Sit below 1 and is negative, so subtracting it adds to your total — a fine, and the bigger is the more it hurts. Sit above 1 and you get a small rebate instead. There is no rule left in ; there is only a number to minimise.
Slide the price and watch where bottoms out. Too cheap and it settles in the forbidden zone; too dear and it overshoots.
You do not have to slide anything — the right price can be calculated. These four moves are exactly what the SVDD derivation does next, and what Question 6 asks you to do for OCSVM.
and a value of — the answer we could see at the start. The SVDD derivation runs these same four moves; the only difference is that its primal has three variables (, , ) rather than one, so move 2 produces three identities instead of one, and move 3 has more to cancel.
The problem you started with — minimise over , obeying the rule — is the primal. The one you finished with — maximise over the price , no rule in sight — is the dual. Two facts make trading one for the other safe.
Whatever you pick, never exceeds the true answer, because at the true solution the price costs nothing and the rebate can only help. So every price gives a lower bound — the table shows it.
For a convex problem — which SVDD and OCSVM both are, being quadratic — the best of those lower bounds is not merely close, it is the true answer. Nothing is lost by solving the dual instead.
| price | |||||
|---|---|---|---|---|---|
| bottoms out at | 0 | 0.5 | 1 | 1.5 | 2 |
| value there, | 0 | 0.75 | 1 | 0.75 | 0 |
One last thing to carry into Question 6. At the best price, each rule ends up in one of two states: you are pressed right against it and its price is positive, or you are comfortably inside it and its price is zero. You never pay for a rule you were not going to break. That is why reading the afterwards tells you where each data point sits:
Comfortably inside. Delete this point and the answer would not change.
Pressed right against the boundary. These are the support vectors.
Paying the maximum and still outside — an anomaly.
Question 6 asks you to do for OCSVM exactly what the lecture did for SVDD. So replay the SVDD derivation once — it is the four moves from the primer on a real primal — and Question 6 becomes the same four moves again.
Find the smallest ball in feature space that encloses (almost) all the data, paying per unit of slack:
is the radius, the centre, the slack that lets point sit outside, and the non-linear feature map. Its inner products are written , the kernel — the only form in which ever has to be evaluated.
One multiplier per enclosure constraint, one per non-negativity constraint on the slack.
In the lecture we saw how to derive SVDD's dual from its primal. Given OCSVM's primal below, derive its dual.
Instead of a ball, OCSVM separates the mapped data from the origin by the widest possible margin. The decision boundary is :
is a prior on the fraction of training points that are anomalous, and it regulates the false-positive / false-negative trade-off — which is why OCSVM is also called -SVM.
Same shape as SVDD: for the margin constraints, for . The primal variables are now , and instead of , and .
| SVDD | OCSVM | |
|---|---|---|
| geometry | smallest enclosing ball | max-margin hyperplane from the origin |
| primal vars | ||
| dual objective | ||
| box | ||
| equality |
The two duals differ by one linear term. For an invariant kernel such as the Gaussian, for every point, so that term is the constant and drops out of the argmin — the two problems become identical. That is the lecture's remark that for invariant kernels, and Question 7 is where you can watch it happen.
Using LIBSVM and the KDDCUP data set: use SVDD and OCSVM to identify the attacks. How many data points are common among the anomalies identified by the different methods?
OCSVM scores a new point with and calls it an anomaly when . SVDD calls it an anomaly when . And the last OCSVM slide adds the punchline: for the special case of invariant kernels, e.g. Gaussian, .
Jaccard overlap is over the two flagged sets and : means the two methods flagged exactly the same points, that they shared none.