學習機器學習的童鞋對於EM演算法應該都不陌生。它被稱為「上帝的演算法」——極大期望演算法。

對於有些數據來說，它可能是不完全的，比如拋兩次硬幣，第一次的結果會影響第二次的選擇，但是我們只有最後結果的數據，而沒有第一次的。這就是所謂的隱藏變數。

EM演算法處理的問題是什麼？

直接給出觀測隨機變數的數據了，

但是這些觀測的數據依賴於一些隱藏的變數。最終的問題就是出現這樣的觀測隨機變數的數據的概率是多少？

所以我們的目的是：設置你不知道的那些參數，讓這個「在我們手裡的樣本」的出現概率最大。

#你隨機抽來的樣本是所有事件中概率最大的，這樣才合情合理。

演算法分為兩步：E為求期望，M為求極大。

下面就說一下市面上的兩種理解：

「感性」角度：

代表文章（個人最喜歡）：如何感性地理解EM演算法？

簡單的說：

1.給未知參數一個初始值，
（未知參數：被你抽出來的樣本（觀測的數據）服從的分佈裡面的參數或者簡單問題裡面的概率p）
2.用這個初始參數去求隱藏隨機變數的可能值
（硬幣問題：選最可能的，也就是概率最大的第一次結果，更嚴格的是其求期望）
（聚類問題就是它在哪個類別裏）
3.根據剛剛求出的隱藏隨機變數，重新設定更合理的參數。
（硬幣問題：每個硬幣出現正面的概率因為第一次的結果改變而改變，什麼概率能讓隱藏+觀測的結果最可能出現）
（聚類問題：上一步我們把每個數據分了類別，那麼用每個類別現在的數據，更新他的分佈函數裏的參數）
4.用參數去求隱藏隨機變數的可能值（就是第二步）
迭代。。。。3（M），4（E）
5.直到參數穩定下來，變化<=eps。

求極大肯定是求似然函數的極大了，而且一般都是對數似然。我們一般解決模型參數求解問題，都是在給定數據的情況下，求解使得似然函數最大的參數的取值。用公式表示就是：

讓觀測數據X「出現的可能性」成為最大的θ值。

通常的做法是對似然函數求偏導，然後令偏導等於零，參數取得的數值就是近似最優值。但是，有些含有隱變數的模型沒辦法直接進行似然函數的偏導。

那就假設已經知道隱變數的值，然後將似然函數簡化進行下一步的求偏導。

隱變數的值怎麼來？這就是所謂的求期望。（E步驟）

將隱變數的期望代入到經過隱變數改寫的對數似然函數中，就可以按照通常的極大似然估計求解參數了（M步驟）

這種理性角度的好處是由一般的極大似然估計自然地引入到EM方法，比較容易理解；但是缺點是一般很難寫出引入隱變數的似然函數的改寫。

然後就有了很多你看著：哇，真好理解的文章。

氮素，它們都沒有公式推導，然後就只是理解了而已。寫不出來公式還是傻乎乎的。

理性角度：

代表文章（個人喜歡）：你真的瞭解EM演算法嗎？

推了一堆公式，耐著性子自己推好，還沒來得及散花，我就突然思考了一個問題：我是誰？我在哪？我在幹什麼？

推是推了，好像也會用了，但是怎麼和我感性的理解聯繫不起來？(╯‵□′)╯︵┻━┻

但是你還是要推，現在默認你看過了推導過程。

有一個概念叫做「Q函數」，還有一個東西叫做：「EM演算法是通過不斷求解『下界的極大化』逼近求解『對數似然函數的極大化』。」大概你還看過這個圖：

這就是gt作為下屆函數帶著L（θ），即最大似然函數走向人生巔峯的故事。（局部人生巔峯）

那麼，Q函數是誰？Q函數從哪來？EM演算法是怎麼不斷求解下界的極大化呢？

假設在第i次迭代後θ的估計值是 。我們希望新估計值 能使L(θ)增加，即：L(θ)>L( )

通過迭代，我們求到極大的L（θ）

那麼我們考慮兩者差值：

利用Jensen不等式（對數函數的E[f(x)]<=f(E[x])）

得到其下界B( , )。《統計學習方法》中有推導過程，或者NLP -- 圖模型（零）：EM演算法簡述及簡單示例（三硬幣模型）

由上面的藍綠圖，gt就是L的下界函數。那麼不斷地找B(..)的極大值，就可以不斷地得到L的更大值。

在使B(...)達到極大的過程中，省去對θ的極大化而言是常數的項，剩下的部分，我們給它起了一個名字，就叫做：Q函數。

從形式上看，Q函數是未觀測數據的條件概率分佈的期望。

條件期望將期望用於條件概率。我們知道，條件概率是事件B條件下， A的概率，即P(A|B)。條件概率只不過是在一個縮小了的樣本空間B上，重新計算A的概率。

一個隨機變數的期望為一個數值。

但一個條件分佈的期望，比如E(X|Y=y)，會隨著隨機變數Y的變化而變化。所以，條件期望是隨機變數Y的函數。對於離散隨機變數：

Q函數是「完全數據的對數似然函數」關於在「給定觀測數據和當前參數」下對「未觀測數據」的條件概率分佈的期望.

loop

E-step：求Q函數（即隱變數的條件概率分佈的期望，是個關於θ的函數）
M-step：求使Q函數極大的當前參數的取值；(對θ分別求導，分別=0的值為更新後的參數值）

end

兩種理解的聯繫：

在使用Jensen不等式的時候，需要假設隱變數服從某種形式的概率分佈，纔可以將推導過程的一部分看成是期望的表達形式從而應用Jensen不等式。這個分佈其實就是：已知觀測數據（數據x）的隱變數（隨機變數y）的後驗概率分佈.

先驗概率：對某個隨機變數y的概率的預先估計。

（如果是離散型隨機變數就是預先估計的它的概率分佈，若是連續型隨機變數則是預先估計的它的概率密度函數。）後驗概率：當我們觀察到了數據x之後，然後得到的隨機變數y的概率的估計。

離散樣本為例扒一扒Q函數：

用當前迭代出來的θ值和觀測值算出隱藏值分別為*的概率，這一步就是後驗概率。

隱變數為*的後驗概率乘上隱變數為*時的似然函數，加和，這一步就是後驗概率的期望。

然後就是Q函數計算的最後一步了，由於對「隱變數為*的概率乘上隱變數為*時的似然函數」求和是一個樣本（一個觀測值）的，所以我們要把所有樣本的求和。

綜上，由於求Q函數時候，我們不知不覺中，求出了隱變數的後驗概率的期望。因此，這就可以解釋為什麼EM演算法的感性理解角度的E步驟是求隱變數的期望了。

ps:EM演算法解決某個具體問題的時候，我們會發現M步驟極大化的居然是完全數據的對數似然函數。

這是因為，Q函數雖然是完全數據的對數似然函數的某種期望，但是求這個期望的過程有時其實就是將隱變數的後驗概率的期望代入就可以了。

推薦閱讀：