Neural networks II: what they can fit, and backprop with vectors

Why a network can approximate anything but might not learn it, what non-convexity really costs you, how to tell underfitting from overfitting, and backpropagation built up from a width-1 chain to a full matrix layer — every blank the slides left for the board, filled in.

1. Can a network fit any function?

Start with the worry. Logistic regression draws one straight line. The lecture's demo (Karpathy's ConvNetJS 2-D classifier) shows a small network carving out a triangle, a disc, even an interlocking spiral. Is there any shape it can't do?

Concretely: pick $H+1$ points $x_0 < x_1 < \dots < x_H$ on the curve you want. Join them with straight segments. The joined-up curve is

where $s_i$ is the slope of segment $i$. Read it as a network: hidden neuron $i$ has weight $1$ and bias $-x_i$; the output neuron's weights are the changes in slope $s_i - s_{i-1}$, and its bias is $f(x_0)$. One hidden layer, $H$ neurons. The figure builds exactly this.

2. Non-convex: does getting stuck matter?

Logistic regression's loss is a bowl — one minimum, and gradient descent finds it. A network's loss is not: the hidden-layer weights multiply each other (and you can relabel hidden neurons without changing the function), so the surface has many valleys. The lecture makes three points:

1. The objective is non-convex → gradient descent can get stuck in a local minimum.
2. Stochastic gradient descent takes noisy, pseudo-random steps → that noise helps it pop out of shallow minima.
3. "Is getting stuck at a local minimum necessarily a bad thing??" — the slide leaves this open. Answered below.

3. What if there are no non-linear activations?

Delete every $g$ and keep stacking linear layers. Do you get a more powerful model? No:

Two layers: $\mathbf z_1 = W_1\mathbf x + \mathbf b_1$, then $\mathbf z_2 = W_2\mathbf z_1 + \mathbf b_2$. Substitute:

One matrix, one bias. By induction, any number of linear layers collapses the same way.

4. How many neurons and layers? Debug it from the losses

There's no formula for the right size. Instead, train something, then read two numbers — training loss and validation loss — and let them tell you which way to move.

"But how do we choose a new network structure?" — the slide's follow-up. Treat width and depth as hyperparameters: pick a few candidates, train each, and compare validation loss, exactly as chapter 12's cross-validation did for $\lambda$. Usual practice is to start from an architecture known to work on a similar problem and adjust.

5. Backprop on a width-1 chain

Now the calculus. The lecture's warm-up is a deliberately "dumb" network: five layers, one neuron each, no biases. It has none of the index mess of a real network, so you can see the structure of the computation clearly.

Written out, $\hat y = g(w_5\, g(w_4\, g(w_3\, g(w_2\, g(w_1 x)))))$ — a nesting of $f$ (multiply by a weight) and $g$ (activation), ten deep.

The question: gradient descent needs $\partial J/\partial w_\ell$ for every $\ell$ so it can update $w_\ell \leftarrow w_\ell - \alpha\,\partial J/\partial w_\ell$. The chain rule along the single path gives, e.g.

Now write the same thing for $w_1$: it's the same long product with two more factors on the end. Computing each $\partial J/\partial w_\ell$ from scratch repeats almost all the work.

6. The generic layer: the only interface backprop needs

Zoom out. Every layer, whatever it computes, is a box $\mathbf z_{\text{out}} = f(\mathbf z_{\text{in}}, \theta)$. The forward pass pushes values left-to-right through the boxes. The backward pass pushes $\partial J/\partial(\cdot)$ right-to-left. Each box only has to know its own local derivatives.

For a scalar layer the two outputs are

That's why deep-learning libraries can let you build arbitrary networks from Lego-brick layers: each brick implements forward and backward, and the library just calls them in order, then in reverse.

7. Multivariate chain rule: when paths fork, add

The chain above has exactly one path from each weight to $J$. Real networks fork: one value feeds several neurons. The lecture's first exercise is the simplest fork.

Three versions of the chain rule

The third column is the one to remember — the other two are special cases. The sum over $j$ is "add over every intermediate the influence can flow through".

Why the updated layer says "+="

The lecture's "Generic Layer Implementation (updated)" slide changes $=$ to $+=$:

8. A layer with a vector output

Now let the layer output $K$ numbers, $\mathbf z_{\text{out}} \in \R^K$, with parameters $\boldsymbol\theta \in \R^M$. The slide leaves the formulas blank on its first version. Fill them in with the third column of the table: $z_{\text{in}}$ reaches $J$ through each of the $K$ outputs, so sum over them.

Here $j$ indexes a single parameter; you compute this once per $j = 1,\dots,M$. The incoming message is now a vector $\partial J/\partial\mathbf z_{\text{out}} \in \R^K$, one number per output.

9. The linear layer: $\mathbf z = W\mathbf a + \mathbf b$

The workhorse. Input $\mathbf a \in \R^M$, weights $W \in \R^{K\times M}$, bias $\mathbf b \in \R^K$, output $\mathbf z \in \R^K$. Entry by entry:

The slides pose three blanks: $\partial J/\partial a_j$, $\partial J/\partial W_{i,j}$, $\partial J/\partial b_i$. Here they are, filled.

Scalar version — derive each one

Step 1, the vector-output rule: every derivative is $\sum_k \frac{\partial J}{\partial z_k}\cdot(\text{how much } z_k \text{ moves})$.

Step 2, the local derivatives from $z_k = b_k + \sum_j W_{k,j}a_j$:

• $\frac{\partial z_k}{\partial a_j} = W_{k,j}$ — every output depends on every input.
• $\frac{\partial z_k}{\partial W_{i,j}} = a_j$ if $k = i$, and $0$ otherwise — weight $W_{i,j}$ only appears in output $i$.
• $\frac{\partial z_k}{\partial b_i} = 1$ if $k = i$, and $0$ otherwise.

Step 3, plug in. The sum over $k$ survives for $\mathbf a$, and collapses to a single term for $W$ and $\mathbf b$:

Matrix version — two layouts

Stack those into vectors and matrices. Write $\boldsymbol\delta = \partial J/\partial\mathbf z$ for the incoming message.

10. Putting it together: backprop for a whole network

A fully connected network is linear layers alternating with element-wise activation layers. You now have both bricks. The activation brick $\mathbf a = g(\mathbf z)$ acts on each entry separately, so output $k$ depends only on input $k$, and the sum over $k$ collapses to one term:

where $\odot$ means multiply entry by entry. Chain the bricks:

forward(x):
    a[0] = x
    for l = 1..L:
        z[l] = W[l] @ a[l-1] + b[l]        # linear brick (store a[l-1])
        a[l] = g(z[l])                     # activation brick (store z[l])
    return J = loss(a[L], y)

backward():
    dA = dJ/da[L]                          # from the loss
    for l = L..1:
        dZ    = dA * g'(z[l])              # activation brick, element-wise
        dW[l] = dZ @ a[l-1].T              # outer product
        db[l] = dZ
        dA    = W[l].T @ dZ                # message to the layer below
    # then: W[l] -= alpha * dW[l],  b[l] -= alpha * db[l]  for every l

Set every width to 1 and this is exactly §5's chain. That's the payoff of the lecture's "dumb" warm-up: the structure was already there.

11. Recap

1. Universal approximation: one hidden layer with enough neurons can approximate any continuous function — ReLUs are kinks in a bendable wire. Says nothing about learnability or size.
2. Non-convex loss → local minima; SGD's noise helps escape. Local minima aren't necessarily bad: we care about validation loss, and in big nets most minima are similar.
3. No nonlinearity → one linear layer: $W_2(W_1\mathbf x + \mathbf b_1) + \mathbf b_2 = (W_2W_1)\mathbf x + (W_2\mathbf b_1 + \mathbf b_2)$.
4. Debug underfitting first (bad train loss → more capacity), then overfitting (good train, bad validation, large weights → regularise / more data). Size is a hyperparameter.
5. Backprop = chain rule, computed right-to-left, reusing the running product. Each layer: receive $\partial J/\partial z_{\text{out}}$, emit $\partial J/\partial z_{\text{in}}$ and $\partial J/\partial\theta$.
6. Multivariate chain rule: multiply along paths, add over paths → in code, $+=$.
7. Linear layer: $\partial J/\partial\mathbf a = W^\top\boldsymbol\delta$, $\partial J/\partial W = \boldsymbol\delta\mathbf a^\top$, $\partial J/\partial\mathbf b = \boldsymbol\delta$ (denominator layout). Activation: $\boldsymbol\delta = \partial J/\partial\mathbf a \odot g'(\mathbf z)$.