Monte Carlo methods
Estimating things about a probability distribution by drawing samples from it instead of integrating over it. In information-theory-inference-learning-algorithms this is not a numerical sideline — it is the answer to the problem bayesian-inference creates, because the posterior ensemble that inference produces is almost never something you can write down.
The two problems being solved
MacKay states them separately, and the second is the harder one:
- Generate samples from a distribution
P(x)you can only evaluate up to a constant. - Estimate expectations of functions under it.
The obstacle is the normalizing constant. Evaluating Z by visiting every point in the state space
costs exponentially in the number of dimensions, which is why the whole family exists.
The methods
Chapters 29–32 build them in order of ambition: importance sampling and rejection sampling, then the Metropolis method, Gibbs sampling and slice sampling, then more efficient schemes, Ising-model applications, and exact sampling. The recurring theme is that a sampler’s cost is governed by how badly its random walk explores the space, not by how expensive one evaluation is.
The homonym, from the ML side
../optimization-algorithms-wiki owns simulated-annealing and the rest of the
metaheuristic family, and the vocabulary overlaps hard — both traditions do randomized search over
a high-dimensional space with a temperature-like parameter. The distinction is what the search is
for: a metaheuristic optimizer wants the single best point in an objective landscape, a sampler
wants a fair draw from a distribution and is actively harmed by converging on one point. The
machinery is shared, since annealing came into both traditions from statistical physics, which is
why the two spokes cross-link rather than merge.
Related
bayesian-inference · information-theory-inference-learning-algorithms · information-theory · machine-learning · synthesis