EM算法及其推廣的幾種算法

姚紅娟　趙子龍　王會(huì)娟

摘 要 引入了可處理缺失數(shù)據(jù)的EM算法。EM算法是一種迭代算法，每一次迭代都能保證似然函數(shù)值增加，并且收斂到一個(gè)局部極大值。在此基礎(chǔ)上，本文也給出了推廣的幾種EM算法。

關(guān)鍵詞 EM算法 ECM算法 ECME算法 MCEC算法

中圖分類號(hào)：O212.1 文獻(xiàn)標(biāo)識(shí)碼：A

0前言

EM 算法是 Dempster Laind，Rubin 于 1977 年提出的求參數(shù)極大似然估計(jì)的一種方法，它可以從非完整數(shù)據(jù)集中對(duì)參數(shù)進(jìn)行 MLE 估計(jì)，是一種非常簡(jiǎn)單實(shí)用的學(xué)習(xí)算法。這種方法可以廣泛地應(yīng)用于處理缺損數(shù)據(jù)，截尾數(shù)據(jù)，帶有噪聲等所謂的不完全數(shù)據(jù)。本文主要說(shuō)明了EM算法的基本原理及其應(yīng)用，再針對(duì)它的加速收斂性引出了推廣的幾種EM算法，或稱為廣義的EM算法。

1 EM算法原理及其應(yīng)用

1.1 EM算法的思想及步驟

EM算法的每一次迭代有兩步組成：E步（求期望） 和M步（極大化）。一般的，以p（ |Y） 表示 的基于觀測(cè)數(shù)據(jù)的后驗(yàn)分布密度函數(shù)，稱為觀測(cè)后驗(yàn)分布， p（ |Y，Z） 表示添加數(shù)據(jù)Z后得到的關(guān)于 的后驗(yàn)分布密度函數(shù)，稱為添加后驗(yàn)分布，p（Z| ，Y） 表示在給定 和觀測(cè)數(shù)據(jù)Y下潛在數(shù)據(jù)Z的條件分布密度函數(shù)。我們的目的是計(jì)算觀測(cè)后驗(yàn)分布p（ |Y） 的眾數(shù)，于是，EM算法如下進(jìn)行。

E步：將p（ |Y，Z） log p（ |Y，Z）關(guān)于Z的條件分布求期望，從而把Z積掉，即

Q（（ | （i），Y）≡EZ[log p （ | Y， Z） | （i），Y （1）

M步：將Q（（ | （i），Y）極大化，即找一個(gè)點(diǎn) （i+1）使

Q（（ | （i），Y）=Q（（ | （i），Y） （2）

如此形成了一次迭代 （i）→ （i+1）。將上述E步和M步進(jìn)行迭代直至|| （i+1） （i）||或||Q（ （i+1）| （i），Y） Q（ （i）| （i），Y）||充分小時(shí)停止。

1.2 EM算法的優(yōu)缺點(diǎn)

EM算法是一種求參數(shù)極大似然估計(jì)的迭代算法，在處理不完全數(shù)據(jù)中有重要應(yīng)用。EM算法實(shí)現(xiàn)簡(jiǎn)單，數(shù)值計(jì)算穩(wěn)定，存儲(chǔ)量小，并具有良好的全局收斂性。但是，EM算法收斂速度相當(dāng)慢，只是次線性的收斂速度，這個(gè)缺點(diǎn)防礙了EM算法的應(yīng)用?，F(xiàn)已提出了多種加速EM算法收斂的方法。

2 推廣的幾種EM算法

2.1 ECM算法

EM 算法流行的原因有二：其一，M 步僅涉及完全數(shù)據(jù)極大似然，通常計(jì)算比較簡(jiǎn)單；其二，它的收斂是穩(wěn)定的，因?yàn)槊看蔚迫缓瘮?shù)是不斷增加的。但是如果完全數(shù)據(jù)對(duì)數(shù)似然的估計(jì)本身比較復(fù)雜時(shí)，EM 算法就不再有吸引力了，因此Meng 和Rubin （1993） 提出了 ECM 算法，這種算法的基本思想是用一系列的計(jì)算更加簡(jiǎn)單的CM 步來(lái)代替一個(gè)復(fù)雜的 M 步。當(dāng)M步?jīng)]有顯式的表達(dá)式時(shí)，CM步通常有顯式的表達(dá)式。即使 CM 步?jīng)]有顯式的表達(dá)式 ，但 ECM 算法通常更加穩(wěn)定，因?yàn)樗臉O大化是在更低維度（ dimension） 的參數(shù)空間中進(jìn)行的。

2.2 ECME算法

這種方法是由Liu and Rubin（ 1994） 提出的，它是ECM算法的推廣，在 ECM 算法中，CM 步是對(duì)完全數(shù)據(jù)對(duì)數(shù)似然函數(shù)的期望進(jìn)行極大化。同樣，可以把這種思想運(yùn)用到觀察數(shù)據(jù)對(duì)數(shù)似然上，也就是說(shuō)，在CM 步上，可以考慮在一定的約束條件下，對(duì)對(duì)數(shù)似然函數(shù)進(jìn)行極大化，因此就產(chǎn)生了ECME算法。

2.3 MCEM算法

而對(duì)于EM算法的E步，有時(shí)要獲得期望的顯式表示是不可能的，即使近似計(jì)算也很困難，這時(shí)用Monte Carlo方法來(lái)完成，就是所謂的MonteCarlo EM（MCEM） 方法。MCEM算法比較靈活，但是需要仔細(xì)選擇模擬容量和確保正確的收斂性準(zhǔn)則。我們可以通過(guò)增加迭代次數(shù)來(lái)提高模擬容量。除此以外，由于蒙特卡羅誤差，該EM算法不具有單調(diào)性，難以估計(jì)其收斂性。

3結(jié)論

EM算法可以應(yīng)用于醫(yī)學(xué)研究中，尤其是臨床醫(yī)學(xué)中十分常見(jiàn)的一種數(shù)據(jù)觀測(cè)形式為重復(fù)觀測(cè)，其特點(diǎn)是在同一實(shí)驗(yàn)單位上進(jìn)行多次重復(fù)觀測(cè)，這個(gè)過(guò)程由于各種原因經(jīng)常導(dǎo)致實(shí)驗(yàn)觀測(cè)數(shù)據(jù)缺失。本文給出了EM算法的基本思想，并給出了幾種推廣的EM算法，其應(yīng)用范圍更加廣泛。

參考文獻(xiàn)

[1] 茆詩(shī)松，王靜龍，濮曉龍.高等數(shù)理統(tǒng)計(jì)[M].北京：高等教育出版社，1998.

[2] 楊基棟.EM算法理論及其應(yīng)用[J].安慶師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2009，15（4）：30-35.

[3] 陳長(zhǎng)生，王彤，徐勇勇，尚磊.醫(yī)學(xué)科研中缺失數(shù)據(jù)的EM估計(jì)[J].第四軍醫(yī)大學(xué)學(xué)報(bào)，2002，23（1）：59-61.