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

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

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

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

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

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

E Step

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

M step 

The Expectation-Maximization (EM) algorithm can be interpreted as a coordinate ascent algorithm. By treating both the latent variables $$Z$$ and the model parameters $$\theta$$ as variables to be optimized, the EM algorithm alternates between optimizing one set of variables while holding the other fixed. Consequently, each optimization step (the E-step and the M-step) is parallel to one of the coordinate axes in the parameter space.

Coordinate Ascent Perspective of the Expectation-Maximization Algorithm

If we have complete data $$\left\{X, Z\right\}$$, it is easy to maximize the likelihood $$p(X, Z | \theta)$$. Unfortunately, with incomplete data ($$X$$ only), we must marginalize over the latent variables $$Z$$, so:

$$\ln(p(X|\theta)) = \ln\left(\sum_Z p(X,Z|\theta)\right)$$

The parameters $$\theta$$ inside the logarithm make it difficult to compute the maximum likelihood directly.

Learn Before

Related