14  EM Algorithm and Factor Analysis

Lecture 14

Keywords

EM algorithm, mixture of Gaussians, factor analysis, multivariate Gaussian, coordinate ascent

Based on the lecture by Andrew Ng — CS229, Stanford University, Autumn 2018.

Factor analysis is a density model for data with many more dimensions than examples. For example, a hundred temperature sensors give a hundred-dimensional reading, but you may have only thirty days of data. An ordinary Gaussian cannot be fitted to such data, because its maximum-likelihood covariance is singular. The model assumes that each observation is a low-dimensional hidden cause zz, mapped linearly into the high-dimensional space, plus independent noise in every coordinate. Because zz is hidden, the model is fitted with EM, and doing so means working out the conditional distributions of a joint Gaussian.

The lecture first closes off the previous one. It shows how the abstract E- and M-steps of Section 13.7 become code for the mixture of Gaussians, and it recasts EM as coordinate ascent. It then spends the rest of the hour on factor analysis.

14.1 From the general algorithm to the mixture updates

3:00 The general M-step says to maximise the lower bound over θ\theta with the QiQ_i held fixed. For the mixture of Gaussians, Qi(z(i)=j)Q_i(z^{(i)} = j) is the responsibility wj(i)=p(z(i)=j∣x(i);ϕ,μ,Σ)w^{(i)}_j = p(z^{(i)} = j \mid x^{(i)}; \phi, \mu, \Sigma) that the E-step computes and stores. The joint density factorises as p(x(i)∣z(i)=j) p(z(i)=j)=N(x(i);μj,Σj) ϕjp(x^{(i)} \mid z^{(i)} = j)\,p(z^{(i)} = j) = \mathcal{N}(x^{(i)}; \mu_j, \Sigma_j)\,\phi_j. So the quantity the M-step maximises is a double sum that can be written out in full:

J(ϕ,μ,Σ)=∑i=1m∑j=1kwj(i)log⁡1(2π)n/2∣Σj∣1/2exp⁡ ⁣(−12(x(i)−μj)⊤Σj−1(x(i)−μj)) ϕjwj(i).(14.1) J(\phi, \mu, \Sigma) = \sum_{i=1}^m \sum_{j=1}^k w^{(i)}_j \log \frac{\dfrac{1}{(2\pi)^{n/2} |\Sigma_j|^{1/2}} \exp\!\Bigl(-\tfrac12 (x^{(i)} - \mu_j)^\top \Sigma_j^{-1} (x^{(i)} - \mu_j)\Bigr)\,\phi_j}{w^{(i)}_j} . \tag{14.1}

Ng’s point is that this objective is what gives you the updates. The rule “move each mean to the weighted average of the points” was an intuition in the last lecture, and here it is derived. Differentiating Equation 14.1 with respect to μj\mu_j and setting the result to zero gives

μj=∑iwj(i)x(i)∑iwj(i), \mu_j = \frac{\sum_i w^{(i)}_j x^{(i)}}{\sum_i w^{(i)}_j},

and the same procedure gives Σj\Sigma_j.

For ϕ\phi, “differentiate and set to zero” does not quite work, and the board skips over why. The only terms in ϕ\phi are ∑i∑jwj(i)log⁡ϕj\sum_i \sum_j w^{(i)}_j \log \phi_j, whose derivative with respect to ϕj\phi_j is ∑iwj(i)/ϕj\sum_i w^{(i)}_j / \phi_j. That derivative is positive for every value of ϕj\phi_j, so it never vanishes. Taken alone, the objective wants every ϕj\phi_j to be infinite. What stops it is the constraint ∑jϕj=1\sum_j \phi_j = 1, so the step needs a Lagrange multiplier. With the multiplier, the solution is ϕj=1m∑iwj(i)\phi_j = \frac1m \sum_i w^{(i)}_j. The generator confirms this on a three-component one-dimensional mixture. At the closed-form M-step, the unconstrained derivative equals exactly m=200m = 200 for all three components (the multiplier), and none of 300 random perturbations of (ϕ,μ,σ2)(\phi, \mu, \sigma^2) that stay on the simplex raises JJ.

14:11 Ng then gives a second view of EM that the factor-analysis derivation leans on. Treat the lower bound as a function of both arguments,

J(θ,Q)=∑i∑z(i)Qi(z(i))log⁡p(x(i),z(i);θ)Qi(z(i))  ≤  ℓ(θ)for every θ and Q. J(\theta, Q) = \sum_i \sum_{z^{(i)}} Q_i(z^{(i)}) \log \frac{p(x^{(i)}, z^{(i)}; \theta)}{Q_i(z^{(i)})} \;\le\; \ell(\theta) \quad \text{for every } \theta \text{ and } Q .

The E-step maximises JJ over QQ with θ\theta fixed, and the maximum is the choice that makes J=ℓJ = \ell. The M-step maximises JJ over θ\theta with QQ fixed. EM is therefore coordinate ascent on JJ: it maximises over one block of variables, then the other, and alternates. This view also tells you how to check that an implementation is working. JJ cannot decrease in either step, and since it equals ℓ(θ)\ell(\theta) after every E-step, the log-likelihood you print at each iteration must not decrease either. If it ever goes down, there is a bug. On the mixture above, the generator asserts that J=ℓJ = \ell after each E-step to 10−810^{-8}, and that ℓ\ell never falls over 40 iterations: from −544.2-544.2 it reaches −388.9-388.9 after three iterations and −358.1-358.1 at the end.

When zz is continuous, as it will be in factor analysis, every step of the derivation in Section 13.7 goes through with the sum over z(i)z^{(i)} replaced by an integral. Jensen’s inequality does not care which kind of expectation it is applied to.

14.2 Fewer examples than dimensions

17:46 A mixture of Gaussians suits data like Ng’s two-dimensional picture with a hundred points: m≫nm \gg n, and each cluster has plenty of points to estimate its covariance. Factor analysis is for the opposite regime, where m≈nm \approx n or m≪nm \ll n. Ng’s running example is a Stanford PhD student’s project with temperature sensors placed around campus buildings: a hundred sensors and thirty days of readings, so n=100n = 100 and m=30m = 30. The goal was anomaly detection by density estimation, as in Section 13.3. A window left open on a winter day produces a reading with low p(x)p(x), and in practice the point was saving energy rather than detecting fires. To do this you need a joint density over all hundred sensors, because neighbouring sensors are strongly correlated, and you have thirty examples to fit it with.

22:01 The obvious model is a single Gaussian with its maximum-likelihood estimates μ=1m∑ix(i)\mu = \frac1m \sum_i x^{(i)} and Σ=1m∑i(x(i)−μ)(x(i)−μ)⊤\Sigma = \frac1m \sum_i (x^{(i)} - \mu)(x^{(i)} - \mu)^\top. If m≤nm \le n, this Σ\Sigma is singular. The reason is that it is a sum of mm rank-one matrices whose vectors x(i)−μx^{(i)} - \mu sum to zero, so its rank is at most m−1m - 1. The generator checks the exact statement on random data for n=2,5,10n = 2, 5, 10 and every mm from 2 to n+2n + 2: the rank is min⁡(m−1,n)\min(m - 1, n), so the estimate is invertible exactly when m≥n+1m \ge n + 1. A singular Σ\Sigma breaks the density in two ways. The normaliser contains ∣Σ∣1/2=0|\Sigma|^{1/2} = 0 and the exponent contains Σ−1\Sigma^{-1}, which does not exist, so evaluating p(x)p(x) gives 0/00/0 at best. Ng’s picture with m=n=2m = n = 2 shows the second problem (Figure 14.1, first panel). The fitted Gaussian has its contours squashed to zero width along the segment joining the two points. All of its probability mass lies on that line, so any test point slightly off the line gets density zero. That is a numerical failure, and it is also a bad model of the data.

Figure 14.1: Maximum-likelihood Gaussians on two-dimensional data, with the one- and two-standard-deviation contours. With two points (left) the full covariance is singular and the Gaussian collapses onto the line through them. With twelve strongly correlated points (sample correlation 0.93) the full covariance follows the tilt of the data, the diagonal covariance gives axis-aligned ellipses that miss it, and the spherical covariance gives circles.

26:53 Ng adds that one of the earliest applications of factor analysis had the same shape: psychological testing, with a hundred questionnaire items and thirty subjects, where the question is how attributes like verbal and mathematical ability are correlated.

14.3 Restricting the covariance

28:15 One way out is to fit fewer parameters. If Σ\Sigma is constrained to be diagonal, the maximum-likelihood estimate is what you would guess: each feature gets its own sample variance, Σjj=1m∑i(xj(i)−μj)2\Sigma_{jj} = \frac1m \sum_i (x^{(i)}_j - \mu_j)^2. That makes nn parameters in place of about n2/2n^2/2, and they can be fitted from any m≥2m \ge 2. The contours are axis-aligned ellipses. The price is that the model assumes the features are uncorrelated, and for a hundred sensors in one room that is plainly false (Figure 14.1, third panel).

31:36 A stronger restriction is Σ=σ2I\Sigma = \sigma^2 I, with one parameter and circular contours. Its estimate is the average squared deviation over every coordinate of every example, which is the mean of the diagonal model’s nn variances. A student asks why anyone would bother with a model that is worse still. Ng’s answer is that it is a building block: factor analysis uses a diagonal covariance for its noise, not for the data.

34:38 Another student asks about the standard fix, a Wishart prior on Σ\Sigma. In practice this means adding a constant λ\lambda to the diagonal of the maximum-likelihood estimate. Ng’s verdict is that it removes the singularity “in a technical way” but is not the best model for many data sets. The generator puts that verdict to a test at the end of the chapter (Section 14.6). What Ng wants instead is a model that captures the main correlations, such as the room warming and cooling as a whole or one side heating up under the lamps, without paying for a full covariance matrix.

He follows this with an aside about small data that is worth keeping. The large technology companies, he says, all work on the same few big-data problems (translation, speech, face recognition), while many real applications in healthcare and manufacturing have a hundred or a thousand examples. The best algorithm for a thousand examples is often not the best for a million, and the field does not yet know how to make one algorithm work along the whole range. He mentions using a modified factor analysis on a manufacturing problem that same week.

14.4 The factor analysis model

40:32 Like the mixture of Gaussians, the model is a joint density p(x,z)=p(x∣z) p(z)p(x, z) = p(x \mid z)\,p(z) with zz hidden. This time zz is continuous and of lower dimension than xx:

z∼N(0,I),z∈Rd, d<n,x=μ+Λz+ε,ε∼N(0,Ψ),(14.2) \begin{aligned} z &\sim \mathcal{N}(0, I), \qquad z \in \mathbb{R}^d,\ d < n, \\ x &= \mu + \Lambda z + \varepsilon, \qquad \varepsilon \sim \mathcal{N}(0, \Psi), \end{aligned} \tag{14.2}

with zz and ε\varepsilon independent. The parameters are the mean μ∈Rn\mu \in \mathbb{R}^n, the factor loading matrix Λ∈Rn×d\Lambda \in \mathbb{R}^{n \times d}, and a diagonal Ψ∈Rn×n\Psi \in \mathbb{R}^{n \times n}. Equivalently, x∣z∼N(μ+Λz,Ψ)x \mid z \sim \mathcal{N}(\mu + \Lambda z, \Psi).

43:30 Ng’s reading of the model uses the room. Suppose three strong forces drive the temperatures in the room: the temperature outside, the lights on the left side, and the lights on the right. Then d=3d = 3, and zz holds those three numbers. Each sensor reads a linear combination of the three, weighted by where it sits, so a sensor near the door leans on the outdoor term. On top of that each sensor adds noise of its own, such as a gust of wind or a bad thermistor. The assumption that Ψ\Psi is diagonal says that this noise is independent across sensors once the shared factors are accounted for. All correlation between sensors has to come through Λz\Lambda z.

46:21 The lecture’s example makes this concrete with d=1d = 1, n=2n = 2, m=7m = 7, Λ=(2,1)⊤\Lambda = (2, 1)^\top, μ=0\mu = 0 and Ψ=diag⁡(1,2)\Psi = \operatorname{diag}(1, 2) (Figure 14.2). Seven draws of zz fall on the real line. Multiplying by Λ\Lambda places them on the line x2=x1/2x_2 = x_1 / 2 in the plane. Around each of these points, the noise ε\varepsilon has axis-aligned elliptical contours, taller than wide in the ratio 2:1\sqrt2 : 1. Drawing one sample from each gives the observed points. Only those crosses are data. The zz values, and the points on the line, are latent.

Figure 14.2: The factor-analysis model as a generative process, with the lecture’s parameters. Seven draws of zz (left) map through Λz+μ\Lambda z + \mu onto a line in the plane (centre). Independent axis-aligned noise with covariance Ψ\Psi moves each one to the observed xx, the crosses (right). The thin lines join each latent point to its observation.

51:05 Ng repeats the construction with d=2d = 2 and n=3n = 3, carrying the five sampled zz points on a sheet of cardboard and holding it up into three-dimensional space. The data then lie close to a two-dimensional “pancake” in R3\mathbb{R}^3, with some fuzz off it. Factor analysis takes data in a hundred dimensions and models it as lying near a three-dimensional subspace, plus independent noise in each coordinate. 54:57 Asked what happens when the data do not lie near a subspace, he concedes that the model is then not the best one. He adds that in a hundred dimensions you rarely know, because you cannot look.

14.5 Marginals and conditionals of Gaussians

56:43 Fitting the model needs two facts about multivariate Gaussians. Partition a Gaussian vector into blocks x1∈Rrx_1 \in \mathbb{R}^r and x2∈Rsx_2 \in \mathbb{R}^s:

[x1x2]∼N ⁣([μ1μ2],[Σ11Σ12Σ21Σ22]). \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \sim \mathcal{N}\!\left( \begin{bmatrix} \mu_1 \\ \mu_2 \end{bmatrix}, \begin{bmatrix} \Sigma_{11} & \Sigma_{12} \\ \Sigma_{21} & \Sigma_{22} \end{bmatrix} \right).

The first fact is that the marginal of x1x_1 is N(μ1,Σ11)\mathcal{N}(\mu_1, \Sigma_{11}). You can prove it by integrating x2x_2 out of the joint density, but the result is the obvious one: the mean and covariance of x1x_1 are the corresponding blocks. The second fact is that the conditional is also Gaussian,

x1∣x2∼N(μ1∣2,Σ1∣2),μ1∣2=μ1+Σ12Σ22−1(x2−μ2),Σ1∣2=Σ11−Σ12Σ22−1Σ21.(14.3) x_1 \mid x_2 \sim \mathcal{N}\bigl(\mu_{1|2}, \Sigma_{1|2}\bigr), \qquad \mu_{1|2} = \mu_1 + \Sigma_{12} \Sigma_{22}^{-1} (x_2 - \mu_2), \qquad \Sigma_{1|2} = \Sigma_{11} - \Sigma_{12} \Sigma_{22}^{-1} \Sigma_{21} . \tag{14.3}

This one is less obvious, and the lecture states it without proof. The conditional mean is a linear regression of x1x_1 on x2x_2. The conditional covariance does not depend on the value of x2x_2 that was observed.

1:02:32 Applying this to factor analysis starts with the observation that (z,x)(z, x) is jointly Gaussian, since xx is a linear function of the Gaussians zz and ε\varepsilon. Its mean is (0,μ)(0, \mu). Ng derives the lower-right block of the covariance and leaves the others to the notes. Expanding

E[(x−μ)(x−μ)⊤]=E[(Λz+ε)(Λz+ε)⊤]=Λ E[zz⊤] Λ⊤+E[εε⊤]=ΛΛ⊤+Ψ. \mathbb{E}\bigl[(x - \mu)(x - \mu)^\top\bigr] = \mathbb{E}\bigl[(\Lambda z + \varepsilon)(\Lambda z + \varepsilon)^\top\bigr] = \Lambda\,\mathbb{E}[z z^\top]\,\Lambda^\top + \mathbb{E}[\varepsilon \varepsilon^\top] = \Lambda \Lambda^\top + \Psi .

Here the cross terms vanish because zz and ε\varepsilon are independent with mean zero. The same expansion gives E[z(x−μ)⊤]=Λ⊤\mathbb{E}[z (x - \mu)^\top] = \Lambda^\top, so

[zx]∼N ⁣([0μ],[IΛ⊤ΛΛΛ⊤+Ψ]).(14.4) \begin{bmatrix} z \\ x \end{bmatrix} \sim \mathcal{N}\!\left( \begin{bmatrix} 0 \\ \mu \end{bmatrix}, \begin{bmatrix} I & \Lambda^\top \\ \Lambda & \Lambda\Lambda^\top + \Psi \end{bmatrix} \right). \tag{14.4}

For the lecture’s example, Equation 14.4 gives the covariance of (z,x1,x2)(z, x_1, x_2) as rows (1,2,1)(1, 2, 1), (2,5,2)(2, 5, 2) and (1,2,3)(1, 2, 3). A Monte Carlo estimate from 200,000 samples in the generator agrees to within 0.015 in every entry.

By the marginal rule, x∼N(μ,ΛΛ⊤+Ψ)x \sim \mathcal{N}(\mu, \Lambda\Lambda^\top + \Psi). This explains why the model escapes the singularity: Ψ\Psi is diagonal with positive entries, so ΛΛ⊤+Ψ\Lambda\Lambda^\top + \Psi is positive definite however small mm is. The covariance has nd+nnd + n free parameters: a rank-dd part that carries the correlations, plus a diagonal part. 1:10:09 The log-likelihood ∑ilog⁡N(x(i);μ,ΛΛ⊤+Ψ)\sum_i \log \mathcal{N}(x^{(i)}; \mu, \Lambda\Lambda^\top + \Psi) is perfectly well defined, but setting its gradient to zero has no closed-form solution in Λ\Lambda and Ψ\Psi. That is why the lecture turns to EM.

14.6 EM for factor analysis

1:11:03 In the mixture of Gaussians, QiQ_i was a list of kk numbers. Here z(i)z^{(i)} is continuous, so the question is how to represent QiQ_i in a computer. The answer is that Qi(z(i))=p(z(i)∣x(i))Q_i(z^{(i)}) = p(z^{(i)} \mid x^{(i)}) is Gaussian, by Equation 14.3 applied to Equation 14.4, so it is stored as a mean vector and a covariance matrix:

μz(i)∣x(i)=Λ⊤(ΛΛ⊤+Ψ)−1(x(i)−μ),Σz(i)∣x(i)=I−Λ⊤(ΛΛ⊤+Ψ)−1Λ.(14.5) \mu_{z^{(i)} \mid x^{(i)}} = \Lambda^\top (\Lambda\Lambda^\top + \Psi)^{-1} (x^{(i)} - \mu), \qquad \Sigma_{z^{(i)} \mid x^{(i)}} = I - \Lambda^\top (\Lambda\Lambda^\top + \Psi)^{-1} \Lambda . \tag{14.5}

The generator checks Equation 14.5 against Bayes’ rule applied directly, multiplying the prior on zz by the likelihood of xx on a grid of 12,000 points. For three different observations in the lecture’s example, the two agree to 10−610^{-6} in mean and variance. As the formula says, the posterior variance is the same for every observation: 1/(1+4+12)=0.18181/(1 + 4 + \tfrac12) = 0.1818. In code, the n×nn \times n inverse is avoided with the matrix-inversion lemma, Σz∣x=(I+Λ⊤Ψ−1Λ)−1\Sigma_{z \mid x} = (I + \Lambda^\top \Psi^{-1} \Lambda)^{-1}, which is d×dd \times d.

1:13:39 The M-step derivation is long, and Ng gives only its two tricks. The first is to recognise expectations instead of expanding integrals. The objective contains terms like ∫Qi(z(i)) z(i) dz(i)\int Q_i(z^{(i)})\, z^{(i)}\, dz^{(i)}. Substituting the Gaussian formula for QiQ_i and integrating is the wrong approach. The integral is Ez(i)∼Qi[z(i)]\mathbb{E}_{z^{(i)} \sim Q_i}[z^{(i)}], which is μz(i)∣x(i)\mu_{z^{(i)} \mid x^{(i)}}, already computed in the E-step. 1:18:13 The second is to expand a Gaussian density when a logarithm sits in front of it. Then the log cancels the exponential and leaves a quadratic in the parameters, whose expectation under QiQ_i is again a quadratic that can be maximised in closed form. The resulting update for Λ\Lambda is

Λ=(∑i=1m(x(i)−μ) μz(i)∣x(i)⊤)(∑i=1m[μz(i)∣x(i)μz(i)∣x(i)⊤+Σz(i)∣x(i)])−1,(14.6) \Lambda = \left( \sum_{i=1}^m (x^{(i)} - \mu)\, \mu_{z^{(i)} \mid x^{(i)}}^\top \right) \left( \sum_{i=1}^m \Bigl[ \mu_{z^{(i)} \mid x^{(i)}} \mu_{z^{(i)} \mid x^{(i)}}^\top + \Sigma_{z^{(i)} \mid x^{(i)}} \Bigr] \right)^{-1}, \tag{14.6}

with μ\mu the sample mean. Ψ\Psi is the diagonal of a similar expression, given in the official notes. Equation 14.6 has the form of the normal equations for regressing xx on zz, except that the unknown z(i)z^{(i)} are replaced by their posterior moments. The bracket in the second factor is E[z(i)z(i)⊤]\mathbb{E}[z^{(i)} z^{(i)\top}] under QiQ_i. That is the mean’s outer product plus the posterior covariance, because E[zz⊤]\mathbb{E}[zz^\top] is not E[z] E[z]⊤\mathbb{E}[z]\,\mathbb{E}[z]^\top.

The official notes warn that dropping Σz∣x\Sigma_{z \mid x} here is a common mistake, which treats the posterior mean as if it were the true zz. They do not say what the mistake costs, so the generator runs both versions (Figure 14.3). The data are 30 examples in n=100n = 100 dimensions, drawn from a three-factor model; the sample covariance has rank 29, as Section 14.2 says it must. Correct EM increases ℓ\ell on every one of 200 iterations, from −5744.2-5744.2 at the start to −3254.7-3254.7 after 10 iterations and −3203.0-3203.0 at 200. Over the last 50 iterations it is still gaining 1.3 nats. The shortcut version is deceptive. It climbs faster at first and reaches −3221.0-3221.0 at iteration 4, ahead of the correct algorithm. Then the likelihood falls on every remaining iteration, 196 of 200 in all. Correct EM overtakes it at iteration 38, and the shortcut finishes at −3235.3-3235.3. The shortcut is not coordinate ascent on any bound, so the monitoring rule of Section 14.1 is exactly what catches it: an implementation whose log-likelihood ever decreases has a bug, even if its first few iterations look better than the correct one.

Figure 14.3: EM for factor analysis with n=100n = 100, m=30m = 30, d=3d = 3. Left: training log-likelihood per iteration for the correct M-step and for the shortcut that uses E[z]E[z]⊤\mathbb{E}[z]\mathbb{E}[z]^\top in place of E[zz⊤]\mathbb{E}[zz^\top]. The first few iterations climb from far below and are clipped. The shortcut leads early, then declines on every iteration. Right: average log-likelihood of 300 held-out examples under factor analysis, a full Gaussian with λI\lambda I added to its covariance (with λ\lambda chosen on the test set itself, which favours it), and a diagonal Gaussian.

The same run tests Ng’s remark about the Wishart fix from Section 14.3. On 300 held-out examples, factor analysis scores an average log-likelihood of −129.0-129.0 per example. The full Gaussian with λI\lambda I added scores −138.5-138.5, even though λ\lambda was chosen from a grid using the test set itself, which is an unfair advantage. The diagonal Gaussian scores −198.8-198.8. The comparison does favour factor analysis, because the data were generated from a factor model. What it shows is narrower than “factor analysis is better” in general. When the correlations really are low-rank, adding λI\lambda I makes the covariance invertible without capturing that structure, and the diagonal model throws the correlations away entirely.

NoteIn the official notes

Restrictions on Σ\Sigma, the marginal and conditional formulas with a derivation of the conditional, the joint distribution of (z,x)(z, x), and the full M-step for μ\mu, Λ\Lambda and Ψ\Psi are in cs229-notes9, sections 1 to 4. The mixture-of-Gaussians M-step with the Lagrange multiplier for ϕ\phi, and the coordinate-ascent view of EM, are in cs229-notes8, sections 2 and 3. The EM algorithm for factor analysis was given by Rubin and Thayer (1982).