Suppose we have a probabilistic model with observed variables , latent variables and a joint distribution parametrized by . Typically, the goal is to maximize the likelihood function given by:
We also suppose that direct optimization of is difficult, but that optimization of is significantly easier. To proceed, we introduce a distribution over the latent variables. We then have:
Since the left-hand side does not depend on and sums to one, we can take the expectation of both sides under :
So
Since , we have , i.e. is a lower bound on the log evidence. The bound is tight when , because the KL divergence is then zero.
The EM algorithm alternates directly setting in the appropriate manner and optimizing wrt while keeping fixed to obtain . After the E step, the lower bound takes the form: