機器學習: EM 演算法(Expectation-Maximization Algorithm, EM)、高斯混合模型(Gaussian Mixture Model, GMM)和GMM-EM詳細推導
這篇結構為
- 複習一些線代東西，EM會用到的。
凸函數
Jensen’s inequality - EM 演算法(Expectation-Maximization Algorithm)
- 高斯混合模型（Gaussian Mixed Model）
GMM概念
GMM公式怎麼來的 - GMM-EM
GMM-EM演算法流程
GMM-EM詳細推導
如果只是要看GMM用EM演算法流程的，請直接看「GMM-EM演算法流程」，想看推導的再看推導，因為有點複雜。
開始之前先稍微複習EM會用到的線性代數或是最佳化理論的內容
凸函數
如果f為實數x的函數，二階微分大於等於0，則f稱為凸函數，二階微分大於0稱為嚴格凸函數。
如果f為向量x的函數，二階微分矩陣(Hessian Matrix, H)如果是半正定(determinant(H)≥0)，則f稱j為凸函數，如果determinant(H)>0稱為嚴格凸函數。
Jensen’s inequality
機率論觀點，如果φ是凸函數，X是隨機變量
E: 期望值(expectation)，公式如下:
f:是x的機率密度函數。
EM 演算法(Expectation-Maximization Algorithm)
假設有一組n個資料，每個樣本之間彼此獨立，這組資料的概似函數(likelihood function)為
f為機率密度函數，θ為機率密度函數的參數。
這邊我們取了個概似函數的對數，如果熟悉MLE (maximum likelihood estimation，最大概似估計)的人會比較清楚。這邊簡單說原因就是「因為一堆樣本的概似函數為每個樣本的機率密度函數相乘(統計獨立的特性)，在推論上一堆東西相乘會難推導很多，所以這邊取個對數，讓概似函數變成每個樣本的機率密度函數的相加」。
Recall: 假設有兩個樣本x和y，如果x和y統計獨立則f(x,y)=f(x)f(y)。
假設每個樣本之間都有一些隱藏資訊z (因為EM大多用在GMM或是HMM中，所以需要假設有一個隱藏資訊)，我們要找到資訊z使的概似函數最大化，
如果要直接求θ，因為有z存在會困難一點，但當z確定後，用MLE求解就容易很多。EM則是用來解決存在隱藏資訊最佳化問題的方法；因為我們無法直接最大化L(θ)，所以我們可以不斷建立L(θ)的下界(E-step)，然後最佳化下界(M-step)，所以一般看到EM演算法都會聽到E-step和M-step兩個步驟。
剛剛的概似函數我們在前面乘上一個然後除上一個隱含變數z的機率分佈(q(z))
所以可以說
其中
φ=ln(X)是凹函數，所以上述式子可以用Jensen’s inequality表示，但等式要反向。
Recall: Jensen’s inequality
因為φ=ln(X)是凹函數，所以
所以概似函數L(θ)的下界(Lower Bound, LB)出來了
下界越大代表概似函數L(θ)越大，跟MLE理念相同，我們希望估計出來的概似函數可以越大越好。
假設θ給定，那L(θ)的值取決在於q(z(i))和f((i)x, z(i))，所以我們可以透過這兩個函數使下界不斷上生，去逼近L(θ)。當不等式變成等式時，代表我們調整出來的q(z(i))和f((i)x, z(i))可以讓下界等於L(θ)。
根據Jensen’s inequality，要讓等式成立需要讓隨機變數X變成常數。
因為q(z)是機率密度函數，
因為分子除以分母是常數，當分母項和是1時，分子項相加為那個常數，因此
上述(假設θ給定到這行)就是E-step的結果。
EM演算法步驟就是不斷重複E-step和M-step直到參數收斂。
這邊沒有對E-step和M-step做很多推導，因為E-step和M-step只是概念，實際隱藏參數和概似函數參數都會依據你實際應用的模型而產生，後面講到的GMM就是其中一種。
高斯混合模型（Gaussian Mixed Model）
GMM概念
一般在講高斯模型都會假設說資料分佈來自一個高斯模型，高斯模型如下:
我這邊舉一些資料是從高斯分佈(平均數是160, 標準差是5)抽樣出來的資料(100筆)，然後取直方圖，理論上樣本的分佈要跟高斯分佈要很像，實際上也很像(下圖)，這邊樣本如果樣本抽越多紅色線跟藍色線就越像。
但假設我從高斯分佈(平均數是160, 標準差是5)抽樣100筆資料，然後從高斯分佈(平均數是180, 標準差是5)抽樣100筆資料，此刻我有兩百筆資料，我如果一樣用單一個高斯分佈去估計這200筆資料就可能有問題，如下圖:
由上圖我們可以知道不能單用一個高斯分佈去估計資料，因此我這邊用2個高斯分佈相加去估計資料，此刻估計出來的分佈就會比較像實際資料的分佈，這個過程就稱為高斯混和模型，
有了上述概念後再來看高斯混合模型(Gaussian mixture model, GMM)會簡單很多，上面是說為什麼我們要用很多個高斯模型來形容我們的資料，至於是多少個高斯模型比較合適就是需要去測試才知道。
GMM公式怎麼來的
接下來這邊舉個例子是GMM的模型怎麼處理機率密度函數。
假設有K個袋子裡面有無窮多個糖果，每個袋子的機率密度函數都是高斯函數，當我們要拿一顆糖果出來的時候，我們要先隨一個袋子，然後從袋子拿一顆糖果出來，我們總共重複抽n次糖果，如下圖。
所以動作有
1. 先選一個袋子
這時候選袋子有是一種隨機變量，這邊假設K個袋子的隨機變量這邊假設是離散型的，連續型基本上差不多)為
2. 從袋子拿一顆糖果
從這個例子我們知道，z是無法量測的隨機變量，也就是隱藏變數，且其事前機率(priori)為
αk也就是第k個袋子(高斯分佈)被選中的事前機率，或稱為每個袋子被挑中的權重。
因此隱藏變數z的機率密度函數為
假設我們今天選中第k個袋子，然後抽中糖果x發生機率是
寫的比較general一點就是
如果看過後驗機率應該知道有一個分母項叫全機率，把所有z可能的概似函數乘上事前機率再相加
其中
Θ稱為高斯混合模型的參數集。
現在我們這個機率模式我把高斯分佈寫進去替換
這就是GMM的公式。
αk等於每個高斯分佈的界於0到1的權重，然後我們會限定權重和為1。
假設我們已經知道高斯混合模型的參數(Θ)了，此刻我們有一顆糖果x，根據它的後驗機率可以推論出來是來自第k個糖果袋子的機率，也可以解讀成這個糖果在全部袋子中，第k個袋子將負責多少比例的機率
此時wk(x)具有一個特性，全部K個糖果袋子的機率和是1
GMM概似函數估計
這邊會延續糖果的例子。
假設我們抽了n個糖果，所是事件集合是{x1,x2,…,xn}，我們要用這些糖果來反推論參數，分別是
聽起來就很困難對吧，從抽出來的糖果要去推這麼多東西，EM是視乎是一個有效的估計方法。
這邊將我們抽了n個糖果的概似函數寫出來，然後取對數：
EM是一種不斷迭代的算法，所以參數會不斷的更新，這邊假設
Jensen’s inequality
所以
因為已經在算t+1次，所以第t次的參數Θ(t)固定時，可視為一個常數C不重要可以刪除。
我們定義一個函數q
上述式子可以簡化成
所以式子右邊那一串(三項相加)等於ln(L(Θ(t+1)))的下界
原本目的是希望t+1次的對數概似函數(ln(L(Θ(t+1))))最大化，但因為很困難，所以我們去最大化ln(L(Θ(t+1)))的下界會比較容義一些，因此最大化q(Θ(t),Θ(t+1))會使得ln(L(Θ(t+1)))變大。
GMM-EM
GMM-EM演算法流程:
假設給定樣本集合{x1,x2,…,xn}
1. 初始化參數
設定K個數，t(第t次計算)設定為0
2. E-step:
假設所有參數(Θ(t))已知，計算
3. M-step:
利用MLE去估計q(Θ(t),Θ(t+1))的參數Θ(t+1)
參數估計出來為:
4. 重複2~3，直到滿足收斂條件(參數收斂或是概似函數收斂)
GMM-EM詳細推導
整理一下GMM-EM
E-step:
使用(所以參數固定)
然後
M-step:
在M-step要估計的參數是什麼?
分別是
所以我們將M-step最佳化拆成兩項來看
我們先解
因為我們有限制K個糖果盒子的權重和等於1 (前面有提到)
因此q1最佳化問題為
用 Lagrange函數來解
對 Lagrange函數作偏微分找解
對上式子將所有的高斯分佈(k=1,2,…,K)都相加起來
所以就找到 αk(t+1)的解了。
再來我們解高斯機率密度函數參數(平均項量和共變異數矩陣)
從q2著手
所以我們要對q2作偏微分找參數解
此刻我們再對q2偏微分等於0求解即可求得共變異數矩陣的最佳解:
我們先對q2對平均向量做偏微分求解，即可求得平均向量的最佳解:
再來要找共變異數矩陣的解，但在那之前，我們先來個回憶一下線性代數，因為共變異數矩陣的求解需要額外的技巧
有了上面馬式距離用trace調整的方法後，我們將q2公式調整一下:
此刻我們再對q2偏微分等於0求解即可求得共變異數矩陣的最佳解:
結束@@
打這篇的心得是會推公式外加打公式，弄到眼睛脫窗。
基本上一堆公式和數學會弄到你不要不要的，如果對推論沒有興趣的，請直接看子章節「GMM-EM演算法流程」即可；對推導有興趣的可以詳讀，我打得很細。
