人人都能看懂的EM算法推導(dǎo)
來源：深度學(xué)習(xí)初學(xué)者 本文約6800字，建議閱讀10分鐘
本文通過案例帶大家學(xué)習(xí)EM算法的推導(dǎo)。
1. 從極大似然到EM
1.1 極大似然
1.1.1 問題描述
假設(shè)我們需要調(diào)查我們學(xué)校學(xué)生的身高分布。我們先假設(shè)學(xué)校所有學(xué)生的身高服從正態(tài)分布 
。(注意：極大似然估計的前提一定是要假設(shè)數(shù)據(jù)總體的分布，如果不知道數(shù)據(jù)分布，是無法使用極大似然估計的)，這個分布的均值 
和方差 
未知，如果我們估計出這兩個參數(shù)，那我們就得到了最終的結(jié)果。那么怎樣估計這兩個參數(shù)呢？
學(xué)校的學(xué)生這么多，我們不可能挨個統(tǒng)計吧？這時候我們需要用到概率統(tǒng)計的思想，也就是抽樣，根據(jù)樣本估算總體。假設(shè)我們隨機抽到了 200 個人（也就是 200 個身高的樣本數(shù)據(jù)，為了方便表示，下面“人”的意思就是對應(yīng)的身高）。然后統(tǒng)計抽樣這 200 個人的身高。根據(jù)這 200 個人的身高估計均值 和方差 。
用數(shù)學(xué)的語言來說就是：為了統(tǒng)計學(xué)校學(xué)生的身高分布，我們獨立地按照概率密度 
抽取了 200 個（身高），組成樣本集 
(其中
表示抽到的第 
個人的身高，這里 N 就是 200，表示樣本個數(shù))，我們想通過樣本集 X 來估計出總體的未知參數(shù) 
。這里概率密度 服從高斯分布 ，其中的未知參數(shù)是 
。
那么問題來了怎樣估算參數(shù) 呢？
1.1.2 估計參數(shù)
我們先回答幾個小問題：
問題一：抽到這 200 個人的概率是多少呢？
由于每個樣本都是獨立地從 中抽取的，換句話說這 200 個學(xué)生隨便捉的，他們之間是沒有關(guān)系的，即他們之間是相互獨立的。假如抽到學(xué)生 A（的身高）的概率是 
，抽到學(xué)生B的概率是 
，那么同時抽到男生 A 和男生 B 的概率是 
，同理，我同時抽到這 200 個學(xué)生的概率就是他們各自概率的乘積了，即為他們的聯(lián)合概率，用下式表示：
n 為抽取的樣本的個數(shù)，本例中 
，這個概率反映了，在概率密度函數(shù)的參數(shù)是 時，得到 X 這組樣本的概率。上式中等式右側(cè)只有 是未知數(shù)，所以 L 是 的函數(shù)。
這個函數(shù)反映的是在不同的參數(shù) 取值下，取得當(dāng)前這個樣本集的可能性，因此稱為參數(shù) 相對于樣本集 X 的似然函數(shù)（likelihood function），記為 
。
對 L 取對數(shù)，將其變成連加的，稱為對數(shù)似然函數(shù)，如下式：
Q：這里為什么要取對數(shù)？
取對數(shù)之后累積變?yōu)槔酆停髮?dǎo)更加方便
概率累積會出現(xiàn)數(shù)值非常小的情況，比如1e-30，由于計算機的精度是有限的，無法識別這一類數(shù)據(jù)，取對數(shù)之后，更易于計算機的識別(1e-30以10為底取對數(shù)后便得到-30)。
問題二：學(xué)校那么多學(xué)生，為什么就恰好抽到了這 200 個人 ( 身高) 呢？
在學(xué)校那么學(xué)生中，我一抽就抽到這 200 個學(xué)生（身高），而不是其他人，那是不是表示在整個學(xué)校中，這 200 個人（的身高）出現(xiàn)的概率極大啊，也就是其對應(yīng)的似然函數(shù) 極大，即
這個叫做 的極大似然估計量，即為我們所求的值。
問題三：那么怎么極大似然函數(shù)？
求 對所有參數(shù)的偏導(dǎo)數(shù)，然后讓這些偏導(dǎo)數(shù)為 0，假設(shè)有 
個參數(shù)，就有 個方程組成的方程組，那么方程組的解就是似然函數(shù)的極值點了，從而得到對應(yīng)的 了。
1.1.3 極大似然估計
極大似然估計你可以把它看作是一個反推。多數(shù)情況下我們是根據(jù)已知條件來推算結(jié)果，而極大似然估計是已經(jīng)知道了結(jié)果，然后尋求使該結(jié)果出現(xiàn)的可能性極大的條件，以此作為估計值。
比如說：
假如一個學(xué)校的學(xué)生男女比例為 9:1 (條件)，那么你可以推出，你在這個學(xué)校里更大可能性遇到的是男生 (結(jié)果)；
假如你不知道那女比例，你走在路上，碰到100個人，發(fā)現(xiàn)男生就有90個 (結(jié)果)，這時候你可以推斷這個學(xué)校的男女比例更有可能為 9:1 (條件)，這就是極大似然估計。
極大似然估計，只是一種概率論在統(tǒng)計學(xué)的應(yīng)用，它是參數(shù)估計的方法之一。說的是已知某個隨機樣本滿足某種概率分布，但是其中具體的參數(shù)不清楚，通過若干次試驗，觀察其結(jié)果，利用結(jié)果推出參數(shù)的大概值。
極大似然估計是建立在這樣的思想上：已知某個參數(shù)能使這個樣本出現(xiàn)的概率極大，我們當(dāng)然不會再去選擇其他小概率的樣本，所以干脆就把這個參數(shù)作為估計的真實值。
1.1.4 求極大似然函數(shù)估計值的一般步驟：
（1）寫出似然函數(shù)；
（2）對似然函數(shù)取對數(shù)，并整理；
（3）求導(dǎo)數(shù)，令導(dǎo)數(shù)為 0，得到似然方程；
（4）解似然方程，得到的參數(shù)。
應(yīng)用一 ：回歸問題中的極小化平方和 （極小化代價函數(shù)）
假設(shè)線性回歸模型具有如下形式: 
，其中 
， 誤差 
， 如何求 呢？
最小二乘估計：最合理的參數(shù)估計量應(yīng)該使得模型能最好地擬合樣本數(shù)據(jù)，也就是估計值和觀測值之差的平方和最小，其推導(dǎo)過程如下所示：
求解方法是通過梯度下降算法，訓(xùn)練數(shù)據(jù)不斷迭代得到最終的值。
極大似然法：最合理的參數(shù)估計量應(yīng)該使得從模型中抽取 m 組樣本觀測值的概率極大，也就是似然函數(shù)極大。1
假設(shè)誤差項
，
則 
(建議復(fù)習(xí)一下正態(tài)分布的概率密度函數(shù)和相關(guān)的性質(zhì))
令 
則
， 即將極大似然函數(shù)等價于極小化代價函數(shù)。
，
時， 
時，
， 即將極大似然函數(shù)等價于極小化代價函數(shù)。1.2 EM算法
1.2.1 問題描述
。實際情況并不是這樣的，男生和女生分別服從兩種不同的正態(tài)分布，即男生 
，女生 
，(注意：EM算法和極大似然估計的前提是一樣的，都要假設(shè)數(shù)據(jù)總體的分布，如果不知道數(shù)據(jù)分布，是無法使用EM算法的)。那么該怎樣評估學(xué)生的身高分布呢？1.2.2 EM 算法
當(dāng)我們知道了每個人是男生還是女生，我們可以很容易利用極大似然對男女各自的身高的分布進行估計。 反過來，當(dāng)我們知道了男女身高的分布參數(shù)我們才能知道每一個人更有可能是男生還是女生。例如我們已知男生的身高分布為 
， 女生的身高分布為 
， 一個學(xué)生的身高為180，我們可以推斷出這個學(xué)生為男生的可能性更大。
先設(shè)定男生和女生的身高分布參數(shù)(初始值)，例如男生的身高分布為 ， 女生的身高分布為 ，當(dāng)然了，剛開始肯定沒那么準(zhǔn)；然后計算出每個人更可能屬于第一個還是第二個正態(tài)分布中的（例如，這個人的身高是180，那很明顯，他極大可能屬于男生），這個是屬于Expectation 一步； 我們已經(jīng)大概地按上面的方法將這 200 個人分為男生和女生兩部分，我們就可以根據(jù)之前說的極大似然估計分別對男生和女生的身高分布參數(shù)進行估計（這不變成了極大似然估計了嗎？極大即為Maximization）這步稱為 Maximization； 然后，當(dāng)我們更新這兩個分布的時候，每一個學(xué)生屬于女生還是男生的概率又變了，那么我們就再需要調(diào)整E步； ……如此往復(fù)，直到參數(shù)基本不再發(fā)生變化或滿足結(jié)束條件為止。
1.2.3 總結(jié)
2. EM算法推導(dǎo)
2.1 基礎(chǔ)知識
2.1.1 凸函數(shù)
設(shè)是定義在實數(shù)域上的函數(shù)，如果對于任意的實數(shù)，都有：
那么是凸函數(shù)。若不是單個實數(shù)，而是由實數(shù)組成的向量，此時，如果函數(shù)的 Hesse 矩陣是半正定的，即
是凸函數(shù)。特別地，如果 
或者 
，稱為嚴格凸函數(shù)。
2.1.2 Jensen不等式
如下圖，如果函數(shù) 
是凸函數(shù)， 
是隨機變量，有 0.5 的概率是 a，有 0.5 的概率是 b， 的期望值就是 a 和 b 的中值了那么：
其中，
，這里 a 和 b 的權(quán)值為 0.5, 
與 a 的權(quán)值相等，
與 b 的權(quán)值相等。
特別地，如果函數(shù) 是嚴格凸函數(shù)，當(dāng)且僅當(dāng)：
(即隨機變量是常量) 時等號成立。
是凹函數(shù)，Jensen不等式符號相反。2.1.3 期望
，數(shù)學(xué)期望 
為：
是權(quán)值，滿足兩個條件 
。
，則數(shù)學(xué)期望 為：
， 若 
是離散型隨機變量，則：
是連續(xù)型隨機變量，則：
2.2 EM算法的推導(dǎo)
個相互獨立的樣本 
，對應(yīng)的隱含數(shù)據(jù) 
，此時 
即為完全數(shù)據(jù)，樣本的模型參數(shù)為 , 則觀察數(shù)據(jù) 
的概率為 
，完全數(shù)據(jù) 
的似然函數(shù)為 
。
，我們僅需要找到合適的 極大化對數(shù)似然函數(shù)即可：
之后，我們的目標(biāo)變成了找到合適的 和 讓對數(shù)似然函數(shù)極大：
嗎？那我們自然而然會想到分別對未知的 和 分別求偏導(dǎo)，這樣做可行嗎？ 和 分別求偏導(dǎo)，由于
是 
邊緣概率(建議沒基礎(chǔ)的同學(xué)網(wǎng)上搜一下邊緣概率的概念)，轉(zhuǎn)化為 求導(dǎo)后形式會非常復(fù)雜（可以想象下 
復(fù)合函數(shù)的求導(dǎo)) ，所以很難求解得到 和 。那么我們想一下可不可以將加號從 log 中提取出來呢？我們對這個式子進行縮放如下：
，滿足：
其中：
為第 i 個樣本， 為第 i 個樣本對應(yīng)的權(quán)重，那么：
的下界，我們發(fā)現(xiàn)實際上就是 
的加權(quán)求和，由于上面講過權(quán)值 累積和為1，因此上式是 的加權(quán)平均，也是我們所說的期望，這就是Expectation的來歷啦。下一步要做的就是尋找一個合適的 
最優(yōu)化這個下界(M步)。 已經(jīng)給定，那么 
的值就取決于 和 
了。我們可以通過調(diào)整這兩個概率使下界逼近 的真實值，當(dāng)不等式變成等式時，說明我們調(diào)整后的下界能夠等價于 了。由 Jensen 不等式可知，等式成立的條件是隨機變量是常數(shù)，則有：
，我們得到：
。從上面兩式，我們可以得到：
是已知樣本和模型參數(shù)下的隱變量分布。
, 則第 (2) 式是我們的包含隱藏數(shù)據(jù)的對數(shù)似然的一個下界。如果我們能極大化這個下界，則也在嘗試極大化我們的對數(shù)似然。即我們需要極大化下式：
后分布 的選擇問題， 從而建立了 的下界，這是 E 步，接下來的M 步驟就是固定 后，調(diào)整 ，去極大化的下界。 ，則我們需要極大化的對數(shù)似然下界為：
2.3 EM算法流程
，聯(lián)合分布 
，條件分布 
， 極大迭代次數(shù) 
。 的初值 
：E步：計算聯(lián)合分布的條件概率期望：
M步：極大化 ,得到 :
重復(fù)E、M步驟直到 收斂
2.4 EM算法另一種理解
2.5 EM算法的收斂性思考
為 
和 
，并相減得到：
使得
極大，因此有：
，證明了EM算法的收斂性。 是凸的，則EM算法可以保證收斂到全局極大值，這點和梯度下降法這樣的迭代算法相同。至此我們也回答了上面提到的第二個問題。2.6. EM算法應(yīng)用
支持向量機的SMO算法 混合高斯模型 K-means 隱馬爾可夫模型
3. EM算法案例-兩硬幣模型
http://ai.stanford.edu/~chuongdo/papers/em_tutorial.pdf
CASE a
，5次實驗中B正面向上的次數(shù)再除以總次數(shù)作為即為 ，即：
CASE b
和 
，計算每個實驗中選擇的硬幣是 A 和 B 的概率，例如第一個實驗中選擇 A 的概率為：
， 
代表第 
次實驗正面朝上的個數(shù)，
代表第 次實驗選擇硬幣 A 的概率，
代表第 次實驗選擇硬幣B的概率 。
求導(dǎo)：
, 進行第二輪 EM，計算每個實驗中選擇的硬幣是 A 和 B 的概率（E步），然后在計算M步，如此繼續(xù)迭代......迭代十步之后
引用文獻： 1.《從最大似然到EM算法淺解》(https://blog.csdn.net/zouxy09/article/details/8537620) 2. Andrew Ng 《Mixtures of Gaussians and the EM algorithm》 3.《What is the expectation maximization algorithm?》http://ai.stanford.edu/~chuongdo/papers/em_tutorial.pdf
編輯：王菁