Lecture notes · Foundations of Deep Learning · Chapter 16

Continuous Latent Variables

Images, sounds and measurements usually vary in far fewer ways than they have coordinates: they lie close to a low-dimensional manifold. A continuous latent variable \(\bz\) describes the position on that manifold, and a conditional distribution \(p(\bx\given\bz)\) adds the scatter around it. This chapter starts with the linear case: principal component analysis (Section 16.1), its probabilistic version and factor analysis, independent component analysis and the Kalman filter (Section 16.2). The evidence lower bound (Section 16.3) gives EM algorithms for all of them, and Section 16.4 replaces the linear map by a neural network, which is the common starting point of the generative models in Chapters 17 to 20.

Ch. 1 Deep learning revolution Ch. 2 Probabilities Ch. 3 Standard distributions Ch. 4 Regression Ch. 5 Classification Ch. 6 Deep neural networks Ch. 7 Gradient descent Ch. 8 Backpropagation Ch. 9 Regularization Ch. 10 Convolutional networks Ch. 11 Structured distributions Ch. 12 Transformers Ch. 13 Graph neural networks Ch. 14 Sampling Ch. 15 Discrete latent variables Ch. 16 Continuous latent variables Ch. 17 GANs Ch. 18 Normalizing flows Ch. 19 Autoencoders Ch. 20 Diffusion models Appendices A to C

How to read these notes

They follow the book. Sections carry the book's numbers (16.1, 16.2.3, ...) and every displayed equation that appears in the book carries the book's own equation number, e.g. (16.46). Equations without a number are steps that the book skips.

Filling the gaps. Wherever the book states a result without proof, says it "can be shown", or leaves it to an exercise, an orange Filling the gap box or a proof gives the full argument. Proofs start hidden: open one with its bar, or use the button below.

Figures and demonstrations. Twelve of the fifteen figures are reproduced by the Python code, four of them (16.2, 16.7, 16.11, 16.15) computed from explicit data or densities where the book draws a schematic. Figures 16.8, 16.9 and 16.12 are graphical-model drawings with no data and are not reproduced. Seven supplementary figures (16.S1 to 16.S7, our own) illustrate the gaps that are filled. The ▶ Demo boxes open an interactive demonstration already set to the case being discussed.

Main reference

C. M. Bishop and H. Bishop, Deep Learning: Foundations and Concepts, Springer (2024), Chapter 16, pages 495–531. Section, equation, figure and exercise numbers below refer to this book. Further reading is listed in the references; the book's website is www.bishopbook.com. There is no official solution for the exercises of this chapter; all solutions below are my own.

The explanations, derivations, figures and code are my own; equations are cited by their numbers in the book.

Companion course: Bayesian and Probabilistic Machine Learning

Sections 16.1 to 16.3 retell Chapter 12 of Bishop (2006), which the companion course Bayesian and Probabilistic Machine Learning covers in full. Here the results shared with that chapter are stated with a short proof and a link to the complete derivation; what this book adds or presents differently (the evidence lower bound as the bridge to variational autoencoders, the nonlinear latent variable model and the cost of its likelihood, dequantisation, the eigen-digits, and a closer look at the prior in independent component analysis) is treated in full.

The chapter at a glance

  • 16.1 The \(M\)-dimensional subspace that keeps the most variance and the one that loses the least squared error are the same: the span of the \(M\) leading eigenvectors of the covariance \(\bS\), with error equal to the sum of the discarded eigenvalues (Results 16.1, 16.2). For \(N<D\) the eigenvectors come from an \(N\times N\) matrix (Result 16.4).
  • 16.2 Probabilistic PCA is the linear-Gaussian model \(\bx=\bW\bz+\bmu+\beps\); its likelihood is maximised in closed form by the principal eigenvectors, and every other eigenvector choice is a saddle point (Result 16.6). Factor analysis replaces \(\sigma^2\bI\) by a diagonal \(\bPsi\). Both are invariant to rotations of \(\bz\); independent component analysis removes the rotation with a non-Gaussian prior, and the prior's tails must match the sources' (Result 16.10). The Kalman filter chains the latent variables in time (Result 16.11).
  • 16.3 For any \(q(\bz)\), \(\ln p(\bx)\)\({}=\L(q)+\KL(q\Vert p(\bz\given\bx))\) (Result 16.12); EM alternates the two ways of raising \(\L\). For PPCA and factor analysis each step is closed form and costs \(O(NDM)\); in the zero-noise limit EM is subspace iteration (Result 16.14).
  • 16.4 With \(\bx=\bg(\bz,\bw)+\beps\) the likelihood is an intractable integral. Estimating it from \(K\) prior samples (16.83) is unbiased, but \(K\) must grow like \(\sigma^{-M}\) (Result 16.15), which is why the next chapters learn a posterior approximation (VAEs), make \(\bg\) invertible (flows), drop the likelihood (GANs) or denoise step by step (diffusion). Dequantisation turns a density on discretised data into a lower bound on a proper discrete likelihood (Result 16.16).

Notation. \(\bx\in\R^D\) is an observation, \(\bz\in\R^M\) a latent variable, \(N\) the number of data points, \(\bxbar\) the sample mean and \(\bS\) the sample covariance with divisor \(N\) (16.3); \(\lambda_1\ge\dots\ge\lambda_D\) and \(\bu_1,\dots,\bu_D\) are its eigenvalues and orthonormal eigenvectors, \(\bU_M=(\bu_1,\dots,\bu_M)\), \(\bL_M=\diag(\lambda_1,\dots,\lambda_M)\). In probabilistic PCA, \(\bC=\bW\bW^\T+\sigma^2\bI\) and \(\bM=\bW^\T\bW+\sigma^2\bI\) (an \(M\times M\) matrix, not the integer \(M\)). \(\L(q,\bw)\) is the evidence lower bound (ELBO).

Printings. The first printing has a few slips in this chapter (the size of an MNIST image, a missing square root in the scaling of \(\bW_{\rm ML}\), the definition of "missing at random", a typo in Exercise 16.17); each is flagged where it occurs and listed with the evidence in the summary before the exercises.

Derivations start hidden: click any bar to open one.

See also the companion course, Chapter 12 introduction (data near a low-dimensional manifold), and Section 6.1.3 of these notes (data manifolds).

pp. 495–496 Take one handwritten digit, enlarge it, and paste copies into a larger blank field, each copy rotated and shifted at random (Figure 16.1). Every image is a point in a space with one coordinate per pixel (here \(100\times100=10\,000\)), yet the whole collection is described by three numbers: an angle and two shifts. These are latent variables: they generated the data but are not recorded with it. The set of possible images is a three-dimensional manifold in pixel space, and it is curved: as the digit slides past a pixel, that pixel goes from blank to dark and back, which is not a linear function of the shift. Real digits have more degrees of freedom (stroke width, slant, writing style) but still far fewer than pixels, and real data are not exactly on a manifold, so the departures are modelled as noise. This gives the generative picture used throughout the chapter: draw a point on the manifold from a latent distribution, then add noise from a conditional distribution.

Six copies of the same handwritten three in a large white field, each rotated by a different angle between minus 34 and plus 35 degrees and shifted by up to 14 pixels; the angle and shift are printed above each copy.
Figure 16.1 (computed). An MNIST three, enlarged from \(28\times28\) to \(64\times64\) pixels and placed in a \(100\times100\) field with a random rotation (printed in degrees) and a random shift (in pixels). Every image is a point in \(\R^{10\,000}\), but the set of such images has only three degrees of freedom. Reproduces Bishop and Bishop (2024), Figure 16.1. Download: PDF · SVG

(Erratum. The book describes the MNIST digit as a \(64\times64\) image; MNIST images are \(28\times28\), as the book itself says in Figure 16.3. The enlargement above reconciles the two.) How strongly curved this manifold is can be measured with PCA itself: Figure 16.S1 in Section 16.1.5 shows that a linear subspace needs 43 dimensions to hold 90% of the variance of these three-parameter images.

The simplest model takes both the latent distribution and the conditional distribution to be Gaussian, with a mean that depends linearly on \(\bz\) (the linear-Gaussian model of Section 11.1.4 and Section 3.2.6). It leads to probabilistic PCA and factor analysis. We begin with the classical, non-probabilistic PCA.

16.1 Principal Component Analysis

See also the companion course, Section 12.1 (principal component analysis) and its PCA and probabilistic PCA demo.

p. 497 Principal component analysis (PCA) projects the data orthogonally onto a lower-dimensional linear subspace, the principal subspace (Figure 16.2). It serves for dimensionality reduction, lossy compression, feature extraction and visualisation, and is also called the Kosambi–Karhunen–Loève transform. There are two classical definitions: the subspace on which the projected data have the largest variance (Hotelling, 1933), and the subspace that minimises the mean squared distance between the data and their projections (Pearson, 1901). They give the same answer.

Fourteen red data points in the plane, a magenta line through their mean along the direction u1, green dots at the orthogonal projections of the red points onto the line, and blue segments joining each red point to its projection.
Figure 16.2 (computed). Fourteen points (red) and their orthogonal projections (green) onto the first principal direction \(\bu_1\) (magenta line through the mean). The projected points have variance 1.08, the largest eigenvalue \(\lambda_1\) of \(\bS\); the mean squared length of the blue projection errors is 0.13, the other eigenvalue \(\lambda_2\). Reproduces Bishop and Bishop (2024), Figure 16.2. Download: PDF · SVG

16.1.1 Maximum variance formulation

See also the companion course, Section 12.1.1 and Filling the gap 12.1.

pp. 497–498 Let \(\bx_1,\dots,\bx_N\in\R^D\) be the data and fix \(M<D\). For \(M=1\) the subspace is the line spanned by a unit vector \(\bu_1\) (only its direction matters, so we impose \(\bu_1^\T\bu_1=1\)). Point \(\bx_n\) projects to the number \(\bu_1^\T\bx_n\), the projections have mean \(\bu_1^\T\bxbar\) with

\[ \bxbar=\frac1N\sum_{n=1}^N\bx_n, \tag{16.1} \]

and variance

\[ \frac1N\sum_{n=1}^N\big\{\bu_1^\T\bx_n-\bu_1^\T\bxbar\big\}^2=\bu_1^\T\bS\bu_1, \tag{16.2} \] \[ \bS=\frac1N\sum_{n=1}^N(\bx_n-\bxbar)(\bx_n-\bxbar)^\T. \tag{16.3} \]

To maximise \(\bu_1^\T\bS\bu_1\) under the constraint \(\bu_1^\T\bu_1=1\) we introduce a Lagrange multiplier \(\lambda_1\) (Appendix C of the book) and make stationary

\[ \bu_1^\T\bS\bu_1+\lambda_1\big(1-\bu_1^\T\bu_1\big). \tag{16.4} \]

The gradient with respect to \(\bu_1\) is \(2\bS\bu_1-2\lambda_1\bu_1\), so

\[ \bS\bu_1=\lambda_1\bu_1, \tag{16.5} \]

\(\bu_1\) is an eigenvector of \(\bS\), and multiplying by \(\bu_1^\T\),

\[ \bu_1^\T\bS\bu_1=\lambda_1 . \tag{16.6} \]

The projected variance equals the eigenvalue, so the best \(\bu_1\) is the eigenvector of the largest eigenvalue: the first principal component.

Definition 16.1 (principal components and principal subspace) pp. 497–499

Let \(\bS\) be the sample covariance (16.3) with eigenvalues \(\lambda_1\ge\lambda_2\ge\dots\)\({}\ge\lambda_D\ge0\) and orthonormal eigenvectors \(\bu_1,\dots,\bu_D\). The \(i\)th principal component (direction) is \(\bu_i\); the principal subspace of dimension \(M\) is \(\bxbar+\span(\bu_1,\dots,\bu_M)\); the scores of \(\bx\) are \(a_i=\bu_i^\T(\bx-\bxbar)\). If \(\lambda_M=\lambda_{M+1}\) the principal subspace is not unique.

Result 16.1 (maximum variance in \(M\) dimensions) p. 498; Exercise 16.1

For every \(D\times M\) matrix \(\bQ\) with orthonormal columns, \(\Tr(\bQ^\T\bS\bQ)\)\({}\le\lambda_1+\dots+\lambda_M\), with equality when \(\span(\bQ)=\span(\bu_1,\dots,\bu_M)\) (and only then if \(\lambda_M>\lambda_{M+1}\)). So the projection onto an \(M\)-dimensional subspace that keeps the most variance is onto the span of the \(M\) leading eigenvectors, and the variance kept is \(\sum_{i\le M}\lambda_i\).

Proof (short; the full argument is Result 12.2 of the companion course)

Write \(\bS=\sum_i\lambda_i\bu_i\bu_i^\T\). Then \(\Tr(\bQ^\T\bS\bQ)=\sum_i\lambda_ic_i\) with \(c_i=\Vert\bQ^\T\bu_i\Vert^2\). Each \(c_i\in[0,1]\) (the length of a projection of a unit vector), and \(\sum_ic_i=\Tr(\bQ^\T\bQ)=M\). Maximising \(\sum_i\lambda_ic_i\) over such weights puts weight 1 on the \(M\) largest \(\lambda_i\): any weight on a smaller eigenvalue can be moved to a larger one without decreasing the sum. Equality forces \(c_1=\dots=c_M=1\) when \(\lambda_M>\lambda_{M+1}\), i.e. \(\bu_1,\dots,\bu_M\in\span(\bQ)\). ∎

Filling the gap 16.1: the induction of Exercise 16.1, and what it does and does not prove p. 498, "easily shown using proof by induction"

The book builds the components one at a time. The induction step is short, but it proves a greedy statement; Result 16.1 is what shows the greedy answer is also the best \(M\)-dimensional subspace.

Derivation

Induction step. Suppose \(\bu_1,\dots,\bu_M\) are orthonormal eigenvectors of \(\bS\) for \(\lambda_1,\dots,\lambda_M\). We look for a unit vector \(\bu\) orthogonal to all of them that maximises \(\bu^\T\bS\bu\). With multipliers \(\lambda\) for \(\bu^\T\bu=1\) and \(\eta_j\) for \(\bu^\T\bu_j=0\), stationarity of \(\bu^\T\bS\bu+\lambda(1-\bu^\T\bu)\)\({}+\sum_j\eta_j\bu^\T\bu_j\) gives \[ 2\bS\bu-2\lambda\bu+\sum_{j=1}^M\eta_j\bu_j=\bzero . \] Multiply by \(\bu_k^\T\) (\(k\le M\)): \(2\bu_k^\T\bS\bu=2\lambda_k\bu_k^\T\bu=0\) because \(\bS\) is symmetric and \(\bu\perp\bu_k\); the middle term vanishes for the same reason, and \(\bu_k^\T\bu_j=\delta_{kj}\). Hence \(\eta_k=0\) for every \(k\), so \(\bS\bu=\lambda\bu\): \(\bu\) is an eigenvector of \(\bS\) orthogonal to the first \(M\), with variance \(\bu^\T\bS\bu=\lambda\). The largest such \(\lambda\) is \(\lambda_{M+1}\). The base case \(M=1\) is (16.5)–(16.6).

What it shows. The induction proves that choosing directions one after another, each maximising the variance among directions orthogonal to the earlier ones, yields \(\bu_1,\bu_2,\dots\). It does not by itself exclude an \(M\)-dimensional subspace that is not built greedily but keeps more total variance; the trace inequality of Result 16.1 closes that gap, and shows that the greedy and the joint optimum coincide for this objective.

Cost. A full eigendecomposition costs \(O(D^3)\). The power method or Lanczos iterations find the leading \(M\) eigenvectors at \(O(MD^2)\) per sweep once \(\bS\) is formed, and forming \(\bS\) costs \(O(ND^2)\); EM for PCA (Section 16.3.2) avoids \(\bS\) altogether at \(O(NDM)\) per iteration. ∎

Algorithm 16.1 (principal component analysis) p. 498

  1. Compute \(\bxbar\) (16.1) and \(\bS\) (16.3).
  2. Find the \(M\) leading eigenpairs \((\lambda_i,\bu_i)\) of \(\bS\) (or, if \(N<D\), use Result 16.4).
  3. Return the scores \(a_{ni}=\bu_i^\T(\bx_n-\bxbar)\), \(i=1,\dots,M\), and, if wanted, the reconstructions (16.20).

16.1.2 Minimum-error formulation

See also the companion course, Section 12.1.2, Filling the gap 12.2 and Result 12.3.

pp. 499–501 Take a complete orthonormal basis \(\{\bu_i\}_{i=1}^D\),

\[ \bu_i^\T\bu_j=\delta_{ij}. \tag{16.7} \]

Every point has the exact expansion

\[ \bx_n=\sum_{i=1}^D\alpha_{ni}\bu_i, \tag{16.8} \]

and taking inner products with \(\bu_j\) gives \(\alpha_{nj}=\bx_n^\T\bu_j\), so

\[ \bx_n=\sum_{i=1}^D\big(\bx_n^\T\bu_i\big)\bu_i . \tag{16.9} \]

An \(M\)-dimensional approximation keeps \(M\) point-specific coefficients and replaces the others by constants shared by all points:

\[ \bxt_n=\sum_{i=1}^Mz_{ni}\bu_i+\sum_{i=M+1}^Db_i\bu_i , \tag{16.10} \]

and we choose \(\{\bu_i\}\), \(\{z_{ni}\}\) and \(\{b_i\}\) to minimise the distortion

\[ J=\frac1N\sum_{n=1}^N\Vert\bx_n-\bxt_n\Vert^2 . \tag{16.11} \]

The optimal coefficients are

\[ z_{nj}=\bx_n^\T\bu_j\quad(j\le M), \tag{16.12} \] \[ b_j=\bxbar^\T\bu_j\quad(j>M), \tag{16.13} \]

so that

\[ \bx_n-\bxt_n=\sum_{i=M+1}^D\big\{(\bx_n-\bxbar)^\T\bu_i\big\}\bu_i , \tag{16.14} \]

a vector orthogonal to the principal subspace, and

\[ J=\frac1N\sum_{n=1}^N\sum_{i=M+1}^D\big(\bx_n^\T\bu_i-\bxbar^\T\bu_i\big)^2=\sum_{i=M+1}^D\bu_i^\T\bS\bu_i . \tag{16.15} \]

For \(D=2\), \(M=1\), minimising \(J=\bu_2^\T\bS\bu_2\) with a multiplier \(\lambda_2\),

\[ \widetilde J=\bu_2^\T\bS\bu_2+\lambda_2\big(1-\bu_2^\T\bu_2\big), \tag{16.16} \]

gives \(\bS\bu_2=\lambda_2\bu_2\) and \(J=\lambda_2\), smallest when \(\bu_2\) belongs to the smaller eigenvalue. In general the minimum is attained with eigenvectors,

\[ \bS\bu_i=\lambda_i\bu_i , \tag{16.17} \]

and its value is

\[ J=\sum_{i=M+1}^D\lambda_i , \tag{16.18} \]

the sum of the eigenvalues orthogonal to the principal subspace. With \(M=D\) PCA is just a rotation of the axes. Canonical correlation analysis (Hotelling, 1936), mentioned on p. 501, applies the same idea to two sets of variables and leads to a generalised eigenproblem.

Result 16.2 (minimum error; the two definitions agree) pp. 499–501, (16.12)–(16.18); Exercise 16.2

Over all orthonormal bases and all coefficients, the minimum of (16.11) is \(\sum_{i>M}\lambda_i\), attained by the principal subspace of Result 16.1 with \(z_{nj}\) and \(b_j\) as in (16.12)–(16.13). Since \(J=\Tr\bS-\Tr(\bU_M^\T\bS\bU_M)\), minimising the error and maximising the retained variance are the same problem.

Filling the gap 16.2: from (16.10) to (16.15), and the general solution with a matrix of multipliers pp. 499–501; Exercise 16.2

Derivation

The coefficients. Subtract (16.10) from (16.9): \(\bx_n-\bxt_n\)\({}=\sum_{i\le M}(\bx_n^\T\bu_i\)\({}-z_{ni})\bu_i\)\({}+\sum_{i>M}(\bx_n^\T\bu_i-b_i)\bu_i\). By orthonormality (16.7) the squared norm is a sum of squares, \[ J=\frac1N\sum_n\Big[\sum_{i\le M}(\bx_n^\T\bu_i-z_{ni})^2+\sum_{i>M}(\bx_n^\T\bu_i-b_i)^2\Big]. \] Each \(z_{ni}\) appears in one square, minimised by \(z_{ni}=\bx_n^\T\bu_i\) (16.12). Each \(b_i\) appears in \(N\) squares; \(\partial J/\partial b_i\)\({}=-\frac2N\sum_n(\bx_n^\T\bu_i-b_i)=0\) gives the average \(b_i=\bxbar^\T\bu_i\) (16.13). Substituting leaves (16.14) and (16.15), using \(\frac1N\sum_n\{(\bx_n-\bxbar)^\T\bu_i\}^2\)\({}=\bu_i^\T\bS\bu_i\).

The basis. Since \(\sum_{i=1}^D\bu_i^\T\bS\bu_i=\Tr\bS\) for any orthonormal basis, \(J=\Tr\bS-\Tr(\bU_M^\T\bS\bU_M)\), and Result 16.1 gives the minimum \(\Tr\bS-\sum_{i\le M}\lambda_i\)\({}=\sum_{i>M}\lambda_i\).

Exercise 16.2's route. Let \(\widehat\bU\) (\(D\times(D-M)\)) hold the discarded directions and \(\bH\) the multipliers of the constraints \(\widehat\bU^\T\widehat\bU=\bI\): \[ \widetilde J=\Tr\{\widehat\bU^\T\bS\widehat\bU\}+\Tr\{\bH(\bI-\widehat\bU^\T\widehat\bU)\}. \tag{16.87} \] Because \(\bI-\widehat\bU^\T\widehat\bU\) is symmetric, only the symmetric part of \(\bH\) enters, so \(\bH=\bH^\T\) without loss. The gradient \(2\bS\widehat\bU-\widehat\bU(\bH+\bH^\T)\) vanishes when \(\bS\widehat\bU=\widehat\bU\bH\). Multiplying by \(\widehat\bU^\T\) gives \(\bH=\widehat\bU^\T\bS\widehat\bU\). Diagonalise \(\bH=\bPsi\Lambda\bPsi^\T\) with \(\bPsi\) orthogonal; then \(\widetilde\bU=\widehat\bU\bPsi\) satisfies \(\bS\widetilde\bU=\widetilde\bU\Lambda\), so its columns are orthonormal eigenvectors of \(\bS\), and \(J=\Tr\bH=\Tr\Lambda\) is the sum of their eigenvalues. Every stationary point therefore spans an invariant subspace of \(\bS\), its value is a sum of \(D-M\) eigenvalues, and the minimum takes the \(D-M\) smallest. A rotated basis of the same subspace (non-diagonal \(\bH\)) gives the same \(J\), as a direct computation confirms. ∎

16.1.3 Data compression

See also the companion course, Section 12.1.3 (applications of PCA).

pp. 501–502 Each eigenvector is a vector in pixel space, so it can be displayed as an image. Figure 16.3 shows the mean and the first four eigenvectors of 6000 MNIST threes, Figure 16.4 the whole spectrum and the distortion \(J(M)\).

Five 28 by 28 images: the blurred mean three in grey, then four eigen-digits in red and blue showing the stroke variations, with eigenvalues 3.6, 2.7, 2.3 and 1.6 times ten to the five.
Figure 16.3 (computed). PCA of the first 6000 MNIST training threes, grey levels 0 to 255: the mean \(\bxbar\) and the eigenvectors \(\bu_1,\dots,\bu_4\) (red positive, blue negative). Our eigenvalues \(3.6,2.7,2.3,1.6\times10^5\) agree with the book's \(3.4,2.8,2.4,1.6\times10^5\) to within 8%; the exact set of 6000 images differs. Reproduces Bishop and Bishop (2024), Figure 16.3. Download: PDF · SVG
Left: the eigenvalues of the threes in decreasing order, falling steeply from 3.6 times ten to the five and reaching zero after about 540. Right: the sum of discarded eigenvalues J against M, falling from 2.9 million to zero.
Figure 16.4 (computed). (a) The eigenvalue spectrum of the threes. Only 544 of the 784 eigenvalues are non-zero: some border pixels are blank in every image. (b) The distortion \(J(M)=\sum_{i>M}\lambda_i\) (16.18), which starts at \(\Tr\bS=2.92\times10^6\). Reproduces Bishop and Bishop (2024), Figure 16.4. Download: PDF · SVG

Substituting (16.12) and (16.13) into (16.10), the approximation of a data point is

\[ \bxt_n=\sum_{i=1}^M(\bx_n^\T\bu_i)\bu_i+\sum_{i=M+1}^D(\bxbar^\T\bu_i)\bu_i \tag{16.19} \] \[ \phantom{\bxt_n}=\bxbar+\sum_{i=1}^M\big(\bx_n^\T\bu_i-\bxbar^\T\bu_i\big)\bu_i , \tag{16.20} \]

where we used completeness in the form

\[ \bxbar=\sum_{i=1}^D\big(\bxbar^\T\bu_i\big)\bu_i . \tag{16.21} \]

Each point is stored as \(M\) numbers \(a_{ni}=(\bx_n-\bxbar)^\T\bu_i\) instead of \(D\); the mean and the \(M\) eigenvectors are stored once.

A handwritten three and four reconstructions: with one component it is a blurred generic three, with 10 the shape appears, with 50 the strokes are sharp, with 250 it is nearly identical to the original; squared errors 18.9, 7.6, 3.0 and 0.2 times ten to the five are printed below.
Figure 16.5 (computed). A training three and its reconstructions (16.20) with \(M=1,10,50,250\) components; the squared errors are \(18.9,7.6,3.0\) and \(0.2\times10^5\). With \(M=784\) the reconstruction would be exact. Reproduces Bishop and Bishop (2024), Figure 16.5. Download: PDF · SVG
▶ DemoEigen-digits: reconstruct a three from \(M\) componentsSlide \(M\) from 0 to 250 and watch the reconstruction, the residual, the coefficients and the error curve; presets 1 to 4 are the four panels of Figure 16.5.

Filling the gap 16.3: the error of one image, and why reconstruction error is a weak novelty score pp. 501–503, (16.18)–(16.21)

(16.18) is an average over the training set. For a single image, and for an image that is not a three, the error behaves differently.

Derivation

One image. Let \(\bx\) be any image with scores \(a_i=\bu_i^\T(\bx-\bxbar)\), \(i=1,\dots,D\). By (16.14) and orthonormality, \[ \Vert\bx-\bxt\Vert^2=\sum_{i>M}a_i^2=\Vert\bx-\bxbar\Vert^2-\sum_{i\le M}a_i^2 , \] a decreasing function of \(M\) that reaches 0 at \(M=D\). Averaging over the training images, \(\frac1N\sum_na_{ni}^2=\bu_i^\T\bS\bu_i\)\({}=\lambda_i\), which gives back (16.18). Each image's curve can lie above or below \(J(M)\); for the three of Figure 16.5 it lies close to it.

A different digit. For an image from another class, the scores along the leading eigenvectors are not where they would be for a three, and \(\Vert\bx-\bxbar\Vert^2\) is larger. In the demo, a 7 seen through the eigenvectors of threes has, at \(M=20\), an error 2.2 times the training average \(J(20)\), while test threes have 0.56 to 0.91 times. But one test three, written unusually, also has 2.1 times, and as \(M\to D\) every image is rebuilt exactly. Reconstruction error measures only the distance to the subspace; a probabilistic model (Section 16.2) adds how far along the subspace the point lies, in units of \(\sqrt{\lambda_i}\). The probabilistic PCA log density of the 7 is \(-5.61\) nats per pixel against \(-4.8\) to \(-5.0\) for most test threes (and \(-5.58\) for the unusual one). ∎

▶ DemoA 7 through the eyes of the threesThe reconstruction error and the probabilistic PCA log likelihood of other digits, compared with those of threes.

16.1.4 Data whitening

See also the companion course, Result 12.4 (whitening) and the whitening view of its PCA demo.

pp. 502–504 PCA is also a pre-processing step. Variables in different units or with very different spreads (in the Old Faithful data the waiting time is about twenty times the eruption duration) are often standardised to zero mean and unit variance; the covariance of the standardised data is the correlation matrix

\[ \rho_{ij}=\frac1N\sum_{n=1}^N\frac{(x_{ni}-\overline x_i)}{\sigma_i}\frac{(x_{nj}-\overline x_j)}{\sigma_j}, \tag{16.22} \]

with \(\rho_{ij}=\pm1\) for perfectly (positively or negatively) correlated variables and 0 for uncorrelated ones. PCA goes further and removes the correlations. Collect the eigenvectors as columns of an orthogonal \(\bU\) and the eigenvalues in a diagonal \(\bL\), so that

\[ \bS\bU=\bU\bL , \tag{16.23} \]

and define

\[ \by_n=\bL^{-1/2}\bU^\T(\bx_n-\bxbar). \tag{16.24} \]

Then \(\{\by_n\}\) has zero mean and covariance

\[ \frac1N\sum_{n=1}^N\by_n\by_n^\T=\bL^{-1/2}\bU^\T\bS\bU\bL^{-1/2}=\bL^{-1/2}\bL\bL^{-1/2}=\bI . \tag{16.25} \]

This is whitening or sphering (Figure 16.6). It needs all \(\lambda_i>0\).

Three scatter plots of the 272 Old Faithful eruptions: original units with two clusters stretched along a diagonal; standardised data with the two principal axes drawn in red; whitened data, a cloud with identity covariance.
Figure 16.6 (computed). The Old Faithful data (eruption duration and waiting time, minutes): original, standardised (16.22) with the principal axes drawn over \(\pm\lambda_i^{1/2}\), and whitened (16.24). The correlation is \(\rho=0.90\). Reproduces Bishop and Bishop (2024), Figure 16.6. Download: PDF · SVG

Result 16.3 (whitening and its non-uniqueness) pp. 503–504, (16.23)–(16.25)

If \(\bS\) is non-singular, \(\by_n=\bL^{-1/2}\bU^\T(\bx_n-\bxbar)\) has sample mean \(\bzero\) and sample covariance \(\bI\). For any orthogonal \(\bR\), \(\bR\by_n\) is white as well, and every linear map \(\bA\) with \(\bA\bS\bA^\T=\bI\) has the form \(\bA=\bR\bL^{-1/2}\bU^\T\).

Proof

The mean is \(\bL^{-1/2}\bU^\T(\bxbar-\bxbar)=\bzero\) and the covariance is (16.25). For \(\bR\by_n\) the covariance is \(\bR\bI\bR^\T=\bI\). Conversely, if \(\bA\bS\bA^\T=\bI\), put \(\bR=\bA\bU\bL^{1/2}\); then \(\bR\bR^\T=\bA\bU\bL\bU^\T\bA^\T\)\({}=\bA\bS\bA^\T=\bI\), so \(\bR\) is orthogonal and \(\bA=\bR\bL^{-1/2}\bU^\T\). ∎

The rotation \(\bR\) is exactly what second-order statistics cannot determine, and what independent component analysis (Section 16.2.5) recovers from higher-order statistics.

16.1.5 High-dimensional data

See also the companion course, Section 12.1.4 and Result 12.5.

pp. 504–505 When \(N<D\) (a few hundred images of millions of pixels) the \(N\) centred points span at most \(N-1\) dimensions, at least \(D-N+1\) eigenvalues are zero, and an \(O(D^3)\) eigensolver is wasteful. Let \(\bX\) be the \(N\times D\) centred data matrix with rows \((\bx_n-\bxbar)^\T\), so \(\bS=N^{-1}\bX^\T\bX\) and

\[ \frac1N\bX^\T\bX\bu_i=\lambda_i\bu_i . \tag{16.26} \]

Multiplying by \(\bX\),

\[ \frac1N\bX\bX^\T(\bX\bu_i)=\lambda_i(\bX\bu_i), \tag{16.27} \]

so \(\bv_i=\bX\bu_i\) solves the \(N\times N\) problem

\[ \frac1N\bX\bX^\T\bv_i=\lambda_i\bv_i . \tag{16.28} \]

Conversely, multiplying (16.28) by \(\bX^\T\),

\[ \Big(\frac1N\bX^\T\bX\Big)(\bX^\T\bv_i)=\lambda_i(\bX^\T\bv_i), \tag{16.29} \]

and normalising (for unit \(\bv_i\)),

\[ \bu_i=\frac1{(N\lambda_i)^{1/2}}\bX^\T\bv_i . \tag{16.30} \]

Result 16.4 (PCA through the \(N\times N\) matrix) pp. 504–505, (16.26)–(16.30); Exercise 16.3

  1. \(\bX^\T\bX/N\) and \(\bX\bX^\T/N\) have the same non-zero eigenvalues, with the same multiplicities.
  2. Since the rows of the centred \(\bX\) sum to zero, \(\operatorname{rank}\bX\le\min(N-1,D)\); so \(\bS\) has at least \(D-N+1\) zero eigenvalues when \(N\le D\), and \(\bX\bX^\T\) has the eigenvector \(\mathbf 1\) with eigenvalue 0.
  3. If \(\bv_i\) is a unit eigenvector of \(\bX\bX^\T/N\) with \(\lambda_i>0\), (16.30) is a unit eigenvector of \(\bS\). The cost is \(O(N^2D)\) to form \(\bX\bX^\T\), \(O(N^3)\) to diagonalise it and \(O(NDM)\) to map back.
Proof (short; full version in Result 12.5)

(1) From the singular value decomposition \(\bX=\sum_k s_k\mathbf a_k\mathbf b_k^\T\): \(\bX^\T\bX\)\({}=\sum_ks_k^2\mathbf b_k\mathbf b_k^\T\) and \(\bX\bX^\T\)\({}=\sum_ks_k^2\mathbf a_k\mathbf a_k^\T\). (2) \(\mathbf 1^\T\bX=\sum_n(\bx_n-\bxbar)^\T\)\({}=\bzero^\T\), so the \(N\) rows are linearly dependent and \(\bX\bX^\T\mathbf 1=\bX(\bX^\T\mathbf1)\)\({}=\bzero\). The null space of \(\bS\) has dimension \(D-\operatorname{rank}\bX\ge D-N+1\). (3) By (16.29) \(\bX^\T\bv_i\) is an eigenvector, and \(\Vert\bX^\T\bv_i\Vert^2\)\({}=\bv_i^\T\bX\bX^\T\bv_i\)\({}=N\lambda_i\bv_i^\T\bv_i=N\lambda_i\), which is the factor in (16.30) (Exercise 16.3). ∎

Applied to 60 threes: 725 eigenvalues of \(\bS\) vanish, and the \(60\times60\) route reproduces the non-zero eigenvalues and unit eigenvectors to \(10^{-8}\).

The \(N\times N\) route is what makes PCA of the \(10\,000\)-pixel images of Figure 16.1 cheap. It answers a question raised in the introduction: how linear is the three-parameter manifold?

Left: eigenvalues of 1500 rotated and shifted copies of a three, decaying smoothly over hundreds of indices on a log scale. Middle: the fraction of variance retained against M, reaching 90 percent at M equals 43 and 99 percent at 202. Right: the first eight eigenvectors as 100 by 100 images, smooth ring-like patterns.
Figure 16.S1 (our own). PCA of 1500 images like those of Figure 16.1 (three degrees of freedom), computed through the \(1500\times1500\) matrix (16.28). A linear subspace needs \(M=43\) components for 90% of the variance and 202 for 99%: the manifold is strongly curved. The leading eigenvectors are smooth, ring-like patterns that encode rotations and shifts only approximately. Download: PDF · SVG

16.2 Probabilistic Latent Variables

See also the companion course, Section 12.2 (probabilistic PCA).

p. 506 The scores \(z_{nj}\) of (16.12) are deterministic latent variables. Recasting PCA as the maximum likelihood solution of a probabilistic latent variable model (Tipping and Bishop, 1997, 1999; Roweis, 1998) brings: a Gaussian whose number of parameters grows only linearly with \(D\) yet captures the main correlations; an EM algorithm that never forms \(\bS\); a principled treatment of missing values; mixtures of PCA models; a likelihood for comparing with other density models (plain PCA gives a small reconstruction cost to points near the subspace however far they are from the data); class-conditional densities for classification; sampling; and Bayesian versions that choose \(M\) (Bishop, 2006; companion Section 12.2.3).

16.2.1 Generative model

See also the companion course, Definition 12.2, and the linear-Gaussian model of Section 11.1.4 of these notes (Gaussian variables in graphical models).

pp. 506–507 Probabilistic PCA is a linear-Gaussian model with

\[ p(\bz)=\N(\bz\given\bzero,\bI), \tag{16.31} \] \[ p(\bx\given\bz)=\N(\bx\given\bW\bz+\bmu,\sigma^2\bI), \tag{16.32} \]

where \(\bW\) is \(D\times M\) and \(\bmu\in\R^D\). The covariance of \(p(\bx\given\bz)\) is diagonal, so the components of \(\bx\) are independent given \(\bz\): a naive Bayes structure (Section 11.2.3; Exercise 16.7). Equivalently,

\[ \bx=\bW\bz+\bmu+\beps,\qquad\beps\sim\N(\bzero,\sigma^2\bI)\ \text{independent of }\bz. \tag{16.33} \]

The map goes from latent space to data space, the reverse of the projection view of Section 16.1; Bayes' theorem will supply the other direction. A general Gaussian prior \(\N(\bz\given\mathbf m,\Sig)\) gives nothing new (Exercise 16.4).

Definition 16.2 (probabilistic PCA) pp. 506–507, (16.31)–(16.33)

Parameters \(\bW\in\R^{D\times M}\), \(\bmu\in\R^D\), \(\sigma^2>0\). Data are generated by drawing \(\bz\sim\N(\bzero,\bI_M)\) and then \(\bx\sim\N(\bW\bz+\bmu,\sigma^2\bI_D)\), independently for each data point (Figure 16.8, a plate diagram, not reproduced).

Left: a red standard normal density p(z) with a blue dot at a sampled value z-hat. Middle: a blue line through mu along w, a point at w z-hat plus mu, and two red circles of the isotropic noise around it. Right: green ellipses of the marginal density of x elongated along w, with grey sample points.
Figure 16.7 (computed). Probabilistic PCA with \(D=2\), \(M=1\), \(\bw=(1,0.75)\), \(\sigma^2=0.12\): draw \(\widehat z\) from \(p(z)\), then \(\bx\) from the isotropic Gaussian (red circles at 1 and 2 standard deviations) centred at \(\bw\widehat z+\bmu\). The marginal \(p(\bx)\) (green, 1 and 2 standard deviations, with 150 samples) is a "pancake" stretched along \(\bw\). Reproduces Bishop and Bishop (2024), Figure 16.7. Download: PDF · SVG

16.2.2 Likelihood function

pp. 507–509 The marginal of \(\bx\) is

\[ p(\bx)=\int p(\bx\given\bz)p(\bz)\,\d\bz \tag{16.34} \]

and, the model being linear-Gaussian,

\[ p(\bx)=\N(\bx\given\bmu,\bC), \tag{16.35} \] \[ \bC=\bW\bW^\T+\sigma^2\bI . \tag{16.36} \]

Directly from (16.33), using the independence of \(\bz\) and \(\beps\):

\[ \E[\bx]=\E[\bW\bz+\bmu+\beps]=\bmu , \tag{16.37} \] \[ \cov[\bx]=\E\big[(\bW\bz+\beps)(\bW\bz+\beps)^\T\big]=\E\big[\bW\bz\bz^\T\bW^\T\big]+\E[\beps\beps^\T] \tag{16.38} \] \[ \phantom{\cov[\bx]}=\bW\bW^\T+\sigma^2\bI . \tag{16.39} \]

The density is like Gaussian ink sprayed from a can moving along the principal subspace. It does not identify \(\bW\): for any orthogonal \(\bR\), \(\widetilde\bW=\bW\bR\) gives

\[ \widetilde\bW\widetilde\bW^\T=\bW\bR\bR^\T\bW^\T=\bW\bW^\T , \tag{16.40} \]

a rotation of latent space. Evaluating the density needs \(\bC^{-1}\); by the Woodbury identity

\[ \bC^{-1}=\sigma^{-2}\bI-\sigma^{-2}\bW\bM^{-1}\bW^\T , \tag{16.41} \] \[ \bM=\bW^\T\bW+\sigma^2\bI , \tag{16.42} \]

which costs \(O(M^3)\) (plus \(O(DM^2)\) to form \(\bM\)) instead of \(O(D^3)\). The posterior, from the linear-Gaussian result (3.100) of Section 3.2.6, is

\[ p(\bz\given\bx)=\N\big(\bz\given\bM^{-1}\bW^\T(\bx-\bmu),\ \sigma^2\bM^{-1}\big); \tag{16.43} \]

its mean depends on \(\bx\), its covariance does not.

Result 16.5 (marginal and posterior of probabilistic PCA) pp. 507–509, (16.35)–(16.43); Exercises 16.4, 16.6, 16.8

  1. \(p(\bx)=\N(\bmu,\bW\bW^\T+\sigma^2\bI)\), invariant under \(\bW\mapsto\bW\bR\) for orthogonal \(\bR\).
  2. \(\bC^{-1}\) is given by (16.41), and \(|\bC|=\sigma^{2(D-M)}|\bM|\).
  3. \(p(\bz\given\bx)\) is (16.43).
  4. A prior \(\N(\mathbf m,\Sig)\) on \(\bz\) gives the same family of marginals, with \(\bW'=\bW\Sig^{1/2}\) and \(\bmu'=\bmu+\bW\mathbf m\).
Proof (short; full version in Result 12.6 of the companion course)

(1) \((\bz,\beps)\) is jointly Gaussian, so \(\bx\), an affine function of it, is Gaussian with the moments (16.37)–(16.39). (2) Woodbury: \((\sigma^2\bI+\bW\bW^\T)^{-1}\)\({}=\sigma^{-2}\bI\)\({}-\sigma^{-2}\bW(\sigma^2\bI\)\({}+\bW^\T\bW)^{-1}\bW^\T\); multiply by \(\bC\) to verify. The determinant follows from \(|\sigma^2\bI_D+\bW\bW^\T|\)\({}=\sigma^{2D}|\bI_M+\sigma^{-2}\bW^\T\bW|\)\({}=\sigma^{2(D-M)}|\bM|\) (Sylvester). (3) The joint of \((\bz,\bx)\) is Gaussian with \(\cov[\bz,\bx]=\bW^\T\); conditioning gives mean \(\bW^\T\bC^{-1}(\bx-\bmu)\) and covariance \(\bI-\bW^\T\bC^{-1}\bW\). With (16.41), \(\bW^\T\bC^{-1}\)\({}=\sigma^{-2}(\bI\)\({}-\bW^\T\bW\bM^{-1})\bW^\T\)\({}=\sigma^{-2}(\bM\)\({}-\bW^\T\bW)\bM^{-1}\bW^\T\)\({}=\bM^{-1}\bW^\T\), and then \(\bI-\bM^{-1}\bW^\T\bW\)\({}=\bM^{-1}(\bM-\bW^\T\bW)\)\({}=\sigma^2\bM^{-1}\). (4) If \(\bz=\mathbf m+\Sig^{1/2}\bz'\) with \(\bz'\sim\N(\bzero,\bI)\), then \(\bW\bz+\bmu\)\({}=\bW\Sig^{1/2}\bz'+(\bmu+\bW\mathbf m)\). ∎

16.2.3 Maximum likelihood

See also the companion course, Section 12.2.1 and Result 12.8 (the full Tipping–Bishop analysis).

pp. 509–513 For data \(\bX=\{\bx_n\}\) the log likelihood is

\[ \ln p(\bX\given\bmu,\bW,\sigma^2)=\sum_{n=1}^N\ln p(\bx_n\given\bW,\bmu,\sigma^2)=-\frac{ND}2\ln(2\pi)-\frac N2\ln|\bC|-\frac12\sum_{n=1}^N(\bx_n-\bmu)^\T\bC^{-1}(\bx_n-\bmu). \tag{16.44} \]

It is a concave quadratic in \(\bmu\) (Hessian \(-N\bC^{-1}\); Exercises 16.9, 16.10), maximised by \(\bmu=\bxbar\), after which

\[ \ln p(\bX\given\bW,\bmu,\sigma^2)=-\frac N2\Big\{D\ln(2\pi)+\ln|\bC|+\Tr\big(\bC^{-1}\bS\big)\Big\}. \tag{16.45} \]

Tipping and Bishop (1999) showed that all stationary points in \(\bW\) have the form

\[ \bW_{\rm ML}=\bU_M(\bL_M-\sigma^2\bI)^{1/2}\bR , \tag{16.46} \]

where the columns of \(\bU_M\) are any \(M\) eigenvectors of \(\bS\), \(\bL_M\) holds their eigenvalues and \(\bR\) is any orthogonal matrix; the maximum takes the \(M\) leading eigenvectors (all other choices are saddle points), and then

\[ \sigma^2_{\rm ML}=\frac1{D-M}\sum_{i=M+1}^D\lambda_i , \tag{16.47} \]

the average variance of the discarded directions. With \(\bR=\bI\), the columns of \(\bW\) are the eigenvectors scaled by \((\lambda_i-\sigma^2)^{1/2}\). (Erratum. The book says "scaled by the variance parameters \(\lambda_i-\sigma^2\)"; the scale factor is the square root, so that the variance contributed along \(\bu_i\) is \(\lambda_i-\sigma^2\).) Along a retained eigenvector the model variance is \(\bu_i^\T\bC\bu_i\)\({}=(\lambda_i-\sigma^2)+\sigma^2=\lambda_i\), exactly the data variance; along any direction \(\bv\) orthogonal to the principal subspace it is \(\bv^\T\bC\bv=\sigma^2\), the average of the discarded eigenvalues. If the likelihood is maximised numerically (conjugate gradients, EM), \(\bR\) is arbitrary and the columns of \(\bW\) need not be orthogonal; they can be orthogonalised afterwards. The continuum of equivalent \(\bR\) is a continuous non-identifiability, the analogue of label switching in mixtures. With \(M=D\) the model reproduces the sample covariance:

\[ \bC=\bU(\bL-\sigma^2\bI)^{1/2}\bR\bR^\T(\bL-\sigma^2\bI)^{1/2}\bU^\T+\sigma^2\bI=\bU\bL\bU^\T=\bS . \tag{16.48} \]

Result 16.6 (maximum likelihood probabilistic PCA; Tipping and Bishop, 1999) pp. 510–511, (16.45)–(16.48)

Assume \(\bS\) is non-singular. Then:

  1. \(\bW\) is a stationary point of (16.45) for fixed \(\sigma^2\) iff \(\bS\bC^{-1}\bW=\bW\), iff \(\bW=\bU_q(\bL_q-\sigma^2\bI)^{1/2}\bR\) for some set \(q\) of eigenvectors with \(\lambda_i\ge\sigma^2\) (columns for which \(\lambda_i=\sigma^2\) are zero, so \(\bW\) may have rank below \(M\)).
  2. For a given set of \(M\) retained eigenvalues, the optimal \(\sigma^2\) is the mean of the others, (16.47).
  3. If a retained eigenvalue \(\lambda_r\) is smaller than a discarded one \(\lambda_d\), the stationary point is a saddle: turning the column for \(\bu_r\) towards \(\bu_d\) increases the likelihood. The global maximum therefore retains \(\lambda_1,\dots,\lambda_M\).

Filling the gap 16.4: why the eigenvectors appear, why only the principal ones give the maximum p. 510, "It was shown by Tipping and Bishop (1999)"

The book quotes the result. Here is a self-contained proof of each part; the companion course's Result 12.8 gives an alternative presentation.

Derivation

Gradient. With \(\d\ln|\bC|=\Tr(\bC^{-1}\d\bC)\), \(\d\bC^{-1}=-\bC^{-1}\d\bC\,\bC^{-1}\) and \(\d\bC=\d\bW\,\bW^\T+\bW\,\d\bW^\T\), \[ \frac{\partial}{\partial\bW}\ln p=N\big(\bC^{-1}\bS\bC^{-1}\bW-\bC^{-1}\bW\big), \] which vanishes iff \(\bS\bC^{-1}\bW=\bW\) (multiply by \(\bC\)).

Solving the stationarity equation. Write the thin SVD \(\bW=\mathbf V\mathbf K\bR^\T\) (\(\mathbf V\): \(D\times M\) orthonormal columns, \(\mathbf K=\diag(k_j)\ge0\)). Then \(\bC\mathbf V\)\({}=\mathbf V\mathbf K^2+\sigma^2\mathbf V\), so \(\bC^{-1}\mathbf V\)\({}=\mathbf V(\mathbf K^2+\sigma^2\bI)^{-1}\) and \(\bC^{-1}\bW\)\({}=\mathbf V(\mathbf K^2\)\({}+\sigma^2\bI)^{-1}\mathbf K\bR^\T\). The equation becomes \(\bS\mathbf v_j\,k_j/(k_j^2+\sigma^2)\)\({}=\mathbf v_jk_j\) for each \(j\). If \(k_j>0\), \(\bS\mathbf v_j\)\({}=(k_j^2+\sigma^2)\mathbf v_j\): \(\mathbf v_j\) is an eigenvector \(\bu_i\) and \(k_j=(\lambda_i-\sigma^2)^{1/2}\), which needs \(\lambda_i\ge\sigma^2\). If \(k_j=0\) the column is zero. This is (16.46).

The noise variance. At such a point \(\bC\) has eigenvectors \(\bu_1,\dots,\bu_D\), with eigenvalue \(\lambda_i\) for the retained ones and \(\sigma^2\) for the others. So \(\ln|\bC|\)\({}=\sum_{\rm ret}\ln\lambda_i+(D\)\({}-M)\ln\sigma^2\) and \(\Tr(\bC^{-1}\bS)\)\({}=M+\sigma^{-2}\sum_{\rm disc}\lambda_j\). Setting the \(\sigma^2\)-derivative of (16.45) to zero, \((D-M)/\sigma^2\)\({}=\sigma^{-4}\sum_{\rm disc}\lambda_j\), which is (16.47). The profile log likelihood is \[ -\frac N2\Big\{D\ln 2\pi+\sum_{\rm ret}\ln\lambda_i+(D-M)\ln\bar\lambda_{\rm disc}+D\Big\}. \]

Saddles. Let \(\lambda_r\) be retained and \(\lambda_d>\lambda_r\) discarded, with \(\lambda_r>\sigma^2\). Replace the column \(k_r\bu_r\) by \(k_r(\cos\epsilon\,\bu_r\)\({}+\sin\epsilon\,\bu_d)\). This rotates \(\bC\) within \(\span(\bu_r,\bu_d)\), so \(\ln|\bC|\) is unchanged. In that plane \(\bC\)\({}=\sigma^2\bI+k_r^2\mathbf v\mathbf v^\T\) with \(\mathbf v\)\({}=\cos\epsilon\,\bu_r+\sin\epsilon\,\bu_d\), \(\bC^{-1}\)\({}=\sigma^{-2}\big(\bI\)\({}-\tfrac{k_r^2}{\lambda_r}\mathbf v\mathbf v^\T\big)\) (since \(k_r^2+\sigma^2=\lambda_r\)), and \(\bS=\diag(\lambda_r,\lambda_d)\). Hence \[ \Tr(\bC^{-1}\bS)=\sigma^{-2}\Big[\lambda_r+\lambda_d-\frac{\lambda_r-\sigma^2}{\lambda_r}\big(\lambda_r\cos^2\epsilon+\lambda_d\sin^2\epsilon\big)\Big]+\text{(other directions)}, \] whose derivative with respect to \(\sin^2\epsilon\) is \(-\sigma^{-2}\frac{\lambda_r-\sigma^2}{\lambda_r}(\lambda_d\)\({}-\lambda_r)\)\({}<0\). The trace falls, so the log likelihood rises: there is an ascent direction, and the point is not a maximum. Since a maximum exists (the log likelihood tends to \(-\infty\) as \(\sigma^2\to0\), \(\sigma^2\to\infty\) or \(\Vert\bW\Vert\to\infty\) when \(\bS\) is non-singular) and must be stationary, it retains the \(M\) largest eigenvalues. (When \(\lambda_M\le\sigma^2_{\rm ML}\) some columns are zero; this cannot happen if \(\lambda_M>\lambda_{M+1}\), since then \(\lambda_M>\bar\lambda_{\rm disc}\).) Numerically one finds a stationary saddle for \(\{\bu_1,\bu_3\}\) and that perturbations of the principal solution never increase the likelihood. ∎

Back to data space. pp. 511–512 Probabilistic PCA maps latent to data space; for visualisation or compression we reverse it with Bayes' theorem. A point \(\bx\) is summarised by its posterior mean

\[ \E[\bz\given\bx]=\bM^{-1}\bW_{\rm ML}^\T(\bx-\bxbar), \tag{16.49} \]

which maps back to

\[ \bW\E[\bz\given\bx]+\bmu \tag{16.50} \]

(a regularised linear regression, as in Section 4.1.6), and by the \(\bx\)-independent posterior covariance \(\sigma^2\bM^{-1}\). As \(\sigma^2\to0\) the posterior mean becomes

\[ (\bW_{\rm ML}^\T\bW_{\rm ML})^{-1}\bW_{\rm ML}^\T(\bx-\bxbar), \tag{16.51} \]

the orthogonal projection of standard PCA (with zero posterior covariance: the density becomes singular). For \(\sigma^2>0\) the latent projection is shrunk towards the origin.

Result 16.7 (the posterior mean shrinks; the best reconstruction undoes it) p. 512, (16.49)–(16.51); Exercises 16.11–16.13

At the ML solution with \(\bR=\bI\), let \(a_j=\bu_j^\T(\bx-\bxbar)\). Then \[ \E[z_j\given\bx]=\frac{(\lambda_j-\sigma^2)^{1/2}}{\lambda_j}a_j,\qquad\text{orthogonal projection (16.51): }\ \frac{a_j}{(\lambda_j-\sigma^2)^{1/2}} , \] so the posterior mean is the projection multiplied by \((\lambda_j-\sigma^2)/\lambda_j\in(0,1)\), tending to 1 as \(\sigma^2\to0\). The reconstruction (16.50) is \(\bxbar\)\({}+\sum_j\frac{\lambda_j-\sigma^2}{\lambda_j}a_j\bu_j\) (shrunk), while the least-squares reconstruction from \(\E[\bz\given\bx]\) is \[ \bxt=\bW_{\rm ML}(\bW_{\rm ML}^\T\bW_{\rm ML})^{-1}\bM\,\E[\bz\given\bx]+\bxbar=\bxbar+\sum_{j\le M}a_j\bu_j , \tag{16.88} \] the PCA reconstruction (16.20).

Proof (short; full version in Result 12.9)

With \(\bW=\bU_M(\bL_M-\sigma^2\bI)^{1/2}\): \(\bW^\T\bW=\bL_M-\sigma^2\bI\), \(\bM=\bL_M\), \(\bW^\T(\bx-\bxbar)\)\({}=(\bL_M-\sigma^2\bI)^{1/2}\mathbf a\). Hence \(\E[\bz\given\bx]\)\({}=\bL_M^{-1}(\bL_M\)\({}-\sigma^2\bI)^{1/2}\mathbf a\) and (16.51) gives \((\bL_M-\sigma^2\bI)^{-1/2}\mathbf a\); their ratio is \((\lambda_j-\sigma^2)/\lambda_j\). For (16.88): minimising \(\Vert\bx-\bxbar-\bW\mathbf c\Vert^2\) over \(\mathbf c\) gives \(\mathbf c\)\({}=(\bW^\T\bW)^{-1}\bW^\T(\bx-\bxbar)\)\({}=(\bW^\T\bW)^{-1}\bM\,\E[\bz\given\bx]\) by (16.49), and \(\bW\mathbf c\) is the orthogonal projection \(\sum_ja_j\bu_j\). (The book's (16.88) omits \(+\bxbar\); it is needed unless \(\bx\) is centred.) ∎

Counting parameters. pp. 512–513 A full covariance has \(D(D+1)/2\) parameters, a diagonal one \(D\) but no correlations. Probabilistic PCA sits between them: \(\bW\) and \(\sigma^2\) have \(DM+1\) entries, of which a rotation \(\bR\) (\(M(M-1)/2\) parameters) is redundant, so the covariance has

\[ DM+1-M(M-1)/2 \tag{16.52} \]

degrees of freedom: linear in \(D\) for fixed \(M\). With \(M=D-1\) this is \(D(D+1)/2\) (a full covariance: \(D-1\) directions from \(\bW\), the last from \(\sigma^2\)); with \(M=0\) it is 1 (isotropic).

Result 16.8 (degrees of freedom of the PPCA and factor analysis covariances) pp. 512–513, (16.52); Exercises 16.14, 16.15

At a generic \((\bW,\sigma^2)\) the Jacobian of the map \((\bW,\sigma^2)\mapsto\bC\) has rank \(DM+1-M(M-1)/2\); for factor analysis \((\bW,\bPsi)\mapsto\bW\bW^\T+\bPsi\) it has rank \(DM+D-M(M-1)/2\) (when this does not exceed \(D(D+1)/2\)).

Proof

The orthogonal \(M\times M\) matrices form a manifold of dimension \(M(M-1)/2\): the first column is a unit vector (\(M-1\) free parameters), the second a unit vector orthogonal to it (\(M-2\)), and so on, \(\sum_{k=1}^{M-1}k=M(M-1)/2\); equivalently, its tangent space at \(\bI\) is the space of antisymmetric matrices. The fibre \(\{\bW\bR\}\) of a full-rank \(\bW\) has exactly this dimension, and no other changes of \(\bW\) leave \(\bW\bW^\T\) fixed (if \(\bW\bW^\T=\bW'\bW'^\T\) with \(\bW\) of full column rank, then \(\bW'=\bW\bR\) for an orthogonal \(\bR\)). So the image has dimension \(DM+1-M(M-1)/2\). For \(M=D-1\): \(D(D-1)+1-(D-1)(D-2)/2\)\({}=D(D+1)/2\). For factor analysis the \(D\) entries of \(\bPsi\) replace the single \(\sigma^2\). A direct computation of the numerical rank of the Jacobian gives 16 for \(D=6,M=3\), 14 for \(D=7,M=2\), and 20 for factor analysis with \(D=7,M=2\), as predicted. ∎

16.2.4 Factor analysis

See also the companion course, Section 12.2.4, Result 12.13 and its Bayesian PCA and factor analysis demo.

pp. 513–514 Factor analysis differs from probabilistic PCA only in the noise:

\[ p(\bx\given\bz)=\N(\bx\given\bW\bz+\bmu,\bPsi),\qquad\bPsi\ \text{diagonal}. \tag{16.53} \]

The variables are still independent given \(\bz\); \(\bPsi\) holds the variance specific to each variable (the uniquenesses) and the columns of \(\bW\) (the factor loadings) the shared covariance. The marginal is \(\N(\bx\given\bmu,\bC)\) with

\[ \bC=\bW\bW^\T+\bPsi . \tag{16.54} \]

Lawley (1953) and Anderson (1963) found the stationary points for \(\bPsi=\sigma^2\bI\); Tipping and Bishop (1999) identified the maximum. Unlike PPCA, factor analysis has no closed-form maximum likelihood solution (Section 16.3.3 gives EM). The model is again invariant to rotations of \(\bz\), which made attempts to interpret individual factors controversial; to remove the rotation one needs a non-Gaussian latent distribution (Section 16.2.5).

Definition 16.3 (factor analysis) p. 513, (16.53)–(16.54)

As Definition 16.2 but with \(p(\bx\given\bz)=\N(\bW\bz+\bmu,\bPsi)\), \(\bPsi=\diag(\psi_1,\dots,\psi_D)\), \(\psi_i>0\).

Result 16.9 (how the fits transform) pp. 513–514; Exercises 16.16, 16.17

Let a model have \(p(\bx\given\bz)=\N(\bW\bz+\bmu,\bPhi)\) with \(\bPhi\) in some class, and let \(\bA\) be non-singular. If \((\bmu,\bW,\bPhi)\) maximises the likelihood of \(\{\bx_n\}\), then \((\bA\bmu,\bA\bW,\bA\bPhi\bA^\T)\) maximises the likelihood of \(\{\bA\bx_n\}\), provided \(\bPhi\mapsto\bA\bPhi\bA^\T\) maps the class onto itself. This holds for factor analysis (diagonal \(\bPhi\)) with diagonal \(\bA\) (rescaling each variable), and for PPCA (\(\bPhi=\sigma^2\bI\)) with orthogonal \(\bA\) (rotating the axes). Both models are invariant under \(\bW\mapsto\bW\bR\).

Proof (short; full version in Result 12.13)

If \(\bx\sim\N(\bmu,\bW\bW^\T+\bPhi)\) then \(\bA\bx\sim\N(\bA\bmu,(\bA\bW)(\bA\bW)^\T\)\({}+\bA\bPhi\bA^\T)\), so the log likelihood of the transformed data under the transformed parameters is the original one minus \(N\ln|\det\bA|\), a constant. The parameter map is a bijection of the parameter set whenever it preserves the class of \(\bPhi\): \(\bA\bPsi\bA^\T=\diag(a_i^2\psi_i)\) for diagonal \(\bA\), and \(\bA\sigma^2\bI\bA^\T=\sigma^2\bI\) for orthogonal \(\bA\). A bijection that shifts the objective by a constant maps maximisers to maximisers. Rotation invariance: \(\bW\bR\bR^\T\bW^\T=\bW\bW^\T\). Note that a rescaling of factor-analysis data is absorbed by \(\bPsi\) and by the rows of \(\bW\); the book mentions only \(\bPsi\). A direct computation confirms that every EM iterate of factor analysis on rescaled data is the rescaled iterate, with the log likelihood shifted by exactly \(-N\sum_i\ln a_i\). ∎

16.2.5 Independent component analysis

See also the companion course, Section 12.4.1, Definition 12.4 and Result 12.16.

pp. 514–515 Keep the linear map but make the latent distribution non-Gaussian and factorised:

\[ p(\bz)=\prod_{j=1}^Mp(z_j). \tag{16.55} \]

The motivating problem is blind source separation (Cardoso, 1998): two people talk at once and two microphones record different linear combinations of their voices (ignoring delays and echoes). Neither the voices nor the mixing coefficients are observed; if the mixing is learned and is invertible, it can be undone. Treating the time samples as independent (MacKay, 2003), the model has two latent sources and two observed signals, \(\bx=\bA\bz\), with no noise term: since \(M=D\), the distribution of \(\bx\) is non-singular. The log likelihood is a function of the mixing coefficients and can be maximised by gradient methods. This needs non-Gaussian sources: with a Gaussian \(p(\bz)\), \(\bW\) and \(\bW\bR\) give the same likelihood (16.40), and decorrelating the data (PCA) gives independence only for Gaussians, since zero correlation is necessary but not sufficient for independence. A common choice is

\[ p(z_j)=\frac1{\pi\cosh(z_j)}=\frac2{\pi(e^{z_j}+e^{-z_j})}, \tag{16.56} \]

whose tails, \(\propto e^{-|z|}\), are heavier than a Gaussian's; it has variance \(\pi^2/4\) and excess kurtosis 2. The original ICA algorithm maximised information transfer (Bell and Sejnowski, 1995); the probabilistic view leads to extensions such as independent factor analysis (Attias, 1999), with noise, unequal numbers of sources and sensors, and mixture-of-Gaussian sources.

Definition 16.4 (noise-free square ICA) p. 514

Sources \(\bz\in\R^D\) with independent components, \(p(\bz)=\prod_jp_j(z_j)\); observations \(\bx=\bA\bz\) with \(\bA\) a non-singular \(D\times D\) mixing matrix. The unmixing matrix is \(\bW=\bA^{-1}\) with rows \(\bw_j^\T\), so \(z_j=\bw_j^\T\bx\). We write \(\varphi_j=-(\ln p_j)'\) (the score with the sign changed): \(\varphi(z)=\tanh z\) for (16.56).

Result 16.10 (the ICA likelihood, its gradient, and when it identifies the sources) pp. 514–515

  1. \(\displaystyle\ln p(\bX\given\bW)\)\({}=N\ln|\det\bW|\)\({}+\sum_{n=1}^N\sum_{j=1}^D\ln p_j(\bw_j^\T\bx_n)\), with gradient \(N\bW^{-\T}\)\({}-\sum_n\boldsymbol\varphi(\bz_n)\bx_n^\T\) and natural gradient \(\big(N\bI\)\({}-\sum_n\boldsymbol\varphi(\bz_n)\bz_n^\T\big)\bW\) (Amari, Cichocki and Yang, 1996).
  2. If the sources are Gaussian, \(p(\bx)=\N(\bzero,\bA\bA^\T)\) depends on \(\bA\) only through \(\bA\bA^\T\): \(\bA\) and \(\bA\bR\) cannot be distinguished. If at most one source is Gaussian, \(\bA\) is identifiable up to permutation and scaling of its columns (Comon, 1994, from the Darmois–Skitovich theorem).
  3. On whitened data with unit-variance sources, rotations \(\bW=\bR(\theta)\) and the light-tailed prior \(p(z)\propto e^{-z^4/4}\): \[ \frac1N\ln p\to\const+\frac{\kappa_1+\kappa_2}{8}\sin^2 2\phi ,\qquad\phi=\text{angle between }\bR(\theta)\text{ and the separating rotation}, \] where \(\kappa_j=\E z_j^4-3\) are the sources' excess kurtoses. With the sech prior (16.56) the same calculation to fourth order gives \(\const\)\({}-\frac{\kappa_1+\kappa_2}{24}\sin^22\phi\). So a prior that is heavier-tailed than a Gaussian recovers super-Gaussian sources (\(\kappa>0\)), and a lighter-tailed one recovers sub-Gaussian sources (\(\kappa<0\)); with the wrong one, the separating rotation is a minimum of the likelihood and the maximum lies \(45^\circ\) away.

Filling the gap 16.5: the ICA likelihood by a change of variables, and why the prior's tails must match the sources pp. 514–515, "the log likelihood can be maximized using gradient-based optimization"; (16.56)

The book describes the model and the choice (16.56) in words. Here are the likelihood, its gradient, the natural gradient, the non-identifiability, and the condition under which (16.56) actually works, which the book does not discuss and which decides success or failure in practice.

Derivation

Likelihood. \(\bx=\bA\bz\) is an invertible linear change of variables, so by (16.78) \(p(\bx)=p_{\bz}(\bW\bx)\,|\det\bW|\) with \(\bW=\bA^{-1}\). Independence gives \(\ln p(\bx)\)\({}=\ln|\det\bW|+\sum_j\ln p_j(\bw_j^\T\bx)\); sum over \(n\).

Gradient. \(\partial\ln|\det\bW|/\partial\bW\)\({}=\bW^{-\T}\) (Jacobi's formula), and \(\partial\ln p_j(\bw_j^\T\bx)/\partial\bw_j\)\({}=-\varphi_j(z_j)\bx\). Together, \(\nabla_\bW\)\({}=N\bW^{-\T}\)\({}-\sum_n\boldsymbol\varphi(\bz_n)\bx_n^\T\). Multiplying on the right by \(\bW^\T\bW\) (a positive-definite preconditioner, the natural gradient on the group of invertible matrices) gives \(\big(N\bI\)\({}-\sum_n\boldsymbol\varphi(\bz_n)\bz_n^\T\big)\bW\), which needs no matrix inverse and whose fixed points satisfy \(\frac1N\sum_n\varphi_i(z_{ni})z_{nj}\)\({}=\delta_{ij}\): off-diagonal, a nonlinear decorrelation that independence implies (\(\E[\varphi_i(z_i)z_j]\)\({}=\E[\varphi_i(z_i)]\E[z_j]=0\) for zero-mean \(z_j\)); diagonal, a scale condition. Finite differences confirm the gradient.

Gaussian sources. If \(p(\bz)=\N(\bzero,\bI)\), \(p(\bx)=\N(\bzero,\bA\bA^\T)\), and \(\bA\bR\) gives the same. More generally, for whitened data \(\by\) and a Gaussian prior, \(\sum_j\ln p((\bR\by)_j)\)\({}=-\frac12\Vert\bR\by\Vert^2+\const\)\({}=-\frac12\Vert\by\Vert^2+\const\) for every rotation: the likelihood is exactly flat (confirmed numerically).

Whitening reduces the search to a rotation. Whiten first, \(\by=\mathbf V\bx\) (Result 16.3). If the sources have unit variance, \(\by=(\mathbf V\bA)\bz\) is white, so \(\mathbf V\bA\) is orthogonal, and the unmixing matrix of \(\by\) is a rotation (times a sign or permutation). With \(\bW=\bR\) orthogonal the term \(\ln|\det\bW|=0\), and the average log likelihood is \(\ell(\bR)\)\({}=\frac1N\sum_n\sum_j\ln p((\bR\by_n)_j)\).

The sign of the kurtosis. Take \(D=2\) and write the estimates as a rotation by \(\phi\) of the true sources, \(\hat z_1=c\,s_1+s\,s_2\), \(\hat z_2=-s\,s_1+c\,s_2\) (\(c=\cos\phi\), \(s=\sin\phi\)), with independent, zero-mean, unit-variance sources and \(m_j=\E s_j^4=3+\kappa_j\). Odd moments of a single source may be non-zero, but every cross term containing an odd power of an independent zero-mean factor vanishes, so \[ \E\hat z_1^4=c^4m_1+s^4m_2+6c^2s^2,\qquad\E\hat z_2^4=s^4m_1+c^4m_2+6c^2s^2 , \] \[ \E\hat z_1^4+\E\hat z_2^4=(1-2c^2s^2)(m_1+m_2)+12c^2s^2=(m_1+m_2)-\tfrac12\sin^22\phi\,(\kappa_1+\kappa_2), \] using \(c^4+s^4=1-2c^2s^2\) and \(2c^2s^2=\frac12\sin^22\phi\). For the light-tailed prior, \(\ln p(z)=-z^4/4-\ln c_4\) exactly, so \(\ell\)\({}=-\frac14(\E\hat z_1^4+\E\hat z_2^4)\)\({}+\const\)\({}=\frac{\kappa_1+\kappa_2}8\sin^22\phi\)\({}+\const\): if \(\kappa_1+\kappa_2<0\) the maximum is at \(\phi=0\) (separation), otherwise at \(\phi=45^\circ\). For the sech prior, \(\ln p(z)=-\ln\cosh z-\ln\pi\) and \(\ln\cosh z\)\({}=\frac{z^2}2-\frac{z^4}{12}+O(z^6)\); the quadratic term is rotation-invariant for white data, so to fourth order \(\ell=\frac1{12}\sum_j\E\hat z_j^4+\const\)\({}=-\frac{\kappa_1+\kappa_2}{24}\sin^22\phi\)\({}+\const\): maximum at separation iff \(\kappa_1+\kappa_2>0\). (The fourth-order truncation is a heuristic for the sech prior; the curves of Figure 16.S2(e), computed exactly from samples, have this shape.) The normalising constant of the light-tailed prior is \(c_4=\int e^{-z^4/4}\d z\)\({}=4^{1/4}\Gamma(1/4)/2\).

Consequences. (16.56) is the right default for speech and many natural signals, which are super-Gaussian. For sub-Gaussian sources (uniform noise, sinusoids, sawtooth waves) it converges to the most mixed rotation. Practical algorithms either choose the nonlinearity per source from the sign of an estimated kurtosis ("extended infomax", Lee, Girolami and Sejnowski, 1999) or learn flexible source densities (Attias, 1999). ∎

Algorithm 16.2 (maximum likelihood ICA by natural gradient) pp. 514–515

  1. Centre and whiten the data, \(\by_n=\bL^{-1/2}\bU^\T(\bx_n-\bxbar)\) (16.24).
  2. Start from \(\bW=\bI\) (or any rotation). Repeat: \(\bz_n=\bW\by_n\); \(\bW\leftarrow\bW+\eta\big(\bI-\frac1N\sum_n\boldsymbol\varphi(\bz_n)\bz_n^\T\big)\bW\), with \(\varphi=\tanh\) for (16.56).
  3. The sources are recovered up to order, sign and scale; the full unmixing matrix for \(\bx\) is \(\bW\bL^{-1/2}\bU^\T\).
Five panels. Red heavy-tailed sources in a plus-shaped cloud; the green observed mixture stretched along two dashed mixing directions; the blue whitened cloud with two purple unmixing directions; the purple ICA estimates, again plus-shaped. Last panel: log likelihood against rotation angle from 0 to 90 degrees; the red curve for heavy-tailed sources peaks at 21 degrees, the blue curve for uniform sources has its minimum there and its peak 45 degrees away, the grey Gaussian curve is nearly flat.
Figure 16.S2 (our own). ICA of 500 samples of two sources drawn from (16.56): (a) sources, (b) observations \(\bx=\bA\bz\) with the mixing directions dashed, (c) whitened data with the learned unmixing directions, (d) the estimates after 200 natural-gradient steps (each correlates more than 0.999 with one source). (e) The sech-prior log likelihood of whitened data along rotations (2000 samples, mean removed): heavy-tailed sources peak at the separating angle, uniform sources have a minimum there, Gaussian sources are flat up to sampling noise. Download: PDF · SVG
▶ DemoICA separates heavy-tailed sourcesMix, whiten and unmix; the log likelihood along rotations and the natural-gradient run are drawn live.
▶ DemoUniform sources with the sech prior: the wrong peakPreset 2 shows the flat likelihood of Gaussian sources; presets 3 and 4 the kurtosis condition of Result 16.10(3); preset 5 unmixes a sine and a sawtooth.

16.2.6 Kalman filters

See also the companion course, Section 13.3 (linear dynamical systems), Section 13.3.1 (inference) and its Kalman filter demo.

pp. 515–516 For sequences the i.i.d. assumption fails. As the hidden Markov model chains discrete latent variables, a linear dynamical system chains continuous ones (Figure 16.9, a drawing not reproduced): each \(p(\bx_n\given\bz_n)\) is a linear-Gaussian latent variable model, and the latent variables form a Markov chain with linear-Gaussian transitions \(p(\bz_n\given\bz_{n-1})\). The parameters are shared across time steps. The book calls the model a Kalman filter (Zarchan and Musoff, 2005); strictly, the Kalman filter is the recursive algorithm that computes \(p(\bz_n\given\bx_1,\dots,\bx_n)\) in this model. Hidden Markov models and linear dynamical systems were developed separately and share the same graph; the book returns to i.i.d. data after this section.

Definition 16.5 (linear dynamical system) pp. 515–516

\(\bz_1\sim\N(\bmu_0,\mathbf P_0)\); \(\bz_n=\bA\bz_{n-1}+\mathbf w_n\), \(\mathbf w_n\sim\N(\bzero,\boldsymbol\Gamma)\); \(\bx_n=\bC\bz_n+\mathbf v_n\), \(\mathbf v_n\sim\N(\bzero,\Sig)\); all noises independent. (In this subsection \(\bA\) and \(\bC\) are the transition and emission matrices.)

Result 16.11 (the Kalman filter and the likelihood) pp. 515–516

\(p(\bz_n\given\bx_1,\dots,\bx_n)\)\({}=\N(\bmu_n,\mathbf P_n)\), computed recursively: predict \(\bmu_n^-=\bA\bmu_{n-1}\), \(\mathbf P_n^-\)\({}=\bA\mathbf P_{n-1}\bA^\T\)\({}+\boldsymbol\Gamma\) (for \(n=1\): \(\bmu_0,\mathbf P_0\)); then with gain \(\mathbf K_n\)\({}=\mathbf P_n^-\bC^\T(\bC\mathbf P_n^-\bC^\T\)\({}+\Sig)^{-1}\), \[ \bmu_n=\bmu_n^-+\mathbf K_n(\bx_n-\bC\bmu_n^-),\qquad\mathbf P_n=(\bI-\mathbf K_n\bC)\mathbf P_n^- . \] The likelihood factorises into predictive terms, \(\ln p(\bx_1,\dots,\bx_N)\)\({}=\sum_n\ln\N(\bx_n\given\bC\bmu_n^-,\bC\mathbf P_n^-\bC^\T\)\({}+\Sig)\), which is what maximum likelihood learning maximises (by EM with the smoother, or by gradients).

Filling the gap 16.6: the filter recursions from two linear-Gaussian operations p. 516, "efficient algorithms that involve propagating messages around the graph"

Derivation

Induction on \(n\). Suppose \(p(\bz_{n-1}\given\bx_{1:n-1})\)\({}=\N(\bmu_{n-1},\mathbf P_{n-1})\). Predict: \(\bz_n=\bA\bz_{n-1}+\mathbf w_n\) with \(\mathbf w_n\) independent of \(\bz_{n-1}\) and of the past observations, so \(p(\bz_n\given\bx_{1:n-1})\) is Gaussian with mean \(\bA\bmu_{n-1}\) and covariance \(\bA\mathbf P_{n-1}\bA^\T\)\({}+\boldsymbol\Gamma\) (the marginal of a linear-Gaussian model, as in (16.35)). Update: given \(\bz_n\), \(\bx_n\) is independent of \(\bx_{1:n-1}\), so \(p(\bz_n\given\bx_{1:n})\)\({}\propto p(\bx_n\given\bz_n)p(\bz_n\given\bx_{1:n-1})\), a linear-Gaussian Bayes step exactly like (16.43): the joint of \((\bz_n,\bx_n)\) has \(\cov[\bz_n,\bx_n]=\mathbf P_n^-\bC^\T\) and \(\cov[\bx_n]=\bC\mathbf P_n^-\bC^\T+\Sig\), and conditioning gives the stated mean and covariance. The normaliser of that Bayes step is \(p(\bx_n\given\bx_{1:n-1})\)\({}=\N(\bC\bmu_n^-,\bC\mathbf P_n^-\bC^\T\)\({}+\Sig)\), and the product rule \(p(\bx_{1:N})\)\({}=\prod_np(\bx_n\given\bx_{1:n-1})\) gives the likelihood.

Steady state. For the scalar model of Figure 16.S3 (\(z_n=az_{n-1}+w\), \(x_n=z_n+v\)), the predictive variance obeys the Riccati recursion \(P^-_{n+1}=a^2P^-_nr/(P^-_n+r)+q\), a contraction whose fixed point solves \(P^2+(r-a^2r-q)P-qr=0\); the gain converges to \(P/(P+r)\). With \(a=0.95\), \(q=0.1\), \(r=1\) the steady gain is 0.241. The filter is confirmed against brute-force conditioning of the joint Gaussian of the whole sequence (mean and variance at \(n=25\), and the total log likelihood, to \(10^{-9}\)). Full derivations, the smoother and EM are in the companion course, Section 13.3.1 and Section 13.3.2. ∎

Left: 100 noisy grey observations, the black latent path and the red Kalman filter mean with a pink two-standard-deviation band that follows the latent path. Right: the Kalman gain falling from 0.5 to its steady-state value 0.24 within ten steps.
Figure 16.S3 (our own). A one-dimensional linear dynamical system, \(z_n=0.95z_{n-1}+w_n\), \(x_n=z_n+v_n\), \(\var w=0.1\), \(\var v=1\): observations (grey), latent path (black), filter mean with \(\pm2\) standard deviations (red). Right: the gain \(K_n\) reaches the steady state of the Riccati equation within about ten steps. Download: PDF · SVG

16.3 Evidence Lower Bound

See also the companion course, Section 9.4 (the EM algorithm in general), Result 9.14 and its EM lower-bound demo.

pp. 516–517 Chapter 15 derived the evidence lower bound for discrete latent variables; the same argument works for continuous ones, and for mixtures of both. Let \(p(\bx,\bz\given\bw)\) be a model with parameters \(\bw\), and \(q(\bz)\) any distribution over the latent variable. Then

\[ \ln p(\bx\given\bw)=\L(q,\bw)+\KL\big(q(\bz)\Vert p(\bz\given\bx,\bw)\big) \tag{16.57} \]

with

\[ \L(q,\bw)=\int q(\bz)\ln\Big\{\frac{p(\bx,\bz\given\bw)}{q(\bz)}\Big\}\d\bz , \tag{16.58} \] \[ \KL\big(q(\bz)\Vert p(\bz\given\bx,\bw)\big)=-\int q(\bz)\ln\Big\{\frac{p(\bz\given\bx,\bw)}{q(\bz)}\Big\}\d\bz . \tag{16.59} \]

(The book writes \(\L(\bw)\) on the left of (16.57) and in (16.60); the bound depends on \(q\) as well.) Because the Kullback–Leibler divergence is non-negative (Section 2.5.5),

\[ \ln p(\bx\given\bw)\ge\L(q,\bw), \tag{16.60} \]

and \(\L\) is the evidence lower bound (ELBO). The EM algorithm maximises \(\L\) alternately over \(q\) (E step, with \(\bw=\bw^{\rm old}\) fixed: the best \(q\) is the posterior, which makes the KL term zero) and over \(\bw\) (M step). With \(q(\bz)=p(\bz\given\bx,\bw^{\rm old})\),

\[ \L(q,\bw)=\int p(\bz\given\bx,\bw^{\rm old})\ln p(\bx,\bz\given\bw)\,\d\bz-\int p(\bz\given\bx,\bw^{\rm old})\ln p(\bz\given\bx,\bw^{\rm old})\,\d\bz ; \tag{16.61} \]

the second term does not depend on \(\bw\), so the M step maximises the expected complete-data log likelihood. For i.i.d. data

\[ \ln p(\bX\given\bw)=\sum_{n=1}^N\ln p(\bx_n\given\bw), \tag{16.62} \]

and with one \(q(\bz_n)\) per data point

\[ \L(q,\bw)=\sum_{n=1}^N\int q(\bz_n)\ln\Big\{\frac{p(\bx_n,\bz_n\given\bw)}{q(\bz_n)}\Big\}\d\bz_n . \tag{16.63} \]

When the exact E step is impossible, as in the variational autoencoders of Chapter 19, \(q\) is restricted to a family computed by a neural network, and \(\L\) is maximised jointly over that network and \(\bw\).

Result 16.12 (the evidence lower bound) pp. 516–517, (16.57)–(16.63); Exercises 16.18, 16.19

  1. (16.57) holds for every density \(q\) with \(q(\bz)>0\)\({}\Rightarrow p(\bz\given\bx,\bw)>0\) (if \(q\) puts mass where the posterior is zero, the KL is \(+\infty\) and \(\L=-\infty\)). Hence \(\L\le\ln p\), with equality iff \(q=p(\bz\given\bx,\bw)\) almost everywhere.
  2. For i.i.d. data the bound is (16.63); a joint \(q(\bz_1,\dots,\bz_N)\) gives a bound that is also maximised by the product of the individual posteriors.
  3. EM never decreases the log likelihood: \(\ln p(\bx\given\bw^{\rm new})\)\({}\ge\L(q,\bw^{\rm new})\)\({}\ge\L(q,\bw^{\rm old})\)\({}=\ln p(\bx\given\bw^{\rm old})\).
  4. (Fisher's identity.) \(\nabla_\bw\ln p(\bx\given\bw)\)\({}=\E_{p(\bz\given\bx,\bw)}\big[\nabla_\bw\ln p(\bx,\bz\given\bw)\big]\)\({}=\nabla_\bw\L(q,\bw)\) at \(q=p(\bz\given\bx,\bw)\): the bound touches the log likelihood with the same slope.
  5. If the posterior is an equal mixture \(\frac12(p_1+p_2)\) of two densities with disjoint supports, then for any \(q\) supported inside the support of \(p_1\), \(\KL(q\Vert p(\bz\given\bx))\)\({}=\ln2+\KL(q\Vert p_1)\ge\ln2\). A single Gaussian sitting on one well-separated mode therefore pays at least \(\ln2\) nats.

Filling the gap 16.7: the decomposition, its conditions, the slope of the bound and the \(\ln2\) gap pp. 516–517; Exercises 16.18, 16.19

Derivation

(1) Use the product rule \(p(\bx,\bz\given\bw)\)\({}=p(\bz\given\bx,\bw)p(\bx\given\bw)\) (16.89) inside (16.58): \[ \L(q,\bw)=\int q\ln p(\bx\given\bw)\,\d\bz+\int q\ln\frac{p(\bz\given\bx,\bw)}{q}\,\d\bz=\ln p(\bx\given\bw)-\KL\big(q\Vert p(\bz\given\bx,\bw)\big), \] since \(\int q=1\). Both integrals are well defined in \([-\infty,\infty)\) under the support condition. Gibbs' inequality: \(-\KL=\int q\ln(p/q)\le\ln\int q\,(p/q)\)\({}=\ln\int_{q>0}p\le0\) by Jensen's inequality for the concave logarithm, with equality iff \(p/q\) is constant on \(\{q>0\}\) and \(\int_{q>0}p=1\), i.e. \(q=p\).

(2) With \(q(\bZ)=\prod_nq(\bz_n)\) and \(p(\bX,\bZ\given\bw)\)\({}=\prod_np(\bx_n,\bz_n\given\bw)\), \(\ln\{p(\bX,\bZ)/q(\bZ)\}\)\({}=\sum_n\ln\{p(\bx_n,\bz_n)/q(\bz_n)\}\), and each term integrates against its own \(q(\bz_n)\) (the others integrate to 1): this is (16.63). For a general \(q(\bZ)\), (16.57) applied to the whole data set gives the gap \(\KL(q(\bZ)\Vert\prod_np(\bz_n\given\bx_n))\), zero for the product of posteriors.

(3) The E step sets \(q=p(\bz\given\bx,\bw^{\rm old})\), so \(\L(q,\bw^{\rm old})\)\({}=\ln p(\bx\given\bw^{\rm old})\); the M step does not decrease \(\L(q,\cdot)\); and (16.60) holds at \(\bw^{\rm new}\).

(4) \(\nabla_\bw\ln p(\bx\given\bw)\)\({}=\frac{\int\nabla_\bw p(\bx,\bz\given\bw)\d\bz}{p(\bx\given\bw)}\)\({}=\int\frac{p(\bx,\bz\given\bw)}{p(\bx\given\bw)}\nabla_\bw\ln p(\bx,\bz\given\bw)\,\d\bz\), assuming differentiation under the integral is allowed (e.g. dominated convergence). For fixed \(q\), \(\nabla_\bw\L(q,\bw)\)\({}=\int q\,\nabla_\bw\ln p(\bx,\bz\given\bw)\,\d\bz\), equal to the previous line when \(q\) is the posterior at \(\bw\). This is why maximising the ELBO with a good \(q\) is nearly as good as maximising the likelihood, and it is the gradient that a VAE estimates.

(5) On the support of \(p_1\) the posterior equals \(\frac12p_1\), so \(\KL(q\Vert\frac12p_1)\)\({}=\int q\ln\frac{q}{p_1/2}\)\({}=\ln2+\KL(q\Vert p_1)\). A Gaussian has unbounded support, so the statement holds only approximately; for the circle model at \(\bx=(0,-1)\) (\(z=\pm\pi\) map to the same point, \(\sigma=0.3\)) the best Gaussian has \(\KL=0.6939\) against \(\ln2=0.6931\) (Figure 16.S6). Exercise 16.18 is part (1), Exercise 16.19 part (2). ∎

Left: over the latent axis, the grey prior, a black posterior with two equal narrow peaks at minus and plus 2.9, and a red best Gaussian q sitting on the left peak. Middle: a heat map of the ELBO over the mean m and standard deviation s of q, with two bright maxima at m near plus and minus 2.9 and s near 0.3. Right: horizontal bars of the KL gap: 12.8 nats for the prior, 0.694 for the best Gaussian, 1.34 for a too narrow Gaussian on one mode, with a dotted line at ln 2.
Figure 16.S6 (our own). The ELBO for the circle model of Figure 16.13 (\(\sigma=0.3\)) at \(\bx=(0,-1)\), where \(\ln p(\bx)=-4.482\). (a) The posterior has two equal modes near \(z=\pm\pi\) (pulled in slightly by the prior); the best Gaussian \(q\) covers one. (b) The ELBO over \(q=\N(m,s^2)\) has two symmetric maxima. (c) The gap \(\KL(q\Vert p(z\given\bx))\)\({}=\ln p(\bx)-\L(q)\): 12.8 nats for \(q=p(z)\) (the prior), 0.694 for the best Gaussian, close to \(\ln2\) (dotted), and 1.34 for a Gaussian on one mode that is too narrow. Download: PDF · SVG
▶ DemoA two-mode posterior: the gap is ln 2Click any point of the plane to see its posterior over \(z\), move the Gaussian \(q\), and watch \(\ln p(\bx)=\) ELBO \(+\) KL.

16.3.1 Expectation maximization

See also the companion course, Section 12.2.2, Filling the gap 12.4 and Filling the gap 12.5 (missing values).

pp. 518–519 For probabilistic PCA EM may seem pointless, since the maximum likelihood solution is known in closed form. But in high dimensions EM can be cheaper, it extends to factor analysis (no closed form) and it handles missing data. The complete-data log likelihood is

\[ \ln p(\bX,\bZ\given\bmu,\bW,\sigma^2)=\sum_{n=1}^N\big\{\ln p(\bx_n\given\bz_n)+\ln p(\bz_n)\big\}, \tag{16.64} \]

where row \(n\) of \(\bZ\) is \(\bz_n\). Setting \(\bmu=\bxbar\) and taking the expectation over the posterior,

\[ \E[\ln p(\bX,\bZ\given\bmu,\bW,\sigma^2)]=-\sum_{n=1}^N\Big\{\frac D2\ln(2\pi\sigma^2)+\frac12\Tr\big(\E[\bz_n\bz_n^\T]\big)+\frac1{2\sigma^2}\Vert\bx_n-\bmu\Vert^2-\frac1{\sigma^2}\E[\bz_n]^\T\bW^\T(\bx_n-\bmu)+\frac1{2\sigma^2}\Tr\big(\E[\bz_n\bz_n^\T]\bW^\T\bW\big)+\frac M2\ln(2\pi)\Big\}. \tag{16.65} \]

It depends on the posterior only through its first two moments. The E step computes, with the old parameters,

\[ \E[\bz_n]=\bM^{-1}\bW^\T(\bx_n-\bxbar), \tag{16.66} \] \[ \E[\bz_n\bz_n^\T]=\sigma^2\bM^{-1}+\E[\bz_n]\E[\bz_n]^\T , \tag{16.67} \]

and the M step sets

\[ \bW_{\rm new}=\Big[\sum_{n=1}^N(\bx_n-\bxbar)\E[\bz_n]^\T\Big]\Big[\sum_{n=1}^N\E[\bz_n\bz_n^\T]\Big]^{-1}, \tag{16.68} \] \[ \sigma^2_{\rm new}=\frac1{ND}\sum_{n=1}^N\Big\{\Vert\bx_n-\bxbar\Vert^2-2\E[\bz_n]^\T\bW_{\rm new}^\T(\bx_n-\bxbar)+\Tr\big(\E[\bz_n\bz_n^\T]\bW_{\rm new}^\T\bW_{\rm new}\big)\Big\}. \tag{16.69} \]

Algorithm 16.3 (EM for probabilistic PCA) pp. 518–519, (16.66)–(16.69)

  1. Centre the data; initialise \(\bW\) (e.g. random) and \(\sigma^2>0\).
  2. E step: \(\bM=\bW^\T\bW+\sigma^2\bI\); for all \(n\), \(\E[\bz_n]\) and \(\E[\bz_n\bz_n^\T]\) by (16.66)–(16.67).
  3. M step: \(\bW\) by (16.68), then \(\sigma^2\) by (16.69) with the new \(\bW\).
  4. Repeat until the log likelihood (16.45) (computed with (16.41) and \(|\bC|=\sigma^{2(D-M)}|\bM|\)) stops increasing.

Filling the gap 16.8: the expected complete-data log likelihood, the M step, and the cost pp. 518–519, (16.65)–(16.69); Exercise 16.21

Derivation

(16.65). \(\ln p(\bx\given\bz)\)\({}=-\frac D2\ln(2\pi\sigma^2)\)\({}-\frac1{2\sigma^2}\Vert\bx-\bmu\)\({}-\bW\bz\Vert^2\) and \(\ln p(\bz)\)\({}=-\frac M2\ln2\pi-\frac12\bz^\T\bz\). Expand \(\Vert\bx-\bmu-\bW\bz\Vert^2\)\({}=\Vert\bx-\bmu\Vert^2-2\bz^\T\bW^\T(\bx\)\({}-\bmu)+\Tr(\bz\bz^\T\bW^\T\bW)\) and \(\bz^\T\bz=\Tr(\bz\bz^\T)\); the expectation is linear, so only \(\E[\bz_n]\) and \(\E[\bz_n\bz_n^\T]\) appear. (16.66)–(16.67) are the posterior mean (16.43) and \(\E[\bz\bz^\T]\)\({}=\cov[\bz]+\E[\bz]\E[\bz]^\T\).

(16.68). Using \(\partial\Tr(\mathbf B\bW^\T\bW)/\partial\bW\)\({}=\bW(\mathbf B+\mathbf B^\T)\) (the book's (A.24)) with symmetric \(\mathbf B=\E[\bz_n\bz_n^\T]\), the gradient of (16.65) is \(\frac1{\sigma^2}\sum_n\big[(\bx_n\)\({}-\bxbar)\E[\bz_n]^\T\)\({}-\bW\E[\bz_n\bz_n^\T]\big]\), zero at (16.68). (16.65) is a concave quadratic in \(\bW\) because \(\sum_n\E[\bz_n\bz_n^\T]\) is positive definite, so this is the maximum.

(16.69). With \(\bW=\bW_{\rm new}\) fixed, (16.65) is \(-\frac{ND}2\ln\sigma^2\)\({}-\frac{B}{2\sigma^2}+\const\) with \(B=\sum_n\{\cdots\}\), maximised at \(\sigma^2=B/(ND)\). (The pair is a coordinate-wise maximum, and since (16.65) is jointly maximised by first choosing \(\bW\), whose optimum does not depend on \(\sigma^2\), it is also the joint maximum.) Numerically, random perturbations of the M-step values always lower (16.65).

Cost. The E step needs \(\bW^\T(\bx_n-\bxbar)\) for all \(n\): \(O(NDM)\), plus \(O(DM^2+M^3)\) for \(\bM\) and its inverse. The M step needs \(\sum_n(\bx_n-\bxbar)\E[\bz_n]^\T\) (\(O(NDM)\)) and an \(M\times M\) inverse. Forming \(\bS\) would cost \(O(ND^2)\) and diagonalising it \(O(D^3)\); the snapshot method of Section 16.1.5 costs \(O(N^3)\). For large \(N\) and \(D\) with \(M\ll D\), EM's \(O(NDM)\) per iteration wins, and the sums can be accumulated one data point at a time (an online version that never stores the data set). The price is the number of iterations: convergence is linear, slow when the leading eigenvalues are close. On the 6000 threes with \(M=10\) (Figure 16.S4(a)), EM from a random start is still 0.46 nats per image below the maximum after 300 iterations. ∎

Result 16.13 (EM for probabilistic PCA with missing values) p. 519; Exercise 16.22

Let \(o_n\) be the observed coordinates of \(\bx_n\) and \(m_n\) the missing ones, assumed missing at random. With \(\bW_o\) the rows of \(\bW\) in \(o_n\), the E step uses \(\bM_n=\bW_o^\T\bW_o+\sigma^2\bI\), \(\E[\bz_n]\)\({}=\bM_n^{-1}\bW_o^\T(\bx_{n,o}-\bmu_o)\), \(\E[\bz_n\bz_n^\T]\)\({}=\sigma^2\bM_n^{-1}\)\({}+\E[\bz_n]\E[\bz_n]^\T\), and fills in the expected statistics of the missing entries, \(\E[x_{ni}\widetilde\bz_n^\T]\)\({}=\boldsymbol\theta_i^\T\E[\widetilde\bz_n\widetilde\bz_n^\T]\) and \(\E[x_{ni}^2]\)\({}=\boldsymbol\theta_i^\T\E[\widetilde\bz_n\widetilde\bz_n^\T]\boldsymbol\theta_i\)\({}+\sigma^2\), where \(\widetilde\bz=(\bz,1)\) and \(\boldsymbol\theta_i=(\bw_i,\mu_i)\) are the old row parameters. The M step solves \(\boldsymbol\theta_i^{\rm new}\)\({}=\big(\sum_n\E[x_{ni}\widetilde\bz_n^\T]\big)\big(\sum_n\E[\widetilde\bz_n\widetilde\bz_n^\T]\big)^{-1}\) for every row and sets \(\sigma^2\) to the average expected squared residual. The observed-data likelihood \(\sum_n\ln\N(\bx_{n,o}\given\bmu_o,\bW_o\bW_o^\T\)\({}+\sigma^2\bI)\) never decreases, and with no missing values (and \(\bmu\) started at \(\bxbar\)) the iteration is exactly (16.66)–(16.69).

Proof

The latent variables are \(\bz_n\) and \(\bx_{n,m}\). Their joint posterior factorises as \(p(\bz_n\given\bx_{n,o})p(\bx_{n,m}\given\bz_n)\), because given \(\bz_n\) the coordinates of \(\bx_n\) are independent: the first factor is (16.43) with the observed rows, the second is \(\N(\bW_m\bz_n+\bmu_m,\sigma^2\bI)\). The complete-data log likelihood is \(\sum_n\sum_i\{-\frac12\ln2\pi\sigma^2-\frac1{2\sigma^2}(x_{ni}-\boldsymbol\theta_i^\T\widetilde\bz_n)^2\}\)\({}+\sum_n\ln p(\bz_n)\), whose expectation involves only \(\E[x_{ni}^2]\), \(\E[x_{ni}\widetilde\bz_n]\) and \(\E[\widetilde\bz_n\widetilde\bz_n^\T]\); for a missing \(x_{ni}\)\({}=\boldsymbol\theta_i^{\rm old\,\T}\widetilde\bz_n\)\({}+\epsilon\) these are the stated formulae. Each row \(\boldsymbol\theta_i\) is then a separate least-squares problem, and \(\sigma^2\) follows as in (16.69). Monotonicity is Result 16.12(3). Without missing values, \(\sum_n\E[\bz_n]\)\({}=\bM^{-1}\bW^\T\sum_n(\bx_n-\bxbar)\)\({}=\bzero\), so the \(\mu\) row stays at \(\bxbar\) and the \(\bW\) rows reduce to (16.68). Both statements are confirmed numerically on data with 20% of entries removed.

On "missing at random". The book defines it as missingness that depends neither on observed nor on unobserved values. That is missing completely at random; missing at random (Rubin, 1976) allows dependence on the observed values, and the likelihood-based EM above remains valid under that weaker condition, because the factor describing the missingness then does not involve the model parameters. ∎

16.3.2 EM for PCA

See also the companion course, Result 12.12 (EM for PCA is subspace iteration) and the EM view of its PCA demo.

pp. 519–520 In the limit \(\sigma^2\to0\) (standard PCA) EM still makes sense (Roweis, 1998). Only \(\E[\bz_n]\) is needed and \(\bM=\bW^\T\bW\). Let \(\bXt\) be the \(N\times D\) matrix with rows \((\bx_n-\bxbar)^\T\) and \(\bOm\) the \(M\times N\) matrix with columns \(\E[\bz_n]\). The E step (16.66) becomes

\[ \bOm=(\bW_{\rm old}^\T\bW_{\rm old})^{-1}\bW_{\rm old}^\T\bXt^\T \tag{16.70} \]

and the M step (16.68)

\[ \bW_{\rm new}=\bXt^\T\bOm^\T(\bOm\bOm^\T)^{-1}. \tag{16.71} \]

The E step projects the points orthogonally onto the current subspace; the M step moves the subspace to minimise the squared reconstruction error with the projections held fixed (Exercise 16.23). Picture a rod (the subspace) attached to each point by a spring: the E step lets the attachment points slide along the fixed rod to their lowest-energy positions (the orthogonal projections), and the M step releases the rod with the attachments fixed (Figure 16.10).

Six panels of 40 green points. (a) The true principal axes as magenta arrows. (b) An initial red line at a steep angle with cyan projections and grey springs. (c) After the M step the red line has turned towards the data cloud. (d) After the E step the cyan points are orthogonal projections. (e) After the second M step the line is almost aligned. (f) The converged line along the principal axis.
Figure 16.10 (computed). EM for PCA (16.70)–(16.71) on 40 standardised points: (a) data and the principal axes scaled by \(\lambda_i^{1/2}\); (b) the initial subspace (red) with the latent points mapped back, \(\bZ\bW^\T\) (cyan), and the springs (grey); (c) after the first M step (\(\bZ\) fixed); (d) after the next E step (orthogonal projections); (e) after the second M step; (f) the converged solution. Reproduces Bishop and Bishop (2024), Figure 16.10. Download: PDF · SVG

Result 16.14 (EM for PCA is subspace iteration) pp. 519–520, (16.70)–(16.71); Exercise 16.23

  1. (16.70) minimises \(J\)\({}=\sum_n\Vert\bx_n-\bxbar-\bW\bz_n\Vert^2\) (16.90) over the \(\bz_n\) for fixed \(\bW\), and (16.71) minimises it over \(\bW\) for fixed \(\bz_n\).
  2. \(\bW_{\rm new}\)\({}=\bS\bW_{\rm old}(\bW_{\rm old}^\T\bS\bW_{\rm old})^{-1}\bW_{\rm old}^\T\bW_{\rm old}\), so \(\span\bW_{\rm new}\)\({}=\span(\bS\bW_{\rm old})\).
  3. Hence, if \(\lambda_M>\lambda_{M+1}\) and the starting subspace is not orthogonal to any leading eigenvector, \(\span\bW\) converges to the principal subspace, with the sine of the largest principal angle shrinking by the factor \(\lambda_{M+1}/\lambda_M\) per iteration.

Filling the gap 16.9: alternating least squares, power iteration, and the rate p. 520, "a simple interpretation"; Exercise 16.23

Derivation

(1) For fixed \(\bW\), \(J\) is a sum of separate least-squares problems in \(\bz_n\), solved by \(\bz_n\)\({}=(\bW^\T\bW)^{-1}\bW^\T(\bx_n-\bxbar)\): the columns of (16.70). For fixed \(\bOm\), \(J=\Vert\bXt^\T-\bW\bOm\Vert_F^2\) is least squares in \(\bW\) with normal equations \(\bW\bOm\bOm^\T=\bXt^\T\bOm^\T\): (16.71). (The mean: minimising (16.90) over \(\bmu\) gives \(\bmu=\bxbar-\bW\bar\bz\), and substituting turns \(\bx_n\), \(\bz_n\) into \(\bx_n-\bxbar\), \(\bz_n-\bar\bz\); see Exercise 16.23.) Each step lowers \(J\), which is bounded below, so \(J\) converges.

(2) With \(\mathbf G=(\bW^\T\bW)^{-1}\): \(\bOm\bOm^\T\)\({}=\mathbf G\bW^\T\bXt^\T\bXt\bW\mathbf G\)\({}=N\mathbf G\bW^\T\bS\bW\mathbf G\) and \(\bXt^\T\bOm^\T=\bXt^\T\bXt\bW\mathbf G\)\({}=N\bS\bW\mathbf G\). Then \(\bW_{\rm new}\)\({}=N\bS\bW\mathbf G\,(N\mathbf G\bW^\T\bS\bW\mathbf G)^{-1}\)\({}=\bS\bW(\bW^\T\bS\bW)^{-1}\mathbf G^{-1}\), whose column space is that of \(\bS\bW\) (right multiplication by an invertible \(M\times M\) matrix).

(3) So after \(k\) iterations \(\span\bW_k=\span(\bS^k\bW_0)\): this is orthogonal (subspace) iteration, the block power method. Writing \(\bW_0\) in the eigenbasis, the components along \(\bu_{M+1},\dots\) shrink relative to those along \(\bu_1,\dots,\bu_M\) by at least \((\lambda_{M+1}/\lambda_M)^k\) (Golub and Van Loan, 1996, Section 7.3). The measured rate is 0.8476 against \(\lambda_3/\lambda_2=0.8476\) on data with population eigenvalues 5, 4, 3.4, ...; Figure 16.S4(b) shows the same on the threes. Every fixed point spans an invariant subspace of \(\bS\), but only the principal one is stable. ∎

Left: on a log scale, the gap between the maximum log likelihood and the EM log likelihood per image falls from 137 nats to 0.46 over 300 iterations, quickly at first and then slowly. Right: the sine of the largest angle between the EM-for-PCA subspace and the principal subspace falls geometrically for M equal to 1, 5 and 10, with dotted lines of slope lambda M plus 1 over lambda M matching each.
Figure 16.S4 (our own). (a) EM for probabilistic PCA (16.66)–(16.69) on the 6000 threes (grey levels in \([0,1]\), \(M=10\), random start): the gap to the closed-form maximum (16.46)–(16.47), per image. The first iterations gain 130 nats, the last 200 only a few, because \(\lambda_{10}\) and \(\lambda_{11}\) are close. (b) EM for PCA (16.70)–(16.71): the largest principal angle to the principal subspace shrinks at the rate \(\lambda_{M+1}/\lambda_M\) (dotted). Download: PDF · SVG

16.3.3 EM for factor analysis

See also the companion course, Filling the gap 12.7 and Algorithm 12.5.

pp. 520–521 For factor analysis \(\bmu=\bxbar\) again (Exercise 16.26), but \(\bW\) and \(\bPsi\) have no closed form; EM (Rubin and Thayer, 1982) has the E step

\[ \E[\bz_n]=\bG\bW^\T\bPsi^{-1}(\bx_n-\bxbar), \tag{16.72} \] \[ \E[\bz_n\bz_n^\T]=\bG+\E[\bz_n]\E[\bz_n]^\T , \tag{16.73} \] \[ \bG=(\bI+\bW^\T\bPsi^{-1}\bW)^{-1}, \tag{16.74} \]

which inverts only \(M\times M\) matrices (and the diagonal \(\bPsi\), in \(O(D)\)), and the M step

\[ \bW_{\rm new}=\Big[\sum_{n=1}^N(\bx_n-\bxbar)\E[\bz_n]^\T\Big]\Big[\sum_{n=1}^N\E[\bz_n\bz_n^\T]\Big]^{-1}, \tag{16.75} \] \[ \bPsi_{\rm new}=\diag\Big\{\bS-\bW_{\rm new}\frac1N\sum_{n=1}^N\E[\bz_n](\bx_n-\bxbar)^\T\Big\}, \tag{16.76} \]

where \(\diag\) sets the off-diagonal elements to zero.

Algorithm 16.4 (EM for factor analysis; Rubin and Thayer, 1982) pp. 520–521, (16.72)–(16.76)

  1. Centre the data, compute \(\bS\); initialise \(\bW\) and \(\bPsi\) (e.g. \(\bPsi=\diag\bS\)).
  2. E step: \(\bG\) by (16.74), then (16.72)–(16.73) for all \(n\).
  3. M step: \(\bW\) by (16.75), \(\bPsi\) by (16.76). Repeat until the log likelihood stops increasing.

Filling the gap 16.10: the E and M steps of factor analysis pp. 520–521; Exercises 16.24, 16.25

Derivation

E step. As a function of \(\bz\), \(\ln p(\bz)+\ln p(\bx\given\bz)\)\({}=-\frac12\bz^\T\bz-\frac12(\bx-\bmu\)\({}-\bW\bz)^\T\bPsi^{-1}(\bx-\bmu-\bW\bz)\)\({}+\const\)\({}=-\frac12\bz^\T(\bI\)\({}+\bW^\T\bPsi^{-1}\bW)\bz\)\({}+\bz^\T\bW^\T\bPsi^{-1}(\bx-\bmu)+\const\). Completing the square: precision \(\bG^{-1}\), mean \(\bG\bW^\T\bPsi^{-1}(\bx-\bmu)\), which are (16.72)–(16.74) with \(\bmu=\bxbar\).

Expected complete-data log likelihood. \[ \sum_n\Big\{-\frac12\ln|2\pi\bPsi|-\frac12\Tr\Big[\bPsi^{-1}\big((\bx_n-\bxbar)(\bx_n-\bxbar)^\T-2\bW\E[\bz_n](\bx_n-\bxbar)^\T+\bW\E[\bz_n\bz_n^\T]\bW^\T\big)\Big]\Big\}+(\text{terms without }\bW,\bPsi). \] \(\bW\): the gradient \(\bPsi^{-1}\sum_n[(\bx_n\)\({}-\bxbar)\E[\bz_n]^\T\)\({}-\bW\E[\bz_n\bz_n^\T]]\) vanishes at (16.75), independently of \(\bPsi\). \(\bPsi\): for a diagonal entry, \(\partial/\partial\psi_i\) of \(-\frac N2\ln\psi_i\)\({}-\frac1{2\psi_i}\sum_n[\cdots]_{ii}\) vanishes at \(\psi_i\)\({}=\frac1N\sum_n[(\bx_n-\bxbar)(\bx_n\)\({}-\bxbar)^\T-2\bW\E[\bz_n](\bx_n\)\({}-\bxbar)^\T\)\({}+\bW\E[\bz_n\bz_n^\T]\bW^\T]_{ii}\). By (16.75), \(\bW_{\rm new}\sum_n\E[\bz_n\bz_n^\T]\bW_{\rm new}^\T\)\({}=\sum_n(\bx_n\)\({}-\bxbar)\E[\bz_n]^\T\bW_{\rm new}^\T\), whose diagonal equals that of \(\bW_{\rm new}\sum_n\E[\bz_n](\bx_n\)\({}-\bxbar)^\T\) (a matrix and its transpose have the same diagonal); the last two terms combine to \(-\bW_{\rm new}\frac1N\sum_n\E[\bz_n](\bx_n\)\({}-\bxbar)^\T\), giving (16.76). Over 300 iterations the log likelihood never decreases and the uniquenesses of the generating model are recovered to within 0.12. ∎

16.4 Nonlinear Latent Variable Models

See also the companion course, Section 12.4 (nonlinear latent variable models) and Advanced topics, lecture 1 (variational autoencoders); Section 2.4 of these notes (transformation of densities).

p. 522 Replace the linear map by a deep network. Start from a simple latent distribution

\[ p_{\bz}(\bz)=\N(\bz\given\bzero,\bI) \tag{16.77} \]

and set \(\bx=\bg(\bz,\bw)\), a network with weights and biases \(\bw\). Sampling is easy and non-iterative: draw \(\bz\), apply the network. To fit \(\bw\) by maximum likelihood we need \(p(\bx\given\bw)\). If \(\bg\) is invertible, the change of variables gives

\[ p_{\bx}(\bx)=p_{\bz}(\bz(\bx))\,|\det\bJ(\bx)| , \tag{16.78} \] \[ J_{ij}(\bx)=\frac{\partial z_i}{\partial x_j}, \tag{16.79} \]

which requires \(\bz=\bg^{-1}(\bx,\bw)\). For most networks the inverse does not exist (many-to-one maps), and if \(\dim\bz\ne\dim\bx\) the map cannot be invertible. Restricting to invertible networks of equal dimension leads to normalizing flows (Chapter 18).

Filling the gap 16.11: what goes wrong with (16.78) when \(\bg\) is not invertible or \(M<D\) pp. 522–523

The book says the formula "does not give a well-defined density". The two cases fail in different ways, and only one of them actually lacks a density.

Derivation

Invertible case. If \(\bg\) is a \(C^1\) bijection with non-singular Jacobian, then for any set \(B\), \(P(\bx\in B)=P(\bz\in\bg^{-1}(B))\)\({}=\int_{\bg^{-1}(B)}p_\bz(\bz)\,\d\bz\)\({}=\int_Bp_\bz(\bg^{-1}(\bx))\,|\det\partial\bg^{-1}/\partial\bx|\,\d\bx\) by the substitution \(\bz=\bg^{-1}(\bx)\), which is (16.78)–(16.79).

Many-to-one, \(M=D\). If \(\bg\) is \(C^1\) and each \(\bx\) has finitely many preimages \(\bz^{(k)}\), all with non-singular Jacobian, splitting the latent space into pieces on which \(\bg\) is invertible gives \(p_\bx(\bx)\)\({}=\sum_kp_\bz(\bz^{(k)})/|\det\partial\bg/\partial\bz(\bz^{(k)})|\). A density exists; what fails is that (16.78) needs a single inverse, and finding all preimages of a network output is impractical. (At points where the Jacobian is singular the density may be infinite.)

\(M<D\). The image \(\bg(\R^M)\) of a \(C^1\) (indeed locally Lipschitz) map is a set of Lebesgue measure zero in \(\R^D\). The distribution of \(\bx\) puts probability 1 on it, so it has no density with respect to Lebesgue measure: \(p(\bx)\) is "zero off the manifold and infinite on it". Any data point not exactly on the manifold has likelihood zero, and small changes of \(\bw\) do not change that, so the gradient is zero. Adding noise (16.80) convolves the singular distribution with a Gaussian, producing the smooth, everywhere-positive density \(p(\bx)\)\({}=\int\N(\bx\given\bg(\bz,\bw),\sigma^2\bI)p(\bz)\,\d\bz\), differentiable in \(\bw\). ∎

16.4.1 Nonlinear manifolds

pp. 522–524 With \(M<D\) the distribution of \(\bg(\bz,\bw)\) is confined to an \(M\)-dimensional manifold (Figure 16.11). This encodes the inductive bias that data such as natural images do not fill their space (Section 6.1.4), even if the manifold's shape and dimension are unknown. To get a density on the whole space we add noise, as in regression:

\[ p(\bx\given\bz,\bw)=\N(\bx\given\bg(\bz,\bw),\sigma^2\bI), \tag{16.80} \]

with a network with linear outputs, \(\bg\in\R^D\) (Figure 16.12, the two-node graph \(\bz\to\bx\), is not reproduced). Sampling takes three steps: draw \(\bz\) (Section 14.1.2), compute \(\bg(\bz,\bw)\), add Gaussian noise. The marginal is

\[ p(\bx)=\int p(\bz)p(\bx\given\bz)\,\d\bz . \tag{16.81} \]

Definition 16.6 (nonlinear latent variable model) pp. 522–524, (16.77), (16.80), (16.81)

\(\bz\sim\N(\bzero,\bI_M)\), \(\bx\given\bz\sim\N(\bg(\bz,\bw),\sigma^2\bI_D)\) with \(\bg\) a neural network with linear outputs. Probabilistic PCA is the case \(\bg(\bz,\bw)=\bW\bz+\bmu\).

Left: a square grid in the latent plane z1, z2 with a red point z. Right: the image of the grid under a small tanh network, a curved blue surface in three dimensions, with the red image point x.
Figure 16.11 (computed). A two-dimensional latent space mapped into three dimensions by a network with 8 tanh hidden units and fixed random weights: the square \([-1.5,1.5]^2\) becomes a curved surface, and the point \(\bz\) maps to \(\bx=\bg(\bz,\bw)\). Reproduces Bishop and Bishop (2024), Figure 16.11. Download: PDF · SVG
Left: the standard normal prior with three marked values of z. Then three heat maps of the conditional density of x given z equal to minus 1.5, 0 and 1.5: round blobs at the left, top and right of a circle. Last: the marginal density, a bright arc over the top of a dotted unit circle, fading towards the bottom.
Figure 16.13 (computed). A one-dimensional latent space and a two-dimensional data space, with \(\bg(z)=(\sin z,\cos z)\) and \(\sigma=0.3\): (a) the prior; (b) \(p(\bx\given z)\) for \(z=-1.5,0,1.5\), and the marginal \(p(\bx)\) (16.81) by quadrature over \(z\). The mean traces the unit circle (dotted), but most prior mass has \(|z|<2\), so the density is an arc, densest at the top. Reproduces Bishop and Bishop (2024), Figure 16.13. Download: PDF · SVG
▶ DemoThe book's circle model, and the posterior of any pointThe density of Figure 16.13 with adjustable \(\sigma\); click a point to see which \(z\) explain it.

16.4.2 Likelihood function

pp. 524–525 The likelihood

\[ p(\bx\given\bw)=\int p(\bx\given\bz,\bw)p(\bz)\,\d\bz=\int\N(\bx\given\bg(\bz,\bw),\sigma^2\bI)\N(\bz\given\bzero,\bI)\,\d\bz \tag{16.82} \]

is intractable: both factors are Gaussian, but \(\bg\) is nonlinear. One could sample the prior,

\[ p(\bx\given\bw)\simeq\frac1K\sum_{i=1}^Kp(\bx\given\bz_i,\bw),\qquad\bz_i\sim p(\bz), \tag{16.83} \]

which treats the model as a mixture of \(K\) Gaussians with weights \(1/K\) and is exact as \(K\to\infty\). But the \(K\) needed is far too large. The book's example (Figure 16.14, from Doersch, 2016) shows why: under a Gaussian \(p(\bx\given\bz)\) the likelihood falls off with squared distance, and squared distance ranks a visibly damaged digit closer to the original than a perfect copy shifted by half a pixel. A \(\sigma\) small enough to reject the damaged digit rejects the shifted one too, so only latent samples that reproduce \(\bx\) almost pixel for pixel contribute, and they are rare.

Three images of a handwritten two in white on black: the original, a copy with a two-pixel gap cut through its diagonal stroke, and a copy shifted half a pixel down and right, slightly blurred; squared distances 5.47 and 18.02 are printed under the second and third.
Figure 16.14 (computed; the book reprints images from Doersch, 2016). The same phenomenon with an MNIST two (pixel values in \([0,1]\)): (a) the original; (b) a two-pixel gap cut through the stroke, squared distance 5.47 from (a); (c) the original shifted half a pixel down and to the right by bilinear interpolation, squared distance 18.02. The good digit (c) is three times further from (a) than the bad one (b). (The book's values, 0.0387 and 0.2693, come from different images and a different normalisation.) Reproduces Bishop and Bishop (2024), Figure 16.14. Download: PDF · SVG

Result 16.15 (the Monte Carlo likelihood (16.83): unbiased, biased in log, and exponentially costly in \(M\)) pp. 524–525

Let \(\widehat p_K\)\({}=\frac1K\sum_ip(\bx\given\bz_i)\) with \(\bz_i\sim p(\bz)\) i.i.d., and \(\rho=\E[p(\bx\given\bz)^2]/p(\bx)^2-1\).

  1. \(\E[\widehat p_K]=p(\bx)\) and \(\var[\widehat p_K]/p(\bx)^2=\rho/K\); so \(K\approx\rho/\varepsilon^2\) samples give relative error \(\varepsilon\).
  2. \(\E[\ln\widehat p_K]\le\ln p(\bx)\) (Jensen), and \(\E[\ln\widehat p_K]\)\({}=\ln p(\bx)-\rho/(2K)+o(1/K)\).
  3. For Gaussian noise (16.80), if \(\bx=\bg(\bz^\star)\) lies on the manifold at a unique \(\bz^\star\) with \(\bJ=\partial\bg/\partial\bz\) of full rank \(M\), then as \(\sigma\to0\) \[ 1+\rho\approx\frac{|\bJ^\T\bJ|^{1/2}}{p(\bz^\star)\,(2\sqrt\pi\,\sigma)^M}, \] so the samples needed grow like \(\sigma^{-M}\): exponentially in the latent dimension.
  4. Sampling \(\bz_i\) from a \(q(\bz)\) close to the posterior and averaging \(p(\bx,\bz_i)/q(\bz_i)\) is unbiased with zero variance when \(q=p(\bz\given\bx)\); and \(\E\ln\) of this importance-weighted estimate lies between the ELBO \(\L(q)\) and \(\ln p(\bx)\) (Burda, Grosse and Salakhutdinov, 2016).

Filling the gap 16.12: how many samples does (16.83) need? p. 525, "the value of \(K\) needed for effective training will typically be far too high"

Derivation

(1)–(2). The terms \(p(\bx\given\bz_i)\) are i.i.d. with mean \(\int p(\bx\given\bz)p(\bz)\d\bz=p(\bx)\), so the average is unbiased with variance \(\var[p(\bx\given\bz)]/K\). Jensen's inequality for the concave logarithm gives \(\E\ln\widehat p_K\le\ln\E\widehat p_K\). For the expansion write \(\widehat p_K=p(1+\delta)\) with \(\E\delta=0\), \(\E\delta^2=\rho/K\): \(\ln(1+\delta)\)\({}=\delta-\delta^2/2+O(\delta^3)\), and the third moment of an average is \(O(K^{-2})\). (Training with \(\ln\widehat p_K\) therefore maximises a biased objective; the bias is largest exactly when \(\rho\) is large.)

(3). For a Gaussian, \(\N(\bx\given\bg,\sigma^2\bI)^2\)\({}=(4\pi\sigma^2)^{-D/2}\N(\bx\given\bg,\tfrac{\sigma^2}2\bI)\), so \(\E[p(\bx\given\bz)^2]\)\({}=(4\pi\sigma^2)^{-D/2}p_{\sigma/\sqrt2}(\bx)\), where \(p_s\) denotes the marginal with noise \(s\). Laplace's method: near \(\bz^\star\), \(\Vert\bx-\bg(\bz)\Vert^2\)\({}\approx(\bz-\bz^\star)^\T\bJ^\T\bJ(\bz\)\({}-\bz^\star)\), and \[ p_s(\bx)\approx p(\bz^\star)(2\pi s^2)^{-D/2}\int e^{-(\bz-\bz^\star)^\T\bJ^\T\bJ(\bz-\bz^\star)/2s^2}\d\bz=p(\bz^\star)(2\pi s^2)^{-(D-M)/2}|\bJ^\T\bJ|^{-1/2}. \] Dividing \((4\pi\sigma^2)^{-D/2}p_{\sigma/\sqrt2}(\bx)\) by \(p_\sigma(\bx)^2\), the powers of \(\sigma\) combine to \(\sigma^{-D-(D-M)+2(D-M)}=\sigma^{-M}\) and the constants to \(2^{-M}\pi^{-M/2}\), which is the formula. Intuitively, \(1+\rho\) is about one over the prior probability of the region of latent space that explains \(\bx\), a region of width \(\propto\sigma\) in each of \(M\) directions. For the circle model at \(z^\star=0.5\), \(\sigma=0.1\): \(|\bJ^\T\bJ|=1\), \(p(z^\star)=0.352\), and the formula gives \(\rho\approx7.01\) against 7.04 by quadrature and 7.02 measured from 20 000 repetitions; the log estimate with \(K=50\) is biased by \(-0.085\) (asymptotic value \(-0.070\)). Figure 16.S5(a) shows \(K\propto\sigma^{-1}\) for \(M=1\) and \(\propto\sigma^{-2}\) for a two-dimensional latent version; an image model with \(M=20\) and small \(\sigma\) would need astronomically many samples.

(4). \(p(\bx)\)\({}=\int q(\bz)\frac{p(\bx,\bz)}{q(\bz)}\d\bz\), so averaging the weights \(p(\bx,\bz_i)/q(\bz_i)\) is unbiased; if \(q=p(\bz\given\bx)\) every weight equals \(p(\bx)\). By Jensen, \(\E\ln(\text{weight})=\L(q)\)\({}\le\E\ln\widehat p^{\,q}_K\le\ln p(\bx)\). In Figure 16.S5(b), with \(q\) the best Gaussian (widened by 1.5) the standard deviation of \(\ln\widehat p\) drops from 0.43 to 0.046 at \(K=100\). Learning such a \(q\) for every \(\bx\) with a network is the variational autoencoder (Chapter 19). ∎

Left: on log-log axes, the number of prior samples needed for ten percent relative error against sigma: a red line of slope minus one for the one-dimensional latent circle, rising to about four thousand at sigma 0.02, and a blue line of slope minus two for a two-dimensional latent cylinder, rising to over one hundred thousand. Right: histograms of the log-likelihood estimate from 4000 repetitions: a wide red histogram from prior samples with a long left tail, and a narrow blue spike from importance samples, both near the exact value 1.032.
Figure 16.S5 (our own). (a) Prior samples needed by (16.83) for 10% relative error at a point on the manifold, from the exact variance by quadrature: \(K\propto\sigma^{-1}\) for the circle model (\(M=1\)) and \(\propto\sigma^{-2}\) for \(\bg(z_1,z_2)=(\sin z_1,\cos z_1,z_2)\) (\(M=2\)); dotted lines have slopes \(-1\) and \(-2\). (b) 4000 estimates \(\ln\widehat p\) with \(K=100\), \(\sigma=0.05\): from prior samples (red; spread 0.43, long left tail, mean below the truth) and from importance samples of a Gaussian \(q\) fitted by the ELBO (blue; spread 0.046). Download: PDF · SVG

Training anyway, in low dimension. With \(M=1\) the integral (16.82) can be done by quadrature, and a small network can be trained by maximum likelihood directly. Figure 16.S7 does this on three two-dimensional data sets and compares with probabilistic PCA, the linear special case; the demo trains the same network live and contrasts the grid with Monte Carlo samples.

Two rows of three density maps. Top: a tanh network with a one-dimensional latent variable fitted to an arc, a ring and a spiral; its red curve follows each data set and the density hugs the points, with a small gap at the top of the ring. Bottom: probabilistic PCA with one component on the same data: a straight red line and a broad elliptical density that ignores the shape.
Figure 16.S7 (our own). Top: \(\bg(z,\bw)\)\({}=\mathbf V\tanh(\mathbf az+\mathbf b)\)\({}+\mathbf c\) with 16 hidden units, \(\sigma=0.15\), trained by Adam on the likelihood (16.82) computed with a 64-point grid over \(z\) (3000 steps; blue points: 200 data). Bottom: probabilistic PCA with \(M=1\) (16.46)–(16.47). Mean log likelihood per point: arc \(-0.57\) against \(-1.62\), ring \(-0.96\) against \(-2.13\), spiral \(-1.01\) against \(-1.76\). A continuous image of the real line cannot close the ring without a gap. Download: PDF · SVG
▶ DemoTrain a network \(\bg(z,\bw)\) by maximum likelihoodAdam in the browser on the arc (preset 3) and the ring (preset 4); the training objective, the learned curve and the posterior of any point.
▶ DemoMonte Carlo with \(K=4\): noisy and biasedTraining with (16.83) and four fresh prior samples per step reaches \(-4.2\) nats per point, against \(-0.42\) with the grid; the readout compares prior and importance samples.

16.4.3 Discrete data

p. 526 For independent binary variables the network outputs Bernoulli probabilities,

\[ p(\bx\given\bz,\bw)=\prod_{i=1}^Dg_i(\bz,\bw)^{x_i}\big(1-g_i(\bz,\bw)\big)^{1-x_i}, \tag{16.84} \]

with \(g_i=\sigma(a_i(\bz,\bw))\) the logistic sigmoid of the pre-activation \(a_i\). For one-hot categorical variables,

\[ p(\bx\given\bz,\bw)=\prod_{i=1}^Dg_i(\bz,\bw)^{x_i}, \tag{16.85} \] \[ g_i(\bz,\bw)=\frac{\exp(a_i(\bz,\bw))}{\sum_j\exp(a_j(\bz,\bw))}, \tag{16.86} \]

and mixed data use products of such factors. Continuous quantities are usually stored discretised, e.g. 8-bit intensities \(\{0,\dots,255\}\); a flexible density model can then collapse onto those values and its likelihood can grow without limit. Dequantisation adds noise, typically uniform over the interval between successive values, replacing each training value by a random point of its interval (Figure 16.15).

Left: a distribution on 0, 1 and 2 shown as three thin bars of heights 0.25, 0.5 and 0.25. Right: the dequantised density, a step function equal to 0.25 on the interval from 0 to 1, 0.5 from 1 to 2 and 0.25 from 2 to 3.
Figure 16.15 (computed). (a) A distribution on \(\{0,1,2\}\); (b) the density of \(x+u\), \(u\sim\Unif(0,1)\): constant on each unit interval, with the interval's probability as its height. Reproduces Bishop and Bishop (2024), Figure 16.15. Download: PDF · SVG

Result 16.16 (why dequantisation works) p. 526, Figure 16.15

  1. Without it, a continuous model can have unbounded likelihood on discrete data: Gaussians of width \(s\) centred on the data values give \(\ln p\to+\infty\) as \(s\to0\).
  2. For any density \(p\) on \(\R^D\) define the discrete model \(P(\bx)=\int_{[0,1)^D}p(\bx+\bu)\,\d\bu\) on integer vectors. Then \(\E_{\bu\sim\Unif[0,1)^D}[\ln p(\bx+\bu)]\)\({}\le\ln P(\bx)\le0\). So the dequantised log likelihood is a lower bound on the log probability of a proper discrete model, bounded above by 0; equality holds when \(p\) is constant on each cell.

Filling the gap 16.13: dequantisation as a lower bound p. 526, "this makes it less likely that the model will discover a pathological solution"

Derivation

(1) For data \(x_n\in\{0,1,2,\dots\}\) and the mixture \(p_s(x)=\frac1K\sum_{k}\N(x\given k,s^2)\) over the \(K\) distinct values, each data point contributes at least \(\ln\{\frac1K\N(x_n\given x_n,s^2)\}\)\({}=-\ln K-\ln(s\sqrt{2\pi})\to+\infty\). A direct computation shows the log likelihood of seven integers rising from 0.0 to 16.1 to 32.2 as \(s\) goes from 0.1 to 0.01 to 0.001.

(2) \(\bu\mapsto p(\bx+\bu)\) is a density times 1 on the unit cube, so by Jensen's inequality for the concave logarithm and a uniform \(\bu\), \(\E_\bu[\ln p(\bx+\bu)]\)\({}\le\ln\E_\bu[p(\bx+\bu)]\)\({}=\ln\int_{[0,1)^D}p(\bx+\bu)\,\d\bu\)\({}=\ln P(\bx)\). The cells \(\bx+[0,1)^D\) partition \(\R^D\), so \(\sum_\bx P(\bx)=1\) and \(P(\bx)\le1\). Equality in Jensen holds iff \(p(\bx+\bu)\) is constant in \(\bu\). Training on dequantised samples is thus stochastic maximisation of a lower bound on \(\sum_n\ln P(\bx_n)\), which cannot exceed 0, so the collapse in (1) gains nothing. ∎

16.4.4 Four approaches to generative modelling

See also the companion course, Advanced topics: variational autoencoders (lecture 1), normalizing flows (lecture 2) and diffusion models (lecture 4).

p. 527 Nonlinear latent variable models can approximate essentially any distribution and sample in one pass, but the likelihood is the obstacle. The rest of the book follows four ways around it:

ApproachWhat changesLikelihoodSamplingBook
Generative adversarial networks\(M<D\) allowed, no likelihood; a second network (discriminator) provides the training signalnoneone passChapter 17
Variational autoencodersa second network approximates \(p(\bz\given\bx)\); train on the ELBO (16.58)lower boundone passChapter 19
Normalizing flows\(M=D\) and \(\bg\) invertible; use (16.78)exactone passChapter 18
Diffusion modelsa network learns to undo many small noising stepsboundmany passesChapter 20

GAN training can be brittle but gives high-quality samples; VAE training is more robust but the best sample quality is harder to reach; flows are restricted in form; diffusion models give state-of-the-art results at the price of many network evaluations per sample.

Summary: errors and imprecisions found in the chapter (first printing)

  • p. 495: MNIST digits are \(28\times28\) images, not "\(64\times64\)" (the book's own Figure 16.3 caption says \(28\times28\)).
  • (16.57) and (16.60): \(\L(\bw)\) should be \(\L(q,\bw)\), as in (16.58); the bound depends on \(q\).
  • p. 510: with \(\bR=\bI\) the columns of \(\bW_{\rm ML}\) are the eigenvectors scaled by \((\lambda_i-\sigma^2)^{1/2}\), not by \(\lambda_i-\sigma^2\) (from (16.46); checked: \(\bu_i^\T\bC\bu_i=\lambda_i\) only with the square root).
  • p. 519: the definition given for "missing at random" (missingness independent of observed and unobserved values) is that of missing completely at random; EM remains valid under the weaker missing-at-random condition (Rubin, 1976).
  • pp. 498, 506 (cross-references): the EM algorithm for probabilistic PCA is in Section 16.3.1; Section 16.3.2 is its zero-noise limit.
  • Exercise 16.13, (16.88): the reconstruction needs \(+\bxbar\) unless \(\bx\) is centred.
  • Exercise 16.17: "\(p(\bz)=\N(\bx\given\bzero,\bI)\)" should read \(\N(\bz\given\bzero,\bI)\).
  • p. 514 (imprecision): a component-wise rescaling of the data is absorbed by \(\bPsi\) and by the rows of \(\bW\) (Result 16.9).
  • p. 522 (imprecision): for a many-to-one \(\bg\) with \(M=D\) a density still exists (a sum over preimages); the difficulty is evaluating it. Only for \(M<D\) is there no density (Filling the gap 16.11).
  • Section 16.2.6 (terminology): the model is the linear dynamical system; the Kalman filter is the inference algorithm for it.

Exercises

All 26 exercises of Chapter 16 (Bishop and Bishop, 2024, pp. 527–531), restated in my own words, with complete solutions (hidden). Stars give the book's difficulty. The official solutions manual stops at Chapter 10, so these solutions are my own; most exercises correspond to exercises of Bishop (2006), Chapter 12, and the companion course's solution is linked.

  1. Exercise 16.1 (★★). Show by induction on \(M\) that the \(M\)-dimensional projection maximising the projected variance is given by the eigenvectors of \(\bS\) with the \(M\) largest eigenvalues: given the result for \(M\), use Lagrange multipliers for normalisation and orthogonality to \(\bu_1,\dots,\bu_M\) to show that \(\bu_{M+1}\) is an eigenvector, then that its eigenvalue must be \(\lambda_{M+1}\).

    Solution

    The step is written out in Filling the gap 16.1: stationarity gives \(2\bS\bu-2\lambda\bu+\sum_j\eta_j\bu_j\)\({}=\bzero\); multiplying by \(\bu_k^\T\) and using \(\bS\bu_k=\lambda_k\bu_k\), \(\bu_k^\T\bu=0\), gives \(\eta_k=0\), so \(\bS\bu=\lambda\bu\) with \(\bu\perp\bu_1,\dots,\bu_M\). The variance \(\bu^\T\bS\bu=\lambda\) is then maximised by the largest eigenvalue among the remaining eigenvectors, \(\lambda_{M+1}\). The base case is (16.5)–(16.6). That the greedy choice is also optimal among all \(M\)-dimensional subspaces is Result 16.1. (Companion Exercise 12.1.)

  2. Exercise 16.2 (★★). Minimise (16.15) under the orthonormality constraints using a symmetric matrix \(\bH\) of multipliers, (16.87); show that the solution satisfies \(\bS\widehat\bU=\widehat\bU\bH\), and that every solution gives the same \(J\) as one whose columns are eigenvectors.

    Solution

    See Filling the gap 16.2: only the symmetric part of \(\bH\) enters (16.87); the gradient \(2\bS\widehat\bU-2\widehat\bU\bH\) vanishes iff \(\bS\widehat\bU=\widehat\bU\bH\); then \(\bH=\widehat\bU^\T\bS\widehat\bU\), and with \(\bH=\bPsi\Lambda\bPsi^\T\) the columns of \(\widehat\bU\bPsi\) are orthonormal eigenvectors and \(J=\Tr\bH=\Tr\Lambda\). The minimum discards the \(D-M\) smallest eigenvalues. (Companion Exercise 12.2.)

  3. Exercise 16.3 (★). Show that (16.30) has unit length when \(\bv_i\) does.

    Solution

    \(\Vert\bX^\T\bv_i\Vert^2\)\({}=\bv_i^\T\bX\bX^\T\bv_i\)\({}=\bv_i^\T(N\lambda_i\bv_i)=N\lambda_i\) by (16.28), so \(\Vert\bu_i\Vert^2\)\({}=N\lambda_i/(N\lambda_i)=1\). (Needs \(\lambda_i>0\). Companion Exercise 12.3.)

  4. Exercise 16.4 (★). Replace the prior (16.31) by \(\N(\bz\given\mathbf m,\Sig)\). Show that, after redefining the parameters, the marginal of \(\bx\) is the same family as before.

    Solution

    Write \(\bz=\mathbf m+\Sig^{1/2}\bz'\) with \(\bz'\sim\N(\bzero,\bI)\). Then \(\bx\)\({}=\bW\Sig^{1/2}\bz'+(\bmu+\bW\mathbf m)\)\({}+\beps\), a standard PPCA with \(\bW'=\bW\Sig^{1/2}\), \(\bmu'=\bmu+\bW\mathbf m\): marginal \(\N(\bmu+\bW\mathbf m,\bW\Sig\bW^\T\)\({}+\sigma^2\bI)\). Every pair \((\bW',\bmu')\) arises (take \(\bW=\bW'\Sig^{-1/2}\), \(\bmu=\bmu'-\bW\mathbf m\)), so the family of marginals is unchanged. (Result 16.5(4); companion Exercise 12.4.)

  5. Exercise 16.5 (★★). If \(\bx\sim\N(\bmu,\Sig)\) in \(\R^D\) and \(\by=\bA\bx+\mathbf b\) with \(\bA\) an \(M\times D\) matrix, show that \(\by\) is Gaussian, find its mean and covariance, and discuss \(M<D\), \(M=D\), \(M>D\).

    Solution

    The moment generating function is \(\E e^{\mathbf t^\T\by}\)\({}=e^{\mathbf t^\T\mathbf b}\E e^{(\bA^\T\mathbf t)^\T\bx}\)\({}=\exp\{\mathbf t^\T(\bA\bmu+\mathbf b)+\frac12\mathbf t^\T\bA\Sig\bA^\T\mathbf t\}\), that of \(\N(\bA\bmu+\mathbf b,\bA\Sig\bA^\T)\). For \(M<D\) with \(\bA\) of full row rank, \(\bA\Sig\bA^\T\) is positive definite (\(\mathbf t^\T\bA\Sig\bA^\T\mathbf t\)\({}=(\bA^\T\mathbf t)^\T\Sig(\bA^\T\mathbf t)\)\({}>0\) for \(\mathbf t\ne\bzero\)) and \(\by\) has a density; marginalisation is the case of a selection matrix. For \(M=D\), \(\by\) has a density iff \(\bA\) is invertible (then also by the change of variables (16.78)). For \(M>D\), \(\operatorname{rank}\bA\Sig\bA^\T\le D\)\({}<M\): the Gaussian is degenerate, concentrated on the affine subspace \(\mathbf b+\operatorname{range}\bA\), and has no density on \(\R^M\), which is the singular case of Filling the gap 16.11. (Companion Exercise 12.5.)

  6. Exercise 16.6 (★★). Derive (16.35) from the general formulae (2.122)–(2.123) for the mean and covariance in terms of conditional moments.

    Solution

    \(\E[\bx]=\E_\bz[\E[\bx\given\bz]]\)\({}=\E[\bW\bz+\bmu]=\bmu\) and \(\cov[\bx]\)\({}=\E_\bz[\cov[\bx\given\bz]]\)\({}+\cov_\bz[\E[\bx\given\bz]]\)\({}=\sigma^2\bI+\bW\cov[\bz]\bW^\T\)\({}=\bW\bW^\T+\sigma^2\bI\). Gaussianity: \(\bx\) is an affine function of the jointly Gaussian \((\bz,\beps)\) (Exercise 16.5). (Companion Exercise 12.7.)

  7. Exercise 16.7 (★). Draw the directed graph of probabilistic PCA with each component of \(\bx\) as its own node, and check that it has the independence structure of the naive Bayes model.

    Solution

    Nodes: \(\bz\) (or its components), and \(x_1,\dots,x_D\); edges \(\bz\to x_i\) for every \(i\), plus parameter nodes \(\bw_i\) (row \(i\) of \(\bW\)), \(\mu_i\) and \(\sigma^2\) pointing into \(x_i\); no edges among the \(x_i\). Every path between \(x_i\) and \(x_j\) passes through \(\bz\) tail-to-tail, so it is blocked when \(\bz\) is observed: \(x_i\perp x_j\given\bz\), as the factorisation \(p(\bx\given\bz)\)\({}=\prod_i\N(x_i\given\bw_i^\T\bz\)\({}+\mu_i,\sigma^2)\) confirms. This is the naive Bayes structure (Section 11.2.3) with a continuous "class" \(\bz\). (Companion Exercise 12.6.)

  8. Exercise 16.8 (★★). Using (3.100), show that the posterior of probabilistic PCA is (16.43).

    Solution

    (3.100) states that for \(p(\bz)\)\({}=\N(\bmu_z,\boldsymbol\Lambda^{-1})\) and \(p(\bx\given\bz)\)\({}=\N(\bA\bz+\mathbf b,\bL^{-1})\), \(p(\bz\given\bx)\)\({}=\N(\Sig\{\bA^\T\bL(\bx-\mathbf b)+\boldsymbol\Lambda\bmu_z\},\Sig)\), \(\Sig\)\({}=(\boldsymbol\Lambda+\bA^\T\bL\bA)^{-1}\). Substitute \(\bmu_z=\bzero\), \(\boldsymbol\Lambda=\bI\), \(\bA=\bW\), \(\mathbf b=\bmu\), \(\bL=\sigma^{-2}\bI\): \(\Sig=(\bI+\sigma^{-2}\bW^\T\bW)^{-1}\)\({}=\sigma^2\bM^{-1}\), mean \(\sigma^2\bM^{-1}\sigma^{-2}\bW^\T(\bx\)\({}-\bmu)\)\({}=\bM^{-1}\bW^\T(\bx-\bmu)\). (Companion Exercise 12.8.)

  9. Exercise 16.9 (★). Show that maximising (16.44) over \(\bmu\) gives \(\bmu_{\rm ML}=\bxbar\).

    Solution

    \(\partial/\partial\bmu\) of (16.44) is \(\sum_n\bC^{-1}(\bx_n-\bmu)\)\({}=\bC^{-1}N(\bxbar-\bmu)\), zero iff \(\bmu=\bxbar\) since \(\bC\) is invertible. (Companion Exercise 12.9.)

  10. Exercise 16.10 (★★). Using second derivatives, show that \(\bmu=\bxbar\) is the unique maximum.

    Solution

    The Hessian of (16.44) with respect to \(\bmu\) is \(-N\bC^{-1}\), negative definite and independent of \(\bmu\). The log likelihood is therefore a strictly concave quadratic in \(\bmu\), whose only stationary point \(\bxbar\) is the global maximum. (Checked numerically; companion Exercise 12.10.)

  11. Exercise 16.11 (★★). Show that as \(\sigma^2\to0\) the posterior mean becomes an orthogonal projection onto the principal subspace, as in PCA.

    Solution

    As \(\sigma^2\to0\), \(\bM\to\bW^\T\bW\) and \(\E[\bz\given\bx]\)\({}\to(\bW^\T\bW)^{-1}\bW^\T(\bx-\bxbar)\) (16.51), the least-squares coordinates of \(\bx-\bxbar\) in the basis given by the columns of \(\bW\); mapped back, \(\bW(\bW^\T\bW)^{-1}\bW^\T(\bx-\bxbar)\) is the orthogonal projector onto \(\span\bW\), the principal subspace, applied to \(\bx-\bxbar\). (With \(\bW_{\rm ML}\) also depending on \(\sigma^2\), its column space stays \(\span\bU_M\), so the limit is the same; Result 16.7; companion Exercise 12.11.)

  12. Exercise 16.12 (★★). For \(\sigma^2>0\), show that the posterior mean is shrunk towards the origin relative to the orthogonal projection.

    Solution

    By Result 16.7, in the eigenbasis (with \(\bR=\bI\)) each coordinate of the posterior mean is the coordinate of the orthogonal projection (16.51) times \((\lambda_j-\sigma^2)/\lambda_j\in[0,1)\). For general \(\bR\) both vectors are rotated by \(\bR^\T\), which preserves lengths, so \(\Vert\E[\bz\given\bx]\Vert\)\({}<\Vert(\bW^\T\bW)^{-1}\bW^\T(\bx\)\({}-\bxbar)\Vert\) whenever the projection is non-zero. (Checked numerically; companion Exercise 12.12.)

  13. Exercise 16.13 (★★). Show that the least-squares optimal reconstruction from the posterior mean is (16.88).

    Solution

    Look for \(\bxt=\bW\mathbf c+\bxbar\) minimising \(\Vert\bx-\bxt\Vert^2\): \(\mathbf c\)\({}=(\bW^\T\bW)^{-1}\bW^\T(\bx-\bxbar)\). By (16.49), \(\bW^\T(\bx-\bxbar)=\bM\E[\bz\given\bx]\), so \(\bxt\)\({}=\bW(\bW^\T\bW)^{-1}\bM\E[\bz\given\bx]\)\({}+\bxbar\), the orthogonal projection onto the principal subspace, identical to the PCA reconstruction (16.20) (Result 16.7). The book's (16.88) omits \(\bxbar\). (Companion Exercise 12.13.)

  14. Exercise 16.14 (★). Verify that (16.52) gives the count of a general covariance for \(M=D-1\) and of an isotropic covariance for \(M=0\).

    Solution

    \(M=D-1\): \(D(D-1)+1-\frac{(D-1)(D-2)}2\)\({}=\frac{2D^2-2D+2-D^2+3D-2}2\)\({}=\frac{D(D+1)}2\). \(M=0\): \(0+1-0=1\). (Confirmed by Jacobian ranks in Result 16.8; companion Exercise 12.14.)

  15. Exercise 16.15 (★). Find the number of independent parameters of factor analysis.

    Solution

    \(\bW\) has \(DM\) entries, \(\bPsi\) has \(D\), and rotations remove \(M(M-1)/2\): \(DM+D-M(M-1)/2\) for the covariance, plus \(D\) for \(\bmu\). The count is meaningful only while it does not exceed \(D(D+1)/2\) (otherwise the model is not identifiable). (Result 16.8: rank 20 for \(D=7\), \(M=2\); companion Exercise 12.18.)

  16. Exercise 16.16 (★★). Show that factor analysis is invariant under rotations of the latent coordinates.

    Solution

    Replace \(\bz\) by \(\bz'=\bR^\T\bz\) with \(\bR\) orthogonal; \(\bz'\sim\N(\bzero,\bR^\T\bR)\)\({}=\N(\bzero,\bI)\) and \(\bW\bz=\bW\bR\bz'\), so the model with \(\bW\bR\) generates the same \(\bx\). Equivalently, \(\bW\bR(\bW\bR)^\T+\bPsi=\bW\bW^\T+\bPsi\): the marginal and the likelihood are unchanged. (Checked numerically; companion Exercise 12.19.)

  17. Exercise 16.17 (★★). For \(p(\bz)=\N(\bz\given\bzero,\bI)\) and \(p(\bx\given\bz)=\N(\bW\bz+\bmu,\bPhi)\) with \(\bPhi\) symmetric positive definite, show that if \((\bmu,\bW,\bPhi)_{\rm ML}\) fits \(\{\bx_n\}\) then \((\bA\bmu,\bA\bW,\bA\bPhi\bA^\T)\) fits \(\{\bA\bx_n\}\); and that the model's form is kept (i) for diagonal \(\bA\) and diagonal \(\bPhi\) (factor analysis), (ii) for orthogonal \(\bA\) and \(\bPhi=\sigma^2\bI\) (PPCA).

    Solution

    See Result 16.9: the transformed log likelihood equals the original minus \(N\ln|\det\bA|\), and the parameter map is a bijection when it preserves the constraint on \(\bPhi\); (i) \(\bA\bPsi\bA^\T=\diag(a_i^2\psi_i)\) is diagonal; (ii) \(\bA\sigma^2\bI\bA^\T=\sigma^2\bI\). Factor analysis is therefore covariant under rescaling of each variable, PPCA under rotations of data space (as is PCA). (Note the typo \(\N(\bx\given\bzero,\bI)\) in the book's statement. Companion Exercise 12.25.)

  18. Exercise 16.18 (★). Verify (16.57)–(16.59) using the product rule (16.89).

    Solution

    Filling the gap 16.7, part (1): insert \(p(\bx,\bz\given\bw)\)\({}=p(\bz\given\bx,\bw)p(\bx\given\bw)\) in (16.58) and use \(\int q=1\). (Companion Exercise 9.24, the discrete version.)

  19. Exercise 16.19 (★). Show that for i.i.d. data the ELBO has the form (16.63).

    Solution

    Filling the gap 16.7, part (2): with \(q(\bZ)=\prod_nq(\bz_n)\), the log ratio is a sum over \(n\) and each term integrates against its own factor.

  20. Exercise 16.20 (★★). Draw the graphical model of a mixture of probabilistic PCA models, each with its own \(\bW\), \(\bmu\), \(\sigma^2\); then the graph in which these are shared by all components.

    Solution

    Inside a plate over \(n=1,\dots,N\): a discrete node \(s_n\) (the component, with parent \(\boldsymbol\pi\) outside the plate), a continuous node \(\bz_n\) (no parents, prior \(\N(\bzero,\bI)\)), and \(\bx_n\) with parents \(s_n\) and \(\bz_n\). Outside the plate, a plate over \(k=1,\dots,K\) holds \(\bW_k,\bmu_k,\sigma_k^2\), all pointing into \(\bx_n\); then \(p(\bx_n\given s_n=k,\bz_n)\)\({}=\N(\bW_k\bz_n+\bmu_k,\sigma_k^2\bI)\). If the parameters are shared, the \(K\)-plate disappears and \(\bW,\bmu,\sigma^2\) point into \(\bx_n\) directly; the edge \(s_n\to\bx_n\) then carries no information (\(p(\bx_n\given s_n,\bz_n)\) does not depend on \(s_n\)) and can be deleted: the mixture collapses to a single PPCA model with \(s_n\) disconnected. Sharing only \(\bW\) and \(\sigma^2\) but not \(\bmu_k\) would give a genuine mixture of shifted copies. (Companion Exercise 12.23.)

  21. Exercise 16.21 (★★). Derive the M step (16.68)–(16.69) by maximising (16.65).

    Solution

    Filling the gap 16.8. (Companion Exercise 12.15.)

  22. Exercise 16.22 (★★★). Derive EM for probabilistic PCA when values are missing at random, treating both the \(\bz_n\) and the missing entries as latent; show that it reduces to Section 16.3.1 when nothing is missing.

    Solution

    Result 16.13 and its proof: the posterior factorises as \(p(\bz_n\given\bx_{n,o})p(\bx_{n,m}\given\bz_n)\); the E step computes the moments of \(\bz_n\) from the observed rows and fills in \(\E[x_{ni}\widetilde\bz_n]\) and \(\E[x_{ni}^2]\) for missing entries; the M step is a least-squares problem per row \((\bw_i,\mu_i)\) and an average for \(\sigma^2\). Without missing values \(\sum_n\E[\bz_n]=\bzero\) when \(\bmu=\bxbar\), so \(\bmu\) stays at \(\bxbar\) and the updates are (16.66)–(16.69) (checked to \(10^{-10}\)). (Companion Exercise 12.16.)

  23. Exercise 16.23 (★★). For \(J=\sum_n\Vert\bx_n-\bmu-\bW\bz_n\Vert^2\) (16.90), show that minimising over \(\bmu\) leads to the same problem with centred \(\bx_n-\bxbar\) and \(\bz_n-\bar\bz\); that minimising over the \(\bz_n\) is the E step (16.70); and over \(\bW\) the M step (16.71).

    Solution

    \(\partial J/\partial\bmu\)\({}=-2\sum_n(\bx_n-\bmu-\bW\bz_n)=\bzero\) gives \(\bmu=\bxbar-\bW\bar\bz\); substituting, \(\bx_n-\bmu-\bW\bz_n\)\({}=(\bx_n-\bxbar)-\bW(\bz_n-\bar\bz)\). The other two parts are Result 16.14(1) with its proof in Filling the gap 16.9. (Companion Exercise 12.17.)

  24. Exercise 16.24 (★★). Derive the E step (16.72)–(16.73) of factor analysis (using Exercise 16.26 to set \(\bmu=\bxbar\)).

    Solution

    Filling the gap 16.10, E step: complete the square in \(\bz\) to get precision \(\bI+\bW^\T\bPsi^{-1}\bW=\bG^{-1}\) and mean \(\bG\bW^\T\bPsi^{-1}(\bx-\bxbar)\); then \(\E[\bz\bz^\T]=\bG+\E[\bz]\E[\bz]^\T\). (Companion Exercise 12.21.)

  25. Exercise 16.25 (★★). Write the expected complete-data log likelihood of factor analysis and derive the M step (16.75)–(16.76).

    Solution

    Filling the gap 16.10, M step: the expectation is displayed there; the \(\bW\)-gradient gives (16.75); the derivative in each \(\psi_i\), simplified with (16.75), gives (16.76). (Companion Exercise 12.22.)

  26. Exercise 16.26 (★★). Show that the only stationary point of the factor analysis log likelihood with respect to \(\bmu\) is \(\bxbar\), and that it is a maximum.

    Solution

    The log likelihood is (16.44) with \(\bC=\bW\bW^\T+\bPsi\), positive definite. Its gradient in \(\bmu\) is \(N\bC^{-1}(\bxbar-\bmu)\), zero only at \(\bxbar\), and its Hessian \(-N\bC^{-1}\) is negative definite everywhere: a strictly concave quadratic with unique maximum \(\bxbar\). (Companion Exercise 12.20.)

Demonstrations

Three interactive pages, each linked above where its topic arises. They reproduce the Python code number for number (largest differences \(8\times10^{-16}\) relative for the eigen-digits, \(7\times10^{-15}\) for the ICA run, \(2\times10^{-14}\) for the trained network and the ELBO). The companion course already has demonstrations of two-dimensional PCA and whitening, EM for PCA, Bayesian PCA, kernel PCA, the Kalman filter and the EM bound (listed above), so the pages here concentrate on what this chapter adds.

References

  1. Bishop, C. M. and Bishop, H. (2024). Deep Learning: Foundations and Concepts. Springer, Cham. Chapter 16, pp. 495–531. doi:10.1007/978-3-031-45468-4. Book website: www.bishopbook.com.
  2. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Chapters 12 and 13.
  3. Amari, S., Cichocki, A. and Yang, H. H. (1996). A new learning algorithm for blind signal separation. In Advances in Neural Information Processing Systems 8, 757–763.
  4. Anderson, T. W. (1963). Asymptotic theory for principal component analysis. Annals of Mathematical Statistics, 34(1), 122–148.
  5. Attias, H. (1999). Independent factor analysis. Neural Computation, 11(4), 803–851.
  6. Bell, A. J. and Sejnowski, T. J. (1995). An information-maximization approach to blind separation and blind deconvolution. Neural Computation, 7(6), 1129–1159.
  7. Burda, Y., Grosse, R. and Salakhutdinov, R. (2016). Importance weighted autoencoders. In International Conference on Learning Representations.
  8. Cardoso, J.-F. (1998). Blind signal separation: statistical principles. Proceedings of the IEEE, 86(10), 2009–2025.
  9. Comon, P. (1994). Independent component analysis, a new concept? Signal Processing, 36(3), 287–314.
  10. Doersch, C. (2016). Tutorial on variational autoencoders. arXiv:1606.05908.
  11. Golub, G. H. and Van Loan, C. F. (1996). Matrix Computations (3rd ed.). Johns Hopkins University Press.
  12. Hotelling, H. (1933). Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 24, 417–441 and 498–520.
  13. Hotelling, H. (1936). Relations between two sets of variates. Biometrika, 28, 321–377.
  14. Kalman, R. E. (1960). A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82(1), 35–45.
  15. Lawley, D. N. (1953). A modified method of estimation in factor analysis and some large sample results. In Uppsala Symposium on Psychological Factor Analysis, 35–42.
  16. Lee, T.-W., Girolami, M. and Sejnowski, T. J. (1999). Independent component analysis using an extended infomax algorithm for mixed subgaussian and supergaussian sources. Neural Computation, 11(2), 417–441.
  17. MacKay, D. J. C. (2003). Information Theory, Inference and Learning Algorithms. Cambridge University Press. Chapter 34.
  18. Pearson, K. (1901). On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 2(11), 559–572.
  19. Roweis, S. (1998). EM algorithms for PCA and SPCA. In Advances in Neural Information Processing Systems 10, 626–632.
  20. Rubin, D. B. (1976). Inference and missing data. Biometrika, 63(3), 581–592.
  21. Rubin, D. B. and Thayer, D. T. (1982). EM algorithms for ML factor analysis. Psychometrika, 47(1), 69–76.
  22. Sirovich, L. (1987). Turbulence and the dynamics of coherent structures. Quarterly of Applied Mathematics, 45(3), 561–590.
  23. Tipping, M. E. and Bishop, C. M. (1999). Probabilistic principal component analysis. Journal of the Royal Statistical Society, Series B, 61(3), 611–622.
  24. Zarchan, P. and Musoff, H. (2005). Fundamentals of Kalman Filtering: A Practical Approach (2nd ed.). AIAA.

Every numerical statement in these notes comes from ch16_continuous_latent_variables.py.