高斯混合模型Gaussian Mixture Models

項目位址：https://github.com/Daya-Jin/ML_for_learner/blob/master/mixture/GaussianMixture.ipynb

原部落格：https://daya-jin.github.io/2019/03/15/Gaussian_Mixture_Models/

算法概述

高斯混合模型(Gaussian Mixture Models)是一種無監督聚類模型。GMM認為不同類别的特征密度函數是不一樣的(實際上也不一樣)，GMM為每個類别下的特征分布都假設了一個服從高斯分布的機率密度函數：

P ( x ∣ c k ) = 1 2 π σ k e x p ( − ( x − μ k ) 2 2 σ k 2 ) P ( x ∣ c k ) ∼ N ( μ k , σ k ) \begin{aligned} P(x|c_{k})&=\frac{1}{\sqrt{2\pi}\sigma_{k}}exp(-\frac{(x-\mu_{k})^{2}}{2\sigma_{k}^2}) \\ P(x|c_{k})&{\sim}N(\mu_{k},\sigma_{k}) \\ \end{aligned} P(x∣ck​)P(x∣ck​)​=2π

​σk​1​exp(−2σk2​(x−μk​)2​)∼N(μk​,σk​)​

而資料中又可能是由多個類混合而成，是以資料中特征的機率密度函數可以使用多個高斯分布的組合來表示：

P ( x ) = ∑ k = 1 K P ( c k ) P ( x ∣ c k ) = ∑ k = 1 K π k N ( x ∣ μ k , σ k ) \begin{aligned} P(x)&=\sum\limits_{k=1}^{K}P(c_{k})P(x|c_{k}) \\ &=\sum\limits_{k=1}^{K}\pi_{k}N(x|\mu_{k},\sigma_{k}) \\ \end{aligned} P(x)​=k=1∑K​P(ck​)P(x∣ck​)=k=1∑K​πk​N(x∣μk​,σk​)​

其中 π k \pi_{k} πk​為類分布機率，也可看做是各高斯分布函數的權重系數，也叫做混合系數(mixture coefficient)，其滿足 ∑ k = 1 K π k = 1 \sum_{k=1}^{K}\pi_{k}=1 ∑k=1K​πk​=1。

Expectation-Maximization

模型的形式有了，給定一組資料 X X X，我們需要得到一組參數 { μ , σ } \{\mu,\sigma\} {μ,σ}，使得在這組參數下觀測資料 X X X出現的機率最大，即最大似然估計。對于資料中的所有樣本，其出現的機率(似然函數)為：

∏ i = 1 N P ( x i ) = ∏ i = 1 N ∑ k = 1 K π k N ( x i ∣ μ k , σ k ) \prod\limits_{i=1}^{N}P(x_{i})=\prod\limits_{i=1}^{N}\sum\limits_{k=1}^{K}\pi_{k}N(x_{i}|\mu_{k},\sigma_{k}) i=1∏N​P(xi​)=i=1∏N​k=1∑K​πk​N(xi​∣μk​,σk​)

對數似然函數為：

∑ i = 1 N ln ⁡ { ∑ k = 1 K π k N ( x i ∣ μ k σ k ) } \sum\limits_{i=1}^{N}\ln\{\sum\limits_{k=1}^{K}\pi_{k}N(x_{i}|\mu_{k}\sigma_{k})\} i=1∑N​ln{k=1∑K​πk​N(xi​∣μk​σk​)}

假設我們現在有了參數 { μ , σ } \{\mu,\sigma\} {μ,σ}，需要計算某個樣本對應的類簇，由貝葉斯公式有：

P ( c k ∣ x i ) = P ( c k , x i ) P ( x i ) = P ( x i ∣ c k ) P ( c k ) P ( x i ) = π k N ( x i ∣ μ k , σ k ) ∑ k = 1 K π k N ( x i ∣ μ k , σ k ) \begin{aligned} P(c_{k}|x_{i})&=\frac{P(c_{k},x_{i})}{P(x_{i})} \\ &=\frac{P(x_{i}|c_{k})P(c_{k})}{P(x_{i})} \\ &=\frac{\pi_{k}N(x_{i}|\mu_{k},\sigma_{k})}{\sum\limits_{k=1}^{K}\pi_{k}N(x_{i}|\mu_{k},\sigma_{k})} \end{aligned} P(ck​∣xi​)​=P(xi​)P(ck​,xi​)​=P(xi​)P(xi​∣ck​)P(ck​)​=k=1∑K​πk​N(xi​∣μk​,σk​)πk​N(xi​∣μk​,σk​)​​

可以看出就是一個softmax的形式。同時，有了 P ( c k ∥ x i ) P(c_{k}\|x_{i}) P(ck​∥xi​)之後，又可以計算出某個類别的分布機率與該類别下的統計量：

N k = ∑ i = 1 N P ( c k ∣ x i ) π k = N k N = 1 N ∑ i = 1 N P ( c k ∣ x i ) μ k = 1 N k ∑ i = 1 N P ( c k ∣ x i ) x i σ k = 1 N k ∑ i = 1 N P ( c k ∣ x i ) ( x i − μ k ) 2 \begin{aligned} N_{k}&=\sum\limits_{i=1}^{N}P(c_{k}|x_{i}) \\ \pi_{k}&=\frac{N_{k}}{N}=\frac{1}{N}\sum\limits_{i=1}^{N}P(c_{k}|x_{i}) \\ \mu_{k}&=\frac{1}{N_{k}}\sum\limits_{i=1}^{N}P(c_{k}|x_{i})x_{i} \\ \sigma_{k}&=\sqrt{\frac{1}{N_{k}}\sum\limits_{i=1}^{N}P(c_{k}|x_{i})(x_{i}-\mu_{k})^{2}} \\ \end{aligned} Nk​πk​μk​σk​​=i=1∑N​P(ck​∣xi​)=NNk​​=N1​i=1∑N​P(ck​∣xi​)=Nk​1​i=1∑N​P(ck​∣xi​)xi​=Nk​1​i=1∑N​P(ck​∣xi​)(xi​−μk​)2

​​

其中 N k N_{k} Nk​為類别 k k k出現的頻率期望。

以上兩步計算實質上對應了期望最大化(Expectation-Maximization)算法的E步(E-step)跟M步(M-step)。

多元資料時的情況

在多元資料下，需要為每個類生成一個多元高斯分布，表示方式與單維情況稍有不同：

N ( x i ∣ μ k , Σ k ) = 1 ( 2 π ) n / 2 Σ k 1 / 2 e x p ( − 1 2 ( x i − μ k ) T Σ k − 1 ( x i − μ k ) ) N(x_{i}|\mu_{k},\Sigma_{k})=\frac{1}{(2\pi)^{n/2}\Sigma_{k}^{1/2}}exp(-\frac{1}{2}(x_{i}-\mu_{k})^{T}\Sigma_{k}^{-1}(x_{i}-\mu_{k})) N(xi​∣μk​,Σk​)=(2π)n/2Σk1/2​1​exp(−21​(xi​−μk​)TΣk−1​(xi​−μk​))

訓練

有了算法架構，怎麼訓練模型呢。在初始時随機生成 K K K個高斯分布，然後不斷地疊代EM算法，直至似然函數變化不再明顯或者達到了最大疊代次數。

E-step

在給定的多元高斯分布下，計算各樣本屬于各個類别的機率：

P ( c k ∣ x i ) = π k P ( c k ∣ x i ) ∑ k = 1 K π k P ( c k ∣ x i ) P(c_{k}|x_{i})=\frac{\pi_{k}P(c_{k}|x_{i})}{\sum\limits_{k=1}^{K}\pi_{k}P(c_{k}|x_{i})} P(ck​∣xi​)=k=1∑K​πk​P(ck​∣xi​)πk​P(ck​∣xi​)​

M_step

根據機率重新計算更優的高斯參數：

N k = ∑ x = 1 N P ( c k ∣ x i ) π k = N k N μ k = 1 N k ∑ i = 1 N P ( c k ∣ x i ) x i Σ k = 1 N k ∑ i = 1 N P ( c k ∣ x i ) ( x i − μ k ) T ( x i − μ k ) \begin{aligned} N_{k}&=\sum\limits_{x=1}^{N}P(c_{k}|x_{i}) \\ \pi_{k}&=\frac{N_{k}}{N} \\ \mu_{k}&=\frac{1}{N_{k}}\sum\limits_{i=1}^{N}P(c_{k}|x_{i})x_{i} \\ \Sigma_{k}&=\frac{1}{N_{k}}\sum\limits_{i=1}^{N}P(c_{k}|x_{i})(x_{i}-\mu_{k})^{T}(x_{i}-\mu_{k}) \\ \end{aligned} Nk​πk​μk​Σk​​=x=1∑N​P(ck​∣xi​)=NNk​​=Nk​1​i=1∑N​P(ck​∣xi​)xi​=Nk​1​i=1∑N​P(ck​∣xi​)(xi​−μk​)T(xi​−μk​)​

實作指導

完整代碼