Convolutions and vision

The operation

Given an image $I$ and a $k\times k$ kernel $K$, the output (without padding) at position $(i,j)$ is

Technically this is cross-correlation; mathematical convolution flips the kernel, but in deep learning the kernel is learned and the distinction does not matter (Goodfellow et al., 2016, ch. 9). With an $n\times n$ image, no padding ($p=0$), and stride 1, the output is $n-k+1$ per side; with stride $s$ and padding $p$ (rows and columns of zeros around the border): $\lfloor (n+2p-k)/s \rfloor + 1$ (Dumoulin and Visin, 2016). Quiz example: $28\times28$ with $k=3$ gives $26\times26$; with $p=1$ the size stays $28\times28$.

Parameters: fully connected versus convolutional

A fully connected layer from $10^4$ inputs to $10^3$ neurons has $10^7$ weights (plus biases). A convolutional layer with $C_{out}$ kernels of $k\times k$ over $C_{in}$ channels has

parameters, independent of the image size. With $C_{in}=1$, $k=3$ and 16 kernels: $16\cdot(9+1)=160$.

The hook’s comparison (10 million versus 10) sets a single kernel against a thousand neurons, and one kernel produces a single map. With 1,000 $3\times3$ kernels on the same $100\times100$ image (no padding) there are $1{,}000\cdot(9+1)=10{,}000$ parameters, a thousand times fewer than $10^7$; but the output is 1,000 maps of $98\times98$ (9,604,000 values) and $98^2\cdot 9\cdot 1{,}000\approx 86$ million multiplications, more than the dense layer’s 10 million. Sharing weights saves parameters (and the data needed to fit them), not operations: it does not change the order of the forward-pass running time, only the memory for the parameters (Goodfellow et al., 2016, §9.2).

Where the idea comes from

Fukushima’s neocognitron (1980) already combined layers of local feature detectors with layers tolerant to shifts, but it was trained with a self-organizing rule, without supervision: it lacked an end-to-end supervised algorithm such as backpropagation (LeCun, Bengio, and Hinton, 2015; Goodfellow et al., 2016, §9.10). LeCun et al. (1989) trained with backpropagation a network with shared weights to recognize handwritten zip code digits provided by the U.S. Postal Service: 9,298 already-segmented digits (7,291 for training, 2,007 for testing) in $16\times16$ images. Its 64,660 connections were controlled by 9,760 independent parameters, and the error was 0.14% on the training set (10 mistakes) and 5.0% on the test set (102 mistakes); a fully connected network with 40 hidden units, tried as a comparison, reached 8.1% on the test set. That network did not use pooling, but convolutions that jumped two pixels at a time. LeNet-5 (LeCun et al., 1998) has 7 layers, a $32\times32$ input, $5\times5$ kernels, 340,908 connections, and about 60,000 free parameters; its “sub-sampling” averages each $2\times2$ block (with a trainable coefficient and bias) instead of taking the maximum.

The lesson’s kernel

The lesson’s edge kernels are those of the Sobel operator (OpenCV documentation, “Sobel Derivatives”). The vertical-edge kernel is

Its magnitude $\sqrt{(K_x * I)^2 + (K_y * I)^2}$ estimates edge strength (same source). Here the kernels are chosen by hand to show the operation; in a trained network they are learned, and in the first layers they tend to resemble oriented-edge detectors and color blobs (Krizhevsky et al., 2012, fig. 3; Yosinski et al., 2014).

Receptive field and hierarchy

Each layer sees a larger region of the original image. With $r_L=1$ at the last layer, the receptive field satisfies $r_{l-1}=s_l\,r_l+(k_l-s_l)$ (Araujo, Norris, and Sim, 2019): two stacked $3\times3$ convolutions “see” $5\times5$; with a $2\times2$ pooling in between ($3\times3$, pooling, $3\times3$) they see $8\times8$, and a unit of the lesson’s example network, after its two poolings, sees $10\times10$ pixels. That is why early layers detect local patterns (edges, colors) and deep layers detect broad combinations.

In an AlexNet-type network, Zeiler and Fergus (2014) visualized what excites each layer: layer 2 responds to corners and edge/color conjunctions; layer 3, to textures and more complex patterns; layer 4, to class-specific parts (dog faces); layer 5, to whole objects with significant pose variation. LeCun, Bengio, and Hinton (2015) summarize it as edges, motifs, parts, and objects, and stress that these layers of features are not designed by human engineers: they are learned from data. What a person does design is the architecture (how many layers, what kernel size, where the pooling goes).

Pooling and shifts

$2\times2$ max pooling with stride 2 halves the map per side and makes the output approximately invariant to small shifts (Goodfellow et al., 2016, §9.3; LeCun, Bengio, and Hinton, 2015). It is only approximate: in the scene, shifting the image by one pixel changes the edge map by 56% (sum of absolute differences over the sum of absolute values) and after pooling by 19%; with 400 random-stripe images, the mean change drops from 0.97 to 0.50 and in 50 of the 400 pooling does not reduce it (script verify-data.ts). Azulay and Weiss (2019) show that in full networks shifting or rescaling the image a little can change the prediction a lot. In the scene, pooling takes the maximum of the absolute value; in a real network the activation (for example ReLU) comes first.

The limits, with numbers

• Textures. Geirhos et al. (2019) showed ImageNet-trained networks images with the shape of one object and the texture of another. When forced to choose, ResNet-50 answered by texture 77.9% of the time (VGG-16, 82.8%; GoogLeNet, 68.8%; AlexNet, 57.1%); people chose shape in 95.9% of their correct decisions. With the same architecture, training on a “stylized” version of ImageNet changed that bias: it depends on the data and the task, not only on convolution.
• Nearly invisible changes. Szegedy et al. (2014) found hardly perceptible perturbations that change the class a network predicts. Goodfellow, Shlens, and Szegedy (2015) took GoogLeNet’s answer on a photo of a panda from “panda” (57.7% confidence) to “gibbon” (99.3%) by adding a perturbation of magnitude 0.007, the smallest bit of an 8-bit image.
• Data unlike the training data. Recht et al. (2019) rebuilt ImageNet test sets with the same procedure and model accuracy dropped by 11% to 14%. Beery et al. (2018): with wildlife camera traps, good performance where it was trained and poor generalization to new places. Hendrycks and Dietterich (2019): ImageNet-C applies 75 alterations (15 types at 5 intensities, including brightness, contrast, fog, and noise), and relative robustness barely improved from AlexNet to ResNet.
• Scenes. Goodfellow et al. (2016, §9.10) note that the human visual system does much more than recognize objects (it understands entire scenes, relationships between objects, and 3D geometry) and that applications of convolutional networks to those problems were then in their infancy.

Reusing an already trained model

Yosinski et al. (2014) measured what can be reused: first-layer features (such as Gabor filters and color blobs) do not depend on the task or the data, while last-layer features do. He, Girshick, and Dollár (2018, technical report) compared, in object detection on COCO, starting from a model pre-trained on ImageNet versus training from scratch: pre-training speeds up convergence, but with enough iterations training from scratch matched the accuracy, even with 10% of the data; only with very little data (fewer than about 10,000 COCO images) did pre-training clearly improve the result.

In code

import numpy as np

def conv2d(img, K, b=0.0):
    k = K.shape[0]
    h, w = img.shape[0] - k + 1, img.shape[1] - k + 1
    out = np.zeros((h, w))
    for i in range(h):
        for j in range(w):
            out[i, j] = b + np.sum(K * img[i:i + k, j:j + k])
    return out

Kx = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]])
img = np.zeros((6, 6)); img[:, 3:] = 1          # half dark, half bright: a vertical edge
print(conv2d(img, Kx))                           # values 4 in the edge columns, 0 elsewhere

What comes next

Backpropagation from lesson 8 trains the kernels like any other weight. Convolutional networks came to dominate vision from 2012 on (lesson 13); LeCun, Bengio, and Hinton (2015) describe them as the dominant approach for almost all recognition and detection tasks. For sequential data such as language, another idea is needed (lesson 12).