Chapter 5: Deep Learning

For a composition $f = f_L \circ f_{L-1} \circ \cdots \circ f_1$, the chain rule gives $\frac{\partial \mathcal{L}}{\partial \mathbf{w}_l} = \frac{\partial \mathcal{L}}{\partial \mathbf{a}_L} \prod_{k=l+1}^{L} \frac{\partial \mathbf{a}_k}{\partial \mathbf{a}_{k-1}} \cdot \frac{\partial \mathbf{a}_l}{\partial \mathbf{w}_l}$ where $\mathbf{a}_l$ is the activation at layer $l$. Each Jacobian $\partial \mathbf{a}_k/\partial \mathbf{a}_{k-1}$ is a matrix, and the product of $L$ matrices determines whether gradients vanish or explode. If all singular values are less than 1, gradients decay exponentially as $O(\sigma_{\max}^L)$. Backpropagation computes this product right-to-left in $O(n)$ time, where $n$ is the number of parameters — the same order as the forward pass.

SGD updates parameters via $\mathbf{w}_{t+1} = \mathbf{w}_t - \eta \nabla_{\mathbf{w}} \mathcal{L}(\mathbf{w}_t)$. For a quadratic loss surface $\mathcal{L}(\mathbf{w}) = \frac{1}{2}\mathbf{w}^T H \mathbf{w}$, convergence requires $\eta < 2/\lambda_{\max}$ where $\lambda_{\max}$ is the largest eigenvalue of the Hessian $H$. The condition number $\kappa = \lambda_{\max}/\lambda_{\min}$ determines convergence speed: $\|\mathbf{w}_t - \mathbf{w}^*\| \leq (\frac{\kappa - 1}{\kappa + 1})^t \|\mathbf{w}_0 - \mathbf{w}^*\|$. Adam adapts per-parameter learning rates using running estimates of first moment $m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t$ and second moment $v_t = \beta_2 v_{t-1} + (1-\beta_2)g_t^2$, effectively scaling $\eta$ by $1/\sqrt{v_t}$ — larger for rare features, smaller for frequent ones.

Consider a deep linear network $y = W_L W_{L-1} \cdots W_1 x$. The gradient norm scales as $\|\nabla_{W_1}\| \propto \prod_{l=2}^L \|W_l\|$. If each $\|W_l\| = \sigma$, then the product is $\sigma^{L-1}$ — exponential growth for $\sigma > 1$ (explosion) and decay for $\sigma < 1$ (vanishing). Xavier initialization sets $\text{Var}(w) = 1/n_{\text{in}}$ so that output variance equals input variance. He initialization uses $\text{Var}(w) = 2/n_{\text{in}}$ to account for ReLU zeroing half the activations. Gradient clipping bounds $\|\nabla\| \leq \theta$ — geometrically, it projects the gradient onto a ball of radius $\theta$, preserving direction.

A computational graph is a directed acyclic graph (DAG) where nodes represent operations and edges carry tensors. The forward pass evaluates nodes in topological order in $O(V + E)$ time. The backward pass traverses the reverse topological order, applying the chain rule at each node. For a node computing $c = f(a, b)$, the backward pass computes $\bar{a} = \bar{c} \cdot \partial c/\partial a$ and $\bar{b} = \bar{c} \cdot \partial c/\partial b$ where $\bar{c} = \partial \mathcal{L}/\partial c$ is the upstream gradient. Memory cost is $O(V)$ because all intermediate activations must be stored for the backward pass — this is why memory, not compute, is often the bottleneck. Gradient checkpointing trades $O(\sqrt{V})$ memory for $O(2V)$ compute by recomputing activations.

The discrete 2D convolution is $(I * K)(i,j) = \sum_m \sum_n I(i+m, j+n) K(m,n)$ where $K$ is a $k \times k$ kernel. For an input of size $H \times W$ with $C_{\text{in}}$ channels and $C_{\text{out}}$ filters, the output size is $\lfloor(H + 2p - k)/s\rfloor + 1$ where $p$ is padding and $s$ is stride. The operation has $C_{\text{out}} \times C_{\text{in}} \times k^2$ parameters — dramatically fewer than a fully connected layer which would need $H \times W \times C_{\text{in}} \times H' \times W' \times C_{\text{out}}$ parameters. This parameter sharing exploits translation equivariance: $T_\delta(I * K) = (T_\delta I) * K$ where $T_\delta$ is a spatial shift.

Max pooling selects the maximum over each $k \times k$ window: $y_{ij} = \max_{(m,n) \in R_{ij}} x_{mn}$. It reduces spatial dimensions by factor $k$ while preserving the strongest activations. The gradient flows only to the argmax location (winner-take-all), making it a form of local routing. Average pooling computes $y_{ij} = \frac{1}{k^2}\sum_{(m,n) \in R_{ij}} x_{mn}$ and distributes gradients equally. Global average pooling (GAP) over the entire feature map produces a $1 \times 1 \times C$ vector, replacing fully connected layers and reducing parameters from $H \times W \times C \times N_{\text{classes}}$ to $C \times N_{\text{classes}}$. Pooling provides a degree of translation invariance: small shifts in input produce the same pooled output.

A typical CNN stacks convolution blocks $\text{Conv} \to \text{BN} \to \text{ReLU} \to \text{Pool}$, progressively reducing spatial resolution while increasing channel depth. If the input is $224 \times 224 \times 3$, after 5 pooling layers of stride 2 the spatial dimensions are $7 \times 7$. The FLOPs for a conv layer are $2 \times C_{\text{in}} \times k^2 \times C_{\text{out}} \times H_{\text{out}} \times W_{\text{out}}$. VGG-16 uses 138M parameters and 15.5G FLOPs. Modern architectures use depthwise separable convolutions to factorize the $C_{\text{in}} \times k^2 \times C_{\text{out}}$ into $C_{\text{in}} \times k^2 + C_{\text{in}} \times C_{\text{out}}$, reducing compute by factor $\sim k^2$.

The receptive field of a neuron in layer $l$ is the region of the input that influences its activation. For a stack of $L$ layers each with kernel size $k$ and stride $s$, the receptive field grows as $r_L = 1 + \sum_{l=1}^{L}(k_l - 1)\prod_{i=1}^{l-1} s_i$. With $k=3$ and $s=1$, each layer adds 2 pixels: after 5 layers, $r = 11$. With $s=2$ pooling, the growth is exponential in depth. The effective receptive field (ERF) — the region that actually contributes significantly to the output — is much smaller than the theoretical one, typically following a Gaussian distribution centered on the neuron. Dilated convolutions increase the receptive field to $k + (k-1)(d-1)$ without reducing resolution, where $d$ is the dilation rate.

A residual block computes $\mathbf{y} = F(\mathbf{x}) + \mathbf{x}$ where $F$ is the residual function. The gradient through the skip connection is $\partial \mathbf{y}/\partial \mathbf{x} = \partial F/\partial \mathbf{x} + I$, so the identity matrix $I$ ensures gradients always have a direct path — they cannot vanish through the skip connection. For a network with $L$ residual blocks, the gradient decomposes into $2^L$ paths of different lengths. The loss surface of ResNets is empirically smoother (smaller Lipschitz constant of the gradient) than plain networks, enabling higher learning rates. ResNet-50 achieves 76% top-1 on ImageNet with 25.6M parameters — the skip connections make training 152-layer networks practical where plain networks of the same depth fail to converge.

Self-attention computes $\text{Attention}(Q, K, V) = \text{softmax}(QK^T/\sqrt{d_k})V$ where $Q, K, V \in \mathbb{R}^{n \times d_k}$ are queries, keys, and values. The dot product $QK^T$ has $n^2$ entries, each measuring similarity between a query-key pair — this is why attention is $O(n^2 d_k)$ in both time and memory. The $1/\sqrt{d_k}$ scaling prevents the dot products from growing with dimension (variance of a sum of $d_k$ products is $d_k$, so dividing by $\sqrt{d_k}$ normalizes to unit variance). Multi-head attention splits $d$ dimensions into $h$ heads of size $d_k = d/h$, allowing each head to attend to different representation subspaces. Vision Transformers (ViT) split an image into $P \times P$ patches, treating each as a token — for 224x224 with P=16, this gives $n = 196$ tokens.

For a mini-batch $\{x_1, ..., x_m\}$, BN normalizes: $\hat{x}_i = (x_i - \mu_B)/\sqrt{\sigma_B^2 + \epsilon}$ then scales and shifts: $y_i = \gamma \hat{x}_i + \beta$. Here $\mu_B = \frac{1}{m}\sum x_i$ and $\sigma_B^2 = \frac{1}{m}\sum(x_i - \mu_B)^2$. BN reduces internal covariate shift — the changing distribution of layer inputs during training. Mathematically, BN makes the loss landscape smoother: the Lipschitz constant of the loss $\|\nabla \mathcal{L}(w_1) - \nabla \mathcal{L}(w_2)\| / \|w_1 - w_2\|$ is bounded, enabling larger learning rates. During inference, $\mu_B$ and $\sigma_B^2$ are replaced by running averages computed during training — the BN layer becomes a fixed affine transform.

During training, dropout sets each neuron to zero with probability $p$, then scales surviving activations by $1/(1-p)$: $\tilde{h}_i = \frac{1}{1-p} h_i \cdot m_i$ where $m_i \sim \text{Bernoulli}(1-p)$. This is equivalent to training an ensemble of $2^n$ thinned networks (where $n$ is the number of neurons) that share weights. At test time, all neurons are active and no scaling is needed (inverted dropout). The expected output is unchanged: $E[\tilde{h}_i] = \frac{1}{1-p}(1-p)h_i = h_i$. Dropout can be interpreted as approximate Bayesian inference — it samples from an approximate posterior over network weights, providing uncertainty estimates via Monte Carlo dropout at test time.