最大期望算法 Expectation Maximization概念

在統計計算中，最大期望（EM，

Expectation–Maximization）算法是在機率（probabilistic）模型中尋找參數最大似然估計的算法，其中機率模型依賴于無法觀測的隐藏變量（Latent Variabl）。最大期望經常用在機器學習和計算機視覺的資料集聚（Data Clustering）領域。

可以有一些比較形象的比喻說法把這個算法講清楚。比如說食堂的大師傅炒了一份菜，要等分成兩份給兩個人吃，顯然沒有必要拿來天平一點一點的精确的去稱分量，最簡單的辦法是先随意的把菜分到兩個碗中，然後觀察是否一樣多，把比較多的那一份取出一點放到另一個碗中，這個過程一直疊代地執行下去，直到大家看不出兩個碗所容納的菜有什麼分量上的不同為止。EM算法就是這樣，假設我們估計知道A和B兩個參數，在開始狀态下二者都是未知的，并且知道了A的資訊就可以得到B的資訊，反過來知道了B也就得到了A。可以考慮首先賦予A某種初值，以此得到B的估計值，然後從B的目前值出發，重新估計A的取值，這個過程一直持續到收斂為止。

EM 算法是 Dempster，Laind，Rubin 于 1977 年提出的求參數極大似然估計的一種方法，它可以從非完整資料集中對參數進行 MLE 估計，是一種非常簡單實用的學習算法。這種方法可以廣泛地應用于處理缺損資料，割尾資料，帶有噪聲等所謂的不完全資料(incomplete data)。

假定集合Z = (X,Y)由觀測資料 X 和未觀測資料Y 組成，X 和Z = (X,Y)分别稱為不完整資料和完整資料。假設Z的聯合機率密度被參數化地定義為P(X,Y|Θ)，其中Θ表示要被估計的參數。Θ的最大似然估計是求不完整資料的對數依然函數L(X;Θ)的最大值而得到的：

L(Θ;X)= log p(X|Θ) = ∫log p(X,Y|Θ)dY ；

EM算法包括兩個步驟：由E步和M步組成，它是通過疊代地最大化完整資料的對數似然函數Lc(X;Θ)的期望來最大化不完整資料的對數似然函數，其中：

Lc(X;Θ) =log p(X,Y |Θ) ；

假設在算法第t次疊代後Θ獲得的估計記為Θ(t) ，則在(t+1)次疊代時，

E-步：計算完整資料的對數似然函數的期望，記為：

Q(Θ|Θ (t)) = E{Lc(Θ;Z)|X;Θ(t)}；

M-步：通過最大化Q(Θ|Θ(t) ) 來獲得新的Θ 。

通過交替使用這兩個步驟，EM算法逐漸改進模型的參數，使參數和訓練樣本的似然機率逐漸增大，最後終止于一個極大點。直覺地了解EM算法，它也可被看作為一個逐次逼近算法：事先并不知道模型的參數，可以随機的選擇一套參數或者事先粗略地給定某個初始參數λ0 ，确定出對應于這組參數的最可能的狀态，計算每個訓練樣本的可能結果的機率，在目前的狀态下再由樣本對參數修正，重新估計參數λ，并在新的參數下重新确定模型的狀态，這樣，通過多次的疊代，循環直至某個收斂條件滿足為止，就可以使得模型的參數逐漸逼近真實參數。

EM算法的主要目的是提供一個簡單的疊代算法計算後驗密度函數，它的最大優點是簡單和穩定，但容易陷入局部最優。