Expectation-Maximization

Fitting a model when some of what you need is missing. If you knew which cluster each point belonged to, fitting the clusters would be easy; if you knew the clusters, assigning the points would be easy. EM breaks the circle by alternating: guess the assignments, fit, re-guess, refit, and repeat until it stops moving.

k-Means Clustering is the recognisable special case, with hard assignments instead of soft ones. The general version keeps a probability of each assignment, which is better behaved and slower. What matters in practice is that it finds a local optimum and which one depends entirely on where it started, so restarts are not optional — a single run of EM has not found the answer, it has found an answer.

Each iteration constructs a lower bound on the log-likelihood that touches it at the current parameters, then maximises the bound. So the likelihood cannot decrease, which is the guarantee, and it says nothing about reaching the global optimum, which is the limitation. That construction is the same one behind the evidence lower bound in variational inference — EM is the case where the bound can be made tight at every step, and variational methods are what you do when it cannot.