All the derivatives of a network
A developer of a neural network library is testing their automatic differentiator and asks for a reference: for a small network and a batch of examples, compute the loss and its derivatives with respect to every weight.
The network has L layers of sizes n0, …, nL. Given an input a (a vector of nl−1 numbers), layer l computes zi = Σk wikak + wi,n (the last weight of a row is the bias). Every layer except the last is followed by tanh. The last layer gives z, and the loss of an example with answer t is ln Σj ezj − zt (softmax and cross-entropy). The loss of the batch is the sum over the examples.
Input
The first line holds L (1 ≤ L ≤ 4), the second n0, …, nL (1 ≤ n ≤ 128, nL ≥ 2). Then the weights: for each layer in order, nl lines of nl−1 + 1 numbers. Then B (1 ≤ B ≤ 50) and B lines: n0 input numbers and the answer t (0 ≤ t < nL).
Output
The first line is the loss of the batch. Then the derivatives of the loss with respect to the weights, in the same order and layout as the weights in the input. Each number is accepted with an error up to 10−6 (for numbers above one, up to 10−6 of the number).
Examples
Example 1
1 2 2 1.0000 0.0000 0.0000 0.0000 1.0000 0.0000 1 1.000 0.000 0
0.3132616875 -0.2689414214 0 -0.2689414214 0.2689414214 0 0.2689414214
Example 2
2 2 2 2 0.5000 -0.5000 0.0000 0.2500 0.2500 0.1000 1.0000 -1.0000 0.0000 -1.0000 1.0000 0.0000 2 1.000 2.000 1 0.000 -1.000 0
0.35319829 0.1424988312 0.6429633609 -0.2154668674 -0.09465939317 -0.6343970116 0.3504188321 -0.1470366282 0.09649231629 -0.1369874045 0.1470366282 -0.09649231629 0.1369874045
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
You could move every weight by a small ε and recompute the loss, but the large test has 13,098 weights, and each needs two passes over the whole batch.
2Hint 2
If you know the derivative of the loss with respect to a layer's outputs z, the derivative with respect to the weight wik is that times the input ak. And the derivative with respect to the layer's inputs is a sum over the outputs. Start from the end.
3The idea
Backpropagation. At the last layer the derivative of the loss with respect to z is the softmax probabilities minus one at the answer. Then for each layer from the last to the first: add δi·ak to the weight derivatives, pass back δ′k = Σi δiwik and multiply by the derivative of tanh, 1 − ak².
4Walkthrough
For each example the forward pass remembers the inputs of all layers (with a one for the bias), and the backward pass accumulates the derivatives by the formulas above in an array shaped like the weights. Softmax is computed shifted by the largest z: ln Σ ez = max + ln Σ ez − max; otherwise with large weights the exponent overflows (in the ninth test z reaches a thousand, and ez in floating point runs out after 709).
4+Solution
5Complexity
O(B·W), where W is the number of weights: the forward and backward passes take one multiplication per weight each. Finite differences take O(B·W²).
6Common mistakes
- Finite differences. This is
wrong.py: they are accurate enough, but with thirteen thousand weights it is twenty-six thousand passes over the batch. - The derivative of tanh through its output. It is 1 − tanh², that is, 1 − a², where a is the neuron's already computed output, not its input z.
- The bias. Its input is a constant one, so the derivative with respect to the bias is just δ, and it passes nothing back.
- Overflow. exp(z) without subtracting the maximum gives infinity at z of a few hundred.