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)
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.
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.
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).
A city has five years of hourly electricity demand for each of 2,000 buildings and no other information. Which question is unsupervised?
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.
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.
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.
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.
# 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 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.
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.
# 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)
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.
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?
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.
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.
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:
(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.
# 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.
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.
What fraction of the volume of a 100-dimensional ball lies within 1% of its radius from the surface?
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.
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.
# 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
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".
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.
# 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.
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\)?
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.
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?
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).
# 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 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?
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.
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).$$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.
# 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.
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.
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.
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:
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.
# 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.
# 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
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).
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.
# 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.
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 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.
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:
# 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.
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.
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?
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.
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.
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.
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.
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).
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.
Each project uses this lecture's methods and public data, and has a clear result.
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)