Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

Representation Learning

Embeddings, autoencoders and self-supervision.

Train a network to sort a million photos into a thousand classes, cut off its last layer, and what remains is a feature extractor that helps on tasks it never saw. Representation learning makes that side effect the goal: map raw data to vectors in which the structure you care about becomes simple, ideally linear. This lesson derives the three main recipes: embeddings, autoencoders and contrastive self-supervision.

What you’ll learn

  • Describe what makes a representation useful (distributed, linearly accessible, invariant, sparse) and read a network's last hidden layer as a learned feature map.
  • Derive the skip-gram negative-sampling objective, its gradient and its cost, and state its link to pointwise mutual information.
  • Prove that an optimal linear autoencoder spans the principal subspace, and explain how denoising, sparse and masked autoencoders avoid the identity map.
  • Write the InfoNCE loss as a softmax cross-entropy, explain collapse, compare SimCLR, MoCo and BYOL, and evaluate representations with linear probes.

Features you do not have to design

For decades, machine learning meant feature engineering: experts turned pixels into edge histograms and text into word counts, and a linear model did the rest. A deep network learns the features as well. Write a classifier as f(x)=σ(w⊤ϕθ(x)+b)f(\mathbf x)=\sigma\big(\mathbf w^\top\boldsymbol\phi_\theta(\mathbf x)+b\big), where ϕθ\boldsymbol\phi_\theta is everything up to the last hidden layer. Training all of it end to end shapes ϕθ\boldsymbol\phi_\theta until a linear readout suffices. That is representation learning, and ϕθ(x)\boldsymbol\phi_\theta(\mathbf x) is a point in a learned latent space.

Check your understanding

The network's output is σ(w1h1+w2h2+b)\sigma(w_1h_1+w_2h_2+b), computed from the last hidden layer (h1,h2)(h_1,h_2), and it classifies every training point correctly. What follows about the training points?

  1. The two spirals are linearly separable in the input plane
  2. Their representations (h1,h2)(h_1,h_2) are linearly separable: a line in the (h1,h2)(h_1,h_2) plane splits the classes
  3. The map x↦(h1,h2)\mathbf x\mapsto(h_1,h_2) is invertible, so no information about x\mathbf x is lost
  4. h1h_1 and h2h_2 are statistically independent features
Show the answer

B. Their representations (h1,h2)(h_1,h_2) are linearly separable: a line in the (h1,h2)(h_1,h_2) plane splits the classes

The output thresholds w1h1+w2h2+bw_1h_1+w_2h_2+b at zero, a line in the (h1,h2)(h_1,h_2) plane, and 100% accuracy says that line separates the classes there. The earlier layers did the hard work of bending the input space until a line suffices.

PropertyWhat it meansWhat encourages it
Distributeda concept is a pattern over many units; dd units can express up to 2d2^d patterns, and similar inputs share unitsany dense hidden layer or embedding
Linearly accessiblethe factors you care about are close to linear functions of the codetraining with a linear head; measured by linear probes
Invariantnuisance changes (crop, lighting, paraphrase) move the code little; task-relevant changes move it a lotdata augmentation, contrastive objectives
Sparseeach input activates few units, so units can specializeL1L_1 penalties, ReLUs, kk-sparse codes
Disentangledseparate factors of variation (pose, identity, lighting) occupy separate directionsinductive biases in architecture and data; provably impossible to guarantee without them (Deep Layer)
Desiderata in the spirit of Bengio, Courville and Vincent (2013). They pull against each other: perfect invariance discards information that some other task may need.

Contrast the simplest code for symbols, the one-hot vector ei∈{0,1}∣V∣\mathbf e_i\in\{0,1\}^{|V|}. Distinct one-hot vectors are orthogonal, cos⁡(ei,ej)=0\cos(\mathbf e_i,\mathbf e_j)=0, so everything learned about "cat" says nothing about "kitten". A dense code in Rd\R^d with d≪∣V∣d\ll|V| lets similar symbols share directions. (The debate over distributed versus local codes is told in Symbols vs. Connections.) The next step learns such codes from raw text, with no labels at all.

Embeddings and skip-gram with negative sampling

An embedding layer stores one vector per symbol in a matrix E∈R∣V∣×dE\in\R^{|V|\times d}. Feeding it a one-hot vector computes ei⊤E\mathbf e_i^\top E, which just selects row ii, so a gradient step touches only the rows of the symbols in the batch.

To learn word vectors without labels, use the distributional hypothesis, "you shall know a word by the company it keeps" (Firth, 1957): train each word to predict its neighbors. The skip-gram model of word2vec (Mikolov et al., 2013) gives each word a center vector vw\mathbf v_w and a context vector uc\mathbf u_c, and for every word cc within a few positions of ww it models

p(c∣w)=euc⊤vw∑c′∈Veuc′⊤vw.p(c\mid w)=\frac{e^{\mathbf u_c^\top\mathbf v_w}}{\sum_{c'\in V}e^{\mathbf u_{c'}^\top\mathbf v_w}}.

The normalizer sums over the whole vocabulary: O(∣V∣d)\order{|V|d} work per training pair, prohibitive for ∣V∣≈106|V|\approx10^6.

ℓ(w,c)=−log⁡σ(uc⊤vw)−∑j=1klog⁡σ(−unj⊤vw),nj∼Pn(c)∝#(c)3/4\ell(w,c)=-\log\sigma\big(\mathbf u_c^\top\mathbf v_w\big)-\sum_{j=1}^{k}\log\sigma\big(-\mathbf u_{n_j}^\top\mathbf v_w\big),\qquad n_j\sim P_n(c)\propto\#(c)^{3/4}
Negative sampling replaces the ∣V∣|V|-way softmax by k+1k+1 logistic regressions that tell the observed context cc apart from kk random "negative" words. Raising counts to the power 3/43/4 samples rare words more often than their frequency. Mikolov et al. used k=5k=5–2020 on small corpora and k=2k=2–55 on large ones.
DerivationThe gradient, and what it costs
  1. ∂ℓ∂s=σ(s)−1,∂ℓ∂sj=σ(sj)\frac{\partial\ell}{\partial s}=\sigma(s)-1,\qquad\frac{\partial\ell}{\partial s_j}=\sigma(s_j)

    Write s=uc⊤vws=\mathbf u_c^\top\mathbf v_w and sj=unj⊤vws_j=\mathbf u_{n_j}^\top\mathbf v_w, and use ddslog⁡σ(s)=1−σ(s)\frac{d}{ds}\log\sigma(s)=1-\sigma(s) and ddslog⁡σ(−s)=−σ(s)\frac{d}{ds}\log\sigma(-s)=-\sigma(s):

  2. ∇vwℓ=(σ(s)−1)uc+∑jσ(sj) unj,∇ucℓ=(σ(s)−1)vw,∇unjℓ=σ(sj) vw\nabla_{\mathbf v_w}\ell=\big(\sigma(s)-1\big)\mathbf u_c+\sum_j\sigma(s_j)\,\mathbf u_{n_j},\qquad\nabla_{\mathbf u_c}\ell=\big(\sigma(s)-1\big)\mathbf v_w,\qquad\nabla_{\mathbf u_{n_j}}\ell=\sigma(s_j)\,\mathbf v_w

    Every candidate gets "prediction minus label", with label 1 for the observed context and 0 for the negatives. The chain rule through the dot products gives

  3. ∣V∣k+1=1066≈1.7×105\frac{|V|}{k+1}=\frac{10^6}{6}\approx1.7\times10^5

    A step costs O((k+1)d)\order{(k+1)d} instead of O(∣V∣d)\order{|V|d}. Descent pulls vw\mathbf v_w toward its real contexts and pushes it away from random words, so words that share contexts end up with similar vectors. With k=5k=5 and a million-word vocabulary the saving is

  4. uc⊤vw=log⁡p(w,c)p(w) p(c)−log⁡k=PMI⁡(w,c)−log⁡k\mathbf u_c^\top\mathbf v_w=\log\frac{p(w,c)}{p(w)\,p(c)}-\log k=\operatorname{PMI}(w,c)-\log k

    What does the optimum encode? If the negatives come from the unigram distribution p(c)p(c) and dd is large enough for every product uc⊤vw\mathbf u_c^\top\mathbf v_w to be set freely, the optimum is the pointwise mutual information shifted by log⁡k\log k (Levy & Goldberg, 2014; proved in the Deep Layer). Skip-gram is implicitly factorizing a word–context matrix.

python
import numpy as np

def sgns_step(V, U, w, c, noise, k=5, eta=0.025, rng=None):
    """One SGD step of skip-gram with negative sampling on the pair (w, c).
    V, U: (|V|, d) center and context vectors; noise: P_n, proportional to count**0.75."""
    rng = rng or np.random.default_rng()
    rows = np.concatenate(([c], rng.choice(len(noise), size=k, p=noise)))
    labels = np.r_[1.0, np.zeros(k)]                # observed context, then k negatives
    s = U[rows] @ V[w]                              # (k+1,) scores u_j . v_w
    g = 1.0 / (1.0 + np.exp(-s)) - labels           # dl/ds: prediction minus label
    grad_v = g @ U[rows]                            # dl/dv_w, before U changes
    np.add.at(U, rows, -eta * np.outer(g, V[w]))    # dl/du_j = g_j v_w; repeats add up
    V[w] -= eta * grad_v

One SGD step on one (word, context) pair. Production code also subsamples frequent words, decays η\eta linearly and runs many such steps in parallel. np.add.at matters because the same negative can be drawn twice.

Autoencoders: compression as a teacher

An autoencoder has an encoder z=fθ(x)∈Rk\mathbf z=f_\theta(\mathbf x)\in\R^k and a decoder x^=gϕ(z)\hat{\mathbf x}=g_\phi(\mathbf z), trained to reconstruct its input: min⁡1n∑i∥xi−gϕ(fθ(xi))∥2\min\frac1n\sum_i\norm{\mathbf x_i-g_\phi(f_\theta(\mathbf x_i))}^2. With k<dk<d (undercomplete) the code must compress. Without a bottleneck or some other constraint, the identity map reconstructs perfectly and nothing is learned. So what does the simplest bottleneck learn?

DerivationProof of the first part
  1. 1n∥X−WdWeX∥F2 ≥ min⁡rank⁡Y≤k1n∥X−Y∥F2\frac1n\norm{X-W_dW_eX}_F^2\ \ge\ \min_{\rank Y\le k}\frac1n\norm{X-Y}_F^2

    Stack the centered data as the columns of X∈Rd×nX\in\R^{d\times n}. The reconstruction WdWeXW_dW_eX passes through a kk-dimensional code, so its rank is at most kk:

  2. 1n∥X−UkUk⊤X∥F2=∑j>kλj\frac1n\norm{X-U_kU_k^\top X}_F^2=\sum_{j>k}\lambda_j

    By the Eckart–Young theorem (proved in PCA, t-SNE & UMAP), the best rank-kk approximation keeps the top kk singular directions, Y⋆=UkUk⊤XY^\star=U_kU_k^\top X, where UkU_k holds the top-kk eigenvectors of the covariance. Its loss is the variance left out:

  3. We=Uk⊤,Wd=Ukand every minimizer hasWdWeX=UkUk⊤XW_e=U_k^\top,\quad W_d=U_k\qquad\text{and every minimizer has}\qquad W_dW_eX=U_kU_k^\top X

    A linear autoencoder attains the bound. Since λk>λk+1\lambda_k>\lambda_{k+1} makes Y⋆Y^\star unique, every minimizer reconstructs the data exactly as Y⋆Y^\star does:

  4. (WdG−1)(GWe)=WdWe\big(W_dG^{-1}\big)\big(GW_e\big)=W_dW_e

    The code itself is fixed only up to an invertible k×kk\times k matrix GG: (GWe, WdG−1)(GW_e,\,W_dG^{-1}) has the same product and the same loss. A linear autoencoder finds the principal subspace, not the individual principal components; recovering those takes extra structure (Deep Layer).

Predict before you look

Centered data in R4\R^4 have covariance eigenvalues 5,3,1,15,3,1,1. A linear autoencoder with a 2-dimensional code is trained to its global minimum. What percentage of the total variance is lost in reconstruction?

Show the answer

20 %

The loss is λ3+λ4=2\lambda_3+\lambda_4=2 out of a total variance of 1010, so 20%. The 80% that survives is the explained-variance ratio of a 2-component PCA, because the two are the same model.

Nonlinear encoders and decoders can do far better: Hinton and Salakhutdinov (2006) trained deep autoencoders whose low-dimensional codes beat PCA's on images and documents. And a bottleneck is not the only way to rule out the identity map:

VariantObjectiveWhat it learns
Sparsereconstruct, plus a penalty λ∥z∥1\lambda\norm{\mathbf z}_1 (or keep only the kk largest units)an overcomplete dictionary of parts, each input built from a few of them; now used to extract interpretable features from language models
Denoising (Vincent et al., 2008)reconstruct the clean x\mathbf x from a corrupted x~=x+ε\tilde{\mathbf x}=\mathbf x+\boldsymbol\varepsilona vector field pointing back toward the data, proportional to ∇log⁡p\nabla\log p for small Gaussian noise: the idea behind diffusion models
Masked (BERT, 2019; MAE, 2022)reconstruct masked-out parts: BERT hides 15% of tokens, MAE 75% of image patchesfeatures good enough to infer missing parts from context
Variationalreconstruct, plus a KL term pulling codes toward a priora smooth latent space you can sample from, a generative model (Variational Autoencoders & the ELBO)
Every variant except the first changes the task, not the shape: the code may be as large as the input, because copying no longer solves the problem.

Self-supervision and the contrastive loss

Self-supervised learning manufactures labels from the data itself: predict a word's neighbors (word2vec), a masked token (BERT), the next token (GPT), or, in contrastive learning, which of many candidates is another view of the same example. For images, two random augmentations of one photo (crops, color jitter, blur) form a positive pair, and views of other photos are negatives. An encoder maps each view to a unit vector z\mathbf z, and the InfoNCE loss (van den Oord, Li & Vinyals, 2018) asks the positive to win a softmax over NN candidates:

L=−log⁡exp⁡(z⊤z+/τ)exp⁡(z⊤z+/τ)+∑j=1N−1exp⁡(z⊤zj−/τ),∥z∥=∥z±∥=1\mathcal L=-\log\frac{\exp(\mathbf z^\top\mathbf z^+/\tau)}{\exp(\mathbf z^\top\mathbf z^+/\tau)+\sum_{j=1}^{N-1}\exp(\mathbf z^\top\mathbf z_j^-/\tau)},\qquad\norm{\mathbf z}=\norm{\mathbf z^\pm}=1
τ\tau is a temperature, typically between about 0.050.05 and 0.50.5. Cosine similarities lie in [−1,1][-1,1], so dividing by a small τ\tau is what lets the softmax become confident.
DerivationInfoNCE is cross-entropy over candidates
  1. L=−s0+log⁡∑j=0N−1esj,pj=esj∑iesi\mathcal L=-s_0+\log\sum_{j=0}^{N-1}e^{s_j},\qquad p_j=\frac{e^{s_j}}{\sum_ie^{s_i}}

    Index the candidates j=0,…,N−1j=0,\dots,N-1 with the positive at j=0j=0, and let sj=z⊤zj/τs_j=\mathbf z^\top\mathbf z_j/\tau. The loss is the cross-entropy of a softmax classifier whose correct class is 00:

  2. ∂L∂sj=pj−1[j=0]\frac{\partial\mathcal L}{\partial s_j}=p_j-\mathbf 1[j=0]

    Its gradient is prediction minus target, as for any softmax cross-entropy:

  3. ∇zL=1τ(∑j=0N−1pj zj−z0)\nabla_{\mathbf z}\mathcal L=\frac1\tau\Big(\sum_{j=0}^{N-1}p_j\,\mathbf z_j-\mathbf z_0\Big)

    Through sj=z⊤zj/τs_j=\mathbf z^\top\mathbf z_j/\tau, descent moves the anchor toward its positive and away from the pp-weighted average of all candidates. Negatives that already look similar get large pjp_j and the strongest push, and a smaller τ\tau concentrates the push on the hardest ones:

  4. I(x;x+) ≥ log⁡N−LI(\mathbf x;\mathbf x^+)\ \ge\ \log N-\mathcal L

    Why should this produce good features? Minimizing L\mathcal L maximizes a lower bound on the mutual information between the two views, a bound that can never exceed log⁡N\log N (proved in the Deep Layer). More negatives raise the ceiling, one reason contrastive methods like large batches.

MethodNegativesKey ingredients
SimCLR (Chen et al., 2020)the other 2N−22N-2 views in a batch of NN imagesstrong augmentation; an MLP projection head that is discarded after training; batches up to 8,192
MoCo (He et al., 2020)a queue of 65,536 keys from earlier batchesa momentum encoder whose weights track the query encoder's, θk←mθk+(1−m)θq\theta_k\leftarrow m\theta_k+(1-m)\theta_q with m=0.999m=0.999
BYOL (Grill et al., 2020)nonean online network with an extra predictor regresses the output of a slowly moving average of itself, with a stop-gradient on that target
CLIP (Radford et al., 2021)the other images and captions in the batchpositives are image–caption pairs; see Contrastive Vision–Language Models

Measuring a representation

How do you compare two representations? The standard protocol is the linear probe (Alain & Bengio, 2016): freeze the encoder, fit logistic regression on its features for a labeled task, and report test accuracy. It measures what is linearly decodable, exactly what a downstream linear head can use. Other protocols are kk-nearest-neighbor accuracy in the embedding space and full fine-tuning. By linear-probe accuracy on ImageNet, SimCLR matched a supervised ResNet-50 in 2020, using a ResNet-50 four times as wide.

Think first SimCLR trains through a projection head gg but probes the layer h\mathbf h before it, and that layer gives markedly better probes than g(h)g(\mathbf h). Why might the head's output be worse?

The contrastive loss rewards invariance to the augmentations, so g(h)g(\mathbf h) learns to discard whatever the augmentations change, such as color and exact position. Some downstream tasks need that information. The head absorbs the invariance, and h\mathbf h keeps more of the input.

Key takeaways

  • A deep network is a learned feature map ϕθ\boldsymbol\phi_\theta plus a simple readout, and training makes the task linear in ϕθ\boldsymbol\phi_\theta. Good representations are distributed, linearly accessible, invariant to nuisances and often sparse.
  • Embeddings are lookup tables trained by gradient descent. Skip-gram with negative sampling replaces a ∣V∣|V|-way softmax by k+1k+1 logistic regressions, costs O((k+1)d)\order{(k+1)d} per pair and at its optimum encodes PMI⁡(w,c)−log⁡k\operatorname{PMI}(w,c)-\log k.
  • An optimal linear autoencoder spans the top-kk principal subspace, in an arbitrary basis, with loss ∑j>kλj\sum_{j>k}\lambda_j. Sparse, denoising and masked autoencoders change the task so that copying fails.
  • InfoNCE is softmax cross-entropy over one positive and N−1N-1 negatives; it lower-bounds mutual information and is capped at log⁡N\log N. Negatives, stop-gradients or variance penalties prevent collapse.
  • Linear probes measure what is linearly decodable from a representation, not what the model uses.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In word2vec's negative sampling, negatives are drawn with probability proportional to #(c)3/4\#(c)^{3/4} rather than to the count #(c)\#(c). What does the exponent do?

  1. It samples frequent words even more often than their frequency
  2. It flattens the distribution: rare words are sampled more often than their frequency, frequent words less
  3. It makes negative sampling compute the exact softmax
  4. It removes stop words from the training text
Show the answer

B. It flattens the distribution: rare words are sampled more often than their frequency, frequent words less

A power below 1 compresses ratios: for counts 10001000 and 1010, the sampling ratio drops from 100100 to 1003/4≈32100^{3/4}\approx32. Mikolov et al. found that 3/43/4 worked better than both the unigram and the uniform distribution.

Question 2

A linear autoencoder with a 3-dimensional code is trained to its global minimum on centered data whose covariance has distinct eigenvalues. Which statement is true?

  1. Its encoder's rows are the top 3 principal components, in order
  2. Its reconstruction error is lower than that of 3-component PCA
  3. It captures curved structure in the data that PCA misses
  4. Its codes span the same subspace as the top 3 PCA scores, but in an arbitrary basis
Show the answer

D. Its codes span the same subspace as the top 3 PCA scores, but in an arbitrary basis

WdWeW_dW_e is the projection onto the top-3 principal subspace, but (GWe,WdG−1)(GW_e,W_dG^{-1}) is equally optimal for every invertible GG, so each code coordinate is an arbitrary mixture of the principal components.

Question 3

A contrastive model is trained with InfoNCE using N=256N=256 candidates per anchor (one positive, 255 negatives), and its loss reaches 0.50.5 nats. What lower bound on the mutual information between the two views does this certify?

  1. 0.50.5 nats
  2. ln⁡256+0.5≈6.05\ln256+0.5\approx6.05 nats
  3. ln⁡256−0.5≈5.05\ln256-0.5\approx5.05 nats
  4. 256×0.5=128256\times0.5=128 nats
Show the answer

C. ln⁡256−0.5≈5.05\ln256-0.5\approx5.05 nats

I≥log⁡N−L=ln⁡256−0.5≈5.55−0.5=5.05I\ge\log N-\mathcal L=\ln256-0.5\approx5.55-0.5=5.05 nats. Even a perfect loss of 00 certifies only ln⁡256≈5.55\ln256\approx5.55 nats, whatever the true mutual information.

Question 4

You train a Siamese encoder only to maximize the cosine similarity between two augmented views of the same image, with no negatives and no other safeguard. What is the likely outcome?

  1. Collapse: every image maps to nearly the same vector, which makes every pair perfectly similar
  2. Excellent features, since the two views share the object's identity
  3. Divergence, because cosine similarity is unbounded
  4. An encoder that exactly undoes the augmentations
Show the answer

A. Collapse: every image maps to nearly the same vector, which makes every pair perfectly similar

A constant output maximizes the similarity of every pair, so nothing forces the encoder to tell images apart. Negatives (InfoNCE), an asymmetric predictor with a stop-gradient (BYOL, SimSiam) or variance penalties (VICReg) rule this solution out or make it unreachable in practice.

Question 5

A linear probe on layer 6 of a language model predicts part-of-speech tags with 95% accuracy. What can you conclude?

  1. The model relies on part of speech to make its predictions
  2. Layer 6 encodes nothing except part of speech
  3. Part-of-speech information is linearly decodable from layer 6
  4. A nonlinear probe would necessarily do worse
Show the answer

C. Part-of-speech information is linearly decodable from layer 6

A probe shows that information is present in a linearly readable form. Whether the model uses it needs interventions, such as removing that direction and measuring the effect on the model's outputs.

Go deeper

Further reading

  • Y. Bengio, A. Courville & P. Vincent, "Representation learning: A review and new perspectives," IEEE Transactions on Pattern Analysis and Machine Intelligence 35, 1798–1828 (2013).
  • T. Mikolov, I. Sutskever, K. Chen, G. Corrado & J. Dean, "Distributed representations of words and phrases and their compositionality," NeurIPS (2013).
  • T. Chen, S. Kornblith, M. Norouzi & G. Hinton, "A simple framework for contrastive learning of visual representations," ICML (2020).
  • I. Goodfellow, Y. Bengio & A. Courville, Deep Learning, ch. 14 "Autoencoders" and ch. 15 "Representation Learning" (MIT Press, 2016).