expectation–maximization algorithm
In plain wordsA method for fitting a model when some information is hidden: guess the hidden parts using the current model, refit the model as if those guesses were right, and repeat until nothing changes.
An iterative scheme for estimating model parameters from incomplete data, where the missing part may be hidden (latent) variables, such as each point's mixture component, or values that were never recorded. Instead of maximizing the observed-data likelihood directly, it alternates two easier steps: the E-step uses the current parameters to compute the posteriorposterior, n.: What you believe after weighing new evidence against what you believed before. It is the updated belief that Bayes' theorem produces. distribution of the hidden variables and, from it, the expected log-likelihood of the completed data; the M-step maximizes this expectation over the parameters, yielding a maximum-likelihoodmaximum likelihood estimation, n.: Tuning a model's settings until the real data it learns from looks as likely, and so as unsurprising, to the model as possible. Most AI training, including the pretraining of chatbots, is a version of this. fit (or a maximum a posteriorimaximum a posteriori estimation, n.: Picking the single most believable setting of a model after combining the evidence with what was assumed beforehand. In practice it often amounts to ordinary training plus a penalty that keeps settings modest. fit if a log-prior is added). No iteration can decrease the observed-data likelihood, and under mild regularity conditions EM converges to a stationary point, usually a local maximum, which makes initialization important; progress is typically fast at first and slow near convergence. Classic instances are fitting Gaussian mixture modelsGaussian mixture model, n.: A model that explains data as coming from several overlapping bell-shaped clouds, working out where each cloud sits, how spread out it is, and how likely each point is to belong to it., the Baum–Welch algorithm for hidden Markov modelshidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds. and estimation with missing values. EM can be read as coordinate ascent on the evidence lower boundevidence lower bound, n.: A quantity that is always less than or equal to how well a model explains its data, but much easier to calculate; pushing it upward is how models such as VAEs learn., which connects it to variational inference.
EM stalled in a poor local optimum, so we restarted it from ten k-means initializations and kept the best likelihood.
Origin
Special cases were proposed many times, including by H. O. Hartley (1958) and in Rolf Sundberg's work on exponential families (1971–1976). Arthur Dempster, Nan Laird and Donald Rubin unified them and named the method in a 1977 paper in the Journal of the Royal Statistical Society. Their convergence argument contained a flaw, which C. F. Jeff Wu corrected in 1983.
Usage note
A recipe rather than a single algorithm: each model needs its own E- and M-steps. When the M-step cannot be solved exactly, generalized EM merely improves the objective; when the E-step is intractable, variational or Monte Carlo approximations replace it.
Related
- Gaussian mixture modelGaussian mixture model, n.: A model that explains data as coming from several overlapping bell-shaped clouds, working out where each cloud sits, how spread out it is, and how likely each point is to belong to it.
- maximum likelihood estimationmaximum likelihood estimation, n.: Tuning a model's settings until the real data it learns from looks as likely, and so as unsurprising, to the model as possible. Most AI training, including the pretraining of chatbots, is a version of this.
- hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds.
- evidence lower boundevidence lower bound, n.: A quantity that is always less than or equal to how well a model explains its data, but much easier to calculate; pushing it upward is how models such as VAEs learn.
- imputationimputation, n.: Filling in missing values in a dataset with sensible estimates, such as the typical value or a prediction from the other columns, so the data can be analyzed or used for training.
- k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat.
Sources
- Dempster, A. P., Laird, N. M. & Rubin, D. B. (1977). Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society, Series B 39(1).
- Wu, C. F. J. (1983). On the Convergence Properties of the EM Algorithm. Annals of Statistics 11(1).
Mentioned in
Gaussian mixture modelGaussian mixture model, n.: A model that explains data as coming from several overlapping bell-shaped clouds, working out where each cloud sits, how spread out it is, and how likely each point is to belong to it., hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds., imputationimputation, n.: Filling in missing values in a dataset with sensible estimates, such as the typical value or a prediction from the other columns, so the data can be analyzed or used for training., k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat., 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., Q-functionQ-function, n.: A score for each possible move in each situation, estimating how well things will turn out, in rewards, if the AI agent makes that move now and sticks to its usual strategy afterward., Jensen's inequalityJensen's inequality, n.: A rule saying that for a bowl-shaped curve, the average of the outputs is at least the output of the average. It is the hidden step behind many proofs in machine learning.