FPEM演算法

⑴ 大數據經典演算法解析（5）一EM演算法

  姓名：崔升    學號：14020120005

【嵌牛導讀】：

  EM作為一種經典的處理大數據的演算法，是我們在學習互聯網大數據時不得不去了解的一種常用演算法

【嵌牛鼻子】：經典大數據演算法之EM簡單介紹

【嵌牛提問】：EM是一種怎麼的演算法，其如何去觀測其中隱變數的？

【嵌牛正文】：

1. 極大似然

極大似然（Maximum Likelihood）估計為用於已知模型的參數估計的統計學方法。比如，我們想了解拋硬幣是正面（head）的概率分布θθ；那麼可以通過最大似然估計方法求得。假如我們拋硬幣1010次，其中88次正面、22次反面；極大似然估計參數θθ值：

θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2θ^=arg⁡maxθl(θ)=arg⁡maxθθ8(1−θ)2

其中，l(θ)l(θ)為觀測變數序列的似然函數（likelihood function of the observation sequence）。對l(θ)l(θ)求偏導

∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8

因為似然函數l(θ)l(θ)不是凹函數（concave），求解極大值困難。一般地，使用與之具有相同單調性的log-likelihood，如圖所示

凹函數（concave）與凸函數（convex）的定義如圖所示：

從圖中可以看出，凹函數「容易」求解極大值，凸函數「容易」求解極小值。

2. EM演算法

EM演算法（Expectation Maximization）是在含有隱變數（latent variable）的模型下計算最大似然的一種演算法。所謂隱變數，是指我們沒有辦法觀測到的變數。比如，有兩枚硬幣A、B，每一次隨機取一枚進行拋擲，我們只能觀測到硬幣的正面與反面，而不能觀測到每一次取的硬幣是否為A；則稱每一次的選擇拋擲硬幣為隱變數。

用Y表示觀測數據，Z表示隱變數；Y和Z連在一起稱為完全數據( complete-data )，觀測數據Y又稱為不完全數據(incomplete-data)。觀測數據的似然函數：

P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)

求模型參數的極大似然估計：

θ^=argmaxθlogP(Y|θ)θ^=arg⁡maxθlog⁡P(Y|θ)

因為含有隱變數，此問題無法求解。因此，Dempster等人提出EM演算法用於迭代求解近似解。EM演算法比較簡單，分為兩個步驟：

E步（E-step），以當前參數θ(i)θ(i)計算ZZ的期望值

Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]Q(θ,θ(i))=EZ[log⁡P(Y,X|θ)|Y,θ(i)]

M步（M-step），求使Q(θ,θ(i))Q(θ,θ(i))極大化的θθ，確定第i+1i+1次迭代的參數的估計值θ(i+1)θ(i+1)

θ(i+1)=argmaxθQ(θ,θ(i))θ(i+1)=arg⁡maxθQ(θ,θ(i))

如此迭代直至演算法收斂。關於演算法的推導及收斂性證明，可參看李航的《統計學習方法》及Andrew Ng的《CS229 Lecture notes》。 這里 有一些極大似然以及EM演算法的生動例子。

3. 實例

[2]中給出極大似然與EM演算法的實例。如圖所示，有兩枚硬幣A、B，每一個實驗隨機取一枚拋擲10次，共5個實驗，我們 可以 觀測到每一次所取的硬幣，估計參數A、B為正面的概率θ=(θA,θB)θ=(θA,θB)，根據極大似然估計求解

如果我們 不能 觀測到每一次所取的硬幣，只能用EM演算法估計模型參數，演算法流程如圖所示：

隱變數ZZ為每次實驗中選擇A或B的概率，則第一個實驗選擇A的概率為

P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45

按照上面的計算方法可依次求出隱變數ZZ，然後計算極大化的θ(i)θ(i)。經過10次迭代，最終收斂。

4. 參考資料

[1] 李航，《統計學習方法》.

[2] Chuong B Do & Serafim Batzoglou, What is the expectation maximization algorithm?

[3] Pieter Abbeel, Maximum Likelihood (ML), Expectation Maximization (EM) .

[4] Rudan Chen, 【機器學習演算法系列之一】EM演算法實例分析 .

⑵ 數據挖掘十大經典演算法之EM

EM（Expectation-Maximum）演算法也稱期望最大化演算法，它是最常見的隱變數估計方法，在機器學習中有極為廣泛的用途，例如常被用來學習高斯混合模型（Gaussian mixture model，簡稱GMM）的參數；隱式馬爾科夫演算法（HMM）、LDA主題模型的變分推斷等等。

EM演算法是一種迭代優化策略，由於它的計算方法中每一次迭代都分兩步，其中一個為期望步（E步），另一個為極大步（M步），一輪輪迭代更新隱含數據和模型分布參數，直到收斂，即得到我們需要的模型參數。

1. EM演算法推導過程

補充知識：Jensen不等式：

如果f是凸函數，函數的期望 大於等於 期望的函數。當且僅當下式中X是常量時，該式取等號。（應用於凹函數時，不等號方向相反）

2. EM演算法流程

3. EM演算法的其他問題

上面介紹的傳統EM演算法對初始值敏感，聚類結果隨不同的初始值而波動較大。總的來說，EM演算法收斂的優劣很大程度上取決於其初始參數。

EM演算法可以保證收斂到一個穩定點，即EM演算法是一定收斂的。

EM演算法可以保證收斂到一個穩定點，但是卻不能保證收斂到全局的極大值點，因此它是局部最優的演算法，當然，如果我們的優化目標是凸的，則EM演算法可以保證收斂到全局最大值，這點和梯度下降法這樣的迭代演算法相同。

EM演算法的簡單實例： https://zhuanlan.hu.com/p/40991784

參考：

https://zhuanlan.hu.com/p/40991784

https://blog.csdn.net/u011067360/article/details/24368085

⑶ （十）EM演算法

 EM演算法的英文全稱是 Expectation Maximization Algorithm——期望極大化演算法 ，它採用迭代的方式逼近帶隱變數的似然函數。通過對似然函數的一個下界求偏導，得到每一步參數估計的過程。
 這個名稱由於缺乏作用對象，讓人一頭霧水。這里的期望是什麼？為什麼我們要極大化這個期望，我們試圖優化什麼？
 這里的期望的含義其實是針對 極大似然估計 中的 似然函數 來說的，這里的期望就是似然函數的一個 下界 ，我們的目的是求這樣一個期望: 這個下界是根據 詹森不等式(Jensen's inequality） 放縮得到的，為什麼要放縮呢？因為我們試圖找出一個下界，極大化這個帶參數的下界之後，可以無限近似於似然函數。你想，如果這個做法ok的話，意味著什麼？意味著我們可以通過這個過程找出極大似然估計或最大後驗估計的參數近似解。這也意味著我們可以搞一個迭代法來得到一個近似解。但是即便我說的天花亂墜，這個下界要是不收斂那也白搭。而下界要收斂必須滿足兩個條件：
 1.這個下界的取值要單調遞增（因為每回迭代的結果要比上一次的取值更大）
 2.這個下界必須有上界(這個上界就是對數似然函數，且這一點可以由詹森不等式保證，這個也是EM的核心)
大白話就是 單調有界必有極限 。

我們來證明一下它確實是收斂的。
 首先，在極大似然估計中，我們的目的是根據手頭上的 個樣本，最大化 後，將參數 估計出來；引入對數： ;此時引入輔助變數 ;我們的對數似然函數就變成了：

設置變分函數： ;那麼：

根據琴生不等式,對數函數為凸函數(因為 ：等號在 為常數時取到)：

上面的這個下界，就是用來逼近原對數似然函數的，這里我們已經證明了演算法收斂的一個條件， 有界性 ；但是在繼續進行下一步的時候，我們還有一個問題沒搞清楚，那就是變分函數 的具體形式,實際上，我們可以通過琴生不等式等號成立的條件導出我們要的這個變分函數q。
令 為常數：
接著我們代入變分函數 的形式，定義這個下界的第一項：

定義下界的第二項：

對於第二項，我們看看隨著迭代步數的增大，它是否是遞增的，

我們將不同參數的 與 看作是兩個分布，那麼這個結果實際上是一個KL散度，它表徵兩個分布的相似度,其結果總是大於等於0的。
大於等於0的原因：

所以：

H為一個遞增的序列，那麼剩下的就是Q是否遞增了，基於前面提到的這個下界是有上界的，上界就是我們的對數似然函數。在這個前提下，現在我們只要證明，Q遞增是整個下界遞增的充分必要條件即可。
必要性：

當整個下界遞增，即：
那麼：
所以 單調遞增，必要性得證。
充分性：
因為：
前面已經證明：

又因為：

所以：

即，在 遞增的情況下，整個下界遞增。
充分性得證。
證畢。

 這個演算法名稱里提及的期望究竟是什麼？
我們說了這么多，實際都是要做一件事，那就是：

由於前面證明過整個下界有界。且只要找到讓第i次迭代的Q函數最大的 作為下一次迭代的參數，我們就可以讓Q遞增，讓演算法收斂。
我們來看看Q的形式。

這就是為什麼叫期望最大演算法的原因。

 我們以概率PCA，來展開EM的應用：
 當然這里的應用只涉及變分函數已知情況下的應用，並不涉及廣義EM的內容，日後看完文獻在來嘮嘮廣義EM，AVE，GAN等內容。
 我們先來算一下PPCA的EM期望的形式：

在 概率PCA 中，我們有提到：


所以：


所以期望裡面是這個式子：

我們的目的是要估計出 和 ;那麼我們分別對它們求偏導:

所以：


因為：

代入偏導中

所以：

我們偏導得到的結果就是：

我們會發現我們還有兩個估計量沒解決，一個是一階估計量 ,另一個是二階估計量
在概率PCA中，我們提到過：

那麼我們就有了一階估計量：

二階估計量可以通過簡單的計算得到：

剩下的代入即可.

結果展示：

⑷ em演算法為什麼可以解決隱含數據問題

EM演算法可以看成是特殊情況下計算極大似然的一種演算法。
現實的數據經常有一些比較奇怪的問題，比如缺失數據、含有隱變數等問題。當這些問題出現的時候，計算極大似然函數通常是比較困難的，而EM演算法可以解決這個問題。
EM演算法已經有很多應用，比如最經典的Hidden Markov模型等。

⑸ em演算法是什麼

最大期望演算法（Expectation-Maximization algorithm, EM），或Dempster-Laird-Rubin演算法，是一類通過迭代進行極大似然估計（Maximum Likelihood Estimation, MLE）的優化演算法 ，通常作為牛頓迭代法（Newton-Raphson method）的替代用於對包含隱變數（latent variable）或缺失數據（incomplete-data）的概率模型進行參數估計。
EM演算法的標准計算框架由E步（Expectation-step）和M步（Maximization step）交替組成，演算法的收斂性可以確保迭代至少逼近局部極大值 。EM演算法是MM演算法（Minorize-Maximization algorithm）的特例之一，有多個改進版本，包括使用了貝葉斯推斷的EM演算法、EM梯度演算法、廣義EM演算法等 。
由於迭代規則容易實現並可以靈活考慮隱變數，EM演算法被廣泛應用於處理數據的缺測值 ，以及很多機器學習（machine learning）演算法，包括高斯混合模型（Gaussian Mixture Model, GMM） 和隱馬爾可夫模型（Hidden Markov Model, HMM） 的參數估計。

⑹ EM演算法深度解析

最近在做文本挖掘的時候遇到了EM演算法，雖然讀書的時候簡單地接觸過，但當時並沒有深入地去了解，導致現在只記得演算法的名字。既然EM演算法被列為數據挖掘的十大演算法之一，正好借這個機會，重新學習一下這個經典的演算法。學習的過程中，我發現網上的資料大多講解地不夠細致，很多地方解釋得並不明了。因此我決定拋開別人的想法，僅從數學推導本身出發，盡力理解每一個公式的含義，並將其對應到實際的實驗過程當中。這篇博客記錄了我對與EM演算法的思考與理解，也是我人生中的第一篇博客，希望能夠對於想要學習EM演算法的同學有所幫助。

前面談到我在做文本挖掘的時候遇到了EM演算法，EM演算法用於估計模型中的參數。提到參數估計，最常見的方法莫過於極大似然估計——在所有的候選參數中，我們選擇的參數應該讓樣本出現的概率最大。相信看到這篇筆記的同學一定對極大似然估計非常熟悉，而EM演算法可以看作是極大似然估計的一個擴充，這里就讓我們用極大似然估計來解決一個簡單的例子，來開始正式的討論。

有A，B，C三枚硬幣，我們想要估計A，B，C三枚硬幣拋出正面的概率 , , 。我們按如下流程進行實驗100次：

記錄100次實驗的結果如下：

我們將上面的實驗結果表述如下：
表示第i次實驗中，硬幣A的結果，1代表正面，0代表反面； 表示第i次實驗中，硬幣B或硬幣C拋出正面的個數，則參數 的極大似然估計分別為：

即硬幣A，B，C各自拋出正面的次數占總次數的比例，其中 為指示函數。

實驗流程與1相同，但是我們不慎遺失了硬幣A的記錄結果，導致我們只知道隨後十次拋出了多少次正面，多少次反面，卻不知道實驗結果來自於硬幣B還是硬幣C。在這種情況下，我們是否還能估計出 , , 的值呢？

這時候利用極大似然估計似乎行不通了， 因為這種情況下，我們不但缺失了硬幣A產生的觀測值，同時也不知道哪些觀測值屬於硬幣B，哪些觀測值屬於硬幣C。

有些同學可能會提出，雖然我們無法得到三個硬幣各自產生的樣本，但是我們依然可以得到每個觀測值出現的概率。比如在第一次實驗中， 我們拋出了5次正面5次反面，我們可以做如下思考：

  假設這5次正面由硬幣B得到，那麼概率應該為 ，而這次觀測值來自於硬幣B，也就是硬幣A拋出正面的概率為

  假設這5次正面由硬幣C得到，那麼概率應該為 ，而這次觀測值來自於硬幣C，也就是硬幣A拋出反面的概率為

  綜合起來，利用條件概率公式，這個觀測值出現的概率就是

因此我們可以將樣本整體的概率和似然函數利用 , , 表示出來，通過對似然函數求導，令其關於 的偏導數等於0，我們可以求出三個參數的值。

這個思路聽上去十分合理，我們可以順著這個思路進行數學推導，看看可以得到什麼樣的結果。首先我們計算樣本的概率:

對應的似然函數為

其中 關於 的條件分布為

的分布為

因此我們可以得到

至此，我們成功地得到了似然函數。然而觀察可以發現，這個函數是由100項對數函數相加組成，每個對數函數內部包含一個求和，想通過求導並解出導數的零點幾乎是不可能的。當然我們可以通過梯度下降來極小化這個函數，藉助深度學習庫的自動微分系統在實現上也非常容易。但是這種做法過於簡單粗暴，有沒有辦法來優雅地解決這個問題呢？在繼續討論之前，我們先將這類問題進行一般化表述：

我們觀測到隨機變數 產生的m個相互獨立的樣本 , 的分布由聯合分布 決定， 是缺失數據或無法在實驗中被直接觀測到，稱為 隱變數 ，我們想要從樣本中估計出模型參數 的值。在接下來的討論中，我們假定 的取值是離散的，於是可以得到似然函數如下:

接下來，我們就探討一下，如何利用EM演算法解決這個問題。

這一部分的數學推導，主要參考了吳恩達CS229n的筆記，並且根據個人的思考和理解，盡力對公式的每一步進行詳細的解釋。我們先簡單地介紹一下琴生不等式。

琴生不等式有多種形式，下面給出其離散形式的表述和概率論中的表述:
1.若 為嚴格凹函數， 為定義域內的n個點， 是n個正實數，且滿足 , 則下述不等式成立:

當且僅當 時，不等式取等號。

2.若 為嚴格凹函數， 為實值隨機變數，且期望存在，則下述不等式成立:

當且僅當 ，即 為常數時，不等式取等號。

註： 這里將函數上方為凹集的函數稱為凹函數， 例如 函數就是凹函數。
相信大家對琴生不等式都十分熟悉，因此這里就不做過多的說明。接下來，我們將琴生不等式應用到我們的問題中。

回到我們之前的問題上， 我們想要極大化下面這個函數:

但是我們無法對這個函數直接求導，因此我們藉助琴生不等式，對這個函數進行變換。為了讓過程看上去簡潔，下面只對求和中的第 項進行計算。

令 滿足 ，且 ，則根據琴生不等式，可以得到：

當且僅當 為常數時，上述不等式取等號。也就是說，對於任意 ， 是一個與 無關的量。設對於任意 ，我們可以得到：

因此當 時，不等式 取等號，容易驗證此時 , 與 無關。將 綜合一下，我們可以得到以下結論:

到這里為止，我們已經擁有了推導出EM演算法的全部數學基礎，基於 我們可以構建出E步和M步。上面的數學推導雖然看上去略為復雜，但實際上只用到了三個知識點：
  1.琴生不等式:

  2.條件概率:

  3.聯合分布求和等於邊緣分布:

對上面的數學推導有疑問的同學，可以結合上面這三點，再將整個推導過程耐心地看一遍。

大部分關於EM演算法的資料，只是在數學形式上引入了 函數，即 ，以滿足琴生不等式的使用條件，卻沒有過多地解釋 函數本身。這導致了很多人完全看懂了演算法的推導，卻還是不理解這些數學公式究竟在做什麼，甚至不明白EM演算法為什麼叫做EM演算法。所以在給出E步和M步之前，我想先談一談 函數。

我們回顧一下 函數所滿足的條件（暫時不考慮琴生不等式取等號的限制），

在 所有可能的取值處有定義。可以看出， 是 的樣本空間上任意的一個概率分布。因此，我們可以對不等式 進行改寫。首先我們可以將含有 的求和寫成期望的形式:

這里 指的是在概率分布 下，求隨機變數 和 的期望。有同學會問，為什麼我們平時求期望的時候只要寫 ，並沒有指明是在哪個概率分布下的期望。這是因為一般情況下，我們都清楚地知道隨機變數 所服從的分布 ，並且默認在分布 下求期望。

舉個例子，我手上有一個硬幣，拋了10次，問拋出正面次數的期望。這種情況下，大部分人會默認硬幣是均勻的，也就是說拋出正面的次數 服從二項分布 ，期望 。這時有人提出了質疑，他說我認為你這個硬幣有問題，拋出正面的概率只有0.3，那麼在他眼裡， 期望 。

回到正題，我們利用等式 改寫不等式 ，可以得到:

這正是琴生不等式在概率論中的形式。我們可以將不等式倒過來理解：
  首先，假定隨機變數 服從概率分布 ， 是 的樣本空間上的任意一個概率分布。這里 可以是一組定值，也可以是關於參數 的函數。

  顯然，當我們取不同的 時，隨機變數 的期望也會隨之改變。需要注意的是，由於 與 相關，所以這里的期望不是一個數值，而是關於 的函數。

  當我們令 為 的後驗分布 時，上面的期望最大。這里有兩點需要注意，1. 後驗分布 也是一個關於參數 的函數。2. 由於期望是關於 的函數，所以這里的最大指的並非是最大值，而是最大的函數。

  若對於每一個 ，我們都令 為 的後驗分布 ，則上述期望之和等於我們要極大化的似然函數，即

通過上述分析，我們為尋找似然函數的極大值點 提供了一個思路。我們不去極大化似然函數本身，而是去極大化 。至於如何將這個思路實際應用，就要利用到EM演算法中的E-step和M-step。

這一節中，我們先給出E-step和M-step的數學形式，隨後在結合拋硬幣的例子來解釋這兩步究竟在做什麼。下面進入演算法的流程，首先我們任意初始化 ，按下述過程進行迭代直至收斂：

在第 次迭代中，
(E-step)對於每個 ，令
(M-step)更新 的估計值，令

EM演算法從任意一點 出發，依次利用E-step優化 ，M-step優化 ，重復上述過程從而逐漸逼近極大值點。而這個過程究竟是怎樣的呢，就讓我們一步步地揭開EM演算法的面紗。

假設我們現在隨機初始化了 ，進入第一輪迭代：
(E-step)

由於我們已經假定模型參數為 ，所以此時 不再是與 有關的函數，而是由一組常數構成的概率分布。結合拋硬幣的例子來看，這一步是在我們已知模型參數 的基礎上(雖然這是我們瞎猜的)，去推測每一次的觀測值是由哪個硬幣產生的，或者說我們對每一次觀測值做一個軟分類。比如我們根據初始化的參數，計算出 ， 。可以解釋為第 個觀測值有20%的概率來自於硬幣B，80%的概率來自於硬幣C；或者說硬幣A拋出了0.2個正面，0.8個反面。

(M-step)

考慮到 是一組常數，我們可以舍棄常數項，進一步簡化上面這個要極大化的函數

由於 不再與 相關，因此上面的函數變成了對數函數求和的形式，這個函數通常來說是容易求導的，令導數等於0，我們可以求出新的參數 。我們仍舊以拋硬幣為例進行解釋，

令 , 可以得到，

這三個參數的解釋是顯而易見的。我們在E-step中對每個觀測值進行了軟分類， 可以看成是硬幣A拋出正面的次數，所以 是 的極大似然估計； 是我們拋硬幣B的次數， 是硬幣B拋出正面的次數，所以 是 的極大似然估計；對於 我們有相同的解釋。

我們將這個結果與拋硬幣1中極大似然估計的結果相比較可以發現，之前結果中的指示函數 變成了這里的 ，在指示函數下，某個觀測值要麼來自於硬幣B，要麼來自於硬幣C，因此也稱為硬分類。而在 函數下，某個觀測值可以一部分來自於硬幣B，一部分來自於硬幣C，因此也稱作軟分類。

將上述兩步綜合起來，EM演算法可以總結如下：我們首先初始化模型的參數，我們基於這個參數對每一個隱變數進行分類，此時相當於我們觀測到了隱變數。有了隱變數的觀測值之後，原來含有隱變數的模型變成了不含隱變數的模型，因此我們可以直接使用極大似然估計來更新模型的參數，再基於新的參數開始新一輪的迭代，直到參數收斂。接來下我們就討論為什麼參數一定會收斂。

前面寫了太多的公式，但是這一部分我不打算給出收斂性的數學推導。其實數學上證明EM演算法的收斂性很容易，只需要證明每一輪迭代之後，參數的似然函數遞增，即

⑺ 怎麼通俗易懂地解釋EM演算法並且舉個例子

在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計或者最大後驗估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。

最大期望演算法經過兩個步驟交替進行計算：

第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；

第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。

M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。

總體來說，EM的演算法流程如下：

1. 初始化分布參數

2. 2.重復直到收斂：

3. E步驟：估計未知參數的期望值，給出當前的參數估計。

4. M步驟：重新估計分布參數，以使得數據的似然性最大，給出未知變數的期望估計。