簡介
EM算法也稱期望最大化（Expectation-Maximum,簡稱EM）算法，其最主要的思想有兩步：
- E：求期望，
- M: 求極大
EM算法采用的是啟發(fā)式的迭代方法，就是當我們無法直接求出模型的參數(shù)分布的時候，我們先猜想隱含的數(shù)據(jù)，根據(jù)猜測的隱含數(shù)據(jù)和觀察數(shù)據(jù)，求對數(shù)似然的最大值。然后根據(jù)當前模型的參數(shù)，繼續(xù)猜測隱含數(shù)據(jù)，然后再求極大化似然函數(shù)，以此類推迭代下去，直到模型參數(shù)的分布基本不變化，那么當前模型的參數(shù)，認為是得到極大似然的最好模型參數(shù)。
其實K-Means就是這種思想。求質(zhì)心的過程其實就是E，計算每個樣本最近的質(zhì)心，就是M步。
數(shù)學推導
輸入：觀測數(shù)據(jù)X，模型參數(shù)為θ。極大化模型分布的對數(shù)似然為：
對于得到的觀察數(shù)據(jù)有未觀察到的隱含數(shù)據(jù)Z，極大化模型分布的對數(shù)似然可以變成：
通過Jensen不等式：
極大化模型分布的對數(shù)似然可以變成：
其中是一個未知的新的分布。
或者說由于對數(shù)函數(shù)是凹函數(shù)，所以有:
f(E(x))≥E(f(x))如果f(x)是凹函數(shù)
此時如果要滿足Jensen不等式的等號，則有：
P(x(i)，z(i);θ)Qi(z(i))=c,c為常數(shù)
由于Qi(z(i))是一個分布，所以滿足：
∑zQi(z(i))=1
從上面兩式，我們可以得到：
Qi(z(i))=P(x(i)，z(i);θ)∑zP(x(i)，z(i);θ)=P(x(i)，z(i);θ)P(x(i);θ)=P(z(i)|x(i);θ))
如果Qi(z(i))=P(z(i)|x(i);θ)), 則第(2)式是我們的包含隱藏數(shù)據(jù)的對數(shù)似然的一個下界。如果我們能極大化這個下界，則也在嘗試極大化我們的對數(shù)似然。即我們需要最大化下式：
argmaxθ∑i=1m∑z(i)Qi(z(i))logP(x(i)，z(i);θ)Qi(z(i))
去掉上式中為常數(shù)的部分，則我們需要極大化的對數(shù)似然下界為：
argmaxθ∑i=1m∑z(i)Qi(z(i))logP(x(i),z(i);θ)
上式也就是我們的EM算法的M步，那E步呢？注意到上式中Qi(z(i))是一個分布，因此∑z(i)Qi(z(i))logP(x(i)，z(i);θ)可以理解為logP(x(i)，z(i);θ)基于條件概率分布Qi(z(i))的期望。
至此，我們理解了EM算法中E步和M步的具體數(shù)學含義。
EM算法流程
輸入: 觀察數(shù)據(jù)x=\left(x^{(1)}, x^{(2)}, \ldots x^{(m)}\right) ,聯(lián)合分布p(x, z | \theta) ,條件分布p(z | x, \theta) ,極大迭代次數(shù)J
隨機初始化模型參數(shù)\thetaθ的初值\theta^{0}
-
from j from 1 to J:
- E步：計算聯(lián)合分布的條件概率期望:
\left.Q_{i}\left(z{(i)}\right):=P\left(z{(i)} | x^{(i)}, \quad \theta\right)\right)- M步：極大化L(\theta)L(θ),得到\thetaθ:
\theta:=\arg \max {\theta} \sum{i=1}^{m} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log P\left(x^{(i)}, z^{(i)} | \theta\right)
- E,M步驟直到\thetaθ收斂。
- 輸出：模型參數(shù)\thetaθ
EM算法收斂性的思考
- 具體的推導參考這個吧 https://www.cnblogs.com/pinard/p/6912636.html
- EM 算法可以保證收斂到一個穩(wěn)定點，但是卻不能保證收斂到全局的極大值點，因此它是局部最優(yōu)的算法,如果我們的優(yōu)化目標是凸的,則EM算法可以保證收斂到全局極大值，這點和梯度下降法這樣的迭代算法相同。
EM算法應用
如果我們從算法思想的角度來思考EM算法，我們可以發(fā)現(xiàn)我們的算法里已知的是觀察數(shù)據(jù)，未知的是隱含數(shù)據(jù)和模型參數(shù)，在E步，我們所做的事情是固定模型參數(shù)的值，優(yōu)化隱含數(shù)據(jù)的分布，而在M步，我們所做的事情是固定隱含數(shù)據(jù)分布，優(yōu)化模型參數(shù)的值。EM的應用包括:
- 支持向量機的SMO算法
- 混合高斯模型
- K-means
- 隱馬爾可夫模型
參考資料：
參考資料1：如何通俗理解EM算法
參考資料2：EM算法原理總結
