EM算法

EM算法作為數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法之一条摸，在統(tǒng)計學(xué)習(xí)領(lǐng)域也有諸多應(yīng)用。EM算法（Expectation-maximization algorithm铸屉，期望極大算法）在統(tǒng)計中被用于尋找依賴于不可觀察的隱性變量的概率模型中參數(shù)的最大似然估計钉蒲。

期望極大算法經(jīng)過兩個步驟交替進行計算，第一步是計算期望（E）抬探，利用對隱藏變量的現(xiàn)有估計值，計算其最大似然估計值帆赢；第二步是極大化（M）小压，極大化在E步上求得的最大似然值來計算參數(shù)的值。M步上找到的參數(shù)估計值被用于下一個E步計算中椰于，這個過程不斷交替進行怠益。

1、EM算法引入

在引入EM算法之前瘾婿，我們先回顧一下最大似然估計方法蜻牢。

(https://web.stanford.edu/class/cs109/lectureNotes/21%20-%20MLE.pdf)

最大似然法（MLE）的思想很樸素，首先假設(shè)參數(shù)為 $\theta$ 偏陪，然后寫出在 $\theta$ 下生成當(dāng)前各獨立樣本的可能性（Likelihood）抢呆，上圖解釋了這里的Likelihood是什么含義——聯(lián)合概率（離散）或聯(lián)合概率密度（連續(xù)）。然后我們求使得這個Likelihood最大的參數(shù)值 $\theta$ 作為我們的參數(shù)估計笛谦。

最大似然法可以發(fā)揮作用的隱含前提是我們可以觀測到各獨立樣本抱虐，且這些樣本就是從服從依賴于 $\theta$ 的分布中生成的。

那么EM算法是用來解決什么問題呢饥脑？EM算法用來解決既含有觀測變量又含有隱變量或潛在變量的參數(shù)估計問題恳邀。所謂隱變量懦冰，就是無法直接觀測到的變量，但它又與可觀測變量的生成密切相關(guān)谣沸，比如混合高斯模型中某個變量（樣本）屬于各個高斯成分的概率就是隱變量刷钢。《統(tǒng)計學(xué)習(xí)方法》中舉了一個很生動的例子：

假設(shè)有3枚硬幣乳附，分別記作A内地，B，C许溅。這些硬幣正面出現(xiàn)的概率分別是 $\pi$ 瓤鼻，p和q。進行如下擲硬幣試驗：先擲硬幣A贤重，根據(jù)其結(jié)果選出硬幣B或硬幣C茬祷，正面選硬幣B，反面選硬幣C并蝗；然后擲選出的硬幣祭犯，擲硬幣的結(jié)果出現(xiàn)正面記作1，出現(xiàn)反面記作0滚停；獨立地重復(fù)n次試驗（這里沃粗，n＝10），觀測結(jié)果如下：

$1,1,0,1,0,0,1,0,1,1$

假設(shè)只能觀測到擲硬幣的結(jié)果键畴，不能觀測擲硬幣的過程最盅。問如何估計三硬幣正面出現(xiàn)的概率，即三硬幣模型的參數(shù)起惕。

下面我們試著寫出其似然函數(shù)涡贱。記 $\theta=(\pi,p,q)$ 是模型參數(shù)， $y$ 是觀測變量惹想，表示一次實驗的觀測結(jié)果是1或0问词， $z$ 是隱變量，表示為觀測到的擲硬幣 $A$ 的結(jié)果嘀粱。則Likelihood可寫作：

$\begin{aligned} P(y|\theta)&=\sum_{z}P(y,z|\theta)=\sum_{z}P(z|\theta)P(y|z,\theta)\\ &=\pi p^y(1-p)^{1-y}+(1-\pi)q^y(1-q)^{1-y}\\ \end{aligned}$

觀測數(shù)據(jù) $Y＝(Y_1,Y_2,\dots,Y_n)^T$ 未觀測數(shù)據(jù) $Z＝(Z_1,Z_2,\dots,Z_n)^T$ 則觀測數(shù)據(jù)的似然函數(shù)為：

$\begin{aligned} P(Y|\theta)&=\Pi_{j=1}^nP(y|\theta)\\ &=\Pi_{j=1}^n[\pi p^{y_j}(1-p)^{1-y_j}+(1-\pi)q^{y_j}(1-q)^{1-y_j}] \end{aligned}$

《統(tǒng)計學(xué)習(xí)方法》一書上說這個似然函數(shù)的極大似然估計是沒有解析解的激挪，因此我們就需要用更巧妙的方法來逼近這個解。EM算法就是通過逼近的過程來解決這樣的問題锋叨。

2垄分、EM算法導(dǎo)出

現(xiàn)在我們把問題從三硬幣問題中抽象出來： $Y$ 表示觀測變量， $Z$ 表示隱隨機變量娃磺， $Y$ 和 $Z$ 一起稱為完全數(shù)據(jù)锋喜， $Y$ 稱為不完全數(shù)據(jù)。 $\theta$ 表示模型參數(shù)。給定觀測數(shù)據(jù) $Y$ 嘿般，我們的目標是極大化 $Y$ 關(guān)于參數(shù) $\theta$ 的對數(shù)似然函數(shù)段标，即極大化：

$L(\theta)=logP(Y|\theta)=log\sum_Z P(Y,Z|\theta)=log(\sum_Z P(Y|Z,\theta)P(Z|\theta))$

這一極大化的主要困難在于：

上式中有未觀測數(shù)據(jù)
上式中包含和（或積分）的對數(shù)

既然不能直接極大化似然函數(shù)，那么我們就希望可以通過某種迭代的方式使得 $L(\theta)$ 不斷增大炉奴。假設(shè)在第 $i$ 次之后的 $\theta$ 估計值為 $\theta^{(i)}$ 逼庞，則我們希望新估計值 $\theta$ 滿足：

$L(\theta)>L(\theta^{(i)})$

為此，考慮兩者之差并利用Jensen不等式得到其下界：

$\begin{aligned} L(\theta)-L(\theta^{(i)}) &=log(\sum_Z P(Z|Y,\theta^{(i)})\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})})-logP(Y|\theta^{(i)})\\ &\geq \sum_Z P(Z|Y,\theta^{(i)})log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})}-logP(Y|\theta^{(i)})\\ &=\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\\ \end{aligned}$

從而有：

$L(\theta)\geq L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}$

定義這個下界為：

$B(\theta,\theta^{(i)})=L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}$

則有：

$L(\theta)\geq B(\theta,\theta^{(i)})$

若我們?nèi)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Ctheta%3D%5Ctheta%5E%7B(i)%7D" alt="\theta=\theta^{(i)}" mathimg="1">可以得到：

$\begin{aligned} B(\theta^{(i)},\theta^{(i)})&=L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y|Z,\theta^{(i)})P(Z|\theta^{(i)})}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\\ &=L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y,Z|\theta^{(i)})}{P(Y,Z|\theta^{(i)})}=L(\theta^{(i)})\\ \end{aligned}$

因此任何可以使 $B(\theta,\theta^{(i)})$ 增大的 $\theta$ 瞻赶，都可以使 $L(\theta)$ 增大赛糟。為了使 $L(\theta)$ 有盡可能大的增長，我們應(yīng)該選擇使得 $B(\theta,\theta^{(i)})$ 達到極大的值砸逊，即：

$\theta^{(i+1)}=arg \max_{\theta} B(\theta,\theta^{(i)})$

下面我們省去對 $\theta$ 的極大化而言是常數(shù)的項：

$\begin{aligned} \theta^{(i+1)}&=arg \max_{\theta} (L(\theta^{(i)}+\sum_Z P(Z|Y,\theta^{(i)})log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})})\\ &=arg \max_{\theta}(\sum_Z P(Z|Y,\theta^{(i)})logP(Y|Z,\theta)P(Z|\theta))\\ &=arg \max_{\theta}(\sum_Z P(Z|Y,\theta^{(i)})logP(Y,Z|\theta))\\ \end{aligned}$

我們定義 $Q(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})logP(Y,Z|\theta)$ 璧南，則：

$\theta^{(i+1)}=arg \max_{\theta} Q(\theta,\theta^{(i)})$

從而我們就可以迭代地更新參數(shù) $\theta$ ，使得對數(shù)似然函數(shù) $L(\theta)$ 不斷增大师逸∷疽校總結(jié)成EM算法如下：

（1）選擇模型參數(shù)初始值 $\theta^{(0)}$
（2）E步：計算 $Q(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})logP(Y,Z|\theta)$
（3）M步： $\theta^{(i+1)}=arg \max_{\theta} Q(\theta,\theta^{(i)})$
（4）重復(fù)E步M步直至收斂。

我們看到（4）默認了EM算法的收斂性篓像，下面我們來證明這一點动知。

3恬口、EM算法的收斂性

為了證明EM算法的收斂性粱坤，我們首先說明由EM算法估計得到的似然函數(shù)序列 $P(Y|\theta^{(i)})$ 是單調(diào)遞增的躯护，即：

$P(Y|\theta^{(i+1)})\geq P(Y|\theta^{(i)})$

由

$P(Y|\theta)=\frac{P(Y,Z|\theta)}{P(Z|Y,\theta)}$

取對數(shù)有

$\log P(Y|\theta)=\log P(Y,Z|\theta)-\log P(Z|Y,\theta)$

令

$Q(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})logP(Y,Z|\theta)$
$H(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})logP(Z|Y,\theta)$

則對數(shù)似然函數(shù)可以寫成：

$\log P(Y|\theta)=Q(\theta,\theta^{(i)})-H(\theta,\theta^{(i)})$

從而

$\begin{aligned} & \log P(Y|\theta^{(i+1)})-log P(Y|\theta^{(i)})\\ & =[Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})]-[H(\theta^{(i+1)},\theta^{(i)})-H(\theta^{(i)},\theta^{(i)})] \end{aligned}$

我們知道 $\theta^{(i+1)}$ 使得 $Q(\theta,\theta^{(i)})$ 達到極大鸵熟，因此

$Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})\geq 0$

又

$\begin{aligned} &H(\theta,\theta^{(i+1)})-H(\theta,\theta^{(i)})\\ &=\sum_Z P(Z|Y,\theta^{(i)})log(\frac{P(Z|Y,\theta^{(i+1)})}{P(Z|Y,\theta^{(i)})})\\ & \leq log(\sum_Z \frac{P(Z|Y,\theta^{(i+1)})}{P(Z|Y,\theta^{(i)})}P(Z|Y,\theta^{(i)}))\\ &=log(\sum_Z P(Z|Y,\theta^{(i+1)}))\\ &=0 \end{aligned}$

故

$logP(Y|\theta^{(i+1)})-logP(Y|\theta^{(i)})\geq 0$

因此，如果 $P(Y|\theta^{(i)})$ 有上界宵蕉，則 $L(\theta^{(i)})=logP(Y|\theta^{(i)})$ 收斂到某個值 $L^*$ 享郊。

最后編輯于：2019.08.10 18:07:52

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末搪哪，一起剝皮案震驚了整個濱河市宋税，隨后出現(xiàn)的幾起案子摊崭，更是在濱河造成了極大的恐慌，老刑警劉巖弃甥，帶你破解...
沈念sama閱讀 206,723評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件爽室，死亡現(xiàn)場離奇詭異汁讼，居然都是意外死亡淆攻，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,485評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門嘿架，熙熙樓的掌柜王于貴愁眉苦臉地迎上來瓶珊，“玉大人，你說我怎么就攤上這事耸彪∩∏郏” “怎么了？”我有些...
開封第一講書人閱讀 152,998評論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長唱较。經(jīng)常有香客問我扎唾，道長，這世上最難降的妖魔是什么南缓？我笑而不...
開封第一講書人閱讀 55,323評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任胸遇，我火速辦了婚禮，結(jié)果婚禮上汉形，老公的妹妹穿的比我還像新娘纸镊。我一直安慰自己，他們只是感情好概疆，可當(dāng)我...
茶點故事閱讀 64,355評論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布逗威。她就那樣靜靜地躺著，像睡著了一般岔冀。火紅的嫁衣襯著肌膚如雪凯旭。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,079評論 1贊 285
城市分裂傳說
那天楣颠，我揣著相機與錄音尽纽，去河邊找鬼。笑死童漩，一個胖子當(dāng)著我的面吹牛弄贿，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播矫膨，決...
沈念sama閱讀 38,389評論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼差凹，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了侧馅？” 一聲冷哼從身側(cè)響起危尿，我...
開封第一講書人閱讀 37,019評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎馁痴，沒想到半個月后谊娇，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,519評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡罗晕，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 35,971評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年济欢，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片小渊。...
茶點故事閱讀 38,100評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡法褥，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出酬屉，到底是詐尸還是另有隱情半等，我是刑警寧澤揍愁，帶...
沈念sama閱讀 33,738評論 4贊 324
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站杀饵，受9級特大地震影響莽囤，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜切距，卻給世界環(huán)境...
茶點故事閱讀 39,293評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一烁登、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧蔚舀，春花似錦饵沧、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,289評論 0贊 19
一樁弒父案狼牺，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至礼患，卻和暖如春是钥，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背缅叠。一陣腳步聲響...
開封第一講書人閱讀 31,517評論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工悄泥，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人肤粱。一個月前我還...
沈念sama閱讀 45,547評論 2贊 354
代替公主和親
正文我出身青樓弹囚，卻偏偏與公主長得像，于是被迫代替她去往敵國和親领曼。傳聞我的和親對象是個殘疾皇子鸥鹉，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 42,834評論 2贊 345

EM算法

1、EM算法引入

2垄分、EM算法導(dǎo)出

3恬口、EM算法的收斂性

推薦閱讀更多精彩內(nèi)容