人人都能看懂的EM算法推導(dǎo)

來(lái)源：深度學(xué)習(xí)初學(xué)者
本文約6800字，建議閱讀10分鐘
本文通過(guò)案例帶大家學(xué)習(xí)EM算法的推導(dǎo)。

假設(shè)我們需要調(diào)查我們學(xué)校學(xué)生的身高分布。我們先假設(shè)學(xué)校所有學(xué)生的身高服從正態(tài)分布  。(注意：極大似然估計(jì)的前提一定是要假設(shè)數(shù)據(jù)總體的分布，如果不知道數(shù)據(jù)分布，是無(wú)法使用極大似然估計(jì)的)，這個(gè)分布的均值  和方差  未知，如果我們估計(jì)出這兩個(gè)參數(shù)，那我們就得到了最終的結(jié)果。那么怎樣估計(jì)這兩個(gè)參數(shù)呢？

學(xué)校的學(xué)生這么多，我們不可能挨個(gè)統(tǒng)計(jì)吧？這時(shí)候我們需要用到概率統(tǒng)計(jì)的思想，也就是抽樣，根據(jù)樣本估算總體。假設(shè)我們隨機(jī)抽到了 200 個(gè)人（也就是 200 個(gè)身高的樣本數(shù)據(jù)，為了方便表示，下面“人”的意思就是對(duì)應(yīng)的身高）。然后統(tǒng)計(jì)抽樣這 200 個(gè)人的身高。根據(jù)這 200 個(gè)人的身高估計(jì)均值  和方差  。

用數(shù)學(xué)的語(yǔ)言來(lái)說(shuō)就是：為了統(tǒng)計(jì)學(xué)校學(xué)生的身高分布，我們獨(dú)立地按照概率密度  抽取了 200 個(gè)（身高），組成樣本集 (其中 表示抽到的第  個(gè)人的身高，這里 N 就是 200，表示樣本個(gè)數(shù))，我們想通過(guò)樣本集 X 來(lái)估計(jì)出總體的未知參數(shù)  。這里概率密度  服從高斯分布  ，其中的未知參數(shù)是  。

那么問(wèn)題來(lái)了怎樣估算參數(shù)  呢？

1.1.2 估計(jì)參數(shù)

我們先回答幾個(gè)小問(wèn)題：

問(wèn)題一：抽到這 200 個(gè)人的概率是多少呢？

由于每個(gè)樣本都是獨(dú)立地從  中抽取的，換句話說(shuō)這 200 個(gè)學(xué)生隨便捉的，他們之間是沒(méi)有關(guān)系的，即他們之間是相互獨(dú)立的。假如抽到學(xué)生 A（的身高）的概率是  ，抽到學(xué)生B的概率是  ，那么同時(shí)抽到男生 A 和男生 B 的概率是  ，同理，我同時(shí)抽到這 200 個(gè)學(xué)生的概率就是他們各自概率的乘積了，即為他們的聯(lián)合概率，用下式表示：

n 為抽取的樣本的個(gè)數(shù)，本例中  ，這個(gè)概率反映了，在概率密度函數(shù)的參數(shù)是  時(shí)，得到 X 這組樣本的概率。上式中等式右側(cè)只有  是未知數(shù)，所以 L 是  的函數(shù)。

這個(gè)函數(shù)反映的是在不同的參數(shù)  取值下，取得當(dāng)前這個(gè)樣本集的可能性，因此稱為參數(shù)  相對(duì)于樣本集 X 的似然函數(shù)（likelihood function），記為  。

對(duì) L 取對(duì)數(shù)，將其變成連加的，稱為對(duì)數(shù)似然函數(shù)，如下式：

Q：這里為什么要取對(duì)數(shù)？

• 取對(duì)數(shù)之后累積變?yōu)槔酆?，求?dǎo)更加方便

• 概率累積會(huì)出現(xiàn)數(shù)值非常小的情況，比如1e-30，由于計(jì)算機(jī)的精度是有限的，無(wú)法識(shí)別這一類數(shù)據(jù)，取對(duì)數(shù)之后，更易于計(jì)算機(jī)的識(shí)別(1e-30以10為底取對(duì)數(shù)后便得到-30)。

問(wèn)題二：學(xué)校那么多學(xué)生，為什么就恰好抽到了這 200 個(gè)人 ( 身高) 呢？

在學(xué)校那么學(xué)生中，我一抽就抽到這 200 個(gè)學(xué)生（身高），而不是其他人，那是不是表示在整個(gè)學(xué)校中，這 200 個(gè)人（的身高）出現(xiàn)的概率極大啊，也就是其對(duì)應(yīng)的似然函數(shù)  極大，即

 這個(gè)叫做  的極大似然估計(jì)量，即為我們所求的值。

問(wèn)題三：那么怎么極大似然函數(shù)？

求  對(duì)所有參數(shù)的偏導(dǎo)數(shù)，然后讓這些偏導(dǎo)數(shù)為 0，假設(shè)有  個(gè)參數(shù)，就有  個(gè)方程組成的方程組，那么方程組的解就是似然函數(shù)的極值點(diǎn)了，從而得到對(duì)應(yīng)的  了。

1.1.3 極大似然估計(jì)

極大似然估計(jì)你可以把它看作是一個(gè)反推。多數(shù)情況下我們是根據(jù)已知條件來(lái)推算結(jié)果，而極大似然估計(jì)是已經(jīng)知道了結(jié)果，然后尋求使該結(jié)果出現(xiàn)的可能性極大的條件，以此作為估計(jì)值。

比如說(shuō)：

• 假如一個(gè)學(xué)校的學(xué)生男女比例為 9:1 (條件)，那么你可以推出，你在這個(gè)學(xué)校里更大可能性遇到的是男生 (結(jié)果)；

• 假如你不知道那女比例，你走在路上，碰到100個(gè)人，發(fā)現(xiàn)男生就有90個(gè) (結(jié)果)，這時(shí)候你可以推斷這個(gè)學(xué)校的男女比例更有可能為 9:1 (條件)，這就是極大似然估計(jì)。

極大似然估計(jì)，只是一種概率論在統(tǒng)計(jì)學(xué)的應(yīng)用，它是參數(shù)估計(jì)的方法之一。說(shuō)的是已知某個(gè)隨機(jī)樣本滿足某種概率分布，但是其中具體的參數(shù)不清楚，通過(guò)若干次試驗(yàn)，觀察其結(jié)果，利用結(jié)果推出參數(shù)的大概值。

極大似然估計(jì)是建立在這樣的思想上：已知某個(gè)參數(shù)能使這個(gè)樣本出現(xiàn)的概率極大，我們當(dāng)然不會(huì)再去選擇其他小概率的樣本，所以干脆就把這個(gè)參數(shù)作為估計(jì)的真實(shí)值。

1.1.4 求極大似然函數(shù)估計(jì)值的一般步驟：

（1）寫出似然函數(shù)；

（2）對(duì)似然函數(shù)取對(duì)數(shù)，并整理；

（3）求導(dǎo)數(shù)，令導(dǎo)數(shù)為 0，得到似然方程；

（4）解似然方程，得到的參數(shù)。

應(yīng)用一 ：回歸問(wèn)題中的極小化平方和 （極小化代價(jià)函數(shù)）

假設(shè)線性回歸模型具有如下形式: ，其中  ， 誤差  ， 如何求  呢？

• 最小二乘估計(jì)：最合理的參數(shù)估計(jì)量應(yīng)該使得模型能最好地?cái)M合樣本數(shù)據(jù)，也就是估計(jì)值和觀測(cè)值之差的平方和最小，其推導(dǎo)過(guò)程如下所示：

  
  

求解方法是通過(guò)梯度下降算法，訓(xùn)練數(shù)據(jù)不斷迭代得到最終的值。

• 極大似然法：最合理的參數(shù)估計(jì)量應(yīng)該使得從模型中抽取 m 組樣本觀測(cè)值的概率極大，也就是似然函數(shù)極大。1

• 假設(shè)誤差項(xiàng)  ，

則  (建議復(fù)習(xí)一下正態(tài)分布的概率密度函數(shù)和相關(guān)的性質(zhì))

令  則 ， 即將極大似然函數(shù)等價(jià)于極小化代價(jià)函數(shù)。

根據(jù)之前學(xué)過(guò)的內(nèi)容我們知道  ，

當(dāng)  時(shí)， 

當(dāng)  時(shí)，

 

令  

則  ， 即將極大似然函數(shù)等價(jià)于極小化代價(jià)函數(shù)。

上面我們先假設(shè)學(xué)校所有學(xué)生的身高服從正態(tài)分布  。實(shí)際情況并不是這樣的，男生和女生分別服從兩種不同的正態(tài)分布，即男生  ，女生  ，(注意：EM算法和極大似然估計(jì)的前提是一樣的，都要假設(shè)數(shù)據(jù)總體的分布，如果不知道數(shù)據(jù)分布，是無(wú)法使用EM算法的)。那么該怎樣評(píng)估學(xué)生的身高分布呢？

1.2.2 EM 算法

• 當(dāng)我們知道了每個(gè)人是男生還是女生，我們可以很容易利用極大似然對(duì)男女各自的身高的分布進(jìn)行估計(jì)。
• 反過(guò)來(lái)，當(dāng)我們知道了男女身高的分布參數(shù)我們才能知道每一個(gè)人更有可能是男生還是女生。例如我們已知男生的身高分布為  ， 女生的身高分布為  ， 一個(gè)學(xué)生的身高為180，我們可以推斷出這個(gè)學(xué)生為男生的可能性更大。

• 先設(shè)定男生和女生的身高分布參數(shù)(初始值)，例如男生的身高分布為  ， 女生的身高分布為  ，當(dāng)然了，剛開始肯定沒(méi)那么準(zhǔn)；
• 然后計(jì)算出每個(gè)人更可能屬于第一個(gè)還是第二個(gè)正態(tài)分布中的（例如，這個(gè)人的身高是180，那很明顯，他極大可能屬于男生），這個(gè)是屬于Expectation 一步；
• 我們已經(jīng)大概地按上面的方法將這 200 個(gè)人分為男生和女生兩部分，我們就可以根據(jù)之前說(shuō)的極大似然估計(jì)分別對(duì)男生和女生的身高分布參數(shù)進(jìn)行估計(jì)（這不變成了極大似然估計(jì)了嗎？極大即為Maximization）這步稱為 Maximization；
• 然后，當(dāng)我們更新這兩個(gè)分布的時(shí)候，每一個(gè)學(xué)生屬于女生還是男生的概率又變了，那么我們就再需要調(diào)整E步；
• ……如此往復(fù)，直到參數(shù)基本不再發(fā)生變化或滿足結(jié)束條件為止。

1.2.3 總結(jié)

設(shè)是定義在實(shí)數(shù)域上的函數(shù)，如果對(duì)于任意的實(shí)數(shù)，都有：

那么是凸函數(shù)。若不是單個(gè)實(shí)數(shù)，而是由實(shí)數(shù)組成的向量，此時(shí)，如果函數(shù)的 Hesse 矩陣是半正定的，即

是凸函數(shù)。特別地，如果  或者  ，稱為嚴(yán)格凸函數(shù)。

2.1.2 Jensen不等式

如下圖，如果函數(shù)  是凸函數(shù)，  是隨機(jī)變量，有 0.5 的概率是 a，有 0.5 的概率是 b，  的期望值就是 a 和 b 的中值了那么：

其中， ，這里 a 和 b 的權(quán)值為 0.5,  與 a 的權(quán)值相等， 與 b 的權(quán)值相等。

特別地，如果函數(shù)  是嚴(yán)格凸函數(shù)，當(dāng)且僅當(dāng)： (即隨機(jī)變量是常量) 時(shí)等號(hào)成立。

注：若函數(shù)  是凹函數(shù)，Jensen不等式符號(hào)相反。

2.1.3 期望

對(duì)于離散型隨機(jī)變量 X 的概率分布為  ，數(shù)學(xué)期望  為：

 是權(quán)值，滿足兩個(gè)條件  。

若連續(xù)型隨機(jī)變量X的概率密度函數(shù)為  ，則數(shù)學(xué)期望  為：

設(shè) ， 若  是離散型隨機(jī)變量，則：

若  是連續(xù)型隨機(jī)變量，則：

對(duì)于  個(gè)相互獨(dú)立的樣本  ，對(duì)應(yīng)的隱含數(shù)據(jù)  ，此時(shí)  即為完全數(shù)據(jù)，樣本的模型參數(shù)為  , 則觀察數(shù)據(jù)  的概率為  ，完全數(shù)據(jù)  的似然函數(shù)為  。

假如沒(méi)有隱含變量 ，我們僅需要找到合適的  極大化對(duì)數(shù)似然函數(shù)即可：

增加隱含變量  之后，我們的目標(biāo)變成了找到合適的  和  讓對(duì)數(shù)似然函數(shù)極大：

不就是多了一個(gè)隱變量  嗎？那我們自然而然會(huì)想到分別對(duì)未知的  和  分別求偏導(dǎo)，這樣做可行嗎？

理論上是可行的，然而如果對(duì)分別對(duì)未知的  和  分別求偏導(dǎo)，由于 是  邊緣概率(建議沒(méi)基礎(chǔ)的同學(xué)網(wǎng)上搜一下邊緣概率的概念)，轉(zhuǎn)化為  求導(dǎo)后形式會(huì)非常復(fù)雜（可以想象下 復(fù)合函數(shù)的求導(dǎo)) ，所以很難求解得到  和  。那么我們想一下可不可以將加號(hào)從 log 中提取出來(lái)呢？我們對(duì)這個(gè)式子進(jìn)行縮放如下：

 

上面第(1)式引入了一個(gè)未知的新的分布 ，滿足：

其中：

也就是說(shuō)  為第 i 個(gè)樣本，  為第 i 個(gè)樣本對(duì)應(yīng)的權(quán)重，那么：

上式我實(shí)際上是我們構(gòu)建了  的下界，我們發(fā)現(xiàn)實(shí)際上就是  的加權(quán)求和，由于上面講過(guò)權(quán)值  累積和為1，因此上式是  的加權(quán)平均，也是我們所說(shuō)的期望，這就是Expectation的來(lái)歷啦。下一步要做的就是尋找一個(gè)合適的  最優(yōu)化這個(gè)下界(M步)。

假設(shè)  已經(jīng)給定，那么  的值就取決于  和  了。我們可以通過(guò)調(diào)整這兩個(gè)概率使下界逼近  的真實(shí)值，當(dāng)不等式變成等式時(shí)，說(shuō)明我們調(diào)整后的下界能夠等價(jià)于 了。由 Jensen 不等式可知，等式成立的條件是隨機(jī)變量是常數(shù)，則有：

 

其中 c 為常數(shù)，對(duì)于任意 ，我們得到：

由于 。從上面兩式，我們可以得到：

邊緣概率公式： 

條件概率公式： 

從上式可以發(fā)現(xiàn) 是已知樣本和模型參數(shù)下的隱變量分布。

如果  , 則第 (2) 式是我們的包含隱藏?cái)?shù)據(jù)的對(duì)數(shù)似然的一個(gè)下界。如果我們能極大化這個(gè)下界，則也在嘗試極大化我們的對(duì)數(shù)似然。即我們需要極大化下式：

 

至此，我們推出了在固定參數(shù) 后分布  的選擇問(wèn)題， 從而建立了  的下界，這是 E 步，接下來(lái)的M 步驟就是固定  后，調(diào)整 ，去極大化的下界。

去掉上式中常數(shù)的部分  ，則我們需要極大化的對(duì)數(shù)似然下界為：

輸入：觀察數(shù)據(jù)，聯(lián)合分布  ，條件分布 ， 極大迭代次數(shù)  。

1) 隨機(jī)初始化模型參數(shù)  的初值 

2) ：

• E步：計(jì)算聯(lián)合分布的條件概率期望：

• M步：極大化  ,得到  :

• 重復(fù)E、M步驟直到  收斂

輸出：模型參數(shù) 

在上式中分別取  為  和 ，并相減得到：

由于使得極大，因此有：

至此，我們得到了： ，證明了EM算法的收斂性。

從上面的推導(dǎo)可以看出，EM 算法可以保證收斂到一個(gè)穩(wěn)定點(diǎn)，但是卻不能保證收斂到全局的極大值點(diǎn)，因此它是局部最優(yōu)的算法，當(dāng)然，如果我們的優(yōu)化目標(biāo)  是凸的，則EM算法可以保證收斂到全局極大值，這點(diǎn)和梯度下降法這樣的迭代算法相同。至此我們也回答了上面提到的第二個(gè)問(wèn)題。

• 支持向量機(jī)的SMO算法
• 混合高斯模型
• K-means
• 隱馬爾可夫模型

http://ai.stanford.edu/~chuongdo/papers/em_tutorial.pdf

上面這個(gè)式子求導(dǎo)之后發(fā)現(xiàn)，5 次實(shí)驗(yàn)中A正面向上的次數(shù)再除以總次數(shù)作為即為  ，5次實(shí)驗(yàn)中B正面向上的次數(shù)再除以總次數(shù)作為即為 ，即：

E步：初始化和  ，計(jì)算每個(gè)實(shí)驗(yàn)中選擇的硬幣是 A 和 B 的概率，例如第一個(gè)實(shí)驗(yàn)中選擇 A 的概率為：

M步：求出似然函數(shù)下界 ， 代表第  次實(shí)驗(yàn)正面朝上的個(gè)數(shù)， 代表第  次實(shí)驗(yàn)選擇硬幣 A 的概率， 代表第  次實(shí)驗(yàn)選擇硬幣B的概率 。

針對(duì)L函數(shù)求導(dǎo)來(lái)對(duì)參數(shù)求導(dǎo)，例如對(duì) 求導(dǎo)：

第二輪迭代：基于第一輪EM計(jì)算好的  , 進(jìn)行第二輪 EM，計(jì)算每個(gè)實(shí)驗(yàn)中選擇的硬幣是 A 和 B 的概率（E步），然后在計(jì)算M步，如此繼續(xù)迭代......迭代十步之后

 

編輯：王菁