Expectation Maximization Algorithm

Expectation Maximization Algorithm:

 The general form of the EM algorithm is discussed in this post so that every latent variable model can be trained.

1. Jensen's inequality and Kullback Leibler divergence.

Find the mathematical definition of the concave function in slide 1. This definition is related to the Jensen's inequality as shown in slide 2. Jensen's inequality relates the value of a convex function of an integral to the integral of the convex function, and generalizes even in probability theory. In probability theory Jensen's inequality states that the for a concave function f(x), f(EXP[t]) is bigger or equal to EXP[f(t)] (see slide 3).




The Kullback Leibler (KL) divergence is a measure between two probabilistic density function on how close they are. In fact, KL(q¦¦p) is the expected value on probability q(x) for the logarithm of their ratio. Basically we are averaging over the log of the ratio of q(x) and p(x). Yet, mathematically it is not a proper distance as KL(q¦¦p) is not equal to KL(p¦¦q). The other properties are KL(q¦¦q) = 0 and KL(q¦¦p) is always big or equal to zero. This is because the logarithm is concave and Jensens inequality holds (see slide 4 for the proof).

2. General Form of the Expectation Maximization Algorithm.

The problem statement is as follows: we would like to find the maximum likelihood estimate of the parameters with the latent variable t. The likelihood in this case is marginalized with t. Yet, instead of maximizing the marginalized likelihood we use Jensen's inequality to define the lower bound L(theta,q), and maximize L(theta,q) (called variational lower bound).

 The optimization takes E-step (finding q that maximizes the variational lower bound) and M-step (finding theta that maximizes the variational lower bound).



3. E-step and M-step.

Again, the E-step is fixing theta and finding q that minimizes the gap between the log of the marginal likelihood and the variational lower bound which is equivalent to maximizing the variational lower bound with respect to q. Mathematically it can be derived that this gap is the same as the KL divergence between the probability density function of the latent variable t and the posterior probability density of the latent variable t given the data and the parameter theta. Since KL divergence is zero if the two distributions are the same, the gap is minimized or equals zero when q(t) is equivalent to the posterior of t given the data and the parameter theta.

 The M-step involves fixing the variational distribution q and finding theta that minimizes the gap between the log of the marginal likelihood and the variational lower bound which is equivalent to maximizing the variational lower bound. Mathematically the variational lower bound is the expectation of joing probability distribution of the data X and the latent variable T given the parameters with some constant being added. The expectation is over the variational distribution q here. Usually this function is concave with respect to theta and therefore, the optimization becomes easy.


Note that the convergence is guaranteed for the EM algorithm by definition of E-step and M-step. The objective function is always decreasing although it may converge to the local minima or saddle point.

The EM algorithm is the method for training the latent variable models, with complicated constrains (stochastic gradient descent may not work well as discussed before) and it handles the missing data. The EM invovles the sequences of simple tasks (E-step and M-step) instead of one single hard task. (direct evaluation of the likelihood). Due to nature of this NP hard problem the only problem with the EM algorithm is its convergence to local minima.

4. Youtube tutorials on EM. 

1. Expectation Maximization Algorithm:
https://www.youtube.com/watch?v=AnbiNaVp3eQ&list=PLD0F06AA0D2E8FFBA&index=116 

2. Why EM makes sense? 
https://www.youtube.com/watch?v=6JZ-PKpx5Kc&list=PLD0F06AA0D2E8FFBA&index=117 
https://www.youtube.com/watch?v=X9yF2djExhY&index=118&list=PLD0F06AA0D2E8FFBA 

 There are also other videos from the mathematical monk on EM algorithms.

 

Comments

Post a Comment

Popular posts from this blog

Notes on "Focal Loss for Dense Object Detection" (RetinaNet)

Image
Focal Loss for Dense Object Detection by Lin et al (2017) The central idea of this paper is a proposal for a new loss function to train one-stage detectors which works effectively for class imbalance problems (typically found in one-stage detectors such as SSD). The authors also introduce RetinaNet based on the proposed loss function which outperforms the state-of-the-art detection algorithms including the two-stage detectors. Focal loss function: pt is defined as p if y = 1 and p-1 otherwise. In this way, CE(pt) is the cross entropy where p is the probability score. As shown below, the cross entropy is denoted blue (gamma = 0). By adding the factor (see the focal loss FL(pt)) the loss function computes smaller value for the well classified examples and puts more focus on hard and misclassified eamples. In this way the easy background examples are dealt with, which enables the training of highly accurate desne object detection algorithms. Just like alpha-cross entropy is the comm
Read more

Introduction to Bayesian methods

Image
Introduction to Bayesian methods: 1. Bayesian way of thinking: A man is running. Why? Some of the possible explanations are (1) this man is in hurry, (2) this man is running, (3) this man just spotted a dragon, and (4) this man always runs. There are three principles in Bayesian way of thinking which we can use to conclude which of these explanations are the most reasonable. These principles are: 1. Use the prior knowledge on the problem - there is no dragon. 2. Choose the answer that explains the data the most - the man is not wearing the runner. 3. Avoid making extra assumptions - crude to think that any man always run. The answer number "1. this man is in hurry" should be chosen following this principles. 2. Review of probability: Checklists are: 1. What is the probability? 2. What are random variables? 3. What is the probability mass function (PMF)? 4. What is the probability density function (PDF)? 5. What does it mean for the random variables X and Y
Read more

Conjugate Priors

Conjugate Priors. 1. Analytical inference: See the Bayes formulae. The problem is that the evidence is difficult to estimate for the analytical inference. One way to get away is the maximum posterior (MAP) and is very easy to compute, but it comes with many problems. 1. Lack of the in-variance to re-parameterization. 2. The MAP cannot be used as the prior. 3. The MAP is an untypical point (the mode). 4. The credible regions may not be computed. 2. Conjugate distributions. Another approach to avoid computing the evidence is called the conjugate distributions. As the likelihood and the evidence is fixed by our model, we can only vary the prior so that it is easier to compute the posterior. I f the posterior distribution p(θ|x) are in the same family as the prior distribution p(θ), the prior and posterior are then called conjugate distributions, and the prior is called a conjugate prior for the likelihood. For example, the Gaussian family is conjugate to itself (or self-
Read more