Paper 01 · Era I · Pretext · 2014
Discriminative Unsupervised Feature Learning with Exemplar Convolutional Neural Networks — Dosovitskiy, Fischer, Springenberg, Riedmiller & Brox
Before contrastive learning had a name, before MoCo and SimCLR, someone asked a deceptively simple question: if every photo is its own class, and we invent the members of that class by distorting it — can a network learn to see without labels?
01
By 2014, supervised CNNs (AlexNet and its descendants) had just broken open computer vision. The recipe was clear: take millions of labeled images, train a deep net, and get features that transfer surprisingly well. But two cracks were already visible.
Question everything
Why do we need labels at all? Pixels already contain structure — objects, lighting, geometry. If a human infant can learn to see without a teacher naming every object, why must a network wait for ImageNet?
And even if labels work for classification: are class labels the right signal for every task? Matching two patches across viewpoint change does not care whether the patch is a “dog” or a “car.” Class supervision might even hurt.
Unsupervised methods of the time mostly tried to model the input distribution $p(\mathbf{x})$: autoencoders reconstruct the image; sparse coding finds a dictionary that rebuilds it. The hope was that a good model of $p(\mathbf{x})$ would somehow contain $p(y\mid\mathbf{x})$. That hope was only partly true — and those methods were hard to stack into deep CNNs end-to-end.
So the paper’s real starting point is not “can we beat ImageNet?” It is: can we invent a training signal from unlabeled images that forces a CNN to learn features that are both discriminative and invariant?
02
Here is the entire idea, stripped bare:
The surrogate classification loop
Why should this work at all?
To tell “this distorted patch came from seed 47, not seed 891,” the network must find something stable about seed 47 — identity that survives translation, scale, mild rotation, colour shifts. That stability is invariance. And because it must separate thousands of seeds, the features cannot collapse to a constant: they must stay discriminative.
Notice what is not being asked: reconstruct the pixels, model $p(\mathbf{x})$, or predict a human label. The network only has to answer: which exemplar did this come from? That is enough.
Why “Exemplar”?
Each surrogate class is born from a single real sample (one exemplar), not from a semantic category that already contains many natural instances. Data augmentation usually expands a labeled class; here the class is the augmentation of one unlabeled patch.
03
Start with unlabeled images (they used STL-10’s 100k unlabeled set). Sample $N$ patches of $32\times 32$ — but not uniformly. Sample with probability proportional to mean squared gradient magnitude, so you preferentially get patches with edges and structure, not empty sky.
Why not sample uniformly?
A blank patch transformed a hundred ways is still blank. Discriminating empty patches teaches nothing about objects. The gradient prior is a cheap prior that “interesting content exists here.” It is handcrafted — and that is already a design choice worth noticing.
Then define a family of transformations $\{T_{\boldsymbol{\alpha}}\}$ parameterized by a vector $\boldsymbol{\alpha}$. Each $T_{\boldsymbol{\alpha}}$ is a composition of elementary transforms. For classification they used:
| Transform | Range | What invariance does it buy? |
|---|---|---|
| Translation | up to 20% of patch size | object position within the crop |
| Scaling | factor $0.7$–$1.4$ | apparent size / distance |
| Rotation | up to $\pm 20^\circ$ | mild viewpoint / camera tilt |
| Contrast (PCA) | per-PC multiply $0.5$–$2$ | lighting / camera response |
| Contrast (HSV) | S,V power & scale | saturation / brightness |
| Color (hue) | $\pm 0.1$ on H | global colour cast |
For each seed $\mathbf{x}_i$, draw $K$ random parameter vectors and form the set
$$ S_{\mathbf{x}_i} = \{ T_{\boldsymbol{\alpha}_i^{1}}\mathbf{x}_i,\;\ldots,\; T_{\boldsymbol{\alpha}_i^{K}}\mathbf{x}_i \}. $$Assign every member of $S_{\mathbf{x}_i}$ the surrogate label $i$. Subtract per-pixel mean over the whole surrogate dataset. Train.
Are these the “right” transforms?
They are a bet about which variations a useful visual feature should ignore. The paper’s own ablations later show translation, colour, and contrast matter most for classification; rotation and scale less so. For matching, they had to add blur — because without it, the network overfit to sharp edges and failed under defocus. So the transform list is not universal truth; it is the definition of the invariances you want.
A quiet assumption
Transforms must not change the identity of the content. If two seeds look almost the same after heavy colour jitter, the labels become lying teachers. If you force hue invariance, you cannot later distinguish a black panther from a puma by colour alone. The paper says this explicitly — the objective encodes a prior about what should not matter.
04
With surrogate classes defined, training is ordinary multiclass classification. The empirical loss is
Equation (1) — surrogate classification
$$ L(X)=\sum_{\mathbf{x}_i\in X}\sum_{T\in\mathcal{T}_i} \ell\!\big(i,\, T\mathbf{x}_i\big). $$With a softmax output $f(\cdot)$ and one-hot target $\mathbf{e}_i$, the per-sample loss is cross-entropy:
Equation (2) — multinomial negative log-likelihood
$$ \ell(i,\,T\mathbf{x}_i)=-\langle\mathbf{e}_i,\,\log f(T\mathbf{x}_i)\rangle =-\sum_k (\mathbf{e}_i)_k\log f_k(T\mathbf{x}_i). $$If we imagine infinitely many transforms per class, this becomes an expectation over transform parameters:
Equation (3) — population form
$$ \widehat{L}(X)=\sum_{\mathbf{x}_i\in X}\mathbb{E}_{\boldsymbol{\alpha}}\big[\ell(i,\,T_{\boldsymbol{\alpha}}\mathbf{x}_i)\big]. $$Intuition so far: pull all transforms of one seed toward the same class logit; push different seeds apart. But the paper does something more careful — it decomposes this objective to show those two forces explicitly.
05
Write $g(\mathbf{x})$ for the second-to-last layer (the “feature”), $\mathbf{W}$ for the final linear layer, $h(\mathbf{x})=\mathbf{W}g(\mathbf{x})$ for pre-softmax logits, and
$$ f(\mathbf{x})=\mathrm{softmax}(h(\mathbf{x})),\qquad \mathrm{softmax}(\mathbf{z})=\frac{\exp(\mathbf{z})}{\|\exp(\mathbf{z})\|_1}. $$Plugging into the population loss and expanding $-\langle\mathbf{e}_i,\log f\rangle$ gives
Equation (5)
$$ \sum_{\mathbf{x}_i}\mathbb{E}_{\boldsymbol{\alpha}} \Big[ -\langle\mathbf{e}_i,\,h(T_{\boldsymbol{\alpha}}\mathbf{x}_i)\rangle +\log\|\exp(h(T_{\boldsymbol{\alpha}}\mathbf{x}_i))\|_1 \Big]. $$Now introduce the average feature of a seed under random transforms:
$$ \widehat{\mathbf{g}}_i=\mathbb{E}_{\boldsymbol{\alpha}}\big[g(T_{\boldsymbol{\alpha}}\mathbf{x}_i)\big]. $$Rewrite (5) by adding and subtracting terms that involve only $\widehat{\mathbf{g}}_i$. You get two sums:
Equation (6) — discrimination + invariance
$$ \begin{aligned} &\underbrace{\sum_i\Big[ -\langle\mathbf{e}_i,\,\mathbf{W}\widehat{\mathbf{g}}_i\rangle +\log\|\exp(\mathbf{W}\widehat{\mathbf{g}}_i)\|_1 \Big]}_{\text{(A) classify the average representation}} \\[0.6em] +& \underbrace{\sum_i\Big[ \mathbb{E}_{\boldsymbol{\alpha}}\log\|\exp(h(T_{\boldsymbol{\alpha}}\mathbf{x}_i))\|_1 -\log\|\exp(\mathbf{W}\widehat{\mathbf{g}}_i)\|_1 \Big]}_{\text{(B) force each transform close to the average}}. \end{aligned} $$This is multinomial logistic regression on the pairs $(\widehat{\mathbf{g}}_i,\,\mathbf{e}_i)$. Different seeds must stay separable in feature space — otherwise the classifier cannot assign the right surrogate label.
Because $\log\|\exp(\cdot)\|_1$ is convex, Jensen says (B) $\ge 0$, with equality only when $h(T_{\boldsymbol{\alpha}}\mathbf{x}_i)$ is essentially constant across $\boldsymbol{\alpha}$. So (B) is a regularizer that rewards transform-invariance.
Jensen’s inequality for a convex function $Z$:
$$ \mathbb{E}[Z(\mathbf{u})]\;\ge\;Z(\mathbb{E}[\mathbf{u}]). $$Take $Z(\mathbf{z})=\log\|\exp(\mathbf{z})\|_1$ (log-sum-exp — convex; the appendix proves its Hessian is positive semidefinite with kernel $\mathrm{span}\{\mathbf{1}\}$). Set $\mathbf{u}=h(T_{\boldsymbol{\alpha}}\mathbf{x}_i)$. Then
Equation (7)
$$ \mathbb{E}_{\boldsymbol{\alpha}}\big[\log\|\exp(h(T_{\boldsymbol{\alpha}}\mathbf{x}_i))\|_1\big] -\log\|\exp(\mathbf{W}\widehat{\mathbf{g}}_i)\|_1\;\ge\;0. $$Equality holds when the logits do not move (up to an additive constant shared across classes) as you transform the patch — i.e., when the representation is invariant. So the surrogate classification loss is secretly:
“Keep seeds separable” + “make each seed’s transforms look the same.”
Could we have written those two terms by hand?
Yes — and later papers effectively do (contrastive losses, VICReg’s variance/invariance/covariance split, BYOL’s predict-the-other-view). Exemplar-CNN’s contribution is realizing that ordinary cross-entropy on augmented exemplars already contains both pressures, without an explicit reconstruction term or noise model.
An autoencoder says: represent $\mathbf{x}$ so you can rebuild it. That forces the code to keep almost everything — including details irrelevant to recognition. Exemplar-CNN says: represent $\mathbf{x}$ so you can tell it apart from other seeds after distortion. Reconstruction is unnecessary; those degrees of freedom can be spent on useful invariances instead.
06
Training details that matter: thousands of surrogate classes (sweet spot around 8k–16k), on the order of 100 samples per class, ordinary SGD + dropout, then freeze the net and train a linear SVM on pooled features for the real task.
On STL-10, CIFAR-10, Caltech-101, Caltech-256, their best Exemplar-CNN beat prior unsupervised methods — sometimes by a large margin (STL-10: 74.2%). Still below fully supervised SOTA where labels are abundant, which is honest and expected: class labels are a stronger signal for class prediction.
For geometric matching, AlexNet features (trained on ImageNet classes) were often worse than Exemplar-CNN, and with blur augmentation Exemplar-CNN beat SIFT on most pairs. The punchline: when the downstream task does not care about object categories, category supervision is not sacred — and can be the wrong teacher.
What was “solved”
Not “unsupervised features beat supervised forever.” Solved: a practical, end-to-end discriminative pretext that yields transferable CNN features from unlabeled images, with a clear invariance story — and evidence that the right pretext depends on the target task.
07
Is this really unsupervised?
No human labels, yes. But the transform family and the gradient-based sampling prior are strong human-designed signals. Later contrastive work still depends on augmentation design in the same way. “Unsupervised” here means “no semantic annotation,” not “no inductive bias.”
Is $N$-way classification over instances scalable?
With 16k classes you already feel collisions. With a million images, a softmax over a million logits is ugly. Later methods (Instance Discrimination with a memory bank, MoCo’s queue, SimCLR’s in-batch negatives) keep the same spirit — “each image is its own class” — but replace the giant softmax with contrastive comparisons. Exemplar-CNN is the conceptual parent; it is not the scalable form.
Does invariance always help?
Their own contrast ablation hints no: too much contrast jitter can erase a cue (strong vs weak edges) that classification wants. Perfect invariance to everything is collapse by another name. You want invariance to nuisance variation, not to the signal.
Did the formal split (A)+(B) change practice?
Mostly as understanding, not as an implemented loss. Practitioners just ran cross-entropy on surrogate labels. The decomposition is there to explain why that works — and to connect to tangent-prop-style invariance ideas without explicitly penalizing Jacobians.
08
Read the Steeped timeline again with this paper in mind. The seed it planted is one sentence:
Different views of one image should mean the same thing — and different images should remain distinguishable.
Everything that follows elaborates that sentence:
Carry forward
When you open the next paper, ask: what plays the role of the seed? what plays the role of $T_{\boldsymbol{\alpha}}$? how do they enforce (A) discrimination and (B) invariance — and what happens if either force fails?