MAP and EM for MAP Estimation

The EM algorithm that we talked about in class was for solving a maximum likelihood estimation problem in which we wish to maximize

where the $z^{(i)}$'s are latent random variables. Suppose we are working in a Bayesian framework, and wanted to find the MAP estimation of the parameters $\theta$ by maximizing

Generalize the EM algorithm to work for MAP estimation. You may assume that $log~p(x,z|\theta)$ and $log~p(\theta)$ are both concave in $\theta$.

MAP Recap

Given training datasete

In Miximum Likelihood Estimation, we try to approximate the parameter by

the intuition is, what $\theta$ is more likely to produce the training dataset.

But in Maximum A Posteriori Estimation, we assume parameter $\theta$ follows an prior distribution, and try to approximate the parameter by

The intuition is, given the training dataset, what $\theta$ is the most likely one.

And in MAP estimation, we transform $P(\theta|S)$ according to Bayes Rule.

Actually, the denominator is just $P(S)$, it's irrelevant to $\theta$, so we just

Note that what we are maximizing is almost the same as we maximize in Maximum Likelihood Estimation, only introducing an prior distribution on $\theta$.

EM for MAP Estimation

When we introduce latent variables into MAP Estimation, we approximate the paramter $\theta$ by maximizing

where $z^{(i)}$'s are the latent variables. And the derivation for EM Algorithm is very strarightforward, when you take the log likelihood, $P(\theta)$ is just a additional term add to the main equation.

Since $log$ is concave, according to Jensen's Inequality,

To hold equality at Jensen's Inequality step for current $\theta$, we need this to be a constant

Hence

The left part is $1$ since $Q_i(z^{(i)})$ is a distribution over $z^{(i)}$. And the right is

And so

The E-Step is just the general case

And M-Step is to find the maximum of the lower bound