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

{ P ( X ∣ c ) = ∑ k = 1 K π k N ( x ( n ) ∣ μ k , Σ k ) N ( x ( n ) ∣ μ k , Σ k ) = 1 ( 2 π ) d 2 ∣ Σ k ∣ 1 2 e x p [ − 1 2 ( x ( n ) − μ k ) T Σ − 1 ( x ( n ) − μ k ) ] ∑ k = 1 K π k = 1 \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​

π k \pi_k πk​ – the probability of one example belongs to the k t h k^{th} kth Gaussian model/the weight of k t h 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

γ n k \gamma_{nk} γnk​ – the probability of x ( n ) x^{(n)} x(n) belongs to k t h k^{th} kth model
N k N_k Nk​ – the expectation of #examples belong to k t h k^{th} kth 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.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！