Convolutions

Advanced

Introduction

A fully connected layer on a 200 × 200 colour image would need 120,000 weights per neuron, and it would have to learn separately that a cat's ear looks the same at the top left and at the bottom right. Convolutions fix both problems: a small kernel of weights, perhaps 3 × 3, slides across the image and is applied at every position. Convolutional networks (CNNs) brought deep learning its first big successes in image recognition and remain central to vision.

How it works

In deep learning, "convolution" means cross-correlation: put the kernel over a patch of the input, multiply matching entries and add them up. That sum is one output. Move the kernel one step and repeat. In one dimension, with input x and kernel w of length k:

out[i] = Σⱼ x[i + j] · w[j]

In two dimensions the kernel is a small grid and the sum runs over its rows and columns. The outputs form a feature map: large where the input matches the kernel's pattern. A kernel such as [[1, 0, −1], [1, 0, −1], [1, 0, −1]] responds to vertical edges, where brightness changes from left to right.

The output size depends on three choices:

  • kernel size k: a valid convolution of n inputs gives n − k + 1 outputs;
  • padding p: adding p zeros on every side lets the kernel cover the edges;
  • stride s: moving s positions at a time shrinks the output.

Output size = ⌊(n + 2p − k) / s⌋ + 1 in each direction.

Real layers have several input channels (red, green, blue, or the previous layer's feature maps) and several kernels, one per output feature map. Each kernel spans all input channels.

Training needs gradients. If dY is the gradient of the loss with respect to the outputs, then each kernel weight's gradient adds up dY times the input value that weight touched, over every position: dK[a][b] = Σᵢⱼ dY[i][j] · X[i + a][j + b]. Each input value's gradient adds up dY times the kernel weights it met: the kernel is "stamped" back onto the input, scaled by each output's gradient.

Syntax

def conv2d(x, k):
    kh, kw = len(k), len(k[0])
    return [[sum(x[i + a][j + b] * k[a][b] for a in range(kh) for b in range(kw))
             for j in range(len(x[0]) - kw + 1)]
            for i in range(len(x) - kh + 1)]

Example

image = [
    [0, 0, 0, 9, 9, 9],
    [0, 0, 0, 9, 9, 9],
    [0, 0, 0, 9, 9, 9],
    [9, 9, 9, 9, 9, 9],
    [9, 9, 9, 9, 9, 9],
]
vertical = [[1, 0, -1], [1, 0, -1], [1, 0, -1]]
horizontal = [[1, 1, 1], [0, 0, 0], [-1, -1, -1]]


def convolve(img, kernel, padding=0, stride=1):
    if padding:
        width = len(img[0]) + 2 * padding
        img = [[0] * width] * padding + [[0] * padding + row + [0] * padding for row in img] + [[0] * width] * padding
    k = len(kernel)
    rows = (len(img) - k) // stride + 1
    cols = (len(img[0]) - k) // stride + 1
    return [
        [
            sum(img[r * stride + a][c * stride + b] * kernel[a][b] for a in range(k) for b in range(k))
            for c in range(cols)
        ]
        for r in range(rows)
    ]


for name, kernel in [("vertical edges", vertical), ("horizontal edges", horizontal)]:
    print(name + ":")
    for row in convolve(image, kernel):
        print("   ", " ".join(f"{v:4}" for v in row))
out = convolve(image, vertical, padding=1, stride=2)
print(f"with padding 1 and stride 2 the output is {len(out)} x {len(out[0])}")
Open in compiler

Line by line

  1. The image is dark (0) on the top left and bright (9) elsewhere.
  2. The vertical-edge kernel gives large values (here negative) only where brightness changes from left to right, at the boundary in the top rows.
  3. The horizontal-edge kernel responds where brightness changes from top to bottom, at the boundary in the left columns.
  4. Where the image is flat, every output is 0: the kernel's weights add up to zero.
  5. With padding 1 and stride 2, the 5 × 6 image gives a 3 × 3 output, as the size formula predicts.

Expected result

vertical edges:
       0  -27  -27    0
       0  -18  -18    0
       0   -9   -9    0
horizontal edges:
       0    0    0    0
     -27  -18   -9    0
     -27  -18   -9    0
with padding 1 and stride 2 the output is 3 x 3

In the real world

The first layers of trained image networks learn kernels that look like edge and colour detectors, much like the hand-made ones here; deeper layers combine them into textures, parts and objects. Convolutions also process audio, where the kernel slides along time, and they are used inside some language and speech models. Phone cameras run small CNNs for face detection and image enhancement.

Common mistakes

  • Flipping the kernel: deep learning "convolution" does not flip it.
  • Getting the output size wrong by forgetting padding or stride.
  • Mixing up rows and columns of a non-square kernel.
  • Forgetting that a kernel spans all input channels, so its weight count is k × k × channels.

Best practices

  • Write the output size down before coding, using the formula.
  • Test a convolution on an image with a single bright pixel: the output shows the kernel.
  • Use small kernels (3 × 3) stacked in several layers rather than one large kernel.

Summary

A convolution slides a small kernel across the input and sums the products at each position, producing a feature map that responds to a local pattern. Padding and stride control the output size, ⌊(n + 2p − k) / s⌋ + 1. Weight sharing keeps the number of weights small, and gradients for the kernel and input are sums of output gradients times inputs and kernel weights.

Quick check

1. How many outputs does a valid convolution of 10 inputs with a kernel of 3 give?
2. What is the output width for width 32, kernel 5, padding 2, stride 1?
3. What does weight sharing mean in a convolution layer?
4. Where does a vertical-edge kernel give large outputs?

Key takeaways

  • Each output is the sum of the kernel times the patch of input under it.
  • Output size = (input + 2 × padding − kernel) / stride + 1, rounded down.
  • A convolution layer has very few weights because the same kernel is used everywhere.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.