Introduction to Machine Learning
One recipe for learning, and many assumptions about the data.
Three kinds of real data come back all session: the 20,000 handwritten digits of last lecture, Beirut's daily temperature since 2010, and one digit, a 4 from the held-out set, that we follow through every network.
Held-out digits it reads correctly
We could show it shifted copies of every digit. Or we could build the fact that a stroke is a stroke anywhere into the function itself. That second move is what an architecture is.
Backpropagation does not care what the pieces are. It needs the derivative of each one, and the chain rule does the rest. So inventing an architecture means choosing pieces and how they connect, not inventing a new way to train.
A right assumption is information the network gets for free, so it needs less data. A wrong one is a cage no amount of data opens. The name for it is inductive bias.
Part 2 of 6
What do images share, and how can a layer build it in?
The first fact is locality, the second is translation. Built in together, they are a convolutional layer: many small sets of weights like this one, each slid over the whole image.
Move the digit and the map moves with it, otherwise unchanged. Shift in, shift out: the layer is equivariant to translation, because the same 9 weights are used everywhere.
The first layer finds strokes and edges. The second combines them on a coarser grid, the third combines those. Each layer sees more of the image than the last: one cell of the third layer depends on an 18 by 18 window, more than the whole digit. That is the feature hierarchy, and nobody designed its features.
The same hierarchy in a large network: Zeiler and Fergus, ECCV 2014, arXiv:1311.2901. Notes: Stanford CS231n.
Vertical shifts hurt both more than horizontal ones: these digits nearly fill the height of the frame, so moving them up or down pushes ink off the edge. And the convolutional network has 14,378 weights against 8,554: the saving is not in the total, it is that each weight is reused at every position.
And at 180 degrees a 6 is a 9. Some invariances would be wrong: choosing the bias is a decision about the data, not a free upgrade.
Cohen and Welling, Group equivariant convolutional networks, ICML 2016, arXiv:1602.07576.
Part 3 of 6
How can a network remember?
Loading the temperatures...
A fully connected network could read the 30 days as 30 separate inputs, as the linear model does. It would not know that day 29 comes after day 28, and it could not read 31 days without new weights. A sequence has an order, and no fixed length.
Data: ERA5 reanalysis through the Open-Meteo archive API (CC BY 4.0), the grid cell at Beirut; trained on 2010 to 2021, tested on 2022 to 2025.
\(x_t\) is the temperature on day \(t\). The same \(W_h, W_x, b\) are used on every day.
A convolution shares its weights across space; a recurrent network shares them across time. Unrolled over 30 days it is a 30-layer network in which every layer is the same, so it reads a sequence of any length.
Elman, Finding structure in time, Cognitive Science 14(2), 179 to 211, 1990. doi:10.1207/s15516709cog1402_1
A product of \(k\) matrices: if they shrink vectors, it vanishes; if they stretch them, it explodes. Gradient descent cannot learn to use day \(T-30\) when its gradient has all but disappeared.
Bengio, Simard and Frasconi, Learning long-term dependencies with gradient descent is difficult, IEEE Transactions on Neural Networks 5(2), 157 to 166, 1994. doi:10.1109/72.279181
The forget gate \(f_t\), input gate \(i_t\) and output gate \(o_t\) are sigmoids of \(h_{t-1}\) and \(x_t\), numbers between 0 and 1; \(g_t\) is the new content. Along the cell the gradient is multiplied only by \(f_t\). Where the network learns \(f_t \approx 1\), memory and gradient pass through many steps.
Hochreiter and Schmidhuber, Long short-term memory, Neural Computation 9(8), 1735 to 1780, 1997. doi:10.1162/neco.1997.9.8.1735
Barely.
Part 4 of 6
What can a network learn from the data alone?
To push 256 pixels through \(d = 2\) numbers and back, the encoder \(f\) must keep what varies between digits and drop what does not. The assumption built in: the data lie near a surface of far fewer dimensions than the space of all images.
Hinton and Salakhutdinov, Reducing the dimensionality of data with neural networks, Science 313(5786), 504 to 507, 2006. doi:10.1126/science.1127647
Digits of the same kind gather although nobody said which was which. Between two clusters the decoder draws something in between, a 4 on its way to a 9: the code space is continuous, and every point in it is a drawing.
Kingma and Welling, Auto-encoding variational Bayes, 2013, arXiv:1312.6114.
The discriminator \(D\) is a classifier, trained to tell real from generated. The generator \(G\) turns random numbers \(z\) into samples, and is trained through \(D\)'s gradient to make \(D\) call them real. Neither ever sees a formula for the data. The assumption is in the training, not in a layer: plausible means whatever a learned critic cannot tell from the data.
Goodfellow, Pouget-Abadie, Mirza, Xu, Warde-Farley, Ozair, Courville and Bengio, Generative adversarial nets, NeurIPS 2014, arXiv:1406.2661.
Watch the generator chase the two peaks, and the discriminator's curve rise wherever real days outnumber generated ones. It rarely settles: each player's improvement changes the other's problem, so the game oscillates instead of descending a fixed loss.
Radford, Metz and Chintala, Unsupervised representation learning with deep convolutional generative adversarial networks, 2015, arXiv:1511.06434.
Part 5 of 6
What if any part may matter to any other?
A dictionary returns the value whose key matches exactly. Attention returns a blend of all the values, weighted by how well each key matches the query. The weights \(\alpha_{ij}\) are computed from the input, afresh for every input: the network decides which parts relate.
Here the tokens are the 16 patches of our 4, each 4 by 4 pixels. The lines show how much one patch draws from every other in a trained network.
Nothing about neighbours was built in: patch 1 can attend to patch 16 as easily as to patch 2, and position is only a learned vector added to each patch. Whatever structure you see, the network found in the data.
The price: \(n\) tokens make \(n^2\) pairs, and an assumption you did not build in has to be learned from data.
Vaswani, Shazeer, Parmar, Uszkoreit, Jones, Gomez, Kaiser and Polosukhin, Attention is all you need, NeurIPS 2017, arXiv:1706.03762.
On 14 million to 300 million images the order flips: the vision transformer matched or beat the best convolutional networks only after training at that scale. With little data, build in what you know. With a great deal, assume less.
Dosovitskiy et al., An image is worth 16x16 words: transformers for image recognition at scale, ICLR 2021, arXiv:2010.11929.
Part 6 of 6
Which assumption for which data?
| Data | Structure it has | Built in by | Architecture | Today, on real data |
|---|---|---|---|---|
| Any list of numbers | none assumed | a weight for every input of every unit | Fully connected | 96.5% of held-out digits; 32.8% moved 2 pixels right |
| Images | nearby pixels belong together; a stroke is a stroke anywhere | small kernels shared across positions; pooling | Convolutional | 97.4%; 94.8% moved 2 pixels right; 38.1% rotated 45° |
| Sequences | order; the past shapes the present | one cell reused at every step; gates on a memory | Recurrent, LSTM | 1.38 and 1.35 °C, against 1.46 °C for tomorrow equals today |
| Data without labels | the data lie near a surface of few dimensions | a bottleneck | Autoencoder | error 0.035 per pixel at d = 2, PCA 0.045 |
| Examples to imitate | a new sample should be impossible to tell from a real one | a critic network trained against the generator | GAN | after 30 epochs: 305 sevens, 150 fours in 2,000 |
| Parts that relate | any part may matter to any other | attention over all pairs | Transformer | 96% from 16,000 digits; 50% moved up to 2 pixels (convolutional: 80%) |
| Things and links | listing them in another order changes nothing | messages along the links | Graph network | not run today: see the weather lecture |
In every row the recipe is the same: a composition of differentiable pieces, a loss, and gradient descent. Only the assumption changes.
Every filter reaches through the full depth of its input. A layer with \(C_\text{out}\) filters of size \(k \times k\) on \(C_\text{in}\) maps has \(k \cdot k \cdot C_\text{in} \cdot C_\text{out} + C_\text{out}\) weights: here \(5 \cdot 5 \cdot 3 \cdot 6 + 6 = 456\), whatever the size of the image.
The drawing shows the first row of windows: grey cells are padding, outlined squares are where the kernel lands. A 2 by 2 max pooling with stride 2 is the same formula with \(k = 2, p = 0, s = 2\), and has no weights.
| Layer | Output shape | Weights | One cell sees |
|---|---|---|---|
| Input | 16 × 16 × 1 | 1 × 1 | |
| Convolution 1: 16 filters, 3 × 3, padding 1, ReLU | 16 × 16 × 16 | 3·3·1·16 + 16 = 160 | 3 × 3 |
| Max pooling, 2 × 2 | 8 × 8 × 16 | 0 | 4 × 4 |
| Convolution 2: 32 filters, 3 × 3, padding 1, ReLU | 8 × 8 × 32 | 3·3·16·32 + 32 = 4,640 | 8 × 8 |
| Max pooling, 2 × 2 | 4 × 4 × 32 | 0 | 10 × 10 |
| Convolution 3: 32 filters, 3 × 3, padding 1, ReLU | 4 × 4 × 32 | 3·3·32·32 + 32 = 9,248 | 18 × 18 |
| Average over each map | 32 | 0 | all |
| Dense, softmax | 10 | 32·10 + 10 = 330 | |
| Total | 14,378 |
import torch.nn as nn
net = nn.Sequential(
nn.Conv2d(1, 16, 3, padding=1), nn.ReLU(),
nn.MaxPool2d(2),
nn.Conv2d(16, 32, 3, padding=1), nn.ReLU(),
nn.MaxPool2d(2),
nn.Conv2d(32, 32, 3, padding=1), nn.ReLU(),
nn.AdaptiveAvgPool2d(1), nn.Flatten(),
nn.Linear(32, 10),
)
print(sum(p.numel() for p in net.parameters()))
# 14378Most weights sit in the deep layers, where many maps meet many maps. The fully connected network of last lecture has 8,554 weights, and they buy no shift invariance.