簡介

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

1. 隨機初始化模型參數(shù)\thetaθ的初值\theta^{0}

2. 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算法應(yīng)用

如果我們從算法思想的角度來思考EM算法揪利，我們可以發(fā)現(xiàn)我們的算法里已知的是觀察數(shù)據(jù)，未知的是隱含數(shù)據(jù)和模型參數(shù)狠持，在E步疟位，我們所做的事情是固定模型參數(shù)的值，優(yōu)化隱含數(shù)據(jù)的分布工坊，而在M步献汗，我們所做的事情是固定隱含數(shù)據(jù)分布敢订，優(yōu)化模型參數(shù)的值王污。EM的應(yīng)用包括:
- 支持向量機的SMO算法
- 混合高斯模型
- K-means
- 隱馬爾可夫模型

參考資料：

• 參考資料1：如何通俗理解EM算法

• 參考資料2：EM算法原理總結(jié)