I'm reading about EM; It seems that transforms the likelihood $$Pr(X| \theta)$$ in $$\sum_h Pr(X,H=h |\theta)$$ with $H$ hidden variable that is a not observed variable which could, hypothetically, influence the data $X$. My questions are:

  1. so, EM is possible in any case? hypothetically, any data could be "decomposed" into an observed part $X$ and an hidden part $H$ that influence $X$, or are there cases which doesn't accept EM "decomposition" in hidden+observed?

  2. if 1. is true, when i break down my model (i.e. when I transform $Pr(X| \theta)$ in $\sum_h Pr(X,H=h |\theta)$ ), could I break down my hidden variable in more hidden variables? i.e. could have $$Pr(X| \theta)=\sum_{h_1}\sum_{h_2}Pr(X,H_1=h_1 ,H_2=h_2|\theta)$$ or $$Pr(X| \theta)=\sum_{h_1}\sum_{h_2}\sum_{h_3}Pr(X,H_1=h_1 ,H_2=h_2,H_3=h_3|\theta)$$ and so on? Is there a limit or why using just an hidden variable (or, complementarily, more variables) to model a problem?


EM is in principle applicable any time you have a joint model over the observations and the data. In fact, usually we are interested in cases where there are many hidden variables. For example, consider unsupervised Part of Speech (PoS) tagging with a Hidden Markov Model (HMM). In unsupervised PoS tagging, we are interested in finding labels for each word token so that verbs have the same label, nouns have the same label, and so on. This means that, for each word sequence, there is a hidden variable $p_t$ for the PoS tag of each word $w_t$:

\begin{align} P( \mathbf{w} | \theta ) & = \sum_{\mathbf{p}} P( \mathbf{w}, \mathbf{p} | \theta) \\ & = \sum_{p_1}\sum_{p_2}\ldots\sum_{p_n} P( w_1, \ldots, w_n, p_1, \ldots, p_n | \theta ) \\ & = \sum_{p_1}\sum_{p_2}\ldots\sum_{p_n} \prod_{i=1}^{n} P( w_i | p_i, \theta )P( p_{i} | p_{i-1}, \theta ) \end{align} where $p_0$ is a special "start" tag, $n$ is the length of $\mathbf{w}$, and $\mathbf{p}$ is the space of all PoS tag sequences the same length as $\mathbf{w}$.

However, there are cases where the MLE is the "wrong" answer, so EM will give you the wrong answer. Consider an infinite HMM in which the number of different PoS tags is unknown and therefore treated as part of $\theta$. The maximum-likelihood solution will then have an enormous number of PoS tags so that $P( w_i | p_i, \theta)$ is always 1, and $P( p_i | p_{i-1}, \theta )$ is always 1 for the word strings that occur in the dataset. For example, EM could say that each word token has a unique PoS tag and thereby assign the entire dataset a probability of one.

The issue here is that EM minimizes the data complexity (= maximizes the data marginal likelihood) but does not pay attention to the complexity of the parameters that results from hypothesizing a large number of PoS tags. We need a prior on $\theta$, including the number of tags, to balance model complexity against data complexity. For problems like this, non-parametric Bayesian approaches such as Dirichlet Processes are appropriate.

So, EM can, in principle, be applied to any joint model to find the MLE, regardless of the number of hidden variables, but the MLE itself may not be quite what you want.


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.