2
$\begingroup$

Background - I'm trying to follow section 7.2.4 in this EM tutorial. Basically the setup is I have a vector with 10 points $x$, and each of them can be assigned ($y$) to either Gaussian 1 or to Gaussian 2, and I want to estimate the parameters $\theta$ = (mean, std) of both Gaussians and assign which point belongs to which Gaussian.


I understand how do they arrive to

$Q(\theta|\theta^t) = \sum_y{p(y|x,\theta^t)logP(x,y|\theta)}$

Should it be read as: an expectation over $y$ = all possible configurations of the entire sample of all 10 points ($2^{10}$ configurations), each with its own probability (under the old parameters $\theta^t$), of the complete log likelihood of the sample and the assignments, under the new parameter $\theta$.

If this is the correct way to read this, I fail to understand the trick that helps us simplify the Q function to regarding one point at a time, and one Gaussian assignment at a time! What's the core idea that leads to the simplification:

$Q(\theta|\theta^t) = \sum_i\sum_j{p(y_{ij} = 1|x_i,\theta^t)logP(x_i,y_i = j|\theta)}$

Sorry if this is trivial, but the derivation just doesn't sit right for me and if someone could give me an intuition for this it would be a great help.

$\endgroup$
  • $\begingroup$ My understanding of $\sum_y{p(y|x,\theta^t)logP(x,y|\theta)}$ is that we have a value of confidence into our guess that this data is from a particular class $y$, which is formulated as the posterior. This posterior we multiply with a particular observation vector $x_i$. In Figure 1 of this source, it would be for instance for the first datasample and class A 0.45*5 Heads = 2.2 Heads. Is this correct? Source: nature.com/nbt/journal/v26/n8/fig_tab/nbt1406_F1.html $\endgroup$ – Pegah Aug 6 '17 at 21:31
2
+100
$\begingroup$

I'll use the example @Pegah quoted from nature. We are presented with 5 sets of 10 coin tosses. Each set was done with one of two imbalanced coins $A$ or $B$. We want to use EM in order to estimate the parameter of each coin $\theta_A$ and $\theta_B$ (the probability of heads in each coin), and to assign each set to the likely coin.

Now the general formulation of $Q$ is referring to vectors not specific instances, as it does not assume our instances are IID. So in our example $\vec{y}$ is the assignment of all 5 sets to either $A$ or $B$ and when we say:

$p(\vec{y}|\vec{x},\theta^t)$

we mean: the probability of a specific assignment $\vec{y}$ (e.g. $y_1 = A,y_2=A,y_3=B,y_4=A,y_5=B$) being the true assignment, given that we saw $\vec{x}$ which is the number of heads in each 10-tosses set (e.g. $x_1=4, x_2=3, x_3 = 7, x_4=2, x_5=1$) and under the current parameters $\theta^t_A$ and $\theta^t_B$.

So $Q$ is the expectation over all $2^5$ such $\vec{y}$ of the complete log-likelihood:

$Q(\theta|\theta^t) = \sum_{\vec{y}}{p(\vec{y}|\vec{x},\theta^t)logP(\vec{x},\vec{y}|\theta)}$

Not easy to compute with all those annoying vectors, huh?


Luckily in our case every instance (set of tosses) is IID from the other sets. So we simplify the complete log-likelihood:

$p(\vec{x}, \vec{y}|\theta_t) = \prod_i \prod_{j=\{A,B\}} p(x_i, y_i=j|\theta_t)^{y_{ij}}$

where ${y_{ij}}$ is an indicator variable which is 1 if $y_i = j$ and 0 otherwise.

so we can rewrite $Q$ as:

$Q(\theta|\theta^t) = \sum_{\vec{y}}{p(\vec{y}|\vec{x},\theta^t)} \sum_i\sum_j{y_{ij}logP(x_i,y_i = j|\theta)}$

we're still stuck with the vector, but now we can rearrange:

$Q(\theta|\theta^t) = \sum_i\sum_j logP(x_i,y_i = j|\theta) \sum_{\vec{y}} y_{ij} p(\vec{y}|\vec{x},\theta^t)$

and for a given $i, j$ the sum over all $\vec{y}$ is a sum over all $\vec{y}$ in which $y_i = j$ as in the others $y_{ij} = 0$, so according to the law of total probability it's just

$\sum_{\vec{y}} y_{ij} p(\vec{y}|\vec{x},\theta^t) = p(y_{ij} = 1|\vec{x},\theta^t)$

and because they are IID, that simplifies again to

$p(y_{ij} = 1|x_i,\theta^t)$

because the coins assigned to the other sets don't matter to $y_i$.

so we arrived to this nice form:

$Q(\theta|\theta^t) = \sum_i\sum_j logP(x_i,y_i = j|\theta) p(y_{ij} = 1|x_i,\theta^t)$

Thanks to EG for explaining this to me.

$\endgroup$
  • $\begingroup$ Many thanks! I understand the simplifications I think, I was more interested in being able to interpret the Q-function, but now it is clear as well:) Two questions: So, in the EM context, observations are usually = percentages? Also, do you know any good source for understanding EMs practically, exercises or coding-wise? $\endgroup$ – Pegah Aug 11 '17 at 7:23
  • $\begingroup$ @Pegah - observations are not usually percentages! The observations are a set of any observed data, and the latent variable is an unobserved, usually discrete variable. Classic example: you're given the height of several people (observations) and do not know their genders (latent variable). You assume that the heights for each gender distribute normally. you now use EM to estimate the most likely parameters $\mu$ and $\sigma$ for each gender AND to estimate which person is male and which is female. $\endgroup$ – ihadanny Aug 11 '17 at 14:06
  • $\begingroup$ I know this is why it confuse(d) me that here the x_i are not just integers (ie "3" for 3 heads etc.) or the like...? $\endgroup$ – Pegah Aug 11 '17 at 14:22
  • 1
    $\begingroup$ @Pegah - in the example you quoted from nature, the observations are the number of heads in a 10 tosses set (or the percentage of heads, its the same because all sets have exactly 10 tosses in your setup), and the latent variable is which coin was used for that set. The parameters you need to estimate for this distribution are simpler - a single parameter $p$ for each coin. And finally - I don't know of any good source for EM code.. but this looks promising: people.duke.edu/~ccc14/sta-663/EMAlgorithm.html $\endgroup$ – ihadanny Aug 11 '17 at 14:25

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.