Gaussian Mixture Model 高斯混合模型 GMM

---

Gaussian mixture model is a combine of multiple Gaussian models. These Gaussian models mixture according to ‘weight’ $\pi$π. The picture is a mixture of two models.

---

GMM

$\left\{\begin{array}{l} P(X|c) = \sum\limits_{k=1}^K\pi_kN(x^{(n)}|\mu_k, \Sigma_k) \\ N(x^{(n)}|\mu_k, \Sigma_k) = \frac{1}{(2\pi)^{\frac d2}|\Sigma_k|^{\frac12}}exp[-\frac12(x^{(n)}-\mu_k)^T\Sigma^{-1}(x^{(n)}-\mu_k)] \\ \sum\limits_{k=1}^K \pi_k= 1 \end{array}\right.$⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​P(X∣c)=k=1∑K​πk​N(x(n)∣μk​,Σk​)N(x(n)∣μk​,Σk​)=(2π)2d​∣Σk​∣21​1​exp[−21​(x(n)−μk​)TΣ−1(x(n)−μk​)]k=1∑K​πk​=1​

$\pi_k$πk​ – the probability of one example belongs to the $k^{th}$kth Gaussian model/the weight of $k^{th}$kth model in the mixture model

Attention! GMM is not a convex function and it has local optima(k local optima). What shall we do?
Strategies:
(i) gradient descent
(ii) heuristic algorithm including Simulated Annealing, Evolutionary Algorithms, etc (People hardly use these algorithms nowadays)
(iii)EM algorithm Today’s superstar

EM Algorithm for GMM

general EM Algorithm

Pros and cons

Cons:

1. EM algorithm is not a general algorithm dealing with non-convex problem.

Pros:

1. No hyper-parameters
2. Simple coding work
3. Theoretically graceful

---

EM for GMM

$\gamma_{nk}$γnk​ – the probability of $x^{(n)}$x(n) belongs to $k^{th}$kth model
$N_k$Nk​ – the expectation of #examples belong to $k^{th}$kth model

$randomize \{\pi_k,\mu_k,\Sigma_k\}_{k=1\sim K} \\ while (!converge) \\ \{ \\ \ \ \ \ \ \ \ \ E-step: \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \gamma_{nk} = \frac{\pi_kN(x_n|\mu_k, \Sigma_k)}{\sum\limits_{k=1}^KN(x_n|\mu_k, \Sigma_k)} \\ \ \ \ \ \ \ \ \ M-step: \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ N_k= \sum\limits_{k=1}^K\gamma_{nk} \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ for(k \ models) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \{ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pi_k^{(new)}=\frac{N_k}{N} \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mu_k^{(new)} = \frac{1}{N_k}\sum\limits_{n=1}^N\gamma_{nk}x^{(n)} \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Sigma_k^{(new)} = \frac{1}{N_k}\sum\limits_{n=1}^N\gamma_{nk}[x^{(n)}-\mu_k^{(new)}] [x^{(n)}-\mu_k^{(new)}] ^T \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \{ \\ \}$randomize{πk​,μk​,Σk​}k=1∼K​while(!converge){        E−step:                 γnk​=k=1∑K​N(xn​∣μk​,Σk​)πk​N(xn​∣μk​,Σk​)​        M−step:                 Nk​=k=1∑K​γnk​                for(k models)                {                        πk(new)​=NNk​​                        μk(new)​=Nk​1​n=1∑N​γnk​x(n)                        Σk(new)​=Nk​1​n=1∑N​γnk​[x(n)−μk(new)​][x(n)−μk(new)​]T                {}
We use soft discrimination in this application of EM algorithm, which means we will compute the probability of each examples belongs to all models. In other applictions, take K-Means clustering algorithm for example, we use winner-takes-all strategy.