Expectation step is to calculate the conditional probability expectation of the joint distribution.

University of Michigan - Ann Arbor

The EM algorithm is an iterative optimization strategy. Since each iteration in its calculation method is divided into two steps, one is the expectation step (E step) and the other is the maximization step (M step), so the algorithm is called EM Algorithm (Expectation-Maximization Algorithm). The EM algorithm was originally to solve the problem of parameter estimation in the case of missing data.

Expectation Maximization Algorithm

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Deep Learning

It's the most widely used latent variables' approximation algorithm. It's used in HMM models, GMM models, LDA models or such.  It could be used to solve the missing data problem as well. 

Application Scenarios of Using EM Algorithm

Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906.  Jensen's inequality generalizes the statement that the secant line of a convex function lies above the graph of the function, which is Jensen's inequality for two points: the secant line consists of weighted means of the convex function. For t belongs to [0,1], there exists:
$f(t x_1 + (1-t) x_2) <= t f(x_1) + (1-t) f(x_2)$

Jensen's Inequality

If we have completed data ${X,Z}$, it's easy for us to maximize the likelihood $p(X,Z|\theta)$.
Unfortuantely, with incomplete data($X$ only), we must maginalize over $Z$, so:
$ln(p(X|\theta)) = ln(\sum_Z p(X,Z|\theta))$
The $\theta$ inside the log makes it hard.

Why is it hard to approximate latent variables? 

If we consider $ln(x)$ as a function, the Jensen Inequality provides us a convenience to solve the problem of the sum part inside it. As a result, it's much easier for us to calculate the gradient and such thing. We just need to maximize the lower bound of the Jensen's Inequality. 

The relationship between EM algorithm with Jensen's Inequality

The coin example. Assume that we have two coins, coin A and coin B(for short, A and B). There exist two different possibility distributions of A and B about whether heads or tails come down. We have no idea about the frequency about selecting A and B as well. We only know about the the results of tossing coins. 
To approximate this process, we assume out the possibility distribution of A and B and initialize them randomly. Then we use them to approximate the probability of selecting A or B for the coin used in the game. It's the expectation step. Then we approximate new probability distributions of A and B according to the probability of selecting coins based on maximum likelihood principle. It's the maximization step. We repeatedly do these two steps until one of them converges. 

The Coin Example of EM Algorithm 

Assume that we want to approximate a primary school's sex distribution. Obviously, the height distributions of the boys and girls are different. However, we only have height records but no idea about whether each height is with a boy or a girl. To approximate the sex distribution, we randomly initialize the gaussian distributions of heights of boys and girls. We use these distributions to approximate whether each height is with a boy or a girl. Then we use the sex distributions to approximate the parameters of the gaussian distributions again. We repeatedly do those two steps until one of them converges.

The student example of EM algorithm

Fortunately, EM algorithm will definitely converges. It's a great mathematical practice to prove why it must converges. But the basic intuition between this conclusion is fairly easy. We just need to prove that our log approximation fuctions continuously keep increasing in the EM Algorithm process. 

Convergence of EM Algorithm

Unfortunately, there is no guarantee that em algorithm will converge at a global optimum. However, if we can prove that our optimization target, naming it $L(\theta, \theta^j)$, is a convex function, then the EM Algorithm will be guaranteed to converge at the global optimum.

Global Optimum of EM Algorithm

https://people.eecs.berkeley.edu/~pabbeel/cs287-fa13/slides/Likelihood_EM_HMM_Kalman.pdf

A Helpful Presentation Explaining mathematical Details and Applications of EM Algorithm Provided by Berkeley

If we consider both the Z parameters, representing the possibilities of selecting different possibility distributions, and the $\theta$ parameters, representing the possibility distributions, as similar parameters. We could consider it as some coordinate ascent algorithm with only optimizing part of the parameters in every step. As a result, their optimizing steps are always parallel with some of the coordinate axis.

A Coordinate Ascent View of Understanding EM Algorithm

E Step

M step is to optimize the loss function so that get better parameters.

Learn Before

Related