關(guān)于EM算法的九層境界的淺薄介紹，?Hinton和Jordan理解的EM算法

---

知乎上有一個(gè)討論：EM算法存在的意義是什么？是什么原因使得EM算法這么流行呢？EM算法是Hinton和Jordan強(qiáng)強(qiáng)發(fā)力的領(lǐng)域，本文作者縱向解析EM算法的9層境界，深入淺出，值得一讀。

Hinton, 這個(gè)深度學(xué)習(xí)的締造者( 參考攢說 Geoff Hinton)， Jordan 當(dāng)世概率圖模型的集大成者（參考 “喬丹上海行”）， 他們碰撞的領(lǐng)域，EM算法！這個(gè)是PCA外的，另外一個(gè)無監(jiān)督學(xué)習(xí)的經(jīng)典，是我們的主題。

他們怎么認(rèn)識的呢？Jordan的導(dǎo)師，就是著名的鏈接主義核心人物Rumelhart

（參考“易圖秒懂の連接主義誕生”）。在“人工智能深度學(xué)習(xí)人物關(guān)系[全]”里面我們介紹到，Hinton和Rumelhart是同事，都在Francis Crick的小組。

前言

為什么說EM算法是他們強(qiáng)強(qiáng)發(fā)力的領(lǐng)域呢？

這里我們討論Hinton和統(tǒng)計(jì)大神Jordan的強(qiáng)強(qiáng)發(fā)力的領(lǐng)域。當(dāng)Bayes網(wǎng)絡(luò)發(fā)展到高級階段， 概率圖模型使得計(jì)算成為問題，由此開啟了Variational Bayes領(lǐng)域。在“變の貝葉斯”里面， 我們解釋了研究Variational Bayes，有3撥人。 第一撥人， 把物理的能量搬到了機(jī)器學(xué)習(xí)（參考 “給能力以自由吧！”）。 第二撥人， 就是Hinton，他將VB和EM算法聯(lián)系了起來，奠定了現(xiàn)在我們看到的VB的基礎(chǔ)。 第三撥人，就是Jordan， 他重建了VB的框架ELBO的基礎(chǔ)。所以說EM算法擴(kuò)展的VBEM算法，就是Hinton和Jordan共同發(fā)力的部分。

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

為什么無監(jiān)督深度學(xué)習(xí)突出成果都是Hinton和Jordan家的？

無監(jiān)督深度學(xué)習(xí)，除了強(qiáng)化學(xué)習(xí)，主要包括BM、自動(dòng)編碼器AE和GAN領(lǐng)域。 1）這些領(lǐng)域中的DBN和DBM是Hinton搞的。2）AE中的經(jīng)典，VAE是DP Kingma和M Welling搞得。DP Kingma碩士導(dǎo)師是LeCun，LeCun的博士后導(dǎo)師是Hinton，并且Welling的博士后導(dǎo)師是Hinton。 3）而GAN是Ian Goodfellow和Yoshua Bengio的杰作， Goodfellow是Bengio的學(xué)生， 而Bengio的博士后導(dǎo)師是Jordan。 一句話， 無監(jiān)督深度學(xué)習(xí)的經(jīng)典模型幾乎全是Hinton和Jordan家的。 為什么？ 因?yàn)槟軓氐桌斫釫M算法到深不見底的人非Hinton和Jordan莫屬。

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

EM算法理解的九層境界

1. EM 就是 E + M

2. EM 是一種局部下限構(gòu)造

3. K-Means是一種Hard EM算法

4. 從EM 到 廣義EM

5. 廣義EM的一個(gè)特例是VBEM

6. 廣義EM的另一個(gè)特例是WS算法

7. 廣義EM的再一個(gè)特例是Gibbs抽樣算法

8. WS算法是VAE和GAN組合的簡化版

9. KL距離的統(tǒng)一

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

最經(jīng)典的例子就是拋3個(gè)硬幣，跑I硬幣決定C1和C2，然后拋C1或者C2決定正反面， 然后估算3個(gè)硬幣的正反面概率值。

這個(gè)例子為什么經(jīng)典， 因?yàn)樗嬖V我們，當(dāng)存在隱變量I的時(shí)候， 直接的最大似然估計(jì)無法直接搞定。什么是隱變量？為什么要引入隱變量？ 對隱變量的理解是理解EM算法的第一要義！Chuong B Do & Serafim Batzoglou的Tutorial論文“What is the expectation maximization algorithm?”對此有詳細(xì)的例子進(jìn)行分析。

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

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

第二層境界， EM算法就一種局部下限構(gòu)造

如果你再深入到基于隱變量的EM算法的收斂性證明， 基于log(x)函數(shù)的Jensen不等式構(gòu)造， 我們很容易證明，EM算法是在反復(fù)的構(gòu)造新的下限，然后進(jìn)一步求解。

所以，先固定當(dāng)前參數(shù)， 計(jì)算得到當(dāng)前隱變量分布的一個(gè)下屆函數(shù)， 然后優(yōu)化這個(gè)函數(shù)， 得到新的參數(shù)， 然后循環(huán)繼續(xù)。

也正是這個(gè)不停的構(gòu)造下限的思想未來和VB方法聯(lián)系起來了。 如果你理解了這個(gè)， 恭喜你， 進(jìn)入理解EM算法的第二層境界，看山看石。

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

在第二層境界的基礎(chǔ)上， 你就能隨意傲游EM算法用到GMM和HMM模型中去了。 尤其是對GMM的深入理解之后， 對于有隱變量的聯(lián)合概率，如果利用高斯分布代入之后：

很容易就和均方距離建立聯(lián)系：

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

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

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

如果你理解了這個(gè)， 恭喜你， 進(jìn)入理解EM算法的第三層境界，看山看峰。

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

通過前3層境界， 你對EM算法的理解要跨過隱變量， 進(jìn)入隱分布的境界。 如果我們把前面的EM收斂證明稍微重復(fù)一下，但是引入隱分布。

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

有了廣義EM算法之后， 我們對自由能深入挖掘， 發(fā)現(xiàn)自由能和似然度和KL距離之間的關(guān)系：

所以固定參數(shù)的情況下， 那么只能最優(yōu)化KL距離了， 那么隱分布只能取如下分布：

而這個(gè)在EM算法里面是直接給出的。 所以EM算法是廣義EM算法的天然最優(yōu)的隱分布情況。但是很多時(shí)候隱分布不是那么容易計(jì)算的！

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

其次要理解， 為什么傳統(tǒng)的EM算法，不存在第一個(gè)最優(yōu)化？因?yàn)樵跊]有限制的隱分布（天然情況下）情況下， 第一個(gè)最優(yōu)就是要求：

而這個(gè)隱分布， EM算法里面是直接給出的，而不是讓你證明得到的。

這樣， 在廣義EM算法中，你看到兩個(gè)優(yōu)化步驟，我們進(jìn)入了兩個(gè)優(yōu)化步驟理解EM算法的境界了。

如果你理解了這個(gè)， 恭喜你， 進(jìn)入理解EM算法的第四層境界，有水有山。

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

在隱分布沒有限制的時(shí)候， 廣義EM算法就是EM算法， 但是如果隱分布本身是有限制的呢？譬如有個(gè)先驗(yàn)分布的限制， 譬如有計(jì)算的限制呢？

例如先驗(yàn)分布的限制：從pLSA到LDA就是增加了參數(shù)的先驗(yàn)分布！

例如計(jì)算上的限制：mean-field計(jì)算簡化的要求，分量獨(dú)立。

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

基于有限制的理解， 再引入模型變分的思想， 根據(jù)模型m的變化， 對應(yīng)參數(shù)和隱變量都有相應(yīng)的分布：

并且滿足分布獨(dú)立性簡化計(jì)算的假設(shè)：

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

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

如果你理解了這個(gè)， 恭喜你， 進(jìn)入理解EM算法的第五層境界，水轉(zhuǎn)山回。

第六層境界，廣義EM的另一個(gè)特例是WS算法

Hinton老爺子搞定VBEM算法后， 并沒有停滯， 他在研究DBN和DBM的Fine-Tuning的時(shí)候， 提出了Wake-Sleep算法。 我們知道在有監(jiān)督的Fine-Tuning可以使用BP算法， 但是無監(jiān)督的Fine-Tuning，使用的是Wake-Sleep算法。

就是這個(gè)WS算法，也是廣義EM算法的一種特例。WS算法分為認(rèn)知階段和生成階段。

在前面自由能里面，我們將KL距離引入了， 這里剛好這兩個(gè)階段分別優(yōu)化了KL距離的兩種形態(tài)。 固定P優(yōu)化Q，和固定Q優(yōu)化P。

所以當(dāng)我們?nèi)〈杂赡芾斫猓?全部切換到KL距離的理解， 廣義EM算法的E步驟和M步驟就分別是E投影和M投影。 因?yàn)橐驥L距離最優(yōu)， 可以等價(jià)于垂直。 而這個(gè)投影， 可以衍生到數(shù)據(jù)D的流形空間， 和模型M的流形空間。

所以你認(rèn)同WS算法是一種廣義EM算法（GEM）之后， 基于KL距離再認(rèn)識GEM算法。 引入了數(shù)據(jù)流形和模型流形。引入了E投影和M投影。

不過要注意的wake識別階段對應(yīng)的是M步驟， 而sleep生成階段對應(yīng)的E步驟。 所以WS算法對應(yīng)的是廣義ME算法。

如果你理解了這個(gè)， 恭喜你， 進(jìn)入理解EM算法的第六層境界，山高水深。

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

其實(shí)，前面基于KL距離的認(rèn)知， 嚴(yán)格放到信息理論的領(lǐng)域， 對于前面E投影和M投影都有嚴(yán)格的定義。M投影的名稱是類似的，但是具體是moment projection，但是E投影應(yīng)該叫I投影，具體是information projection。

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

當(dāng)我們不是直接計(jì)算KL距離， 而是基于蒙特卡洛抽樣方法來估算KL距離。

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

這時(shí)候， 廣義EM算法，就是Gibbs Sampling了。 所以Gibbs Sampling，本質(zhì)上就是采用了蒙特卡洛方法計(jì)算的廣義EM算法。

所以， 如果把M投影和I投影看成是一個(gè)變量上的最小距離點(diǎn)，那么Gibbs Sampling和廣義EM算法的收斂過程是一致的。

VAE的發(fā)明者，Hinton的博士后， Max Welling在論文“Bayesian K-Means as a “Maximization-Expectation” Algorithm”中， 對這種關(guān)系有如下很好的總結(jié)！

另外，Zoubin Ghahramani， Jordan的博士， 在“Factorial Learning and the EM Algorithm”等相關(guān)論文也反復(fù)提到他們之間的關(guān)系。

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

現(xiàn)在我們發(fā)現(xiàn)VB和Gibbs Sampling都可以放到廣義EM的大框架下， 只是求解過程一個(gè)采用近似逼近， 一個(gè)采用蒙特卡洛采樣。 有了EM算法和Gibbs Sampling的關(guān)系， 現(xiàn)在你理解， 為什么Hinton能夠發(fā)明CD算法了么？ 細(xì)節(jié)就不展開了。

如果你理解了這個(gè)， 恭喜你， 進(jìn)入理解EM算法的第七層境界，山水輪回。

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

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

對VAE的理解， 變了加了正則化的KL距離， 而對于GAN的理解變成了加Jensen–Shannon 散度。 所以， 當(dāng)我們把廣義EM算法的自由能， 在WS算法中看成KL散度， 現(xiàn)在看成擴(kuò)展的KL散度。 對于正則化擴(kuò)展， 有很多類似論文， “Mode Regularized Generative Adversarial Networks”， “Stabilizing Training of Generative Adversarial Networks through Regularization” 有興趣可以讀讀。

所以對于VAE，類比WS算法的Wake認(rèn)知階段，不同的是在ELBO這個(gè)VBEM目標(biāo)的基礎(chǔ)上加了KL散度作為正則化限制。 再應(yīng)用再參數(shù)化技巧實(shí)現(xiàn)了VAE。

而對應(yīng)到GAN，類比Sleep階段，正則化限制換了JSD距離， 然后目標(biāo)KL距離也隨著不同GAN的變體也可以變化。

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

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

如果你理解了這個(gè)， 恭喜你， 進(jìn)入理解EM算法的第八層境界，水中有水、山外有山。

第九層境界，KL距離的統(tǒng)一

Jordan 大佬的一片論文， 開啟了KL距離的統(tǒng)一， “On surrogate loss functions and f-divergences”。 里面對于所謂的正反KL距離全部統(tǒng)一到 f 散度的框架下面。 Jordan 首先論述了對于損失函數(shù)統(tǒng)一的Margin理論的意義。

然后把這些損失函數(shù)也映射到 f 散度：

然后微軟的 Sebastian Nowozin， 把 f-散度擴(kuò)展到GAN “f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization”。

然后對正反KL散度也做了一次統(tǒng)一。

對于 f-散度的理解離不開對Fenchel對偶的理解（參考“走近中神通Fenchel”）。

除了f-散度， 還有人基于bregman散度去統(tǒng)一正反KL散度的認(rèn)知。 KL散度就是香農(nóng)熵的bregman散度。

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

然后再基于Bregman距離去研究最小KL投影， 函數(shù)空間采用香農(nóng)熵（參考“信息熵的由來”）。

無論f-散度還是bregman散度對正反KL距離的統(tǒng)一， 之后的廣義EM算法， 都會(huì)變得空間的最優(yōu)投影的交替出現(xiàn)。 或許廣義EM算法也成了不同流形空間上的坐標(biāo)梯度下降算法而已coodinate descent。

如果你理解了這個(gè)， 恭喜你， 進(jìn)入理解EM算法的第九層境界，山水合一。

小結(jié)

這里淺薄的介紹了理解EM算法的9層境界，托名Hinton和Jordan，著實(shí)是因?yàn)榕宸麄儌z和各自的弟子們對EM算法，甚至到無監(jiān)督深度學(xué)習(xí)的理解和巨大貢獻(xiàn)。想來Hinton和Jordan對此必定會(huì)有更為深刻的理解， 很好奇會(huì)到何種程度 。。。 最后依然好奇， 為啥只有他們兩家的子弟能夠不停的突破無監(jiān)督深度學(xué)習(xí)？Hinton 老仙說， 機(jī)器學(xué)習(xí)的未來在于無監(jiān)督學(xué)習(xí)！