View source for Expectation–maximization algorithm

== Introduction ==
The Expectation–Maximization (EM) algorithm is a method used in [[statistical analysis]] and [[machine learning]] to find likely parameter estimates when you have unobserved latent variables or incomplete data. It is an iterative method that starts with a guess about the parameters and refines the estimates iteratively to maximize the likelihood of the data given the parameters.

== History ==
The EM algorithm was introduced in a seminal paper by Arthur Dempster, Nan Laird, and Donald Rubin in 1977. However, the idea had been proposed earlier in different contexts by various researchers. The algorithm has since been widely used in many fields, including [[statistics]], [[computer science]], [[data mining]], and [[bioinformatics]].

== Mathematical Background ==
The EM algorithm is based on the concept of [[maximum likelihood estimation]] (MLE). MLE is a method of estimating the parameters of a statistical model given observations. The goal is to find the parameter values that maximize the likelihood function, which measures the plausibility of the parameter values given the observations.

The EM algorithm extends MLE to situations where the model depends on unobserved latent variables. It does this by introducing an auxiliary function, called the Q-function, which is the expected value of the log-likelihood function with respect to the conditional distribution of the latent variables given the observed data and the current parameter estimates.

== Algorithm ==
The EM algorithm consists of two steps: the Expectation step (E-step) and the Maximization step (M-step). 

In the E-step, the algorithm computes the expected value of the log-likelihood function, given the observed data and the current estimate of the parameters. This is done by taking the expectation over the distribution of the latent variables conditional on the observed data and the current parameter estimates.

In the M-step, the algorithm maximizes the expected log-likelihood found in the E-step with respect to the parameters to update the parameter estimates. This is typically done using standard optimization techniques.

The algorithm alternates between these two steps until convergence, i.e., until the parameter estimates do not change significantly between iterations.

== Applications ==
The EM algorithm has been widely used in a variety of applications. In statistics and machine learning, it is often used for parameter estimation in models with latent variables, such as [[Gaussian mixture models]], [[hidden Markov models]], and [[latent Dirichlet allocation]]. In bioinformatics, it is used for sequence alignment and motif finding. In computer vision, it is used for image segmentation and object recognition.

== Limitations and Extensions ==
While the EM algorithm has been successful in many applications, it has several limitations. One limitation is that it only finds a local maximum of the likelihood function, not necessarily the global maximum. This means that the final estimates can depend on the initial guess for the parameters.

Another limitation is that the E-step can be computationally expensive if the number of latent variables is large. This has led to the development of various extensions and approximations to the EM algorithm, such as the Variational EM algorithm and the Stochastic EM algorithm.

== See Also ==
* [[Maximum likelihood estimation]]
* [[Gaussian mixture model]]
* [[Hidden Markov model]]
* [[Latent Dirichlet allocation]]
* [[Variational EM algorithm]]
* [[Stochastic EM algorithm]]

[[Image:Detail-58924.jpg|thumb|center|A computer screen showing the iterative process of the Expectation-Maximization algorithm.|class=only_on_mobile]]
[[Image:Detail-58925.jpg|thumb|center|A computer screen showing the iterative process of the Expectation-Maximization algorithm.|class=only_on_desktop]]

[[Category:Statistical algorithms]]
[[Category:Machine learning algorithms]]
[[Category:Bioinformatics algorithms]]