Data Types · Efficient Convolution Algorithms · Random or Unsupervised Features

§9.7 Data types

Convolutional data usually has several channels, each a different quantity observed at a point in space or time. The dimensionality of the grid and the number of channels vary widely (table 9.1):

Table 9.1 — data formats for convolutional networks
	single channel	multi-channel
1-D	Audio waveform: convolve over time, one amplitude per time step.	Skeleton animation: one channel per joint-axis angle, over time.
2-D	Fourier-transformed audio: rows = frequency, columns = time (convolving over frequency makes the same melody in another octave produce the same representation, shifted in height).	Color image: R, G, B channels; the kernel moves over both spatial axes → translation equivariance in both directions.
3-D	Volumetric data, e.g. CT scans.	Color video: axes are time, frame height, and frame width.

Dotted-underlined cells have explanations — click one.

A unique advantage: variable-size inputs

Convolution can process inputs of varying spatial extent, which a fixed-shape weight matrix simply cannot represent — the kernel is just applied a different number of times and the output scales accordingly (the same kernel induces a different-sized doubly block circulant matrix per input size). The output may vary too (per-pixel labels) or be fixed (a single label, via pooling regions that scale with the input). This only makes sense when the size varies because there is more of the same kind of thing — different recording lengths, different image widths — not when it varies by including different kinds of observations (you would not convolve the same weights over a student’s grades and their test scores).

§9.8 Efficient convolution algorithms

Modern conv nets have over a million units, so efficient implementation (and parallel hardware, §12.1) matters. Two algorithmic speedups: convolution equals a Fourier-domain point-wise multiplication (transform input and kernel, multiply, invert) — faster for some sizes; and, when a kernel is separable (an outer product of one vector per axis), it decomposes into a chain of cheap 1-D convolutions:

Term by term

O(w^d) \;\longrightarrow\; O(w \times d)

$\text{separable}$	a d-dimensional kernel that equals the OUTER PRODUCT of d vectors, one per axis	the condition
$O(w^d)$	naive d-D convolution with a w-wide kernel costs w^d in both runtime AND parameter storage	naive
$O(w \times d)$	compose d one-dimensional convolutions instead → w×d, a huge saving. (But not every kernel is separable)	separable

Faster (or approximate) convolution is an active research area — even forward-pass-only speedups are valuable, since deployment often costs more than training.

§9.9 Random or unsupervised features

The most expensive part of training a conv net is learning the features — every gradient step needs a full forward and backward pass. One shortcut: obtain the kernels without supervised training.

Three ways to get kernels for free

(1) Random. Surprisingly, random filters work well — convolution followed by pooling becomes frequency-selective and translation-invariant even with random weights . This gives a cheap way to choose an architecture: train only the last layer on several candidate architectures, pick the best, then train it fully.
(2) Hand-designed. Set kernels by hand to detect edges at chosen orientations or scales.
(3) Unsupervised. Learn kernels with an unsupervised criterion — e.g. k-means on image patches, using each centroid as a kernel. Because the features are learned separately from the classifier, you can extract them once and then train the (convex) last layer cheaply.

An intermediate option is greedy layer-wise pretraining (train each layer once, then the next) — the canonical example being the convolutional deep belief network. Because a conv net can be trained on a small patch and its parameters copied into the kernel, you can even train one without ever running convolution during training. This was popular from ~2007–2013, when labeled data and compute were scarce; today most conv nets are trained in a purely supervised fashion.

Next: the neuroscience behind convolutional networks — V1, simple and complex cells, and Gabor functions — the neuroscientific basis.

Check yourself — data types, efficient convolution, random features

1.What unique advantage do convolutional networks have over fixed-shape matrix-multiplication networks for input size?

2.In table 9.1, what is an example of 2-D multi-channel data, and what does convolving over both axes give?

3.When a kernel is 'separable', how much can it save?

4.Why do random convolution filters work 'surprisingly well', and how is that useful?

5.What are the three ways to obtain convolution kernels without supervised training?

5 questions