Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

CNNs, RNNs & Residual Networks

Architectures that bake in structure.

To a fully connected network, a photo is a list of unrelated numbers: shift the cat by one pixel and every input changes. The architectures that made deep learning work build in what is known about the data: images look alike everywhere, sequences unfold in time, and deep functions are small corrections to the identity. They learn from far less data and train far deeper.

What you’ll learn

  • Compute a convolutional layer's output (cross-correlation with stride and padding), its output size and parameter count, and prove that convolution is translation equivariant.
  • Compute the receptive fields of stacked convolutions and pooling, and trace the LeNet, AlexNet, VGG and ResNet lineage.
  • Derive backpropagation through time for a recurrent network and explain why its gradients vanish or explode over long sequences.
  • Write the LSTM, GRU and residual-block equations, and explain how their additive paths keep gradients alive.

Convolution: sharing weights across space

A fully connected layer from a 224×224×3224\times224\times3 image to a feature map of the same size with 64 channels would need about 4.8×10114.8\times10^{11} weights. A convolutional layer instead slides small kernels across the image and reuses them at every position. With CinC_{\text{in}} input channels, CoutC_{\text{out}} output channels, k×kk\times k kernels, stride ss and zero padding pp:

Yo,r,c=bo+∑i=1Cin∑u=0k−1∑v=0k−1Ko,i,u,v Xi, rs+u−p, cs+v−p,nout=⌊n+2p−ks⌋+1Y_{o,r,c}=b_o+\sum_{i=1}^{C_{\text{in}}}\sum_{u=0}^{k-1}\sum_{v=0}^{k-1}K_{o,i,u,v}\,X_{i,\,rs+u-p,\,cs+v-p},\qquad n_{\text{out}}=\Big\lfloor\frac{n+2p-k}{s}\Big\rfloor+1
Cout(Cink2+1)C_{\text{out}}(C_{\text{in}}k^2+1) parameters whatever the image size: 64⋅(3⋅9+1)=1,79264\cdot(3\cdot9+1)=1{,}792 for a 3×33\times3 layer on RGB input. This is cross-correlation. Deep-learning libraries call it convolution, while a true convolution flips the kernel, using Ko,i,k−1−u,k−1−vK_{o,i,k-1-u,k-1-v}; since the kernels are learned, the difference is only a relabeling.

Two assumptions are built in. Locality: each output depends on a small patch. Weight sharing: the same detector is applied everywhere. Together they give the layer its defining symmetry.

Check your understanding

Suppose the widget computed a true convolution, rotating each kernel by 180∘180^\circ before sliding it. What would change?

  1. Nothing, for any kernel
  2. Every feature map would shift by one pixel
  3. The Sobel maps would change sign everywhere, while blur, sharpen and edge would be unchanged
  4. Only the blur map would change
Show the answer

C. The Sobel maps would change sign everywhere, while blur, sharpen and edge would be unchanged

Rotating Sobel-y by 180∘180^\circ gives top row minus bottom row, exactly −-Sobel-y, and likewise for Sobel-x. Blur, sharpen and edge are symmetric under the rotation, so for them convolution and cross-correlation agree. In a network the kernels are learned, so it would simply learn the rotated kernels.

Pooling, receptive fields and the classic CNNs

Pooling summarizes each window, usually by its maximum over 2×22\times2 blocks with stride 2. It halves the resolution, has no parameters, and makes the output insensitive to small shifts within a block. A unit's receptive field is the input region it depends on. Track its width rr and the jump jj, the input distance between adjacent units, through layers with kernel size klk_l and stride sls_l:

rl=rl−1+(kl−1) jl−1,jl=jl−1 sl,r0=j0=1r_l=r_{l-1}+(k_l-1)\,j_{l-1},\qquad j_l=j_{l-1}\,s_l,\qquad r_0=j_0=1
Each layer widens the field by kl−1k_l-1 steps of the current jump, and strides multiply the jump. LL stride-1 3×33\times3 convolutions see (2L+1)×(2L+1)(2L+1)\times(2L+1) pixels; after one stride-2 layer, each further 3×33\times3 layer adds 4.
Predict before you look

Three 3×33\times3 convolutions with stride 1, then 2×22\times2 max pooling with stride 2, then two more 3×33\times3 convolutions. How wide is the receptive field of one final unit, in input pixels?

Show the answer

16

The convolutions give r=1→3→5→7r=1\to3\to5\to7; pooling gives 7+(2−1)⋅1=87+(2-1)\cdot1=8 and doubles the jump to j=2j=2; each later 3×33\times3 layer adds 2⋅2=42\cdot2=4, so 8→12→168\to12\to16. Downsampling is what lets receptive fields cover a whole object after a few layers.

The VGG networks (Simonyan & Zisserman, 2015) used only 3×33\times3 kernels, because a stack of small kernels is cheaper and more expressive than one large kernel with the same field. With CC channels in and out, two 3×33\times3 layers see 5×55\times5 with 2⋅9C2=18C22\cdot9C^2=18C^2 weights instead of 25C225C^2, three see 7×77\times7 with 27C227C^2 instead of 49C249C^2, and every extra layer adds a nonlinearity.

NetworkYearDepth and sizeWhat it introduced or showed
LeNet-519987 layers, about 60,000 parametersconvolution, subsampling and end-to-end gradient training for reading digits and documents (LeCun et al.)
AlexNet20128 learned layers, about 60 million parametersReLU, dropout, data augmentation and two GPUs; won ImageNet with 15.3% top-5 error against 26.2% (Krizhevsky, Sutskever & Hinton)
VGG-16201416 weight layers, about 138 million parametersdepth from uniform 3×33\times3 stacks (Simonyan & Zisserman)
ResNet-1522015152 layers, about 60 million parametersresidual connections; won ImageNet 2015 with 3.57% top-5 error (He et al.)
Years of the results; the VGG and ResNet papers appeared in 2015 and 2016. Errors are top-5 on the ImageNet challenge test set, the ResNet figure for an ensemble. ResNet-152 needs fewer operations per image than VGG-16 while being nearly ten times deeper.

Recurrent networks and backpropagation through time

A recurrent network reads a sequence x1,…,xT\mathbf x_1,\dots,\mathbf x_T one element at a time and carries a hidden state forward, using the same weights at every step: weight sharing across time instead of space.

ht=tanh⁡(Wht−1+Uxt+b),y^t=Vht+c,L=∑t=1Tℓt(y^t)\mathbf h_t=\tanh\big(W\mathbf h_{t-1}+U\mathbf x_t+\mathbf b\big),\qquad\hat{\mathbf y}_t=V\mathbf h_t+\mathbf c,\qquad L=\sum_{t=1}^T\ell_t(\hat{\mathbf y}_t)
Unrolled in time, an RNN is a TT-layer feedforward network whose layers share WW, UU and b\mathbf b. It can map a sequence to a sequence or to a single label, or, as a language model, predict each next element.
DerivationBackpropagation through time
  1. ∂L∂ht=V⊤∂ℓt∂y^t+W⊤Dt+1∂L∂ht+1\frac{\partial L}{\partial\mathbf h_t}=V^\top\frac{\partial\ell_t}{\partial\hat{\mathbf y}_t}+W^\top D_{t+1}\frac{\partial L}{\partial\mathbf h_{t+1}}

    Backpropagate through the unrolled graph. The state ht\mathbf h_t affects the loss through its own output and through ht+1\mathbf h_{t+1}. With Dt=diag⁡(1−ht2)D_t=\operatorname{diag}(1-\mathbf h_t^2), the slope of tanh:

  2. ∂L∂W=∑t=1TDt∂L∂ht ht−1⊤,∂L∂U=∑t=1TDt∂L∂ht xt⊤\frac{\partial L}{\partial W}=\sum_{t=1}^TD_t\frac{\partial L}{\partial\mathbf h_t}\,\mathbf h_{t-1}^\top,\qquad\frac{\partial L}{\partial U}=\sum_{t=1}^TD_t\frac{\partial L}{\partial\mathbf h_t}\,\mathbf x_t^\top

    A shared weight receives the sum of its contributions at every step:

  3. ∂ht∂hk=∏j=k+1tDjW,∥∂ht∂hk∥≤∥W∥ t−k\frac{\partial\mathbf h_t}{\partial\mathbf h_k}=\prod_{j=k+1}^{t}D_jW,\qquad\Big\lVert\frac{\partial\mathbf h_t}{\partial\mathbf h_k}\Big\rVert\le\norm W^{\,t-k}

    Unrolling the recursion, the influence of hk\mathbf h_k on ht\mathbf h_t is a product of t−kt-k Jacobians. Since ∣tanh⁡′∣≤1\abs{\tanh'}\le1, its norm is at most a power of ∥W∥\norm W:

  4. ∥W∥=0.9:  0.950≈0.005,∥W∥=1.1:  1.150≈117\norm W=0.9:\ \ 0.9^{50}\approx0.005,\qquad\norm W=1.1:\ \ 1.1^{50}\approx117

    If ∥W∥<1\norm W<1, the gradient that a loss at time tt sends to step kk shrinks exponentially in t−kt-k, so long-range dependencies cannot be learned from it (Hochreiter, 1991; Bengio, Simard & Frasconi, 1994). If the largest singular value exceeds 1, the product can instead grow exponentially, and occasional huge gradients wreck training:

Exploding gradients are tamed by gradient clipping. Memory and computation grow with TT, so long sequences use truncated BPTT, backpropagating only KK steps into the past; that caps the cost, but also the span of dependencies the gradient can teach. Vanishing gradients need a change of architecture.

Predict before you look

With ∥W∥=0.9\norm W=0.9, after how many steps back in time does the bound ∥W∥ t−k\norm W^{\,t-k} on a hidden state's influence first fall below 1%?

Show the answer

44

0.9n<0.010.9^n<0.01 needs n>ln⁡100/ln⁡(1/0.9)≈43.7n>\ln100/\ln(1/0.9)\approx43.7, so 44 steps. A dependency 100 steps back is attenuated by up to 0.9100≈3×10−50.9^{100}\approx3\times10^{-5}: its gradient signal is buried under those of recent steps.

Gated memory: LSTM and GRU

The long short-term memory (Hochreiter & Schmidhuber, 1997) adds a cell state ct\mathbf c_t that is updated mostly by addition, with sigmoid gates deciding what to forget, what to write and what to reveal. With vt=[ht−1;xt]\mathbf v_t=[\mathbf h_{t-1};\mathbf x_t] stacked into one vector:

ft=σ(Wfvt+bf),it=σ(Wivt+bi),ot=σ(Wovt+bo),gt=tanh⁡(Wgvt+bg),ct=ft⊙ct−1+it⊙gt,ht=ot⊙tanh⁡(ct)\begin{aligned}\mathbf f_t&=\sigma(W_f\mathbf v_t+\mathbf b_f),\quad\mathbf i_t=\sigma(W_i\mathbf v_t+\mathbf b_i),\quad\mathbf o_t=\sigma(W_o\mathbf v_t+\mathbf b_o),\quad\mathbf g_t=\tanh(W_g\mathbf v_t+\mathbf b_g),\\\mathbf c_t&=\mathbf f_t\odot\mathbf c_{t-1}+\mathbf i_t\odot\mathbf g_t,\qquad\mathbf h_t=\mathbf o_t\odot\tanh(\mathbf c_t)\end{aligned}
Forget gate f\mathbf f, input gate i\mathbf i, output gate o\mathbf o, candidate g\mathbf g. The forget gate was added by Gers, Schmidhuber & Cummins (2000); the 1997 cell kept its content until overwritten.

Along the cell path, ∂ct/∂ct−1=diag⁡(ft)\partial\mathbf c_t/\partial\mathbf c_{t-1}=\operatorname{diag}(\mathbf f_t), plus terms through the gates. Error flowing back nn steps along this path is multiplied by a product of forget gates, which stays near 1 whenever they are open: there is no repeated multiplication by WW and no squashing derivative. Hochreiter and Schmidhuber called the original gate-free path the constant error carousel. Initializing the forget-gate bias near 1 keeps it running early in training (Gers et al., 2000; Jozefowicz, Zaremba & Sutskever, 2015).

The GRU (Cho et al., 2014) merges cell and hidden state and uses two gates, an update gate zt\mathbf z_t and a reset gate rt\mathbf r_t:

zt=σ(Wzvt+bz),rt=σ(Wrvt+br),h~t=tanh⁡(Wh[rt⊙ht−1;xt]+bh),ht=zt⊙ht−1+(1−zt)⊙h~t\mathbf z_t=\sigma(W_z\mathbf v_t+\mathbf b_z),\quad\mathbf r_t=\sigma(W_r\mathbf v_t+\mathbf b_r),\quad\tilde{\mathbf h}_t=\tanh\big(W_h[\mathbf r_t\odot\mathbf h_{t-1};\mathbf x_t]+\mathbf b_h\big),\quad\mathbf h_t=\mathbf z_t\odot\mathbf h_{t-1}+(1-\mathbf z_t)\odot\tilde{\mathbf h}_t
Cho et al.'s convention, in which zt≈1\mathbf z_t\approx1 keeps the old state; some libraries swap the roles of zt\mathbf z_t and 1−zt1-\mathbf z_t. The interpolation is again an additive path: the Jacobian ∂ht/∂ht−1\partial\mathbf h_t/\partial\mathbf h_{t-1} contains the direct term diag⁡(zt)\operatorname{diag}(\mathbf z_t).
CellGatesParameters (input size dd, state size nn)Memory path
Vanilla RNNnonen(n+d+1)n(n+d+1)multiplied by DtWD_tW at every step
LSTMforget, input, output4n(n+d+1)4n(n+d+1)cell ct\mathbf c_t, scaled by ft\mathbf f_t
GRUupdate, reset3n(n+d+1)3n(n+d+1)state ht\mathbf h_t, scaled by zt\mathbf z_t
Counts with one bias vector per gate; some libraries keep two. In empirical comparisons LSTMs and GRUs perform similarly, with no consistent winner (Chung et al., 2014; Jozefowicz et al., 2015).

Residual connections and very deep networks

Depth should not hurt: a deeper network can copy a shallower one and set its extra layers to the identity. Yet He et al. (2016) found that a plain 56-layer CNN had higher training error than a 20-layer one on CIFAR-10. That is not overfitting; the optimizer fails to find the deeper network's better solutions, the degradation problem. Their fix, the residual connection, makes the identity the default:

hl+1=hl+F(hl;θl)\mathbf h_{l+1}=\mathbf h_l+F(\mathbf h_l;\theta_l)
FF is typically two or three convolutions with batch normalization and ReLU. A block implements the identity by driving FF to zero, which is easy, instead of fitting an identity map with nonlinear layers, which is hard. Where the shapes change, the shortcut becomes a 1×11\times1 convolution with stride 2.
DerivationWhy gradients survive (He, Zhang, Ren & Sun, 2016)
  1. hL=hl+∑i=lL−1F(hi;θi)\mathbf h_L=\mathbf h_l+\sum_{i=l}^{L-1}F(\mathbf h_i;\theta_i)

    In the pre-activation form, where nothing follows the addition, unroll the recursion from block ll to the last block LL:

  2. ∂ℓ∂hl=∂ℓ∂hL(I+∂∂hl∑i=lL−1F(hi;θi))\frac{\partial\ell}{\partial\mathbf h_l}=\frac{\partial\ell}{\partial\mathbf h_L}\Big(I+\frac{\partial}{\partial\mathbf h_l}\sum_{i=l}^{L-1}F(\mathbf h_i;\theta_i)\Big)

    Differentiate: the gradient at block ll is the gradient at the top plus correction terms.

  3. plain:  JL−1⋯Jlresidual:  (I+JL−1)⋯(I+Jl)=I+∑iJi+∑i<jJjJi+⋯\text{plain: }\ J_{L-1}\cdots J_l\qquad\text{residual: }\ (I+J_{L-1})\cdots(I+J_l)=I+\sum_iJ_i+\sum_{i<j}J_jJ_i+\cdots

    The identity term carries ∂ℓ/∂hL\partial\ell/\partial\mathbf h_L to every block unchanged, so the gradient cannot vanish through a product of small factors, as it can in a plain network, where it is a product of L−lL-l layer Jacobians JiJ_i. Expanding the residual product writes it as a sum over paths of every length:

With residual connections He et al. trained 152-layer networks on ImageNet and networks of more than 1,000 layers on CIFAR-10. Residual connections, together with batch or layer normalization (Backpropagation & Optimization), are now part of nearly every deep architecture: transformers are stacks of residual attention and feed-forward blocks. The LSTM's cell update ct=ft⊙ct−1+it⊙gt\mathbf c_t=\mathbf f_t\odot\mathbf c_{t-1}+\mathbf i_t\odot\mathbf g_t is a gated residual connection through time, a link that highway networks made explicit across depth (Srivastava, Greff & Schmidhuber, 2015).

Key takeaways

  • A convolutional layer applies shared k×kk\times k kernels at every position (cross-correlation, in practice): Cout(Cink2+1)C_{\text{out}}(C_{\text{in}}k^2+1) parameters whatever the image size, output size ⌊(n+2p−k)/s⌋+1\lfloor(n+2p-k)/s\rfloor+1, and exact translation equivariance away from borders and strides.
  • Receptive fields grow by (kl−1)jl−1(k_l-1)j_{l-1} per layer, with strides and pooling multiplying the jump; stacks of 3×33\times3 kernels (VGG) see as far as large kernels with fewer weights.
  • An RNN shares weights across time. BPTT sums gradients over steps, and the products of Jacobians ∏jDjW\prod_jD_jW make long-range gradients vanish or explode.
  • LSTMs and GRUs add gated, additive memory paths whose Jacobians are diagonal gates near 1; residual connections h+F(h)\mathbf h+F(\mathbf h) do the same across depth, adding an identity term to every gradient.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A convolutional layer maps 64 input channels to 128 output channels with 3×33\times3 kernels and biases. How many parameters does it have, and how does that change if the input image doubles in width and height?

  1. 73,85673{,}856, unchanged when the image grows
  2. 73,85673{,}856, four times as many when the image grows
  3. 1,1521{,}152, unchanged
  4. 8,3208{,}320, unchanged
Show the answer

A. 73,85673{,}856, unchanged when the image grows

128⋅(64⋅9+1)=128⋅577=73,856128\cdot(64\cdot9+1)=128\cdot577=73{,}856. Weight sharing makes the count independent of the image size; only the computation and the activation memory grow, here fourfold.

Question 2

A 32×3232\times32 input passes through a 5×55\times5 convolution with stride 2 and padding 2. What is the spatial size of the output?

  1. 14×1414\times14
  2. 16×1616\times16
  3. 32×3232\times32
  4. 15×1515\times15
Show the answer

B. 16×1616\times16

⌊(32+2⋅2−5)/2⌋+1=⌊15.5⌋+1=16\lfloor(32+2\cdot2-5)/2\rfloor+1=\lfloor15.5\rfloor+1=16. Padding p=⌊k/2⌋p=\lfloor k/2\rfloor would preserve the size at stride 1; stride 2 halves it.

Question 3

Why do vanilla RNNs struggle to learn dependencies that span hundreds of time steps?

  1. They have too few parameters to store long sequences
  2. Backpropagation through time is not exact for recurrent networks
  3. The gradient linking distant steps is a product of many Jacobians DjWD_jW, which typically shrinks (or grows) exponentially with the time gap
  4. The tanh activation cannot represent long-range functions
Show the answer

C. The gradient linking distant steps is a product of many Jacobians DjWD_jW, which typically shrinks (or grows) exponentially with the time gap

∂ht/∂hk=∏jDjW\partial\mathbf h_t/\partial\mathbf h_k=\prod_jD_jW, bounded by ∥W∥t−k\norm W^{t-k} since ∣tanh⁡′∣≤1\abs{\tanh'}\le1. With ∥W∥<1\norm W<1 the contributions of distant steps vanish exponentially; with large singular values they can explode. Gating (LSTM, GRU) adds a path along which the factors stay near 1.

Question 4

In an LSTM, what is ∂ct/∂ct−1\partial\mathbf c_t/\partial\mathbf c_{t-1} along the cell-state path, ignoring the paths through the gates?

  1. WfW_f
  2. diag⁡(ft)\operatorname{diag}(\mathbf f_t)
  3. diag⁡(1−ct2) W\operatorname{diag}(1-\mathbf c_t^2)\,W
  4. diag⁡(ot)\operatorname{diag}(\mathbf o_t)
Show the answer

B. diag⁡(ft)\operatorname{diag}(\mathbf f_t)

ct=ft⊙ct−1+it⊙gt\mathbf c_t=\mathbf f_t\odot\mathbf c_{t-1}+\mathbf i_t\odot\mathbf g_t, so the direct dependence is elementwise multiplication by the forget gate. Over nn steps the error is scaled by a product of forget gates, which stays near 1 when they are open, with no weight matrix and no squashing derivative in the product.

Question 5

A plain 56-layer CNN reaches a higher training error than a plain 20-layer CNN on the same data. What is the most likely explanation?

  1. The deeper network overfits
  2. The deeper network cannot represent the shallower one's function
  3. The training set is too small for 56 layers
  4. Optimization: gradient methods fail to find the deeper network's good solutions, which residual connections fix by making identity blocks easy
Show the answer

D. Optimization: gradient methods fail to find the deeper network's good solutions, which residual connections fix by making identity blocks easy

Overfitting would raise test error, not training error. The deep network can represent everything the shallow one can, with the extra layers set to the identity, so the gap is an optimization failure, the degradation problem. With h+F(h)\mathbf h+F(\mathbf h) blocks, He et al. trained deeper networks to lower training and test error.

Go deeper

Further reading

  • Y. LeCun, L. Bottou, Y. Bengio & P. Haffner, "Gradient-based learning applied to document recognition," Proceedings of the IEEE 86(11) (1998).
  • S. Hochreiter & J. Schmidhuber, "Long short-term memory," Neural Computation 9(8) (1997).
  • K. He, X. Zhang, S. Ren & J. Sun, "Deep residual learning for image recognition," CVPR (2016).
  • I. Goodfellow, Y. Bengio & A. Courville, Deep Learning, chs. 9–10 (MIT Press, 2016).