Overview
Expectation-Maximization estimates hidden variables under the current parameters, then maximizes parameters using those expectations.
CoreSource checked
Expectation-Maximization
Fits latent-variable models by alternating expected assignments and parameter updates.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Advanced
- Family
- Latent Variable Optimization
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
latent variablee-stepm-steplikelihood improvement
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n k)
Average
O(iterations * n k)
Worst
O(iterations * n k)
Space
O(n k)
When to Use
- Use when tuning model parameters needs latent variable.
- Use when the input matches the assumptions behind latent Variable Optimization.
When Not to Use
- Avoid when the objective is cheap and convex enough for a simpler exact solver.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Fits latent-variable models by alternating expected assignments and parameter updates
- Uses latent variable and e-step to guide the work.
- Produces best candidate.
Use Cases
- Tuning model parameters
- Searching design spaces
- Fitting models to noisy data
Inputs
- Objective function
- Initial candidate or population
- Stopping rule
Outputs
- Best candidate
- Objective value
- Search history
Key Formulas (1)
EM objective
Q(θ | θold) = Ez[log p(x, z | θ)]
Q(theta | theta_old) = E_z[log p(x, z | theta)]Optimizes expected complete-data log likelihood.
Pseudocode
- 1.Prepare the inputs and state needed for Expectation-Maximization.
- 2.Apply the latent variable step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return best candidate.
Canonical Example
- Input
- Expectation-Maximization input with a small representative case
- Output
- Best candidate
- Explanation
- Expectation-Maximization applies latent variable to produce best candidate.
Implementation Notes
- Track both best-so-far and current candidate state.
- Keep the latent variable step separate enough to test independently.
Common Pitfalls
- Stopping too early can make a poor local result look like convergence.
- Forgetting to check edge cases can make Expectation-Maximization look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryPlot candidate points, objective values, and improvement steps across iterations.
Step 1 of 4: Prepare the inputs and state needed for Expectation-Maximization.
optimization-mechanismNotes
Expectation-Maximization should be used with the assumptions and tradeoffs of latent Variable Optimization in mind.
Sources (1)
What each reference supports for this entry.
Dempster, Laird, and Rubin 1977
PaperOriginal expectation-maximization paper for maximum-likelihood estimation with incomplete data.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsed byGaussian Mixture Model
Gaussian mixture models often use EM to estimate latent assignments and parameters.
Conceptual neighborHidden Markov Model
Hidden Markov Models commonly use EM-style training through Baum-Welch.
Related Algorithms
Tags
OptimizationProbabilistic ModelModel FittingIterative