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

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

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

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算法計(jì)算流程

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

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

記錄結(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)概率。做成表格如下:

相應(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)算。

簡(jiǎn)化運(yùn)算

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

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

  ? 0.00512/(0.00512 + 0.03087) = 0.14

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

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

其他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é)合下表:

E步

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

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

0.14*3=0.42正

0.14*2=0.28反

依次算出其他四輪,列表如下:

計(jì)算其他四輪

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步。

分享到:
在線咨詢 我要報(bào)名
和我們?cè)诰€交談!