首頁人工智能技術(shù)資訊正文

EM算法是什么?EM算法實現(xiàn)流程

更新時間:2023-09-22 來源:黑馬程序員 瀏覽量:

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

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

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

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

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

EM算法計算流程:

em算法計算流程

EM算法一個超級簡單的案例

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

記錄結(jié)果

可以很容易地估計出P1和P2,如下:

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

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

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

隱變量

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

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

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

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

EM初級版

我們不妨這樣,先隨便給P1和P2賦1個值,比如:

  ? P1 = 0.2

  ? P2 = 0.7

然后,我們看看第1輪拋擲最可能是哪個硬幣。

如果是硬幣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)概率。做成表格如下:

相應(yīng)概率

按照最大似然法則:

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

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

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

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

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

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

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

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

 初始化

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

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

這里有兩個問題:

1、新估計出的P1和P2一定會更接近真實的P1和P2?

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

2、迭代一定會收斂到真實的P1和P2嗎?

答案是:不一定,取決于P1和P2的初始化值,上面我們之所以能收斂到P1和P2,是因為我們幸運地找到了好的初始化值。

EM進階版

下面,我們思考下,上面的方法還有沒有改進的余地?

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

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

所有的z值有多少個呢?

顯然,有2 = 32種,需要我們進行32次估值??

不需要,我們可以用期望來簡化運算。

簡化運算

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

比如第1輪,使用硬幣1的概率是:

  ? 0.00512/(0.00512 + 0.03087) = 0.14

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

依次可以算出其他4輪的概率,如下:

其他4輪的概率

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

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

E步

我們按照期望最大似然概率的法則來估計新的P1和P2:

以P1估計為例,第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值的估計方法后,新估計出的P1要更加接近0.4。原因就是我們使用了所有拋擲的數(shù)據(jù),而不是之前只使用了部分的數(shù)據(jù)。

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

分享到:
在線咨詢 我要報名
和我們在線交談!