Convolutional Neural Networks, machine learning lesson

A small grid of pixel intensities contains an edge, and the same kind of edge could appear in any part of the image. A dense layer gives every pixel its own weight for every unit, so what it learns about a pattern in one corner does not carry over to the same pattern in another corner. A convolutional layer instead applies one small set of weights at every position and records how strongly each patch matches. This lesson computes that operation by hand, derives the output size from stride and padding, follows the part of the image each unit can see, and counts the parameters of a compact image classifier.

Key terms

Convolution

Definition Let $X$ be a single-channel input with $n_h$ rows and $n_w$ columns, and let $K$ be a $k \times k$ array of weights with $k \le n_h$ and $k \le n_w$ . With indices starting at 0, stride 1, no padding and no bias, the operation that deep learning libraries call a convolution produces

Y_{ij} = \sum_{u=0}^{k-1} \sum_{v=0}^{k-1} K_{uv}\, X_{i+u,\, j+v}

for $0 \le i \le n_h - k$ and $0 \le j \le n_w - k$ . In mathematical terms this is cross-correlation. The convolution of signal processing and analysis first flips the filter in both spatial directions, so on the same positions it uses $K_{k-1-u,\, k-1-v}$ in place of $K_{uv}$ . When the weights are learned, both conventions describe the same family of layers, because training simply finds the flipped filter. A calculation by hand, or a filter copied from another source, has to follow the convention of the implementation that will use it.

In plain words Lay the filter over one patch, multiply the entries that sit on top of each other, and add the products. Then move the filter and do the same with the same weights. Each output number answers how strongly one patch matches the filter.

Example Take the constructed $4 \times 4$ image of dimensionless intensities and the $3 \times 3$ filter that adds the left column of a patch and subtracts the right column.

\begin{gathered} X = \begin{bmatrix} 1 & 2 & 0 & 1 \\ 0 & 1 & 3 & 2 \\ 2 & 0 & 1 & 1 \\ 1 & 2 & 2 & 0 \end{bmatrix}, \\[0.4em] K = \begin{bmatrix} 1 & 0 & -1 \\ 1 & 0 & -1 \\ 1 & 0 & -1 \end{bmatrix} \end{gathered}

At the upper left position the left column of the patch sums to $1 + 0 + 2 = 3$ and the right column to $0 + 3 + 1 = 4$ , so $Y_{00} = 3 - 4 = -1$ . Flipping this filter in both directions gives exactly $-K$ , so the flipped convention would report $+1$ at the same position.

Filter and feature map

Definition A filter, also called a kernel, is the array of weights that a convolutional layer applies at every position, together with one bias $b$ . For an input with $C_{\text{in}}$ channels, such as the three color channels of an image, a filter has shape $C_{\text{in}} \times k \times k$ , and with stride 1 and no padding its output is

\begin{aligned} Y_{ij} &= b + \sum_{c=1}^{C_{\text{in}}} \sum_{u=0}^{k-1} \sum_{v=0}^{k-1} \\[0.4em] &\qquad K_{cuv}\, X_{c,\, i+u,\, j+v} . \end{aligned}

The two-dimensional array $Y$ produced by one filter is a feature map. A layer with $C_{\text{out}}$ filters produces $C_{\text{out}}$ feature maps, which form the output channels, and it has $C_{\text{out}}(k^2 C_{\text{in}} + 1)$ parameters whatever the height and width of the input. An activation such as ReLU is usually applied to every entry afterward, and many texts also call the activated array a feature map.

In plain words A filter is a pattern detector of fixed size whose weights are learned, and its feature map is the grid of its scores across the image. A filter always reads every input channel at once, so its depth matches the input. The sign of a score carries meaning too, since a negative response to one pattern is a positive response to the opposite pattern.

Example Sliding the filter $K$ over all four legal positions of $X$ , with bias 0, gives the feature map

Y = \begin{bmatrix} -1 & -1 \\ -3 & 0 \end{bmatrix} .

The negative entries mark patches whose right column is brighter than their left column. ReLU would set all four entries to 0, which does not make the filter useless. The filter $-K$ gives the map with entries $1$ , $1$ , $3$ and $0$ , so a layer containing both filters keeps both orientations after ReLU.

Stride and padding

Definition The stride $s$ is the step, in input positions, between neighboring placements of the filter. The padding $p$ is the number of rows and columns of fixed values, usually zeros, added on each side of the input before filtering. The dilation, the spacing between neighboring filter entries, is 1 on this page, so a filter reads adjacent positions. Along one side of length $n$ , with filter size $k$ and $n + 2p \ge k$ , the number of output positions is

n_{\text{out}} = \left\lfloor \frac{n + 2p - k}{s} \right\rfloor + 1 .

The formula is applied separately to height and width. The floor drops placements that would extend past the padded input, so with a stride above 1 some border rows or columns may never be read. With stride 1 and an odd $k$ , padding $p = (k - 1)/2$ keeps the side length unchanged. The number of output channels equals the number of filters, and neither stride nor padding changes the parameter count.

In plain words Padding lets the filter be centered on pixels near the edge, and stride decides how many positions are skipped between placements. Padded values are part of the computation that someone chose, not an observed continuation of the image. The output size should be derived before it is flattened or passed to the next layer, not read off a diagram.

Example In the image above, $n = 4$ , $k = 3$ , $p = 0$ and $s = 1$ give $\lfloor 1/1 \rfloor + 1 = 2$ positions per side, the $2 \times 2$ map already found. A $7 \times 7$ input with a $3 \times 3$ filter, padding 1 and stride 2 gives $\lfloor 6/2 \rfloor + 1 = 4$ positions per side. A side of length 10 with $k = 3$ , $p = 0$ and $s = 2$ gives $\lfloor 7/2 \rfloor + 1 = 4$ placements, starting at positions 0, 2, 4 and 6, so they cover positions 0 through 8 and the last position is never read.

Receptive field

Definition The receptive field of a unit is the set of input positions whose values can affect that unit’s value. For a stack of convolution and pooling layers with dilation 1, where layer $l$ has window size $k_l$ and stride $s_l$ , its side length $r_l$ follows from

\begin{gathered} r_l = r_{l-1} + (k_l - 1)\, j_{l-1}, \\[0.4em] j_l = j_{l-1}\, s_l, \end{gathered}

starting from $r_0 = 1$ and $j_0 = 1$ . Here $j_l$ is the distance, in input pixels, between neighboring units of layer $l$ . For $L$ stacked layers with $k \times k$ filters and stride 1 this gives $r_L = 1 + L(k - 1)$ . Near a border, part of the receptive field can lie on padding rather than on the image.

In plain words Each layer looks at a small window of the layer below, and a window of windows covers more of the original image. A stride or a pooling step spreads later units apart, so after it every extra layer widens the view faster. The receptive field says which pixels can matter. How much each one matters depends on the weights, and pixels near the center usually reach the unit through more paths than pixels at the edge.

Example One $3 \times 3$ layer with stride 1 sees a $3 \times 3$ patch. A second such layer combines a $3 \times 3$ block of first-layer units, whose patches together span $3 + 2 = 5$ pixels per side, so it sees a $5 \times 5$ patch, and a third sees $7 \times 7$ . If the first layer has stride 2 instead, neighboring first-layer units are 2 pixels apart and the second layer sees $3 + 2 \cdot 2 = 7$ pixels per side after only two layers.

Pooling

Definition A pooling layer replaces each window of a feature map by a fixed summary, computed separately in every channel. Max pooling keeps the largest value in the window, and average pooling keeps the arithmetic mean. A pooling layer has a window size and a stride, often a $2 \times 2$ window with stride 2, its output size follows the same formula as a convolution, and it has no learned parameters. It leaves the number of channels unchanged. During backpropagation, max pooling passes the gradient only to the entry that attained the maximum, with ties broken by the implementation’s rule, and average pooling shares it equally among the window’s entries.

In plain words Pooling shrinks a map by keeping one summary per neighborhood. It lowers the resolution and makes the result insensitive to some small shifts inside a window. It does not make a network invariant to every shift, and it throws away where in the window a response occurred.

Example A $2 \times 2$ window with responses 1, 4, 2 and 3 gives 4 under max pooling and 2.5 under average pooling. In one dimension, max pooling with window 2 and stride 2 sends the row $(0, 5, 0, 0)$ to $(5, 0)$ . Shifting the row one step left to $(5, 0, 0, 0)$ gives $(5, 0)$ again, but shifting it one step right to $(0, 0, 5, 0)$ gives $(0, 5)$ . A shift that crosses a window boundary changes the pooled output.

Convolutional neural network

Definition A convolutional neural network, or CNN, is a neural network in which some layers are convolutional, so that each unit is connected to a local window of the previous layer and the same filter weights are used at every position. A basic image classifier repeats convolution followed by an activation, reduces the spatial size with pooling or with strides, flattens the final maps into a vector, and ends with a dense layer that outputs one logit per class. Training usually minimizes the average cross-entropy on the training data with gradients from backpropagation, and because a filter weight is used at every position, its gradient adds the contributions of all positions,

\frac{\partial L}{\partial K_{uv}} = \sum_{i,\, j} \frac{\partial L}{\partial Y_{ij}}\, X_{i+u,\, j+v} ,

shown here for one channel, stride 1 and no padding.

In plain words Local connections and shared weights build in the assumption that useful patterns are small and can appear anywhere in the image. That assumption is why a convolutional layer has far fewer parameters than a dense layer with the same numbers of inputs and outputs, and it helps only when it suits the task. A strong response from a filter is a fact about the model’s computation, not proof that the model sees an image the way a person does. A network can find shortcuts such as backgrounds, watermarks or the camera used, so evaluation needs data split by independent subjects or sources and a look at the mistakes.

Example Take an $8 \times 8$ single-channel input and four $3 \times 3$ filters with padding 0 and stride 1. They give four $6 \times 6$ feature maps with $4(9 + 1) = 40$ parameters. ReLU keeps the shape, and $2 \times 2$ max pooling with stride 2 gives four $3 \times 3$ maps. Flattening gives 36 numbers, and a dense layer to two class logits adds $36 \cdot 2 + 2 = 74$ parameters, for 114 in total. For a comparison of sharing, a convolutional layer with three input channels, six $3 \times 3$ filters, padding 0 and stride 1 maps a $7 \times 7 \times 3$ input to $5 \times 5 \times 6 = 150$ outputs with $6(27 + 1) = 168$ parameters. A dense layer from the same 147 inputs to 150 outputs needs $147 \cdot 150 = 22{,}050$ weights before its biases.

Check yourself

Apply the filter $B$ to the input $A$ with the library convention, stride 1, no padding and bias 0. Then repeat the calculation with the filter flipped in both directions, and apply $2 \times 2$ max pooling to the first result.

\begin{gathered} A = \begin{bmatrix} 1 & 0 & 2 \\ 3 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix}, \\[0.4em] B = \begin{bmatrix} 1 & -1 \\ 0 & 2 \end{bmatrix} \end{gathered}

Show the answer

The output has $3 - 2 + 1 = 2$ positions per side. At the upper left the patch has entries 1, 0, 3 and 1, so the response is $1 \cdot 1 + 0 \cdot (-1) + 3 \cdot 0 + 1 \cdot 2 = 3$ . The other three patches give $-2$ , $6$ and $3$ in the same way, so the feature map has rows $(3, -2)$ and $(6, 3)$ .

Flipping $B$ in both directions gives rows $(2, 0)$ and $(-1, 1)$ . Repeating the sums with that filter gives rows $(0, -1)$ and $(8, 1)$ , a different map, so a hand calculation has to state which convention it uses.

Max pooling over the whole $2 \times 2$ map of the library convention keeps its largest entry, 6.

An input of size $32 \times 32 \times 3$ , written height, width, channels, goes through a layer of 16 filters of size $5 \times 5$ with padding 2, stride 1 and one bias per filter. Find the output shape and the number of parameters. A classmate counts $16(25 + 1) = 416$ parameters. What did they miss, and what changes if the stride is 2?

Show the answer

Each side gives $\lfloor (32 + 4 - 5)/1 \rfloor + 1 = 32$ positions, and there is one output channel per filter, so the output is $32 \times 32 \times 16$ .

Each filter reads all three input channels, so it has $5 \cdot 5 \cdot 3 = 75$ weights and one bias. The layer has $16 \cdot 76 = 1{,}216$ parameters. The classmate counted a single channel per filter.

With stride 2 each side gives $\lfloor 31/2 \rfloor + 1 = 16$ positions, so the output is $16 \times 16 \times 16$ . The parameter count stays 1,216, because the same filters are used and only the number of placements changes. For contrast, a dense layer from the 3,072 inputs to the 16,384 outputs of the stride 1 case would need $3{,}072 \cdot 16{,}384 = 50{,}331{,}648$ weights.

A network applies a $3 \times 3$ convolution with stride 1, then $2 \times 2$ max pooling with stride 2, then another $3 \times 3$ convolution with stride 1, all with dilation 1. How large is the receptive field of a unit in the last layer? A classmate adds $k_l - 1$ for every layer, as in a stack with stride 1, and gets $1 + 2 + 1 + 2 = 6$ . Why is that wrong?

Show the answer

Start from $r_0 = 1$ and $j_0 = 1$ . The first convolution gives $r_1 = 1 + 2 \cdot 1 = 3$ with $j_1 = 1$ . The pooling layer gives $r_2 = 3 + 1 \cdot 1 = 4$ , and its stride makes $j_2 = 2$ . The second convolution gives

r_3 = 4 + (3 - 1) \cdot 2 = 8 ,

so the receptive field is $8 \times 8$ pixels, away from the borders.

The classmate’s sum treats every layer as if neighboring units were one pixel apart. After the pooling stride, neighboring pooled units are 2 pixels apart in the image, so each extra step of the last filter reaches 2 pixels further, not 1.

Convolutional Neural Networks

Key terms

Convolution

Filter and feature map

Stride and padding

Receptive field

Pooling

Convolutional neural network

Check yourself

How this lesson connects

Builds on

Used later in