# Expectation Maximization for the Gaussian Mixture Model

* Last class we introduced the Gaussian Mixture Model:
     * $p(x) = \sum_{k=1}^K \pi_k N(x | \mu_k, \Sigma_k)$  where $0 \le \pi_k \le 1$ and $\sum_k \pi_k = 1$

* Suppose we are given $X = \left\{ \mathbf{x}_1, \ldots, \mathbf{x}_N\right\}$ where each $\mathbf{x}_i$ is a sample from one of the $K$ Gaussians in our mixture model.  We want to estimate $\pi_k, \mu_k, \Sigma_k$ given $X$. 
*  So, we want to maximize the following data likelihood:
\begin{equation}
\hat\Theta = argmax_\Theta \prod_{i=1}^N \sum_{k=1}^K \pi_k N(x | \mu_k, \Sigma_k)
\end{equation}
where $\Theta = \left\{ \pi_k, \mu_k, \Sigma_k \right\}_{k=1}^K$


* It is difficult to maximize! We should try to simpler version in which we add latent variables to simplify the problem (and apply EM). 

*  The hidden/latent/missing variable we added was the label of the Gaussian from which $\mathbf{x}_i$ was drawn

\begin{equation}
\mathbf{x}, z \sim f(\mathbf{x},z|\theta)
\end{equation}


* The complete data likelihood is then: 
\begin{eqnarray}
L^c &=& \prod_{i=1}^N p(\mathbf{x}_i | z_i, \theta)p(z_i)\\
&=& \prod_{i=1}^N N(\mathbf{x}_i| \mu_{z_i}, \theta_{z_i})\pi_{z_i}
\end{eqnarray}

* Since we do not know the $z_i$ values, we do not just guess one value - we average over all possible values for $z_i$.  In other words, we take the *expectation* of the complete likelihood with respect to $z$

\begin{eqnarray}
Q(\Theta, \Theta^t) &=& \mathbb{E}\left[ \ln p(\mathbf{X}, \mathbf{z}|\Theta) | \mathbf{X}, \Theta^{t} \right]\\
&=& \sum_{\mathbf{z}} p(\mathbf{z}|\mathbf{X},\Theta^t)\ln p(\mathbf{X}, \mathbf{z}|\Theta)\\
&=& \sum_{i=1}^N \sum_{z_i=1}^K p(z_i|\mathbf{x}_i,\Theta^t)\ln p(\mathbf{x}_i, z_i|\Theta)\\
&=& \sum_{i=1}^N \sum_{z_i=1}^K p(z_i|\mathbf{x}_i,\Theta^t)\ln p(\mathbf{x}_i|z_i,\Theta) p(z_i)
\end{eqnarray}

* Thus, to take the expectation, we need $p(z_i|\mathbf{x}_i,\Theta^t)$
\begin{eqnarray}
p(z_i|\mathbf{x}_i,\Theta^t) &=& \frac{\pi_{z_i}^t p_{z_i}(\mathbf{x}_i|\theta_{z_i}^t, z_i)}{p(\mathbf{x}_i|\Theta^t)}\\
&=& \frac{\pi_{z_i}^t p_{z_i}(\mathbf{x}_i|\theta_{z_i}^t, z_i)}{\sum_{k=1}^K \pi_k^t p_k(\mathbf{x}_i|\theta_k^t, k)}
\end{eqnarray}

* This completes the Expectation step in EM.  Now, we must derive the update equations for the Maximization step.  So, we need to maximize for $\pi_k, \Sigma_k, \mu_k$.



## Update equation for mean of the kth Gaussian

* For simplicity, let us assume that $\Sigma_k = \sigma_k^2\mathbf{I}$
\begin{eqnarray}
Q(\Theta, \Theta^t) &=& \sum_{i=1}^N \sum_{z_i=1}^K p(z_i|\mathbf{x}_i,\Theta^t)\ln p(\mathbf{x}_i|z_i,\Theta) p(z_i)\\
 &=& \sum_{i=1}^N \sum_{k=1}^K p(z_i=k|\mathbf{x}_i,\Theta^t)\ln {N}(\mathbf{x}_i|\mu_k, \sigma_k^2) \pi_k\\
 &=& \sum_{i=1}^N \sum_{k=1}^K p(z_i=k|\mathbf{x}_i,\Theta^t)\ln {N}(\mathbf{x}_i|\mu_k, \sigma_k^2) + \ln \pi_k\\
  &=& \sum_{i=1}^N \sum_{k=1}^K p(z_i=k|\mathbf{x}_i,\Theta^t)\left( -\frac{d}{2}\ln\sigma_k^2 -\frac{1}{2\sigma_k^2}\left\| \mathbf{x}_i - \mu_k \right\|_2^2 + \ln \pi_k \right)
\end{eqnarray}

\begin{eqnarray}
\frac{\partial Q(\Theta, \Theta^t)}{\partial \mu_k} &=& \frac{\partial}{\partial \mu_k} \left[\sum_{i=1}^N \sum_{k=1}^K p(z_i=k|\mathbf{x}_i,\Theta^t)\left( -\frac{d}{2}\ln\sigma_k^2 -\frac{1}{2\sigma_k^2}\left\| \mathbf{x}_i - \mu_k \right\|_2^2 + \ln \pi_k \right)\right] = 0\\
&=& \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)\left(  \frac{1}{\sigma_k^2}\left(\mathbf{x}_i - \mu_k \right) \right) = 0\\
&=& \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)\frac{\mathbf{x}_i}{\sigma_k^2} - \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t) \frac{\mu_k}{\sigma_k^2} = 0\\
&=& \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)\frac{\mathbf{x}_i}{\sigma_k^2} = \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t) \frac{\mu_k}{\sigma_k^2}\\
&=& \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)\mathbf{x}_i = \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t) \mu_k\\
& &\mu_k = \frac{\sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)\mathbf{x}_i}{\sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)}
%
\end{eqnarray}



## Update equation for the variance of the kth Gaussian

\begin{eqnarray}
\frac{\partial Q(\Theta, \Theta^t)}{\partial \sigma_k^2} &=& \frac{\partial}{\partial \sigma_k^2} \left[\sum_{i=1}^N \sum_{k=1}^K p(z_i=k|\mathbf{x}_i,\Theta^t)\left( -\frac{d}{2}\ln\sigma_k^2 -\frac{1}{2\sigma_k^2}\left\| \mathbf{x}_i - \mu_k \right\|_2^2 + \ln \pi_k \right)\right] = 0\\
&=&  \sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t)\left[\left( -\frac{1}{2\sigma_k^2} + \frac{2}{2\left(\sigma_k^2\right)^2}\left\| \mathbf{x}_i - \mu_k \right\|_2^2 \right)\right] = 0\\
&=&  \sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t)\frac{2}{2\sigma_k^2} = \sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t)\frac{1}{\left(\sigma_k^2\right)^2}\left\| \mathbf{x}_i - \mu_k \right\|_2^2  \\
&=&  \sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t) = \sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t)\frac{1}{\sigma_k^2}\left\| \mathbf{x}_i - \mu_k \right\|_2^2  \\
&=&  \sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t) = \frac{1}{\sigma_k^2} \sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t)\left\| \mathbf{x}_i - \mu_k \right\|_2^2  \\
&=&   \sigma_k^2 = \frac{\sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t)\left\| \mathbf{x}_i - \mu_k \right\|_2^2}{  \sum_{i=1}^N p(z_i=k|\mathbf{x}_i,\Theta^t)} 
%
\end{eqnarray}

## Update Equation for mixture weights

\begin{eqnarray}
& & \frac{\partial Q(\Theta, \Theta^t)}{\partial \pi_k} = \nonumber \\
& &\frac{\partial}{\partial \pi_k} \left[\sum_{i=1}^N \sum_{k=1}^K p(z_i=k|\mathbf{x}_i,\Theta^t)\left( -\frac{d}{2}\ln\sigma_k^2 -\frac{1}{2\sigma_k^2}\left\| \mathbf{x}_i - \mu_k \right\|_2^2 + \ln \pi_k \right) - \lambda\left(\sum_{k=1}^K \pi_k - 1\right)\right] = 0 \nonumber\\
&=&\sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)\left(\frac{1}{\pi_k} \right) - \lambda  = 0 \nonumber\\
&=& \left(\frac{1}{\pi_k} \right)  \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)- \lambda  = 0 \nonumber\\
&=&  \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)  = \lambda \pi_k \nonumber\\
%
\end{eqnarray}

Since $\sum_k \pi_k = 1$, then:
\begin{eqnarray}
& \sum_{k=1}^K \frac{\sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)}{\lambda}  =  \sum_{k=1}^K \pi_k = 1\nonumber\\
& \lambda = \sum_{k=1}^K \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t) \nonumber\\
\end{eqnarray}

So: 
\begin{eqnarray}
\pi_k &=&\frac{\sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)}{\sum_{k=1}^K \sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)} \\
 &=&\frac{\sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)}{\sum_{i=1}^N \sum_{k=1}^K  p(z_i=k|\mathbf{x}_i,\Theta^t)}\\
  &=&\frac{\sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)}{\sum_{i=1}^N 1}\\
    &=&\frac{\sum_{i=1}^N  p(z_i=k|\mathbf{x}_i,\Theta^t)}{N}
\end{eqnarray}


* We now have everything we need to implement the EM algorithm.  

* Pseudo-code for the algorithm is: 

    * Initialize all parameters
    * t = 1
    * While convergence not yet reached:
        * E-step:  Compute $p(z_i=k|\mathbf{x}_i,\Theta^t)$ for every $\mathbf{x}_i$ and $k$
        * M-step:
            * Update $\mu_k$ for all $k$
            * Update $\sigma_k^2$ for all $k$
            * Update $\pi_k$ for all $k$
        * t = t+1
        * Check convergence criteria



```python

```

ac21a798b683762b25246c87dee1076f7ed98dbb
ipynb
Jupyter Notebook
Lecture10_EM/Expectation Maximization for the Gaussian Mixture Model.ipynb
Danlobaton/LectureNotes
fdfc8521d0cede127eb27f75337fbcc4f63eb042
MIT
Lecture10_EM/Expectation Maximization for the Gaussian Mixture Model.ipynb
Danlobaton/LectureNotes
fdfc8521d0cede127eb27f75337fbcc4f63eb042
MIT
Lecture10_EM/Expectation Maximization for the Gaussian Mixture Model.ipynb
Danlobaton/LectureNotes
fdfc8521d0cede127eb27f75337fbcc4f63eb042
MIT
Qwen/Qwen-72B
1. YES
2. YES