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
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.
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).
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.
Start from initial parameters and repeat until the log-likelihood stops increasing:
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)].$$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.
# 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.
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.
# 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.
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?
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.
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\)
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:
reg_covar in scikit-learn) or uses a prior.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.
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.
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.
# 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%
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).
How many free parameters does a one-dimensional Gaussian mixture with \(K=3\) components have?
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.
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.
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\)
# 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\).
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.
# 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.
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.
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.
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.
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.
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.
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.
# 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
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.
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?
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.
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).
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.
# 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).
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.
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.
# 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.
Which statement about the E-step is correct?
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.
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.
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.
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\).
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.
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.)
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.
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.
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.
Each uses this lecture's methods and public data, and has a clear result.
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)