周志華老師在《機器學(xué)習(xí)》里這樣評價 EM算法：EM算法是最常見的隱變量估計方法咖气，在機器學(xué)習(xí)里有著極為廣泛的用途牙甫，例如常被用來學(xué)習(xí)高斯混合模型（Gaussian mixture model伏伐，簡稱GMM）的參數(shù)隘竭。K均值算法就是一個典型的 EM算法渊抽。
EM算法是怎樣的隱變量估計方法达传？
《機器學(xué)習(xí)》這樣描述隱變量估計方法（見7.6）：我們一直假設(shè)訓(xùn)練樣本所有屬性變量的值都已被觀測到，即訓(xùn)練樣本是完整的劳吠。但在現(xiàn)實應(yīng)用中往往會遇到“不完整”的訓(xùn)練樣本引润，例如由于西瓜的根蒂已脫落，無法看出是“卷縮”還是“硬挺”痒玩，則訓(xùn)練樣本的“根蒂”屬性變量值未知淳附。未觀測變量的學(xué)名是“隱變量”（latent variable）。EM（Expectation-Maximization）算法 [ Dempstert et al.,1977] 是常用的估計參數(shù)隱變量的利器凰荚，它是一種迭代式的方法燃观。EM算法使用兩個步驟交替計算：第一步是期望（E）步褒脯，利用當(dāng)前估計的參數(shù)值來計算對數(shù)似然的期望值;第二步是最大化（M）步便瑟，尋找能使 E步產(chǎn)生的似然期望最大化的參數(shù)值。然后番川，新的到的參數(shù)值重新被用于 E步到涂，直至收斂到局部最優(yōu)解。
2008年自然雜志發(fā)表過這樣一篇文章 What is the expectation maximization algorithm?（什么是EM算法颁督，什么是EM算法? ）践啄，用投硬幣的例子介紹了 EM算法，硬幣是常見的物品沉御，用來理解 EM算法可能會更容易一些屿讽。
這篇科普文基本沒有什么“像樣”的公式，對于受過專業(yè)訓(xùn)練的人而言，公式或許更有利于他們理解算法的基本原理伐谈，但對普通讀者而言烂完，太多的公式，只會嚇走他們诵棵。
如下圖所示抠蚣，有兩個硬幣 A和 B，其中一個的密度不是很均勻履澳，出現(xiàn)正面的概率會大一些嘶窄，我們想知道這個硬幣是哪一個。然后我們做了下面這個試驗距贷，隨機取出一枚硬幣柄冲，記下是 A硬幣還是 B硬幣，并連續(xù)拋10次忠蝗，記錄下每次拋出的結(jié)果（正面或背面）羊初，這樣的試驗總共做了5次，結(jié)果如下圖什湘。
很明顯长赞，如果我們記錄好每次拋的是哪一個硬幣，以及出現(xiàn)正面或背面的結(jié)果闽撤，我們就能夠用某種方法（例如極大似然估計法）估計出每個硬幣出現(xiàn)正面的概率得哆，這個例子中 A硬幣出現(xiàn)正面的概率估計值是0.8，B硬幣出現(xiàn)正面的概率估計值是0.45哟旗。通過試驗和計算贩据，我們可以判斷出哪一個硬幣更容易出現(xiàn)正面，以及相應(yīng)的概率估計值闸餐。
然而饱亮，生活并不是那么如意的。如果做試驗的伙計忘記了記錄每次拋的是哪一個硬幣舍沙，那么他就無法從記錄中區(qū)分哪一些是來自 A硬幣的近上，哪一些是來自 B硬幣的，也就是說拂铡，我們沒辦法估計 A硬幣或 B硬幣出現(xiàn)正面的概率壹无。
難道只能重新做試驗嗎？辦法是有的感帅，例如 EM算法斗锭。
如下圖所示，由于沒有記錄每次試驗選的是哪枚硬幣失球，這個未觀測變量就是隱變量岖是，我們只得到一堆 H（正面）或 T（背面）的記錄，但是我們?nèi)匀豢梢酝ㄟ^某種方法估計出 A硬幣和 B硬幣在每次試驗中出現(xiàn)的概率值。例如投硬幣試驗可以看作多重伯努利試驗豺撑，如果我們先給出 A硬幣和 B硬幣出現(xiàn)正面概率的硬估值（更準確的說是初始值）作箍，再結(jié)合每次試驗出現(xiàn) H或 T的次數(shù)，通過二項分布公式前硫，我們就可以得出 A硬幣和 B硬幣在每次試驗中出現(xiàn)的概率估計值（E-Step）胞得。通過這種辦法，我們把之前因為隱變量無法分清的試驗結(jié)果給“分清”了屹电，這樣我們就又回到了上圖中極大似然估計的路線上阶剑，而極大似然估計方法又幫助我們更新了 A硬幣和 B硬幣出現(xiàn)正面的概率估計值（M-Step），這對值較之前的硬估值有了很大改變危号，但我們?nèi)圆粷M意這樣的結(jié)果牧愁，把這對值再次投入到 E-Step 和 M-Step 中。經(jīng)過多次迭代后外莲，在滿足一定條件下猪半，輸出 A硬幣出現(xiàn)正面的概率估計值是0.80，B硬幣出現(xiàn)正面的概率估計值是0.52偷线，這和上圖有完整數(shù)據(jù)情況下用極大似然估計方法得到的結(jié)果磨确，已經(jīng)非常接近了。
關(guān)于 EM算法的實現(xiàn)声邦，參考的是杜克大學(xué)的計算統(tǒng)計學(xué)網(wǎng)站 EM算法實現(xiàn)乏奥。該網(wǎng)站提供了五種輸出一致的Python腳本，我們從中選擇一種比較簡潔的腳本亥曹，如下圖所示邓了。
我們把這段 Python腳本改寫成 R腳本，看看可不可以更加簡潔一些媳瞪。
Fong Chun Chan's Blog 提供了用 EM算法求高斯混合分布參數(shù)的 R腳本。其中蛇受，他用 k 均值聚類方法得到的聚類結(jié)果作為作為初始估計值（用他的話是 hard-labels）句葵，然后通過 EM算法得到最終的聚類結(jié)果（soft-labels），這種思路是極好的龙巨。我自己做得不夠好的地方就是笼呆，我常常做完粗糙的 hard-labels后，就收工了旨别，而沒有去思考怎么去做更精細的 soft-labels。
簡言之汗茄，如果有不完整數(shù)據(jù)出現(xiàn)（例如數(shù)據(jù)缺失）秸弛，都可以用到 EM算法，或者是用上 EM算法的思路。思路可能更重要递览，因為在生產(chǎn)環(huán)境中叼屠，對算法性能的要求更高，我們可能更多用到的是一些“高大上”的工具绞铃，而不是自己去造工具镜雨。但當(dāng)我們把各種工具連接起來的時候，對這些工具的理解就顯得尤為重要了儿捧。
更重要的是荚坞，如果一個企業(yè)開發(fā)和算法有關(guān)的產(chǎn)品或服務(wù)，項目組內(nèi)的成員對算法的理解南轅北轍菲盾，這樣的產(chǎn)品或服務(wù)即使開發(fā)出來颓影，也很難被客戶接受。所以懒鉴，在數(shù)據(jù)時代诡挂，對全員的算法方面的認知培訓(xùn)是必要的，算法工程師也應(yīng)該盡可能的將抽象的算法轉(zhuǎn)換為能為更多人所接受的知識临谱。
寫本文的初衷璃俗，是希望有一種和同事們進行溝通的媒介，或者作為一種和程序員交流的游戲悉默，基于 Python 和 R 的 EM算法已經(jīng)有了旧找，Java 或 PHP 程序員接個龍好不好啊麦牺？
參考：
[1] 周志華 《機器學(xué)習(xí)》
[2] http://ai.stanford.edu/%7Echuongdo/papers/em_tutorial.pdf? 什么是 EM算法
[3] http://people.duke.edu/%7Eccc14/sta-663/EMAlgorithm.html EM算法實現(xiàn)
[4] http://tinyheero.github.io/2016/01/03/gmm-em.html 用EM算法求GMM參數(shù)
