(转载)机器学习知识点(十四)EM算法原理
1.引言
以前我們討論的概率模型都是只含觀測(cè)變量(observable variable), 即這些變量都是可以觀測(cè)出來(lái)的，那么給定數(shù)據(jù)，可以直接使用極大似然估計(jì)的方法或者貝葉斯估計(jì)的方法；但是當(dāng)模型含有隱變量(latent variable)的時(shí)候, 就不能簡(jiǎn)單地使用這些估計(jì)方法。
如在高斯混合和EM算法中討論的高斯混合就是典型的含有隱變量的例子，已經(jīng)給出EM算法在高斯混合模型中的運(yùn)用，下面我們來(lái)討論一些原理性的東西。
?
2.Jensen 不等式
令是值域?yàn)閷?shí)數(shù)的函數(shù)，那么如果，則就是一個(gè)凸函數(shù)，如果自變量 x 是向量, 那么當(dāng)函數(shù)的海森矩陣?是半正定時(shí)(),?是凸函數(shù)，這是函數(shù)為凸函數(shù)的條件在向量輸入時(shí)的泛化。
如果，則稱(chēng)是嚴(yán)格凸函數(shù)，對(duì)應(yīng)的向量輸入時(shí)的泛化是.
定理 ?令是一個(gè)凸函數(shù)，令是一個(gè)隨機(jī)變量，那么
當(dāng)時(shí)嚴(yán)格凸函數(shù)的時(shí)，當(dāng)且僅當(dāng)?以概率 1 成立的時(shí)，. 即當(dāng)時(shí)常量時(shí)，上面不等式的等號(hào)成立。
注意上面 E 是表示期望的意思，習(xí)慣上，在寫(xiě)變量期望的時(shí)候，會(huì)把緊跟括號(hào)略去，即.
用下面的圖對(duì)上面的定理作一個(gè)解釋：
這個(gè)圖中的實(shí)線代表凸函數(shù), 隨機(jī)變量有 0.5 的概率取 a, 同樣以 0.5 的概率取 b, 所以的期望位于a,b的正中間，即a,b的均值.
從圖中可以看出，在 y 軸上,?位于之間，因?yàn)槭峭购瘮?shù)，則必如上圖所示，
所以很多情況下，許多人并去記憶這個(gè)不等式，而是記住上面的圖，這樣更容易理解。
注意：如果是（嚴(yán)格）凹函數(shù)，即使（嚴(yán)格）凸函數(shù)（即，），那么Jensen不等式照樣成立，只不過(guò)不等號(hào)方向相反：
?
3.EM算法
假設(shè)在一個(gè)估計(jì)問(wèn)題中有m個(gè)獨(dú)立樣本，根據(jù)這些數(shù)據(jù)，希望擬合出模型的參數(shù)，那么對(duì)數(shù)似然函數(shù)：
這里，是隱變量，如果能夠被觀測(cè)出來(lái)，最大似然估計(jì)就會(huì)變得很容易，但是現(xiàn)在觀測(cè)不出來(lái)，是隱變量。
在這種情況下，EM算法給出了一種很有效的最大似然估計(jì)的方法：重復(fù)地構(gòu)造的下界（E步），然后最大化這個(gè)下界（M步）。
?
對(duì)于每個(gè)，令表示隱變量的分布，即，考慮：
由（2）到（3）的推導(dǎo)用到了上面的Jensen不等式，此時(shí)是一個(gè)凹函數(shù)，因?yàn)?#xff0c;考慮上面關(guān)于的分布，
正好是數(shù)量的期望，由Jensen不等式可以得到：
由此可以從（2）推出（3）.
?
但是由于隱變量的存在，直接最大化很困難！試想如果能讓直接與它的下界相等，那么任何可以使的下界增大的，也可以使增大，所以自然就是選擇出使的下界達(dá)到極大的參數(shù).
怎么樣才能使得取得下界呢，即上面不等式取等號(hào)，關(guān)鍵在于隱變量如何處理，下面就此討論。
現(xiàn)在，對(duì)于任意的分布，（3）給出了似然函數(shù)的下界. 對(duì)于分布到底是什么分布，可以有很多種選擇，到底該選擇哪一種呢？
?
在上面討論Jensen不等式的時(shí)候可以看出，不等式中等號(hào)成立的條件是隨機(jī)變量變成“常量”，對(duì)于要想取得下界值，必須要求
其中常數(shù) c 與變量?無(wú)關(guān)，這很容易做到，我們選擇分布的時(shí)候，滿足下面的條件即可：
由于，于是我們可以知道：
注意理解上面這個(gè)等式式子是如何得出來(lái)的！！
于是就可以把分布設(shè)定為：在參數(shù)下，給定后，的后驗(yàn)分布。
這樣設(shè)定好隱變量的分布之后，就直接取其下界，原來(lái)最大化似然函數(shù)的問(wèn)題轉(zhuǎn)換為最大化其下界，這就是E步！
在M步中，就是去調(diào)整參數(shù)最大化上面提到的式子（3）.
不斷重復(fù)E步和M步就是EM算法：
重復(fù)迭代直至收斂{
}
?
我們?nèi)绾沃?span style="margin:0px; padding:0px; color:rgb(51,102,255)">算法收斂呢？
假如和是兩次連續(xù)迭代后的參數(shù),需要證明.
正如上面所述，由于我們?cè)龠x擇分布時(shí)，選擇：，于是：
參數(shù)就是通過(guò)極大化上面右邊的式子得出，因此：
注意第不等式（4）來(lái)自于：
?
這個(gè)式子對(duì)于任意的和都成立，當(dāng)然對(duì)于和也成立。對(duì)于不等式（5），因?yàn)槭峭ㄟ^(guò)如下極大化過(guò)程選出來(lái)的：
所以在處，式子的值要比在處式子的值要大！
式子（6）是通過(guò)上面討論過(guò)的方法選擇出合適的使得Jensen不等式取等號(hào)！
因此，EM算法使得似然函數(shù)單調(diào)收斂。在上面描述EM算法的時(shí)候，說(shuō)是“重復(fù)迭代直至收斂”，一個(gè)常用的檢查收斂的方法是：如果兩次連續(xù)迭代之后，似然函數(shù)的值變化很小（在某個(gè)可容忍的范圍內(nèi)），就EM算法中的變化已經(jīng)很慢，可以停止迭代了。
?
注意：如果定義：
從之前的推導(dǎo)，我們知道.?EM算法看作是關(guān)于函數(shù) J 的梯度上升：E步是關(guān)于參數(shù)Q，M步是關(guān)于參數(shù).
?
?
4.高斯混合的修正
在?高斯混合和EM算法?中，我們將EM算法用于優(yōu)化求解高斯混合模型，擬合參數(shù)和.
E步：
這里表示的是在分布下，取的概率。
M步：考慮參數(shù)，最大化數(shù)值：
?
最大化求，對(duì)上面的式子關(guān)于求偏導(dǎo)數(shù)：
令這個(gè)偏導(dǎo)數(shù)為0，求出的更新方式：
這是在?高斯混合和EM算法?中已經(jīng)得出的結(jié)論。
再考慮如何更新參數(shù),把只與有關(guān)的項(xiàng)寫(xiě)出來(lái)，發(fā)現(xiàn)只需要最大化：
因?yàn)?#xff0c;，所有的和為1，所以這是一個(gè)約束優(yōu)化問(wèn)題，參考簡(jiǎn)易解說(shuō)拉格朗日對(duì)偶（Lagrange duality），構(gòu)造拉格朗日函數(shù)：
?
其中?β 是拉格朗日乘子. 求偏導(dǎo)數(shù)：
令偏導(dǎo)數(shù)為0，得到：
即：利用約束條件：，得到：(注意這里用到：).
于是可以得到參數(shù)的更新規(guī)則：
關(guān)于參數(shù)的更新規(guī)則，以及整個(gè)EM算法如何運(yùn)用到高斯混合模型的優(yōu)化，請(qǐng)參考：高斯混合和EM算法！
5.總結(jié)
所謂EM算法就是在含有隱變量的時(shí)候，把隱變量的分布設(shè)定為一個(gè)以觀測(cè)變量為前提條件的后驗(yàn)分布，使得參數(shù)的似然函數(shù)與其下界相等，通過(guò)極大化這個(gè)下界來(lái)極大化似然函數(shù)，從避免直接極大化似然函數(shù)過(guò)程中因?yàn)殡[變量未知而帶來(lái)的困難！EM算法主要是兩步,E步選擇出合適的隱變量分布（一個(gè)以觀測(cè)變量為前提條件的后驗(yàn)分布），使得參數(shù)的似然函數(shù)與其下界相等；M步：極大化似然函數(shù)的下界，擬合出參數(shù).
轉(zhuǎn)載：http://www.cnblogs.com/90zeng/p/EM_algorithm_theory.html
總結(jié)
以上是生活随笔為你收集整理的(转载)机器学习知识点(十四)EM算法原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： (转载)机器学习知识点(十三)吉布斯采样
- 下一篇： (转载)机器学习知识点(十五)从最大似然