0
$\begingroup$

When using the Expectation Maximization(EM) for estimating the parameters, every time I came across a different problem I see a totally different representation of the likelihood/Expectation function and a different formula in the E-step & M-step i.e. one guy adds extra terms, another remove some terms, yet another bring new ways (tricks) to solve it.

  1. Is there a standard way which we can use it as a rule, not like saying E-step is the Expectation of the Likelihood and M-step is maximizing it?
  2. in EM algorithm there is an expectation of the log-likelihood with respect to the posterior/conditional distribution of the hidden variables i.e. $E_{p(y|x,\theta)}(log(p(x,y|\theta))$. And we know that $p(x,y|\theta)=p(y|x,\theta)\times p(x|\theta)$ i.e. it should be sufficient to find a formula of $p(y|x,\theta)$ for calculating $p(x,y|\theta)$ because $p(x|\theta)$ is the frequency of x in the dataset which should be known. However, I have come through several EM applications/examples and I did not find anyone using this rule, rather all of them use a different and direct (i.e. without depending on $p(y|x,\theta)$ ) formula for $p(x,y|\theta)$. So what is the reason behind that? Isn't it easier to use this rule for finding $p(x,y|\theta)$ instead of trying to find two unique formulas for $p(y|x,\theta)$ and $p(x,y|\theta)$ for caluclating the expectation.
$\endgroup$
  • $\begingroup$ $p(x|\theta)$ is not the frequency of $x$ in the data set, it's the probability density of $x$ given $\theta$. If $x$ were drawn from a continuous distribution, each value of $x$ in a data set of size $n$ would appear once, i.e., with frequency $1/n$, so $p(x|\theta$) would disappear from the set of formulae altogether. $\endgroup$ – jbowman Mar 11 at 3:05
  • $\begingroup$ If you know $p(x,y|\theta)$, you know $p(y|x,\theta)$ up to the constant of integration. It is often quite easy to see what that is just by looking at $p(x,y|\theta)$. $\endgroup$ – jbowman Mar 11 at 3:10
  • $\begingroup$ @jbowman I did not get your point buddy. Could you clarify more what you mean. $\endgroup$ – Mosab Shaheen Mar 11 at 3:22
  • $\begingroup$ With reference to your last sentence, it's the case that it's often easier to work with $p(x,y|\theta)$. $\endgroup$ – jbowman Mar 11 at 14:19
  • $\begingroup$ @jbowman I think you did not get the point. I am saying that in all the applications of EM algorithm I came across, I saw people use different formulas for p(x,y|θ) and p(y|x,θ). You are saying p(x,y|θ) is easier to find. Fine, but then my question is why do not they use p(y|x,θ) = p(x,y|θ)/p(x|θ) ?? why do they always use two unique formulas for both p(y|x,θ) and p(x,y|θ) and those formulas do not directly use p(x|θ) (if they use p(x|θ) then one formula will be enough and p(x|θ) is very easy to find by counting). $\endgroup$ – Mosab Shaheen Mar 11 at 21:41
3
$\begingroup$

The EM method is a generalized algorithm that solves maximum-likelihood problems with latent variables. Suppose that you have a model with some random variables $y$ that you have observed (measurements) and some random variables $z$ that are unknown. We write this model as a joint probability distribution $$ p_\theta(y,z)$$ where $\theta$ are the parameters that you want to estimate.

The problem now is that we cannot do maximum likelihood on this model because we do not known what to put in for the $z$ variables.

One way to solve this problem is marginalization: we remove the unknown random variables from the model by integrating them out with $$ p_\theta(y) = \int p_\theta(y,z) \mathrm{d} z.$$

In most interesting cases this integral cannot be solved in closed form. This is where the EM method comes to help. It is an iterative procedure that starts from any initial estimate $\theta^{(0)}$ and iterates two steps.

In the first (the E-step) we create a lower bound on the likelihood function $\log p_\theta(y)$ by computing $$ Q(\theta,\theta^{(k)}) = \mathbf{E}\{\log p_\theta(y,z)\}$$ where the expectation is taken with respect to the best estimate of the conditional distribution of the latent variables $p_{\theta^{(k)}}(z|y)$.

In the second step (the M-step) we maximize the lower bound to update the parameter estimate: $$\theta^{(k+1)} = \arg \max_\theta Q(\theta,\theta^{(k)}).$$

Under some regularity conditions, $\theta^{(k)} \to \theta_0$ where $\theta_0$ is a local maximum of the marginal likelihood $p_\theta(y)$.

There are a lot of tricks you can use to solve the E-step and the M-step. Most notably

  • if $p_\theta(y,z) = q_\theta(y,z)g(y,z)$ where $g(y,z)$ is independent of $\theta$, you can disregard the whole $g(y,z)$ in computing $Q(\theta,\theta^{(k)})$ because that part will not impact the successive maximization step. This is very useful in hierarchical models: suppose that the joint model is $p_\theta(y,z) = p(y|z_1)p(z_2|z_3)p_\theta(z_3|z_4)p(z_4)$, in the E-step we just need to consider $$ Q(\theta,\theta^{(k)}) = \mathbf{E}\{\log p_\theta(z_3|z_4)\}$$ because all other factors are independent of $\theta$!
  • You can freely add as many variables as you want to the model: these will anyway be integrated out by the EM method! This is especially useful if you can separate parameters given a variable. Suppose that your model depends on two parameters $p_{\theta_1,\theta_2}(y)$. If there is a random variable $z$ such that $p_{\theta_1,\theta_2}(y,z) = p_{\theta_1}(y|z)p_{\theta_2}(z)$, then the EM method gives you two functions $$Q_1(\theta_1,\theta^{(k)}) = \mathbf{E}\{\log p_{\theta_1}(y|z)\}$$ and $$Q_2(\theta_2,\theta^{(k)}) = \mathbf{E}\{\log p_{\theta_2}(z)\}$$ (where all expectations are taken with respect to $p_{\theta^{(k)}}(z|y)$. Similarly, the M-step splits into two different optimization problems: $$\theta_1^{(k+1)} = \arg\max_{\theta_1} Q_1(\theta_1, \theta^{(k)}),$$ and $$\theta_2^{(k+1)} = \arg\max_{\theta_2} Q_2(\theta_2, \theta^{(k)}).$$

Sadly (as you may guess from my examples) there is no general way to solve a problem with EM... it all depends on the structure: How easy is it to compute $p(z|y)$? How easy is it to take expectations with respect to it? Which latent variables $z$ may I need to make the problem simpler? Which part can I disregard?


Additional answer to point 2:

WARNING: notation changes w.r.t. the previous section!

What formulas you use really depend on your model; all in all what you want to solve is $$\hat \theta = \arg \max \log p(x|\theta)$$ where $x$ is the data. The key assumption is that $p(x|\theta)$ is not available in closed form or is complicated to work with (if it were easy, you would just maximize it and be happy!). Instead, you have access to $p(x,y|\theta)$ and you use the EM method to solve $$\hat \theta = \arg \max \log \int p(x,y|\theta) \mathrm d y.$$ In this example the variable $y$ is the latent variable which you introduce to make the problem tractable. Consider for instance the mixture of two Gaussians $$p(x|\theta) = \alpha N(x|m_1,\sigma_1^2) + (1-\alpha)N(x|m_2,\sigma_2^2).$$

Estimating $\theta = {\alpha,m_1,\sigma_1,m_2,\sigma_2}$ from data can be either done directly using numerical optimization; or introducing a latent variable $y$ that tells you which of the mixtures the datapoint belongs to. Then we have the conditional densities (the likelihoods) $$p(x|y=1,\theta) = N(x|m_1,\sigma_1^2)\qquad p(x|y=2, \theta) = N(x|m_2,\sigma_2^2).$$ We apply the EM method by computing, at each iteration, the probability that a sample belongs to either mixture (i.e. $p(y=i|x,\hat\theta^{(k)}$) and then maximizing the likelihood of the parameters using this probability assignment.

I hope this more explicit example answers your question.


Additional remark about discrete latent variables

If $z$ are discrete random variables (say, the outcome of a draw of cards), then the expectation with respect to the latent variables is effectively a sum: $$ \mathbf E\{\log p_\theta(y,z)\} = \sum_{i=1}^M r_i \log p_\theta(y,z_i) $$ where $r_i$ denotes the probability of outcome $z_i$ given the observed data (for the parameter value $ \theta^{(k)}$): $$ r_i = p(z_i | y; \theta^{(k)}).$$


Additional remark about discrete i.i.d. observations

In the previous discourse, $y$ denoted a set of observations. In case we have $y = \{y_j\}_{j=1}^N$ where each measurement $y_j$ is drawn from some distribution $p_\theta(y)$, then we have that the joint distribution is $$\log p_\theta(y) = \sum_{j=1}^N \log p_\theta(y_j).$$

In this case, $$Q(\theta,\theta^{(k)}) = \mathbf{E}\{ \log p_\theta(y,z)\} = \sum_{j=1}^N \mathbf{E}\{\log p_\theta(y_j,z)\}.$$ Combining this with the discussion at the previous point, we have that in case $z_i$ are discrete outcomes,

$$Q(\theta, \theta^{(k)}) = \sum_{j=1}^N\sum_{i=1}^M r_{i,j} \log p_\theta(y_j,z_i).$$ where $r_i = p(z_i|y_j;\theta^{(k)}).$$

$\endgroup$
  • $\begingroup$ Thanks. you mentioned "if $p_\theta(y,z) = q_\theta(y,z)g(y,z)$ where $g(y,z)$ is independent of $\theta$...." what if $p_{\theta}(z|y) = p_{\theta}(z,y)/p(y)$ shall we ignore p(y) because it is independent of $\theta$? $\endgroup$ – Mosab Shaheen Apr 3 at 14:15
  • $\begingroup$ Also what if z is a sequence like in Part of Speech tagging, where z is a sequence like (noun, verb, preposition, adjective, noun) and y is the sentence like (he, went,to, beautiful, place) then if we take $ p_\theta(y) = \Sigma_{z} p_\theta(y,z)$ in this case what will be the values of z. As I said z is a sequence of a length that is equal to the length of the sentence y and if we do not know y beforehand then we can not know the length (number of elements) of the sequence z $\endgroup$ – Mosab Shaheen Apr 3 at 14:31
  • $\begingroup$ and even suppose we knew the length of z is n then there are $n^{M}$ possible sequences where M is the number of Parts of Speech in English. So how can we pick z values in this case (if z is only a part (not parts) of speech i.e. an element (not a sequence) then we have only M values possible for z but in the case where z is a sequence how can we deal with that in the Expectation Maximization Algorithm? $\endgroup$ – Mosab Shaheen Apr 3 at 14:31
  • $\begingroup$ I am asking this because I have already seen papers using EM for Part of Speech tagging but they did not mention the details. $\endgroup$ – Mosab Shaheen Apr 3 at 14:34
  • $\begingroup$ And Last point, sometimes I find people writing $ \theta^{(k+1)} = argmax_{\theta^{'}} \mathbf{E}\{\log p_\theta(y,z)\} = argmax_{\theta^{'}} \Sigma_{(z,y) \in (Z,Y)} p(z|y, \theta) \log p(z,y|\theta)$ and other times, as what you mentioned, $argmax_{\theta^{'}} \Sigma_{(z \in Z)} p(z|y,\theta) \log p(z,y|\theta)$ in other words should not we take all the combinations of both the hidden and observed variables (z,y) or we should take only one sample from the data with all the possible values of (z). $\endgroup$ – Mosab Shaheen Apr 3 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.