EM algorithm for mixture of Gaussians - is it ok to use my updated mu's in my new estimate of Sigma, within a single M-step?

Question

Here is a screenshot from an assignment I am currently working on - these are the Expectation-Maximization update rules for the parameters $\omega$ (latent component "responsibilities"), $\mu$, and $\Sigma$ for a mixture of multivariate Gaussians.

To clarify notation (though this isn't actually too important, my question is for general E-M):

• $p(m|x_t;\theta)$ is the probability of latent component m given an $x_t$ (and there are a total of $T$ such $x_t$'s in the entire dataset $X$)
• $\theta$ is a parameter which holds $\omega$, $\mu$, and $\Sigma$

Within a single M-step, the updates for $\mu$ occur before the updates for $\Sigma$ (as in, the literal line of code for the $\mu$ update gets executed earlier).

So as I code this I am wondering: Is it kosher to use my updated $\mu$ in my calculation of the $\Sigma$ update, within the same "M-step"?

• On one hand, I would think that theoretically, all of these parameter updates are supposed to happen "instantaneously" and at the same time as each other - meaning, I should use the old, un-updated $\mu$ from just before my update.

• On the other hand, the updated $\mu$ is supposed to converge towards the "correct" value, so my updated $\mu$ should be "closer" to the truth - meaning that if I use the new $\mu$, it ought to give me a more "accurate" $\Sigma$ update.

Can anyone comment? Thank you!

---

Small edit: re the (very reasonable!) comment below that the notation should be more explicit in specifying $\theta^{current}$ vs $\theta^{update}$ - I completely agree that the notation as provided from the assignment is not at all clear, and hence the impetus for this question.

I've simplified, but in code my updates look something like this, and this performs reasonably well:

theta.omega = update_omega(theta, X)    
theta.mu = update_mu(theta, X)
theta.Sigma = update_Sigma(theta, X)

While the provided notation can be considered "bad", it does translate nicely to code, so perhaps the professor was just trying to help. If I weren't thinking too hard it would be easy to miss the fact that an updated theta is being fed into each sequential step.

I'm asking this question because I am curious about whether this is standard practice for implementing EM (as it seems to be in the sklearn GaussianMixture class - I believe that within a single M-step they take a freshly updated mu and feed it right into the covariance update), or whether this is technically a "different" approach (as the third comment may suggest!).

Answer 1

In short, updating the parameters all at once in the M step or one by one with the other being fixed are both justified by the same argument that both approaches do increase the (observed) likelihood at each step. See Meng and Rubin (Biometrika, 1993) for more details.

Answer 2

Yes, and it's easy to see why if we look at it the right way.

Forget about the M-step; in fact, forget the fact that we're inside an iterative algorithm at all. Forget about the past and that you ever had other estimates for $\vec{\mu}$ or $\mathbb{\Sigma}$. And forget that there are other classes, and just focus on one class. And forget that the weights can be interpreted as $p(m|\vec{x}_i;\theta)$ and just think of them as sample weights, origin unknown, called $w_i$. For convenience let's also assume that these weights are normalized, e.g. $\sum w_i = 1$.

What remains is a sample of $n$ (instead of $T$ so I can reserve $T$ for "transpose") observations $\vec{x}_i$ with weights $w_i$ which we believe came from a multivariate distribution $\mathcal{N}(\vec{\mu}, \mathbb{\Sigma})$. What is the procedure for estimating $\vec{\mu}$ and $\mathbb{\Sigma}$? Well, it's to first calculate the mean, subtract it off, then average over the outer products:

$$ \vec{\mu}= {1 \over {n}}\sum_{i=1}^n w_i \vec{x}_i \tag{1} $$

$$ \mathbb{\Sigma} = \frac{1}{n} \sum_{i=1}^n w_i ( \vec{x}_i - \vec{\mu} )(\vec{x}_i - \vec{\mu})^T \tag{2} $$

This is the ML estimate. Note that the $\vec{\mu}$ in (2) is exactly the same as the $\vec{\mu}$ in (1) - this is a closed form solution, not an iterative algorithm! Any other estimate for $\vec{\mu}$ and $\mathbb{\Sigma}$ will have lower likelihood, by definition.

Now we can lift our self imposed amnesia and recall that we are using E-M to numerically approximate the maximum likelihood of a GMM. For that one particular M step, we held all other parameters constant and maximized the likelihood with respect to just $\vec{\mu}$ and $\mathbb{\Sigma}$. Because we used the closed form solution of (1) and (2), we didn't take a "step" towards that maximum - we jumped straight to the maximum within that subspace. In particular we can guarantee that likelihood either increased or stayed the same. We need this property because it is necessary for the convergence of the E-M algorithm as a whole. Using the closed form ML estimate for the multivariate distribution is by easiest way to prove it, and any other procedure for updating $\vec{\mu}$ and $\mathbb{\Sigma}$ - such as using the $\mu$ left over from the previous step - would require a separate proof.

One good resource on GMM and the EM algorithm I used was this Stanford Lecture by Andrew Ng. I've linked to the part of the lecture where he shows this update step in particular but the whole lecture is worth watching.