作為N大機(jī)器學(xué)習(xí)方法的一員,EM算法在各種書籍宙攻、博客奠货、網(wǎng)上視頻上被描述或者介紹,每次看完總感覺很多地方含糊不清粘优,不能讓一個初學(xué)者(有一定統(tǒng)計概率基礎(chǔ))接受仇味。最近再B站上,看到徐亦達(dá)老師的課程雹顺,EM算法這塊講解易于理解和接受丹墨,再結(jié)合PRML一書的關(guān)于混合模型和EM章節(jié)內(nèi)容,對整個EM算法從具體的原理上面有了更深入的理解嬉愧。
在下文中贩挣,更多的是通過公式推導(dǎo)和一些文字說明來梳理EM算法,盡量做到大家一看就明白没酣。
極大似然估計
極大似然估計是概率統(tǒng)計中王财,估計模型參數(shù)的一種方法,如果對似然概念以及極大似然估計的概念不理解裕便,可參考維基百科https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E4%BC%BC%E7%84%B6%E4%BC%B0%E8%AE%A1
這里绒净,我們給出一個一維高斯函數(shù)的例子。如圖1所示偿衰,一維空間里面離散分布的樣本點其分布特點可以看成是一種高斯分布挂疆。那這些樣本的高斯分布函數(shù)參數(shù)怎么求解呢?可以通過極大似然估計獲得下翎。
假設(shè)我們獲取圖1中數(shù)據(jù)樣本集合為缤言,其分布函數(shù)假設(shè)為一維高斯分布,即:
那所有數(shù)據(jù)的聯(lián)合概率,即似然函數(shù)為:
對等式兩邊求log视事,即log-likelihood:
分別對參數(shù)求導(dǎo):
可以得到:
通過上述方法胆萧,就可以得到基于樣本數(shù)據(jù)和假設(shè)分布函數(shù)模型情況下,得到樣本數(shù)據(jù)的分布函數(shù)俐东。
高斯混合模型
從圖2所示中跌穗,如果樣本數(shù)據(jù)分布式藍(lán)色點和橙色點的集合,如果依然用高斯分布去進(jìn)行最大似然估計虏辫,得到的分布模型自然是不合適的瞻离。很顯然,樣本數(shù)據(jù)分布存在兩個密集區(qū)(藍(lán)色點和橙色點)乒裆,如果能通過一種方法,確認(rèn)樣本數(shù)據(jù)里面的藍(lán)色點和橙色點,然后分別對藍(lán)色點集合進(jìn)行一個高斯估計鹤耍,對橙色點集進(jìn)行另外一個高斯估計肉迫,兩個高斯混合到一起,是不是比單個高斯能更好的匹配樣本數(shù)據(jù)的分布情況稿黄。這種情況下的分布函數(shù)就是高斯混合模型喊衫。
這里我們先直接給出高斯混合模型的分布函數(shù)(多維):
在圖2例子中,提到如果給每一個數(shù)據(jù)樣本能夠先進(jìn)行分類杆怕,即確定屬于哪一個集中的簇中族购,就能比較容易的進(jìn)行混合模型的求解。這說明了什么呢陵珍?我們可以理解寝杖,原始樣本數(shù)據(jù)是不完全的(incomplete),引入一個K維的二值隨機(jī)變量互纯,這個變量采用"1-of-K"的表示方法瑟幕,即K維中,只有一維是1留潦,其余所有元素等于0只盹。那么每一個樣本數(shù)據(jù),即有數(shù)據(jù)特征兔院,再匹配一個分配變量殖卑,就可以將圖2過程完整描述,即我們認(rèn)為和聯(lián)合在一起才是完全的(complete)坊萝。
數(shù)學(xué)表示上孵稽,我們利用邊緣概率分布和條件概率分布定義聯(lián)合概率分布.
的邊緣概率分布根據(jù)混合系數(shù)進(jìn)行賦值,即,使得邊緣概率分布是合法屹堰,那么:
類似的肛冶,在給定的一個特定的值,即針對某一簇的情況扯键,的條件概率分布是一個高斯分布睦袖,即
那么根據(jù)貝葉斯公式得到高斯混合模型:
由于我們只能觀察樣本數(shù)據(jù),無法直接獲取每個數(shù)據(jù)的分配變量,可理解為潛在變量(latent)
依據(jù)極大似然函數(shù)的求解方法,我們可以對高斯混合模型寫出數(shù)據(jù)的對數(shù)似然函數(shù):
由于對數(shù)函數(shù)內(nèi)部出現(xiàn)求和荣刑,這種情況是沒有辦法通過求導(dǎo)等于0的方式獲取估計參數(shù)的解析解的馅笙。這種情況下,就需要用到EM算法厉亏,通過迭代方式獲取估計參數(shù)董习。下面我們先從一般性問題上進(jìn)行EM算法的理論描述,然后再利用EM算法推導(dǎo)高斯混合模型的計算方法爱只。
EM算法理論證明
EM算法叫做期望最大化方法皿淋,首先我們給出EM算法一般性結(jié)論或者說步驟,其具體分為兩步,即E-step和M-step窝趣。
E-step:是求期望的步驟疯暑,求誰的期望呢?對聯(lián)合概率分布的log數(shù)據(jù)利用潛在變量的條件概率函數(shù)求期望哑舒,這個期望定義為妇拯,我們寫連續(xù)形式,離散形式類似洗鸵。
注:有些書籍或者博客中會將參數(shù)寫在里面越锈,我個人看著比較不習(xí)慣,總會把變量和參數(shù)搞混了膘滨,這里寫在下標(biāo)上甘凭。但如果有了解貝葉斯估計的,那個時候參數(shù)也被考慮成變量吏祸,其有自己的分布对蒲。表達(dá)只是一種形式,背后的理論理解掌握就OK啦贡翘。
M-step:是求最大的步驟蹈矮,求誰的最大呢?自然是期望的最大鸣驱,從而得到新的估計參數(shù)泛鸟,即
EM算法的步驟,通過高斯混合模型可以直觀理解記憶踊东。是什么意思呢北滥,其含義是在給定數(shù)據(jù)樣本的情況下,潛在變量的概率情況闸翅。也就是說在高斯混合模型中再芋,給定樣本數(shù)據(jù),我們推測樣本屬于哪一個高斯簇的概率情況坚冀。在確定分配情況后济赎,每一個簇都用高斯進(jìn)行估計,衡量估計好還是不好记某,用期望形式表示司训。這樣可以幫助理解和記憶Q的定義。那EM算法怎么證明其收斂性呢液南?
我們要保證:
這樣每次迭代可以使得似然函數(shù)隨著參數(shù)變大壳猜,一直到似然函數(shù)不再增大或滿足其他終止條件止。
那怎么保證呢滑凉?首先统扳,利用貝葉斯公式有:
兩邊同時取log
然后兩邊同時用求期望喘帚,可以得:
等式左邊和沒有關(guān)系,是概率密度函數(shù)闪幽,積分是1啥辨,所以等式左邊依然是.
等式右邊第一項就是E-step里面的Q函數(shù),第二項我們記做H函數(shù)盯腌,則:
要保證,首先陨瘩,那么是不是保證滿足腕够,就一定有?答案是肯定的舌劳。(說明一下帚湘,這里面的H和Q函數(shù)都是關(guān)于的函數(shù),每一次迭代是已知的甚淡,他不是變量)
那下面只要證明就可以了大诸。
因此可以得到,則整個EM算法的收斂性證畢贯卦。
注:這里用到了Jessian不等式资柔,如果函數(shù)是convex的,則有函數(shù)的期望大于期望的函數(shù)撵割,即.
EM算法與ELOB和KL散度
上述EM算法的證明贿堰,有一些技巧性,而這些技巧性有沒有一種是在已知結(jié)論基礎(chǔ)上硬湊的感覺呢啡彬,尤其是用去求期望羹与,就是為了去構(gòu)造Q函數(shù)。那有沒有更好的解釋或者更為直觀的方式來得到相同的結(jié)論呢庶灿?答案是有的纵搁。
首先,仍然用到:
我們稍微變個型往踢,假設(shè)一個概率密度函數(shù):
兩邊同時用求期望:
其中等式右邊第一項腾誉,我們記做,可以稱為ELOB菲语,EvidenceLowerBound妄辩,第二項是和的KL散度。
如圖4所示山上,當(dāng)我固定參數(shù)時候眼耀,ELOB就是關(guān)于的泛函(只聽過沒學(xué)過,可理解為函數(shù)的函數(shù))佩憾,那ELOB的上界是什么呢哮伟?那首先要理解KL散度干花,KL散度是衡量兩個概率分布之間的差異性,如果兩個分布沒有差異楞黄,則KL散度等于0池凄,如果有差異則大于0,所以KL散度的最小值就是0鬼廓,那ELOB的上界就是此刻的似然函數(shù)肿仑。
在EM算法中,當(dāng)前迭代時碎税,參數(shù)尤慰,則對于E-step,我們需要使得ELOB最大雷蹂,即KL散度為0伟端,如圖5所示,其中為匪煌。此時责蝠,
對于M-Step,我們是需要得到新的估計參數(shù)萎庭,這個時候霜医,固定,重新獲得ELOB的最大值,這個時候的ELOB是什么樣的呢擎椰?
右邊第二項沒有參數(shù)支子,所以固定最大化ELOB,就等于最大化第一項达舒,而第一項是什么呢值朋?就是函數(shù)。
如圖6所示巩搏,我們最大化函數(shù)昨登,也就是最大化此次迭代的ELOB。在新的參數(shù)下贯底,丰辣,此刻不變,所以和新的在沒有達(dá)到局部(或者全局)極大值的情況下禽捆,是兩個不同的概率分布笙什,即二者KL散度是大于0的,那此刻的似然函數(shù)等于此刻的KL散度加上此刻的ELOB胚想,自然是有琐凭。
從ELOB和KL散度的層面可以更好的理解EM算法的迭代過程。
PRML一書中浊服,有圖7所示的示意圖统屈,能比較形象的說明胚吁,EM算法的迭代過程。
圖7中愁憔,紅色曲線表示(不完整數(shù)據(jù))對數(shù)似然函數(shù)腕扶,它的最大值是我們想要得到的。我們首先選擇某個初始的參數(shù)值,然后在第一個E步驟中,我們計算潛在變量上的后驗概率分布,得到了的一個更小的下界吨掌,它的值等于在處的對數(shù)似然函數(shù)值半抱,用藍(lán)色曲線表示。注意膜宋,下界與對數(shù)似然函數(shù)在處以切線的方式連接代虾,因此兩條曲線的梯度相同。這個界是一個凹函數(shù)激蹲,對于指數(shù)族分布的混合分布來說,有唯一的最大值江掩。在M步驟中,下界被最大化学辱,得到了新的值,這個值給出了比處更大的對數(shù)似然函數(shù)值。接下來的E步驟構(gòu)建了一個新的下界,它在處與對數(shù)似然函數(shù)切線連接,用綠色曲線表示环形。以這樣的方式不停迭代策泣,直到滿足條件。
高斯混合模型EM算法推導(dǎo)
了解了EM算法抬吟,我們來詳細(xì)推導(dǎo)高斯混合模型的E步和M步的內(nèi)容萨咕。這一部分內(nèi)容來自徐亦達(dá)老師的課件。由于公式太多了火本,我就放一些截圖危队,供大家一起學(xué)習(xí)和參考。
徐亦達(dá)老師的課件在:https://github.com/roboticcam/machine-learning-notes/blob/master/em.pdf
后續(xù)關(guān)于EM算法的應(yīng)用會舉例以下幾方面內(nèi)容
(1)Kmeans和高斯混合模型
(2)EM算法應(yīng)用之貝葉斯線性回歸
(3)EM算法應(yīng)用之PLSA
(4)EM算法應(yīng)用之缺失數(shù)據(jù)參數(shù)估計問題