一：EM算法簡介

EM算法簡單來說就是一種迭代優化策略，由于它的計算方法中每一次迭代都分兩步，其中一個為求期望步（E步），另一個為求極大值步M步），所以算法被稱為EM算法（Expectation Maximization
Algorithm）。EM算法適用于求解那些含有隱變量的問題，也就是說你待求解的樣本中含有無法觀測到的記錄值。要學習EM算法，我們需要先了解兩個概念：極大似然估計和Jensen不等式。

二：極大似然估計

首先來了解一下極大似然估計。這個時候就需要小明友情客串一下了。假如小明今年剛考入大學，他在校園里閑逛，發現從身邊經過的每十個人里有八個都是女生，他就想說：妥了，我指定能找到女朋友！那為什么小明會產生“能找到女朋友”這樣的想法呢？其實這里就用到了極大似然估計的思想——根據觀測到的樣本結果推測使該結果出現的最大可能。也就是說，我們可以把極大似然看作一個反推，即根據結果推算使該結果出現的可能性最大的條件。
再舉一個例子：現在我們從學校為數不多的男生中隨機抽取100個男生，加入這些男生的身高服從同一個高斯分布：X~N（ u, ? ）。分別記錄他們的身高數據為X={x1,x2,x3,…,x100}，但是我們不知道他們身高服從的高斯模型的參數是多少，所以我們的目標就是求解參數：θ=[u, ?]T。在這里我們記抽到第i個男生身高的概率為𝑝(x𝑖|𝜃)，假設這100個男生的身高是獨立同分布的，也就是說我抽到第1個男生的身高對我抽到其他男生的身高是沒有影響的，那么抽到這100個男生的身高的概率就是抽到各個男生身高概率的乘積了（即𝑝(x1|𝜃)𝑝(x2|𝜃)····*𝑝(x100|𝜃)，我們把這個式子定義為似然函數L(𝜃),即L(𝜃)是一個概率累乘的形式。
我們再來想，全校那么多男生那么多的身高，為什么我偏偏就抽到了這100個身高呢？是不是可以理解成這100個身高在全校所有的男生身高中所占的比例是最大的，以至于我隨便一抽就抽到了它們呢。當然可以這樣理解了，所以我只要求這100個男生身高的概率乘積的最大值就好了，也就是說要求這個似然函數的最大值。求最大值避免不了要求倒數，對累乘的式子求導運算量大的難以想像，所以我們一般通過取對數把累乘變成累加的形式：

現在我們只需要對似然函數求導，令倒數為0，就可以求解得到𝜃的值了。好了，我們來回顧一下，極大似然函數就是一種反推的過程，已知了樣本滿足的分布（這里就是高斯分布）和樣本數據（這里是男生的身高數據），要根據這樣的結果反推使該結果出現的最大的可能（也就是求解一個最可能的參數𝜃來使我們抽到這樣的100個身高數據）。

三：EM算法引入

現在問題難度升級了，在這100個身高數據中不止有男生的身高，還有女生的身高，也就是說現在我們要新引入一個性別屬性，相當于多了一個變量Z（隱變量）,并且更糟糕的是，我們不知道哪些數據是男生的身高數據，哪些數據是女生的身高數據。假設男生和女生的身高分別服從各自的高斯分布，那么現在我們就要分別求解男生的身高服從的參數𝜃1和女生身高服從的參數𝜃2。如果我們想繼續使用上例中對似然函數求導的方法求解兩個𝜃值，就需要知道每一個人的身高屬于哪個性別屬性；而要想知道每一個身高屬于哪個性別，我們需要先有兩個性別各自的高斯分布模型，才能將各個身高對號入座，也就是要先知道男生身高和女生身高各自的參數𝜃。因此，這個時候就形成了一個相互依賴的矛盾局面。
為了打破這樣的矛盾局面，我們不妨先預測一個θ值出來，假設當前預測θ1 ，然后根據θ1的值對樣本進行分布，也就是將那些更符合θ1的身高數據分到男生（比如這里我們先估計θ1=[1.8,0.1]T，那么對于1.9這個身高很顯然更可能屬于θ1這個分布），余下的就是女生，那自然就可以根據余下的身高數據計算出θ2的值（E步）。根據E步的分布樣本重新估計θ的值（M步），如此循環迭代直到收斂。這就是EM算法的基本思想。
現在，我們的完全數據就包括觀測數據X和隱變量Z，即完全數據（X,Z)，（X，Z）的似然函數為P（X，Z|θ）。則似然函數變成了：
這里每個樣本對應的Z（i）是未知的，所以很難用極大似然估計求解；再加上log后面還有求和（因為需要分別考慮這個身高是男生的可能性和是女生的可能性），這就變的更難解了。這時候就需要EM算法了。

四：EM算法和Jensen不等式

先貼出EM算法求解的方法：

從（1）式到（2）式大家肯定就很費解了，對概率先除以Q(z)再乘以Q(z）是有什么意義嗎？再看從（2）式到（3）式就更疑惑了，為什么log函數一下子就跑到第二個求和符號里面去了？而且等號也變成了>=？這就要用到Jensen不等式來答疑解惑了。

f（x）是定義域為實數的函數，若對于全體實數x，f（x）`` >0，那么f（x）是凸函數，反之則為凹函數。若f是凸函數，有隨機變量X，那么E[f(X)] >= f(E[X]) ， 對于凹函數結論相反。對于下圖，我們不妨假設函數f(x),x為a和b的概率都是0.5，那么E(X)就等于0.5a+0.5b，即a，b的中值，E(X)的函數值如圖所示。E(f（X))就等于0.5f（a）+0.5f（b），即f（a）和f（b）的中值，如圖，顯然E[f(x)]>f[E(X)]。

對于凸函數，所有的x都有這樣的結論成立：函數值的期望>=期望的函數值。在這里似然函數是log，二階導小于0，所以有結論：函數值的期望<=期望的函數值。
說完Jensen不等式，我們回到EM算法的公式推導部分，在這里（2）式乘以的Q(Z)其實是關于z的分布函數（Q(z) = p(Z<=z)）,那么(p(x𝑖,𝑍;𝜃) )/𝑄 (𝑍 ) 就是一個數，Q(z）*(p(x𝑖,𝑍;𝜃) )/𝑄 (𝑍 ) 的累加和就是期望值，所以（2）式可以理解為是期望的函數值，（3）式就是函數的期望值，這個變換我們就不難理解了。
別忘記我們最初的目的是為了求θ值，即求（2）式的極大值，因為（2）式恒>=(3)式，所以只要求出（3）式的最大值，然后對（2）式和（3）式取等號就可以得到（2）式的最大值了。

也就是說我們通過取不同的θ值，來不斷優化上圖所示的下界，而L(θ)是恒大于下界的，當下界能取到最大時，L(θ)自然就是最大了。
那什么時候能夠取等號呢？在Jensen不等式中規定，只有當 (p(x𝑖,𝑍;𝜃) )/𝑄 (𝑍 ) 是一個常數值時等號成立，在這里我們不妨假定Y= (p(x𝑖,𝑍;𝜃) )/𝑄 (𝑍 ) ，那么當Y=C時（2）式和（3）式取等號。因為Q(Z)是z的分布函數，所以Q(Z)關于z求和是等于1的，結合分布函數的這個性質對Y做一個變形得到：
由上式可知，C其實就是p(xi,z|𝜃)對z所有的情況求和，相當于沒有了隱變量Z，只剩下p(x𝑖|𝜃)。（結合男生女生身高的例子，對于一個身高數據，把它是男生身高和是女生身高的兩種情況都考慮進去做一個加和，不就相當于沒有了性別屬性Z這個隱變量嗎）有了這個結論，我們再對Q(z)變形：

很顯然，Q(z)代表的就是在參數𝜃的情況下，第i個數據來自類別z的 概率。求出了Q（z），這其實也是E步需要做的事情。

EM算法的流程如下：

初始化分布參數𝜃。

E-step:根據參數𝜃計算每個樣本屬于Zi的概率。

M-step:根據計算的概率，求出含有𝜃的似然函數的下界并最大化它，得到新的𝜃

不斷的迭代更新下去直至收斂。

總結

以上是生活随笔為你收集整理的EM算法 --入门级详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。