Where we left off

• Session 2: generalized linear models, regularization, SVM, kernels
• Everything so far has been one layer of parameters
• Today: stack layers, let the network learn its own features

From biology to a formal model

• Many inputs (dendrites) → accumulated signal → one all-or-nothing output (axon)
• Some inputs excite, some inhibit, and not all synapses carry the same strength
• McCulloch & Pitts (1943): symbolic logic (no notion of learning)

The formal neuron: a weighted sum of the inputs \(x_0,\dots,x_{d-1}\) plus a bias \(b\), passed through an activation function \(\sigma\).

McCulloch-Pitts formal neuron

\[ h(x) = \sigma(\langle w, x\rangle + b) \]

• \(x\): inputs, \(w\): synaptic strengths, \(b\): firing threshold, \(\sigma\): a thresholding function
• Originally: \(x \in \{0,1\}^d\), $= $ step function, “activated or not”
• The \(\sigma(\langle w,x\rangle + b)\) formula is not explicitly in the 1943 paper → modern restatement of it

A bit of history

• McCulloch & Pitts worked in boolean algebra, not vector spaces
• Their research: which boolean functions can networks of such neurons compute, depending on whether the network has cycles?
• This is the root of what became symbolic AI: logic circuits made of neurons, decades before gradient descent optimization

The Perceptron

• Rosenblatt (1958): the first neural network, built first and foremost as hardware
• Several output units, linked by inhibition so only one fires at a time
• No gradient descent: handcrafted update rules for the circuit’s wiring

From the Perceptron’s manual (public domain)

Hebbian learning

• Hebb (psychologist): “cells that fire together, wire together”
• Rosenblatt’s unsupervised update: strengthen a weight whenever both its input and its output are active \[ w_i \leftarrow w_i + \eta\, x_i\, y \]
• Purely local, no notion of a target label, reinforces co-activation

Supervised learning

• To get supervised learning, Rosenblatt’s Perceptron needed an operator to manually force an output and trigger reinforcement
• Modern terminology: the Perceptron is a linear model with a differentiable \(\sigma\), trained by gradient descent

Impossibility theorem

Proof

The counter-example is XOR: \((0,0)\mapsto 0,\ (1,1)\mapsto 0,\ (0,1)\mapsto 1,\ (1,0)\mapsto 1\)

Let \(\theta\) be the unique threshold such that \(\sigma(\theta) > k\) reads as output \(1\). Solving XOR would require all four of \[ b \leq \theta,\\ \quad w_2+b > \theta,\\ \quad w_1+b > \theta,\\ \quad w_1+w_2+b \leq \theta \] Summing equations 1 and 4 gives \(w_1+w_2+2b \leq 2\theta\). Summing 2 and 3 gives \(w_1+w_2+2b > 2\theta\). Contradiction.

Multi-layer perceptron

• Like kernels: map the input through a non-linearity, hope the result is linearly separable
• Instead of a fixed non-linear map \(\phi\), learn it by stacking perceptrons on top of each other

\[ f_i(x) = \big[\sigma(w_{ij}^\top x + b_{ij})\big]_{j \leq d_i}, \qquad F(x) = f_L \circ \cdots \circ f_1(x) \]

A multilayer perceptron: input \(x\) through 3 fully-connected layers.

Activation functions

Sigmoid, tanh, ReLU, Leaky ReLU, GeLU

• Sigmoid \(\frac{1}{1+e^{-x}}\): range \((0,1)\), saturates both ends (flat gradient, hurts training)
• tanh: range \((-1,1)\), same saturation issue, wider range
• ReLU \(\max(0,x)\): gradient is \(1\) on the right, but dead units on the left (zero gradient forever)
• Leaky ReLU: small slope \(\alpha\) on the left, no dead units
• GeLU \(x\,\Phi(x)\): smooth everywhere, gradient vanishes only where it should

⚡ Solve XOR with 2 hidden neurons

MLP training: ERM

\[ \hat{\mathcal{R}}_{\mathcal{A}}(F) = \frac1n \sum_{i=1}^n \ell(y_i, F(x_i)) \]

• Minimize over every layer’s weights \(w_1, \ldots, w_L\) by gradient descent, estimated on mini-batches
• Need \(\frac{\partial \ell}{\partial w_l}\) for every layer \(l\): chain rule through a composition of \(L\) functions

Chain of neuron

Simplify to a chain of scalar neurons, \(x_0 \to x_1 \to x_2 \to \ell\), with \(x_k = \sigma(w_k x_{k-1})\): \[ x_1 = \sigma(w_1 x_0), \qquad x_2 = \sigma(w_2 x_1), \qquad \ell = \ell(y, x_2) \]

Leibniz notation makes every intermediate variable explicit

Leibniz notation

\[ \frac{\partial \ell}{\partial w_2} = \frac{\partial \ell}{\partial x_2}\cdot \frac{\partial x_2}{\partial w_2} = \ell'(y,x_2)\cdot \sigma'(w_2 x_1)\, x_1 \]

\[ \frac{\partial \ell}{\partial w_1} = \frac{\partial \ell}{\partial x_2}\cdot \frac{\partial x_2}{\partial x_1}\cdot \frac{\partial x_1}{\partial w_1} = \underbrace{\ell'(y,x_2)\,\sigma'(w_2 x_1)}_{\text{reused from above}} \cdot\ w_2\, \sigma'(w_1 x_0)\, x_0 \]

• The term under the brace is re-used (only one computation)

Backpropagating gradients: \(\delta\)

Define \(\delta_2 = \ell'(y,x_2)\,\sigma'(w_2 x_1)\) (the “local gradient” at neuron 2)

\(\delta_1 = \delta_2\, w_2\, \sigma'(w_1 x_0)\). Then

\[ \frac{\partial \ell}{\partial w_2} = \delta_2\, x_1, \qquad \frac{\partial \ell}{\partial w_1} = \delta_1\, x_0 \]

• \(\delta\) propagates backward, each step multiplying by that layer’s own local derivative

Backprop for MLP

Same recursion \[ \delta_L = \ell'(y, F(x)) \circ \sigma'(x_L), \qquad \delta_k = w_{k+1}^\top\big(\sigma'(x_{k+1}) \circ \delta_{k+1}\big) \] \[ \frac{\partial \ell}{\partial w_k} = \delta_k\, x_{k-1}^\top, \qquad \frac{\partial \ell}{\partial b_k} = \delta_k \]

• \(\circ\): element-wise product. \(x_k\): layer \(k\)’s output, stored during the forward pass
• Forward pass computes and stores every \(x_k\); backward pass computes every \(\delta_k\) from \(L\) down to \(1\), reusing the previous step

Backprop is cheap

• Back-propagation costs at most 3x the forward pass: forward, backward through the activations, backward through the weights
• We are lucky: minimizing empirical risk only needs cheap differentiation with one universal recipe
• In practice: an automatic differentiation engine (pytorch, JAX)

Vanishing and exploding gradients

• \(\delta_k\) is a product of per-layer terms, going backward
• If every layer’s local gradient has \(|\delta| < 1\): the product shrinks to \(0\) as depth grows → vanishing gradient
• If every layer’s local gradient has \(|\delta| > 1\): the product grows without bound → exploding gradient

Universal approximation, for the sign function

Proof sketch. Let \(\{u_i\}\) be the inputs with label \(1\). Since binary vectors differ by at least 2 bits, \(\langle x,u_i\rangle \leq n-2\) unless \(x=u_i\). One hidden neuron per \(u_i\), \(h_i(x) = \mathrm{sign}(u_i^\top x - n+1)\), fires only on \(x=u_i\). Output \(F(x) = \mathrm{sign}(\sum_i h_i(x) + k - 1)\) reproduces the label.

Memorization

• The construction literally memorizes every positive example: one hidden neuron each
• For a single hidden layer, this can require exponentially many neurons in the worst case
• Depth: a depth-\(2k\) ReLU network with \(O(k)\) neurons for single hidden-layer with width \(2^k\) (Telgarsky 2016)

Why not just use MLP on images?

• Images: the pattern that matters is not always at the same position (a flower is never perfectly centered in Bluebell)
• An MLP treats every input position with its own weights: move 1 pixel and weights are different
• We want equivariance: shifting the input should shift the output the same way

Equivariance

• For images/sequences, we want equivariance to translation
• Achieved by the convolution operator

Convolution, 1D

• Strictly this is cross-correlation (no kernel reflection), but “convolution” is the name used in deep learning

2D Convolution

\[ (x \star h)[m,n] = \sum_{k}\sum_{l} x[m+k,n+l]\, h[k,l] \]

• Same sliding-window idea but over two spatial axes
• For \(3\)-channel images, \(x[m,n] \in \mathbb{R}^3\): a vector kernel \(h[m,n]\in\mathbb{R}^3\) replaces multiplication with an inner product
• To go from \(d\) channels to \(p\) channels: \(h[m,n]\in\mathbb{R}^{d\times p}\), \((x\star h)[m,n] = \sum_{k,l} h[k,l]^\top x[m+k,n+l]\)

⚡ Convolution and translation don’t commute (finite case)

Recap

• Formal neuron, perceptron: a historical and literal logic-circuit view of what a single unit computes, and how it was first “trained” by hand
• Impossibility theorem: one hyperplane is not enough; MLPs fix this by stacking, at the cost of losing a closed form and needing backprop
• Backprop: the chain rule, reusing each layer’s local gradient exactly once, going backward. Vanishing/exploding gradients are a structural weakness
• CNNs: translation equivariance via weight sharing, from LeNet’s principles to AlexNet’s scale
• ResNet: residual connections, which fix both the optimization and the geometry of the loss