Lecture notes · Foundations of Deep Learning · Chapter 14

Sampling

Deep learning needs random samples all the time: to estimate expectations that have no closed form, to train models whose normalising constant is unknown, and to generate new data from a trained model. This chapter collects the tools. Section 14.1 turns uniform random numbers into samples from simple distributions and approximates expectations by rejection and importance sampling; Section 14.2 builds Markov chains whose long-run distribution is the target (Metropolis–Hastings, Gibbs, ancestral sampling); Section 14.3 introduces energy-based models, shows that their likelihood gradient is a difference between data and model expectations, and samples them with Langevin dynamics, a noisy gradient ascent on the log density.

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 (14.1, 14.3.2, ...) and every displayed equation that appears in the book carries the book's own equation number, e.g. (14.61). 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. Thirteen of the fourteen figures are reproduced by the Python code; most are schematic in the book and are computed here from explicit densities and simulations. Figure 14.12, a drawing of a Markov blanket, has no data and is not reproduced. Six supplementary figures (14.S1 to 14.S6, 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 14, pages 429–458. 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 14.1 and 14.2 retell Chapter 11 of Bishop (2006), which the companion course Bayesian and Probabilistic Machine Learning covers in full. There, these notes give each result with a short proof and link the complete derivation; Section 14.3 (energy-based models, Langevin sampling, contrastive divergence) is new to this book and is treated in full here.

The chapter at a glance

  • 14.1 A Monte Carlo average is unbiased with variance \(\var[f]/L\) whatever the dimension, but correlation inflates the variance by the integrated autocorrelation time (Result 14.1). Transformation, rejection and importance sampling are exact in the limit, and fail in high dimension at an exponential rate (Result 14.5). Gradients of expectations have two unbiased estimators with very different variances (Filling the gap 14.2).
  • 14.2 A Markov chain that satisfies detailed balance with respect to \(p\) leaves \(p\) invariant; Metropolis–Hastings achieves this for any proposal (Result 14.9), and Gibbs sampling is the special case that always accepts (Result 14.10). Local moves cost about \((\sigma_{\max}/\sigma_{\min})^2\) steps per independent sample; for Gibbs on a Gaussian the cost is exactly \(2(L/l)^2-1\) (Result 14.11).
  • 14.3 An energy-based model's likelihood gradient is data expectation minus model expectation of \(\nabla_\bw E\) (Result 14.14). Langevin sampling needs only the score; one step from \(p\) changes expectations by \(O(\eta^2)\), so it is correct to first order (Result 14.15) and its bias for a Gaussian is exactly \(\sigma^2/(1-\eta/2\sigma^2)\) (Result 14.16); a Metropolis correction removes the bias (Result 14.17). One-step contrastive divergence is gradient descent on the score-matching objective, which explains why it cannot remove modes away from the data (Result 14.18).

Notation. \(p(\bz)=\pt(\bz)/Z_p\) is the target, \(\pt\) its unnormalised form and \(Z_p\) the (often unknown) normalising constant; \(q\) is a proposal; \(L\) is the number of samples; \(\tau\) indexes the steps of a chain and \(T(\bz,\bz')\) is its transition density from \(\bz\) to \(\bz'\). In Section 14.3, \(E(\bx,\bw)\) is an energy, \(Z(\bw)\) the partition function, \(\bs(\bx,\bw)\)\({}=\nabla_\bx\ln p(\bx\given\bw)\) the score and \(\eta\) the Langevin step size. \(\tau_{\rm int}\) is an integrated autocorrelation time (IAT).

Printings. The first printing has several slips in this chapter, among them a stray factor in (14.49), "\(u_0\) is retained" for \(z_0\) in rejection sampling, an Exercise 14.8 whose uniform variable has the wrong range, an optimality claim for the Cauchy envelope that does not hold, and an improper example distribution for over-relaxation. Each is flagged where it occurs, and the list with the evidence is in the summary before the exercises.

Derivations start hidden: click any bar to open one.

p. 429 To sample from a distribution \(p(\bz)\) is to produce values that behave like independent draws from it. The book follows the machine-learning convention in which one value is "a sample" (in statistics a sample is a set of values). The variable may be a scalar or an entire image generated by a network; for simple distributions there are exact recipes, for complicated or implicitly defined ones we need approximate methods.

14.1 Basic Sampling Algorithms

See also the companion course, Section 11.1 (basic sampling algorithms) and its sampling basics demo.

p. 430 Everything starts from a pseudo-random generator of numbers uniform on \((0,1)\): a deterministic algorithm whose output passes statistical tests of randomness. (The demonstrations of this course use a small generator of this kind with a seed, so that the browser and the Python code produce the same numbers.)

14.1.1 Expectations

See also the companion course, Monte Carlo estimates, Result 11.1 and Result 11.2.

pp. 430–431 Often the goal is not the samples but an expectation

\[ \E[f]=\int f(\bz)\,p(\bz)\,\d\bz, \tag{14.1} \]

(a sum for discrete variables). With independent draws \(\bz^{(1)},\dots,\bz^{(L)}\) from \(p\) it is approximated by the average

\[ \widehat f=\frac1L\sum_{l=1}^Lf(\bz^{(l)}), \tag{14.2} \]

written

\[ \E[f(\bz)]\simeq\frac1L\sum_{l=1}^Lf(\bz^{(l)}), \tag{14.3} \]

where \(\simeq\) means "is estimated without bias by". Its variance is

\[ \var[\widehat f]=\frac1L\E\big[(f-\E[f])^2\big]. \tag{14.4} \]
A red Gaussian density p(z) centred at 1 and a green wavy function f(z); twelve blue tick marks on the z axis are samples from p, blue dots mark f at those samples, a dashed black line is the exact expectation 0.449 and a dotted blue line is the sample average 0.519.
Figure 14.1 (computed). A function \(f(z)\) (green) whose expectation under \(p(z)=\N(z\given1,0.8^2)\) (red) is wanted. Twelve draws from \(p\) (blue ticks) give the estimate (14.2) \(\widehat f=0.519\) against the exact \(\E[f]=0.449\): unbiased, but noisy at this \(L\). Reproduces Bishop and Bishop (2024), Figure 14.1. Download: PDF · SVG

Result 14.1 (Monte Carlo error) pp. 430–431, (14.2)–(14.4); Exercises 14.1, 14.2

  1. If the \(\bz^{(l)}\) are drawn from \(p\), then \(\E[\widehat f]=\E[f]\); if they are also independent and \(\var[f]<\infty\), then \(\var[\widehat f]=\var[f]/L\) (14.4), and by the central limit theorem \(\widehat f\pm1.96\sqrt{\var[f]/L}\) is an approximate 95% interval.
  2. If instead they form a stationary sequence with autocorrelations \(\rho_k\)\({}=\mathrm{corr}(f(\bz^{(l)}),f(\bz^{(l+k)}))\), the mean is unchanged and \[ \var[\widehat f]=\frac{\var[f]}{L}\Big[1+2\sum_{k=1}^{L-1}\Big(1-\frac kL\Big)\rho_k\Big]\approx\frac{\var[f]}{L}\,\tau_{\rm int},\qquad\tau_{\rm int}=1+2\sum_{k\ge1}\rho_k , \] so \(L\) correlated draws are worth \(L_{\rm eff}=L/\tau_{\rm int}\) independent ones (the "effective sample size" of p. 431). For \(\rho_k=\rho^k\), \(\tau_{\rm int}=(1+\rho)/(1-\rho)\).
Proof (short; the full argument is Result 11.2 of the companion course)

(1) Linearity: \(\E[\widehat f]\)\({}=\frac1L\sum_l\E[f(\bz^{(l)})]\)\({}=\E[f]\). For independent terms the variances add, \(\var[\widehat f]\)\({}=\frac1{L^2}\sum_l\var[f]\)\({}=\var[f]/L\).

(2) \(\var[\widehat f]\)\({}=\frac1{L^2}\sum_{l,m}\cov(f_l,f_m)\)\({}=\frac{\var[f]}{L^2}\sum_{l,m}\rho_{|l-m|}\); there are \(L\) pairs with \(|l-m|=0\) and \(2(L-k)\) with \(|l-m|=k\), which gives the bracket. If \(\sum_k|\rho_k|<\infty\), dominated convergence lets \(L\to\infty\) inside the sum. For \(\rho_k=\rho^k\), \(1+2\sum_{k\ge1}\rho^k\)\({}=1+2\rho/(1-\rho)\)\({}=(1+\rho)/(1-\rho)\). ∎

A direct computation confirms both statements: 40 000 repetitions of \(L=20\) draws give \(L\var[\widehat f]=1.376\) against \(\var[f]=1.370\), and an AR(1) chain with \(\rho=0.9\) gives \(L\var[\widehat f]=18.7\) against \(\tau_{\rm int}=19\).

Filling the gap 14.1: what "independent of the dimensionality" does and does not mean p. 431

The book notes that the \(1/L\) decrease does not depend on the dimension of \(\bz\), and that the error can still be large when \(f\) is large where \(p\) is small. Both statements can be made quantitative.

Derivation

The rate is dimension-free, the constant is not. (14.4) involves \(\bz\) only through the scalar \(\var[f]\). A grid with \(n\) points per axis would need \(n^D\) evaluations; Monte Carlo reaches standard error \(\varepsilon\) with \(L=\var[f]/\varepsilon^2\) draws in any dimension. But \(\var[f]\) itself may grow with \(D\): for \(f(\bz)=\|\bz\|^2\), \(\bz\sim\N(\bzero,\bI_D)\), \(\var[f]=2D\). In Figure 14.S1(a) \(f=\Ind[\sum_iz_i/\sqrt D>0.5]\) has the same variance \(P(1-P)\), \(P=1-\Phi(0.5)\), for every \(D\), and the measured error is indeed the same for \(D=1\), 10 and 1000.

Rare events. Let \(f=\Ind[\bz\in A]\) with \(P=p(A)\) small. Then \(\var[f]=P(1-P)\) and the relative error is \[\frac{\sqrt{\var[\widehat f]}}{P}=\sqrt{\frac{1-P}{LP}},\] so \(L\) must be much larger than \(1/P\) before \(\widehat f\) is even of the right order: this is the precise form of "the expectation may be dominated by regions of small probability". Importance sampling (Section 14.1.5) attacks exactly this case by drawing from a proposal that puts more mass on \(A\).

Correlation. Markov chain samples (Section 14.2) are correlated, and Result 14.1(2) shows the cost: for an AR(1) sequence with \(\rho=0.99\), \(\tau_{\rm int}=199\), so 10 000 steps are worth 50 independent draws (Figure 14.S1(b)). Keeping only every \(M\)th sample ("thinning", p. 441) makes the kept ones nearly independent but never lowers the variance of the average of a given run. ∎

Three panels. Left: root mean square error against L on log axes for D = 1, 10 and 1000, all on one line of slope minus one half. Middle: standard deviation of the chain average against chain length for AR(1) chains with rho 0, 0.5, 0.9 and 0.99, parallel lines shifted up by the square root of tau. Right: the mean square displacement of 4000 random walks grows like tau over 2, with three sample paths in grey.
Figure 14.S1 (our own). (a) The error of (14.2) falls like \(1/\sqrt L\) with the same constant in \(D=1\), 10 and 1000 (100 repetitions per point; black: \(\sqrt{\var[f]/L}\)). (b) Correlated samples: for AR(1) chains the standard deviation of the average is \(\sqrt{\tau_{\rm int}/L}\) (lines) with \(\tau_{\rm int}=(1+\rho)/(1-\rho)\). (c) The random walk (14.28)–(14.30): \(\E[(z^{(\tau)})^2]=\tau/2\) (Exercise 14.11). Download: PDF · SVG

Beyond the book: gradients of expectations

In deep learning the expectation (14.1) is often a training objective whose distribution depends on the parameters, \(J(\btheta)\)\({}=\E_{\bz\sim q(\bz\given\btheta)}[f(\bz)]\): the expected reconstruction under an encoder (Section 19.2 of the book), a reward averaged over a stochastic policy, or the partition function of Section 14.3. We then need \(\nabla_\btheta J\), and the samples cannot simply be differentiated, because moving \(\btheta\) moves the distribution they come from. Two Monte Carlo estimators exist; the book uses the second in Section 19.2, and the first appears implicitly in (14.55).

Filling the gap 14.2: the score-function and reparameterisation estimators, their variances, and when each fails supplement to Section 14.1.1; the book's (19.17)

Let \(q(\bz\given\btheta)\) be differentiable in \(\btheta\). We compare the two unbiased estimators of \(\nabla_\btheta\E_q[f]\) and compute their variances for a Gaussian.

Derivation

Score-function (REINFORCE, likelihood-ratio) estimator (Williams, 1992). If differentiation under the integral is allowed (for example, if \(|f(\bz)\,\nabla_\btheta q(\bz\given\btheta)|\) is bounded near \(\btheta\) by an integrable function of \(\bz\), by dominated convergence), then, using \(\nabla q=q\nabla\ln q\), \[ \nabla_\btheta\E_q[f]=\int f(\bz)\nabla_\btheta q(\bz\given\btheta)\,\d\bz=\E_q\big[f(\bz)\,\nabla_\btheta\ln q(\bz\given\btheta)\big]\simeq\frac1L\sum_lf(\bz^{(l)})\nabla_\btheta\ln q(\bz^{(l)}\given\btheta). \] Only values of \(f\) are needed: \(f\) may be discontinuous or a black box. Taking \(f\equiv1\) gives \(\E_q[\nabla_\btheta\ln q]\)\({}=\nabla_\btheta1\)\({}=\bzero\), so any constant baseline \(b\) can be subtracted, \(\E_q[(f-b)\nabla\ln q]=\nabla\E_q[f]\), without bias. For a scalar parameter with score \(s=\partial_\theta\ln q\), the variance \(\E[(f-b)^2s^2]-(\partial_\theta J)^2\) is a quadratic in \(b\) minimised at \(b^\star=\E[fs^2]/\E[s^2]\).

Reparameterisation estimator. Suppose \(\bz=g(\beps,\btheta)\) with \(\beps\sim r(\beps)\) not depending on \(\btheta\), e.g. \(z=\mu+\sigma\epsilon\), \(\epsilon\sim\N(0,1)\) (the book's (19.17)). Then \(\E_q[f]=\E_r[f(g(\beps,\btheta))]\), and if \(f\) is differentiable with a dominating bound, \[ \nabla_\btheta\E_q[f]=\E_r\big[(\nabla_\btheta g)^\T\nabla_\bz f(g(\beps,\btheta))\big]. \] For the Gaussian: \(\partial_\mu\) gives \(f'(z)\), \(\partial_\sigma\) gives \(f'(z)\epsilon\). The score function for the same family is \(f(z)\epsilon/\sigma\) (for \(\mu\)) and \(f(z)(\epsilon^2-1)/\sigma\) (for \(\sigma\)), since \(\ln\N(z\given\mu,\sigma^2)\)\({}=-\frac{(z-\mu)^2}{2\sigma^2}-\ln\sigma+\const\).

Exact variances for \(f(z)=z^2\), \(\theta=\mu\). The true gradient is \(\partial_\mu(\mu^2+\sigma^2)=2\mu\). Reparameterisation: \(\var[2(\mu+\sigma\epsilon)]=4\sigma^2\), whatever \(\mu\). Score function: with \(\E\epsilon^2=1\), \(\E\epsilon^4=3\), \(\E\epsilon^6=15\) and odd moments zero, \[ \E\Big[\frac{(\mu+\sigma\epsilon)^4\epsilon^2}{\sigma^2}\Big]=\frac{\mu^4+6\mu^2\sigma^2\cdot3+\sigma^4\cdot15}{\sigma^2},\qquad\var=\frac{\mu^4+18\mu^2\sigma^2+15\sigma^4}{\sigma^2}-4\mu^2 , \] which is 87 at \(\mu=2\), \(\sigma=1\) against 4, and grows like \(\mu^4\). With the baseline \(b=\E[f]=\mu^2+\sigma^2\), \((f-b)\epsilon/\sigma\)\({}=2\mu\epsilon^2+\sigma(\epsilon^3-\epsilon)\), whose second moment is \(12\mu^2+\sigma^2(15-6+1)\), so the variance drops to \(8\mu^2+10\sigma^2=42\): better, still ten times worse than reparameterisation.

When reparameterisation is wrong. For \(f=\Ind[z>a]\), \(f'=0\) wherever it exists, so the reparameterisation estimate is exactly \(0\), while \(\partial_\mu P(z>a)\)\({}=\phi((\mu-a)/\sigma)/\sigma\ne0\). The interchange fails because \(f\circ g\) is not differentiable on the set \(\{\epsilon=(a-\mu)/\sigma\}\) and the derivative of \(\E[f]\) comes entirely from mass crossing that point. The score function is unbiased here.

When reparameterisation loses. For \(f=\sin(az)\), \(\var[f'(z)]\)\({}=\frac{a^2}2\big(1+e^{-2a^2\sigma^2}\cos2a\mu\big)-(\partial_\mu J)^2\) grows like \(a^2\), while the score-function variance is at most \(\E[f^2\epsilon^2]/\sigma^2\le1/\sigma^2\). At \(a=3\), \(\mu=0.3\), \(\sigma=1\): 4.50 against 0.50. So the rule "reparameterisation has lower variance" holds for smooth, slowly varying \(f\), not in general.

Link to this chapter. (14.55) is the score-function identity applied to the unnormalised density: \(\nabla_\bw\ln Z(\bw)\)\({}=\E_{p}[\nabla_\bw\ln\pt(\bx\given\bw)]\)\({}=-\E_p[\nabla_\bw E]\). All numbers above are confirmed by quadrature and simulation. ∎

Three panels. Left: histograms of 20000 single-sample gradient estimates for f = z squared at mu = 2: the red score-function histogram is wide with a long tail and variance 84.8, the blue reparameterisation histogram is narrow with variance 4.0; both are centred on the true value 4. Middle: exact variance against mu on a log scale; the red score-function curve rises from 15 to about 220, the dashed baseline curve is lower, the blue reparameterisation line is flat at 4. Right: estimates of the derivative of P(z > 0) against mu; the black true curve is a bell, red score-function estimates with error bars follow it, and the blue reparameterisation line is flat at zero.
Figure 14.S2 (our own). (a) Single-sample estimates of \(\partial_\mu\E[z^2]\) for \(z\sim\N(2,1)\): both are centred on 4, with variances 85 (score function, exact 87) and 4 (reparameterisation). (b) Exact variances against \(\mu\): the score-function variance grows like \(\mu^4\); a baseline helps but does not close the gap. (c) For a step function the reparameterisation estimator is identically zero (biased), the score function is unbiased. Download: PDF · SVG
▶ DemoScore function versus reparameterisation for \(f=z^2\)2000 estimates of each kind from the same noise, with exact variances; move \(\mu\) and watch the score-function variance explode.
▶ DemoA step function defeats reparameterisationThe reparameterisation estimate is always 0; preset 4 shows a smooth but fast-oscillating \(f\) where the score function has the smaller variance.

14.1.2 Standard distributions

See also the companion course, Section 11.1.1 (standard distributions), and Section 2.4 of these notes (transformation of densities).

pp. 431–433 If \(z\) is uniform on \((0,1)\) and \(y=g(z)\), the change-of-variables formula gives

\[ p(y)=p(z)\left|\frac{\d z}{\d y}\right| \tag{14.5} \]

with \(p(z)=1\). Choosing \(g\) so that \(z\) equals the cumulative distribution function of the target,

\[ z=\int_{-\infty}^yp(\widehat y)\,\d\widehat y\equiv h(y), \tag{14.6} \]

gives \(y=h^{-1}(z)\) (Figure 14.2). For the exponential distribution

\[ p(y)=\lambda\exp(-\lambda y),\qquad y\ge0, \tag{14.7} \]

\(h(y)=1-e^{-\lambda y}\) and \(y=-\lambda^{-1}\ln(1-z)\); for the Cauchy distribution

\[ p(y)=\frac1\pi\frac1{1+y^2} \tag{14.8} \]

\(h(y)=\frac12+\frac1\pi\arctan y\) and \(y=\tan\{\pi(z-\frac12)\}\) (Exercise 14.4). In several dimensions the Jacobian determinant replaces the derivative,

\[ p(y_1,\dots,y_M)=p(z_1,\dots,z_M)\left|\frac{\partial(z_1,\dots,z_M)}{\partial(y_1,\dots,y_M)}\right|. \tag{14.9} \]
Left: a red gamma density, scaled to height one, and its blue cumulative distribution function h(y) rising from 0 to 1; grey arrows go from three values of z on the vertical axis across to the blue curve and down to the corresponding y. Right: a histogram of 5000 transformed uniforms closely following the red gamma density.
Figure 14.2 (computed). The transformation method for \(p(y)=\Gam(y\given3,1)\): a uniform \(z\) on the vertical axis is mapped through the inverse of the cumulative distribution function \(h\) (blue) to \(y\). Right: 5000 such values against \(p\). Reproduces Bishop and Bishop (2024), Figure 14.2. Download: PDF · SVG

Box–Muller. Draw \(z_1,z_2\) uniform on \((-1,1)\), keep the pair only if \(r^2=z_1^2+z_2^2\le1\) (Figure 14.3), and set

\[ y_1=z_1\Big(\frac{-2\ln r^2}{r^2}\Big)^{1/2}, \tag{14.10} \] \[ y_2=z_2\Big(\frac{-2\ln r^2}{r^2}\Big)^{1/2}. \tag{14.11} \]

Then

\[ p(y_1,y_2)=p(z_1,z_2)\left|\frac{\partial(z_1,z_2)}{\partial(y_1,y_2)}\right|=\Big[\frac1{\sqrt{2\pi}}e^{-y_1^2/2}\Big]\Big[\frac1{\sqrt{2\pi}}e^{-y_2^2/2}\Big], \tag{14.12} \]

two independent standard Gaussians. A general Gaussian follows by \(y\mapsto\mu+\sigma y\), and a multivariate one by \(\by=\bmu+\bL\bz\) with \(\Sig=\bL\bL^\T\) (Cholesky).

Result 14.2 (the transformation method, Box–Muller, Cholesky) pp. 431–433; Exercises 14.3–14.6

  1. If \(h\) is continuous and strictly increasing on the support of \(p\) and \(z\sim\Unif(0,1)\), then \(y=h^{-1}(z)\) has density \(p\).
  2. The polar Box–Muller map sends the uniform distribution on the unit disc (density \(1/\pi\)) to \(\N(\bzero,\bI_2)\); a pair is accepted with probability \(\pi/4\).
  3. If \(\bz\sim\N(\bzero,\bI)\) and \(\Sig=\bL\bL^\T\), then \(\bmu+\bL\bz\sim\N(\bmu,\Sig)\).
Proof (short; full versions in Results 11.3, 11.4 and 11.5 of the companion course)

(1) \(P(y\le a)\)\({}=P(h^{-1}(z)\le a)\)\({}=P(z\le h(a))\)\({}=h(a)\), and \(h'=p\).

(2) In polar coordinates \(z=r(\cos\theta,\sin\theta)\), the map keeps \(\theta\) and sends \(r\) to \(R=\sqrt{-2\ln r^2}\), so \(r^2=e^{-R^2/2}\). Area elements are \(r\,\d r\,\d\theta\) and \(R\,\d R\,\d\theta\); from \(R^2=-4\ln r\), \(R\,\d R=-2\,\d r/r\), so \(\big|\partial(y_1,y_2)/\partial(z_1,z_2)\big|\)\({}=\frac{R|\d R|}{r\,\d r}\)\({}=\frac2{r^2}\). Hence \(p(\by)\)\({}=\frac1\pi\cdot\frac{r^2}2\)\({}=\frac1{2\pi}e^{-R^2/2}\)\({}=\frac1{2\pi}e^{-(y_1^2+y_2^2)/2}\), which is (14.12). The square has area 4 and the disc \(\pi\).

(3) An affine image of a Gaussian vector is Gaussian, with mean \(\bmu\) and covariance \(\bL\,\E[\bz\bz^\T]\bL^\T\)\({}=\bL\bL^\T\)\({}=\Sig\). Any square root of \(\Sig\) would do; the triangular one is just cheap. ∎

Left: points uniform in the square from minus one to one, blue inside the unit circle and grey outside; 1000 of 1304 accepted. Middle: the green cloud of transformed points, round and centred at zero. Right: the histogram of both coordinates against the red standard normal density.
Figure 14.3 (computed). The polar Box–Muller method: 1304 points uniform in the square, of which 1000 fall in the disc (expected fraction \(\pi/4=0.785\)); the map (14.10)–(14.11) turns them into independent standard Gaussian pairs. Reproduces Bishop and Bishop (2024), Figure 14.3. Download: PDF · SVG

The transformation method needs \(h\) and its inverse in closed form, which is rare, so we turn to rejection and importance sampling. They are limited to low dimensions but serve as building blocks.

14.1.3 Rejection sampling

See also the companion course, Section 11.1.2 (rejection sampling), and the rejection-sampling preset of its demo.

pp. 433–435 Suppose we can evaluate

\[ p(\bz)=\frac1{Z_p}\pt(\bz) \tag{14.13} \]

only up to the constant \(Z_p\). Choose a proposal \(q\) that is easy to sample and a constant \(k\) with \(kq(\bz)\ge\pt(\bz)\) everywhere (the comparison function). Draw \(z_0\sim q\), then \(u_0\) uniform on \([0,kq(z_0)]\); the pair is uniform under the graph of \(kq\). Reject it if \(u_0>\pt(z_0)\) (the grey region of Figure 14.4), otherwise keep \(z_0\). (Erratum. The book says "\(u_0\) is retained"; it is \(z_0\) that is kept.) The acceptance probability is

\[ p(\text{accept})=\int\{\pt(\bz)/kq(\bz)\}\,q(\bz)\,\d\bz=\frac1k\int\pt(\bz)\,\d\bz. \tag{14.14} \]

Result 14.3 (rejection sampling is exact) pp. 433–434, (14.14); Exercise 14.7

If \(q(\bz)>0\) wherever \(\pt(\bz)>0\) and \(kq\ge\pt\), the accepted values have density \(p\), and the acceptance probability is \(Z_p/k\). Any such \(k\) works; the smallest one maximises the acceptance rate.

Proof (short; full version in Result 11.7)

Given \(z_0=\bz\), acceptance has probability \(P(u_0\le\pt(\bz))=\pt(\bz)/kq(\bz)\). By the product rule the joint density of "\(\bz\) drawn and accepted" is \(q(\bz)\pt(\bz)/kq(\bz)=\pt(\bz)/k\); by the sum rule \(P(\text{accept})=\int\pt/k=Z_p/k\), which is (14.14); and by Bayes' theorem the density of accepted values is \((\pt/k)/(Z_p/k)=p\). ∎

Left: a red comparison function k q(z) above a green bimodal unnormalised density, the region between shaded grey; 300 proposal pairs are drawn as dots, green below the green curve and grey above it; a blue vertical line at z0 with a point u0 above the green curve is labelled rejected. Right: a histogram of 8408 accepted values following the green bimodal density.
Figure 14.4 (computed). Rejection sampling of a two-component mixture \(\pt\) (area 2) with a Gaussian proposal, \(k=4.72\), the smallest valid constant. Pairs \((z_0,u_0)\) below \(\pt\) (green) are accepted, those in the grey band rejected; the acceptance rate is \(2/k=0.42\) (observed 8408 of 20 000), and the accepted values follow \(p\). Reproduces Bishop and Bishop (2024), Figure 14.4. Download: PDF · SVG

Sampling a gamma density. For

\[ \Gam(z\given a,b)=\frac{b^az^{a-1}\exp(-bz)}{\Gamma(a)} \tag{14.15} \]

with \(a>1\), a bell-shaped Cauchy comparison function is natural. Transforming a uniform variable \(y\) on \((-\pi/2,\pi/2)\) by \(z=b\tan y+c\) gives Cauchy values, and the comparison function is

\[ kq(z)=\frac{k}{1+(z-c)^2/b^2}. \tag{14.16} \]

(The book writes the left side as \(q(z)\); as printed it is the comparison function \(kq\), since the normalised Cauchy density is \(1/\{\pi b(1+(z-c)^2/b^2)\}\).)

Filling the gap 14.3: the Cauchy envelope of the gamma density, and the claim that \(c=a-1\), \(b^2=2a-1\) minimise the rejection rate pp. 434–435, (14.16), Figure 14.5; Exercise 14.8

The book states that the minimum reject rate is obtained with \(c=a-1\) and \(b^2=2a-1\). That choice is valid and reasonable, but it is not the minimum.

Derivation

Acceptance rate of a Cauchy envelope. For given \((c,b)\) the smallest valid constant is \(k(c,b)\)\({}=\sup_{z>0}\Gam(z\given a,1)\{1+(z-c)^2/b^2\}\), and the area under (14.16) is \(k\pi b\), so by (14.14) the acceptance probability is \(1/\{k(c,b)\,\pi b\}\).

The book's choice is valid. With \(c=a-1\) (the mode) and \(k\) equal to the density at the mode, the envelope lies above the gamma for every \(a>1\) exactly when \(b^2\ge2a-1\); the sign argument is written out in the companion course, Filling the gap 11.4. So \(b^2=2a-1\) is the narrowest envelope among those that touch the gamma at its mode.

It is not optimal. Nothing forces the envelope to touch at the mode. Maximising \(1/\{k(c,b)\pi b\}\) over both \(c\) and \(b\) numerically (with \(k\) recomputed for each candidate) gives, for \(a=10\), \(c=9.33\), \(b^2=9.55\) and acceptance 0.646, against 0.554 for the book's \(c=9\), \(b^2=19\): the rejection rate falls from 44.6% to 35.4%. The optimal envelope is narrower and taller and touches the gamma on both flanks instead of at the peak (Figure 14.5). Simulation confirms both rates (0.555 and 0.646 observed).

Exercise 14.8. As printed, \(z\) is uniform on \([0,1]\); then \(y=b\tan z+c\) lies in \([c,c+b\tan1]\) and is not Cauchy. With \(z\) uniform on \((-\pi/2,\pi/2)\) (or \(y=b\tan\{\pi(z-\frac12)\}+c\) for \(z\) on \((0,1)\)) the inverse map is \(z=\arctan\{(y-c)/b\}\) and \(|\d z/\d y|=b/\{b^2+(y-c)^2\}\), so by (14.5) \(p(y)=\frac1\pi\frac{b}{b^2+(y-c)^2}\), a Cauchy density with location \(c\) and scale \(b\). ∎

A green gamma density with shape 10 peaking near z = 9; a red Cauchy comparison function touching it at the peak and lying well above it in the tails, labelled acceptance 0.554; a dashed orange taller and narrower Cauchy comparison function labelled acceptance 0.646.
Figure 14.5 (computed). \(\Gam(z\given10,1)\) (green) under the Cauchy comparison function with the book's \(c=a-1\), \(b^2=2a-1\) and the smallest valid \(k\) (red, acceptance 0.554), and under the best Cauchy comparison function (dashed orange, acceptance 0.646; see Filling the gap 14.3). Reproduces Bishop and Bishop (2024), Figure 14.5, with the optimal envelope added. Download: PDF · SVG

14.1.4 Adaptive rejection sampling

See also the companion course, Section 11.1.3, Result 11.8 and Algorithm 11.2.

pp. 435–437 If \(\ln p\) is concave, its tangent lines lie above it, so the piecewise-linear minimum of the tangents at a few abscissae is an upper bound on \(\ln p\) (Figure 14.6). The envelope is then piecewise exponential,

\[ q(z)=k_i\lambda_i\exp\{-\lambda_i(z-z_{i-1})\},\qquad z_{i-1}<z\le z_i, \tag{14.17} \]

where here \(z_{i-1},z_i\) are the breakpoints where successive tangents meet. Sample from the envelope, apply the rejection test, and add every rejected point to the abscissae: the envelope tightens and the rejection rate falls (Gilks and Wild, 1992). Without log-concavity a Metropolis–Hastings step can follow each rejection step (Gilks, Best and Tan, 1995).

Result 14.4 (the tangent envelope and how to sample it) pp. 435–436, (14.17); Exercises 14.9, 14.10

Let \(h_j=\ln p(\zeta_j)\) and \(g_j=(\ln p)'(\zeta_j)\) at abscissae \(\zeta_1<\dots<\zeta_n\). Successive tangents meet at \(e_j\)\({}=\dfrac{h_{j+1}-h_j-g_{j+1}\zeta_{j+1}+g_j\zeta_j}{g_j-g_{j+1}}\), and on \((e_{j-1},e_j]\) the envelope is \(\exp\{h_j+g_j(z-\zeta_j)\}\), with mass \(M_j\)\({}=\big(e^{h_j+g_j(e_j-\zeta_j)}-e^{h_j+g_j(e_{j-1}-\zeta_j)}\big)/g_j\). In the form (14.17), \(\lambda_j=-g_j\) and \(k_j\lambda_j\)\({}=e^{h_j+g_j(e_{j-1}-\zeta_j)}/\sum_iM_i\); continuity gives \(k_{j+1}\lambda_{j+1}\)\({}=k_j\lambda_je^{-\lambda_j(e_j-e_{j-1})}\) and normalisation \(\sum_jk_j(1-e^{-\lambda_j(e_j-e_{j-1})})\)\({}=1\). To sample: pick piece \(j\) with probability \(M_j/\sum_iM_i\), then set \(z\)\({}=e_{j-1}-\lambda_j^{-1}\ln\{1-u(1-e^{-\lambda_j(e_j-e_{j-1})})\}\) with \(u\sim\Unif(0,1)\).

Proof (short; details in Filling the gap 11.5)

A concave function lies below each of its tangents, so the envelope (their minimum) is above \(\ln p\); on each interval the lowest tangent is the one at the abscissa inside it, and two neighbouring tangents are equal at \(e_j\), which is the formula above. The masses are integrals of exponentials. On piece \(j\) the normalised density is \(\lambda e^{-\lambda(z-e_{j-1})}/(1-e^{-\lambda\Delta})\), \(\Delta=e_j-e_{j-1}\), whose CDF \((1-e^{-\lambda(z-e_{j-1})})/(1-e^{-\lambda\Delta})\) set equal to \(u\) gives the inversion formula (for \(\lambda=0\) the piece is uniform; unbounded end pieces need \(\lambda>0\) on the right and \(\lambda<0\) on the left). A direct computation confirms the masses against numerical integrals and the sampler by a Kolmogorov–Smirnov test. ∎

Left: the red concave curve ln p(z) for a gamma density with shape 4 and a blue piecewise-linear envelope made of three tangent lines at z1, z2 and z3, with dashed vertical lines at the three points. Right: cumulative rejections against the number of proposals on a log axis, a staircase reaching 21 rejections after about 3000 proposals.
Figure 14.6 (computed). Left: tangent lines of \(\ln\Gam(z\given4,1)\) at three abscissae form a piecewise-linear upper bound. Right: adaptive rejection sampling from these three points: rejected points are added to the abscissae, and only 21 of 3021 proposals are rejected, most of them early. Reproduces Bishop and Bishop (2024), Figure 14.6. Download: PDF · SVG

Rejection sampling in high dimensions. pp. 436–437 Sample \(\N(\bzero,\sigma_p^2\bI_D)\) with the proposal \(\N(\bzero,\sigma_q^2\bI_D)\), \(\sigma_q\ge\sigma_p\). Both densities peak at the origin, so the smallest \(k\) is the ratio of the peaks, \(k=(\sigma_q/\sigma_p)^D\), and the acceptance rate is \(1/k\).

Result 14.5 (acceptance falls exponentially with dimension) pp. 436–437, Figure 14.7

For the Gaussians above, \(p(\text{accept})\)\({}=(\sigma_p/\sigma_q)^D\)\({}=e^{-D\ln(\sigma_q/\sigma_p)}\). With \(\sigma_q=1.01\sigma_p\) and \(D=1000\) this is \(1/20\,959\), the book's "about 1/20,000".

Proof (short; see also Result 11.9)

\(p(\bz)/q(\bz)\)\({}=(\sigma_q/\sigma_p)^D\exp\{-\frac{\|\bz\|^2}2(\sigma_p^{-2}-\sigma_q^{-2})\}\) is largest at \(\bz=\bzero\), so the smallest valid \(k\) is \((\sigma_q/\sigma_p)^D\), and since both densities are normalised, (14.14) gives \(1/k\). Numerically \(1.01^{1000}=20\,959.2\). ∎

Left: a green standard Gaussian and a slightly wider red scaled Gaussian with the same peak height. Right: acceptance rate on a log scale against dimension from 1 to 1000 for ratios 1.01, 1.05 and 1.1; the curves fall faster for larger ratios, red dots from simulation lie on the 1.1 curve, and a blue square at D = 1000 is labelled 1/20959.
Figure 14.7 (computed). Left: \(p=\N(0,1)\) and the comparison function \(kq\) with \(\sigma_q=1.1\), \(k=1.1\): close in one dimension. Right: the acceptance rate \((\sigma_p/\sigma_q)^D\) against \(D\) (dots: simulated for \(\sigma_q/\sigma_p=1.1\)). Reproduces Bishop and Bishop (2024), Figure 14.7, with the dimension dependence added. Download: PDF · SVG

14.1.5 Importance sampling

See also the companion course, Section 11.1.4, Results 11.10–11.12, and the importance-sampling preset of its demo.

pp. 437–439 A uniform grid,

\[ \E[f]\simeq\sum_{l=1}^Lp(\bz^{(l)})f(\bz^{(l)}), \tag{14.18} \]

needs exponentially many points in high dimension and wastes most of them where \(pf\) is negligible. Importance sampling draws from a proposal \(q\) instead (Figure 14.8):

\[ \E[f]=\int f(\bz)p(\bz)\,\d\bz=\int f(\bz)\frac{p(\bz)}{q(\bz)}q(\bz)\,\d\bz\simeq\frac1L\sum_{l=1}^L\frac{p(\bz^{(l)})}{q(\bz^{(l)})}f(\bz^{(l)}). \tag{14.19} \]

The importance weights \(r_l=p(\bz^{(l)})/q(\bz^{(l)})\) correct for sampling from the wrong distribution, and no sample is discarded. If \(p=\pt/Z_p\) and \(q=\qt/Z_q\) are known only up to constants,

\[ \E[f]=\frac{Z_q}{Z_p}\int f(\bz)\frac{\pt(\bz)}{\qt(\bz)}q(\bz)\,\d\bz\simeq\frac{Z_q}{Z_p}\frac1L\sum_{l=1}^L\widetilde r_lf(\bz^{(l)}), \tag{14.20} \]

with \(\widetilde r_l\)\({}=\pt(\bz^{(l)})/\qt(\bz^{(l)})\), and the same draws estimate the ratio of constants,

\[ \frac{Z_p}{Z_q}=\frac1{Z_q}\int\pt(\bz)\,\d\bz=\int\frac{\pt(\bz)}{\qt(\bz)}q(\bz)\,\d\bz\simeq\frac1L\sum_{l=1}^L\widetilde r_l, \tag{14.21} \]

so that

\[ \E[f]\simeq\sum_{l=1}^Lw_lf(\bz^{(l)}), \tag{14.22} \] \[ w_l=\frac{\widetilde r_l}{\sum_m\widetilde r_m}=\frac{\pt(\bz^{(l)})/q(\bz^{(l)})}{\sum_m\pt(\bz^{(m)})/q(\bz^{(m)})}. \tag{14.23} \]

Result 14.6 (importance sampling: bias, consistency, effective sample size) pp. 437–439, (14.19)–(14.23)

  1. If \(q>0\) wherever \(pf\ne0\), (14.19) and (14.21) are unbiased; the variance of (14.19) is \(\frac1L\big(\int f^2p^2/q\,\d\bz-\E[f]^2\big)\), which is infinite if \(q\) has lighter tails than \(p|f|\).
  2. The self-normalised estimate (14.22) is a ratio of two unbiased averages: it is biased for finite \(L\), with bias \(O(1/L)\), but consistent, and its asymptotic variance is \(\frac1L\E_p[(p/q)(f-\E_p f)^2]\).
  3. A common summary of weight degeneracy is \(L_{\rm eff}=1/\sum_lw_l^2\), which is \(L\) for equal weights and 1 when a single weight dominates.
Proof (short; full version in Results 11.10–11.12 and Filling the gap 11.6)

(1) Each term has mean \(\int f\frac pqq=\E[f]\) and second moment \(\int f^2p^2/q\). (2) Write (14.22) as \(A_L/B_L\) with \(A_L\)\({}=\frac1L\sum\widetilde r_lf_l\to Z_p\E[f]/Z_q\) and \(B_L\)\({}=\frac1L\sum\widetilde r_l\to Z_p/Z_q\) almost surely (law of large numbers), so the ratio converges to \(\E[f]\); a first-order expansion of \(A/B\) about the limits (the delta method) gives the variance, and the second-order term gives the \(O(1/L)\) bias. A numerical experiment estimates \(Z_p/Z_q=3\) as 3.0015 and \(\E_p[f]=0.2927\) as 0.2926 for the densities of Figure 14.8. ∎

The book's warning on p. 439, that importance sampling can be badly wrong "with no diagnostic indication", is (1) at work: if \(q\) misses a region where \(pf\) is large, the sample weights look well behaved although the estimator's true variance is huge or infinite.

A red bimodal density p(z), a broad blue proposal q(z) and a green sigmoid-shaped function f(z); purple stems below the axis show the importance weights of 25 samples drawn from q, tallest where p exceeds q.
Figure 14.8 (computed). Importance sampling: 25 draws from a broad Gaussian \(q\) (blue), each weighted by \(p/q\) (purple stems, drawn downwards), estimate \(\E_p[f]=0.293\) as 0.321 with (14.22). Reproduces Bishop and Bishop (2024), Figure 14.8. Download: PDF · SVG

14.1.6 Sampling-importance-resampling

See also the companion course, Section 11.1.5 and Result 11.13; the SIR preset of its demo.

pp. 439–440 SIR avoids the constant \(k\) of rejection sampling: draw \(\bz^{(1)},\dots,\bz^{(L)}\) from \(q\), compute the weights (14.23), and draw \(L\) values from the discrete distribution on \(\{\bz^{(l)}\}\) with probabilities \(w_l\). In one dimension the distribution function of a resampled value is

\[ p(z\le a)=\sum_{l:z^{(l)}\le a}w_l=\frac{\sum_l\Ind(z^{(l)}\le a)\,\pt(z^{(l)})/q(z^{(l)})}{\sum_l\pt(z^{(l)})/q(z^{(l)})} , \tag{14.24} \]

and as \(L\to\infty\) both sums divided by \(L\) converge to integrals against \(q\),

\[ p(z\le a)=\frac{\int\Ind(z\le a)\{\pt(z)/q(z)\}q(z)\,\d z}{\int\{\pt(z)/q(z)\}q(z)\,\d z}=\frac{\int\Ind(z\le a)\pt(z)\,\d z}{\int\pt(z)\,\d z}=\int\Ind(z\le a)p(z)\,\d z . \tag{14.25} \]

Moments can be taken directly from the weighted draws,

\[ \E[f(\bz)]=\int f(\bz)p(\bz)\,\d\bz=\frac{\int f(\bz)[\pt(\bz)/q(\bz)]q(\bz)\,\d\bz}{\int[\pt(\bz)/q(\bz)]q(\bz)\,\d\bz}\simeq\sum_{l=1}^Lw_lf(\bz_l). \tag{14.26} \]

Result 14.7 (what resampling does and does not change) pp. 439–440, (14.24)–(14.26)

(1) The limit (14.25) holds almost surely for every \(a\) if \(q>0\) where \(p>0\) and \(\E_q[\pt/q]<\infty\). (2) For finite \(L\), conditionally on the first-stage draws, the average of \(f\) over the resampled values has mean \(\sum_lw_lf(\bz^{(l)})\), the self-normalised estimate (14.22); resampling therefore adds variance and never removes bias. Its purpose is to produce unweighted samples, for example as input to a later stage.

Proof

(1) The law of large numbers applied to numerator and denominator of (14.24), each divided by \(L\), as written in (14.25). (2) Each resampled value equals \(\bz^{(l)}\) with probability \(w_l\), so its conditional expectation of \(f\) is \(\sum_lw_lf(\bz^{(l)})\). By the law of total variance, the variance of the resampled average is the variance of (14.22) plus the expected conditional (multinomial) variance, which is non-negative. See Result 11.13 of the companion course for (1) in more detail. ∎

14.2 Markov Chain Monte Carlo

See also the companion course, Section 11.2 (Markov chain Monte Carlo) and its Metropolis and Gibbs demo.

pp. 440–441 Rejection and importance sampling break down in high dimensions. Markov chain Monte Carlo (MCMC), which originated in physics (Metropolis and Ulam, 1949), scales much better: the proposal \(q(\bz\given\bz^{(\tau)})\) depends on the current state, so the samples \(\bz^{(1)},\bz^{(2)},\dots\) form a Markov chain, and an acceptance rule makes \(p\) the chain's long-run distribution. Only \(\pt\) is needed.

14.2.1 The Metropolis algorithm

pp. 441–442 With a symmetric proposal, \(q(\bz_A\given\bz_B)\)\({}=q(\bz_B\given\bz_A)\), the candidate \(\bz^\star\) is accepted with probability

\[ A(\bz^\star,\bz^{(\tau)})=\min\Big(1,\frac{\pt(\bz^\star)}{\pt(\bz^{(\tau)})}\Big). \tag{14.27} \]

A move uphill in \(p\) is always accepted. If the candidate is rejected the chain stays put and the current state is recorded again; dropping the repeats would bias the samples.

Algorithm 14.1 (Metropolis sampling) p. 442

  1. Start from \(\bz^{(0)}\).
  2. For \(\tau=1,\dots,T\): draw \(\bz^\star\sim q(\bz\given\bz^{(\tau-1)})\) and \(u\sim\Unif(0,1)\); if \(\pt(\bz^\star)/\pt(\bz^{(\tau-1)})>u\) set \(\bz^{(\tau)}=\bz^\star\), otherwise \(\bz^{(\tau)}=\bz^{(\tau-1)}\).
  3. Return \(\bz^{(1)},\dots,\bz^{(T)}\) (the book returns only \(\bz^{(T)}\)).

(The comment "Iterative message-passing" in the book's listing is a leftover from another algorithm, and its "Output: \(\bz\sim\pt(\bz)\)" means a draw from the normalised \(p\).)

A red ellipse, the one-standard-deviation contour of a correlated Gaussian centred at (1.5, 1.5), with 150 short line segments: green for accepted Metropolis steps forming a wandering path, red for rejected proposals sticking out from it.
Figure 14.9 (computed). Random-walk Metropolis on a two-dimensional Gaussian (mean \((1.5,1.5)\), variances 0.5, correlation 0.9) with an isotropic Gaussian proposal of standard deviation 0.2: 150 candidates, 44 rejected (red). (The book's run has 43 rejections.) Reproduces Bishop and Bishop (2024), Figure 14.9. Download: PDF · SVG

Random walks are slow. p. 442 On the integers, let the chain stay put with probability \(\frac12\) and move one step left or right with probability \(\frac14\) each,

\[ p(z^{(\tau+1)}=z^{(\tau)})=0.5, \tag{14.28} \] \[ p(z^{(\tau+1)}=z^{(\tau)}+1)=0.25, \tag{14.29} \] \[ p(z^{(\tau+1)}=z^{(\tau)}-1)=0.25. \tag{14.30} \]

From \(z^{(0)}=0\), \(\E[z^{(\tau)}]=0\) and \(\E[(z^{(\tau)})^2]=\tau/2\) (Exercise 14.11; Figure 14.S1(c)): after \(\tau\) steps the walk has typically travelled only \(\sqrt{\tau/2}\). Avoiding this random-walk behaviour is a central aim in designing MCMC methods.

14.2.2 Markov chains

See also the companion course, Section 11.2.1, Definition 11.1 and Results 11.16–11.18.

Definition 14.1 (Markov chain, invariance, detailed balance, ergodicity) pp. 442–444, (14.31)–(14.34)

A first-order Markov chain satisfies

\[ p(\bz^{(m+1)}\given\bz^{(1)},\dots,\bz^{(m)})=p(\bz^{(m+1)}\given\bz^{(m)}), \tag{14.31} \]

and is specified by \(p(\bz^{(0)})\) and transition probabilities \(T_m(\bz^{(m)},\bz^{(m+1)})\equiv p(\bz^{(m+1)}\given\bz^{(m)})\); it is homogeneous if \(T_m=T\) for all \(m\). Marginals propagate by

\[ p(\bz^{(m+1)})=\int p(\bz^{(m+1)}\given\bz^{(m)})\,p(\bz^{(m)})\,\d\bz^{(m)}. \tag{14.32} \]

A distribution \(p^\star\) is invariant (stationary) if

\[ p^\star(\bz)=\int T(\bz',\bz)\,p^\star(\bz')\,\d\bz', \tag{14.33} \]

and \(T\) satisfies detailed balance with respect to \(p^\star\) (is reversible) if

\[ p^\star(\bz)T(\bz,\bz')=p^\star(\bz')T(\bz',\bz). \tag{14.34} \]

The chain is ergodic if \(p(\bz^{(m)})\to p^\star\) from every starting distribution; \(p^\star\) is then the unique equilibrium distribution.

Result 14.8 (detailed balance, mixtures and compositions) pp. 444, (14.35)–(14.39)

  1. Detailed balance implies invariance: \[ \int p^\star(\bz')T(\bz',\bz)\,\d\bz'=\int p^\star(\bz)T(\bz,\bz')\,\d\bz' \tag{14.35} \] \[ =p^\star(\bz)\int p(\bz'\given\bz)\,\d\bz' \tag{14.36} \] \[ =p^\star(\bz). \tag{14.37} \]
  2. If \(p^\star\) is invariant for base transitions \(B_1,\dots,B_K\), it is invariant for the mixture \[ T(\bz',\bz)=\sum_{k=1}^K\alpha_kB_k(\bz',\bz) \tag{14.38} \] (\(\alpha_k\ge0\), \(\sum_k\alpha_k=1\)) and for the composition \[ T(\bz',\bz)=\sum_{\bz_1}\cdots\sum_{\bz_{K-1}}B_1(\bz',\bz_1)\cdots B_{K-1}(\bz_{K-2},\bz_{K-1})B_K(\bz_{K-1},\bz). \tag{14.39} \]
  3. If every \(B_k\) is reversible, so is the mixture and so is the palindromic composition \(B_1\cdots B_KB_K\cdots B_1\); the plain composition generally is not.

Erratum. The book's (14.39) sums over \(\bz_1,\dots,\bz_{n-1}\); the index should be \(K-1\), as above.

Proof (short; full version in Result 11.18)

(1) is (14.35)–(14.37): apply (14.34) inside the integral, then use that \(T(\bz,\cdot)\) is a probability distribution. On a finite space write \(\mathbf D=\diag(p^\star)\); invariance is \(p^\star B=p^\star\) and reversibility is \(\mathbf DB=B^\T\mathbf D\). (2) \(p^\star\sum_k\alpha_kB_k\)\({}=\sum_k\alpha_kp^\star\)\({}=p^\star\), and \(p^\star B_1\cdots B_K\)\({}=p^\star B_2\cdots B_K\)\({}=\dots\)\({}=p^\star\). (3) Mixtures: \(\mathbf D\sum\alpha_kB_k\)\({}=\sum\alpha_kB_k^\T\mathbf D\). Compositions: \(\mathbf DB_1B_2\)\({}=B_1^\T\mathbf DB_2\)\({}=B_1^\T B_2^\T\mathbf D\)\({}=(B_2B_1)^\T\mathbf D\), which equals \((B_1B_2)^\T\mathbf D\) only if the factors commute; for a palindrome \(P=B_1\cdots B_KB_K\cdots B_1\) the same manipulation returns the reversed product, which is \(P\) itself, so \(\mathbf DP=P^\T\mathbf D\). A direct computation shows it on two binary variables: the Gibbs sweep \(B_1B_2\) is invariant but \(\max|\mathbf DT-(\mathbf DT)^\T|=0.053\), while \(B_1B_2B_1\) is reversible. ∎

Filling the gap 14.4: when does a chain converge to its invariant distribution? p. 444

The book says a homogeneous chain is ergodic "subject only to weak restrictions" (citing Neal, 1993). On a finite state space the restrictions are exactly two.

Derivation

Finite state space. If \(T\) is irreducible (every state can reach every other with positive probability in some number of steps) and aperiodic (the return times to a state have greatest common divisor 1), then the invariant distribution is unique and \(p(\bz^{(m)})\to p^\star\) geometrically fast from any start. This is the Perron–Frobenius theorem applied to the primitive matrix \(T\); a complete proof is Result 11.17 of the companion course. Both conditions are needed: the identity matrix (the book's example) is aperiodic but reducible and keeps any distribution; the swap \(\big(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\big)\) is irreducible but has period 2 and never converges from a point mass.

Metropolis–Hastings. If the proposal density is positive everywhere, every set of positive probability under \(p\) can be reached in one step, so the chain is irreducible; and since a proposal is rejected with positive probability somewhere, or the kernel has a density, the chain is aperiodic. This is why the book can say that positivity of \(q\) is sufficient (p. 441). General state spaces need the measure-theoretic versions of these notions (\(\varphi\)-irreducibility, Harris recurrence; Robert and Casella, 1999), but the intuition is the same.

What fails in practice is not ergodicity but its speed: Figure 14.14 shows a Gibbs sampler that is not irreducible, and Figure 14.S3 a Langevin sampler that is ergodic but needs astronomically many steps to move mass between two wells. ∎

14.2.3 The Metropolis–Hastings algorithm

See also the companion course, Section 11.2.2 and Result 11.19.

pp. 445–446 For an asymmetric proposal \(q_k\) (\(k\) labels a family of proposals) the candidate is accepted with probability

\[ A_k(\bz^\star,\bz^{(\tau)})=\min\Big(1,\frac{\pt(\bz^\star)\,q_k(\bz^{(\tau)}\given\bz^\star)}{\pt(\bz^{(\tau)})\,q_k(\bz^\star\given\bz^{(\tau)})}\Big), \tag{14.40} \]

which reduces to (14.27) for a symmetric proposal and again needs only \(\pt\).

Algorithm 14.2 (Metropolis–Hastings sampling) p. 446

  1. Start from \(\bz^{(0)}\); fix a rule \(k=M(\tau)\) choosing the proposal at step \(\tau\).
  2. For \(\tau=1,\dots,T\): draw \(\bz^\star\sim q_k(\bz\given\bz^{(\tau-1)})\) and \(u\sim\Unif(0,1)\); accept (\(\bz^{(\tau)}=\bz^\star\)) if \[ \frac{\pt(\bz^\star)\,q_k(\bz^{(\tau-1)}\given\bz^\star)}{\pt(\bz^{(\tau-1)})\,q_k(\bz^\star\given\bz^{(\tau-1)})}>u, \] otherwise repeat the old state.

(The book's listing drops the index \(k\) on \(q\) in the test.)

Result 14.9 (Metropolis–Hastings satisfies detailed balance) p. 445, (14.41)

For every proposal \(q_k\), the Metropolis–Hastings transition satisfies (14.34) with respect to \(p\), hence leaves \(p\) invariant:

\[ p(\bz)q_k(\bz'\given\bz)A_k(\bz',\bz)=\min\big(p(\bz)q_k(\bz'\given\bz),\,p(\bz')q_k(\bz\given\bz')\big)=p(\bz')q_k(\bz\given\bz')A_k(\bz,\bz'). \tag{14.41} \]
Proof

For \(\bz'\ne\bz\) the transition density is \(T(\bz,\bz')\)\({}=q_k(\bz'\given\bz)A_k(\bz',\bz)\). Multiply (14.40) by \(p(\bz)q_k(\bz'\given\bz)\) (the unknown \(Z_p\) cancels in the ratio): \(p(\bz)q_k(\bz'\given\bz)\min(1,\frac{p(\bz')q_k(\bz\given\bz')}{p(\bz)q_k(\bz'\given\bz)})\)\({}=\min(p(\bz)q_k(\bz'\given\bz),p(\bz')q_k(\bz\given\bz'))\), which is symmetric in \(\bz,\bz'\). The remaining part of \(T\) is a point mass at \(\bz'=\bz\) (the rejections), for which (14.34) holds trivially. With (14.35)–(14.37) this gives invariance. A direct computation verifies (14.41) on a random six-state example with an asymmetric proposal. ∎

The scale of the proposal. pp. 445–446 With a Gaussian proposal of scale \(\rho\) on a target whose standard deviations range from \(\sigma_{\min}\) to \(\sigma_{\max}\) (Figure 14.10), \(\rho\) must be of order \(\sigma_{\min}\) to keep the rejection rate down, and the chain then explores the long direction by a random walk of step \(\sigma_{\min}\): reaching distance \(\sigma_{\max}\) takes about \((\sigma_{\max}/\sigma_{\min})^2\) steps. (For a multivariate Gaussian Neal (1993) refines this to \((\sigma_{\max}/\sigma_2)^2\), with \(\sigma_2\) the second-smallest standard deviation.)

Filling the gap 14.5: why about \((\sigma_{\max}/\sigma_{\min})^2\) steps per independent sample p. 445, Figure 14.10

Derivation

Along the long axis the chain moves by increments of size about \(\rho\approx\sigma_{\min}\), roughly independent and of mean near zero (the target is nearly flat on that scale). By the random-walk law of Exercise 14.11, \(\tau\) such steps cover a distance of order \(\sigma_{\min}\sqrt\tau\); to forget the starting point the chain must travel about \(\sigma_{\max}\), so \(\tau\approx(\sigma_{\max}/\sigma_{\min})^2\). The companion course gives the same argument in more detail (Filling the gap 11.9). Figure 14.10(b) measures it: with \(\rho=\sigma_{\min}\), the integrated autocorrelation time of the long-axis coordinate is close to \(6.4\,(\sigma_{\max}/\sigma_{\min})^2\) for ratios 2 to 16, and doubling the ratio multiplies it by 3.7 in simulation (theory: 4). ∎

Left: a long thin red ellipse tilted at 35 degrees with arrows marking sigma max along it and sigma min across it; a grey Metropolis path of 400 steps wanders in its lower half and a small blue circle of radius rho marks the proposal scale. Right: integrated autocorrelation time against the squared ratio of standard deviations on log-log axes, five blue points on a dashed line proportional to the squared ratio.
Figure 14.10 (computed). (a) An isotropic proposal (blue circle, \(\rho=\sigma_{\min}\)) on a Gaussian with \(\sigma_{\max}/\sigma_{\min}=8\): after 400 steps the chain has explored only part of the long axis. (b) Measured integrated autocorrelation time of the long-axis coordinate against \((\sigma_{\max}/\sigma_{\min})^2\): proportional to it. Reproduces Bishop and Bishop (2024), Figure 14.10, with the scaling measured. Download: PDF · SVG

14.2.4 Gibbs sampling

See also the companion course, Section 11.3 (Gibbs sampling), Results 11.20–11.22, and the Metropolis and Gibbs demo.

pp. 446–448 Gibbs sampling (Geman and Geman, 1984) replaces one variable \(z_i\) at a time by a draw from its conditional distribution \(p(z_i\given\bz_{\setminus i})\) given all the others, cycling through the variables or choosing them at random. With three variables, at step \(\tau\):

\[ z_1^{(\tau+1)}\sim p(z_1\given z_2^{(\tau)},z_3^{(\tau)}), \tag{14.42} \] \[ z_2^{(\tau+1)}\sim p(z_2\given z_1^{(\tau+1)},z_3^{(\tau)}), \tag{14.43} \] \[ z_3^{(\tau+1)}\sim p(z_3\given z_1^{(\tau+1)},z_2^{(\tau+1)}), \tag{14.44} \]

each new value being used at once.

Algorithm 14.3 (Gibbs sampling) p. 448

  1. Initialise \(z_1,\dots,z_M\).
  2. For \(\tau=1,\dots,T\), for \(i=1,\dots,M\): draw \(z_i\sim p(z_i\given\{z_j\}_{j\ne i})\).
  3. Return the states (subsampled if nearly independent draws are wanted).

Result 14.10 (Gibbs sampling is Metropolis–Hastings that always accepts) pp. 447–448, (14.45); Exercise 14.12

  1. Each single-variable update leaves \(p\) invariant, and satisfies detailed balance.
  2. Viewed as Metropolis–Hastings with proposal \(q_k(\bz^\star\given\bz)\)\({}=p(z_k^\star\given\bz_{\setminus k})\), \(\bz^\star_{\setminus k}\)\({}=\bz_{\setminus k}\), its acceptance ratio is \[ A(\bz^\star,\bz)=\frac{p(\bz^\star)q_k(\bz\given\bz^\star)}{p(\bz)q_k(\bz^\star\given\bz)}=\frac{p(z^\star_k\given\bz^\star_{\setminus k})p(\bz^\star_{\setminus k})p(z_k\given\bz^\star_{\setminus k})}{p(z_k\given\bz_{\setminus k})p(\bz_{\setminus k})p(z_k^\star\given\bz_{\setminus k})}=1. \tag{14.45} \]
  3. A full systematic sweep is a composition (14.39): invariant, but in general not reversible; a random-scan sweep is a mixture (14.38) and is reversible.
  4. It is ergodic if, for example, no conditional is zero anywhere; if some are, ergodicity must be checked (Figure 14.14).
Proof (short; full version in Result 11.20)

(1) An update of \(z_k\) moves only to states \(\bz'\) with \(\bz'_{\setminus k}=\bz_{\setminus k}\), with kernel \(T(\bz,\bz')\)\({}=p(z_k'\given\bz_{\setminus k})\) there (and zero elsewhere). For such \(\bz'\), \[ p(\bz)T(\bz,\bz')=p(\bz_{\setminus k})\,p(z_k\given\bz_{\setminus k})\,p(z'_k\given\bz_{\setminus k}), \] which is symmetric under \(z_k\leftrightarrow z_k'\): detailed balance, hence invariance. (The book's argument: the marginal of \(\bz_{\setminus k}\) is untouched and the conditional is redrawn exactly, so the joint is unchanged.) (2) Use \(p(\bz)\)\({}=p(z_k\given\bz_{\setminus k})p(\bz_{\setminus k})\) and \(\bz^\star_{\setminus k}\)\({}=\bz_{\setminus k}\): numerator and denominator are the same product. (3) and (4) follow from Result 14.8 and Filling the gap 14.4. ∎

Gibbs on a correlated Gaussian. pp. 448–449 If the conditionals have width \(l\) and the marginals width \(L\) (Figure 14.11), each update moves about \(l\), and the book estimates \((L/l)^2\) steps per independent sample. For a bivariate Gaussian this can be computed exactly.

Result 14.11 (the exact cost of Gibbs sampling a bivariate Gaussian) p. 448, Figure 14.11

Let \((z_1,z_2)\) be Gaussian with unit variances and correlation \(r\), so \(L=1\) and the conditional standard deviation is \(l=\sqrt{1-r^2}\). Under systematic-scan Gibbs sampling, the sequence of \(z_1\) values (one per sweep) is an AR(1) process with coefficient \(r^2\), and its integrated autocorrelation time is

\[ \tau_{\rm int}=\frac{1+r^2}{1-r^2}=2\Big(\frac Ll\Big)^2-1 . \]
Proof

The conditionals are \(z_2\given z_1\sim\N(rz_1,1-r^2)\) and \(z_1\given z_2\sim\N(rz_2,1-r^2)\). One sweep gives \(z_2'=rz_1+\sqrt{1-r^2}\,\xi_1\) and \(z_1'\)\({}=rz_2'+\sqrt{1-r^2}\,\xi_2\)\({}=r^2z_1+r\sqrt{1-r^2}\,\xi_1+\sqrt{1-r^2}\,\xi_2\), with fresh independent standard normals: an AR(1) recursion with coefficient \(r^2\). By Result 14.1(2), \(\tau_{\rm int}=(1+r^2)/(1-r^2)\). Since \((L/l)^2=1/(1-r^2)\), \(\tau_{\rm int}\)\({}=\frac{2-(1-r^2)}{1-r^2}\)\({}=2(L/l)^2-1\). So the book's \(O((L/l)^2)\) is right, with constant 2 in sweeps. Measured values agree (Figure 14.11(b); 9.57 against 9.53 at \(r=0.9\)). ∎

Left: a thin red ellipse along the diagonal with a blue staircase path of 12 Gibbs sweeps moving in horizontal and vertical steps; a green bell curve drawn on a horizontal line shows a conditional distribution of width l, and an arrow below marks the marginal width L. Right: integrated autocorrelation time against (L/l) squared on log-log axes, blue dots on a dashed grey curve labelled 2 (L/l) squared minus 1.
Figure 14.11 (computed). (a) Gibbs sampling of a Gaussian with correlation 0.95 (\(L/l=3.2\)): steps of the size of the conditional width \(l\) (green) make slow progress along the ellipse. (b) Measured autocorrelation time of \(z_1\) against \((L/l)^2\), on the exact curve \(2(L/l)^2-1\) of Result 14.11. Reproduces Bishop and Bishop (2024), Figure 14.11, with the exact cost added. Download: PDF · SVG

Over-relaxation. p. 449 When the conditionals are Gaussian with mean \(\mu_i\) and variance \(\sigma_i^2\), Adler's (1981) over-relaxation replaces \(z_i\) by

\[ z_i'=\mu_i+\alpha_i(z_i-\mu_i)+\sigma_i(1-\alpha_i^2)^{1/2}\nu, \tag{14.46} \]

with \(\nu\sim\N(0,1)\) and \(-1<\alpha_i<1\); \(\alpha=0\) is Gibbs sampling and \(\alpha<0\) pushes to the other side of the mean, which suppresses random-walk behaviour along strong correlations. Ordered over-relaxation (Neal, 1999) extends the idea beyond Gaussian conditionals.

Result 14.12 (over-relaxation leaves the conditional exactly invariant and is reversible) p. 449, (14.46); Exercise 14.14

If \(z_i\sim\N(\mu_i,\sigma_i^2)\) given the other variables, then so is \(z_i'\); the pair \((z_i,z_i')\) is bivariate Gaussian with correlation \(\alpha_i\) and the same marginals, hence exchangeable, so the update satisfies detailed balance.

Erratum. The book motivates the method with "the non-Gaussian distribution \(p(z,y)\propto\exp(-z^2y^2)\)", whose conditionals are Gaussian. That function cannot be normalised: \(\int e^{-z^2y^2}\d z=\sqrt\pi/|y|\), and \(\int\d y/|y|\) diverges at 0 and at \(\infty\) (numerically, the mass over \([10^{-K},10^K]\) growing linearly in \(K\)). A proper example is \(p(z,y)\propto\exp(-z^2y^2-z^2-y^2)\), whose conditionals are still Gaussian. Exercise 14.14 also writes "variance \(\sigma_i\)" for \(\sigma_i^2\).

Proof (see also Result 11.22)

\(z_i'\) is a linear combination of the independent Gaussians \(z_i\) and \(\nu\): \(\E[z_i']=\mu_i+\alpha_i\cdot0=\mu_i\), \(\var[z_i']\)\({}=\alpha_i^2\sigma_i^2+\sigma_i^2(1-\alpha_i^2)\)\({}=\sigma_i^2\), \(\cov(z_i,z_i')=\alpha_i\sigma_i^2\). A bivariate Gaussian with equal marginals is symmetric under swapping its two components, which is detailed balance for the conditional kernel; the other variables are fixed during the update, so the joint \(p\) is invariant as in Result 14.10. ∎

Markov blankets and blocking. pp. 449–450 In a directed graphical model the conditional of a node depends only on its Markov blanket (parents, children and co-parents; Figure 14.12, not reproduced since it is a diagram; see Result 8.10 and Filling the gap 11.10 of the companion course). Many such conditionals are log-concave, so adaptive rejection sampling can draw from them. Blocking Gibbs samplers update groups of variables jointly (Jensen, Kong and Kjærulff, 1995) to weaken the dependence between successive states.

Left: two pink discs, one at lower left and one at upper right, with no overlap in either coordinate; a blue Gibbs path of horizontal and vertical segments fills only the lower-left disc. Right: two larger overlapping-in-projection pink discs, and the blue path fills both.
Figure 14.14 (computed). Exercise 14.13: a density uniform on two discs whose projections on both axes are disjoint (left). Every Gibbs move stays in the disc it starts in (300 sweeps, 0% of the path in the upper disc), so the chain is not ergodic. When the projections overlap (right), the chain moves between the discs (50% in the upper disc). Reproduces Bishop and Bishop (2024), Figure 14.14, with a Gibbs run added. Download: PDF · SVG

14.2.5 Ancestral sampling

See also the companion course, Filling the gap 11.1 (logic sampling) and Filling the gap 11.7 (likelihood weighting).

pp. 450–451 For a directed graph with joint distribution

\[ p(\bz)=\prod_{i=1}^Mp(\bz_i\given\mathrm{pa}(i)), \tag{14.47} \]

with the nodes numbered so that parents come first, one pass that draws each \(\bz_i\) from \(p(\bz_i\given\mathrm{pa}(i))\) with its parents already fixed gives an exact draw from the joint (ancestral sampling). With observed nodes (the evidence \(e\)), logic sampling (Henrion, 1988) discards a pass as soon as a sampled evidence node disagrees with its observed value; the survivors are exact posterior draws, but the acceptance probability \(p(e)\) shrinks rapidly with the amount of evidence. Likelihood weighting (Fung and Chang, 1990; Shachter and Peot, 1990) clamps the evidence nodes and samples the rest ancestrally, with weight

\[ r(\bz)=\prod_{\bz_i\notin e}\frac{p(\bz_i\given\mathrm{pa}(i))}{p(\bz_i\given\mathrm{pa}(i))}\prod_{\bz_i\in e}\frac{p(\bz_i\given\mathrm{pa}(i))}1=\prod_{\bz_i\in e}p(\bz_i\given\mathrm{pa}(i)). \tag{14.48} \]

Result 14.13 (ancestral, logic and likelihood-weighted sampling) pp. 450–451, (14.47)–(14.48); Exercise 14.15

(1) Ancestral sampling draws exactly from (14.47). (2) Logic sampling is rejection sampling with proposal \(p(\bz)\) and acceptance probability \(p(e)\). (3) Likelihood weighting is importance sampling with proposal \(q(\bz_U)\)\({}=\prod_{i\notin e}p(\bz_i\given\mathrm{pa}(i))\) (evidence clamped) for the unnormalised target \(p(\bz_U,e)\); its weights are (14.48), and the self-normalised estimate (14.22) converges to the posterior expectation.

Proof

(1) The probability of producing \(\bz\) is the product of the conditionals used, which is (14.47). (2) A pass survives iff its evidence nodes match \(e\), which happens with probability \(p(e)\); conditioned on surviving, the draw has density \(p(\bz)\Ind[\bz_e=e]/p(e)\)\({}=p(\bz_U\given e)\) (Result 14.3 with \(k=1\)). (3) The target is \(p(\bz_U,e)\)\({}=\prod_{i\notin e}p(\bz_i\given\mathrm{pa}(i))\prod_{i\in e}p(e_i\given\mathrm{pa}(i))\), with the parents evaluated at the sampled or clamped values; dividing by \(q\) cancels the first product, leaving (14.48). On a four-node network (cloudy, sprinkler, rain, wet grass) a direct computation gives \(p(\text{rain}\given\text{wet})=0.708\) exactly, 0.710 by logic sampling and 0.710 by likelihood weighting (100 000 passes each). ∎

14.3 Langevin Sampling

See also the companion course, Section 11.5 (hybrid Monte Carlo, the other sampler that uses gradients) and its slice sampling and HMC demo.

p. 451 Random-walk proposals ignore where the probability is. Just as gradients make training efficient, gradients of \(\ln p\) with respect to the data vector can steer a sampler uphill. Hamiltonian Monte Carlo does this with a Metropolis test (Duane et al., 1987); this section develops Langevin sampling, which in its basic form has no accept/reject step and is widely used in deep learning, notably for energy-based models.

14.3.1 Energy-based models

p. 452 A model \(p(\bx\given\bw)\) must integrate to one,

\[ \int p(\bx\given\bw)\,\d\bx=1, \tag{14.49} \]

(Erratum. The book prints \(\int p(\bx\given\bw)p(\bx)\,\d\bx=1\); the factor \(p(\bx)\) does not belong there.) Dropping this constraint gives much more freedom (LeCun et al., 2006).

Definition 14.2 (energy-based model, partition function) p. 452, (14.50)–(14.51)

Given any real-valued energy \(E(\bx,\bw)\), often a neural network with scalar output,

\[ p(\bx\given\bw)=\frac1{Z(\bw)}\exp\{-E(\bx,\bw)\}, \tag{14.50} \] \[ Z(\bw)=\int\exp\{-E(\bx,\bw)\}\,\d\bx , \tag{14.51} \]

provided \(0<Z(\bw)<\infty\). Low energy means high probability. The name is used when \(Z\) cannot be computed.

Filling the gap 14.6: when (14.50) is a model, and which models are energy-based p. 452; Exercises 14.16, 14.17

Derivation

Normalisation (Exercise 14.16). \(\int p\,\d\bx\)\({}=Z(\bw)^{-1}\int e^{-E}\,\d\bx\)\({}=1\) whenever \(Z\) is finite and positive. Finiteness is a real constraint: \(E(x)=-x^2\) or any energy bounded above on \(\R\) gives \(Z=\infty\). The model used in the demonstration, \(E(x,\bw)=x^2/18+\sum_kw_k\phi_k(x)\) with bounded bumps \(\phi_k\), is normalisable for every \(\bw\) because \(e^{-E}\le e^{\sum_k|w_k|}e^{-x^2/18}\).

Every positive density is energy-based, with \(E=-\ln p\) and \(Z=1\); the energy is defined only up to an additive constant, which \(Z\) absorbs.

Log likelihood (Exercise 14.17). For i.i.d. data, \(\ln p(\mathcal D\given\bw)\)\({}=\sum_n\ln p(\bx_n\given\bw)\)\({}=\sum_n\{-E(\bx_n,\bw)-\ln Z(\bw)\}\), which is (14.52) below. (The exercise asks to show that "the gradient of the log likelihood" has the form (14.52); (14.52) is the log likelihood itself.) ∎

p. 452 The partition function depends on \(\bw\), and so does the log likelihood of an i.i.d. data set \(\mathcal D=(\bx_1,\dots,\bx_N)\):

\[ \ln p(\mathcal D\given\bw)=-\sum_{n=1}^NE(\bx_n,\bw)-N\ln Z(\bw). \tag{14.52} \]

14.3.2 Maximizing the likelihood

pp. 453–454 Training can avoid \(Z\) altogether (score matching, Chapter 20 of the book; Song and Kingma, 2021), or approximate the likelihood gradient by Monte Carlo, as here. For one data point,

\[ \nabla_\bw\ln p(\bx\given\bw)=-\nabla_\bw E(\bx,\bw)-\nabla_\bw\ln Z(\bw), \tag{14.53} \]

and averaging over the data distribution \(p_{\mathcal D}\),

\[ \E_{\bx\sim p_{\mathcal D}}[\nabla_\bw\ln p(\bx\given\bw)]=-\E_{\bx\sim p_{\mathcal D}}[\nabla_\bw E(\bx,\bw)]-\nabla_\bw\ln Z(\bw). \tag{14.54} \]

Differentiating (14.51),

\[ -\nabla_\bw\ln Z(\bw)=\int\{\nabla_\bw E(\bx,\bw)\}\,p(\bx\given\bw)\,\d\bx, \tag{14.55} \]

an expectation under the model \(p_{\mathcal M}(\bx)=p(\bx\given\bw)\),

\[ \int\{\nabla_\bw E(\bx,\bw)\}\,p(\bx\given\bw)\,\d\bx=\E_{\bx\sim\mathcal M}[\nabla_\bw E(\bx,\bw)], \tag{14.56} \]

so that

\[ \nabla_\bw\E_{\bx\sim p_{\mathcal D}}[\ln p(\bx\given\bw)]=-\E_{\bx\sim p_{\mathcal D}}[\nabla_\bw E(\bx,\bw)]+\E_{\bx\sim p_{\mathcal M}(\bx)}[\nabla_\bw E(\bx,\bw)]. \tag{14.57} \]

Result 14.14 (the likelihood gradient of an energy-based model) pp. 453–454, (14.53)–(14.57); Exercise 14.18

  1. (14.55) and (14.57) hold whenever differentiation under the integral in (14.51) is allowed, for instance if \(\|\nabla_\bw E(\bx,\bw)\|e^{-E(\bx,\bw)}\) is bounded, for \(\bw\) in a neighbourhood, by an integrable function of \(\bx\).
  2. Positive and negative phase. The first term of (14.57) lowers the energy (raises the density) at data points; the second raises it at samples from the model (Figure 14.13). Where \(p_{\mathcal M}>p_{\mathcal D}\) the net effect raises the energy, where \(p_{\mathcal M}<p_{\mathcal D}\) it lowers it.
  3. The second derivative is a covariance: \(\nabla_\bw\nabla_\bw^\T\ln Z\)\({}=\cov_{\mathcal M}[\nabla_\bw E]-\E_{\mathcal M}[\nabla_\bw\nabla_\bw^\T E]\). For an energy linear in the parameters, \(E=E_0(\bx)+\bw^\T\bphi(\bx)\), \(\ln Z\) is convex, the average log likelihood is concave, and the gradient (14.57) vanishes exactly when \(\E_{p_{\mathcal D}}[\bphi]\)\({}=\E_{p_{\mathcal M}}[\bphi]\) (moment matching).
  4. The gradient vanishes if \(p_{\mathcal M}=p_{\mathcal D}\) (as the book says), but not only then: a zero of (14.57) need not have \(p_{\mathcal M}=p_{\mathcal D}\) when the family cannot represent \(p_{\mathcal D}\).
Proof

(1) and Exercise 14.18. \(\nabla_\bw\ln Z\)\({}=\frac1Z\nabla_\bw\int e^{-E}\d\bx\)\({}=\frac1Z\int(-\nabla_\bw E)e^{-E}\d\bx\)\({}=-\int\nabla_\bw E\,p(\bx\given\bw)\,\d\bx\), which is (14.55)–(14.56); the interchange of \(\nabla_\bw\) and \(\int\) is justified by dominated convergence under the stated bound (applied to difference quotients via the mean value theorem). Substituting into (14.54) gives (14.57); \(\ln Z\) can be taken outside the expectation over \(p_{\mathcal D}\) because it does not depend on \(\bx\).

(2) A small step \(\Delta\bw=\epsilon\,g\) along the gradient changes the energy at \(\bx\) by \(\epsilon\nabla_\bw E(\bx)^\T g\). For the positive phase alone, \(g=-\E_{\mathcal D}[\nabla_\bw E]\), and averaged over the data the change is \(-\epsilon\|\E_{\mathcal D}[\nabla_\bw E]\|^2\le0\): energy goes down at the data. The negative phase does the opposite at model samples.

(3) Differentiate (14.55) once more: \(\nabla\nabla^\T\ln Z\)\({}=-\int\nabla\nabla^\T E\,p\,\d\bx-\int\nabla E\,(\nabla p)^\T\d\bx\), and \(\nabla_\bw p\)\({}=p\,(-\nabla_\bw E-\nabla_\bw\ln Z)\)\({}=p\,(\E_{\mathcal M}[\nabla E]-\nabla E)\), which gives the covariance. With \(E\) linear in \(\bw\), \(\nabla\nabla^\T E=0\), so the Hessian of \(\ln Z\) is a covariance matrix, positive semi-definite; the average log likelihood \(-\E_{\mathcal D}[E]-\ln Z\) is then concave, and its gradient \(-\E_{\mathcal D}[\bphi]+\E_{\mathcal M}[\bphi]\) is zero iff the moments match. This is the exponential family of the book's Section 3.4 (see these notes).

(4) Take the demonstration's model (17 Gaussian bumps). Newton's method on the concave log likelihood reaches a point with \(\max_k|\partial/\partial w_k|\)\({}=2\times10^{-6}\), where the moments match, yet \(\KL(p_{\mathcal D}\,\|\,p_{\mathcal M})\)\({}=0.146\) for the true data density: the family cannot represent the two Gaussian components exactly, and the fit is to the 200 data points, not to \(p_{\mathcal D}\). ∎

A direct computation confirms (14.55) and (14.57) against finite differences of the quadrature \(\ln Z\) (agreement to \(4\times10^{-10}\)) and the Hessian against the model covariance.

A green energy curve, high and flat on the left and with a deep well near x = 3.5; a red dashed data density with two bumps at about -2 and 0.5; a blue dashed model density with a single peak at 3.5. Red dots on the axis mark six data points with green arrows pushing the energy down above them; blue dots under the model peak mark eight Langevin samples with green arrows pushing the energy up.
Figure 14.13 (computed). The two phases of (14.57) for the one-dimensional energy-based model of the demonstration, at its starting point: the model density \(p_{\mathcal M}\) (blue) sits in an energy well where there are no data, while the data density \(p_{\mathcal D}\) (red) has two bumps. Gradient ascent lowers the energy at data points (red dots) and raises it at model samples (blue dots, drawn by 3000 steps of Langevin sampling (14.61)). Reproduces Bishop and Bishop (2024), Figure 14.13. Download: PDF · SVG
▶ DemoTrain this model with the exact negative phaseThe well at \(x=3.5\) is removed and the density moves onto the data; the log likelihood is computed exactly by quadrature.

14.3.3 Langevin dynamics

pp. 454–455 The data term of (14.57) is an average over the training set,

\[ \E_{\bx\sim p_{\mathcal D}}[\nabla_\bw E(\bx,\bw)]\simeq\frac1N\sum_{n=1}^N\nabla_\bw E(\bx_n,\bw). \tag{14.58} \]

The model term needs samples from \(p_{\mathcal M}\). Langevin sampling (Parisi, 1981; Welling and Teh, 2011) uses only the score, the gradient of the log density with respect to the data vector (not the parameters),

\[ \bs(\bx,\bw)=\nabla_\bx\ln p(\bx\given\bw), \tag{14.59} \]

which for (14.50) is

\[ \bs(\bx,\bw)=-\nabla_\bx E(\bx,\bw): \tag{14.60} \]

\(Z(\bw)\) has dropped out, because it does not depend on \(\bx\). Starting from \(\bx^{(0)}\) drawn from some initial distribution, iterate

\[ \bx^{(\tau+1)}=\bx^{(\tau)}+\eta\nabla_\bx\ln p(\bx^{(\tau)},\bw)+\sqrt{2\eta}\,\beps^{(\tau)},\qquad\tau\in1,\dots,T, \tag{14.61} \]

with independent \(\beps^{(\tau)}\sim\N(\bzero,\bI)\) and step size \(\eta\): a gradient step uphill on \(\ln p\) plus Gaussian noise. The book states that as \(\eta\to0\) and \(T\to\infty\) the final value is a sample from \(p(\bx)\) (it writes \(\bz^{(T)}\) for \(\bx^{(T)}\)). Repeating gives samples \(\bx_1,\dots,\bx_M\) and

\[ \E_{\bx\sim p_{\mathcal M}(\bx)}[\nabla_\bw E(\bx,\bw)]\simeq\frac1M\sum_{m=1}^M\nabla_\bw E(\bx_m,\bw). \tag{14.62} \]

Algorithm 14.4 (Langevin sampling) p. 456

  1. Input \(\bx^{(0)}\), the score of \(p(\bx,\bw)\), the step size \(\eta\) and the number of steps \(T\).
  2. For \(\tau=1,\dots,T\): draw \(\beps\sim\N(\bzero,\bI)\) and set \(\bx\leftarrow\bx+\eta\nabla_\bx\ln p(\bx,\bw)+\sqrt{2\eta}\,\beps\).
  3. Return \(\bx^{(T)}\).

Two names: in this book "score" means \(\nabla_\bx\ln p\), the gradient with respect to the data; the "score-function estimator" of Filling the gap 14.2 uses the statistician's score \(\nabla_\btheta\ln q\), the gradient with respect to parameters. With exact gradients (14.61) is often called the unadjusted Langevin algorithm; Welling and Teh's stochastic gradient Langevin dynamics is the same update with a mini-batch gradient (Filling the gap 14.8).

Why should (14.61) sample from \(p\)? The book says it "can be shown". Here is the argument in three steps: one step from \(p\) is correct to first order in \(\eta\); in the limit of small steps the dynamics has \(p\) as its exact stationary distribution; and for a Gaussian the leftover bias can be computed exactly.

Result 14.15 (one Langevin step leaves \(p\) invariant to first order) p. 455, (14.61)

Let \(p\) be smooth and positive with \(p\,\nabla\varphi\to0\) at infinity, and let \(\varphi\) be a smooth test function with bounded derivatives up to order four. If \(\bx\sim p\) and \(\bx'\)\({}=\bx+\eta\bs(\bx)+\sqrt{2\eta}\,\beps\), then

\[ \E[\varphi(\bx')\given\bx]=\varphi(\bx)+\eta\,\big(\bs\cdot\nabla\varphi+\Delta\varphi\big)(\bx)+O(\eta^2),\qquad\E_p[\varphi(\bx')]-\E_p[\varphi(\bx)]=O(\eta^2), \]

with \(\Delta\) the Laplacian. Over the \(t/\eta\) steps needed to cover a fixed "time" \(t\), the per-step defects add up to \(O(\eta)\): the stationary distribution of (14.61) differs from \(p\) by \(O(\eta)\), and is exactly \(p\) only in the limit \(\eta\to0\).

Proof

Taylor expansion. Write \(\bx'=\bx+\Delta\) with \(\Delta=\eta\bs+\sqrt{2\eta}\,\beps\). Then \(\E_\beps[\Delta]=\eta\bs\), \(\E_\beps[\Delta\Delta^\T]\)\({}=\eta^2\bs\bs^\T+2\eta\bI\), and the third and fourth moments of \(\Delta\) are \(O(\eta^2)\) (the term of order \(\eta^{3/2}\) is an odd moment of \(\beps\), which vanishes). Expanding \(\varphi(\bx+\Delta)\) to fourth order and taking expectations over \(\beps\): \[ \E[\varphi(\bx')\given\bx]=\varphi+\eta\,\bs\cdot\nabla\varphi+\tfrac12\Tr\big(\nabla\nabla^\T\varphi\,(2\eta\bI)\big)+O(\eta^2)=\varphi+\eta(\bs\cdot\nabla\varphi+\Delta\varphi)+O(\eta^2). \]

The first-order term has mean zero under \(p\). Since \(p\,\bs=p\nabla\ln p=\nabla p\), \[ \int p\,(\bs\cdot\nabla\varphi+\Delta\varphi)\,\d\bx=\int(\nabla p\cdot\nabla\varphi+p\,\Delta\varphi)\,\d\bx=\int\nabla\cdot(p\nabla\varphi)\,\d\bx=0 \] by the divergence theorem, the boundary term vanishing by assumption. So \(\E_p[\varphi(\bx')]\)\({}=\E_p[\varphi(\bx)]+O(\eta^2)\).

Accumulation. Each step started at \(p\) moves the expectation of every such \(\varphi\) by \(O(\eta^2)\); the chain needs about \(t_{\rm mix}/\eta\) steps to mix, during which the defects accumulate to \(O(\eta)\). Result 14.16 shows this is sharp for a Gaussian (bias \(\eta/2\) in the variance). Numerically, for the double-well density \(p\propto e^{-x^4/4+x^2/2}\) the one-step defect of \(\varphi=\cos1.3x+0.2x^2\) falls from \(1.08\times10^{-4}\) to \(2.75\times10^{-5}\) when \(\eta\) is halved from 0.01, a factor 3.9 (theory: 4). ∎

Filling the gap 14.7: the continuous-time limit, its exact stationary distribution, and convergence p. 455

The phrase "in the limits \(\eta\to0\) and \(T\to\infty\)" refers to a stochastic differential equation of which (14.61) is the Euler–Maruyama discretisation with time step \(\eta\).

Derivation

The Langevin diffusion. Let \(\d\bx_t\)\({}=\bs(\bx_t)\,\d t+\sqrt2\,\d\mathbf W_t\), with \(\mathbf W\) a Brownian motion. Over a time step \(\eta\), \(\mathbf W\) increases by \(\sqrt\eta\,\beps\), which gives (14.61). From Result 14.15, \(\frac{\d}{\d t}\E[\varphi(\bx_t)]\)\({}=\E[\bs\cdot\nabla\varphi+\Delta\varphi]\); writing \(\rho_t\) for the density of \(\bx_t\) and integrating by parts gives the Fokker–Planck equation \[ \partial_t\rho_t=-\nabla\cdot(\rho_t\bs)+\Delta\rho_t=\nabla\cdot\Big(\rho_t\nabla\ln\frac{\rho_t}{p}\Big), \] using \(\Delta\rho\)\({}=\nabla\cdot(\rho\nabla\ln\rho)\) and \(\bs=\nabla\ln p\).

\(p\) is stationary. At \(\rho_t=p\), \(\ln(\rho_t/p)=0\) and the right side vanishes: there is no discretisation error in continuous time.

Convergence. Differentiate the KL divergence and integrate by parts: \[ \frac{\d}{\d t}\KL(\rho_t\,\|\,p)=\int\partial_t\rho_t\,\ln\frac{\rho_t}p\,\d\bx=-\int\rho_t\,\Big\|\nabla\ln\frac{\rho_t}{p}\Big\|^2\d\bx\le0, \] (the term \(\int\partial_t\rho_t\,\d\bx=0\) drops out), with equality only if \(\rho_t\propto p\). The right side is the relative Fisher information; if \(p\) satisfies a logarithmic Sobolev inequality with constant \(\lambda\) (true, for example, for \(\lambda\)-strongly log-concave \(p\)), it is at least \(2\lambda\KL\), and the divergence decays like \(e^{-2\lambda t}\). For multimodal \(p\) the constant can be tiny and convergence very slow (Filling the gap 14.9).

Changing the noise. With noise \(c\sqrt{2\eta}\,\beps\) instead of \(\sqrt{2\eta}\,\beps\) (the demo's slider \(c\)), the Fokker–Planck equation becomes \(\partial_t\rho\)\({}=-\nabla\cdot(\rho\bs)+c^2\Delta\rho\), whose stationary density is \(\rho\propto p^{1/c^2}\) (check: \(c^2\nabla\rho=\rho\bs\)). So \(c<1\) sharpens the target, \(c=0\) is gradient ascent on \(\ln p\) and converges to a mode, and \(c>1\) flattens it (a higher "temperature"). A direct computation confirms the variance \(c^2\sigma^2/(1-\eta/2\sigma^2)\) for \(c=0.5\). ∎

Result 14.16 (Langevin sampling of a Gaussian: exact bias, stability, mixing time) p. 455, (14.61)

For \(p=\N(0,\sigma^2)\), (14.61) is \(x'\)\({}=(1-\eta/\sigma^2)x+\sqrt{2\eta}\,\epsilon\). It converges iff \(0<\eta<2\sigma^2\), and then its stationary distribution is exactly

\[ \N\Big(0,\ \frac{\sigma^2}{1-\eta/(2\sigma^2)}\Big)=\N\big(0,\ \sigma^2+\tfrac\eta2+O(\eta^2)\big), \]

and the integrated autocorrelation time of \(x\) is \(2\sigma^2/\eta-1\). For \(\N(\bzero,\Sig)\) the same holds along each eigenvector of \(\Sig\) with its own \(\sigma_i^2\): stability needs \(\eta<2\sigma^2_{\min}\), and then the slowest direction has \(\tau_{\rm int}>\sigma^2_{\max}/\sigma^2_{\min}\), the condition number of \(\Sig\).

Proof

The score of \(\N(0,\sigma^2)\) is \(-x/\sigma^2\), so the update is AR(1) with coefficient \(a=1-\eta/\sigma^2\) and noise variance \(2\eta\). It is stable iff \(|a|<1\), i.e. \(0<\eta<2\sigma^2\). A stationary variance \(v\) must satisfy \(v=a^2v+2\eta\), so \[ v=\frac{2\eta}{1-a^2}=\frac{2\eta}{2\eta/\sigma^2-\eta^2/\sigma^4}=\frac{\sigma^2}{1-\eta/(2\sigma^2)}, \] and a Gaussian AR(1) process has a Gaussian stationary law. Its autocorrelations are \(a^k\), so Result 14.1(2) gives \(\tau_{\rm int}\)\({}=(1+a)/(1-a)\)\({}=(2-\eta/\sigma^2)/(\eta/\sigma^2)\)\({}=2\sigma^2/\eta-1\). For \(\N(\bzero,\Sig)\) the update \(\bx'\)\({}=(\bI-\eta\Sig^{-1})\bx+\sqrt{2\eta}\,\beps\) decouples in the eigenbasis of \(\Sig\) (the noise is isotropic, so it stays independent across eigen-directions). With \(\eta<2\sigma^2_{\min}\), the largest direction has \(\tau_{\rm int}\)\({}=2\sigma^2_{\max}/\eta-1>\sigma^2_{\max}/\sigma^2_{\min}-1\). ∎

This is the same trade-off as for gradient descent on a quadratic (Result 7.6): the steep direction limits the step, the shallow one sets the time. A simulation gives a stationary variance of 1.337 against \(4/3\) for \(\eta=0.5\), \(\sigma=1\), and \(\tau_{\rm int}=19.7\) against 19 for \(\eta=0.1\).

Result 14.17 (the Metropolis-adjusted Langevin algorithm, MALA) p. 451 ("an acceptance test"); Roberts and Tweedie (1996)

Use the Langevin move as a Metropolis–Hastings proposal, \(q(\bx'\given\bx)\)\({}=\N\big(\bx'\given\bx+\eta\bs(\bx),\,2\eta\bI\big)\), and accept with (14.40):

\[ \ln A=\ln\pt(\bx')-\ln\pt(\bx)-\frac{\|\bx-\bx'-\eta\bs(\bx')\|^2-\|\bx'-\bx-\eta\bs(\bx)\|^2}{4\eta}. \]

The resulting chain leaves \(p\) exactly invariant for every \(\eta>0\) (no discretisation bias), and the acceptance rate tends to 1 as \(\eta\to0\).

Proof

The log of the proposal density is \(-\|\bx'-\bx-\eta\bs(\bx)\|^2/(4\eta)\) plus a constant that cancels in the ratio, which gives \(\ln A\). Detailed balance and invariance then follow from Result 14.9, whatever the proposal. As \(\eta\to0\), expanding the two squared norms shows that \(\ln A=O(\eta^{3/2})\) for typical \(\bx,\beps\) (the terms of order \(\eta^{1/2}\) and \(\eta\) cancel because the proposal is the discretisation of a \(p\)-reversible diffusion), so \(A\to1\). A direct computation confirms detailed balance numerically on the banana target and a variance of 0.996 (against 1) where unadjusted Langevin gives 1.337. ∎

A grid of twelve panels: rows are a tilted Gaussian, a banana-shaped density and two separated wells; columns are Langevin with step 0.02, Langevin with a larger step, MALA with the larger step, and no noise. Blue dots are 300 chains after 1000 steps and a red line is one chain's path. With no noise all chains collapse onto the modes. In the Gaussian row the large-step Langevin cloud is too wide across the narrow axis. In the wells row the chains split about evenly between the wells although the left well should hold 70 percent.
Figure 14.S3 (our own). 300 Langevin chains after 1000 steps on three targets. Gaussian row: the minor-axis variance (target 0.160) is 0.179 for \(\eta=0.02\) (Langevin's limit 0.171, plus sampling noise from 300 chains) but 0.449 for \(\eta=0.2\), close to the theory value 0.427; MALA with \(\eta=0.2\) gives 0.158 with acceptance 0.71. Banana row: with \(\eta=0.1\) the unadjusted chains are still stable; at \(\eta=0.2\) (not shown) some diverge, because the curvature of \(\ln p\) grows without bound in the tails. Wells row: no method fixes the near 50/50 split in 1000 steps (47% to 54% of the chains in the right well; target 30%). Right column: without noise, (14.61) is gradient ascent. Generated by langevin_run, the same code as the demo. Download: PDF · SVG
Three panels. Left: stationary variance against step size on a log scale; red circles for Langevin follow a red curve 1 over 1 minus eta over 2 that rises to about 10 at eta = 1.8, while blue squares for MALA stay at 1. Middle: integrated autocorrelation time against step size on log-log axes; the red line 2 over eta minus 1 falls from 100 to below 1, blue squares for MALA follow it until about eta = 0.7 and then rise, labelled with acceptance rates 0.99, 0.87 and 0.55. Right: fraction of 400 chains in the right well against time for two step sizes; both start near 0.47 and drift slowly towards the target 0.3.
Figure 14.S4 (our own). (a) Langevin sampling of \(\N(0,1)\) has stationary variance exactly \(1/(1-\eta/2)\) (Result 14.16); MALA has variance 1 at every step size. (b) Mixing time \(2\sigma^2/\eta-1\): small steps are accurate but slow; MALA mixes like Langevin until rejections set in. (c) Two wells with weights 0.7 and 0.3: chains started from a broad distribution split about 50/50 between the wells and the split relaxes towards 0.3 only very slowly. Download: PDF · SVG
▶ DemoLangevin sampling of a correlated Gaussian300 chains; the variance along the narrow axis settles at the target 0.16 (Langevin's own limit with \(\eta=0.02\) is 0.171).
▶ DemoA large step: the bias \(\sigma^2/(1-\eta/2\sigma^2)\)\(\eta=0.25\) near the stability limit \(2\sigma^2_{\min}=0.32\): variance 0.73 instead of 0.16. Preset 3 adds the Metropolis correction and removes the bias.
▶ DemoNo noise: gradient ascent onto the modeSet \(c=0\): every chain climbs to the maximum of \(\ln p\). Move \(c\) back to 1, or beyond, to see the target sharpen or flatten.

Filling the gap 14.8: stochastic gradient Langevin dynamics p. 455 (Welling and Teh, 2011)

Derivation

Welling and Teh (2011) sample a Bayesian posterior \(p(\btheta\given\mathcal D)\propto p(\btheta)\prod_{n=1}^Np(\bx_n\given\btheta)\) with the mini-batch estimate of its score, \(\widehat\bs\)\({}=\nabla\ln p(\btheta)+\frac NB\sum_{n\in\mathcal B}\nabla\ln p(\bx_n\given\btheta)\), which is unbiased for \(\bs\)\({}=\nabla\ln p(\btheta\given\mathcal D)\) when the batch \(\mathcal B\) of size \(B\) is drawn uniformly. Their update with step \(\epsilon_t\) is \(\btheta\leftarrow\btheta+\frac{\epsilon_t}2\widehat\bs+\N(\bzero,\epsilon_t\bI)\), which is (14.61) with \(\eta=\epsilon_t/2\).

Why the mini-batch noise is harmless for small steps. Write \(\eta\widehat\bs\)\({}=\eta\bs+\eta(\widehat\bs-\bs)\). The extra term has mean zero and covariance \(\eta^2\mathbf V\), with \(\mathbf V\) the covariance of the mini-batch score, while the injected noise has covariance \(2\eta\bI\). Their ratio is \(\eta\mathbf V/2\to0\) as \(\eta\to0\): in the small-step limit the gradient noise is swamped by the injected noise and the dynamics is the same Langevin diffusion. Welling and Teh therefore let \(\epsilon_t\) decrease with \(\sum_t\epsilon_t=\infty\) and \(\sum_t\epsilon_t^2<\infty\) (the Robbins–Monro conditions of the book's Section 7.3.2), which removes both the discretisation bias of Result 14.16 and the gradient-noise bias in the limit. The book's phrase "stochastic gradient Langevin dynamics or simply Langevin sampling" merges the two; (14.61) as written uses exact gradients. ∎

Filling the gap 14.9: "an independent sample in the limit": the problem of several modes p. 455

Derivation

The limit \(T\to\infty\) hides a time scale. For the two-well target of the demonstration (weights 0.7 and 0.3, means \(\pm2.5\), standard deviation 0.55), the log density at the midpoint is lower than at the modes by about \(2.5^2/(2\cdot0.55^2)\approx10\) nats. Transitions of a Langevin diffusion over such a barrier happen at a rate that decreases roughly like \(e^{-\Delta}\) with the barrier height \(\Delta\) (the Arrhenius–Kramers law of statistical physics, stated here without proof), so equilibrating the weights takes on the order of \(e^{10}\approx2\times10^4\) time units, millions of steps. Chains started from a broad distribution fall into the nearest well and stay; the fraction in each well reflects the starting distribution and the basins of attraction, not the target weights (Figure 14.S4(c); 53% instead of 30% after 3000 steps). MALA has the same problem: its acceptance step corrects the local shape, not the global weights. This is one motivation for the noise-perturbed scores of diffusion models (Chapter 20 of the book): at high noise the modes merge and can be traversed. ∎

▶ DemoTwo wells: chains do not cross the barrierThe right well keeps about half of the chains instead of 30% however long you run.

Contrastive divergence. p. 455 Long chains are expensive inside a training loop. Contrastive divergence (Hinton, 2002) starts each negative-phase chain at a training point and runs only a few steps, perhaps one. The samples are then biased towards the data, and the book remarks that this shapes the energy only near the data: useful for discrimination, less so for a generative model. This can be made precise.

Result 14.18 (what contrastive divergence optimises) p. 455

Let CD-\(k\) replace the model samples in (14.62) by \(\bx_n^{(k)}\), the result of \(k\) Langevin steps (14.61) from a data point \(\bx_n\). Its expected update direction is \(\frac1N\sum_n\big(\E[\nabla_\bw E(\bx_n^{(k)})]-\nabla_\bw E(\bx_n)\big)\). Then:

  1. for \(k=0\) the update is exactly zero; as \(k\to\infty\), if the chain is ergodic, it tends to the maximum-likelihood gradient (14.57);
  2. for \(k=1\) and small \(\eta\), with \(\psi_j=\partial E/\partial w_j\) and the score \(s=-\partial E/\partial x\) (one dimension for simplicity), \[ \E[\psi_j(x_n^{(1)})]-\psi_j(x_n)=\eta\,\big(s\,\psi_j'+\psi_j''\big)(x_n)+O(\eta^2), \] and averaging over the data gives \(-\eta\,\partial J_{\rm SM}/\partial w_j+O(\eta^2)\), where \[ J_{\rm SM}(\bw)=\frac1N\sum_n\Big[\tfrac12s(x_n,\bw)^2+\partial_xs(x_n,\bw)\Big] \] is Hyvärinen's (2005) score-matching objective, equal up to a constant independent of \(\bw\) to \(\frac12\E_{p_{\mathcal D}}[(s-\partial_x\ln p_{\mathcal D})^2]\).

So CD-1 with Langevin steps is, to first order, gradient descent on score matching. Score matching compares only the slopes of \(\ln p\) at the data; it cannot see probability mass in regions where there are no data.

Proof

(1) For \(k=0\), \(\bx_n^{(0)}=\bx_n\) and the two terms cancel. For \(k\to\infty\), ergodicity gives \(\E[\nabla_\bw E(\bx_n^{(k)})]\to\E_{p_{\mathcal M}}[\nabla_\bw E]\) for every start (with the discretisation bias of Result 14.15 unless \(\eta\to0\) or a Metropolis correction is used), and the update tends to (14.57).

(2) The first display is Result 14.15 with \(\varphi=\psi_j\). For the second, differentiate \(J_{\rm SM}\): \(\partial s/\partial w_j\)\({}=-\partial_x\partial E/\partial w_j\)\({}=-\psi_j'\) and \(\partial(\partial_xs)/\partial w_j\)\({}=-\psi_j''\), so \[ \frac{\partial J_{\rm SM}}{\partial w_j}=\frac1N\sum_n\big[s\,(-\psi_j')+(-\psi_j'')\big](x_n)=-\frac1N\sum_n\big(s\,\psi_j'+\psi_j''\big)(x_n). \] Comparing with the first display, the average CD-1 direction is \(-\eta\,\partial J_{\rm SM}/\partial w_j+O(\eta^2)\); the CD update ascends this direction, i.e. it descends \(J_{\rm SM}\). Finally, \(\E_{p_{\mathcal D}}[s\,\partial_x\ln p_{\mathcal D}]\)\({}=\int s\,\partial_xp_{\mathcal D}\,\d x\)\({}=-\int\partial_xs\,p_{\mathcal D}\,\d x\) by parts (boundary terms vanishing), so \(\frac12\E_{p_{\mathcal D}}[(s-\partial_x\ln p_{\mathcal D})^2]\)\({}=\E_{p_{\mathcal D}}[\frac12s^2+\partial_xs]+\const\), whose empirical version is \(J_{\rm SM}\).

Consequence. In the demonstration the model starts with a deep well at \(x=3.5\), far from all data. The weights of the bumps there barely affect \(s\) or \(\partial_xs\) at the data, so score matching, and CD-1, leave the well in place: after 300 updates 75% of the model's mass is still at \(x>2\), while persistent chains (which wander into the well) and long chains from noise remove it (0.35% and 0.03%). A direct computation confirms the expansion: the relative difference between the expected CD-1 update divided by \(\eta\) and \(-\nabla J_{\rm SM}\) is \(2.5\times10^{-3}\) at \(\eta=10^{-3}\) and ten times smaller at \(\eta=10^{-4}\) (Figure 14.S6). ∎

Left: the data density shaded pink with two bumps, a dotted grey starting model with one peak at 3.5, and four trained model densities: green exact, orange Langevin from noise and blue persistent chains all follow the two bumps, while the red contrastive-divergence curve keeps a tall peak at 3.5 and only small bumps at the data. Right: average log likelihood against iteration; three curves rise within about 30 iterations to near the dashed reference line, the red contrastive-divergence curve climbs slowly to about minus 3.
Figure 14.S5 (our own). Training the energy-based model of Figure 14.13 by (14.57) with four estimates of the negative phase (300 updates, learning rate 1, 100 chains, \(\eta=0.05\)): exact quadrature, fresh Langevin chains from noise (100 steps each), contrastive divergence with one step, and persistent chains with 5 steps per update. Contrastive divergence leaves the spurious mode in place (Result 14.18); the log likelihood (computed exactly) shows the cost. Download: PDF · SVG
▶ DemoContrastive divergence with one step: the spurious mode survivesChains start at the data and never visit \(x=3.5\); compare preset 4 (persistent chains) and preset 5 (CD with 30 steps).
▶ DemoLangevin chains from noise (14.61)–(14.62)Shorten \(T\) or enlarge \(\eta\) and watch the negative phase degrade.
Left: a scatter of 17 points, one per weight, lying on the identity line: the expected one-step contrastive-divergence update divided by eta against minus the score-matching gradient. Right: the relative difference between the two against eta on log-log axes, a straight line of slope one from about 3e-4 at eta = 1e-4 to about 0.3 at eta = 0.3.
Figure 14.S6 (our own). Result 14.18 numerically: (a) the expected CD-1 update (by Gauss–Hermite quadrature over the Langevin noise) divided by \(\eta\) equals \(-\nabla J_{\rm SM}\) weight by weight at \(\eta=0.01\); (b) the relative difference is \(O(\eta)\). Download: PDF · SVG

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

  • p. 434, rejection sampling: "otherwise \(u_0\) is retained" should read \(z_0\); \(u_0\) is only the auxiliary height.
  • (14.16) and Exercise 14.8: the function written \(q(z)\) is the comparison function \(kq(z)\) (it is not normalised); with \(z\) uniform on \([0,1]\), \(y=b\tan z+c\) only takes values in \([c,c+b\tan1]\) and is not Cauchy; \(z\) must be uniform on \((-\pi/2,\pi/2)\) (checked: all values \(\ge c\), whereas a Cauchy puts half its mass below \(c\)).
  • p. 435: \(c=a-1\), \(b^2=2a-1\) do not give "the minimum reject rate". For \(a=10\) the best Cauchy envelope has \(c=9.33\), \(b^2=9.55\) and accepts 64.6% against 55.4% (rejection 35.4% against 44.6%; both confirmed by simulation; Filling the gap 14.3).
  • (14.39): the sums run over \(\bz_1,\dots,\bz_{K-1}\), not \(\bz_{n-1}\).
  • Algorithms 14.1 and 14.2: the comment "Iterative message-passing" does not belong; Algorithm 14.2's test uses \(q\) where \(q_k\) is meant.
  • p. 449: \(p(z,y)\propto\exp(-z^2y^2)\) is not a probability distribution (its integral diverges logarithmically; checked numerically); a proper example with Gaussian conditionals is \(\exp(-z^2y^2-z^2-y^2)\). Exercise 14.14: "variance \(\sigma_i\)" should be \(\sigma_i^2\).
  • (14.49): \(\int p(\bx\given\bw)p(\bx)\,\d\bx=1\) should be \(\int p(\bx\given\bw)\,\d\bx=1\).
  • Exercise 14.17: (14.52) is the log likelihood, not its gradient.
  • p. 455: "the value of \(\bz^{(T)}\)" should be \(\bx^{(T)}\); and (14.61) with exact gradients is the unadjusted Langevin algorithm, while "stochastic gradient Langevin dynamics" (Welling and Teh, 2011) refers to the mini-batch version (Filling the gap 14.8).
  • p. 454 (imprecision): the two terms of (14.57) balance when \(p_{\mathcal M}=p_{\mathcal D}\), but balance does not imply \(p_{\mathcal M}=p_{\mathcal D}\) (Result 14.14(4)).

Exercises

All 18 exercises of Chapter 14 (Bishop and Bishop, 2024, pp. 456–458), 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; where a companion-course exercise is the same, it is linked.

  1. Exercise 14.1 (★). Show that the Monte Carlo average (14.2) is an unbiased estimator of \(\E[f(\bz)]\).

    Solution

    By linearity of expectation and because each \(\bz^{(l)}\) has distribution \(p\), \(\E[\widehat f]\)\({}=\frac1L\sum_{l=1}^L\E[f(\bz^{(l)})]\)\({}=\frac1L\cdot L\,\E[f]\)\({}=\E[f]\). Independence is not needed for this part. (Result 14.1; companion Exercise 11.1.)

  2. Exercise 14.2 (★). Show that (14.2) has the variance (14.4).

    Solution

    For independent draws, \(\var[\widehat f]\)\({}=\frac1{L^2}\sum_l\var[f(\bz^{(l)})]\)\({}=\frac1L\var[f]\)\({}=\frac1L\E[(f-\E[f])^2]\), since the variance of a sum of independent terms is the sum of the variances. For correlated draws see Result 14.1(2). Checked by simulation: \(L\var[\widehat f]=1.376\) against 1.370.

  3. Exercise 14.3 (★). If \(z\sim\Unif(0,1)\) and \(y=h^{-1}(z)\) with \(h\) the indefinite integral (14.6) of \(p\), show that \(y\) has density \(p(y)\).

    Solution

    \(h\) is non-decreasing; assume it is continuous and strictly increasing where \(p>0\) (otherwise use the generalised inverse \(h^{-1}(z)=\inf\{y:h(y)\ge z\}\), for which \(h^{-1}(z)\le a\iff z\le h(a)\) still holds). Then \(P(y\le a)=P(z\le h(a))=h(a)\), so \(y\) has distribution function \(h\) and density \(h'=p\). Equivalently, by (14.5), \(p(y)=1\cdot|\d z/\d y|=h'(y)\). (Companion Exercise 11.2.)

  4. Exercise 14.4 (★★). Find a transformation of a uniform \(z\) on \((0,1)\) that gives the Cauchy distribution (14.8).

    Solution

    \(h(y)\)\({}=\int_{-\infty}^y\frac{\d t}{\pi(1+t^2)}\)\({}=\frac1\pi\big(\arctan y+\frac\pi2\big)\)\({}=\frac12+\frac1\pi\arctan y\). Solving \(z=h(y)\): \(y=\tan\{\pi(z-\frac12)\}\). Check: \(\d z/\d y=\frac1\pi\frac1{1+y^2}\). A simulation finds sample quartiles \(-0.98\), \(0.00\), \(0.99\) against \(-1,0,1\). (Companion Exercise 11.3.)

  5. Exercise 14.5 (★★). For \((z_1,z_2)\) uniform on the unit disc and \((y_1,y_2)\) given by (14.10)–(14.11), show that \((y_1,y_2)\) has the density (14.12).

    Solution

    See the proof of Result 14.2(2): in polar coordinates the map keeps the angle and sends radius \(r\) to \(R=\sqrt{-4\ln r}\); the Jacobian is \(|\partial(y_1,y_2)/\partial(z_1,z_2)|\)\({}=2/r^2\), so \(p(\by)\)\({}=\frac1\pi\frac{r^2}2\)\({}=\frac1{2\pi}e^{-R^2/2}\), the product of two standard normal densities. A second route: \(\theta\) is uniform and \(r^2\sim\Unif(0,1)\) (since \(P(r^2\le t)=\pi t/\pi\)), so \(R^2=-2\ln r^2\) is exponential with mean 2, i.e. \(\chi^2_2\), which with an independent uniform angle is exactly the polar form of \(\N(\bzero,\bI_2)\). A direct computation verifies the Jacobian identity by finite differences. (Companion Exercise 11.4.)

  6. Exercise 14.6 (★★). If \(\bz\sim\N(\bzero,\bI_D)\) and \(\Sig=\bL\bL^\T\) is the Cholesky factorisation, show that \(\by=\bmu+\bL\bz\) is \(\N(\bmu,\Sig)\).

    Solution

    The characteristic function of \(\by\) is \(\E[e^{i\mathbf t^\T\by}]\)\({}=e^{i\mathbf t^\T\bmu}\E[e^{i(\bL^\T\mathbf t)^\T\bz}]\)\({}=e^{i\mathbf t^\T\bmu-\frac12\mathbf t^\T\bL\bL^\T\mathbf t}\), that of \(\N(\bmu,\Sig)\). Directly: \(\E[\by]=\bmu\), \(\cov[\by]=\bL\E[\bz\bz^\T]\bL^\T=\Sig\). Only \(\bL\bL^\T=\Sig\) is used, not triangularity. (Companion Exercise 11.5.)

  7. Exercise 14.7 (★★). Show that rejection sampling accepts a proposal \(\bz\) with probability \(\pt(\bz)/kq(\bz)\), and, using the sum and product rules, that accepted values have density \(p(\bz)\).

    Solution

    Given \(\bz\), \(u_0\) is uniform on \([0,kq(\bz)]\), so \(P(\text{accept}\given\bz)\)\({}=P(u_0\le\pt(\bz))\)\({}=\pt(\bz)/kq(\bz)\le1\). Product rule: the joint density of drawing \(\bz\) and accepting it is \(q(\bz)\pt(\bz)/kq(\bz)=\pt(\bz)/k\). Sum rule: \(P(\text{accept})=\int\pt/k=Z_p/k\). Conditional density: \((\pt/k)/(Z_p/k)=\pt/Z_p=p\). The exercise's requirement that \(k\) be the smallest valid constant is not needed: any \(k\) with \(kq\ge\pt\) works (Result 14.3; companion Exercise 11.6).

  8. Exercise 14.8 (★). Show that \(y=b\tan z+c\) has the Cauchy form (14.16) when \(z\) is uniform.

    Solution

    The uniform variable must range over \((-\pi/2,\pi/2)\), not over \([0,1]\) as printed (see Filling the gap 14.3). Then \(z=\arctan\{(y-c)/b\}\), \(\d z/\d y=\frac{1/b}{1+(y-c)^2/b^2}\), and with \(p(z)=1/\pi\), (14.5) gives \(p(y)\)\({}=\frac1{\pi b}\frac1{1+(y-c)^2/b^2}\), which is (14.16) with \(k=1/(\pi b)\) for the normalised density; in the rejection sampler the comparison function is this times a constant. (Companion Exercise 11.7.)

  9. Exercise 14.9 (★★). Find the coefficients \(k_i\) of the piecewise exponential envelope (14.17) from continuity and normalisation.

    Solution

    Write the breakpoints as \(e_0<e_1<\dots<e_n\) (the book's \(z_{i-1},z_i\) in (14.17)) and the slopes \(\lambda_i=-g_i\), where \(g_i\) is the slope of the tangent used on piece \(i\). Continuity at \(e_i\): \(k_i\lambda_ie^{-\lambda_i(e_i-e_{i-1})}\)\({}=k_{i+1}\lambda_{i+1}\), so \(k_{i+1}\)\({}=k_i\frac{\lambda_i}{\lambda_{i+1}}e^{-\lambda_i\Delta_i}\), \(\Delta_i=e_i-e_{i-1}\): all \(k_i\) are fixed by \(k_1\). Normalisation: \(\int_{e_{i-1}}^{e_i}k_i\lambda_ie^{-\lambda_i(z-e_{i-1})}\d z\)\({}=k_i(1-e^{-\lambda_i\Delta_i})\), so \(\sum_ik_i(1-e^{-\lambda_i\Delta_i})=1\) fixes \(k_1\). In terms of the tangents, \(k_i\lambda_i\)\({}=e^{h_i+g_i(e_{i-1}-\zeta_i)}/\sum_jM_j\) (Result 14.4), and the breakpoints are the tangent intersections. Interpretation: \(k_i\) is the mass the \(i\)th exponential would have if it were extended to infinity. A direct computation confirms the piece masses against numerical integration. (Companion Exercise 11.8.)

  10. Exercise 14.10 (★★). Using the method of Section 14.1.2, devise an algorithm for sampling the piecewise exponential distribution (14.17).

    Solution

    (i) Choose piece \(i\) with probability \(P_i=k_i(1-e^{-\lambda_i\Delta_i})\) (a discrete distribution: compare a uniform \(u_1\) with the cumulative sums). (ii) Within the piece the density is \(\lambda_ie^{-\lambda_i(z-e_{i-1})}/(1-e^{-\lambda_i\Delta_i})\), with distribution function \(F(z)\)\({}=\frac{1-e^{-\lambda_i(z-e_{i-1})}}{1-e^{-\lambda_i\Delta_i}}\); setting \(F(z)=u_2\) gives \(z\)\({}=e_{i-1}-\lambda_i^{-1}\ln\{1-u_2(1-e^{-\lambda_i\Delta_i})\}\). For \(\lambda_i=0\) the piece is uniform; for an unbounded last piece (\(\Delta=\infty\), \(\lambda>0\)) the formula becomes \(z=e_{n-1}-\lambda^{-1}\ln(1-u_2)\), and similarly on the left with \(\lambda<0\). The two-stage draw has the right density because \(P(\text{piece }i)\times\) (density within the piece) \(=k_i\lambda_ie^{-\lambda_i(z-e_{i-1})}\). Implemented as ars_sample; a Kolmogorov–Smirnov test against the envelope passes. (Companion Exercise 11.9.)

  11. Exercise 14.11 (★). For the random walk (14.28)–(14.30), show that \(\E[(z^{(\tau)})^2]\)\({}=\E[(z^{(\tau-1)})^2]+\frac12\), hence \(\E[(z^{(\tau)})^2]=\tau/2\).

    Solution

    Write \(z^{(\tau)}=z^{(\tau-1)}+\xi_\tau\) with \(\xi_\tau\in\{0,+1,-1\}\) with probabilities \(\frac12,\frac14,\frac14\), independent of the past. Then \(\E[\xi_\tau]=0\), \(\E[\xi_\tau^2]=\frac12\), and \(\E[(z^{(\tau)})^2]\)\({}=\E[(z^{(\tau-1)})^2]+2\E[z^{(\tau-1)}]\E[\xi_\tau]+\E[\xi_\tau^2]\)\({}=\E[(z^{(\tau-1)})^2]+\frac12\). With \(z^{(0)}=0\), induction gives \(\tau/2\). Verified exactly by propagating the distribution for 60 steps, and by 20 000 simulated walks (Figure 14.S1(c)). (Companion Exercise 11.10.)

  12. Exercise 14.12 (★★). Show that Gibbs sampling satisfies detailed balance (14.34).

    Solution

    Each single-variable update does: it only reaches states with \(\bz'_{\setminus k}=\bz_{\setminus k}\), and for those \[ p(\bz)T(\bz,\bz')=p(\bz_{\setminus k})\,p(z_k\given\bz_{\setminus k})\,p(z'_k\given\bz_{\setminus k}), \] symmetric in \(\bz\leftrightarrow\bz'\) (Result 14.10). A precise statement matters here: the systematic sweep \(B_1B_2\cdots B_M\) is not reversible in general (a two-binary-variable example has \(\max|\mathbf DT-(\mathbf DT)^\T|=0.053\)), although it keeps \(p\) invariant; the random-scan sampler and the palindromic sweep \(B_1\cdots B_MB_M\cdots B_1\) are reversible (Result 14.8). (Companion Exercise 11.11.)

  13. Exercise 14.13 (★). For the distribution of Figure 14.14 (uniform on two regions), is standard Gibbs sampling ergodic, and does it sample correctly?

    Solution

    No. The two regions have disjoint projections on both axes. Starting in the lower region, the conditional of \(z_1\) given any reachable \(z_2\) is supported only on the lower region's chord, and likewise for \(z_2\); the upper region can never be reached, so the chain is reducible and its long-run distribution depends on the start (uniform on whichever region it started in). Averages then converge to conditional expectations given the starting region, not to expectations under \(p\). If the regions' projections overlap in at least one coordinate, a Gibbs move can jump between them and the sampler is ergodic. Both cases are simulated in Figure 14.14 (0% against 50% of the path in the upper region). Updating along other directions (for instance rotated coordinates, or a Metropolis move) would also restore ergodicity. (Companion Exercise 11.12.)

  14. Exercise 14.14 (★). Show that the over-relaxation update (14.46), applied to \(z_i\) with mean \(\mu_i\) and variance \(\sigma_i^2\), with \(\nu\) of mean 0 and variance 1, gives \(z_i'\) with mean \(\mu_i\) and variance \(\sigma_i^2\).

    Solution

    \(\E[z_i']\)\({}=\mu_i+\alpha_i(\E z_i-\mu_i)+\sigma_i\sqrt{1-\alpha_i^2}\,\E\nu\)\({}=\mu_i\). With \(\nu\) independent of \(z_i\), \(\var[z_i']\)\({}=\alpha_i^2\sigma_i^2+\sigma_i^2(1-\alpha_i^2)\)\({}=\sigma_i^2\). If \(z_i\) and \(\nu\) are Gaussian, \(z_i'\) is Gaussian too, so the conditional distribution itself (not just two moments) is preserved, and the update is reversible (Result 14.12). Checked with \(\alpha=-0.8\): mean 0.699, variance 1.686 (target 0.7, 1.69), correlation \(-0.800\). (The book writes "variance \(\sigma_i\)".) (Companion Exercise 11.14.)

  15. Exercise 14.15 (★). Show that the importance weights of likelihood-weighted sampling are (14.48).

    Solution

    The proposal samples each non-evidence node from its conditional given its (sampled or clamped) parents and sets evidence nodes to their observed values, so \(q(\bz)\)\({}=\prod_{i\notin e}p(\bz_i\given\mathrm{pa}(i))\). The target, up to the constant \(p(e)\), is the joint with the evidence plugged in, \(\prod_{i\notin e}p(\bz_i\given\mathrm{pa}(i))\prod_{i\in e}p(\bz_i\given\mathrm{pa}(i))\). Their ratio is \(r(\bz)\)\({}=\prod_{i\in e}p(\bz_i\given\mathrm{pa}(i))\), (14.48); the unknown \(p(e)\) is handled by self-normalisation (14.22)–(14.23). (Result 14.13; companion Filling the gap 11.7.)

  16. Exercise 14.16 (★). Show that (14.50) is normalised when \(Z(\bw)\) is given by (14.51).

    Solution

    \(\int p(\bx\given\bw)\,\d\bx\)\({}=\frac1{Z(\bw)}\int e^{-E(\bx,\bw)}\d\bx\)\({}=\frac{Z(\bw)}{Z(\bw)}\)\({}=1\), provided \(0<Z(\bw)<\infty\); see Filling the gap 14.6 for when that holds. A numerical experiment integrates the demonstration's model on its grid: \(|\int p-1|<10^{-12}\).

  17. Exercise 14.17 (★★). Using (14.50), show that the log likelihood of an energy-based model for i.i.d. data has the form (14.52).

    Solution

    By independence \(p(\mathcal D\given\bw)\)\({}=\prod_np(\bx_n\given\bw)\), so \(\ln p(\mathcal D\given\bw)\)\({}=\sum_n\ln p(\bx_n\given\bw)\)\({}=\sum_n\{-E(\bx_n,\bw)-\ln Z(\bw)\}\)\({}=-\sum_nE(\bx_n,\bw)-N\ln Z(\bw)\). (The book's wording says "the gradient of the log likelihood"; (14.52) is the log likelihood itself, and its gradient is the subject of Exercise 14.18.)

  18. Exercise 14.18 (★★). Using (14.54)–(14.56), show that the gradient of the expected log likelihood is (14.57).

    Solution

    From (14.51), \(\nabla_\bw\ln Z\)\({}=\frac1Z\int\nabla_\bw e^{-E}\d\bx\)\({}=-\int\nabla_\bw E\,\frac{e^{-E}}Z\,\d\bx\)\({}=-\E_{p_{\mathcal M}}[\nabla_\bw E]\), which is (14.55)–(14.56) (the interchange of derivative and integral needs the domination condition of Result 14.14(1)). Inserting into (14.54), whose last term does not depend on \(\bx\) and so passes through the expectation over \(p_{\mathcal D}\), gives (14.57). A direct computation confirms (14.55) and (14.57) against finite differences to \(4\times10^{-10}\).

Demonstrations

Three interactive pages, each linked above where its topic arises. They run in the browser and reproduce the Python code number for number (largest differences \(2\times10^{-16}\) for the Langevin chains, \(4\times10^{-15}\) for the trained weights, \(4\times10^{-11}\) for the gradient-estimator moments). The companion course's sampling basics demo already covers transformation, rejection, importance sampling and SIR, and its MCMC demo covers Metropolis and Gibbs, 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 14, pp. 429–458. doi:10.1007/978-3-031-45468-4. Book website: www.bishopbook.com.
  2. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Chapter 11.
  3. Adler, S. L. (1981). Over-relaxation method for the Monte Carlo evaluation of the partition function for multiquadratic actions. Physical Review D, 23(12), 2901–2904.
  4. Duane, S., Kennedy, A. D., Pendleton, B. J. and Roweth, D. (1987). Hybrid Monte Carlo. Physics Letters B, 195(2), 216–222.
  5. Fung, R. and Chang, K. C. (1990). Weighing and integrating evidence for stochastic simulation in Bayesian networks. In Uncertainty in Artificial Intelligence 5, 209–219.
  6. Geman, S. and Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6), 721–741.
  7. Gilks, W. R. and Wild, P. (1992). Adaptive rejection sampling for Gibbs sampling. Applied Statistics, 41(2), 337–348.
  8. Gilks, W. R., Best, N. G. and Tan, K. K. C. (1995). Adaptive rejection Metropolis sampling within Gibbs sampling. Applied Statistics, 44(4), 455–472.
  9. Gilks, W. R., Richardson, S. and Spiegelhalter, D. J. (eds) (1996). Markov Chain Monte Carlo in Practice. Chapman and Hall.
  10. Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1), 97–109.
  11. Henrion, M. (1988). Propagation of uncertainty by logic sampling in Bayes' networks. In Uncertainty in Artificial Intelligence 2, 149–164.
  12. Hinton, G. E. (2002). Training products of experts by minimizing contrastive divergence. Neural Computation, 14(8), 1771–1800.
  13. Hyvärinen, A. (2005). Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6, 695–709.
  14. Jensen, C. S., Kong, A. and Kjærulff, U. (1995). Blocking Gibbs sampling in very large probabilistic expert systems. International Journal of Human-Computer Studies, 42, 647–666.
  15. LeCun, Y., Chopra, S., Hadsell, R., Ranzato, M. and Huang, F. J. (2006). A tutorial on energy-based learning. In Predicting Structured Data, MIT Press.
  16. Metropolis, N. and Ulam, S. (1949). The Monte Carlo method. Journal of the American Statistical Association, 44(247), 335–341.
  17. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. and Teller, E. (1953). Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21(6), 1087–1092.
  18. Neal, R. M. (1993). Probabilistic Inference Using Markov Chain Monte Carlo Methods. Technical report CRG-TR-93-1, University of Toronto.
  19. Neal, R. M. (1999). Suppressing random walks in Markov chain Monte Carlo using ordered overrelaxation. In Learning in Graphical Models, MIT Press, 205–228.
  20. Parisi, G. (1981). Correlation functions and computer simulations. Nuclear Physics B, 180, 378–384.
  21. Robert, C. P. and Casella, G. (1999). Monte Carlo Statistical Methods. Springer.
  22. Roberts, G. O. and Tweedie, R. L. (1996). Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, 2(4), 341–363.
  23. Shachter, R. D. and Peot, M. A. (1990). Simulation approaches to general probabilistic inference on belief networks. In Uncertainty in Artificial Intelligence 5, 221–231.
  24. Song, Y. and Kingma, D. P. (2021). How to train your energy-based models. arXiv:2101.03288.
  25. Welling, M. and Teh, Y. W. (2011). Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th International Conference on Machine Learning, 681–688.
  26. Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8, 229–256.

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