EM算法

這篇文章僅僅隻是對 這篇部落格 的總結整理，僅供自己學習之用。可能很多人會疑惑，自己轉載就行了，為啥老是自己寫。我覺得，不管什麼東西，隻有自己咀嚼過一遍，才算真的是領悟了。

1、最大似然

假設我們需要調查學校中男女生的身高分布，因為一個個的去調查費時費力，是以我們需要采用抽樣的方法。假設随機抽取了100名男生和100名女生，規則是：男生在左邊，女生在右邊。然後先統計這100名男生的身高，假設他們的身高服從正态分布，但是這個分布的均值

和方差

我們不知道，是以我們需要求這兩個參數，記作

。

用數學的語言描述：在學校那麼多男生的身高中，我們獨立的按照機率密度(高斯分布

的形式)

抽取了100個身高，組成樣本集

，我們想通過樣本集

估計未知參數

，而

。抽到的樣本集為

，其中

表示抽到的第

個人的身高，這裡

由于所有男生的身高服從高斯分布

，那麼我抽到A的機率為

，抽到B的機率為

，因為抽到每個人各自都是獨立的，是以同時抽到A和B的機率為他們的乘積。是以在分布

的總體樣本抽到100個樣本的機率為樣本集

中所有樣本的聯合機率：

.

這個函數說明了，在不同的參數

的取值下，得到這個樣本集

的可能性，是以稱參數

相對于樣本集

的似然函數（likehood function）。記為

在學校中，我抽到100個男生，他們的機率是似然函數

，我們需要找到一個參數

使得似然函數最大。記為：

一般便于運算，我們将似然函數

取對數，将連乘變成連加：

求最大化，然後就成立一個求導使導數為0的過程，不在贅述。是以說，最大似然估計是已經知道了結果，然後尋求使該結果出現的可能性最大的條件，以此作為估計值。

2、EM算法

針對上面的例子，我們用似然函數求的男生的參數

，對于女生也同樣求解。但是如果例子并沒有那麼簡單，100名男生和100名女生同在一個黑屋裡，你從200個人裡面随便指一個，我并不知道到底是男生還是女生。也就是說，你不知道抽取的那200個人裡面的每一個人到底是從男生分布還是女生分布中取的。這個時候，對于每一個樣本，就有兩個東西需要猜測了。一是這個人是男是女？二是男生和女生對應的身高的高斯分布的參數是多少？。

在上面的例子中，如果沒有第一個問題，那麼似然函數輕松解決。但是現在有第一個問題，我們沒法分析高斯分布的參數。二隻有我們對這兩個分布參數做了準确的估計，才知道哪些人屬于第一個分布，那些人屬于第二個分布。這就陷入了一個死循環。解決的方法是先對分布參數賦一個随機值，然後算出是男女的機率，然後通過男女的機率算分布參數，直到收斂。

EM的意思是“Expectation Maximization”，在我們上面這個問題裡面，我們是先随便猜一下男生（身高）的正态分布的參數：如均值和方差是多少。例如男生的均值是1米7，方差是0.1米（當然了，剛開始肯定沒那麼準），然後計算出每個人更可能屬于第一個還是第二個正态分布中的（例如，這個人的身高是1米8，那很明顯，他最大可能屬于男生的那個分布），這個是屬于Expectation一步。有了每個人的歸屬，或者說我們已經大概地按上面的方法将這200個人分為男生和女生兩部分，我們就可以根據之前說的最大似然那樣，通過這些被大概分為男生的n個人來重新估計第一個分布的參數，女生的那個分布同樣方法重新估計。這個是Maximization。然後，當我們更新了這兩個分布的時候，每一個屬于這兩個分布的機率又變了，那麼我們就再需要調整E步……如此往複，直到參數基本不再發生變化為止。

這裡把每個人（樣本）的完整描述看做是三元組

，其中，

是第i個樣本的觀測值，也就是對應的這個人的身高，是可以觀測到的值。

和

表示男生和女生這兩個高斯分布中哪個被用來産生值

，就是說這兩個值标記這個人到底是男生還是女生（的身高分布産生的）。這兩個值我們是不知道的，是隐含變量。确切的說，

在

由第

個高斯分布産生時值為1，否則為0 。例如一個樣本的觀測值為1.8，然後他來自男生的那個高斯分布，那麼我們可以将這個樣本表示為{1.8, 1, 0}。如果

的值已知，也就是說每個人我已經标記為男生或者女生了，那麼我們就可以利用上面說的最大似然算法來估計他們各自高斯分布的參數。但是它們未知，是以我們隻能用EM算法。

3、EM算法推導

假設我們有一個樣本集

，包含

個獨立樣本。但是每個樣本

對應的類别

是未知的，即隐含變量。我們需要估計機率模型

的參數

，但是裡面有隐含變量

，不能用極大似然，如果

知道了，那麼很容易求解。

對于參數估計，本質上還是想獲得一個使似然函數最大化的那個參數

，唯一不同的是似然函數式多了隐變量

。我們的目标是找到合适的

使得

最大，公式如下：

首先，我們想到是求偏導，但是很複雜，别想了。是以可以通過第（2）步變形，最後得到一個不等式，将和的對數變成對數的和。此變換是通過Jensen不等式來的。

Jensen不等式：

設

是定義域為實數的函數，如果對于所有的實數

，

的二次導數大于等于0，那麼

是凸函數。當

是向量，如果七hessian矩陣H是半正定的，那麼

是凸函數。如果隻大于0，不等于0，那麼稱

是嚴格凸函數。

Jensen不等式表述如下：

如果

是凸函數，

是随機變量，那麼：

。特别地，如果

是嚴格凸函數，當且僅當

是常量時，上式取等号。如圖所示：

在圖中，實線

是随機變量，有0.5機率是a，有0.5的機率是b（就像擲硬币一樣）。

的期望是

的中值了，圖中可以看到

成立。

當

是（嚴格）凹函數，當且進度

是（嚴格）凸函數。

Jensen不等式應用于凹函數時，不等号方向反向。

回到公式（2）,因為

為凹函數（其二次導數為

）。

（2）式中，

的期望，（考慮到

是

的函數，則

），又

，是以就可以得到公式（3）的不等式了：

到這裡，式（3）就可以很容易的求導，但是式（2）和式（3）是不等式，式（3）的最大值不是式(2)的最大值，而我們需要式（2）的最大值。

解決方法是，上面式（2）和式（3）不等式可以寫成：似然函數

，那麼我們可以通過不斷的最大化這個下界

，來使得

不斷提高，最終達到它的最大值。

上圖中，我們固定

，調整

使下界

上升至與

在此點

處相等（綠色曲線到藍色曲線），然後固定

使得下界

達到最大值（

到

），然後在固定

.....知道收斂到似然函數

的最大值處的

。兩個問題：什麼時候下界

與

處相等？為什麼一定會收斂？

首先第一個問題，在Jensen不等式中說到，當自變量

是常數的時候，等式成立。而在這裡，即：

再推導下，由于

（因為

是随機變量

的機率密度函數），則可以得到：分子的和等于

（分子分母都對所有

求和：多個等式分子分母相加不變，這個認為每個樣例的兩個機率比值都是

），則：

我們推出了在固定參數

後，使下界拉升的

的計算公式就是後驗機率，解決了

如何選擇的問題。這一步就是

步，建立

的下界。接下來的

步，就是在給定

後，調整

，去極大化

的下界

（在固定

後，下界還可以調整的更大）。那麼一般的EM算法的步驟如下：

4、EM算法的應用

EM算法有很多的應用，最廣泛的就是GMM混合高斯模型、聚類、HMM等等，自己去搜吧。。。

最後，感謝這些大牛将這麼好的文章po到網上。