Learn R | EM Algorithm of Data Mining（一）

前言

之前，在貝葉斯決策論（Bayesian decision theory）的概率框架下，我們學習了樸素貝葉斯分類器（Naive Bayes classifier），該演算法基於「屬性條件獨立性假設」，在所有相關概率都已知的情況下（即訓練樣本是「完整無缺」的），對樣本採取最優的類別標記（具體內容詳見Learn R | Naive Bayes of Data Mining）。

但是，在現實生活中，我們往往會遇到「不完整」的數據，這個時候使用傳統的貝葉斯分類器已然不可能（部分屬性的概率無法通過計算得到）。為此，我們學習一種新的演算法：期望最大演算法（Expectation Maximization Algorithm EM）。這是一種迭代演算法，目的在於從不完整或有數據丟失的數據集（存在隱含變數）中求解概率模型參數的最大似然估計。

我相信任何深入接觸與學習過EM演算法的人都不得不承認：它真的是一個既簡單，又複雜的演算法。簡單在於該演算法背後所蘊含的基本思想，僅需要兩個步驟（E和M）就可以實現強大的功能；複雜在於龐大而又繁雜的數學推理和概率公式的運用（如果想要深入的掌握，這部分是肯定躲不過去的）。

接下來，我們從基礎知識最大似然估計出發，依次學習掌握EM演算法的基本思想、數學推導及演算法的R實現。

一、最大似然估計(Maximum Likelihood Estimate)

1. 探尋校園中的身高分布

我們從一個實際生活中的例子引入對最大似然估計的學習（例子引自博客從最大似然到EM演算法淺解）

假設需要調查一個學校中男生和女生各自的身高分布，這種情況下一個一個的去收集數據顯然是不現實的，因此我們採取了隨機抽樣的方法，在校園裡隨機選取了100個男生和100個女生，共200個人。接著，男生站左邊，女生站右邊。這樣我們就很容易統計抽樣得到的100個男生或女生的身高。以男生為例，假設他們的身高都是服從高斯分布的，但是這個分布的均值和方差目前還不知道，而這兩個參數就是我們要估計的。記作。

用數學的語言來表述就是：在學校眾多的男生中，我們獨立地按照概率密度抽取100了個樣本，組成樣本集，目的在於通過樣本集來估計出未知參數。

由於每個樣本都是隨機獨立地抽取的，換句話說這100個男生中的任何一個人，從我們自己的角度來看，他們之間是沒有關係的。那麼，從學校那麼多男生中為什麼就恰好抽到了這100個人呢？抽到這100個人的概率是多少呢？

因為這些男生的身高是服從同一個高斯分布的。那麼我抽到男生（的身高）的概率就可以定義為，抽到男生的概率就可以定義為，因為他們之間各自是獨立的，所以很明顯，同時抽到男生和男生的概率為。同理，同時抽到這100個男生的概率就是他們各自概率的乘積了。用數學的語言來表述就是：從分布是的總體樣本中抽取到這100個樣本的概率，也就是在樣本集中各個樣本的聯合概率。

具體公式表示為：(為模型參數，即)

這個公式反映了，當概率密度函數的參數是時，得到樣本的概率。由於已知（我們已經通過抽樣得到100名男生的身高數據了）而未知，因此上面的公式只有是未知數，所以它是關於的函數。這個函數反映的是在參數的不同取值下，取得當前這個樣本集的可能性，因此稱為參數相對於樣本集的似然函數（likelihood function），記為。

2. 似然函數詳解

我們彷彿在最大似然估計里越陷越深了，怎麼又冒出一個似然函數的概念呢？及時回顧一下我們的目的，我們需要在已經抽到這一組樣本的條件下，估計參數的值。那麼值的確定和似然函數有著怎樣的聯繫？接下來通過下面的一個例子，來直觀的了解「似然」這個概念。

假設某位同學與一位獵人一起外出打獵，一隻野兔從前方竄過。只聽一聲槍響，野兔應聲到下，如果要我們推測，這一發命中的子彈是誰打的？大部分人就會想，只發一槍便打中，由於獵人命中的概率一般大於這位同學命中的概率，看來這一槍應該是獵人射中的。

這種帶有主觀色彩的可能性最大的推斷就體現了最大似然法的基本思想。再說回到男生身高那個案例。在學校那麼多的男生中，我們一抽就抽到這100個男生，而不是其他人，那是不是就表示在整個學校中，這100個人（的身高）出現的概率最大呢？那麼這個概率怎麼表示？顯然，就是上面剛剛提到的那個似然函數。

這樣，我們就找到了似然函數和最終目的之間的聯繫：找出一個參數值，其對應的似然函數值最大，也就是說抽到這100個男生（的身高）概率最大。這個叫做的最大似然估計量，記為：。為了便於分析，我們將定義為對數似然函數。

表示為：

接下來，我們就需要求得值，根據似然函數及基本的函數導數知識，首先對似然函數求導，函數極大值處所對應的就是我們所需要的值（當然前提是函數連續可微）。如果是包含多個參數的向量（例如），那麼就需要求對所有參數的偏導數，建立方程組，方程組的解就是似然函數的極值點，與此同時也就得到各參數了。

3. 最大似然估計小結

在大多數情況下，我們是根據已知條件來推算結果。而最大似然估計恰恰相反，它是一個反推的過程：我們已經知道了結果，然後尋求使該結果出現的可能性最大的條件，並以此條件作為估計值。

值得注意的是，在最大似然估計中，我們是假定了隨機誤差需要服從正態分布，這也提示我們，對於最大似然估計，我們的結果是對我們對於隨機變數所假設的概率分布有依賴性的，因此也就要求我們要有一定的先驗知識。

最後，簡單總結一下最大似然估計的一般步驟：

1. 根據概率密度函數寫出似然函數

2. 對似然函數取對數，並整理

3. 對對數似然函數求解極（最）大值（求導計算，多參數時求偏導聯立方程組）

二、EM演算法的基本思想

現在，我們對最大似然估計有了一個基本的把握，再說回到校園中身高估計的這個例子中，之前我們隨機選取了100名男生和100名女生後，男生站左邊，女生站右邊，分別使用最大似然估計就可以得到各自的身高分布了。但要是不這麼做呢？

此時，兩百個人混在一起，如果隨機的從裡面提取一個人的身高（我們這裡假設只能獲取身高的數據，而不受性別等特徵的影響），我們都無法確定這個人（的身高）是男生（的身高）還是女生（的身高）。也就是說，現在不清楚抽取的那到底是來自男生的那個身高分布，還是女生的那個身高分布（隨機抽取的每一個樣本都不知道是從哪個分布抽取的）。

那麼對於每一個樣本而言，以下兩個方面的信息就是我們需要獲取到的：

1. 這個人是男還是女？

2. 男生和女生對應的身高的高斯分布的參數是多少？

只有當我們知道了哪些人屬於同一個高斯分布的時候，我們才能夠對這個分布的參數作出靠譜的預測，但現在兩種高斯分布的人混在一塊了，我們又不知道哪些人屬於第一個高斯分布，哪些屬於第二個，所以就沒法估計這兩個分布的參數。反過來，只有當我們對這兩個分布的參數作出了準確的估計的時候，才能知道到底哪些人屬於第一個分布，那些人屬於第二個分布。

每一方都需要依賴對方所提供的信息做出進一步的判斷：要想獲知分布的參數需要知道某一個樣本是男是女，而是男是女的分辨又需要總體分布的參數支持，這個過程就是一個你依賴我，我依賴你的過程。總是這麼僵持著終歸不是辦法， 總得有一方打破僵局，說，不管了，我先隨便整一個值出來，看你怎麼變，然後我再根據你的變化調整我的變化，然後如此迭代著不斷互相推導，最終就會收斂到一個解。這就是EM演算法的基本思想了。

舉一個更為直觀的例子來闡述演算法思想：

小時候，老媽給一大袋糖果給你，叫你和姐姐等分，然後你懶得去點糖果的個數，所以你也就不知道每個人到底該分多少個。我們一般怎麼做呢？先把一袋糖果目測的分為兩袋，然後把兩袋糖果拿在左右手，看哪個重，如果右手重，那很明顯右手這袋糖果多了，然後你再在右手這袋糖果中抓一把放到左手這袋，然後再感受下哪個重，然後再從重的那袋抓一小把放進輕的那一袋，繼續下去，直到感覺兩袋糖果差不多相等了為止。

這就是所謂的EM演算法，假設我們想估計知道和兩個參數，在開始狀態下二者都是未知的，但如果知道了的信息就可以得到的信息，反過來知道了也就得到了。可以考慮首先賦予某一值，以此得到的估計值，然後從的當前值出發，重新估計的取值，這個過程一直持續，直到收斂為止。

再返回到身高分布這個例子中，我們先隨便猜一下男生（身高）的正態分布的參數：例如均值是1米7，方差是0.1米（一般剛開始肯定沒那麼准），然後計算出每個人更可能屬於第一個還是第二個正態分布（例如一個人的身高是1米8，那很明顯，他最大可能屬於男生的那個分布）。EM的全稱是Expectation Maximization，這個就屬於Expectation一步。有了每個人的歸屬，我們大概地按上面的初始預估參數將這200個人進行了男女生的分類。接著就可以根據之前說的最大似然估計那樣，通過這些被大概分為男生的個人來重新估計第一個分布的參數，女生的那個分布同樣方法重新估計，這個是Maximization。然後，當我們更新了這兩個分布的時候，每一個屬於這兩個分布的概率又變了，那麼我們就再需要調整步……如此往複，直到參數基本不再發生變化為止。

至此，我們就對EM演算法有了一個直觀上的理解，接下來進入最為重要的核心環節：EM演算法的數學推導。

未完待續

References：

1. The EM algorithm - Andrew Ng

2. 最大似然估計(Maximum likelihood estimation)

3. 從最大似然到EM演算法淺解 - zouxy09 - CSDN.NET

4. 最大似然估計 - wikipedia

5. 最大期望演算法 - Wikipedia

6. 機器學習中的EM演算法詳解及R語言實例

7. EM-最大期望演算法 - 劉帝偉

推薦閱讀：