1
$\begingroup$

I was trying to understand Expectation maximization algorithm. This is how it is defined in Andrew Ng's Stanford CS229 course:

$$ \text{Repeat until convergence \{}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \\ \text{(E-step) For each i, set} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\\ Q_{i}\left(z^{(i)}\right):=p\left(z^{(i)} \mid x^{(i)} ; \theta\right) \\ \text{(M-step) Set} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \\ \begin{aligned} \theta &:=\arg \max _{\theta} \sum_{i=1}^{n} \operatorname{ELBO}\left(x^{(i)} ; Q_{i}, \theta\right) \\ &=\arg \max _{\theta} \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \end{aligned}\\ \}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad $$

Then I searched for the example and found this coin flip example. It explains the end part of E-step and M-step as follows:

enter image description here

Though I followed both sources individually, I am unable to see how above calculations for $\theta_a^1$ and $\theta_b^1$ in M-step map to Andrew's M-step. Are these steps map-able / similarly done in both sources?

PS: I tried mapping various equations in both sources:

  • Example's $E=HTH...HT$ is Andrew's $x$
  • $\theta$ is coin bias
  • Example's $Z_i$ is Andrew's $Z^{(i)}$ and is event that we chose coin $i$
  • $Q$ is distribution of $Z$, that is probabilities with which coins will be chosen
  • Example's $P(E|Z_A)$ is Andrew's p(x,z;\theta)
  • Example's $P(Z_A|E)$ is Andrew's $Q_i(z^{(i)})=p(z^{(i)}|x^{(i)};\theta)$
$\endgroup$

1 Answer 1

0
$\begingroup$

Looking at the ELBO equation in Andrew Ng's course, we have a model p representing the data generation process from latent to observable, and an approximation of this model with Q. The ELBO aims to optimise a function such that Q is as close to p as possible, thus giving Q a good fit of p.

This is what the argmax in the M-step finds, the distance here is a probability distance called the KL divergence, read more about this and feel free to ask a question here on it.

So now we know that Q attempts to find a good model to fit p, what is the M-step in the coin flipping example doing and how is it related? Given it is a binomial probability, look up the expectation of a series of coin flips, and the estimation of the probability parameter.

Try and piece together the probability parameter estimation and the M-step above. The M-step is to update the parameters, which here is the estimation of the probability parameter. This should be helpful - give it a go

Also, if you are looking for more examples and some code that displays how the EM algorithm works, I can provide more advice if you are interested in learning about it.

$\endgroup$

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.