EM算法是什么？EM算法實(shí)現(xiàn)流程

EM算法也稱期望最大化(Expectation-Maximum,簡(jiǎn)稱EM)算法。 它是一個(gè)基礎(chǔ)算法，是很多機(jī)器學(xué)習(xí)領(lǐng)域算法的基礎(chǔ)，比如隱式馬爾科夫算法(HMM)等等。 EM算法是一種迭代優(yōu)化策略，由于它的計(jì)算方法中每一次迭代都分兩步， 其中一個(gè)為期望步(E步)， 另一個(gè)為極大步(M步)， 所以算法被稱為EM算法(Expectation-Maximization Algorithm)。

EM算法受到缺失思想影響，最初是為了解決數(shù)據(jù)缺失情況下的參數(shù)估計(jì)問題，其算法基礎(chǔ)和收斂有效性等問題在Dempster、Laird和Rubin三人于1977年所做的文章《Maximum likelihood from incomplete data via the EM algorithm》中給出了詳細(xì)的闡述。其基本思想是：

  ? 首先根據(jù)已經(jīng)給出的觀測(cè)數(shù)據(jù)，估計(jì)出模型參數(shù)的值;

  ? 然后再依據(jù)上一步估計(jì)出的參數(shù)值估計(jì)缺失數(shù)據(jù)的值，再根據(jù)估計(jì)出的缺失數(shù)據(jù)加上之前已經(jīng)觀測(cè)到的數(shù)據(jù)重新再對(duì)參數(shù)值進(jìn)行估計(jì);

  ? 然后反復(fù)迭代，直至最后收斂，迭代結(jié)束。

EM算法計(jì)算流程：

EM算法一個(gè)超級(jí)簡(jiǎn)單的案例

假設(shè)現(xiàn)在有兩枚硬幣1和2，,隨機(jī)拋擲后正面朝上概率分別為P1，P2。為了估計(jì)這兩個(gè)概率，做實(shí)驗(yàn)，每次取1枚硬幣，連擲5下，記錄下結(jié)果，如下：

可以很容易地估計(jì)出P1和P2，如下：

P1 = (3+1+2)/ 15 = 0.4 P2= (2+3)/10 = 0.5

到這里，一切似乎很美好，下面我們加大難度。 

加入隱變量z后的求解，還是上面的問題，現(xiàn)在我們抹去每輪投擲時(shí)使用的硬幣標(biāo)記，如下：

現(xiàn)在我們的目標(biāo)沒變，還是估計(jì)P1和P2，要怎么做呢?

顯然，此時(shí)我們多了一個(gè)隱變量z，可以把它認(rèn)為是一個(gè)5維的向量(z1,z2,z3,z4,z5)，代表每次投擲時(shí)所使用的硬幣，

比如z1，就代表第一輪投擲時(shí)使用的硬幣是1還是2。但是，這個(gè)變量z不知道，就無法去估計(jì)P1和P2，所以，我們必須先估計(jì)出z，然后才能進(jìn)一步估計(jì)P1和P2。

但要估計(jì)z，我們又得知道P1和P2，這樣我們才能用最大似然概率法則去估計(jì)z，這不是雞生蛋和蛋生雞的問題嗎，如何破?

EM初級(jí)版

我們不妨這樣，先隨便給P1和P2賦1個(gè)值，比如：

  ? P1 = 0.2

  ? P2 = 0.7

然后，我們看看第1輪拋擲最可能是哪個(gè)硬幣。

如果是硬幣1，得出3正2反的概率為 0.2 ? 0.2 ? 0.2 ? 0.8 ? 0.8 = 0.00512

如果是硬幣2，得出3正2反的概率為0.7 ? 0.7 ? 0.7 ? 0.3 ? 0.3 = 0.03087

然后依次求出其他4輪中的相應(yīng)概率。做成表格如下：

按照最大似然法則：

第1輪中最有可能的是硬幣2

第2輪中最有可能的是硬幣1

第3輪中最有可能的是硬幣1

第4輪中最有可能的是硬幣2

第5輪中最有可能的是硬幣1

我們就把上面的值作為z的估計(jì)值。然后按照最大似然概率法則來估計(jì)新的P1和P2。

P1 = (2+1+2)/15 = 0.33 P2=(3+3)/10 = 0.6

設(shè)想我們是全知的神，知道每輪拋擲時(shí)的硬幣就是如本文第001部分標(biāo)示的那樣，那么，P1和P2的最大似然估計(jì)就是0.4和0.5(下文中將這兩個(gè)值稱為P1和P2的真實(shí)值)。那么對(duì)比下我們初始化的P1和P2和新估計(jì)出的P1和P2：

看到?jīng)]?我們估計(jì)的P1和P2相比于它們的初始值，更接近它們的真實(shí)值了!

可以期待，我們繼續(xù)按照上面的思路，用估計(jì)出的P1和P2再來估計(jì)z，再用z來估計(jì)新的P1和P2，反復(fù)迭代下去，就可以最終得到P1 = 0.4，P2=0.5，此時(shí)無論怎樣迭代，P1和P2的值都會(huì)保持0.4和0.5不變，于是乎，我們就找到了P1和 P2的最大似然估計(jì)。

這里有兩個(gè)問題：

1、新估計(jì)出的P1和P2一定會(huì)更接近真實(shí)的P1和P2?

答案是：沒錯(cuò)，一定會(huì)更接近真實(shí)的P1和P2，數(shù)學(xué)可以證明，但這超出了本?的主題，請(qǐng)參閱其他書籍或文章。

2、迭代一定會(huì)收斂到真實(shí)的P1和P2嗎?

答案是：不一定，取決于P1和P2的初始化值，上面我們之所以能收斂到P1和P2，是因?yàn)槲覀冃疫\(yùn)地找到了好的初始化值。

EM進(jìn)階版

下面，我們思考下，上面的方法還有沒有改進(jìn)的余地?

我們是用最大似然概率法則估計(jì)出的z值，然后再用z值按照最大似然概率法則估計(jì)新的P1和P2。也就是說，我們使用了?個(gè)最可能的z值，?不是所有可能的z值。

如果考慮所有可能的z值，對(duì)每?個(gè)z值都估計(jì)出?個(gè)新的P1和P2，將每?個(gè)z值概率??作為權(quán)重，將所有新的P1和P2分別加權(quán)相加，這樣的P1和P2應(yīng)該會(huì)更好?些。

所有的z值有多少個(gè)呢?

顯然，有2 = 32種，需要我們進(jìn)行32次估值??

不需要，我們可以用期望來簡(jiǎn)化運(yùn)算。

利用上面這個(gè)表，我們可以算出每輪拋擲中使用硬幣1或者使用硬幣2的概率。

比如第1輪，使用硬幣1的概率是：

  ? 0.00512/(0.00512 + 0.03087) = 0.14

使用硬幣2的概率是1-0.14=0.86

依次可以算出其他4輪的概率，如下：

上表中的右兩列表示期望值。看第一行，0.86表示，從期望的?度看，這輪拋擲使用硬幣2的概率是0.86。相比于前面的方法，我們按照最大似然概率，直接將第1輪估計(jì)為用的硬幣2，此時(shí)的我們更加謹(jǐn)慎，我們只說，有0.14的概率是硬 幣1，有0.86的概率是硬幣2，不再是非此即彼。這樣我們?cè)诠烙?jì)P1或者P2時(shí)，就可以用上全部的數(shù)據(jù)，而不是部分的數(shù)據(jù)，顯然這樣會(huì)更好一些。

這一步，我們實(shí)際上是估計(jì)出了z的概率分布，這步被稱作E步。 結(jié)合下表：

我們按照期望最大似然概率的法則來估計(jì)新的P1和P2：

以P1估計(jì)為例，第1輪的3正2反相當(dāng)于

0.14*3=0.42正

0.14*2=0.28反

依次算出其他四輪，列表如下：

P1=4.22/(4.22+7.98)=0.35

可以看到，改變了z值的估計(jì)方法后，新估計(jì)出的P1要更加接近0.4。原因就是我們使用了所有拋擲的數(shù)據(jù)，而不是之前只使用了部分的數(shù)據(jù)。

這步中，我們根據(jù)E步中求出的z的概率分布，依據(jù)最?似然概率法則去估計(jì)P1和P2，被稱作M步。