Gaussian Mixture Model 高斯混合模型 GMM

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

$$\{\begin{array}{l}P(X|c)=\sum _{k=1}^K{\pi }_{k}N(x^{(n)}|{\mu }_k,{\Sigma }_k)\\ N(x^{(n)}|{\mu }_k,{\Sigma }_k)=\frac{1}{(2\pi {)}^{\frac{d}{2}}|{\Sigma }_k{|}^{\frac{1}{2}}}exp[-\frac{1}{2}(x^{(n)}-{\mu }_k{)}^T{\Sigma }^{-1}(x^{(n)}-{\mu }_k)]\\ \sum _{k=1}^K{\pi }_k=1\end{array}$$

${\pi }_k$ – the probability of one example belongs to the $k^{th}$ Gaussian model/the weight of $k^{th}$ 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}$ – the probability of $x^{(n)}$ belongs to $k^{th}$ model
$N_k$ – the expectation of #examples belong to $k^{th}$ model

r a n d o m i z e { π k , μ k , Σ k } k = 1 ∼ K w h i l e ( ! c o n v e r g e ) { E − s t e p : γ n k = π k N ( x n ∣ μ k , Σ k ) ∑ k = 1 K N ( x n ∣ μ k , Σ k ) M − s t e p : N k = ∑ k = 1 K γ n k f o r ( k m o d e l s ) { π k ( n e w ) = N k N μ k ( n e w ) = 1 N k ∑ n = 1 N γ n k x ( n ) Σ k ( n e w ) = 1 N k ∑ n = 1 N γ n k [ x ( n ) − μ k ( n e w ) ] [ x ( n ) − μ k ( n e w ) ] T { } 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.