Markov chain Monte Carlo
In plain wordsA family of methods for drawing random examples from a complicated probability distribution by taking a long, carefully designed random walk that eventually visits each region in proportion to its probability.
A family of algorithms that draw samples from a probability distributionprobability distribution, n.: A complete description of how likely each possible outcome is — for a fair die, one-sixth for each face. A language model produces one of these over its whole vocabulary at every step. known only up to a normalizing constant by running a random walk — a Markov chainMarkov chain, n.: A chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example. — designed to visit each region in proportion to its probability; after a burn-in period, the walk's successive states serve as correlated samples for Monte CarloMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating. estimates. The Metropolis–Hastings algorithm proposes a move and accepts it with a probability computed from ratios of target and proposal densities, in which the unknown constant cancels; Gibbs sampling updates one variable at a time from its conditional distribution; Langevin methods and Hamiltonian Monte Carlo use the gradientgradient, n.: A list of slopes showing which way, and how steeply, a quantity rises as each of its inputs changes. Training nudges an AI's settings in the opposite direction, downhill. of the log-density to propose better-directed moves, in HMC's case long trajectories that are still usually accepted. MCMC made Bayesian inferenceBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability. practical for complex models — sampling posteriorsposterior, n.: What you believe after weighing new evidence against what you believed before. It is the updated belief that Bayes' theorem produces. in tools such as BUGS and Stan — and was used to train Boltzmann machinesBoltzmann machine, n.: A network of randomly flipping on–off units, including hidden ones, that learns the statistical patterns in its training data and can then produce new examples like them. and other energy-based modelsenergy-based model, n.: A model that scores how well things fit together by giving each possibility an 'energy': low for plausible combinations, high for implausible ones, like a ball settling into the lowest valleys.; Langevin dynamics also underlies sampling in score-based generative modelsscore-based generative model, n.: A generator that learns, for any noisy example, which direction would make it look more like real data — then starts from pure noise and follows those directions step by step.. Diagnosing convergence and mixing remains hard.
The MCMC chains for the hierarchical model mixed poorly until we reparameterized the variance terms.
Origin
Nicholas Metropolis, Arianna and Marshall Rosenbluth, and Augusta and Edward Teller introduced the Metropolis algorithm in 1953 for statistical physics; W. Keith Hastings generalized it for statisticians in 1970. Stuart and Donald Geman's Gibbs sampler (1984) and Alan Gelfand and Adrian Smith's 1990 paper brought MCMC into mainstream Bayesian statistics, where the name took off around 1990; Simon Duane and colleagues introduced Hamiltonian ('hybrid') Monte Carlo in 1987.
Related
- Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating.
- Markov chainMarkov chain, n.: A chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example.
- Bayesian inferenceBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability.
- posteriorposterior, n.: What you believe after weighing new evidence against what you believed before. It is the updated belief that Bayes' theorem produces.
- energy-based modelenergy-based model, n.: A model that scores how well things fit together by giving each possibility an 'energy': low for plausible combinations, high for implausible ones, like a ball settling into the lowest valleys.
- score-based generative modelscore-based generative model, n.: A generator that learns, for any noisy example, which direction would make it look more like real data — then starts from pure noise and follows those directions step by step.
- variational inferencevariational inference, n.: A way of approximating a hard-to-compute probability distribution by picking the closest match from a simpler family of distributions, turning a hard problem of adding up every possibility into an optimization problem.
Sources
- Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21(6).
- Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1).
Mentioned in
Bayesian inferenceBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability., inferenceinference, n.: Drawing a conclusion from evidence. In today's AI it most often means running an already-trained model to get an answer, as opposed to training it., inference engineinference engine, n.: The part of an AI system that does the working-out: in older AI, the program that applies rules to facts; in today's AI, the software that runs a trained model to produce answers., latent Dirichlet allocationlatent Dirichlet allocation, n.: A popular topic-finding method that assumes every document is a blend of a few themes and every theme favors certain words, then works backward from the words to find both., Markov chainMarkov chain, n.: A chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example., Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating., posteriorposterior, n.: What you believe after weighing new evidence against what you believed before. It is the updated belief that Bayes' theorem produces., probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together., samplingsampling, n.: Picking some items at random from a larger set or from a range of possibilities — surveying 1,000 voters, say, or letting an AI choose its next word by a weighted lottery., simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops., Bayesian neural networkBayesian neural network, n.: A neural network that keeps a whole range of plausible settings for its internal numbers instead of one best guess, so that it can say how unsure it is about each prediction., energy-based modelenergy-based model, n.: A model that scores how well things fit together by giving each possibility an 'energy': low for plausible combinations, high for implausible ones, like a ball settling into the lowest valleys., local learning coefficientlocal learning coefficient, n.: A number measuring how complex a trained neural network effectively is around its current settings — usually far less than its raw parameter count suggests — used to spot changes as the network learns., Markov logic networkMarkov logic network, n.: A way of combining logical rules with probabilities, so that a rule like 'friends usually like the same music' can sometimes be broken, with each rule given a weight saying how strongly it holds., Markov random fieldMarkov random field, n.: A model of many linked uncertain quantities, such as neighboring pixels in a photo, in which each one depends directly only on its neighbors, with no notion of which one causes which., probabilistic programmingprobabilistic programming, n.: Writing a statistical model as an ordinary-looking program that includes random choices, and letting the system work out automatically which hidden values best explain the observed data., score-based generative modelscore-based generative model, n.: A generator that learns, for any noisy example, which direction would make it look more like real data — then starts from pure noise and follows those directions step by step., variational inferencevariational inference, n.: A way of approximating a hard-to-compute probability distribution by picking the closest match from a simpler family of distributions, turning a hard problem of adding up every possibility into an optimization problem.