Convolutional Networks

An image classifier should recognize an edge in different parts of an image. A convolutional layer applies the same small filter at each position, sharing weights across the image. We will derive this operation and examine how its output changes when the input shifts.

How can a network recognize the same pattern at different image positions?


Shared Filters

For a signal \(\mathbf x\in\mathbb R^n\) and an integer kernel width \(1\leq k\leq n\), a dense map to \(n-k+1\) outputs uses \(n(n-k+1)\) weights. A convolution learns one kernel \(\mathbf w\in\mathbb R^k\) and slides it across the signal: \[ y_i=\sum_{j=1}^k w_jx_{i+j-1}, \qquad i=1,\ldots,n-k+1. \] This construction imposes two constraints:

  • local connectivity: output \(i\) sees only the \(k\) inputs in its window.
  • weight sharing: the same kernel weights are used at every location.

A three-entry kernel is reused in each valid window of an eight-entry signal. The six matrix rows place the same coefficients at successive positions.

Each output position uses one input window and the same kernel coefficients, shown in the corresponding matrix row. The repeated coefficients connect local computation to the full linear map.

The operation is still a linear layer \(\mathbf y=\mathbf C\mathbf x\), with \(\mathbf C\in\mathbb R^{(n-k+1)\times n}\) and entries \[ C_{i,j}=\begin{cases} w_{j-i+1},&i\leq j<i+k,\\ 0,&\text{otherwise}. \end{cases} \] Locality forces the zeros. Sharing forces repeated entries along diagonals. The matrix has \(n(n-k+1)\) positions but only \(k\) free parameters. Learning an edge detector in one part of the signal therefore learns it everywhere.

Moving from one output row to the next shifts the nonzero entries while preserving their values. Locality determines which connections exist. Sharing determines which weights remain equal.

For an image, the window becomes a small square and its responses form a feature map. A layer learns several kernels in parallel, producing channels for the next layer. The number of free parameters depends on kernel size and channel counts rather than image width and height.

Learning chooses the kernel entries, while the architecture chooses which entries are tied. Backpropagation combines evidence for one shared weight from every location where it was used.

Weight sharing is both a parameter saving and an assumption that translated appearances provide evidence about the same feature. It can be too restrictive when meaning depends on absolute location.

Receptive Fields

Locality saves parameters, but one layer cannot immediately combine distant evidence. Depth supplies that reach. The receptive field of an output is the set of original inputs that can influence it.

A later layer combines neighboring outputs whose input windows overlap. Their union reaches farther than any single window.

A second local layer combines overlapping first-layer windows, expanding the set of inputs that can influence one output.

The receptive-field width depends on both kernel width and depth.

Claim: On an unbounded signal with stride one, no dilation, integer \(k\geq1\), and integer \(L\geq0\), the maximum receptive-field width after \(L\) width-\(k\) layers is \[ 1+L(k-1). \]

Proof

Before any convolution, one representation depends on one input, so \(R^{(0)}=1\). If an output after \(l\) layers can depend on a contiguous block of width \(R^{(l)}\), the next width-\(k\) layer reads \(k\) adjacent such outputs. Consecutive blocks start one input position apart, so their union begins with the first block and extends \(k-1\) positions beyond it. Therefore \[ R^{(l+1)}=R^{(l)}+(k-1). \] Starting from \(R^{(0)}=1\) and applying the recurrence \(L\) times gives \(R^{(L)}=1+L(k-1)\). This proves the formula.

If a decision needs evidence separated by more than \(L(k-1)\) positions, an \(L\)-layer width-\(k\) stack has no path that can combine it.

The receptive field contains inputs that can affect the output. An input inside the field may have little effect after learned weights and nonlinearities. An input outside it has no computational path to the output. Distant interactions can therefore require many local layers.

Translation Equivariance

Weight sharing has a mathematical consequence. If the input shifts by one position, every local window shifts by one position and the output shifts with it. This is translation equivariance: \[ \operatorname{Conv}(\operatorname{Shift}(\mathbf x)) =\operatorname{Shift}(\operatorname{Conv}(\mathbf x)). \] Equivariance means the representation moves predictably with the input. It differs from invariance, in which the final answer does not move at all. A classifier can obtain approximate shift invariance later by pooling or averaging spatial responses, but the convolutional layers first preserve where a feature was found.

Segmentation usually needs equivariance because shifting an object should shift its predicted mask. Classification often seeks invariance because the final label should remain unchanged.

Boundaries require a convention because an ordinary shift can discard data. Circular indexing temporarily removes that ambiguity, so the following result isolates what weight sharing itself guarantees before a padding rule complicates the edges.

Claim: With circular wraparound, a shared convolution \(\mathbf C\) commutes with every integer shift \(\mathbf S_q\): \[ \mathbf C\mathbf S_q=\mathbf S_q\mathbf C. \]

Proof

Index a length-\(n\) signal modulo \(n\), so \(x_{i+n}=x_i\) for every integer \(i\). For any integer \(q\), define the circular shift by \((\mathbf S_q\mathbf x)_i=x_{i-q}\) for \(i=1,\ldots,n\). The circular convolution has \(n\) outputs and is a weighted sum of shifts: \[ \mathbf C=\sum_{j=1}^k w_j\mathbf S_{1-j}, \qquad \mathbf C,\mathbf S_q\in\mathbb R^{n\times n}, \] because \((\mathbf S_{1-j}\mathbf x)_i=x_{i+j-1}\). Shifts commute: for any integers \(p,q\), composing them adds their offsets, so \(\mathbf S_p\mathbf S_q=\mathbf S_{p+q}=\mathbf S_q\mathbf S_p\). Distributing through the finite sum therefore gives \[ \begin{aligned} \mathbf C\mathbf S_q &=\sum_{j=1}^k w_j\mathbf S_{1-j}\mathbf S_q\\ &=\sum_{j=1}^k w_j\mathbf S_q\mathbf S_{1-j} =\mathbf S_q\mathbf C. \end{aligned} \] Weight sharing makes the coefficients \(w_j\) independent of position, which is what lets convolution use this fixed combination of shifts.

The comparison below uses a circular input shift in both cases.

A circular convolution commutes with a circular shift. Zero padding changes boundary neighborhoods and can break that equality.

Circular convolution respects the circular shift. Zero padding creates an edge where the operations can disagree.

Zero padding or cropping breaks exact shift symmetry at an ordinary image boundary, while the shared kernel remains equivariant in the interior.

A convolution learns one local rule and applies it across positions. Depth enlarges the region those rules can combine, and translation equivariance states how their representation moves with the input.