Machine Learning · Lecture 17a

Lecture 17a
Mixture Models and EM

Part IV · Unsupervised learning  |  Gaussian mixtures and soft assignments, the EM algorithm and k-means as hard EM, why EM works, BIC and label switching, Dirichlet processes and the Chinese restaurant, hidden Markov models, topic models, variational inference  |  reading: Dempster, Laird & Rubin (1977); Bishop, Pattern Recognition and Machine Learning (2006), ch. 9 and 13; Blei, Ng & Jordan (2003); Blei, Kucukelbir & McAuliffe (2017)  |  copulas follow in Lecture 17b

Cartoon: the chicken and the eggA stick figure stands between two signposts. One says: if I knew which group each point came from, I could estimate the groups. The other says: if I knew the groups, I could tell which group each point came from. The figure says: then I'll guess one and alternate. Knew the groups? I'dknow who's in which. Knew who's in which?I'd know the groups. guess, then alternate
EM breaks the circle by alternating: guess the parameters, infer the hidden labels, re-estimate the parameters, repeat
In this lecture
  1. Gaussian mixtures
  2. The EM algorithm
  3. Why EM works
  4. How many components? BIC and label switching
  5. Bayesian mixtures and the Dirichlet process
  6. Mixtures in time: hidden Markov models
  7. Mixtures of words: topic models
  8. Variational inference, and the VAE revisited
  9. Summary, exercises, projects, reading

Lecture 15 grouped points by geometry; Lecture 16 found low-dimensional shapes. A mixture model unites both: each point comes from one of several unobserved sub-populations, each with a simple distribution. It is fitted by the expectation–maximisation (EM) algorithm, justified by the evidence lower bound of the variational autoencoder (Lecture 16b). Linking the labels through time gives hidden Markov models; words as data, topic models; unboundedly many components, Dirichlet-process mixtures.

Goals: fit a mixture by EM and prove it never decreases the likelihood; see k-means as a limit of EM; use BIC and understand label switching; count tables in the Chinese restaurant; derive the forward and Viterbi algorithms; describe LDA; relate EM, Bayesian mixtures and the VAE through variational inference.

1 — Gaussian mixtures

The Old Faithful eruptions of Lectures 14 and 16a fall into two groups, short eruptions after short waits and long after long: plausibly two kinds of eruption, each with its own two-dimensional normal. Think of a bag of mixed sweets with the brand labels lost: the weights \(\pi_k\) are the brands' shares, and each component \(N(\mu_k,\Sigma_k)\) is one brand, with mean \(\mu_k\) and covariance \(\Sigma_k\) (drawn as an ellipse).

definition 17.1 — Gaussian mixture model

A Gaussian mixture with \(K\) components has

Each observation is generated in two stages:

$$P(z_i=k)=\pi_k,\qquad x_i\mid z_i=k\;\sim\;N(\mu_k,\Sigma_k),$$

where the label \(z_i\in\{1,\dots,K\}\) is hidden. The density of \(x\) is

$$p(x)=\sum_{k=1}^K\pi_k\,N(x;\mu_k,\Sigma_k).$$

The responsibility of component \(k\) for \(x_i\) is its posterior probability:

$$r_{ik}=P(z_i=k\mid x_i)=\frac{\pi_kN(x_i;\mu_k,\Sigma_k)}{\sum_j\pi_jN(x_i;\mu_j,\Sigma_j)}.$$

Unlike k-means, a mixture assigns points softly, gives each component its own shape and size, and provides a density (useful for anomaly detection, Lecture 14). Its log-likelihood is a log of a sum,

$$\sum_i\log\sum_k\pi_kN(x_i;\mu_k,\Sigma_k),$$

with no closed-form maximiser. The difficulty is circular: known labels would make the components easy to estimate, and known components would give the labels. EM guesses one and alternates.

2 — The EM algorithm

definition 17.2 — the EM algorithm for a Gaussian mixture

Start from initial parameters and repeat until the log-likelihood stops increasing:

$$\pi_k=\frac{N_k}{n},\qquad\mu_k=\frac1{N_k}\sum_ir_{ik}x_i,\qquad\Sigma_k=\frac1{N_k}\sum_ir_{ik}(x_i-\mu_k)(x_i-\mu_k)^\top.$$

In general, for observed \(x\), hidden \(z\) and parameters \(\theta\):

$$\text{E-step: }q(z)=p(z\mid x,\theta_{\text{old}}),\qquad\text{M-step: }\theta=\arg\max_\theta\,\mathbb E_q[\log p(x,z\mid\theta)].$$
idea — the two steps in words

Each point is split among the components in proportion to its responsibilities: a point that is 70% "short eruption" contributes 0.7 of itself to the short component's average and 0.3 to the long one's.

code — EM by hand on Old Faithful, and scikit-learn
# EM for a two-component Gaussian mixture on Old Faithful, written by hand
import numpy as np, pandas as pd
from scipy.stats import multivariate_normal as mvn
of = pd.read_csv('data/faithful.csv'); X = of[['eruptions', 'waiting']].to_numpy(); n = len(X)
def loglik(X, w, mu, S):
    dens = np.column_stack([w[k] * mvn.pdf(X, mu[k], S[k]) for k in range(len(w))])
    return np.log(dens.sum(1)).sum(), dens
w, mu, S = np.array([.5, .5]), np.array([[2.0, 80.0], [4.0, 55.0]]), np.array([np.cov(X.T)] * 2)   # a poor start
trace = []
for it in range(100):
    ll, dens = loglik(X, w, mu, S); trace.append(ll)
    R = dens / dens.sum(1, keepdims=True)                   # E-step: responsibilities r_ik = P(z_i = k | x_i)
    Nk = R.sum(0); w = Nk / n                               # M-step: weighted proportions, means, covariances
    mu = (R.T @ X) / Nk[:, None]
    S = np.array([((X - mu[k]).T * R[:, k]) @ (X - mu[k]) / Nk[k] for k in range(2)])
    if it > 0 and trace[-1] - trace[-2] < 1e-8: break
assert np.all(np.diff(trace) >= -1e-9)                      # Theorem 17.2: the log-likelihood never decreases
print(f"EM converged in {len(trace)} iterations; log-likelihood {trace[0]:.2f} -> {trace[-1]:.4f}")
print("  after iterations 1-5:", " ".join(f"{v:.2f}" for v in trace[1:6]))
o = np.argsort(mu[:, 0]); w, mu, S = w[o], mu[o], S[o]; R = R[:, o]
for k in range(2):
    print(f"  component {k + 1}: weight {w[k]:.3f}, mean ({mu[k, 0]:.2f} min, {mu[k, 1]:.1f} min), "
          f"sd ({np.sqrt(S[k, 0, 0]):.2f}, {np.sqrt(S[k, 1, 1]):.1f}), correlation {S[k, 0, 1] / np.sqrt(S[k, 0, 0] * S[k, 1, 1]):.2f}")
print(f"eruptions with responsibility between 0.05 and 0.95 (genuinely uncertain): {np.sum((R[:, 0] > .05) & (R[:, 0] < .95))} of {n}")
from sklearn.mixture import GaussianMixture
gm = GaussianMixture(2, covariance_type='full', n_init=5, random_state=0).fit(X)
print(f"scikit-learn GaussianMixture: log-likelihood {gm.score(X) * n:.4f}, weights {np.sort(gm.weights_).round(3)}")
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
km = KMeans(2, n_init=10, random_state=0).fit_predict(X); hard = R.argmax(1)
print(f"k-means on the raw scale agrees with the GMM's hard assignments for {max(np.mean(km == hard), np.mean(km != hard)):.1%} of eruptions")
EM converged in 54 iterations; log-likelihood -2740.55 -> -1130.2640
  after iterations 1-5: -1290.81 -1288.09 -1287.30 -1286.98 -1286.83
  component 1: weight 0.356, mean (2.04 min, 54.5 min), sd (0.26, 5.8), correlation 0.29
  component 2: weight 0.644, mean (4.29 min, 80.0 min), sd (0.41, 6.0), correlation 0.38
eruptions with responsibility between 0.05 and 0.95 (genuinely uncertain): 1 of 272
scikit-learn GaussianMixture: log-likelihood -1130.2641, weights [0.356 0.644]
k-means on the raw scale agrees with the GMM's hard assignments for 98.2% of eruptions

From a poor start (means the wrong way round), EM converges in 54 iterations to log-likelihood −1130.264, the value scikit-learn finds with five restarts, never decreasing. The short component has weight 0.356 and mean 2.04 minutes after a 54.5-minute wait; the long one 0.644, 4.29 minutes after 80.0. Only one of the 272 eruptions has a responsibility between 0.05 and 0.95. Raw-scale k-means agrees with the hard assignments for 98.2% of eruptions; the rest differ because the waiting time, with about twelve times the spread, dominates its distances.

EM, one step at a time

Each step is one E-step and one M-step; ellipses are two-standard-deviation contours, colours show responsibilities. With three or four components, different starts reach different local maxima.

k-means (Lecture 15) is EM without the probabilities. Fix every covariance to \(\sigma^2I\) and every weight to \(1/K\). The responsibilities become a softmax of \(-\lVert x_i-\mu_k\rVert^2/2\sigma^2\); as \(\sigma\to0\) they become one-hot, and EM becomes Lloyd's algorithm.

code — k-means as the zero-variance limit of EM
# k-means is hard EM: a shared spherical covariance sigma^2 I with sigma -> 0
Z = StandardScaler().fit_transform(X)
km_lab = KMeans(2, n_init=10, random_state=0).fit(Z); C0 = km_lab.cluster_centers_
for s2 in [1.0, 0.1, 0.01]:
    m = C0.copy()
    for _ in range(200):                                    # EM with fixed equal weights and fixed covariance s2 * I
        d2 = ((Z[:, None, :] - m[None]) ** 2).sum(-1); L = -d2 / (2 * s2)
        Rs = np.exp(L - L.max(1, keepdims=True)); Rs /= Rs.sum(1, keepdims=True)
        m = (Rs.T @ Z) / Rs.sum(0)[:, None]
    print(f"sigma^2 = {s2:5.2f}: mean max responsibility {Rs.max(1).mean():.4f}; centres "
          f"{np.round(m[np.argsort(m[:, 0])], 3).tolist()}")
print(f"k-means centres (standardised data):  {np.round(C0[np.argsort(C0[:, 0])], 3).tolist()}")
sigma^2 =  1.00: mean max responsibility 0.9384; centres [[-1.072, -1.038], [0.692, 0.67]]
sigma^2 =  0.10: mean max responsibility 0.9962; centres [[-1.258, -1.198], [0.712, 0.678]]
sigma^2 =  0.01: mean max responsibility 0.9999; centres [[-1.26, -1.202], [0.71, 0.677]]
k-means centres (standardised data):  [[-1.26, -1.202], [0.71, 0.677]]

The average largest responsibility is 0.938 at \(\sigma^2=1\) (soft points pull the centres together) and 0.996 at \(\sigma^2=0.1\); at 0.01 the centres match k-means to three decimals.

spot check 17.1

A two-component mixture has weights 0.5 and 0.5. At a point \(x\), the first component's density is 0.1 and the second's is 0.4. What is the responsibility of the first component?

\(r_1=\pi_1p_1/(\pi_1p_1+\pi_2p_2)\).
\(0.05/(0.05+0.2)=0.2\). With weights 0.8 and 0.2 it would be \(0.08/(0.08+0.08)=0.5\): the prior weight matters as much as the fit.

3 — Why EM works

EM climbs an easier function, the evidence lower bound (ELBO), that lies below the log-likelihood and touches it at the current parameters, so raising the bound raises the likelihood. The gap is a KL divergence, zero only when the two distributions agree. This is the identity of Lecture 16b in this lecture's notation.

theorem 17.1 — the ELBO decomposition

For any distribution \(q(z)\) over the hidden variables,

$$\log p(x\mid\theta)=\mathcal L(q,\theta)+\mathrm{KL}\big(q(z)\,\Vert\,p(z\mid x,\theta)\big),$$

where the ELBO is

$$\mathcal L(q,\theta)=\mathbb E_q\big[\log p(x,z\mid\theta)\big]-\mathbb E_q[\log q(z)].$$

Hence \(\log p(x\mid\theta)\ge\mathcal L(q,\theta)\), with equality if and only if \(q(z)=p(z\mid x,\theta)\).

For every \(z\),

$$\log p(x\mid\theta)=\log p(x,z\mid\theta)-\log p(z\mid x,\theta).$$

Add and subtract \(\log q(z)\), and average over \(q\):

$$\log p(x\mid\theta)=\mathbb E_q\left[\log\frac{p(x,z\mid\theta)}{q(z)}\right]+\mathbb E_q\left[\log\frac{q(z)}{p(z\mid x,\theta)}\right]=\mathcal L(q,\theta)+\mathrm{KL}(q\Vert p(\cdot\mid x,\theta)).$$

The KL divergence is non-negative and zero only when the two distributions are equal (Theorem 16.8). \(\square\)

theorem 17.2 — EM never decreases the likelihood

Let \(\theta_{t+1}\) be obtained from \(\theta_t\) by one E-step and one M-step. Then

$$\log p(x\mid\theta_{t+1})\;\ge\;\log p(x\mid\theta_t).$$

The E-step sets \(q_t=p(z\mid x,\theta_t)\), so the KL term vanishes and

$$\mathcal L(q_t,\theta_t)=\log p(x\mid\theta_t).$$

The M-step chooses \(\theta_{t+1}\) to maximise \(\mathcal L(q_t,\theta)\). The entropy term \(-\mathbb E_{q_t}[\log q_t]\) does not depend on \(\theta\), so this is the same as maximising \(\mathbb E_{q_t}[\log p(x,z\mid\theta)]\).

By Theorem 17.1 (first inequality) and the M-step (second),

$$\log p(x\mid\theta_{t+1})\;\ge\;\mathcal L(q_t,\theta_{t+1})\;\ge\;\mathcal L(q_t,\theta_t)\;=\;\log p(x\mid\theta_t).\qquad\square$$

EM is thus coordinate ascent on the ELBO: the E-step maximises over \(q\), the M-step over \(\theta\). Hence:

4 — How many components? BIC and label switching

More components always fit the training data better, so the likelihood cannot choose \(K\). The Bayesian answer compares the marginal likelihood, the probability of the data averaged over the prior; a model with many parameters spreads its prior thinly and is penalised automatically. Schwarz's BIC approximates it, as Occam's razor with a price list: each extra parameter must raise the log-likelihood by \(\tfrac12\log n\), about 2.2 for 82 galaxies, so a new three-parameter component must gain about 6.6.

theorem 17.3 — BIC as a Laplace approximation (Schwarz, 1978)

Let a model \(M\) have \(p\) free parameters, maximum-likelihood estimate \(\hat\theta\) and \(n\) independent observations. Under regularity conditions,

$$\log p(x\mid M)=\log\int p(x\mid\theta,M)\,p(\theta\mid M)\,d\theta=\log p(x\mid\hat\theta,M)-\frac p2\log n+O(1).$$

So, up to a bounded term, \(-2\) times the log marginal likelihood is

$$\mathrm{BIC}=-2\log p(x\mid\hat\theta,M)+p\log n.$$

Lower BIC is better. AIC replaces \(p\log n\) by \(2p\).

Write the integrand as \(\exp(nh(\theta))\), where

$$h(\theta)=\tfrac1n\big[\log p(x\mid\theta)+\log p(\theta)\big].$$

For large \(n\) it peaks sharply near \(\hat\theta\), with width \(O(1/\sqrt n)\). A second-order Taylor expansion gives a Gaussian integral (Laplace's method):

$$\int e^{nh(\theta)}d\theta\approx e^{nh(\hat\theta)}\left(\frac{2\pi}n\right)^{p/2}\big|{-\nabla^2h(\hat\theta)}\big|^{-1/2}.$$

Taking logarithms,

$$\log p(x\mid M)\approx\log p(x\mid\hat\theta)+\log p(\hat\theta)+\frac p2\log2\pi-\frac p2\log n-\frac12\log|{-\nabla^2h}|.$$

As \(n\) grows, \(-\nabla^2h\) tends to the Fisher information per observation, which does not grow with \(n\), so all terms but the first and \(-\frac p2\log n\) are \(O(1)\). \(\square\)

Mixtures break the regularity conditions (parameters are not identifiable when a weight is zero or two components coincide, exactly the boundary model comparison cares about), so for mixtures BIC is a well-tested heuristic rather than a theorem.

data — galaxy velocities

Velocities, in thousands of km/s, of 82 galaxies in a region of the Corona Borealis constellation, measured by Postman, Huchra and Geller (1986) and analysed by Roeder (1990) as a mixture: if galaxies cluster in space, their recession velocities should form groups. The data are distributed as MASS::galaxies in R; we use the Rdatasets copy on GitHub. Richardson and Green's (1997) Bayesian analysis made it the standard test of methods that infer the number of components.

code — BIC and AIC for 1 to 8 components; label switching and local maxima
# Galaxy velocities: how many components? BIC, AIC, and label switching
gal = pd.read_csv('data/galaxies.csv').dat.to_numpy() / 1000.0       # 82 velocities, in 1000 km/s
G1 = gal[:, None]; bic, aic, fits = {}, {}, {}
for k in range(1, 9):
    g = GaussianMixture(k, n_init=20, random_state=0, reg_covar=1e-4).fit(G1)
    bic[k], aic[k], fits[k] = g.bic(G1), g.aic(G1), g
print(" k   log-lik    params   BIC      AIC")
for k in range(1, 9):
    p = 3 * k - 1; print(f"{k:2d}  {fits[k].score(G1) * len(gal):8.2f}   {p:3d}   {bic[k]:7.2f}  {aic[k]:7.2f}")
print(f"BIC chooses k = {min(bic, key=bic.get)}, AIC chooses k = {min(aic, key=aic.get)}")
for seed in [0, 1, 2]:                                       # best of 20 random starts, three times
    g = GaussianMixture(3, n_init=20, random_state=seed, init_params='random_from_data').fit(G1)
    print(f"seed {seed}: log-lik {g.score(G1) * len(gal):.3f}, means in label order {np.round(g.means_.ravel(), 2).tolist()}")
single = [GaussianMixture(3, n_init=1, random_state=s, init_params='random_from_data').fit(G1).score(G1) * len(gal) for s in range(50)]
print(f"50 single random starts: log-lik from {min(single):.2f} to {max(single):.2f}; within 0.01 of the best: {np.mean(np.array(single) > max(single) - 0.01):.0%}")
 k   log-lik    params   BIC      AIC
 1   -240.34     2    489.49   484.68
 2   -220.06     5    462.15   450.12
 3   -203.18     8    441.61   422.36
 4   -202.20    11    452.88   426.41
 5   -190.17    14    442.03   408.34
 6   -189.26    17    453.43   412.52
 7   -187.94    20    464.01   415.87
 8   -181.83    23    465.02   409.67
BIC chooses k = 3, AIC chooses k = 5
seed 0: log-lik -203.179, means in label order [21.4, 33.04, 9.71]
seed 1: log-lik -203.179, means in label order [21.4, 9.71, 33.04]
seed 2: log-lik -203.179, means in label order [21.4, 33.04, 9.71]
50 single random starts: log-lik from -233.51 to -203.18; within 0.01 of the best: 16%
1015202530350.00.10.20.3velocity (1000 km/s)densityk = 3 (BIC)k = 5 (AIC)
Histogram of the 82 galaxy velocities (bins of 1,000 km/s) with the maximum-likelihood mixtures of 3 components (rose, chosen by BIC) and 5 components (moss, chosen by AIC).

BIC chooses three components, near 9.7, 21.4 (the large central group) and 33.0 thousand km/s; AIC's lighter penalty gives five, splitting the central group. Neither is "right": with 82 numbers the answer depends on the penalty, ultimately a prior judgement (Section 5).

Choosing k for the galaxies

The maximum-likelihood mixture with \(k\) components (left) and the BIC and AIC curves for \(k=1\) to 8 (right; dashed line at the current \(k\)).

spot check 17.2

How many free parameters does a one-dimensional Gaussian mixture with \(K=3\) components have?

Count means, variances and weights; the weights sum to 1.
3 means + 3 variances + 2 free weights = 8, as in the code's table (\(3K-1\)). A \(d\)-dimensional mixture with full covariances has \(K\big(d+d(d+1)/2\big)+K-1\).

5 — Bayesian mixtures and the Dirichlet process

A Bayesian mixture puts a prior on all parameters and computes their posterior. The natural prior on the weights is a Dirichlet distribution, over proportions summing to 1; its parameter makes them even or dominated by a few. Letting the number of components grow without limit gives the Dirichlet process.

definition 17.3 — the Chinese restaurant process and the Dirichlet-process mixture

Customers enter a restaurant with infinitely many tables, and the first sits at a table. Given \(i\) seated customers and a concentration \(\alpha>0\), customer \(i+1\)

The seating plan is a random partition of the customers: the Chinese restaurant process (CRP).

In a Dirichlet-process mixture, tables are clusters, each table has parameters drawn from a base distribution \(G_0\), and each customer's observation is drawn from its table's distribution.

This is the law of the cluster labels under a Dirichlet-process prior \(G\sim\mathrm{DP}(\alpha,G_0)\) on the mixing distribution (Ferguson, 1973; Blackwell and MacQueen, 1973).

The rich get richer, yet new tables keep opening, ever more slowly.

proposition 17.4 — the expected number of tables

Under the CRP with concentration \(\alpha\), the expected number of occupied tables after \(n\) customers is

$$\mathbb E[K_n]=\sum_{i=0}^{n-1}\frac\alpha{\alpha+i}\;\approx\;\alpha\log\!\left(1+\frac n\alpha\right).$$

Customer \(i+1\) opens a new table with probability \(\alpha/(\alpha+i)\), whatever the previous seating. \(K_n\) counts these openings, a sum of indicators, so linearity of expectation gives the sum.

For the approximation, compare the sum with

$$\int_0^n\frac\alpha{\alpha+t}\,dt=\alpha\log(1+n/\alpha).$$

The summand is decreasing and its first term is 1, so the sum exceeds the integral by less than 1. \(\square\)

code — simulating the restaurant
# The Chinese restaurant process: expected number of tables, simulation against Proposition 17.4
def crp(n, alpha, rg):
    tables = []
    for i in range(n):
        p = np.array(tables + [alpha], float); j = rg.choice(len(p), p=p / p.sum())
        if j == len(tables): tables.append(1)
        else: tables[j] += 1
    return tables
rg = np.random.default_rng(1)
for alpha in [0.3, 1.0, 3.0, 10.0]:
    sims = [len(crp(82, alpha, rg)) for _ in range(2000)]
    exact = sum(alpha / (alpha + i) for i in range(82))
    print(f"alpha = {alpha:4.1f}, n = 82: simulated mean tables {np.mean(sims):5.2f}, exact {exact:5.2f}, "
          f"alpha log(1 + n/alpha) = {alpha * np.log(1 + 82 / alpha):5.2f}")
alpha =  0.3, n = 82: simulated mean tables  2.35, exact  2.37, alpha log(1 + n/alpha) =  1.68
alpha =  1.0, n = 82: simulated mean tables  5.00, exact  4.99, alpha log(1 + n/alpha) =  4.42
alpha =  3.0, n = 82: simulated mean tables 10.61, exact 10.54, alpha log(1 + n/alpha) = 10.03
alpha = 10.0, n = 82: simulated mean tables 22.70, exact 22.65, alpha log(1 + n/alpha) = 22.19

Simulation and formula agree (\(\alpha=1\), 82 customers: 5.00 tables simulated, 4.99 exact), and the logarithmic approximation is within a table. Clusters grow without bound but only like \(\log n\), so a Dirichlet-process mixture need not be told \(K\).

The Chinese restaurant

Seat \(n\) customers by the CRP; tables are sorted by size, with area proportional to customers. New seating reruns with another seed.

Gibbs sampling re-draws one unknown at a time given the others; after many sweeps the draws behave like a posterior sample. With a conjugate normal–inverse-gamma prior (posterior of the same form) on each component's mean and variance, the component parameters integrate out, and a collapsed Gibbs sampler (Neal, 2000) needs only the seating. Remove one galaxy and reseat it

The predictive densities are Student-t distributions.

code — a Dirichlet-process mixture for the galaxies by collapsed Gibbs sampling
# A Dirichlet-process mixture of normals for the galaxies, by collapsed Gibbs sampling (Chinese restaurant process)
from scipy.special import gammaln
mu0, k0, a0, b0 = gal.mean(), 0.1, 2.0, 2.0                 # normal-inverse-gamma prior on each component's (mean, variance)
def log_pred(x, n, s, ss):                                  # log predictive density of x for a table with n, sum s, sum of squares ss
    kn = k0 + n; mn = (k0 * mu0 + s) / kn; an = a0 + n / 2
    bn = b0 + 0.5 * (ss - s * s / n if n else 0) + (k0 * n * ((s / n if n else 0) - mu0) ** 2) / (2 * kn)
    sc2 = bn * (kn + 1) / (an * kn); nu = 2 * an           # Student-t with nu degrees of freedom
    return gammaln((nu + 1) / 2) - gammaln(nu / 2) - 0.5 * np.log(nu * np.pi * sc2) - (nu + 1) / 2 * np.log1p((x - mn) ** 2 / (nu * sc2))
def dp_gibbs(x, alpha, sweeps, seed):
    rg = np.random.default_rng(seed); z = np.zeros(len(x), int); stats = {0: [len(x), x.sum(), (x**2).sum()]}; Ks = []
    for t in range(sweeps):
        for i in rg.permutation(len(x)):
            st = stats[z[i]]; st[0] -= 1; st[1] -= x[i]; st[2] -= x[i] ** 2
            if st[0] == 0: del stats[z[i]]
            labs = list(stats); lp = [np.log(stats[c][0]) + log_pred(x[i], *stats[c]) for c in labs]   # join a table: n_c
            lp.append(np.log(alpha) + log_pred(x[i], 0, 0.0, 0.0)); labs.append(max(stats, default=-1) + 1)   # new table: alpha
            p = np.exp(np.array(lp) - max(lp)); c = labs[rg.choice(len(p), p=p / p.sum())]
            z[i] = c; stats.setdefault(c, [0, 0.0, 0.0]); st = stats[c]; st[0] += 1; st[1] += x[i]; st[2] += x[i] ** 2
        Ks.append(len(stats))
    return np.array(Ks), z
for alpha in [0.3, 1.0, 3.0]:
    Ks, zl = dp_gibbs(gal, alpha, 1500, 0); K = Ks[300:]
    dist = np.bincount(K, minlength=16)[3:15] / len(K)
    print(f"alpha = {alpha}: P(K = 3..14) = {' '.join(f'{v:.2f}' for v in dist)};  posterior mean K {K.mean():.2f}")
    if alpha == 1.0: z_dp = zl
sizes = sorted(np.bincount(z_dp)[np.bincount(z_dp) > 0].tolist(), reverse=True)
print(f"last sample at alpha = 1: table sizes {sizes}")
alpha = 0.3: P(K = 3..14) = 0.06 0.15 0.31 0.32 0.13 0.03 0.00 0.00 0.00 0.00 0.00 0.00;  posterior mean K 5.44
alpha = 1.0: P(K = 3..14) = 0.00 0.01 0.04 0.14 0.24 0.23 0.18 0.10 0.04 0.02 0.00 0.00;  posterior mean K 7.97
alpha = 3.0: P(K = 3..14) = 0.00 0.00 0.00 0.00 0.00 0.03 0.06 0.13 0.16 0.19 0.16 0.11;  posterior mean K 12.20
last sample at alpha = 1: table sizes [35, 19, 10, 7, 5, 4, 2]

The posterior over the number of clusters depends strongly on the prior: with \(\alpha=0.3\) the most probable values are 5 and 6 (mean 5.44); with \(\alpha=1\), 7 to 9 (mean 7.97); with \(\alpha=3\), more than 10. Many clusters are tiny (the last sample at \(\alpha=1\) has tables of 35, 19, 10, 7, 5, 4 and 2), and the variance prior matters as much: ours allows narrow components, favouring many. Richardson and Green (1997) found the same sensitivity: 82 observations cannot override the prior on "how many groups", so an honest analysis reports how the answer moves with it.

Bayes — three ways to fit a mixture

All three alternate between labels and parameters.

The Dirichlet process works with all three: via the CRP in Gibbs sampling, and via truncated stick-breaking in variational inference (Blei and Jordan, 2006), as in scikit-learn's BayesianGaussianMixture.

history — Pearson's crabs, EM, and talking machines

Karl Pearson fitted the first mixture model (1894) to Walter Weldon's slightly asymmetric ratios of forehead breadth to body length in 1,000 Naples crabs. Suspecting two sub-species, he matched five moments of a two-normal mixture and solved a degree-nine polynomial by hand. EM was used in special cases for decades before Dempster, Laird and Rubin unified them (1977), in one of the most cited papers in statistics; C. F. Jeff Wu corrected its convergence proof in 1983. EM for HMMs came earlier, from Leonard Baum, Lloyd Welch and colleagues at the Institute for Defense Analyses around 1970. Through Frederick Jelinek's group at IBM and James and Janet Baker (Dragon Systems), Baum–Welch HMMs underlay practically all speech recognition from the 1980s until deep networks took over around 2012.

6 — Mixtures in time: hidden Markov models

In many sequences the hidden labels are not independent: parts of speech depend on the previous word's, DNA is coding or non-coding for hundreds of bases, and markets switch between calm and turbulent periods lasting months. A hidden Markov model lets the labels form a Markov chain (the next state depends only on the current one), seen only through noisy clues, like weather inferred from umbrellas.

definition 17.4 — hidden Markov model

A hidden Markov model (HMM) with \(K\) states has

The hidden states \(z_1,\dots,z_T\) form a Markov chain, and each observation \(x_t\) depends only on \(z_t\):

$$p(x_{1:T},z_{1:T})=\pi_{z_1}b_{z_1}(x_1)\prod_{t=2}^TA_{z_{t-1}z_t}\,b_{z_t}(x_t).$$

A Gaussian mixture is the special case in which every row of \(A\) equals \(\pi\).

The likelihood \(p(x_{1:T})\) sums the joint over all \(K^T\) state paths. Dynamic programming avoids listing them: as in route finding, it suffices to remember, for each state at each time, the total probability of reaching it while producing the observations so far.

theorem 17.5 — the forward algorithm

Define \(\alpha_t(k)=p(x_1,\dots,x_t,z_t=k)\). Then

$$\alpha_1(k)=\pi_kb_k(x_1),\qquad\alpha_{t+1}(k)=b_k(x_{t+1})\sum_{j=1}^K\alpha_t(j)A_{jk},$$ $$p(x_{1:T})=\sum_k\alpha_T(k).$$

The likelihood is thus computed in \(O(TK^2)\) operations instead of \(O(TK^T)\).

The first equation is the definition at \(t=1\). For the recursion, sum over the previous state and use the two conditional independences (next state given current; next observation given next state):

$$\alpha_{t+1}(k)=\sum_jp(x_{1:t},z_t=j)\,P(z_{t+1}=k\mid z_t=j)\,p(x_{t+1}\mid z_{t+1}=k)=b_k(x_{t+1})\sum_j\alpha_t(j)A_{jk}.$$

Each step computes \(K\) sums of \(K\) terms, so \(T\) steps cost \(O(TK^2)\); summing \(\alpha_T\) over the final state gives the likelihood.

In practice each \(\alpha_t\) is rescaled to sum to 1 against underflow; the log-likelihood is the sum of the logs of the scaling factors. \(\square\)

A backward recursion

$$\beta_t(j)=\sum_kA_{jk}b_k(x_{t+1})\beta_{t+1}(k)$$

gives \(\beta_t(j)=p(x_{t+1:T}\mid z_t=j)\) and the state posteriors \(P(z_t=k\mid x_{1:T})\propto\alpha_t(k)\beta_t(k)\), and similarly for transitions. That is the E-step of the Baum–Welch algorithm (EM for HMMs); the M-step re-estimates \(A\) from expected transition counts and the emissions as in a weighted mixture. Replacing the sum by a maximum, with back-pointers, gives the Viterbi algorithm (1967) for the most probable state path.

data — daily US stock-market returns (Fama–French)

The daily excess return of the US stock market (the value-weighted return on all NYSE, AMEX and NASDAQ stocks minus the one-month Treasury-bill rate, in per cent), 1 July 1963 to 30 April 2020, 14,306 trading days, from Kenneth French's Data Library at Dartmouth (file F-F_Research_Data_5_Factors_2x3_daily, built from the CRSP database; the column is labelled MER in this copy). The library itself was not reachable from the build environment, so we use the copy in the GitHub repository omartinsky/FamaFrench, which ends in April 2020.

code — Baum–Welch and Viterbi for a two-state market model
# A two-state Gaussian hidden Markov model of daily US stock-market returns (Baum-Welch and Viterbi)
ff = pd.read_csv('data/ff5_daily.csv', skiprows=4, skipfooter=1, engine='python', index_col=0)
ff.index = pd.to_datetime(ff.index.astype(str).str.strip(), format='%Y%m%d'); r = ff['MER'].to_numpy()   # market minus T-bill, % per day
T = len(r); print(f"{T:,} trading days, {ff.index[0]:%d %b %Y} to {ff.index[-1]:%d %b %Y}; sd {r.std():.2f}% per day")
def norm_pdf(x, m, s): return np.exp(-0.5 * ((x[:, None] - m) / s) ** 2) / (s * np.sqrt(2 * np.pi))
def forward_backward(B, A, pi):                             # scaled forward-backward; B[t, k] = p(r_t | state k)
    T, K = B.shape; al = np.zeros((T, K)); c = np.zeros(T)
    al[0] = pi * B[0]; c[0] = al[0].sum(); al[0] /= c[0]
    for t in range(1, T): al[t] = (al[t - 1] @ A) * B[t]; c[t] = al[t].sum(); al[t] /= c[t]
    be = np.ones((T, K))
    for t in range(T - 2, -1, -1): be[t] = (A @ (B[t + 1] * be[t + 1])) / c[t + 1]
    return al, be, c, np.log(c).sum()                       # the log-likelihood is the sum of the log scaling factors
m, s, A, pi = np.array([0.05, -0.05]), np.array([0.6, 1.8]), np.array([[0.98, 0.02], [0.05, 0.95]]), np.array([0.5, 0.5])
lls = []
for it in range(200):
    B = norm_pdf(r, m, s); al, be, c, ll = forward_backward(B, A, pi); lls.append(ll)
    gam = al * be; gam /= gam.sum(1, keepdims=True)         # P(state at t | all data)
    xi = (al[:-1, :, None] * A[None] * (B[1:] * be[1:])[:, None, :]) / c[1:, None, None]   # P(states at t, t+1 | data)
    A = xi.sum(0) / xi.sum((0, 2))[:, None]; pi = gam[0]
    m = (gam * r[:, None]).sum(0) / gam.sum(0); s = np.sqrt((gam * (r[:, None] - m) ** 2).sum(0) / gam.sum(0))
    if it and lls[-1] - lls[-2] < 1e-6: break
assert np.all(np.diff(lls) > -1e-6)
print(f"Baum-Welch converged in {len(lls)} iterations; log-likelihood {lls[-1]:.1f}")
for k in range(2):
    print(f"  state {k}: mean {m[k]:+.3f}% per day, sd {s[k]:.2f}%, stays with probability {A[k, k]:.4f} "
          f"(expected run {1 / (1 - A[k, k]):.0f} days), share of days {gam[:, k].mean():.1%}")
mix = GaussianMixture(2, random_state=0).fit(r[:, None])
print(f"same two normals without the Markov chain (i.i.d. mixture): log-likelihood {mix.score(r[:, None]) * T:.1f}")
def viterbi(B, A, pi):
    lA = np.log(A); d = np.log(pi) + np.log(B[0]); back = np.zeros((len(B), len(pi)), int)
    for t in range(1, len(B)): sc = d[:, None] + lA; back[t] = sc.argmax(0); d = sc.max(0) + np.log(B[t])
    path = [int(d.argmax())]
    for t in range(len(B) - 1, 0, -1): path.append(back[t, path[-1]])
    return np.array(path[::-1])
vit = viterbi(norm_pdf(r, m, s), A, pi); turb = int(np.argmax(s))
for a, b, nm in [('1987-10-01', '1987-12-31', 'Oct-Dec 1987'), ('2008-09-01', '2009-03-31', 'Sep 2008-Mar 2009'),
                 ('2017-01-01', '2017-12-31', '2017'), ('2020-02-20', '2020-04-30', '20 Feb-30 Apr 2020')]:
    msk = (ff.index >= a) & (ff.index <= b); print(f"  {nm:20s}: Viterbi path turbulent on {np.mean(vit[msk] == turb):.0%} of days")
x10 = r[:10]; B10 = norm_pdf(x10, m, s); import itertools       # the forward algorithm against brute force, first 10 days
brute = sum(pi[p[0]] * B10[0, p[0]] * np.prod([A[p[t - 1], p[t]] * B10[t, p[t]] for t in range(1, 10)])
            for p in itertools.product(range(2), repeat=10))
print(f"first 10 days: forward algorithm log p = {forward_backward(B10, A, pi)[3]:.6f}; sum over all 1,024 paths {np.log(brute):.6f}")
14,306 trading days, 01 Jul 1963 to 30 Apr 2020; sd 1.01% per day
Baum-Welch converged in 23 iterations; log-likelihood -17747.4
  state 0: mean +0.062% per day, sd 0.62%, stays with probability 0.9875 (expected run 80 days), share of days 74.7%
  state 1: mean -0.083% per day, sd 1.70%, stays with probability 0.9634 (expected run 27 days), share of days 25.3%
same two normals without the Markov chain (i.i.d. mixture): log-likelihood -18657.4
  Oct-Dec 1987        : Viterbi path turbulent on 95% of days
  Sep 2008-Mar 2009   : Viterbi path turbulent on 100% of days
  2017                : Viterbi path turbulent on 0% of days
  20 Feb-30 Apr 2020  : Viterbi path turbulent on 98% of days
first 10 days: forward algorithm log p = -8.070323; sum over all 1,024 paths -8.070323
196519701975198019851990199520002005201020152020-10-50510daily return (%)19 Oct 1987: -17.4% (clipped)
Daily market excess returns, 1963–2020 (sky), with the posterior probability of the turbulent state shaded in amber. Turbulence clusters in time: in 1974, 1999–2002, 2008–09, 2011 and 2020 the turbulent state has posterior probability above 0.6 on average over the year, and the autumn of 1987 stands out as a short burst.

Baum–Welch converges in 23 iterations. Calm (74.7% of days): daily standard deviation 0.62%, mean +0.062%. Turbulent (25.3%): 1.70%, mean −0.083%. Both persist: calm continues with probability 0.9875 a day (expected run 80 trading days), turbulence lasts 27 days on average. Persistence matters: an independent mixture of the same normals scores 910 lower (−18,657.4 against −17,747.4).

The Viterbi path is turbulent on 95% of days from October to December 1987, every day from September 2008 to March 2009, 98% of days from 20 February to 30 April 2020, and no day of quiet 2017. On the first 10 days the forward algorithm matches an explicit sum over all 1,024 paths to six decimals. Such regime-switching models (Hamilton, 1989) describe the past well but say little about when the next switch will come.

Market regimes

Bars are daily returns; amber shading is the posterior probability of the turbulent state. Look at 1987, 2000–2003, 2008 and early 2020, and at the calm mid-1990s and 2017.

spot check 17.3

A Markov-chain state with self-transition probability \(a\) lasts a geometric number of steps with mean \(1/(1-a)\). The fitted turbulent state has \(a=0.9634\). How many trading days does a turbulent spell last on average?

\(1/(1-0.9634)\).
\(1/0.0366\approx27\) trading days, five or six weeks. The geometric law is a strong assumption (its mode is one day); hidden semi-Markov models allow any duration distribution.

7 — Mixtures of words: topic models

A paper on reinforcement learning for robot vision mixes three topics; a plain mixture would allow one. Latent Dirichlet allocation (Blei, Ng and Jordan, 2003) makes every document its own mixture of shared topics, each a distribution over words. Imagine an author choosing a recipe (say 60% statistics, 30% medicine, 10% computing), then writing each word by picking a topic from the recipe and a word from that topic. LDA runs the story backwards.

definition 17.5 — latent Dirichlet allocation

LDA with \(K\) topics generates a corpus as follows.

Fitting infers the topics \(\phi_k\) and proportions \(\theta_d\) from the words alone, by variational inference or Gibbs sampling.

The same model, with individuals, ancestral populations and alleles for documents, topics and words, appeared three years earlier in population genetics as STRUCTURE (Pritchard, Stephens and Donnelly, 2000).

data — arXiv abstracts

Titles, abstracts and subject categories of 51,774 arXiv papers (38,972 after removing duplicates), collected by Soumik Rakshit and Sayak Paul for a Keras multi-label classification example, on GitHub (soumik12345/multi-label-text-classification); the arXiv API itself was not reachable. We keep papers whose first listed category is a machine-learning or vision category and sample 12,000: 6,347 in computer vision (cs.CV), 4,884 in machine learning (cs.LG) and 769 in statistical machine learning (stat.ML). The collection has no dates, so trends over time could not be studied here; Project 2 does that.

code — LDA on 12,000 abstracts
# A topic model of machine-learning research: LDA on arXiv abstracts
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.decomposition import LatentDirichletAllocation
ax = pd.read_csv('data/arxiv_data.csv').drop_duplicates('titles')
ax['primary'] = ax.terms.str.extract(r"'([^']+)'")[0]
ax = ax[ax.primary.isin(['cs.LG', 'stat.ML', 'cs.CV', 'cs.CL', 'cs.AI'])].sample(12000, random_state=0)
cv = CountVectorizer(max_df=0.4, min_df=10, stop_words='english', max_features=6000, token_pattern=r'(?u)\b[a-zA-Z][a-zA-Z]+\b')
Wc = cv.fit_transform(ax.summaries); vocab = np.array(cv.get_feature_names_out())
Wtr, Wte = Wc[:10000], Wc[10000:]
print(f"{len(ax):,} abstracts (10,000 to fit, 2,000 held out); vocabulary {len(vocab):,} words; "
      f"primary categories {ax.primary.value_counts().to_dict()}")
for K in [5, 10, 20, 40]:
    l = LatentDirichletAllocation(K, learning_method='batch', max_iter=15, random_state=0).fit(Wtr)
    print(f"K = {K:2d}: held-out perplexity {l.perplexity(Wte):7.1f}")
    if K == 10: lda = l
theta = lda.transform(Wc)
for k in np.argsort(-theta.mean(0)):
    print(f"topic {k}: {theta[:, k].mean():.1%} of words | " + " ".join(vocab[np.argsort(-lda.components_[k])[:9]]))
share = pd.DataFrame(theta, index=ax.primary.values).groupby(level=0).mean()
top = share.idxmax(1)
print("most prominent topic by primary category:", {c: f"topic {k} ({share.loc[c, k]:.0%})" for c, k in top.items()})
12,000 abstracts (10,000 to fit, 2,000 held out); vocabulary 6,000 words; primary categories {'cs.CV': 6347, 'cs.LG': 4884, 'stat.ML': 769}
K =  5: held-out perplexity  2148.4
K = 10: held-out perplexity  2408.8
K = 20: held-out perplexity  2942.3
K = 40: held-out perplexity  4113.7
topic 5: 14.5% of words | algorithm policy reinforcement rl algorithms function problem methods state
topic 7: 11.6% of words | image images generative domain method segmentation resolution adversarial gan
topic 3: 11.4% of words | graph representation networks neural graphs network space structure methods
topic 9: 11.0% of words | machine models using deep used research different analysis results
topic 4: 10.9% of words | object point detection depth segmentation objects method estimation network
topic 1: 9.7% of words | networks neural training network deep models performance adversarial accuracy
topic 8: 9.6% of words | attention video features network temporal information feature recognition state
topic 2: 8.6% of words | time detection series classification training supervised class performance methods
topic 6: 7.1% of words | visual tasks task language models image representations human representation
topic 0: 5.7% of words | real agent time environment reinforcement agents world approach deep
most prominent topic by primary category: {'cs.CV': 'topic 4 (19%)', 'cs.LG': 'topic 5 (26%)', 'stat.ML': 'topic 5 (36%)'}

Ten topics recover recognisable areas without labels: reinforcement learning (policy, reinforcement, rl, state; 14.5% of words), generative image models (generative, adversarial, gan, resolution), graph representation learning, detection and depth, adversarial robustness, video and attention, time series and classification, vision-and-language, and agents in environments. One (machine, models, using, deep, used, research) is generic vocabulary, a usual by-product. Proportions match the unseen categories: the leading topic is detection and depth in computer vision (19% of words), reinforcement learning in cs.LG and stat.ML (26% and 36%).

A caution: scikit-learn's held-out perplexity rises with the number of topics, from 2,148 with 5 to 4,114 with 40, as if 5 fitted best. That is not credible. It is computed from the variational bound, which is known to penalise larger models and is unreliable for choosing \(K\) (Wallach et al., 2009, discuss better estimators). Topic models are judged instead by coherence and usefulness: unsupervised models need external checks (Lecture 14).

8 — Variational inference, and the VAE revisited

When the exact posterior is intractable (LDA, Bayesian mixtures, the VAE), we maximise the ELBO over a restricted family. The mean-field family treats the unknowns as independent; it typically gets posterior centres right but spreads too narrow.

definition 17.6 — mean-field variational inference

Let \(u=(u_1,\dots,u_m)\) be all unknowns of a model (hidden labels and parameters alike) and \(x\) the data. Mean-field variational inference chooses a factorised

$$q(u)=\prod_jq_j(u_j)$$

to maximise the ELBO

$$\mathcal L(q)=\mathbb E_q[\log p(x,u)]-\mathbb E_q[\log q(u)],$$

equivalently to minimise \(\mathrm{KL}(q\Vert p(u\mid x))\) (Theorem 17.1). Coordinate ascent updates one factor at a time by

$$\log q_j(u_j)=\mathbb E_{q_{-j}}[\log p(x,u)]+\text{const}.$$

EM is the special case with \(q\) unrestricted over the labels and a point mass over the parameters. Giving the parameters distributions too switches off unsupported components, because the KL term charges each component for the information its parameters carry.

code — EM against variational Bayes with six components
# Variational inference against EM: given 6 components, the variational Bayesian mixture switches most of them off
from sklearn.mixture import BayesianGaussianMixture
Zs = StandardScaler().fit_transform(X)
em6 = GaussianMixture(6, n_init=5, random_state=0).fit(Zs)
vb6 = BayesianGaussianMixture(n_components=6, weight_concentration_prior_type='dirichlet_process',
                              weight_concentration_prior=0.01, n_init=5, max_iter=2000, random_state=0).fit(Zs)
for nm, g in [('EM (maximum likelihood)', em6), ('variational Bayes, DP prior', vb6)]:
    print(f"{nm:28s} weights {np.sort(g.weights_)[::-1].round(3).tolist()}; components above 1%: {np.sum(g.weights_ > 0.01)}")
print(f"held-in log-likelihood per point: EM with 6 components {em6.score(Zs):.3f}, EM with 2 {GaussianMixture(2, random_state=0).fit(Zs).score(Zs):.3f}")
EM (maximum likelihood)      weights [0.241, 0.197, 0.158, 0.157, 0.142, 0.106]; components above 1%: 6
variational Bayes, DP prior  weights [0.644, 0.356, 0.0, 0.0, 0.0, 0.0]; components above 1%: 2
held-in log-likelihood per point: EM with 6 components -1.314, EM with 2 -1.417

With six components on the standardised eruptions, EM uses all six (weights 0.106 to 0.241), splitting the real groups for a slightly higher training likelihood (−1.314 per point against −1.417 with two). Variational Bayes with a Dirichlet-process prior keeps exactly two, with weights 0.644 and 0.356 as in Section 2, and zeroes the other four: \(K\) is chosen without an information criterion.

The VAE of Lecture 16b is this ELBO with an encoder network giving each point's Gaussian posterior (amortisation) and the expectation estimated by reparameterised sampling. It is an infinite mixture,

$$p(x)=\int p(x\mid z)\,N(z;0,I)\,dz,$$

with one decoded distribution per latent point \(z\). The lineage Gaussian mixture → EM → variational EM → VAE replaces, at each step, an exact computation with a more flexible approximation of the same bound.

spot check 17.4

Which statement about the E-step is correct?

Look at the proof of Theorem 17.2.
Setting \(q=p(z\mid x,\theta_t)\) zeroes the KL term, so the bound touches the likelihood; the M-step then raises both. Variational inference restricts \(q\), so the bound no longer touches.
quantum — mixed states are mixture models

A system prepared in state \(|\psi_i\rangle\) with probability \(p_i\) has density matrix \(\rho=\sum_ip_i|\psi_i\rangle\langle\psi_i|\), a mixed state: a mixture with hidden label \(i\). But different ensembles \(\{p_i,|\psi_i\rangle\}\) give the same \(\rho\), so no measurement can tell them apart: label switching taken much further. Conversely, a quantum circuit Born machine (Benedetti et al., 2019; Liu and Wang, 2018) prepares a state \(|\psi_\theta\rangle\) and samples bit strings \(x\) with probability \(|\langle x|\psi_\theta\rangle|^2\), training \(\theta\) to match data. Whether such models beat classical generative models is open; demonstrations are small.

big picture — hidden sub-populations everywhere

Speaker diarisation ("who spoke when") clusters audio embeddings with Gaussian mixtures and HMMs. Ancestry tests rest on STRUCTURE and ADMIXTURE, LDA by another name. Anomaly scores use mixture densities (Lecture 14); topic models organise legal discovery, archives and surveys; HMMs segment genomes, tag parts of speech and track economic regimes. And VAEs and diffusion models are mixtures over a continuous latent, trained through a version of the ELBO.

9 — Summary, exercises, projects, reading

summary

Next: Lecture 17b models dependence directly: Sklar's theorem separates any joint distribution into its margins and a copula, and copulas show where in the distribution two variables move together.

exercises
  1. Derive the M-step update for \(\mu_k\) by maximising \(\sum_i\sum_kr_{ik}\log\big(\pi_kN(x_i;\mu_k,\Sigma_k)\big)\) over \(\mu_k\).

    The terms involving \(\mu_k\) are

    $$-\tfrac12\sum_ir_{ik}(x_i-\mu_k)^\top\Sigma_k^{-1}(x_i-\mu_k).$$

    The gradient is \(\Sigma_k^{-1}\sum_ir_{ik}(x_i-\mu_k)\). Setting it to zero gives a weighted mean,

    $$\mu_k=\frac{\sum_ir_{ik}x_i}{\sum_ir_{ik}}.$$

    The weights follow similarly with a Lagrange multiplier for \(\sum_k\pi_k=1\), giving \(\pi_k=N_k/n\).

  2. Show that the log-likelihood of a Gaussian mixture is unbounded: let one component's mean equal a data point \(x_1\) and its variance tend to zero. Why does EM usually not run into this, and what do practical implementations do?

    That component's density at \(x_1\) is

    $$N(x_1;x_1,\sigma^2)=(2\pi\sigma^2)^{-1/2}\to\infty,$$

    while the other components keep every other point's density bounded away from zero, so the total log-likelihood tends to infinity.

    EM moves continuously from its start and usually reaches a sensible local maximum first, though collapse can happen with many components or few data. Implementations add a small ridge to each covariance's diagonal (a weak prior), or maximise a posterior.

  3. For the CRP with \(\alpha=1\), compute the probability that the first three customers all sit at the same table, and that they sit at three different tables.

    Customer 2 joins customer 1 with probability \(1/(1+1)=1/2\); customer 3 then joins them with probability \(2/(2+1)=2/3\): together \(1/3\).

    Three different tables: \(\frac12\cdot\frac13=\frac16\). (The remaining \(1/2\) is the probability of a 2–1 split.)

  4. Write the Viterbi recursion \(\delta_{t+1}(k)=b_k(x_{t+1})\max_j\delta_t(j)A_{jk}\) and explain why it finds the most probable path, using the same argument as the forward algorithm with max in place of sum.

    Let \(\delta_t(k)\) be the largest joint probability of \(x_{1:t}\) and any state path ending in state \(k\) at time \(t\).

    The best path ending in \(k\) at \(t+1\) extends some best path ending in \(j\) at \(t\) by the transition \(j\to k\) and the emission; maximising over \(j\) gives the recursion (the principle of optimality).

    Store the maximising \(j\) and trace back from \(\arg\max_k\delta_T(k)\). Max distributes over products as sum does, so the \(O(TK^2)\) structure carries over.

  5. In LDA, explain why setting the document-topic Dirichlet parameter \(\alpha\) small (say 0.1) encourages each document to use few topics, while a large \(\alpha\) spreads documents evenly across topics.

    With all parameters below 1, a Dirichlet puts most mass near the corners of the simplex (a few large coordinates, the rest near zero); above 1, near the centre (similar proportions).

    So \(\alpha<1\) says "each document is about a few topics", as people write, and gives more interpretable topics.

  6. (Code.) Fit three-state HMMs to the daily market returns, starting from several random initialisations. Do you get a "crash" state? Compare the log-likelihoods and BIC of the two- and three-state models.

    Extend m, s, A and pi to three states. Typically the third state captures a few extreme days or splits the calm regime into very calm and normal.

    The log-likelihood rises, and BIC's penalty for the 7 extra parameters (\(7\log14306\approx67\), counting the initial distribution) is small with 14,306 observations, so BIC usually prefers three states. Whether the extra state is useful (say, for risk management) is best judged out of sample.

student projects

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

1. Regimes in New York City motor-vehicle collisions

question
Do daily collision counts in New York switch between distinct regimes, and are the switches explained by weather, holidays, policy changes (such as speed-camera expansions or the 2020 lockdown) or reporting changes?
data
NYPD Motor Vehicle Collisions – Crashes (NYC Open Data), aggregated to daily counts by borough, 2013 to the present; NOAA daily weather for Central Park and LaGuardia; the city's holiday calendar.
method
Poisson or negative-binomial HMMs with 2–4 states, with and without day-of-week effects; Viterbi paths; comparison of state changes with weather and known events; BIC and out-of-sample likelihood for the number of states.
outcome
A dated list of regime changes in the city's road safety, separating real changes from weather and data artefacts, of direct interest to the Vision Zero programme.

2. The topics of a discipline over time

question
How have the topics of machine-learning research (or of a university's course catalogue) risen and fallen over the last two decades?
data
arXiv metadata with submission dates (the arXiv bulk metadata snapshot), restricted to cs.LG, stat.ML and related categories; alternatively the course descriptions in a university's successive catalogues.
method
LDA and a dynamic topic model; topic coherence to choose \(K\); topic proportions by year with bootstrap intervals; comparison with category labels and with keyword counts as a baseline.
outcome
A data-driven history of the field's topics (for example the rise of deep learning, reinforcement learning and large language models), with an assessment of which trends are robust to the topic model's settings.

Reading and sources

Data. Old Faithful: R datasets::faithful (Rdatasets copy), as in Lecture 14. Galaxy velocities: R MASS::galaxies, Rdatasets copy on GitHub. Daily market excess returns: Kenneth R. French Data Library (Dartmouth), copy of F-F_Research_Data_5_Factors_2x3_daily to April 2020 from github.com/omartinsky/FamaFrench, used because the library was not reachable. arXiv abstracts: S. Rakshit and S. Paul, github.com/soumik12345/multi-label-text-classification (release v0.2), used because the arXiv API was not reachable; it has no dates.

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