一文詳盡系列之EM演算法
- 2019 年 11 月 27 日
- 筆記
EM 演算法，全稱 Expectation Maximization Algorithm。期望最大演算法是一種迭代演算法，用於含有隱變數（Hidden Variable）的概率參數模型的最大似然估計或極大後驗概率估計。
思想
EM 演算法的核心思想非常簡單，分為兩步：Expection-Step 和 Maximization-Step。E-Step 主要通過觀察數據和現有模型來估計參數，然後用這個估計的參數值來計算上述對數似然函數的期望值；而 M-Step 是尋找似然函數最大化時對應的參數。由於演算法會保證在每次迭代之後似然函數都會增加，所以函數最終會收斂。
舉例
我們舉兩個例子來直觀的感受下 EM 演算法。
2.1 例子 A
第一個例子我們將引用 Nature Biotech 的 EM tutorial 文章中的例子。
2.1.1 背景
假設有兩枚硬幣 A 和 B，他們的隨機拋擲的結果如下圖所示：
我們很容易估計出兩枚硬幣拋出正面的概率：
現在我們加入隱變數，抹去每輪投擲的硬幣標記：
|
Coin |
Statistics |
|---|---|
|
Coin * |
5 H, 5 T |
|
Coin * |
9 H, 1 T |
|
Coin * |
8 H, 2 T |
|
Coin * |
4 H, 6 T |
|
Coin * |
7 H, 3 T |
碰到這種情況，我們該如何估計 和 的值？
我們多了一個隱變數 ，代表每一輪所使用的硬幣，我們需要知道每一輪拋擲所使用的硬幣這樣才能估計 和 的值，但是估計隱變數 Z 我們又需要知道 和 的值，才能用極大似然估計法去估計出 Z。這就陷入了一個雞生蛋和蛋生雞的問題。
其解決方法就是先隨機初始化 和 ，然後用去估計 Z， 然後基於 Z 按照最大似然概率去估計新的 和 ，循環至收斂。
2.1.2 計算
隨機初始化 和
對於第一輪來說，如果是硬幣 A，得出的 5 正 5 反的概率為：；如果是硬幣 B，得出的 5 正 5 反的概率為：。我們可以算出使用是硬幣 A 和硬幣 B 的概率分別為：
|
No |
Coin A |
Coin B |
|---|---|---|
|
1 |
0.45 |
0.55 |
|
2 |
0.80 |
0.20 |
|
3 |
0.73 |
0.27 |
|
4 |
0.35 |
0.65 |
|
5 |
0.65 |
0.35 |
從期望的角度來看，對於第一輪拋擲，使用硬幣 A 的概率是 0.45，使用硬幣 B 的概率是 0.55。同理其他輪。這一步我們實際上是估計出了 Z 的概率分布，這部就是 E-Step。
結合硬幣 A 的概率和上一張投擲結果，我們利用期望可以求出硬幣 A 和硬幣 B 的貢獻。以第二輪硬幣 A 為例子，計算方式為：
於是我們可以得到：
|
No |
Coin A |
Coin B |
|---|---|---|
|
1 |
2.2 H, 2.2 T |
2.8 H, 2.8 T |
|
2 |
7.2 H, 0.8 T |
1.8 H, 0.2 T |
|
3 |
5.9 H, 1.5 T |
2.1 H, 0.5 T |
|
4 |
1.4 H, 2.1 T |
2.6 H, 3.9 T |
|
5 |
4.5 H, 1.9 T |
2.5 H, 1.1 T |
|
total |
21.3 H, 8.6 T |
11.7 H, 8.4 T |
然後用極大似然估計來估計新的 和 。
這步就對應了 M-Step，重新估計出了期望值。
如此反覆迭代，我們就可以算出最終的參數值。
上述講解對應下圖：
2.2 例子 B
如果說例子 A 需要計算你可能沒那麼直觀，那就舉更一個簡單的例子：
現在一個班裡有 50 個男生和 50 個女生，且男女生分開。我們假定男生的身高服從正態分布：，女生的身高則服從另一個正態分布： 。這時候我們可以用極大似然法（MLE），分別通過這 50 個男生和 50 個女生的樣本來估計這兩個正態分布的參數。
但現在我們讓情況複雜一點，就是這 50 個男生和 50 個女生混在一起了。我們擁有 100 個人的身高數據，卻不知道這 100 個人每一個是男生還是女生。
這時候情況就有點尷尬，因為通常來說，我們只有知道了精確的男女身高的正態分布參數我們才能知道每一個人更有可能是男生還是女生。但從另一方面去考量，我們只有知道了每個人是男生還是女生才能儘可能準確地估計男女各自身高的正態分布的參數。
這個時候有人就想到我們必須從某一點開始，並用迭代的辦法去解決這個問題：我們先設定男生身高和女生身高分布的幾個參數（初始值），然後根據這些參數去判斷每一個樣本（人）是男生還是女生，之後根據標註後的樣本再反過來重新估計參數。之後再多次重複這個過程，直至穩定。這個演算法也就是 EM 演算法。
推導
給定數據集，假設樣本間相互獨立，我們想要擬合模型 到數據的參數。根據分布我們可以得到如下似然函數：
第一步是對極大似然函數取對數，第二步是對每個樣本的每個可能的類別 z 求聯合概率分布之和。如果這個 z 是已知的數，那麼使用極大似然法會很容易。但如果 z 是隱變數，我們就需要用 EM 演算法來求。
事實上，隱變數估計問題也可以通過梯度下降等優化演算法，但事實由於求和項將隨著隱變數的數目以指數級上升，會給梯度計算帶來麻煩；而 EM 演算法則可看作一種非梯度優化方法。
對於每個樣本 i，我們用 表示樣本 i 隱含變數 z 的某種分布，且 滿足條件（）。
我們將上面的式子做以下變化：
上面式子中，第一步是求和每個樣本的所有可能的類別 z 的聯合概率密度函數，但是這一步直接求導非常困難，所以將其分母都乘以函數 ，轉換到第二步。從第二步到第三步是利用 Jensen 不等式。
我們來簡單證明下：
Jensen 不等式給出：如果 是凹函數，X 是隨機變數，則 ，當 嚴格是凹函數是，則 ，凸函數反之。當 時，即為常數時等式成立。
我們把第一步中的 函數看成一個整體，由於 的二階導數小於 0，所以原函數為凹函數。我們把 看成一個概率 ，把 看成 z 的函數 。根據期望公式有：
根據 Jensen 不等式的性質：
證明結束。
通過上面我們得到了： 的形式（z 為隱變數），那麼我們就可以通過不斷最大化 的下界來使得 不斷提高。下圖更加形象：
這張圖的意思就是：首先我們固定 ，調整 使下界 上升至與 在此點 處相等（綠色曲線到藍色曲線），然後固定 ，調整 使下界 達到最大值（ 到 ），然後再固定 ，調整 ，一直到收斂到似然函數 的最大值處的 。
也就是說，EM 演算法通過引入隱含變數，使用 MLE（極大似然估計）進行迭代求解參數。通常引入隱含變數後會有兩個參數，EM 演算法首先會固定其中的第一個參數，然後使用 MLE 計算第二個變數值；接著通過固定第二個變數，再使用 MLE 估測第一個變數值，依次迭代，直至收斂到局部最優解。
但是這裡有兩個問題：
- 什麼時候下界 與 相等？
- 為什麼一定會收斂？
首先第一個問題，當 時，即為常數時等式成立：
做個變換：
其中 ，所以可以推導出：
因此得到了：
至此我們推出了在固定參數下，使下界拉升的 的計算公式就是後驗概率，同時解決了 如何選擇的問題。這就是我們剛剛說的 EM 演算法中的 E-Step，目的是建立 的下界。接下來得到 M-Step 目的是在給定 後調整 ，從而極大化似然函數 的下界 。
對於第二個問題，為什麼一定會收斂？
這邊簡單說一下，因為每次 更新時（每次迭代時），都可以得到更大的似然函數，也就是說極大似然函數時單調遞增，那麼我們最終就會得到極大似然估計的最大值。
但是要注意，迭代一定會收斂，但不一定會收斂到真實的參數值，因為可能會陷入局部最優。所以 EM 演算法的結果很受初始值的影響。
另一種理解
坐標上升法（Coordinate ascent）：
途中直線為迭代優化路徑，因為每次只優化一個變數，所以可以看到它沒走一步都是平行與坐標軸的。
EM 演算法類似於坐標上升法，E 步：固定參數，優化 Q；M 步：固定 Q，優化參數。交替將極值推向最大。
應用
在高斯混合模型和 K-means 中有很大的用處。
參考
[1]《機器學習》周志華
[2] https://www.zhihu.com/question/27976634
[3] https://blog.csdn.net/zouxy09/article/details/8537620
[4] Do, C. B., & Batzoglou, S. (2008). What is the expectation maximization algorithm?. Nature biotechnology, 26(8), 897.
