Machine Learning · Lecture 14

Lecture 14
Learning Without Labels

Part IV · Unsupervised learning  |  what structure means, histograms and kernel density estimation, bandwidth as a bias–variance dial, the curse of dimensionality, anomaly detection and isolation forests, Hopfield networks and Boltzmann machines, self-supervised and contrastive learning, InfoNCE, judging unsupervised results without ground truth  |  reading: Hastie, Tibshirani & Friedman, The Elements of Statistical Learning (2nd ed.), §6.6 and ch. 14; Wasserman, All of Nonparametric Statistics (2006), ch. 6; MacKay, Information Theory, Inference, and Learning Algorithms (2003), ch. 42–43; Chen et al. (2020)

Cartoon: nothing to learn?One stick figure shrugs beside a cloud of unlabelled dots and says there are no labels, so nothing to learn. A second figure points at the cloud, where the dots crowd into two clumps and one dot sits far away, and says there is plenty to learn. No labels, so there isnothing to learn. Two crowds and one loner:that is plenty to learn.
Without labels there is no right answer to predict, but the data still have a shape: where they are dense, how they group, and which points do not belong
In this lecture
  1. What "structure" means
  2. Histograms and kernel density estimation
  3. The curse of dimensionality
  4. Anomaly detection
  5. Energy-based models: Hopfield networks and Boltzmann machines
  6. Self-supervised learning
  7. Evaluating without ground truth
  8. Summary, exercises, projects, reading

Every method so far has been given pairs \((x,y)\) and asked to predict \(y\). Most data come without the \(y\): taxi trips without a note of which days were unusual, images without captions. Part IV asks what can be learned from \(x\) alone. This lecture covers density estimation, the curse of dimensionality, anomaly detection, energy-based networks and self-supervision, and ends with the question that runs through Part IV: without labels, how do we know we have learned anything?

By the end you should be able to build and tune kernel density estimates and derive the \(n^{-1/5}\) bandwidth rate; prove that distances concentrate in high dimensions; detect anomalies by seasonal baseline, isolation forest, local outlier factor and nearest-neighbour distance; prove that a Hopfield network's energy never increases and describe Boltzmann machines; state the InfoNCE bound; and evaluate unsupervised results without ground truth.

1 — What "structure" means

With unlabelled data \(x_1,\dots,x_n\) drawn from \(p(x)\), the only thing to learn is \(p\) itself, or a feature of it. A probability density \(p(x)\) is a histogram at infinite resolution: high where points crowd together, and its area over a range is the probability of landing there. Four features of \(p\) organise Part IV:

Mixture models (Lecture 17a) combine the first three: a density built from clusters, each with a low-dimensional shape. Copulas (Lecture 17b) take a joint density apart instead, into one distribution per variable and a description of how the variables depend on one another. On top sits a newer idea, self-supervised learning (Section 6): hide part of each example and predict it. It is how every large language and vision model is now pretrained.

idea — unsupervised learning is estimating \(p(x)\), in whole or in part

A density estimate is the most complete answer and the hardest to get. A clustering, a projection or an anomaly score each estimates one feature of \(p\) (modes, directions, tails), needs less data, and so remains feasible in high dimensions (Section 3).

spot check 14.1

A city has five years of hourly electricity demand for each of 2,000 buildings and no other information. Which question is unsupervised?

Which question can be answered from the demand curves alone?
It asks only where the distribution of curves is thin. Clusters might match schools, offices and homes, but checking that would need labels.

2 — Histograms and kernel density estimation

The histogram cuts the line into bins of width \(h\) and divides each count by \(nh\), so the bars have total area 1. Its shape depends on where the bins start, and it is a step function even when the density is smooth. The kernel density estimate (KDE) fixes both by centring a small bump on every data point and adding the bumps up.

idea — piles of sand

Tip an identical pile of sand on each data point; crowded points merge into a dune, whose height is the KDE. The kernel is the shape of a pile and the bandwidth \(h\) its spread. Narrow piles reproduce every accident of sampling; wide ones flatten everything into one mound.

definition 14.1 — kernel density estimate

A kernel is a function \(K\ge0\) with

$$\int K=1,\qquad \int uK(u)\,du=0\qquad \mu_2=\int u^2K(u)\,du<\infty.$$

Given data \(x_1,\dots,x_n\in\mathbb R\) and a bandwidth \(h>0\), the kernel density estimate is

$$\hat f_h(x)=\frac1{nh}\sum_{i=1}^nK\!\left(\frac{x-x_i}{h}\right).$$

Common kernels:

In \(d\) dimensions one uses \(h^{-d}K(\lVert x-x_i\rVert/h)\) with a radial kernel, or a bandwidth matrix.

The estimate is itself a density (substitute \(u=(x-x_i)/h\)). The kernel matters little; \(h\) matters a great deal.

data — Old Faithful eruptions

Durations of 272 eruptions of the Old Faithful geyser in Yellowstone, in minutes, with the preceding waiting times, as distributed with R (datasets::faithful, from Härdle, 1991; see also Azzalini and Bowman, 1990), via Vincent Arel-Bundock's Rdatasets on GitHub. Short and long eruptions form two groups. Most durations are recorded to the second, but 67 only to the nearest tenth of a minute, leaving small spikes.

code — histograms, kernel density estimates and three bandwidth selectors
# Old Faithful: histograms, kernel density estimates and three ways to choose the bandwidth
import numpy as np, pandas as pd
x = pd.read_csv('data/faithful.csv').eruptions.to_numpy()        # 272 eruption durations (minutes)
n = len(x); s = x.std(ddof=1); iqr = np.subtract(*np.percentile(x, [75, 25]))
print(f"n = {n}, mean {x.mean():.2f} min, sd {s:.2f}, IQR {iqr:.2f}")

def kde(grid, data, h):                    # Gaussian-kernel density estimate on a grid
    u = (grid[:, None] - data[None, :]) / h
    return np.exp(-0.5 * u**2).sum(1) / (len(data) * h * np.sqrt(2 * np.pi))

def loo_loglik(data, h):                   # leave-one-out log-likelihood per point
    u = (data[:, None] - data[None, :]) / h
    K = np.exp(-0.5 * u**2) / (h * np.sqrt(2 * np.pi)); np.fill_diagonal(K, 0)
    return np.mean(np.log(K.sum(1) / (len(data) - 1)))

def lscv(data, h):                         # least-squares cross-validation (estimates ISE - const)
    d = data[:, None] - data[None, :]; m = len(data)
    phi = lambda v, s: np.exp(-0.5 * (v / s)**2) / (s * np.sqrt(2 * np.pi))
    term1 = phi(d, h * np.sqrt(2)).sum() / m**2
    K = phi(d, h); np.fill_diagonal(K, 0)
    return term1 - 2 * K.sum() / (m * (m - 1))

hs = np.exp(np.linspace(np.log(0.03), np.log(1.5), 400))
h_silv = 0.9 * min(s, iqr / 1.34) * n**(-1/5)                   # Silverman's rule of thumb
h_ll = hs[np.argmax([loo_loglik(x, h) for h in hs])]
h_ls = hs[np.argmin([lscv(x, h) for h in hs])]
for name, h in [("Silverman's rule", h_silv), ("leave-one-out likelihood", h_ll), ("least-squares CV", h_ls)]:
    g = np.linspace(1, 6, 1001); f = kde(g, x, h)
    modes = g[1:-1][(f[1:-1] > f[:-2]) & (f[1:-1] > f[2:])]
    print(f"{name:26s} h = {h:.3f}  LOO log-lik {loo_loglik(x, h):+.3f}  modes at {np.round(modes, 2)}")
for h in [0.05, 1.0]:
    f = kde(np.linspace(1, 6, 1001), x, h); g = np.linspace(1, 6, 1001)
    print(f"h = {h:4.2f}: {((f[1:-1] > f[:-2]) & (f[1:-1] > f[2:])).sum():2d} modes, LOO log-lik {loo_loglik(x, h):+.3f}")
for bins in [5, 20, 80]:                                         # histograms: same dial, coarser
    c, e = np.histogram(x, bins=bins, range=(1.5, 5.5))
    print(f"histogram, {bins:2d} bins of width {e[1]-e[0]:.2f}: {np.sum(c == 0):2d} empty bins")
n = 272, mean 3.49 min, sd 1.14, IQR 2.29
Silverman's rule           h = 0.335  LOO log-lik -1.111  modes at [1.98 4.38]
leave-one-out likelihood   h = 0.102  LOO log-lik -0.996  modes at [1.87 2.86 4.48]
least-squares CV           h = 0.102  LOO log-lik -0.996  modes at [1.87 2.86 4.48]
h = 0.05: 12 modes, LOO log-lik -1.021
h = 1.00:  1 modes, LOO log-lik -1.573
histogram,  5 bins of width 0.80:  0 empty bins
histogram, 20 bins of width 0.20:  2 empty bins
histogram, 80 bins of width 0.05: 22 empty bins

Silverman's rule of thumb,

$$h=0.9\min(s,\mathrm{IQR}/1.34)\,n^{-1/5},$$

is the normal-theory choice (Theorem 14.1), made robust by the interquartile range. It gives \(h=0.335\) minutes and two modes, at 1.98 and 4.38; the geyser is far from normal, so it oversmooths. Two data-driven selectors agree on \(h=0.102\):

Both find a third, small mode at 2.86 minutes; whether it is real or an artefact of rounding, the data cannot settle. At \(h=0.05\) there are 12 wiggles and at \(h=1\) a single hump, both with worse held-out likelihood; with 80 histogram bins, 22 are empty.

The bandwidth dial

A KDE of the 272 eruptions (rose; rug below) over a histogram with bin width \(2h\). Slide the bandwidth and watch the modes and the leave-one-out log-likelihood. Try the waiting times and the box kernel.

The bandwidth trades bias for variance, as \(k\) did in \(k\)-nearest neighbours (Lecture 1). A wide kernel shaves peaks and fills valleys (bias of about \(h^2f''\)); a narrow one averages over only about \(nh\) points (variance). The mean integrated squared error (MISE) adds the two, integrated along the axis.

theorem 14.1 — bias and variance of the kernel density estimate

Let \(x_1,\dots,x_n\) be independent with a density \(f\) that has two bounded continuous derivatives, and let \(K\) be a kernel as in Definition 14.1 with \(R(K)=\int K^2<\infty\). As \(n\to\infty\) and \(h\to0\) with \(nh\to\infty\),

$$\mathbb E\,\hat f_h(x)-f(x)=\tfrac12h^2\mu_2f''(x)+o(h^2),$$ $$\operatorname{Var}\hat f_h(x)=\frac{f(x)R(K)}{nh}+o\!\left(\frac1{nh}\right).$$

Integrating squared bias plus variance over \(x\) gives the asymptotic mean integrated squared error

$$\mathrm{AMISE}(h)=\frac{h^4\mu_2^2R(f'')}{4}+\frac{R(K)}{nh},$$

which is minimised by

$$h^*=\left(\frac{R(K)}{\mu_2^2R(f'')\,n}\right)^{1/5}\propto n^{-1/5},\qquad \mathrm{AMISE}(h^*)\propto n^{-4/5}.$$

Bias. Each term of \(\hat f_h\) has the same mean, so

$$\mathbb E\,\hat f_h(x)=\frac1h\int K\!\left(\frac{x-t}{h}\right)f(t)\,dt=\int K(u)f(x-hu)\,du.$$

By Taylor's theorem,

$$f(x-hu)=f(x)-huf'(x)+\tfrac12h^2u^2f''(x)+o(h^2).$$

Integrating against \(K\): the first term gives \(f(x)\), the second vanishes because \(\int uK=0\), and the third gives \(\tfrac12h^2\mu_2f''(x)\).

Variance. The terms are independent, so the variance is \(1/n\) times the variance of one term, which is at most its second moment:

$$\frac1{nh^2}\int K^2\!\left(\frac{x-t}{h}\right)f(t)\,dt=\frac1{nh}\int K^2(u)f(x-hu)\,du=\frac{f(x)R(K)}{nh}+o\!\left(\frac1{nh}\right).$$

Subtracting the squared mean changes this only by \(O(1/n)\), which is smaller.

Optimum. Integrate \(\text{bias}^2+\text{variance}\) over \(x\), using \(\int f=1\), to get the AMISE. Setting its derivative to zero,

$$h^3\mu_2^2R(f'')-\frac{R(K)}{nh^2}=0$$

gives \(h^*\), at which both terms are of order \(n^{-4/5}\). Passing from the pointwise expansions to the integrated one needs uniformly small remainders, which holds under the stated conditions; see Wasserman (2006, §6.3) and Wand and Jones (1995, ch. 2). \(\square\)

For a normal density with standard deviation \(\sigma\) and a Gaussian kernel, the formula gives (Exercise 2)

$$h^*=(4/3)^{1/5}\sigma n^{-1/5}\approx1.06\,\sigma n^{-1/5},$$

the origin of Silverman's rule. The error falls like \(n^{-4/5}\), slower than the \(n^{-1}\) of a correct parametric model: the price of assuming nothing about the shape. And \(h^*\) depends on the unknown roughness \(R(f'')\), so it must be estimated, as cross-validation does. To check the rates, the code averages the exactly computable integrated squared error over 40 standard normal samples per \(n\) and finds the best \(h\) on a grid.

code — the rates of Theorem 14.1 by simulation
# Theorem 14.1 by simulation: the MISE-optimal bandwidth shrinks like n^(-1/5), the error like n^(-4/5)
rng = np.random.default_rng(0)
phi = lambda v, s: np.exp(-0.5 * (v / s)**2) / (s * np.sqrt(2 * np.pi))
def ise(data, h):            # exact integrated squared error of a Gaussian KDE when the truth is N(0,1)
    d = data[:, None] - data[None, :]; m = len(data)
    return phi(d, h * np.sqrt(2)).sum() / m**2 - 2 * phi(data, np.sqrt(1 + h**2)).mean() + 1 / (2 * np.sqrt(np.pi))
ns, hopt, mise = [50, 100, 200, 400, 800, 1600], [], []
hgrid = np.exp(np.linspace(np.log(0.05), np.log(1.2), 60))
for m in ns:
    reps = [rng.standard_normal(m) for _ in range(40)]
    M = np.array([np.mean([ise(r, h) for r in reps]) for h in hgrid])
    hopt.append(hgrid[M.argmin()]); mise.append(M.min())
    print(f"n = {m:5d}: best h = {hopt[-1]:.3f} (theory 1.06 n^-1/5 = {1.06 * m**-0.2:.3f}), MISE = {M.min():.5f}")
b_h = np.polyfit(np.log(ns), np.log(hopt), 1)[0]; b_m = np.polyfit(np.log(ns), np.log(mise), 1)[0]
print(f"log-log slopes: bandwidth {b_h:.3f} (theory -0.2), MISE {b_m:.3f} (theory -0.8)")
n =    50: best h = 0.535 (theory 1.06 n^-1/5 = 0.485), MISE = 0.00948
n =   100: best h = 0.480 (theory 1.06 n^-1/5 = 0.422), MISE = 0.00595
n =   200: best h = 0.387 (theory 1.06 n^-1/5 = 0.367), MISE = 0.00316
n =   400: best h = 0.329 (theory 1.06 n^-1/5 = 0.320), MISE = 0.00183
n =   800: best h = 0.296 (theory 1.06 n^-1/5 = 0.278), MISE = 0.00125
n =  1600: best h = 0.252 (theory 1.06 n^-1/5 = 0.242), MISE = 0.00079
log-log slopes: bandwidth -0.222 (theory -0.2), MISE -0.729 (theory -0.8)
5010020040080016000.0010.010.11sample size n (log scale)log scalebest bandwidth h*minimum MISE1.06 n^(-1/5)
Best bandwidth (sky) and the smallest achievable mean integrated squared error (rose) against sample size, both on log scales, for a Gaussian KDE of standard normal data. The dashed line is the asymptotic optimum \(1.06\,n^{-1/5}\).

The fitted slopes are −0.222 for the bandwidth and −0.729 for the error, against the asymptotic −0.2 and −0.8: the expansions drop terms that still matter for a few hundred points, but direction and rough size are as the theorem says.

spot check 14.2

A KDE with a well-chosen bandwidth is fitted to 1,000 points. You collect 32,000 points from the same source. By what factor should the bandwidth be multiplied, according to Theorem 14.1?

\(h^*\propto n^{-1/5}\), and \(n\) grows by a factor of 32.
\(32^{-1/5}=2^{-1}=0.5\): halve the bandwidth. The error falls by \(32^{-4/5}=1/16\): 32 times the data buys a 16-fold reduction in MISE, not a 32-fold one.
Bayes — density estimation is the generative half of Bayes' rule

Bayes' rule writes a classifier as \(P(y\mid x)\propto\pi_y\,p(x\mid y)\). A generative classifier estimates the class-conditional densities \(p(x\mid y)\) and priors \(\pi_y\); naive Bayes (Lectures 4 and 13) uses products of one-dimensional densities, and a KDE per class gives a nonparametric version that can draw any decision boundary. The same densities detect points unlike any class, sample new data, and survive a shift in base rates (new \(\pi_y\), not new densities). A KDE is also a mixture with one equally weighted Gaussian on every point: the extreme case of the mixtures of Lecture 17a.

history — Rosenblatt, Parzen and the window

Murray Rosenblatt (Chicago) introduced the kernel estimate, with its bias and variance, in "Remarks on some nonparametric estimates of a density function" (Annals of Mathematical Statistics, 1956). Emanuel Parzen (Stanford) gave the general theory in "On estimation of a probability density function and mode" (1962), hence the Parzen window. Evelyn Fix and Joseph Hodges had proposed nearest-neighbour discrimination in a 1951 US Air Force report. Bernard Silverman's Density Estimation for Statistics and Data Analysis (1986) made the rule of thumb standard, using Old Faithful (a different sample of 107 eruptions) throughout.

3 — The curse of dimensionality

A KDE needs a few hundred points in one dimension and millions in ten. The "curse of dimensionality" (coined by Richard Bellman in 1957 for dynamic programming) names facts about high-dimensional space that defeat low-dimensional intuition. The two most useful:

theorem 14.2 — volume in a thin shell; concentration of distances

(a) Thin shell. For \(0<\varepsilon<1\), the fraction of the volume of a ball of radius \(r\) in \(\mathbb R^d\) lying within \(\varepsilon r\) of its surface is

$$1-(1-\varepsilon)^d\;\longrightarrow\;1\qquad(d\to\infty).$$

(b) Concentration. Let \(X,Y\in\mathbb R^d\) be independent, each with independent coordinates distributed like \(Z\), where \(Z\) has variance \(\sigma^2\) and a finite fourth moment. Let \(v=\operatorname{Var}\big((Z_1-Z_2)^2\big)\) for independent copies \(Z_1,Z_2\). Then

$$\mathbb E\lVert X-Y\rVert^2=2d\sigma^2,\qquad \operatorname{Var}\lVert X-Y\rVert^2=d\,v.$$

Hence the squared distance divided by its mean has standard deviation

$$\frac{\sqrt v}{2\sigma^2\sqrt d}\;\longrightarrow\;0$$

and for every \(\delta>0\),

$$P\left(\left|\frac{\lVert X-Y\rVert^2}{2d\sigma^2}-1\right|>\delta\right)\le\frac{v}{4\sigma^4\delta^2d}\to0.$$

(a) Volume in \(\mathbb R^d\) scales as the \(d\)-th power of length, so the inner ball of radius \((1-\varepsilon)r\) has \((1-\varepsilon)^d\) times the volume of the whole ball. The shell is the rest.

(b) Write \(\lVert X-Y\rVert^2=\sum_{k=1}^dD_k\) with \(D_k=(X_k-Y_k)^2\). The \(D_k\) are independent and identically distributed, with mean

$$\mathbb E(X_k-Y_k)^2=\operatorname{Var}X_k+\operatorname{Var}Y_k=2\sigma^2$$

and variance \(v\), finite because \(Z\) has a fourth moment. Means add and, by independence, so do variances, giving \(2d\sigma^2\) and \(dv\).

Chebyshev's inequality with deviation \(\delta\cdot2d\sigma^2\) gives the bound

$$\frac{dv}{4d^2\sigma^4\delta^2}.\qquad\square$$

Most of a high-dimensional orange is peel (a). And a squared distance is a sum of \(d\) independent terms, which concentrates, so the nearest neighbour is barely nearer than the farthest (b); the same holds for a fixed query point in place of \(Y\). Methods built on "nearby points are similar" (the KDE, nearest neighbours, the detectors of Section 4) lose their grip. Neighbourhoods also empty out: to hold 10% of uniform points in a unit cube, a sub-cube needs side 0.1 in one dimension, \(0.1^{1/10}\approx0.79\) in ten and \(0.1^{1/100}\approx0.98\) in a hundred. The code also tests a KDE with bandwidth \(h=n^{-1/(d+4)}\) on held-out data.

code — distances, shells and density estimation as the dimension grows
# The curse of dimensionality: distances concentrate, volume moves to the shell, neighbourhoods empty
import numpy as np
rng = np.random.default_rng(1)
print("   d   mean dist   sd/mean   (max-min)/min   P(in 10% shell)   KDE log-lik gap")
for d in [1, 2, 10, 100, 1000]:
    X = rng.uniform(size=(500, d)); q = rng.uniform(size=d)
    D = np.linalg.norm(X - q, axis=1)                         # distances from one query point
    shell = 1 - 0.9**d                                        # fraction of a d-ball within 10% of its surface
    # a Gaussian KDE (Scott's bandwidth) fitted to 500 N(0,I) points, scored on 500 new points,
    # compared with the true log-density: how much likelihood per dimension does the KDE lose?
    Z, Zt = rng.standard_normal((500, d)), rng.standard_normal((500, d))
    h = 500**(-1 / (d + 4))
    sq = (Zt**2).sum(1)[:, None] + (Z**2).sum(1)[None, :] - 2 * Zt @ Z.T
    lk = -sq / (2 * h * h) - d * np.log(h * np.sqrt(2 * np.pi))
    kde_ll = (np.log(np.exp(lk - lk.max(1, keepdims=True)).mean(1)) + lk.max(1)).mean()
    true_ll = (-0.5 * (Zt**2).sum(1) - 0.5 * d * np.log(2 * np.pi)).mean()
    print(f"{d:4d}   {D.mean():8.3f}   {D.std() / D.mean():7.3f}   {(D.max() - D.min()) / D.min():12.3f}"
          f"   {shell:14.3f}   {(true_ll - kde_ll) / d:10.3f} per dim")
   d   mean dist   sd/mean   (max-min)/min   P(in 10% shell)   KDE log-lik gap
   1      0.251     0.614       1391.241            0.100        0.003 per dim
   2      0.586     0.428         82.116            0.190        0.014 per dim
  10      1.203     0.186          2.480            0.651        0.070 per dim
 100      4.271     0.055          0.372            1.000        0.248 per dim
1000     12.957     0.016          0.115            1.000        0.397 per dim

For 500 uniform points in the unit cube, the relative spread of distances from a query point falls from 0.614 in one dimension to 0.055 in 100 and 0.016 in 1,000, close to the \(1/\sqrt d\) rate. The farthest point is over a thousand times farther than the nearest in one dimension, only 11.5% farther in 1,000. Essentially all of a 100-dimensional ball lies within 10% of its surface. The KDE loses 0.003 nats per dimension in one dimension but 0.248 in 100. Since the best error falls like \(n^{-4/(4+d)}\), halving it takes \(2^{14/4}\approx11\) times the data in 10 dimensions and \(2^{26}\), about 67 million times, in 100.

All distances look alike

All 19,900 pairwise distances of 200 random points in \(d\) dimensions, divided by their mean. Slide \(d\) up and they bunch around 1.

Real data often escape the curse because their intrinsic dimension, the number of coordinates needed to say where the points lie, is far below the number recorded; a crumpled sheet of paper is still two-dimensional. Fashion-MNIST images have 784 pixels, but neighbouring pixels are strongly correlated and few possible images look like clothing. Lecture 16 finds such low-dimensional sets; the encoders of Section 6 learn coordinates on them in which distances mean something again.

spot check 14.3

What fraction of the volume of a 100-dimensional ball lies within 1% of its radius from the surface?

Theorem 14.2(a) with \(\varepsilon=0.01\) and \(d=100\).
\(1-0.99^{100}=0.634\). A shell only 1% thick holds almost two-thirds of the volume; at \(d=1000\) it holds all but 0.004%.

4 — Anomaly detection

An anomaly is a point that the bulk of the data makes unlikely: flag \(x\) when \(\hat p(x)\) is small. Three families of cheaper stand-ins:

All three fit "normal" from the same unlabelled data and assume anomalies are too rare to distort it. Two cautions. An anomaly is not an error: a blizzard is real, merely unusual. And rarity means false alarms: if one day in a thousand is unusual and the detector wrongly flags one ordinary day in a hundred, most flagged days are ordinary, the base-rate problem of Lecture 13.

data — NYC taxi passengers (Numenta Anomaly Benchmark)

New York City taxi passengers per half-hour from 1 July 2014 to 31 January 2015 (10,320 values), aggregated from Taxi and Limousine Commission trip records by Numenta for the Numenta Anomaly Benchmark (NAB; Lavin and Ahmad, 2015), file realKnownCause/nyc_taxi.csv on GitHub (AGPL-3.0). NAB labels five anomalies, "the NYC marathon, Thanksgiving, Christmas, New Year's Day, and a snow storm", each inside a window several days wide where detections count as correct (labels/combined_windows.json). The labels are used only to judge results, never to fit.

Taxi demand has a strong weekly cycle, so the first detector's baseline for each half-hour is the median of all values at that half-hour of the week (the median resists the anomalies). The residual is the log ratio to baseline; a day's score is its mean absolute residual over 48 half-hours.

code — a seasonal baseline and the days that do not fit
# NYC taxi demand: a seasonal baseline, residuals, and the days that do not fit
import pandas as pd, json
df = pd.read_csv('data/nyc_taxi.csv', parse_dates=['timestamp'])        # passengers per 30 minutes
win = json.load(open('data/combined_windows.json'))['realKnownCause/nyc_taxi.csv']
win = [(pd.Timestamp(a).normalize(), pd.Timestamp(b).normalize()) for a, b in win]   # NAB's 5 windows
slot = (df.timestamp.dt.dayofweek * 48 + df.timestamp.dt.hour * 2 + df.timestamp.dt.minute // 30).to_numpy()
base = df.value.groupby(slot).transform('median').to_numpy()          # typical value for this half-hour of the week
df['r'] = np.log(df.value / base)                                      # log residual: 0.1 is about 10% above normal
df['date'] = df.timestamp.dt.normalize()
day = df.groupby('date').agg(score=('r', lambda z: np.abs(z).mean()), total=('value', 'sum'))
print(f"{len(df):,} half-hours, {len(day)} days, {day.total.mean():,.0f} passengers a day on average")
in_win = lambda t: any(a <= t <= b for a, b in win)
def report(scores, k=10, show=True):
    top = scores.sort_values(ascending=False).index[:k]
    hits = [in_win(t) for t in top]
    found = sum(any(a <= t <= b for t in top) for a, b in win)
    if show:
        for t, h in zip(top, hits): print(f"   {t:%a %d %b %Y}  score {scores[t]:.3f}  {'in a labelled window' if h else '-'}")
    return sum(hits), found
h, f = report(day.score)
print(f"top 10 days: {h} inside NAB's windows; windows found: {f} of 5")
r = df.set_index('timestamp').r
print("largest half-hour residuals:", ", ".join(f"{t:%d %b %H:%M} ({v:+.2f})" for t, v in r[r.abs().nlargest(6).index].items()))
print("Sun 2 Nov 2014 (marathon, and the night the clocks went back):",
      ", ".join(f"{t:%H:%M} {v:+.2f}" for t, v in r['2014-11-02 00:30':'2014-11-02 03:00'].items()))
10,320 half-hours, 215 days, 726,603 passengers a day on average
   Tue 27 Jan 2015  score 2.348  in a labelled window
   Thu 01 Jan 2015  score 0.743  in a labelled window
   Mon 26 Jan 2015  score 0.743  in a labelled window
   Thu 25 Dec 2014  score 0.707  in a labelled window
   Fri 26 Dec 2014  score 0.594  in a labelled window
   Mon 01 Sep 2014  score 0.459  -
   Thu 27 Nov 2014  score 0.455  in a labelled window
   Fri 04 Jul 2014  score 0.432  -
   Sat 05 Jul 2014  score 0.421  -
   Sat 27 Dec 2014  score 0.399  in a labelled window
top 10 days: 7 inside NAB's windows; windows found: 4 of 5
largest half-hour residuals: 27 Jan 03:00 (-5.58), 27 Jan 04:00 (-5.45), 27 Jan 03:30 (-5.16), 27 Jan 01:00 (-5.01), 27 Jan 02:00 (-4.90), 27 Jan 05:30 (-4.76)
Sun 2 Nov 2014 (marathon, and the night the clocks went back): 00:30 -0.06, 01:00 +0.53, 01:30 +0.51, 02:00 -0.38, 02:30 -0.35, 03:00 -0.41
JulAugSepOctNovDecJan0.000.250.500.751.00passengers per day (millions)
Daily taxi passengers (sky), with NAB's five labelled anomaly windows shaded and the ten highest-scoring days of the seasonal-residual detector circled.

The top day by far is Tuesday 27 January 2015, when a forecast blizzard closed the roads to non-emergency traffic overnight: at 3 a.m. the residual is −5.58, demand about 0.4% of normal. New Year's Day, Christmas and the day after, and Thanksgiving follow. Seven of the top ten days fall inside NAB's windows, and four of the five windows are found. The three "false alarms", 4 and 5 July and Labor Day (1 September), are public holidays NAB did not label: the labels, too, are uncertain.

The marathon on Sunday 2 November ranks only 30th of 215: during the race, 10 a.m. to 3 p.m., demand stayed within about 4% of baseline. The day's clearest signal is at 1 a.m., 70% above normal (log residual +0.53), then a deficit: daylight saving time ended at 2 a.m., so the hour from 1 to 2 a.m. happened twice in one bin. "Finding the marathon" mostly means finding the clock change; every hand-made label is a claim to check.

The second family treats each day as a point in 48-dimensional space (log demand per half-hour). The simplest score is the distance to the \(k\)-th nearest neighbour. The local outlier factor (LOF; Breunig et al., 2000) compares a point's local density with its neighbours', so a uniformly sparse region (weekends) is not penalised as such; a score well above 1 means "less dense than my neighbours".

definition 14.2 — isolation forest

An isolation tree is grown on a random subsample of \(\psi\) points by recursive splitting:

The path length \(h(x)\) is the number of edges from the root to the leaf containing \(x\), with a correction for leaves that still hold several points. An isolation forest (Liu, Ting and Zhou, 2008) averages over many trees and reports

$$s(x)=2^{-\mathbb E[h(x)]/c(\psi)},\qquad c(\psi)=2H(\psi-1)-\frac{2(\psi-1)}{\psi},$$

where \(H(i)\approx\ln i+0.5772\) is the harmonic number. The normaliser \(c(\psi)\) is the average path length of an unsuccessful search in a binary search tree on \(\psi\) keys, used as the typical depth.

Anomalies are "few and different", so random splits cut them off early, as "taller than 1.9 m?" singles out the one two-metre person in twenty questions. The trees (Lecture 8) have no target; only depth matters. With no distances, the method suffers less from Theorem 14.2, and it scales to millions of points because each tree sees a small subsample.

code — isolation forest, local outlier factor and nearest-neighbour distance on daily profiles
# Isolation forest, local outlier factor and k-NN distance on daily demand profiles (48 numbers per day)
from sklearn.ensemble import IsolationForest
from sklearn.neighbors import LocalOutlierFactor, NearestNeighbors
prof = np.log(df.pivot_table(index='date', columns=df.timestamp.dt.hour * 2 + df.timestamp.dt.minute // 30,
                          values='value'))                       # 215 days x 48 half-hours, log scale
Xd = prof.to_numpy()
iso = IsolationForest(n_estimators=500, random_state=0).fit(Xd)
scores = {'isolation forest': -iso.score_samples(Xd),
          'local outlier factor': -LocalOutlierFactor(n_neighbors=10).fit(Xd).negative_outlier_factor_,
          'distance to 5th neighbour': NearestNeighbors(n_neighbors=6).fit(Xd).kneighbors(Xd)[0][:, -1],
          'seasonal residual (c4)': day.score.reindex(prof.index).to_numpy()}
for name, sc in scores.items():
    h, f = report(pd.Series(sc, index=prof.index), show=False)
    top = pd.Series(sc, index=prof.index).nlargest(5).index
    print(f"{name:26s} top-10 in windows: {h:2d}   windows found: {f}   top 5: {', '.join(f'{t:%d %b}' for t in top)}")
# the score: s = 2^(-E[h]/c(m)), with E[h] the mean depth at which a day is isolated, m = 215 days per tree
c = lambda m: 2 * (np.log(m - 1) + 0.5772156649) - 2 * (m - 1) / m
s_iso = -iso.score_samples(Xd); Eh = -c(len(Xd)) * np.log2(s_iso)
i27 = prof.index.get_loc(pd.Timestamp('2015-01-27'))
print(f"c(215) = {c(215):.2f}; 27 Jan: s = {s_iso[i27]:.3f}, isolated at mean depth {Eh[i27]:.1f}; "
      f"median day: s = {np.median(s_iso):.3f}, depth {np.median(Eh):.1f}")
print("LOF top 10:", ", ".join(f"{t:%d %b}" for t in pd.Series(scores['local outlier factor'], index=prof.index).nlargest(10).index))
isolation forest           top-10 in windows:  7   windows found: 5   top 5: 27 Jan, 26 Jan, 25 Dec, 01 Jan, 01 Nov
local outlier factor       top-10 in windows: 10   windows found: 5   top 5: 27 Jan, 26 Jan, 01 Jan, 01 Nov, 26 Dec
distance to 5th neighbour  top-10 in windows: 10   windows found: 4   top 5: 27 Jan, 26 Jan, 25 Dec, 26 Dec, 01 Jan
seasonal residual (c4)     top-10 in windows:  7   windows found: 4   top 5: 27 Jan, 01 Jan, 26 Jan, 25 Dec, 26 Dec
c(215) = 9.90; 27 Jan: s = 0.852, isolated at mean depth 2.3; median day: s = 0.401, depth 13.0
LOF top 10: 27 Jan, 26 Jan, 01 Jan, 01 Nov, 26 Dec, 02 Nov, 31 Dec, 26 Nov, 28 Jan, 25 Dec

All four detectors put the blizzard first; the isolation forest isolates it at an average depth of 2.3 cuts (\(s=0.852\)), against 13.0 for a median day (\(s=0.401\)). LOF has all ten top days inside a window and touches all five windows. But the windows are wide (27 of the 215 days, 13%), and LOF's list includes 31 December, 26 November and 28 January, eves and morrows of labelled events. The marathon window is "found" through 1 November (Halloween-night crowds) and, for LOF, the clock change on 2 November. No detector sees the race.

Anomalous days in NYC taxi demand

Daily passengers (sky), the median baseline (dashed) and NAB's windows (amber). Flagged days are circled moss inside a window, rose outside. Which "false alarms" appear as you flag more?

spot check 14.4

In an isolation forest with subsamples of \(\psi=256\) points, a point's average path length equals \(c(256)\). What is its anomaly score \(s\)?

Put \(\mathbb E[h(x)]=c(\psi)\) into Definition 14.2.
\(s=2^{-1}=0.5\): the point is isolated at exactly the typical depth, neither early (anomalous, \(s\to1\)) nor late (deep in a crowd, \(s\) well below 0.5).

5 — Energy-based models: Hopfield networks and Boltzmann machines

Physics describes many systems as a ball rolling into a valley. An energy \(E(s)\) scores every state \(s\), the system moves towards lower energy, and at temperature \(T\) state \(s\) has Boltzmann probability

$$p(s)=\frac{e^{-E(s)/T}}{Z}.$$

Near \(T=0\) the system sits in the lowest valleys; at high \(T\) it wanders almost uniformly. To model data, choose an energy whose valleys sit where the data are, so \(p(s)\propto e^{-E(s)}\); learning means shaping the landscape. The first neural networks to learn without labels worked this way.

definition 14.3 — Hopfield network

A Hopfield network has \(N\) binary units \(s_i\in\{-1,+1\}\) and symmetric weights with zero diagonal:

$$W_{ij}=W_{ji},\qquad W_{ii}=0.$$

Its energy is

$$E(s)=-\tfrac12\,s^\top Ws=-\sum_{i<j}W_{ij}s_is_j.$$

An asynchronous update chooses one unit \(i\) and sets it to the sign of its local field \(h_i=\sum_jW_{ij}s_j\), with \(+1\) when \(h_i=0\).

To store patterns \(\xi^1,\dots,\xi^P\in\{-1,+1\}^N\), the Hebb rule sets

$$W=\frac1N\sum_{\mu=1}^P\xi^\mu(\xi^\mu)^\top\quad\text{with the diagonal set to zero.}$$

The Hebb rule strengthens connections between units that agree in the stored patterns ("cells that fire together wire together"). With one pattern \(\xi\), the field at \(s=\xi\) is \(h_i=\frac{N-1}N\xi_i\), so \(\xi\) is a fixed point, and from a copy with fewer than half its bits wrong every update moves towards it. This is a content-addressable memory: as the first bars of a song recall the rest, a corrupted pattern rolls down into its valley. But why does the network settle at all?

theorem 14.3 — the Hopfield energy never increases

Under asynchronous updates:

Suppose unit \(i\) changes from \(s_i\) to \(s_i'\), and let \(\Delta=s_i'-s_i\in\{-2,+2\}\).

Using \(W_{ij}=W_{ji}\) and \(W_{ii}=0\), the terms of \(E\) involving \(s_i\) are \(-s_i\sum_{j\ne i}W_{ij}s_j=-s_ih_i\), and \(h_i\) does not involve \(s_i\). Hence

$$\Delta E=-\Delta\,h_i.$$

A flip happens only when \(s_i'=\operatorname{sign}(h_i)\ne s_i\), so either \(\Delta\) has the sign of \(h_i\), giving \(\Delta E=-2|h_i|<0\); or \(h_i=0\), giving \(\Delta E=0\), and by the tie rule the flip is from \(-1\) to \(+1\).

The state space is finite, so the energy can strictly decrease only finitely often. Between strict decreases every flip turns a \(-1\) into a \(+1\), which can happen at most \(N\) times in a row. So only finitely many flips occur, and once none is possible the state is a fixed point. \(\square\)

Symmetry and asynchrony are both essential: otherwise the network can cycle or oscillate (Exercise 4). The theorem guarantees some minimum, not the right one. Too many stored patterns create crosstalk, stored patterns stop being minima and spurious mixtures appear. For random patterns the limit is near \(P\approx0.138N\) with small errors allowed (Amit, Gutfreund and Sompolinsky, 1985), and about \(N/(2\ln N)\) for perfect recall (McEliece et al., 1987).

code — storing and recalling patterns
# Hopfield networks: store patterns with the Hebb rule, recall them from corrupted copies
import numpy as np
rng = np.random.default_rng(2)
def hebb(pats):                                   # W = (1/N) sum_mu xi xi^T, zero diagonal
    W = pats.T @ pats / pats.shape[1]; np.fill_diagonal(W, 0); return W
def energy(W, s): return -0.5 * s @ W @ s
def recall(W, s, rng, sweeps=20):                 # asynchronous updates in random order
    s = s.copy(); E = [energy(W, s)]
    for _ in range(sweeps):
        changed = 0
        for i in rng.permutation(len(s)):
            new = 1 if W[i] @ s >= 0 else -1
            if new != s[i]: s[i] = new; changed += 1; E.append(energy(W, s))
        if changed == 0: break
    assert np.all(np.diff(E) <= 1e-9)             # Theorem 14.3: the energy never goes up
    return s
N = 400
print(f"random patterns, N = {N} neurons, start from a stored pattern with 10% of its bits flipped")
for P in [10, 20, 40, 50, 60, 80]:
    pats = rng.choice([-1, 1], size=(P, N)); W = hebb(pats); ok = []
    for mu in range(min(P, 20)):
        s0 = pats[mu] * np.where(rng.random(N) < 0.1, -1, 1)
        ok.append((recall(W, s0, rng) @ pats[mu]) / N)
    print(f"  P = {P:3d} (P/N = {P / N:.3f}): mean overlap after recall {np.mean(ok):.3f}, "
          f"perfect recalls {np.mean(np.array(ok) > 0.999):.0%}")
# real images are not random: binarised Fashion-MNIST items overlap strongly
import gzip
def load_fmnist(kind):
    with gzip.open(f'data/{kind}-images-idx3-ubyte.gz') as f: X = np.frombuffer(f.read(), np.uint8, offset=16)
    with gzip.open(f'data/{kind}-labels-idx1-ubyte.gz') as f: y = np.frombuffer(f.read(), np.uint8, offset=8)
    return X.reshape(-1, 784).astype(np.float32) / 255, y.astype(np.int32)
Xtr, ytr = load_fmnist('train'); Xte, yte = load_fmnist('t10k')
names = ['T-shirt', 'trouser', 'pullover', 'dress', 'coat', 'sandal', 'shirt', 'sneaker', 'bag', 'boot']
for classes in [(1, 8), (1, 7, 8, 9), (0, 1, 2, 3, 7, 8)]:
    idx = [np.flatnonzero(ytr == c)[0] for c in classes]
    pats = np.where(Xtr[idx] > 0.3, 1, -1); W = hebb(pats)
    ov = pats @ pats.T / 784; res = []
    for mu in range(len(idx)):
        s0 = pats[mu] * np.where(rng.random(784) < 0.25, -1, 1)
        res.append(recall(W, s0, rng) @ pats[mu] / 784)
    print(f"{len(idx)} items ({', '.join(names[c] for c in classes)}): mean |overlap| between stored items "
          f"{np.abs(ov[np.triu_indices(len(idx), 1)]).mean():.2f}; overlap after recall from 25% noise: "
          + ", ".join(f"{r:.2f}" for r in res))
random patterns, N = 400 neurons, start from a stored pattern with 10% of its bits flipped
  P =  10 (P/N = 0.025): mean overlap after recall 1.000, perfect recalls 100%
  P =  20 (P/N = 0.050): mean overlap after recall 1.000, perfect recalls 100%
  P =  40 (P/N = 0.100): mean overlap after recall 0.998, perfect recalls 75%
  P =  50 (P/N = 0.125): mean overlap after recall 0.987, perfect recalls 45%
  P =  60 (P/N = 0.150): mean overlap after recall 0.940, perfect recalls 15%
  P =  80 (P/N = 0.200): mean overlap after recall 0.538, perfect recalls 0%
2 items (trouser, bag): mean |overlap| between stored items 0.04; overlap after recall from 25% noise: 1.00, 1.00
4 items (trouser, sneaker, bag, boot): mean |overlap| between stored items 0.24; overlap after recall from 25% noise: 1.00, 1.00, 1.00, 0.97
6 items (T-shirt, trouser, pullover, dress, sneaker, bag): mean |overlap| between stored items 0.26; overlap after recall from 25% noise: 0.78, 0.76, 0.62, 0.89, 1.00, 1.00

With \(N=400\) units, recall from 10% noise is perfect up to 20 random patterns; at 40 (above \(N/(2\ln N)\approx33.4\)) a quarter of recalls end a few bits away; at 60 (\(P/N=0.15\)) the mean overlap falls to 0.940; at 80 memory has collapsed. Binarised Fashion-MNIST items overlap by 0.24–0.26 on average, against about \(1/\sqrt{784}\approx0.04\) for random patterns. Four items are recalled almost perfectly, but with six (load \(6/784\)) four end well away, with overlaps between 0.62 and 0.89: crosstalk is a sum of overlaps, so correlated memories interfere far more.

A Hopfield network of 144 units

Store some of four 12×12 patterns (Hebb rule), corrupt one, and step or run the updates. Thumbnails show overlaps; the energy trace only goes down (Theorem 14.3). Store all four with noise near 45% to find spurious states.

spot check 14.5

A Hopfield network has three units with \(W_{12}=1\), \(W_{13}=-2\), \(W_{23}=1\), and is in state \(s=(+1,+1,+1)\). Unit 1 is updated. What is the change in energy?

Compute \(h_1=W_{12}s_2+W_{13}s_3\), decide whether unit 1 flips, and use \(\Delta E=-\Delta\,h_1\).
\(h_1=1-2=-1\), so unit 1 flips to \(-1\) and \(\Delta=-2\); then \(\Delta E=-(-2)(-1)=-2\). Directly: \(E\) goes from \(-(1-2+1)=0\) to \(-(-1+2+1)=-2\).

A Hopfield network stores given patterns but learns no distribution. The Boltzmann machine (Ackley, Hinton and Sejnowski, 1985) does: its stochastic units sample states with Boltzmann probabilities, and hidden units let the energy capture dependencies the visible units alone cannot.

definition 14.4 — Boltzmann machine and restricted Boltzmann machine

A Boltzmann machine on binary units \(s=(v,h)\), split into visible units \(v\) and hidden units \(h\), assigns

$$p(s)=\frac{e^{-E(s)}}{Z},\qquad E(s)=-\tfrac12s^\top Ws-b^\top s,\qquad Z=\sum_se^{-E(s)},$$

and models the data by the marginal \(p(v)=\sum_hp(v,h)\).

A restricted Boltzmann machine (RBM) connects only visible to hidden units, with \(v,h\in\{0,1\}\) and

$$E(v,h)=-v^\top Wh-a^\top v-b^\top h.$$

The hidden units are then conditionally independent given \(v\), and vice versa:

$$P(h_j=1\mid v)=\sigma\Big(b_j+\sum_iW_{ij}v_i\Big),\qquad P(v_i=1\mid h)=\sigma\Big(a_i+\sum_jW_{ij}h_j\Big).$$
proposition 14.4 — the Boltzmann learning rule

For a Boltzmann machine as in Definition 14.4, the gradient of the log-likelihood of one visible vector is

$$\frac{\partial\log p(v)}{\partial W_{ij}}=\langle s_is_j\rangle_{\text{data}}-\langle s_is_j\rangle_{\text{model}},$$

where

For the RBM, \(s_is_j\) is \(v_ih_j\).

Write

$$\log p(v)=\log\sum_he^{-E(v,h)}-\log Z.$$

Since \(\partial(-E)/\partial W_{ij}=s_is_j\) (for \(i\ne j\), counting the symmetric pair once),

$$\frac{\partial}{\partial W_{ij}}\log\sum_he^{-E(v,h)}=\frac{\sum_hs_is_je^{-E(v,h)}}{\sum_he^{-E(v,h)}}=\sum_hp(h\mid v)\,s_is_j.$$

In the same way,

$$\frac{\partial\log Z}{\partial W_{ij}}=\sum_sp(s)\,s_is_j.\qquad\square$$

The rule is local: strengthen connections between units on together when the network sees data ("wake"), weaken those on together when it dreams freely ("sleep"); learning stops when dreams match the data's statistics. The model term needs samples, in general from a Markov chain run to equilibrium. Gibbs sampling resamples units from their conditional probabilities, a whole RBM layer at once. Contrastive divergence (Hinton, 2002) starts the chain at the data and runs only one or a few steps: enough to see which way the model drifts. The persistent variant (Tieleman, 2008), used by scikit-learn, keeps its chains between updates.

code — a restricted Boltzmann machine on Fashion-MNIST
# A restricted Boltzmann machine on Fashion-MNIST, trained by contrastive divergence without labels
from sklearn.neural_network import BernoulliRBM
from sklearn.linear_model import LogisticRegression
import time
t0 = time.time()
rbm = BernoulliRBM(n_components=256, learning_rate=0.02, batch_size=50, n_iter=15, random_state=0)
rbm.fit(Xtr[:20000])                                        # 20,000 images, no labels
print(f"RBM with 256 hidden units trained on 20,000 unlabelled images in {time.time() - t0:.0f} s; "
      f"pseudo-likelihood per image {rbm.score_samples(Xte[:2000]).mean():.1f}")
Htr, Hte = rbm.transform(Xtr), rbm.transform(Xte)           # P(h_j = 1 | v): 256 features per image
lab = np.concatenate([np.flatnonzero(ytr == c)[:100] for c in range(10)])   # 100 labels per class
for feats, (A, B) in [('raw pixels (784)', (Xtr, Xte)), ('RBM hidden units (256)', (Htr, Hte))]:
    for name, ix in [('1,000 labels', lab), ('60,000 labels', np.arange(60000))]:
        clf = LogisticRegression(max_iter=2000, C=1.0).fit(A[ix], ytr[ix])
        print(f"  linear probe on {feats:24s} with {name:13s}: test accuracy {clf.score(B, yte):.3f}")
RBM with 256 hidden units trained on 20,000 unlabelled images in 14 s; pseudo-likelihood per image -210.7
  linear probe on raw pixels (784)         with 1,000 labels : test accuracy 0.789
  linear probe on raw pixels (784)         with 60,000 labels: test accuracy 0.843
  linear probe on RBM hidden units (256)   with 1,000 labels : test accuracy 0.796
  linear probe on RBM hidden units (256)   with 60,000 labels: test accuracy 0.849

The features barely help. A linear classifier on the 256 hidden-unit probabilities scores 0.796 with 1,000 labels and 0.849 with all 60,000, against 0.789 and 0.843 on raw pixels. In 2006 stacks of RBMs first made deep networks trainable (Hinton, Osindero and Teh, 2006), starting the deep-learning revival; better initialisation, ReLUs and normalisation (Lectures 10 and 11) soon made such pretraining unnecessary, and contrastive methods replaced it for learning without labels.

quantum — Boltzmann machines are Ising models

With spins \(s_i=\pm1\), couplings \(J_{ij}=W_{ij}\) and fields \(b_i\), the Boltzmann energy is an Ising model of a magnet; a Hopfield network is one at zero temperature, and its capacity analysis came from spin-glass theory. A quantum annealer (such as D-Wave's) encodes an Ising energy in superconducting qubits, adds a transverse field that lets the state tunnel, and slowly removes it. Its imperfect, low-energy readouts have served as approximate Boltzmann samples for the "model" term of Proposition 14.4 (Adachi and Henderson, 2015); a quantum Boltzmann machine puts the transverse field in the model (Amin et al., 2018). The samples' effective temperature is hard to control, and no training advantage over good classical samplers has been demonstrated.

history — from Hebb to the 2024 Nobel Prize

Donald Hebb proposed in The Organization of Behavior (1949) that a connection between two neurons strengthens when they fire together. Shun-ichi Amari (1972), William Little (1974) and others built associative memories on the idea, but John Hopfield's "Neural networks and physical systems with emergent collective computational abilities" (PNAS, 1982) made the energy function central and brought physicists in. Geoffrey Hinton and Terrence Sejnowski, with David Ackley, made it the stochastic Boltzmann machine (1983–85); Paul Smolensky's "harmonium" (1986) was the restricted version; contrastive divergence (2002) and deep belief networks (2006) made it trainable and deep. In October 2024 Hopfield and Hinton received the Nobel Prize in Physics "for foundational discoveries and inventions that enable machine learning with artificial neural networks".

The energy view lives on. "Modern" Hopfield networks with a softmax energy store exponentially many patterns, and their one-step update is the attention of Lecture 12 (Ramsauer et al., 2021). Diffusion models learn the "score" \(\nabla_x\log p(x)=-\nabla_xE(x)\), which avoids \(Z\) altogether.

6 — Self-supervised learning: inventing labels from the data

Modelling the whole input distribution, as the Boltzmann machine does, is expensive and not obviously useful. Since about 2018 a different idea has taken over: hide part of an example and predict it from the rest, so that training examples are as plentiful as raw data. This pretext task matters only for what the network must learn to solve it. Two main kinds:

definition 14.5 — the InfoNCE loss

Let \(f(x,y)\) be a score ("critic") for how well \(y\) matches \(x\). Given \(x\), draw

The InfoNCE loss is the cross-entropy of picking out the positive among the \(K\) candidates:

$$\mathcal L_{\text{InfoNCE}}=-\,\mathbb E\left[\log\frac{e^{f(x,y^+)}}{\sum_{j=1}^Ke^{f(x,y_j)}}\right].$$

In SimCLR (Chen et al., 2020):

The loss averaged over all \(2B\) anchors is called NT-Xent.

The augmentations declare what should not matter, as you recognise a friend in a cropped, darker photo; \(\tau\) sets how sharply near-misses are separated from clear mismatches. After training, the projection head is discarded and the encoder is tested by a linear probe: a linear classifier trained with a few labels on its frozen outputs. Our version fits one CPU core: a two-layer convolutional network with 128-dimensional output; views by shifting, flipping, erasing a square patch, changing brightness and adding noise; batches of 256 and 1,500 steps, about six passes over the 60,000 unlabelled training images.

code — SimCLR in miniature (JAX)
# SimCLR in miniature: contrastive pretraining of a small CNN on unlabelled Fashion-MNIST (JAX, CPU)
import jax, jax.numpy as jnp, time
STEPS = 1500 if 'STEPS' not in globals() else STEPS
def init(key):
    k = jax.random.split(key, 5); he = lambda k, s, fan: jax.random.normal(k, s) * jnp.sqrt(2 / fan)
    return {'c1': he(k[0], (3, 3, 1, 32), 9), 'b1': jnp.zeros(32), 'c2': he(k[1], (3, 3, 32, 64), 288),
            'b2': jnp.zeros(64), 'd': he(k[2], (3136, 128), 3136), 'bd': jnp.zeros(128),        # encoder f
            'p1': he(k[3], (128, 128), 128), 'p2': he(k[4], (128, 64), 128)}                  # projection head g
def encode(p, x):                                            # x: (B, 28, 28) -> representation (B, 128)
    conv = lambda x, w: jax.lax.conv_general_dilated(x, w, (2, 2), 'SAME', dimension_numbers=('NHWC', 'HWIO', 'NHWC'))
    h = jax.nn.relu(conv(x[..., None], p['c1']) + p['b1'])
    h = jax.nn.relu(conv(h, p['c2']) + p['b2'])
    return jax.nn.relu(h.reshape(len(x), -1) @ p['d'] + p['bd'])
def augment(key, x):                                         # one random view of one image
    k1, k2, k3, k4, k5 = jax.random.split(key, 5)
    pad = jnp.pad(x, 4); i, j = jax.random.randint(k1, (2,), 0, 9)
    x = jax.lax.dynamic_slice(pad, (i, j), (28, 28))                     # random shift by up to 4 pixels
    x = jnp.where(jax.random.bernoulli(k2), x[:, ::-1], x)               # horizontal flip
    ci, cj = jax.random.randint(k3, (2,), 0, 28); r, c = jnp.arange(28)[:, None], jnp.arange(28)[None, :]
    x = jnp.where((jnp.abs(r - ci) < 6) & (jnp.abs(c - cj) < 6), 0.0, x) # erase a 11x11 patch
    x = x * jax.random.uniform(k4, minval=0.6, maxval=1.4)               # brightness
    return x + 0.1 * jax.random.normal(k5, x.shape)                      # noise
aug = jax.vmap(augment)
def nt_xent(p, key, x, tau=0.2):                             # the InfoNCE loss of Definition 14.5, both directions
    ka, kb = jax.random.split(key); B = len(x)
    z = jnp.concatenate([aug(jax.random.split(ka, B), x), aug(jax.random.split(kb, B), x)])
    z = jax.nn.relu(encode(p, z) @ p['p1']) @ p['p2']
    z = z / jnp.linalg.norm(z, axis=1, keepdims=True)
    S = z @ z.T / tau - 1e9 * jnp.eye(2 * B)                 # cosine similarities; a view is not its own negative
    pos = jnp.concatenate([jnp.arange(B, 2 * B), jnp.arange(B)])
    return jnp.mean(jax.nn.logsumexp(S, axis=1) - S[jnp.arange(2 * B), pos])
@jax.jit
def step(p, m, v, t, key, x, lr=1e-3):                       # Adam (Lecture 2)
    L, g = jax.value_and_grad(nt_xent)(p, key, x)
    m = jax.tree.map(lambda m, g: 0.9 * m + 0.1 * g, m, g); v = jax.tree.map(lambda v, g: 0.999 * v + 0.001 * g * g, v, g)
    p = jax.tree.map(lambda p, m, v: p - lr * (m / (1 - 0.9**t)) / (jnp.sqrt(v / (1 - 0.999**t)) + 1e-8), p, m, v)
    return p, m, v, L
key = jax.random.PRNGKey(0); p0 = init(key); p = p0
m = jax.tree.map(jnp.zeros_like, p); v = jax.tree.map(jnp.zeros_like, p)
Ximg = jnp.asarray(Xtr.reshape(-1, 28, 28)); t0 = time.time(); B = 256; losses = []
for t in range(1, STEPS + 1):
    key, k1, k2 = jax.random.split(key, 3)
    p, m, v, L = step(p, m, v, t, k1, Ximg[jax.random.randint(k2, (B,), 0, 60000)])
    losses.append(float(L))
    if t in (1, 100, 500, 1000, STEPS):
        print(f"step {t:5d}  contrastive loss {np.mean(losses[-50:]):.3f}  (chance level log(2B-1) = {np.log(2 * B - 1):.3f})")
print(f"pretraining: {STEPS} steps of {B} images (no labels) in {time.time() - t0:.0f} s")
step     1  contrastive loss 6.188  (chance level log(2B-1) = 6.236)
step   100  contrastive loss 4.460  (chance level log(2B-1) = 6.236)
step   500  contrastive loss 3.387  (chance level log(2B-1) = 6.236)
step  1000  contrastive loss 3.107  (chance level log(2B-1) = 6.236)
step  1500  contrastive loss 2.975  (chance level log(2B-1) = 6.236)
pretraining: 1500 steps of 256 images (no labels) in 159 s

The loss falls from the chance level \(\log(2B-1)=6.236\) (a view's partner indistinguishable from 510 strangers) to 2.975, a partner probability of about \(e^{-2.975}\approx0.051\) among 511 candidates. Next, linear probes on this encoder, on an untrained network of the same shape (a strong baseline) and on raw pixels, against the same network trained end to end on the labels.

code — linear probes and the supervised alternative
# Linear probes: how good are the learned features, and how many labels do they save?
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
feat = jax.jit(encode)
def features(p, X): return np.concatenate([np.asarray(feat(p, jnp.asarray(X[i:i + 2000].reshape(-1, 28, 28))))
                                           for i in range(0, len(X), 2000)])
def probe(Ftr, Fte, ix):
    sc = StandardScaler().fit(Ftr[ix]); clf = LogisticRegression(max_iter=3000, C=0.5)
    return clf.fit(sc.transform(Ftr[ix]), ytr[ix]).score(sc.transform(Fte), yte)
F = {'random CNN (no training)': (features(p0, Xtr), features(p0, Xte)),
     'contrastive CNN (SimCLR)': (features(p, Xtr), features(p, Xte))}
lab10 = np.concatenate([np.flatnonzero(ytr == c)[:10] for c in range(10)])
for name, (A, Bt) in F.items():
    accs = [probe(A, Bt, ix) for ix in (lab10, lab, np.arange(60000))]
    knn = KNeighborsClassifier(10, metric='cosine').fit(A[lab], ytr[lab]).score(Bt, yte)
    print(f"{name:26s} probe with 100 / 1,000 / 60,000 labels: {accs[0]:.3f} / {accs[1]:.3f} / {accs[2]:.3f};"
          f"  10-NN with 1,000: {knn:.3f}")
# the supervised alternative: the same CNN trained end to end on the labels alone, with the usual light
# augmentation (shifts of up to 2 pixels and flips); the strong SimCLR views hurt supervised training here
def light(key, x):
    k1, k2 = jax.random.split(key); i, j = jax.random.randint(k1, (2,), 0, 5)
    x = jax.lax.dynamic_slice(jnp.pad(x, 2), (i, j), (28, 28))
    return jnp.where(jax.random.bernoulli(k2), x[:, ::-1], x)
def sup_loss(q, key, x, y):
    o = encode(q, jax.vmap(light)(jax.random.split(key, len(x)), x)) @ q['W'] + q['bW']
    return jnp.mean(jax.nn.logsumexp(o, 1) - o[jnp.arange(len(x)), y])
@jax.jit
def sstep(q, m, v, t, key, x, y, lr=1e-3):
    L, g = jax.value_and_grad(sup_loss)(q, key, x, y)
    m = jax.tree.map(lambda m, g: 0.9 * m + 0.1 * g, m, g); v = jax.tree.map(lambda v, g: 0.999 * v + 0.001 * g * g, v, g)
    return jax.tree.map(lambda p, m, v: p - lr * (m / (1 - 0.9**t)) / (jnp.sqrt(v / (1 - 0.999**t)) + 1e-8), q, m, v), m, v, L
for nl in [1000, 3000, 10000]:
    ix = np.concatenate([np.flatnonzero(ytr == c)[:nl // 10] for c in range(10)])
    q = dict(init(jax.random.PRNGKey(1)), W=jnp.zeros((128, 10)), bW=jnp.zeros(10)); m = jax.tree.map(jnp.zeros_like, q); v = jax.tree.map(jnp.zeros_like, q)
    kk = jax.random.PRNGKey(2); Xl, yl = Ximg[ix], jnp.asarray(ytr[ix])
    for t in range(1, 1001):
        kk, k1, k2 = jax.random.split(kk, 3); b = jax.random.randint(k2, (128,), 0, len(ix))
        q, m, v, L = sstep(q, m, v, t, k1, Xl[b], yl[b])
    acc = np.mean(np.concatenate([np.asarray((feat(q, jnp.asarray(Xte[i:i + 2000].reshape(-1, 28, 28))) @ q['W'] + q['bW']).argmax(1))
                                  for i in range(0, 10000, 2000)]) == yte)
    print(f"supervised CNN trained end to end on {nl:6,d} labels (1,000 steps): test accuracy {acc:.3f}")
random CNN (no training)   probe with 100 / 1,000 / 60,000 labels: 0.655 / 0.732 / 0.809;  10-NN with 1,000: 0.700
contrastive CNN (SimCLR)   probe with 100 / 1,000 / 60,000 labels: 0.678 / 0.772 / 0.831;  10-NN with 1,000: 0.743
supervised CNN trained end to end on  1,000 labels (1,000 steps): test accuracy 0.830
supervised CNN trained end to end on  3,000 labels (1,000 steps): test accuracy 0.857
supervised CNN trained end to end on 10,000 labels (1,000 steps): test accuracy 0.864
random CNN (no training)contrastive CNN (SimCLR)T-shirttrouserpulloverdresscoatsandalshirtsneakerbagboot
The first two principal components of the 128-dimensional representations of 2,000 test images, coloured by their true class (which neither network saw). Left: the untrained network, whose random convolutional features already separate footwear from trousers. Right: after contrastive pretraining, trousers and sandals form tighter groups, but T-shirts, pullovers, coats and shirts remain mixed in both pictures.

Pretraining beats no training at every label budget (0.772 against 0.732 with 1,000 labels), and 10-nearest-neighbour accuracy rises from 0.700 to 0.743. But raw pixels do better with the same 1,000 labels (0.789), and the network trained end to end on them reaches 0.830 (0.857 with 3,000): at this scale pretraining saves no labels. Chen et al. used a ResNet-50, batches of 4,096 and hundreds of passes over ImageNet; our network has two convolutional layers and saw each image about six times. The pretext task was learned, but its features only partly separate a shirt from a pullover, and Fashion-MNIST leaves little for pretraining to add. Self-supervision pays where unlabelled data are vast and labels expensive (Project 2).

The mutual information \(I(X;Y)\) measures how much knowing one quantity reduces uncertainty about the other (zero if independent), here in nats (one nat is about 1.44 bits).

theorem 14.5 — InfoNCE bounds the mutual information

For any critic \(f\) and \(K\) candidates drawn as in Definition 14.5,

$$I(X;Y)\;\ge\;\log K-\mathcal L_{\text{InfoNCE}}.$$

The bound is tightest for the critic

$$f(x,y)=\log\frac{p(y\mid x)}{p(y)}+c(x),$$

and even then it can never exceed \(\log K\).

(Statement; proofs in van den Oord, Li and Vinyals, 2018, and Poole et al., 2019.)

Minimising the contrastive loss thus maximises a lower bound on the views' mutual information. The \(\log K\) ceiling holds because a \(K\)-way cross-entropy is non-negative (Exercise 5): a \(K\)-option test can certify at most \(\log K\). The code checks both halves on correlated Gaussians, where the mutual information and best critic are known.

code — the InfoNCE bound for correlated Gaussians
# Theorem 14.5 numerically: InfoNCE never exceeds the mutual information, nor log K
rng = np.random.default_rng(3); d, rho = 10, 0.8
I_true = -0.5 * d * np.log(1 - rho**2)                         # exact mutual information (nats)
def f_opt(u, w):        # best possible critic: log p(y|x)/p(y) for the Gaussian pair, up to a constant
    return (-((w[None, :, :] - rho * u[:, None, :])**2).sum(-1) / (2 * (1 - rho**2))
            + (w[None, :, :]**2).sum(-1) / 2)
print(f"d = {d}, correlation {rho}: true I(X;Y) = {I_true:.3f} nats")
for K in [2, 8, 64, 512, 4096]:
    est = []
    for _ in range(max(1, 20000 // K)):
        u = rng.standard_normal((K, d)); w = rho * u + np.sqrt(1 - rho**2) * rng.standard_normal((K, d))
        S = f_opt(u, w)                                         # S[i, j] = f(u_i, w_j); diagonal = positive pairs
        est.append(np.mean(np.diag(S) - (np.log(np.mean(np.exp(S - S.max(1, keepdims=True)), 1)) + S.max(1))))
    print(f"  K = {K:5d}: InfoNCE estimate {np.mean(est):.3f}   log K = {np.log(K):.3f}")
d = 10, correlation 0.8: true I(X;Y) = 5.108 nats
  K =     2: InfoNCE estimate 0.675   log K = 0.693
  K =     8: InfoNCE estimate 1.967   log K = 2.079
  K =    64: InfoNCE estimate 3.552   log K = 4.159
  K =   512: InfoNCE estimate 4.543   log K = 6.238
  K =  4096: InfoNCE estimate 4.941   log K = 8.318

Even with the best critic, the estimate stays below the true 5.108 nats and below \(\log K\); with 2 or 8 candidates it is pinned near \(\log K\), and only with 4,096 does it come within 0.17 nats. Hence the many negatives: SimCLR's batches of thousands, MoCo's queue of past examples (He et al., 2020). Yet mutual information is not the whole story: encoders with higher estimates can give worse features (Tschannen et al., 2020). What the augmentations make the network ignore matters at least as much as what it keeps.

spot check 14.6

A contrastive model is trained with \(K=256\) candidates per anchor and reaches a loss of essentially 0. What is the largest mutual information, in nats, that Theorem 14.5 lets you certify?

The bound is \(\log K-\mathcal L\), with the natural logarithm.
\(\log256=5.545\) nats (8 bits). However large the true mutual information, a perfect 256-way classifier cannot show more; the bound saturates.
big picture — every foundation model is pretrained without labels

The large models of 2026 all begin with self-supervision at enormous scale. Language models (the GPT, Claude, Gemini, Llama and DeepSeek families) are pretrained on next-token prediction over trillions of tokens, then fine-tuned on human examples and preferences (Lecture 22). Vision models use masking (MAE) or self-distillation between views (DINOv2, 142 million curated images, no labels). CLIP trains image and text encoders with the InfoNCE loss on web image–caption pairs; such encoders steer most text-to-image generators. Speech (wav2vec 2.0), proteins (ESM) and single-cell "foundation models" mask or contrast in the same way. The reason is largely economic: labels are scarce, raw data abundant, and one encoder adapts to many tasks.

7 — Evaluating without ground truth

Without labels there is no error to measure, yet every unsupervised method returns something: a density, anomalies, features, a clustering (Lecture 15). Five tools help decide whether it is real:

code — agreement, stability and label-free diagnostics
# Checking unsupervised results without labels: agreement, stability, and label-free embedding diagnostics
top10 = {k: set(pd.Series(v, index=prof.index).nlargest(10).index) for k, v in scores.items()}
ks = list(top10); J = lambda a, b: len(a & b) / len(a | b)
for i in range(4):
    print(f"{ks[i]:26s}" + "".join(f"{J(top10[ks[i]], top10[ks[j]]):6.2f}" for j in range(4)))
seed_tops = [set(pd.Series(-IsolationForest(n_estimators=n, random_state=s).fit(Xd).score_samples(Xd),
                           index=prof.index).nlargest(10).index) for n in (50, 500) for s in range(10)]
for n, tops in [(50, seed_tops[:10]), (500, seed_tops[10:])]:
    print(f"isolation forest, {n:3d} trees, 10 seeds: mean pairwise Jaccard of top-10 days "
          f"{np.mean([J(a, b) for i, a in enumerate(tops) for b in tops[i + 1:]]):.2f}")
def align_unif(q, X, key):      # Wang & Isola (2020): alignment of positive pairs, uniformity on the sphere
    x = jnp.asarray(X[:2000].reshape(-1, 28, 28)); ka, kb = jax.random.split(key)
    za, zb = (encode(q, aug(jax.random.split(k, 2000), x)) for k in (ka, kb))
    za, zb = (z / jnp.linalg.norm(z, axis=1, keepdims=True) for z in (za, zb))
    sq = (2 - 2 * za @ za.T)[np.triu_indices(2000, 1)]        # squared distances of unit vectors
    return float(jnp.mean(jnp.sum((za - zb) ** 2, 1))), float(jnp.log(jnp.mean(jnp.exp(-2 * sq))))
for name, q in [('random CNN', p0), ('contrastive CNN', p)]:
    a, u = align_unif(q, Xte, jax.random.PRNGKey(5))
    print(f"{name:16s} alignment {a:.3f} (lower: views of one image agree)   uniformity {u:.3f} (lower: spread out)")
isolation forest            1.00  0.43  0.43  0.67
local outlier factor        0.43  1.00  0.43  0.33
distance to 5th neighbour   0.43  0.43  1.00  0.43
seasonal residual (c4)      0.67  0.33  0.43  1.00
isolation forest,  50 trees, 10 seeds: mean pairwise Jaccard of top-10 days 0.77
isolation forest, 500 trees, 10 seeds: mean pairwise Jaccard of top-10 days 0.87
random CNN       alignment 0.738 (lower: views of one image agree)   uniformity -1.545 (lower: spread out)
contrastive CNN  alignment 0.269 (lower: views of one image agree)   uniformity -1.148 (lower: spread out)

The detectors agree only in part: top-10 Jaccard overlaps (rows and columns in the same order) range from 0.33 (LOF against seasonal residual) to 0.67 (isolation forest against seasonal residual). All lists contain the blizzard, New Year's Day and Christmas; borderline days differ. Two isolation-forest runs with different seeds share a top-ten overlap of 0.77 on average with 50 trees and 0.87 with 500; the last places are not findings. For the encoders, contrastive training improves alignment (0.738 to 0.269) but worsens uniformity (-1.545 to -1.148). That label-free warning matches the weak probes: agreement between views was partly bought by squeezing different images together, a mild form of the collapse that large batches, many negatives and long training prevent.

idea — stability is necessary, not sufficient

A bug that ignores the data is perfectly stable and perfectly wrong: stability rules results out, never in. Methods sharing an assumption ("a day is a point in 48-dimensional space") can agree on the same mistake. The strongest evidence is a stable result, agreement between independent methods, and a check against information they did not use, itself examined for errors.

spot check 14.7

An analyst runs an isolation forest on a year of sensor data with 20 random seeds, and the same 12 readings top the list every time. What does this show?

What can repeated runs of one method rule out, and what can they not establish?
Stability rules out an accident of randomness, not a mismatch between "unusual" and "fault": the 12 readings might be a calibration change, a shutdown or a logging error, like the taxi data's clock change.

8 — Summary, exercises, projects, reading

summary
exercises
  1. Two data points lie at \(-1\) and \(+1\). Compute the Gaussian kernel density estimate at \(x=0\) and at \(x=1\), first with bandwidth \(h=1\) and then with \(h=0.5\). How many modes does each estimate have?

    With \(h=1\):

    $$\hat f(0)=\tfrac12\big(\varphi(1)+\varphi(1)\big)=\varphi(1)=0.242,\qquad \hat f(1)=\tfrac12\big(\varphi(0)+\varphi(2)\big)=0.227.$$

    The centre is higher than the data points: the two bumps, two standard deviations apart, merge into a single flat-topped mode at 0.

    With \(h=0.5\), \(\hat f(x)=\varphi\big(2(x+1)\big)+\varphi\big(2(x-1)\big)\), so

    $$\hat f(0)=2\varphi(2)=0.108,\qquad \hat f(1)=\varphi(4)+\varphi(0)=0.399:$$

    two modes, near \(\pm1\). The number of modes depends on the bandwidth as much as on the data, which is why the third Old Faithful mode needs care.

  2. For a normal density with standard deviation \(\sigma\) and a Gaussian kernel, show that the AMISE-optimal bandwidth of Theorem 14.1 is \(h^*=(4/3)^{1/5}\sigma n^{-1/5}\approx1.06\,\sigma n^{-1/5}\). You may use \(R(f'')=\int f''(x)^2dx=3/(8\sqrt\pi\,\sigma^5)\).

    For the Gaussian kernel \(\mu_2=1\) and \(R(K)=\int\varphi^2=1/(2\sqrt\pi)\). Then

    $$h^*=\left(\frac{1/(2\sqrt\pi)}{3n/(8\sqrt\pi\sigma^5)}\right)^{1/5}=\left(\frac{4\sigma^5}{3n}\right)^{1/5}=\left(\tfrac43\right)^{1/5}\sigma n^{-1/5},$$

    and \((4/3)^{1/5}=1.059\). Silverman's 0.9 instead of 1.06, with the interquartile range, is a deliberate undersmoothing that copes better with skewed and bimodal densities.

  3. What fraction of the cube \([-1,1]^{10}\) lies inside its inscribed unit ball? (The volume of the unit ball in \(\mathbb R^{10}\) is \(\pi^5/5!\).) What does this say about sampling a ball by rejection from a cube in high dimensions?
    $$\frac{\pi^5/120}{2^{10}}=\frac{2.550}{1024}=0.00249.$$

    Only one sample in about 400 would be accepted in ten dimensions, and the ratio keeps falling faster than exponentially. The volume of a cube sits in its corners, at distance up to \(\sqrt d\) from the centre, while the ball reaches only 1.

  4. A Hopfield network of two units has \(W_{12}=W_{21}=-1\) and starts in \(s=(+1,+1)\). Show that if both units update simultaneously the network oscillates for ever, but under asynchronous updates it stops after one flip. Which assumption of Theorem 14.3 does the synchronous rule violate?

    Synchronously: each unit sees field \(-1\cdot(+1)=-1\), so both flip to \((-1,-1)\); there each sees \(+1\), and both flip back. The energy \(-W_{12}s_1s_2=s_1s_2\) is \(+1\) in both states, so it does not decrease.

    Asynchronously: updating unit 1 gives \((-1,+1)\) with energy \(-1\); unit 2 then sees field \(+1\) and stays, and unit 1 sees \(-1\) and stays: a fixed point.

    The proof of Theorem 14.3 computes \(\Delta E\) for a change in one unit with the others fixed; when two units change together, the cross term \(-W_{12}\Delta_1\Delta_2\) is not controlled.

  5. Show that \(\log K-\mathcal L_{\text{InfoNCE}}\le\log K\) for any critic, so InfoNCE can never certify more than \(\log K\) nats of mutual information, and that a critic which ignores its input (a constant \(f\)) gives exactly zero. Why does SimCLR use large batches?

    Each term of the loss is

    $$-\log\frac{e^{f(x,y^+)}}{\sum_je^{f(x,y_j)}},$$

    minus the log of a probability, so it is at least 0; hence \(\log K-\mathcal L\le\log K\).

    A constant critic gives every candidate probability \(1/K\), so \(\mathcal L=\log K\) and the bound is 0.

    Once the positive is picked out with near certainty, there is nothing more to gain. Larger batches give more negatives, a harder task and a higher ceiling, which is one reason SimCLR used batches of several thousand (and MoCo a queue of negatives).

  6. (Code.) Change the seasonal baseline in the first anomaly code box from the median to the mean of each half-hour of the week, and rerun it. Which days move, and why does the choice matter most for the weeks that contain the anomalies?

    The mean is pulled towards the anomalies themselves. Each half-hour of the week has only about 30 values, so one blizzard night noticeably lowers the mean baseline for that Monday–Tuesday slot, and the blizzard's own residual shrinks. Holidays on the same weekday (Christmas and New Year's Day were both Thursdays in this period) pull down each other's baselines.

    The median ignores a few extreme values, so it keeps the baseline at "normal" demand. The general rule: the model of normal must be fitted robustly, because the training data contain the anomalies.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Anomalies in New York subway ridership

question
Which hours and days of unusual subway ridership do unsupervised detectors find, and how many of them match known events (storms, outages, parades, holidays, major games)?
data
MTA Subway Hourly Ridership (New York State open data portal, data.ny.gov), by station complex, from 2020; NOAA daily weather for Central Park; an event timeline built by the students from MTA service alerts, NYC Emergency Management notices and the city's event permits.
method
A robust seasonal baseline per station, isolation forests and LOF on daily station profiles, as in Section 4; precision and recall against the event timeline, with careful treatment of holidays and clock changes; spatial patterns (which stations react to which events).
outcome
A labelled benchmark of ridership anomalies for the largest transit system in the United States, with an honest comparison of detectors, and a list of detections that the timeline does not explain.

2. How many labels does contrastive pretraining save?

question
On a small image set from a specialised domain, how many labelled examples does a supervised network need to match a linear probe on a contrastively pretrained encoder?
data
A domain set with few labels, such as research-grade iNaturalist observations from New York City parks (photographs licensed for reuse, labelled by species) or a public medical image collection from MedMNIST.
method
SimCLR as in Section 6, with augmentations chosen for the domain; linear probes and supervised baselines at 1, 3, 10, 30 and 100% of the labels; repeated over seeds with confidence intervals; an ablation of each augmentation.
outcome
A "label-efficiency curve" for the domain and a statement such as "pretraining is worth \(m\) labels per class", with an analysis of which augmentations matter there.

3. Where does New York complain about noise?

question
Where and when are noise complaints concentrated, and how much do the "hot spots" depend on the bandwidth used to find them?
data
NYC 311 Service Requests (NYC Open Data), complaint types beginning "Noise", with coordinates and timestamps; census-tract population from the American Community Survey for normalisation.
method
Two-dimensional kernel density estimation with bandwidths chosen by rule of thumb and by likelihood cross-validation, separately by hour and season; densities per resident versus per square kilometre; stability of the top hot spots across bandwidths and years.
outcome
Maps of complaint density with an honest account of how much each conclusion depends on the bandwidth, and a comparison of complaint density with population, which separates noisy places from places where people complain.

Reading and sources

Data. Old Faithful: R datasets::faithful (Härdle, 1991; Azzalini and Bowman, 1990), copy from github.com/vincentarelbundock/Rdatasets. NYC taxi passengers and anomaly windows: Numenta Anomaly Benchmark, github.com/numenta/NAB (AGPL-3.0), derived from NYC Taxi and Limousine Commission trip records. Fashion-MNIST: H. Xiao, K. Rasul, R. Vollgraf (2017), github.com/zalandoresearch/fashion-mnist (MIT licence). All three were downloaded directly from GitHub; no substitutes were needed.

numbers in the text not printed by a code box are computed in verify_L14.py, figures and widget data in figs_L14.py; code-box outputs are pasted from actual runs (numpy, scikit-learn and JAX on one CPU core)