Convolutional Networks

MML (CC BY 4.0) · D2L (CC BY-SA 4.0) · 9 of 12

Convolutions exploit spatial structure: shared weights, local receptive fields, translation equivariance. Pooling provides invariance. The hierarchy — edges, textures, parts, objects — emerges from stacking layers.

1D convolution by hand

A 1D convolution slides a kernel (a small vector of weights) across an input signal. At each position, it computes the dot product of the kernel with the local patch. The kernel is shared across all positions — this is the parameter sharing that makes CNNs efficient.

Scheme

; 1D convolution: slide a kernel across a signal
; kernel [1, 0, -1] detects edges (differences)

(define (conv1d signal kernel)
  (let ((k-len (length kernel))
        (s-len (length signal)))
    (let loop ((i 0) (result '()))
      (if (> (+ i k-len) s-len) (reverse result)
          (let inner ((j 0) (sum 0))
            (if (= j k-len)
                (loop (+ i 1) (cons sum result))
                (inner (+ j 1)
                       (+ sum (* (list-ref signal (+ i j))
                                 (list-ref kernel j))))))))))

(define signal '(3 1 4 1 5 9 2))
(define kernel '(1 0 -1))

(display "Signal: ") (display signal) (newline)
(display "Kernel: ") (display kernel) (newline)
(display "Conv:   ") (display (conv1d signal kernel))
; Each output = difference between elements 2 apart

Max pooling

Pooling downsamples the feature map by taking the maximum (or average) over local windows. This provides a degree of translation invariance: small shifts in the input don't change the pooled output. It also reduces the spatial dimensions, cutting computation.

Scheme

; Max pooling: take the max in each window of size k
(define (max-pool signal k)
  (let ((s-len (length signal)))
    (let loop ((i 0) (result '()))
      (if (> (+ i k) s-len) (reverse result)
          (let inner ((j 0) (mx -999999))
            (if (= j k)
                (loop (+ i k) (cons mx result))
                (inner (+ j 1)
                       (max mx (list-ref signal (+ i j))))))))))

(define feature-map '(2 5 1 8 3 7 4 6))

(display "Feature map:     ") (display feature-map) (newline)
(display "Max pool (k=2):  ") (display (max-pool feature-map 2)) (newline)
(display "Max pool (k=4):  ") (display (max-pool feature-map 4))
; Halves (or quarters) the length, keeps strongest activations

Conv + pool pipeline

A CNN stacks convolution and pooling layers. Each convolution extracts local features; each pooling step compresses the spatial dimension. After enough layers, the feature map is small enough to feed into a fully connected classifier. The early layers detect edges, the middle layers textures, the deep layers objects.

Scheme

; Simple conv -> ReLU -> pool pipeline on a 1D signal

(define (conv1d signal kernel)
  (let ((k-len (length kernel)) (s-len (length signal)))
    (let loop ((i 0) (result '()))
      (if (> (+ i k-len) s-len) (reverse result)
          (let inner ((j 0) (sum 0))
            (if (= j k-len) (loop (+ i 1) (cons sum result))
                (inner (+ j 1) (+ sum (* (list-ref signal (+ i j))
                                         (list-ref kernel j))))))))))

(define (relu xs) (map (lambda (x) (max 0 x)) xs))

(define (max-pool xs k)
  (let loop ((i 0) (result '()))
    (if (> (+ i k) (length xs)) (reverse result)
        (let inner ((j 0) (mx -999999))
          (if (= j k) (loop (+ i k) (cons mx result))
              (inner (+ j 1) (max mx (list-ref xs (+ i j)))))))))

(define signal '(0 0 1 3 5 3 1 0 0 2 4 6 4 2 0 0))
(define edge-kernel '(1 0 -1))

(define step1 (conv1d signal edge-kernel))
(define step2 (relu step1))
(define step3 (max-pool step2 2))

(display "Input:           ") (display signal) (newline)
(display "After conv:      ") (display step1) (newline)
(display "After ReLU:      ") (display step2) (newline)
(display "After max-pool:  ") (display step3)

; Simple conv -> ReLU -> pool pipeline on a 1D signal

(define (conv1d signal kernel)
  (let ((k-len (length kernel)) (s-len (length signal)))
    (let loop ((i 0) (result '()))
      (if (> (+ i k-len) s-len) (reverse result)
          (let inner ((j 0) (sum 0))
            (if (= j k-len) (loop (+ i 1) (cons sum result))
                (inner (+ j 1) (+ sum (* (list-ref signal (+ i j))
                                         (list-ref kernel j))))))))))

(define (relu xs) (map (lambda (x) (max 0 x)) xs))

(define (max-pool xs k)
  (let loop ((i 0) (result '()))
    (if (> (+ i k) (length xs)) (reverse result)
        (let inner ((j 0) (mx -999999))
          (if (= j k) (loop (+ i k) (cons mx result))
              (inner (+ j 1) (max mx (list-ref xs (+ i j)))))))))

(define signal '(0 0 1 3 5 3 1 0 0 2 4 6 4 2 0 0))
(define edge-kernel '(1 0 -1))

(define step1 (conv1d signal edge-kernel))
(define step2 (relu step1))
(define step3 (max-pool step2 2))

(display "Input:           ") (display signal) (newline)
(display "After conv:      ") (display step1) (newline)
(display "After ReLU:      ") (display step2) (newline)
(display "After max-pool:  ") (display step3)

Notation reference

Math	Scheme	Meaning
(f * g)[n]	(conv1d signal kernel)	1D convolution
max(x_i..i+k)	(max-pool xs k)	Max pooling with window k
ReLU(x) = max(0,x)	(max 0 x)	Rectified linear unit
stride, padding	step size, zero-fill	Control output dimensions

Translation notes

Convolution in signal processing flips the kernel; in deep learning, cross-correlation (no flip) is standard but still called "convolution." The Scheme code above implements cross-correlation. In practice, learned kernels absorb the flip.

Neighbors

∫ Ch.8 Integration Techniques — convolution as integral transform
📡 Shannon Ch.6 — channel capacity constrains what filters can extract

← Regularization by june.kim Sequence Models →