如何感性地理解EM演算法?
作者: milter
原文鏈接:https://www.jianshu.com/p/1121509ac1dc查看更多的專業文章,請移步至「人工智慧LeadAI」公眾號,查看更多的課程信息和產品信息,請移步至全新打造後呈現的官網:www.leadai.org.
如果使用基於最大似然估計的模型,模型中存在隱變數,就要用EM演算法做參數估計。個人認為,理解EM演算法背後的idea,遠比看懂它的數學推導重要。idea會讓你有一個直觀的感受,從而明白演算法的合理性,數學推導只是將這種合理性用更加嚴謹的語言表達出來而已。打個比方,一個梨很甜,用數學的語言可以表述為糖分含量90%,但只有親自咬一口,你才能真正感覺到這個梨有多甜,也才能真正理解數學上的90%的糖分究竟是怎麼樣的。如果EM是個梨,本文的目的就是帶領大家咬一口。
01
一個非常簡單的例子
假設現在有兩枚硬幣1和2,,隨機拋擲後正面朝上概率分別為P1,P2。為了估計這兩個概率,做實驗,每次取一枚硬幣,連擲5下,記錄下結果,如下:
硬幣結果統計1正正反正反3正-2反2反反正正反2正-3反1正反反反反1正-4反2正反反正正3正-2反1反正正反反2正-3反
可以很容易地估計出P1和P2,如下:
P1 = (3+1+2)/ 15 = 0.4
P2= (2+3)/10 = 0.5到這裡,一切似乎很美好,下面我們加大難度。
02
加入隱變數z
還是上面的問題,現在我們抹去每輪投擲時使用的硬幣標記,如下:
硬幣結果統計Unknown正正反正反3正-2反Unknown反反正正反2正-3反Unknown正反反反反1正-4反Unknown正反反正正3正-2反Unknown反正正反反2正-3反
好了,現在我們的目標沒變,還是估計P1和P2,要怎麼做呢?
顯然,此時我們多了一個隱變數z,可以把它認為是一個5維的向量(z1,z2,z3,z4,z5),代表每次投擲時所使用的硬幣,比如z1,就代表第一輪投擲時使用的硬幣是1還是2。但是,這個變數z不知道,就無法去估計P1和P2,所以,我們必須先估計出z,然後才能進一步估計P1和P2。
但要估計z,我們又得知道P1和P2,這樣我們才能用最大似然概率法則去估計z,這不是雞生蛋和蛋生雞的問題嗎,如何破?
答案就是先隨機初始化一個P1和P2,用它來估計z,然後基於z,還是按照最大似然概率法則去估計新的P1和P2,如果新的P1和P2和我們初始化的P1和P2一樣,請問這說明了什麼?(此處思考1分鐘)
這說明我們初始化的P1和P2是一個相當靠譜的估計!
就是說,我們初始化的P1和P2,按照最大似然概率就可以估計出z,然後基於z,按照最大似然概率可以反過來估計出P1和P2,當與我們初始化的P1和P2一樣時,說明是P1和P2很有可能就是真實的值。這裡面包含了兩個交互的最大似然估計。
如果新估計出來的P1和P2和我們初始化的值差別很大,怎麼辦呢?就是繼續用新的P1和P2迭代,直至收斂。
這就是下面的EM初級版。
03
EM初級版
我們不妨這樣,先隨便給P1和P2賦一個值,比如:
P1 = 0.2
P2 = 0.7然後,我們看看第一輪拋擲最可能是哪個硬幣。
如果是硬幣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輪中的相應概率。做成表格如下:
輪數若是硬幣1若是硬幣210.005120.0308720.020480.0132330.081920.0056740.005120.0308750.020480.01323
按照最大似然法則:
第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設想我們是全知的神,知道每輪拋擲時的硬幣就是如本文第001部分標示的那樣,那麼,P1和P2的最大似然估計就是0.4和0.5(下文中將這兩個值稱為P1和P2的真實值)。那麼對比下我們初始化的P1和P2和新估計出的P1和P2:
初始化的P1估計出的P1真實的P1初始化的P2估計出的P2真實的P20.20.330.40.70.60.5
看到沒?我們估計的P1和P2相比於它們的初始值,更接近它們的真實值了!
可以期待,我們繼續按照上面的思路,用估計出的P1和P2再來估計z,再用z來估計新的P1和P2,反覆迭代下去,就可以最終得到P1 = 0.4,P2=0.5,此時無論怎樣迭代,P1和P2的值都會保持0.4和0.5不變,於是乎,我們就找到了P1和P2的最大似然估計。
這裡有兩個問題:
1、新估計出的P1和P2一定會更接近真實的P1和P2?
答案是:沒錯,一定會更接近真實的P1和P2,數學可以證明,但這超出了本文的主題,請參閱其他書籍或文章。2、迭代一定會收斂到真實的P1和P2嗎?
答案是:不一定,取決於P1和P2的初始化值,上面我們之所以能收斂到P1和P2,是因為我們幸運地找到了好的初始化值。04
EM進階版
下面,我們思考下,上面的方法還有沒有改進的餘地?
我們是用最大似然概率法則估計出的z值,然後再用z值按照最大似然概率法則估計新的P1和P2。也就是說,我們使用了一個最可能的z值,而不是所有可能的z值。
如果考慮所有可能的z值,對每一個z值都估計出一個新的P1和P2,將每一個z值概率大小作為權重,將所有新的P1和P2分別加權相加,這樣的P1和P2應該會更好一些。
所有的z值有多少個呢?顯然,有2^5=32種,需要我們進行32次估值??
不需要,我們可以用期望來簡化運算。
輪數若是硬幣1若是硬幣210.005120.0308720.020480.0132330.081920.0056740.005120.0308750.020480.01323
利用上面這個表,我們可以算出每輪拋擲中使用硬幣1或者使用硬幣2的概率。比如第1輪,使用硬幣1的概率是:
0.00512/(0.00512+0.03087)=0.14
使用硬幣2的概率是1-0.14=0.86依次可以算出其他4輪的概率,如下:
輪數z_i=硬幣1z_i=硬幣210.140.8620.610.3930.940.0640.140.8650.610.39
上表中的右兩列表示期望值。看第一行,0.86表示,從期望的角度看,這輪拋擲使用硬幣2的概率是0.86。相比於前面的方法,我們按照最大似然概率,直接將第1輪估計為用的硬幣2,此時的我們更加謹慎,我們只說,有0.14的概率是硬幣1,有0.86的概率是硬幣2,不再是非此即彼。這樣我們在估計P1或者P2時,就可以用上全部的數據,而不是部分的數據,顯然這樣會更好一些。
這一步,我們實際上是估計出了z的概率分布,這步被稱作E步。
結合下表:
硬幣結果統計Unknown正正反正反3正-2反Unknown反反正正反2正-3反Unknown正反反反反1正-4反Unknown正反反正正3正-2反Unknown反正正反反2正-3反
我們按照期望最大似然概率的法則來估計新的P1和P2:
以P1估計為例,第1輪的3正2反相當於
0.14*3=0.42正0.14*2=0.28反依次算出其他四輪,列表如下:
輪數正面反面10.420.2821.221.8330.943.7640.420.2851.221.83總計4.227.98
P1=4.22/(4.22+7.98)=0.35
可以看到,改變了z值的估計方法後,新估計出的P1要更加接近0.4。原因就是我們使用了所有拋擲的數據,而不是之前只使用了部分的數據。
這步中,我們根據E步中求出的z的概率分布,依據最大似然概率法則去估計P1和P2,被稱作M步。
05
總結
以上,我們用一個實際的小例子,來實際演示了EM演算法背後的idea,共性存於個性之中,通過這個例子,我們可以對EM演算法究竟在幹什麼有一個深刻感性的認識,掌握EM演算法的思想精髓。
06
參考資料
http://pan.baidu.com/s/1i4NfvP7
推薦閱讀:
※趣說遊戲AI開發:曼哈頓街角的A*演算法
※首都機場率先引入阿里雲ET航空大腦,每天調度1700架次航班節省5000個小時
※求各位大俠推薦一些有關於概率地圖(機器人路徑規劃)方面的書籍,目前只能找到相關文獻,求推薦!?
※機器學習入門系列:關於機器學習演算法你需要了解的東西、如何開發機器學習模型?
TAG:算法 |