§17.1–17.2Sampling and Monte Carlo Methods · Importance Sampling

§17.1 Two kinds of randomized algorithm

Randomized algorithms split into two families, and the difference decides which one machine learning can use:

Because most machine-learning problems admit no precise answer — ruling out exact methods and Las Vegas las vegas algorithm A randomized algorithm that always returns the exact answer (or reports failure) but consumes a random amount of time/memory. defined in ch. 17 — open in glossary algorithms — we lean on Monte Carlo monte carlo algorithm A randomized algorithm returning an answer with random error that shrinks as more compute is spent; gives an approximate answer for any fixed budget (contrast Las Vegas). defined in ch. 17 — open in glossary approximations. Why sample at all? Three recurring reasons: to speed up a tractable-but-costly sum (minibatches subsample the full training cost); to approximate an intractable sum or integral (the gradient of an undirected model’s log partition function, chapter 18); and sometimes because sampling is the goal — we want a model that generates data like the training set.

§17.1.2 The basics: sums as expectations

The trick of Monte Carlo sampling monte carlo sampling Approximating a sum/integral s=E_p[f(x)] by the empirical average ŝ_n=(1/n)Σf(x⁽ⁱ⁾) of n samples from p; unbiased, with error ∝ 1/√n. defined in ch. 17 — open in glossary is to view an intractable sum or integral as an expectation, then approximate it by an average of samples:

This estimate is trustworthy for three reasons. It is unbiased, $\mathbb{E}[\hat{s}_n] = s$ (eq 17.4). By the law of large numbers it converges almost surely, $\lim_{n\to\infty}\hat{s}_n = s$ (eq 17.5), provided $\mathrm{Var}[f]$ is finite. And its own variance falls off as

The central limit theorem adds that $\hat{s}_n$ is approximately Gaussian around $s$, so we can put confidence intervals on it. See all of this at once — estimate $\pi$ by throwing darts, and watch the error track the $1/\sqrt{n}$ line:

§17.2 Importance sampling

Everything above assumed we can sample from $p$. When we cannot — or when sampling from $p$ is wasteful — importance sampling importance sampling Estimating an expectation (here the softmax negative-phase gradient) by sampling from a cheap proposal distribution q instead of the model, correcting the bias with importance weights — avoids computing scores for the whole vocabulary. Biased importance sampling normalizes the weights. defined in ch. 12 — open in glossary exploits a freedom in the setup. The product $p(\boldsymbol{x})f(\boldsymbol{x})$ can be re-split around any distribution $q$:

The remarkable part: the estimator’s mean does not depend on $q$, $\mathbb{E}_q[\hat{s}_q] = s$ (eq 17.11) — every $q$ is correct on average. But its variance is exquisitely sensitive to $q$ (eq 17.12), and there is a single best choice — optimal importance sampling optimal importance sampling The minimum-variance choice q*∝p(x)|f(x)| (eq 17.13); gives zero variance when f has constant sign, but computing it solves the original problem. defined in ch. 17 — open in glossary :

The payoff and the peril are both huge. A good $q$ concentrates samples where they matter; a bad $q$ — especially in high dimensions, where a simple $q$ matches $p|f|$ poorly — gives an estimator that usually underestimates $s$ and rarely, wildly overestimates it. Estimate a rare-event probability and feel the difference:

When $p$ and $q$ are only known unnormalized (the usual case for energy-based models), use biased importance sampling biased importance sampling An importance-sampling estimator using unnormalized p̃,q̃ (needs no normalizers); biased but asymptotically unbiased as n→∞. defined in ch. 17 — open in glossary (eqs 17.14–17.16): divide the weighted sum of $f$ by the sum of the weights, using $\tilde{p}, \tilde{q}$ and needing no normalizers. It is biased — but asymptotically unbiased, since the denominator converges to $1$ as $n \to \infty$.

When even a good $q$ is out of reach, we give up on independent samples and build a sequence of samples that converges to $p$ — the Markov chain Monte Carlo approach.