EM演算法存在的意義是什麼？

01-13

對於含有隱變數的問題，直接使用最大似然估計(MLE)似乎也是可行的。MLE方法需要解一個非線性方程組，雖然難以求得最優解，但EM演算法也很難求得最優解呀！是因為EM演算法收斂速度更快，還是什麼原因，使得EM演算法這麼流行呢？

Hinton, 這個深度學習的締造者( 參考攢說 Geoff Hinton ) ， Jordan 當世概率圖模型的集大成者（參考「喬丹上海行」），他們碰撞的領域就是EM演算法！這個是PCA外的，另外一個無監督學習的經典。

他們怎麼認識的呢？Jordan的導師，就是著名的鏈接主義核心人物Rumelhart

為什麼說EM演算法是他們強強發力的領域呢？

這裡我們討論Hinton和統計大神Jordan的強強發力的領域。當Bayes網路發展到高級階段，概率圖模型使得計算成為問題，由此開啟了Variational Bayes領域。在「變の貝葉斯」裡面，我們解釋了研究Variational Bayes，有3撥人。第一撥人，把物理的能量搬到了機器學習（參考「給能力以自由吧！」）。第二撥人，就是Hinton，他將VB和EM演算法聯繫了起來，奠定了現在我們看到的VB的基礎。第三撥人，就是Jordan，他重建了VB的框架ELBO的基礎。所以說EM演算法擴展的VBEM演算法，就是Hinton和Jordan共同發力的部分。

Hinton曾在採訪中，不無感慨的說到，他當時研究VB和EM演算法的關係的時候，主動去請教當時的EM演算法的大佬們，結果那些人說Hinton是異想天開，神經有問題。但是最終，他還是突破重圍，搞定了VBEM演算法，打下了VB世界最閃光的那盞燈。老爺子真心不容易！如果想切實深入到VB的世界，我推薦Daphne Koller的神書「Probabilistic Graphical Models: Principles and Techniques」，尤其其中的第8章：The Exponential Family 和第19章 Partially Observed Data。這兩章幾乎是Hinton對VBEM演算法研究的高度濃縮。國內機器學習牛人王飛躍老師，率領各路弟子花了5年時間翻譯了這本神書！所以有中文版，買了，反覆閱讀8、19章，要的！

為什麼無監督深度學習突出成果都是Hinton和Jordan家的？

無監督深度學習，除了強化學習，主要包括BM、自動編碼器AE和GAN領域。 1）這些領域中的DBN和DBM是Hinton搞的。2）AE中的經典，VAE是DP Kingma和M Welling搞得。 DP Kingma碩士導師是LeCun，LeCun的博士後導師是Hinton，並且Welling的博士後導師是Hinton。 3）而GAN是Ian Goodfellow和Yoshua Bengio的傑作， Goodfellow是Bengio的學生，而Bengio的博士後導師是Jordan。一句話，無監督深度學習的經典模型幾乎全是Hinton和Jordan家的。為什麼？因為能徹底理解EM演算法到深不見底的人非Hinton和Jordan莫屬。

你現在明白徹底理解EM演算法的重要性了吧？下面我淺薄的縱向理解（忽略EM的各種變種的橫向）EM演算法的9層境界，再回頭反思一下Hinton和Jordan等會對EM演算法的理解到何種程度，簡直嘆而觀止！

EM演算法理解的九層境界

EM 就是 E + M
EM 是一種局部下限構造
K-Means是一種Hard EM演算法
從EM 到廣義EM
廣義EM的一個特例是VBEM
廣義EM的另一個特例是WS演算法
廣義EM的再一個特例是Gibbs抽樣演算法
WS演算法是VAE和GAN組合的簡化版
KL距離的統一

第一層境界， EM演算法就是E 期望 + M 最大化

最經典的例子就是拋3個硬幣，跑I硬幣決定C1和C2，然後拋C1或者C2決定正反面，然後估算3個硬幣的正反面概率值。

這個例子為什麼經典，因為它告訴我們，當存在隱變數I的時候，直接的最大似然估計無法直接搞定。 什麼是隱變數？為什麼要引入隱變數？對隱變數的理解是理解EM演算法的第一要義！Chuong B Do Serafim Batzoglou的Tutorial論文「What is the expectation maximization algorithm?」對此有詳細的例子進行分析。

通過隱變數，我們第一次解讀了EM演算法的偉大！突破了直接MLE的限制（不詳細解釋了）。

至此，你理解了EM演算法的第一層境界，看山是山。

第二層境界， EM演算法就一種局部下限構造

如果你再深入到基於隱變數的EM演算法的收斂性證明，基於log(x)函數的Jensen不等式構造，我們很容易證明，EM演算法是在反覆的構造新的下限，然後進一步求解。

所以，先固定當前參數，計算得到當前隱變數分布的一個下屆函數，然後優化這個函數，得到新的參數，然後循環繼續。

也正是這個不停的構造下限的思想未來和VB方法聯繫起來了。如果你理解了這個，恭喜你，進入理解EM演算法的第二層境界， 看山看石。

第三層境界， K-均值方法是一種Hard EM演算法

在第二層境界的基礎上，你就能隨意傲遊EM演算法用到GMM和HMM模型中去了。尤其是對GMM的深入理解之後，對於有隱變數的聯合概率，如果利用高斯分布代入之後：

很容易就和均方距離建立聯繫：

但是，能不能說K-均值就是高斯分布的EM演算法呢？不是，這裡雖然拓展到了相同的距離公式，但是背後邏輯還是不一樣，不一樣在哪裡呢？K-均值在討論隱變數的決定時候，用的是dirac delta 分布，這個分布是高斯分布的一種極限。

如果你覺得這個擴展不太好理解，那麼更為簡單直觀的就是， k-均值用的hard EM演算法，而我們說的EM演算法是soft EM演算法。所謂hard 就是要麼是，要麼不是0-1抉擇。而Soft是0.7比例是c1，0.3比例是c2的情況。

那麼充分理解了k-均值和EM演算法本身的演化和差異有什麼幫助呢？讓你進一步理解到隱變數是存在一種分布的。

如果你理解了這個，恭喜你，進入理解EM演算法的第三層境界，看山看峰。

第四層境界，EM 是廣義EM的特例

通過前3層境界，你對EM演算法的理解要跨過隱變數，進入隱分布的境界。如果我們把前面的EM收斂證明稍微重複一下，但是引入隱分布。

這樣我們把Jensen不等收右邊的部分定義為自由能（如果你對自由能有興趣，請參考「給能量以自由吧！」，如果沒有興趣，你就視為一種命名）。那麼E步驟是固定參數優化隱分布， M步驟是固定隱分布優化參數，這就是廣義EM演算法了。

有了廣義EM演算法之後，我們對自由能深入挖掘，發現自由能和似然度和KL距離之間的關係：

所以固定參數的情況下，那麼只能最優化KL距離了，那麼隱分布只能取如下分布：

而這個在EM演算法裡面是直接給出的。所以EM演算法是廣義EM演算法的天然最優的隱分布情況。 但是很多時候隱分布不是那麼容易計算的！

前面的推理雖然很簡單，但是要理解到位真心不容易，首先要深入理解KL距離是如何被引入的？

其次要理解，為什麼傳統的EM演算法， 不存在第一個最優化？因為在沒有限制的隱分布（天然情況下）情況下，第一個最優就是要求：

而這個隱分布， EM演算法裡面是直接給出的，而不是讓你證明得到的。

這樣，在廣義EM演算法中，你看到兩個優化步驟，我們進入了兩個優化步驟理解EM演算法的境界了。如果你理解了這個，恭喜你，進入理解EM演算法的第四層境界，有水有山。

第五層境界，廣義EM的一個特例是VBEM

在隱分布沒有限制的時候，廣義EM演算法就是EM演算法，但是如果隱分布本身是有限制的呢？譬如有個先驗分布的限制，譬如有計算的限制呢？

例如先驗分布的限制：從pLSA到LDA就是增加了參數的先驗分布！

例如計算上的限制：mean-field計算簡化的要求，分量獨立。

諸如此類限制，都使得廣義EM裡面的第一步E優化不可能達到無限制最優，所以KL距離無法為0。

基於有限制的理解，再引入模型變分的思想，根據模型m的變化，對應參數和隱變數都有相應的分布：

並且滿足分布獨立性簡化計算的假設：

在變分思想下，自由能被改寫了：

這樣我們就得到了VBEM演算法了：

如果你理解了這個，恭喜你，進入理解EM演算法的第五層境界，水轉山回。

第六層境界，廣義EM的另一個特例是WS演算法

Hinton老爺子搞定VBEM演算法後，並沒有停滯，他在研究DBN和DBM的Fine-Tuning的時候，提出了Wake-Sleep演算法。我們知道在有監督的Fine-Tuning可以使用BP演算法，但是無監督的Fine-Tuning，使用的是Wake-Sleep演算法。

就是這個WS演算法，也是廣義EM演算法的一種特例。 WS演算法分為認知階段和生成階段。

在前面自由能裡面，我們將KL距離引入了，這裡剛好這兩個階段分別優化了KL距離的兩種形態。固定P優化Q，和固定Q優化P。

所以當我們取代自由能理解，全部切換到KL距離的理解，廣義EM演算法的E步驟和M步驟就分別是E投影和M投影。因為要求KL距離最優，可以等價於垂直。而這個投影，可以衍生到數據D的流形空間，和模型M的流形空間。

所以你認同WS演算法是一種廣義EM演算法（GEM）之後，基於KL距離再認識GEM演算法。引入了數據流形和模型流形。引入了E投影和M投影。

不過要注意的wake識別階段對應的是M步驟，而sleep生成階段對應的E步驟。所以WS演算法對應的是廣義ME演算法。如果你理解了這個，恭喜你，進入理解EM演算法的第六層境界，山高水深。

第七層境界，廣義EM的再一個特例是Gibbs Sampling

其實，前面基於KL距離的認知，嚴格放到信息理論的領域，對於前面E投影和M投影都有嚴格的定義。 M投影的名稱是類似的，但是具體是moment projection，但是E投影應該叫I投影，具體是information projection。

上面這種可能不太容易體會到M投影和I投影的差異，如果再回到最小KL距離，有一個經典的比較。可以體會M投影和I投影的差異。 上面是I投影，只覆蓋一個峰。下面是M投影，覆蓋了兩個峰。

當我們不是直接計算KL距離，而是基於蒙特卡洛抽樣方法來估算KL距離。

有興趣對此深入的，可以閱讀論文「On Monte Carlo methods for estimating ratios of normalizing constants」

這時候，廣義EM演算法，就是Gibbs Sampling了。所以Gibbs Sampling，本質上就是採用了蒙特卡洛方法計算的廣義EM演算法。

所以，如果把M投影和I投影看成是一個變數上的最小距離點，那麼Gibbs Sampling和廣義EM演算法的收斂過程是一致的。

VAE的發明者，Hinton的博士後， Max Welling在論文「Bayesian K-Means as a 「Maximization-Expectation」 Algorithm」中，對這種關係有如下很好的總結！

另外， Zoubin Ghahramani， Jordan的博士，在「Factorial Learning and the EM Algorithm」等相關論文也反覆提到他們之間的關係。

這樣，通過廣義EM演算法把Gibbs Sampling和EM， VB， K-Means和WS演算法全部聯繫起來了。有了Gibbs Sampling的背書，你是不是能更好的理解，為什麼WS演算法可以是ME步驟，而不是EM的步驟呢？另外，我們知道坐標下降Coordinate Descent也可以看成一種Gibbs Sampling過程，如果有人把Coordinate Descent和EM演算法聯繫起來，你還會覺得奇怪么？

現在我們發現VB和Gibbs Sampling都可以放到廣義EM的大框架下，只是求解過程一個採用近似逼近，一個採用蒙特卡洛採樣。有了EM演算法和Gibbs Sampling的關係，現在你理解，為什麼Hinton能夠發明CD演算法了么？細節就不展開了。

如果你理解了這個，恭喜你，進入理解EM演算法的第七層境界，山水輪迴。

第八層境界，WS演算法是VAE和GAN組合的簡化版

Jordan的弟子邢波老師，他的學生胡志挺，發表了一篇文章， On Unifying Deep Generative Models，試圖通過WS演算法，統一對VAE和GAN的理解。

對VAE的理解，變了加了正則化的KL距離，而對於GAN的理解變成了加Jensen–Shannon 散度。所以，當我們把廣義EM演算法的自由能，在WS演算法中看成KL散度，現在看成擴展的KL散度。對於正則化擴展，有很多類似論文，「Mode Regularized Generative Adversarial Networks」，「Stabilizing Training of Generative Adversarial Networks through Regularization」有興趣可以讀讀。

所以對於VAE，類比WS演算法的Wake認知階段， 不同的是在ELBO這個VBEM目標的基礎上加了KL散度作為正則化限制。再應用再參數化技巧實現了VAE。

而對應到GAN，類比Sleep階段，正則化限制換了JSD距離，然後目標KL距離也隨著不同GAN的變體也可以變化。

所以， VAE和GAN都可以理解為有特殊正則化限制的Wake-Sleep步驟，那麼組合起來也並不奇怪。

這就是為什麼那麼多論文研究如何組合VAE/GAN到同一個框架下面去。目前對這方面的理解還在廣泛探討中。

如果你理解了這個，恭喜你，進入理解EM演算法的第八層境界，水中有水、山外有山。

第九層境界，KL距離的統一

Jordan 大佬的一片論文，開啟了KL距離的統一，「On surrogate loss functions and f-divergences」。裡面對於所謂的正反KL距離全部統一到 f 散度的框架下面。 Jordan 首先論述了對於損失函數統一的Margin理論的意義。

然後把這些損失函數也映射到 f 散度：

然後微軟的 Sebastian Nowozin，把 f-散度擴展到GAN 「f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization」。

然後對正反KL散度也做了一次統一。

對於 f-散度的理解離不開對Fenchel對偶的理解（參考「走近中神通Fenchel」）。

除了f-散度，還有人基於bregman散度去統一正反KL散度的認知。 KL散度就是香農熵的bregman散度。

而Bregman散度本身是基於一階泰勒展開的一種偏離度的度量。

然後再基於Bregman距離去研究最小KL投影，函數空間採用香農熵（參考「信息熵的由來」）。

無論f-散度還是bregman散度對正反KL距離的統一，之後的廣義EM演算法，都會變得空間的最優投影的交替出現。或許廣義EM演算法也成了不同流形空間上的坐標梯度下降演算法而已coodinate descent。

如果你理解了這個，恭喜你，進入理解EM演算法的第九層境界，山水合一。

小結

這裡淺薄的介紹了理解EM演算法的9層境界，託名Hinton和Jordan，著實是因為佩服他們倆和各自的弟子們對EM演算法，甚至到無監督深度學習的理解和巨大貢獻。想來Hinton和Jordan對此必定會有更為深刻的理解，很好奇會到何種程度。。。最後依然好奇，為啥只有他們兩家的子弟能夠不停的突破無監督深度學習？Hinton 老仙說，機器學習的未來在於無監督學習！

相關話題：

Hinton是如何理解PCA？

相關參考鏈接：

http://sens.tistory.com/304

https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm

http://stats.stackexchange.com/questions/65876/confusion-related-to-em-algorithm

http://cdn-ak.f.st-hatena.com/images/fotolife/i/isseing333/20110412/20110412233430.png

https://www.quora.com/What-is-an-intuitive-explanation-for-the-expectation-maximization-EM-algorithm

http://math.stackexchange.com/questions/25111/how-does-expectation-maximization-work

http://www.cse.cuhk.edu.hk/~lxu/papers/journal/XUNPL97.PDF

http://web.stanford.edu/class/ee378b/papers/wu-em.pdf

https://hal.archives-ouvertes.fr/hal-00720617/document

http://www.cs.tut.fi/kurssit/TLT-5906/EM_presentation_2013.pdf

對於含有隱變數的問題，如果 (1) 隱變數不容易被積分掉 (marginalized)，或者 (2) 積分掉以後也不好做優化，直接求解最大似然估計 (MLE) 往往是不可行的。對於這類問題，如果 (1) 隱變數的分布 q 可以求解 (2) 似然函數關於 q 的積分可以做優化，用 EM 至少可以找到一個局部最優解。

因為很多模型都含有隱變數，而且滿足上述條件，所以 EM 其實很有用。甚至，一些模型可以通過引入隱變數 (data augmentation) 的方法來構造 EM 演算法。

含有隱變數的mle

EM是拿來求解MLE的一種方法。

合適的時候用(比如方便計算的時候)，不必強行用。

很多時候推公式並不能增強你的認識，尤其是不能解答「為什麼我們需要它」。

採用兩步演算法的本質，不過是對latent variable 和 parameter的區別對待；而題主的根本困惑，其實是沒有明白為何要對二者區別對待。

本質上，latent variable 和 parameter 可以說沒區別，都是變數，圖模型里的白圈。
實際上，paramater常指那些絕對數量少，表達內容多、從充足的樣本中統計得到的、具有全局不變意味的少數幾個統計量，例如：GMM裡面每個中心的均值、方差、HMM裡面的轉移矩陣、NB裡面的類條件、類先驗。
而latent variable則往往指那些絕對數量多、表達內容少、sample-wise的、帶有assignment/index指示意味的、茫茫多的值，例如：GMM/NB裡面每個數據的類歸屬、HMM裡面每個時間點的狀態。
在訓練時，對parameter，我們必須要求它的精確值，這是我們學習的目的，你將來在預測時指望的就是他；而對latent variable，我們則只要知道個大概的統計量，大概到足以支撐paramater的求解即可，而不必知道每一條訓練數據的具體latent variable值，因為將來你在預測時，根本用不上他。更因為，每個latent variable背後只有一條data sample的支持，即便你想求他的最優解，也很難準確，反不如用統計量來表示的趨勢更好。這，就是區別對待的根本原因。
具體到實際操作，其中一種用一步求parameter精確值，用另一步求latent variable大概統計量，就是名為EM的演算法了。在這個演算法里，「大概統計量」這個很不精確的意味，被叫做responsibility的數學表達實現（以GMM為例）。

你現在再回頭看公式，也許會有更深入的發現。

MLE是一個optimization goal, EM是求解這個goal的演算法。和EM比較的應該是其他的優化演算法比如

@Richardkwo 說得很好了。

補充一點：gradient descent. EM一般認為比gradient descent在parameter space 更"global"一些更容易得到更好的解。

paper一篇： http://dspace.mit.edu/bitstream/handle/1721.1/7195/AIM-1520.pdf?sequence=2 的conclusion part講了EM的優點和缺點

請舉個例子，怎麼不用em，直接mle求解hmm

Em演算法是因為無法直接得到隱變數的信息，需要估計隱變數的期望值，從而迭代收斂於最優結果

求解MLE的方法很多，在無法直接通過求導得到closed-form解的時候，可以用gradient descent甚至second-order的優化方法，或者用EM。EM的優點在於通過構造隱藏變數，可以保證每一步迭代似然函數肯定是增加的，直到局部最優。

有時候直接通過極大似然估計函數求導是求不出參數解的。

David 9 的EM演算法寫的還行。