期望最大化(EM)算法真如用起来那么简单？
前言
小夕曾經問一位做機器學習理論的學姐：“學姐學姐，EM算法是什么呢？”
學姐回答：“EM算法啊，就是解決包含隱變量的參數估計問題。”
小夕：
然后小夕去問一位做工程的學長：“學長學長，EM算法是什么呢？”
學長回答：“EM算法就那樣啊，就是先用有標簽的樣本訓練個分類器，再給未知標簽的樣本貼標簽，然后再拿全部樣本再訓練分類器，就這樣來回倒騰~”
小夕：
于是小夕自己一個人看了一整天的EM算法QAQ
EM算法在工程上確實有很多應用場景，例如：
在不同場景中用過EM算法的攻城獅可能有這種感覺”不同場景的EM算法有時看起來差別很大，但是又總隱約覺得應該有一根線將它們串起來。“這一根線就是本文的目標。
一個栗子
工程上的EM算法非常簡單，甚至有時給人Naive的感覺。比如小夕搬出一個半監督學習的大栗子，這是EM算法非常典型的工程應用。
比如，我們要做文檔分類。我們手頭有10000篇文章，其中只有600篇標好了類別，其余9400篇均沒有類別標簽。那么如何訓練出一個盡可能高精度的分類器呢？
半監督學習的原理
有人可能想，既然9400篇文檔都沒有標簽，難道這些沒有標簽的數據都會有助于提高分類器的精度？怎么可能呢？
其實很好理解。雖然有些文檔沒有類別標簽，但是這些文檔的內容就包含分類信息啊。這里的信息指的是“詞共現”，或者廣義上說“特征共現”。比如我們利用有標簽的文檔發現“么么噠”是非常有助于文檔分類的強特征，然而我們又在沒有標簽的文檔中發現“么么噠”經常與“抱抱”一起出現！也就是共現！那么就可以從很大程度上說明“抱抱”也是有助于文檔分類的強特征。
舉個生動的事實，在UseNet語料庫中做新聞類別分類，若要達到70%的精度，則需要2000篇有類別標記的文檔。但是，如果我們有600篇有類別標記的文檔，還有10000篇無類別標記的文檔，那么同樣可以達到70%的精度。
攻城獅眼中的EM算法
在攻城獅眼中，對于上面這個半監督學習問題，顯然是可以搬出來EM算法的。
在攻城獅眼中，EM算法可能非常簡單：
誒？明明思路很簡單啊，小夕怎么會說它并沒有看起來那么簡單呢？
機智的你有沒有想過，算法為什么要這樣寫呢？這就是關鍵啦。在進一步討論之前，小夕用盡可能嚴謹而通俗的語言來講解一下EM算法的純理論原理。
理論家眼中的EM算法
首先聲明一下，對于沒有微積分與概率統計基礎的同學，或者有公式恐懼癥的同學，請快速下滑跳過本章節！
ps：這一章節在知乎上的排版有些混亂，最佳閱讀體驗請移步該章節原文。
開門見山，EM算法的目標是使包含隱變量的數據集的后驗概率或似然函數最大化，進而得到最優的參數估計。
我們知道，通過貝葉斯公式，可以發現后驗概率中包含了似然函數和先驗概率（忽略分母的那個evidence項），因此求最大后驗概率的過程中包含了求極大似然估計的過程。因此雖然EM算法的目標是最大化后驗概率或似然函數，而本質上就可以認為是最大化似然函數。因此下面我們直接討論最大化似然函數。
似然函數設為l(θ)，描述樣本可以用多維隨機變量（對應于機器學習的多維特征），每一維的隨機變量都可以認為服從某種概率分布。因此要描述每一維的樣本情況，我們只需要估計出這一維度的概率分布模型的參數就可以啦。而將所有維度的分布模型的參數放在一起，就是似然函數的參數，即θ。因此根據定義，
即似然函數代表著該包含m個樣本的樣本集存在的合理性（似然函數值越大，該樣本集的存在就越合理，即意味著參數取的越正確），描述每個樣本的多維隨機變量的分布模型的參數即上面的θ，p(x; θ)代表著固定θ的值，求p(x)的概率。
第二行的z則代表隱變量，確切的說是隱含的隨機變量。哈？看不懂第二步怎么來的？請回去復習微積分...算了，小夕太過善良，還是講講吧。
顯然，這里似然函數討論的是離散情況（畢竟都是∑符號而不是∫符號呀），因此，在p(x; θ)中加上z這個隨機變量后，只能將這個隨機變量積分掉才能保證加上z以后的式子依然等于p(x;θ)，當然，z是離散的，所以積分掉的意思是“求和”掉。
（回顧一下，對于任何一個連續隨機變量x，∫p(x)dx=1；對于任何一個離散隨機變量x，∑p(x)=1）
好，懂了第二步，在繼續往下推之前，想一想我們可不可以直接計算第二步呢？當然不行啦，不僅有θ，還有隱變量啊。因此繼續往下推。
誒？又出來個Qi。這個Qi是什么呢？這個Qi是隱變量z的概率分布函數啦。為什么要加上它呢？再好好觀察一下最后這一步中的這一部分！
有沒有發現什么！？對！這就是數學期望呀~別說數學期望都忘了啊，小夕還是再啰嗦一下吧...對于某離散隨機變量X來說，其數學期望
看吧~加上Qi這個概率分布函數后，是不是就出來了一個數學期望啦！但好像還是不能計算，懂數值計算的讀者應該知道log(∑…)的計算量是十分恐怖的，而且我們還被我們加上了一個不知道怎么計算的Qi！！！因此要繼續變！！！怎么變呢？Jensen不等式來啦！
直接摳了個圖（看不懂沒關系）：
通過這個Jensen不等式，我們發現可以進一步往下推了。
誒？雖然是往下推了一步，但是我們必須要讓等號恒成立才行啊，否則這個推理是不成立的呀。。。那么怎么讓等號恒成立呢？
根據Jensen不等式的等號成立條件，E[f(X)]≥f(E[X])中的隨機變量X必須恒等于常數！！也就是說：
≡c（c為常數）
于是重點來了，將分母的Qi移到右邊，將右邊的c移到左邊！我們發現：
好，再利用
（概率分布函數的基本性質），發現我們可以繼續這樣推！推到最后竟然是這個？？？？？
這個不就是每個樣本的隱變量z的后驗概率嗎！！！
也就是說我們只要求出來了每個樣本的隱變量的每個取值的后驗概率，就能得到這個樣本的Qi！！！
就能讓Jensen不等式的等號成立！！！
就能讓log(∑…)的不可計算成功變成可計算！！！
就能計算我們的目標——似然函數啦！！！
所以，總之，我們首先固定一個θ（也就是隨便給θ取個初始值），然后我們計算出隱變量z的取值的后驗概率，就能讓這個包含隱變量的似然函數變成傳統意義上的似然函數~也就是只考慮參數θ的似然函數~（這個過程稱為E步）
而最大化傳統意義上的似然函數就不用啰嗦啦~那就用傳統的方法最大化呀~最大化了以后就得到了當前的最優θ。（這個過程稱為M步）
而得到了當前的最優θ以后，我們又可以重新計算出隱變量z的取值的后驗概率，就能……~~~總之就又可以E步，然后又M步，然后又E，又M……
就這樣一直重復，一直重復，直到似然函數的值不再變化，此時每個樣本的Qi就是每個樣本的標簽~而此時的θ就是最終那個最優的θ啦~
至此，理論上的EM算法完成了，最終得到的就是我們要估計的最優參數θ，順便得到了每個樣本的隱變量的取值。
好橋梁，小夕造
可以看到，我們在理論EM中的目標是最大化似然函數！而小夕也講到了，其實最大化后驗概率的本質工作就是最大化似然函數。
這時再回顧一下工程上看似簡單的EM算法：
誒？發現了沒有~在工程上，我們在第2步中收集分類器對每個標簽的把握并求和，那不就是收集的整個數據集的后驗概率嘛！不就是在近似計算似然函數嘛！
因此，顯然，在工程上的第4步，也就是不停的重復2、3步，肯定會讓分類器的精度越來越大呀，因此分類器會對每個標簽的把握越來越大！因此這不就是相當于理論上的最大化似然函數嘛！
再想，在工程上，第3步的訓練樸素貝葉斯分類器的本質是什么？不就是訓練樸素貝葉斯分類器的參數嘛！而樸素貝葉斯分類器的參數是什么？不就是先驗概率跟每個類別下的每個特征的每個值的后驗概率嘛！而先驗概率不用管了，那每個類別下的每個特征的每個值的后驗概率合在一起是什么？不就是理論EM算法中的每個隨機變量的概率分布模型的參數嘛！恍然大悟啊有沒有？！
路人某：╮(╯_╰)╭并沒有。
小夕：(╯°Д°)╯︵ /(.□ . \)
好吧，給你幾分鐘時間接受一下訓練分類器的理論意義竟然是計算隨機變量所服從的概率分布模型的參數這個事實。
工程EM的第2、3、4步竟然完完全全的卡到了理論EM算法的相應位置。那么理論EM算法還有哪一步沒有對應上呢？當然是參數θ的初始化啦~相信機智的你已經想到了，那就是工程EM中的第1步所做的事情啦。
細心的你又有沒有留意到什么不同之處呢？
如果能留意到，那就非常厲害了。還記得理論EM中，我們計算似然函數的過程中，是要計算無標簽樣本的每種標簽取值的概率之和的！對，就是下面這貨：
然而，我們在工程上計算似然函數則是先用分類器預測一個類別，然后疊加該類別的后驗概率！
這意味著什么呢？顯然意味著忽略了樣本為其他類別的概率呀！這樣做，肯定導致導致計算出的后驗概率沒有那么準，但是，卻極大的提高了計算效率！
因此，本質上講，工程上，半監督學習中的EM算法不過是簡化了計算、優化了初始化的理論EM模型罷了╮(╯▽╰)╭
同樣的道理，在其他工程應用場景中，EM算法必然是以數學理論為主線，從某些角度來對數學過程進行簡化或優化，從而完成工程場景的適配。這也是為什么討厭數學的攻城獅可能會記住很多場景下的EM算法，而喜歡數學（最起碼不要跟數學打起來）的攻城獅則以不變應萬變，早已看透一切(￣?￣)
更多精彩文章，歡迎關注小夕的訂閱號”夕小瑤的賣萌屋“o(≧v≦)o
總結
以上是生活随笔為你收集整理的期望最大化(EM)算法真如用起来那么简单？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 美团外卖iOS多端复用的推动、支撑与思考
- 下一篇： Spring Boot 2.x基础教程：