EM估計演算法

1. em演算法的EM演算法

在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計或者最大後驗估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。
最大期望演算法經過兩個步驟交替進行計算：
第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；
第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。
M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
總體來說，EM的演算法流程如下：
1.初始化分布參數
2.重復直到收斂：
E步驟：估計未知參數的期望值，給出當前的參數估計。
M步驟：重新估計分布參數，以使得數據的似然性最大，給出未知變數的期望估計。

2. 高斯混合模型(GMM)和EM演算法

學號：20021110074     電院    姓名：梁雪玲

【嵌牛導讀】：GMM與EM演算法的學習與推導。

【嵌牛鼻子】：GMM    EM  

【嵌牛提問】：GMM是什麼？EM演算法是什麼？二者之間的關系？演算法的推導？如何深入學習？

【嵌牛正文】：

在深度學習的路上，從頭開始了解一下各項技術。本人是DL小白，連續記錄我自己看的一些東西，大家可以互相交流。

本文參考：

http://www.ituring.com.cn/article/497545(GMM)

https://blog.csdn.net/xmu_jupiter/article/details/50889023(GMM)

http://www.cnblogs.com/wjy-lulu/p/7010258.html(EM演算法)

https://blog.csdn.net/zouxy09/article/details/8537620(EM演算法)

一、前言

    高斯混合模型(Gaussian Mixture Model)簡稱GMM，是一種業界廣泛使用的聚類演算法。它是多個高斯分布函數的線性組合，理論上GMM可以擬合出任意類型的分布，通常用於解決同一集合下的數據包含多種不同的分布的情況。高斯混合模型使用了期望最大(Expectation Maximization， 簡稱EM)演算法進行訓練，故此我們在了解GMM之後，也需要了解如何通過EM演算法訓練(求解)GMM。

二、高斯混合模型(GMM)

    在了解高斯混合模型之前，我們先了解一下這種模型的具體參數模型-高斯分布。高斯分布又稱正態分布，是一種在自然界中大量存在的，最為常見的分布形式。

    如上圖，這是一個關於身高的生態分布曲線，關於175-180對稱，中間高兩邊低，相信大家在高中已經很了解了，這里就不再闡述。

    現在，我們引用《統計學習方法》-李航 書中的定義，如下圖：

    根據定義，我們可以理解為，GMM是多個高斯分布的加權和，並且權重α之和等於1。這里不難理解，因為GMM最終反映出的是一個概率，而整個模型的概率之和為1，所以權重之和即為1。高斯混合模型實則不難理解，接下來我們介紹GMM的訓練(求解)方法。

PS.從數學角度看，對於一個概率模型的求解，即為求其最大值。從深度學習角度看，我們希望降低這個概率模型的損失函數，也就是希望訓練模型，獲得最大值。訓練和求解是不同專業，但相同目標的術語。

三、最大似然估計

     想要了解EM演算法，我們首先需要了解最大似然估計這個概念。我們通過一個簡單的例子來解釋一下。

    假設，我們需要調查學校男女生的身高分布。我們用抽樣的思想，在校園里隨機抽取了100男生和100女生，共計200個人(身高樣本數據)。我們假設整個學校的身高分布服從於高斯分布。但是這個高斯分布的均值u和方差∂2我們不知道，這兩個參數就是我們需要估計的值。記作θ=[u, ∂]T。

    由於每個樣本都是獨立地從p(x|θ)中抽取的，並且所有的樣本都服從於同一個高斯分布p(x|θ)。那麼我們從整個學校中，那麼我抽到男生A（的身高）的概率是p(xA|θ)，抽到男生B的概率是p(xB|θ)。而恰好抽取出這100個男生的概率，就是每個男生的概率乘積。用下式表示：

    這個概率反映了，在概率密度函數的參數是θ時，得到X這組樣本的概率。在公式中，x已知，而θ是未知，所以它是θ的函數。這個函數放映的是在不同的參數θ取值下，取得當前這個樣本集的可能性，因此稱為參數θ相對於樣本集X的似然函數（likehood function）。記為L(θ)。

    我們先穿插一個小例子，來闡述似然的概念。

某位同學與一位獵人一起外出打獵，一隻野兔從前方竄過。只聽一聲槍響，野兔應聲到下，如果要你推測，這一發命中的子彈是誰打的？你就會想，只發一槍便打中，由於獵人命中的概率一般大於這位同學命中的概率，看來這一槍是獵人射中的。

      這個例子所作的推斷就體現了極大似然法的基本思想，我們並不知道具體是誰打的兔子，但是我們可以估計到一個看似正確的參數。回到男生身高的例子中。在整個學校中我們一次抽到這100個男生(樣本)，而不是其他的人，那麼我們可以認為這100個男生(樣本)出現的概率最大，用上面的似然函數L(θ)來表示。

    所以，我們就只需要找到一個參數θ，其對應的似然函數L(θ)最大，也就是說抽到這100個男生（的身高）概率最大。這個叫做θ的最大似然估計量，記為：

因為L(θ)是一個連乘函數，我們為了便於分析，可以定義對數似然函數，運用對數的運算規則，把連乘轉變為連加：

PS.這種數學方法在MFCC中我們曾經用過，可以回溯一下上一篇文章。

    此時，我們要求θ，只需要使θ的似然函數L(θ)極大化，然後極大值對應的θ就是我們的估計。在數學中求一個函數的最值問題，即為求導，使導數為0，解方程式即可(前提是函數L(θ)連續可微)。在深度學習中，θ是包含多個參數的向量，運用高等數學中的求偏導，固定其中一個變數的思想，即可求出極致點，解方程。

總結而言：

    最大似然估計，只是一種概率論在統計學的應用，它是參數估計的方法之一。說的是已知某個隨機樣本滿足某種概率分布，但是其中具體的參數不清楚，參數估計就是通過若干次試驗，觀察其結果，利用結果推出參數的大概值。最大似然估計是建立在這樣的思想上：已知某個參數能使這個樣本出現的概率最大，我們當然不會再去選擇其他小概率的樣本，所以乾脆就把這個參數作為估計的真實值。

    求最大似然函數估計值的一般步驟：

（1）寫出似然函數；

（2）對似然函數取對數，並整理；(化乘為加)

（3）求導數，令導數為0，得到似然方程；

（4）解似然方程，得到的參數即為所求。

四、EM演算法

    期望最大(Expectation Maximization， 簡稱EM)演算法，稱為機器學習十大演算法之一。它是一種從不完全數據或有數據丟失的數據集（存在隱含變數）中求解概率模型參數的最大似然估計方法。

    現在，我們重新回到男女生身高分布的例子。我們通過抽取100個男生身高，並假設身高分布服從於高斯分布，我們通過最大化其似然函數，可以求的高斯分布的參數θ=[u, ∂]T了，對女生同理。但是，假如這200人，我們只能統計到其身高數據，但是沒有男女信息(其實就是面對200個樣本，抽取得到的每個樣本都不知道是從哪個分布抽取的，這對於深度學習的樣本分類很常見)。這個時候，我們需要對樣本進行兩個東西的猜測或者估計了。

      EM演算法就可以解決這個問題。假設我們想估計知道A和B兩個參數，在開始狀態下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反過來知道了B也就得到了A。可以考慮首先賦予A某種初值，以此得到B的估計值，然後從B的當前值出發，重新估計A的取值，這個過程一直持續到收斂為止。

    在男女生身高分布的例子中，我們運用EM演算法的思想。首先隨便猜一下男生的高斯分布參數:均值和方差。假設均值是1.7米，方差是0.1米，然後計算出每個人更可能屬於第一個還是第二個正態分布中。這是第一步，Expectation。在分開了兩類之後，我們可以通過之前用的最大似然，通過這兩部分，重新估算第一個和第二個分布的高斯分布參數:均值和方差。這是第二步，Maximization。然後更新這兩個分布的參數。這是可以根據更新的分布，重新調整E(Expectation)步驟...如此往復，迭代到參數基本不再發生變化。

    這里原作者提到了一個數學思維，很受啟發，轉給大家看一眼(比較雞湯和啰嗦，大家可以跳過)

這時候你就不服了，說你老迭代迭代的，你咋知道新的參數的估計就比原來的好啊？為什麼這種方法行得通呢？有沒有失效的時候呢？什麼時候失效呢？用到這個方法需要注意什麼問題呢？呵呵，一下子拋出那麼多問題，搞得我適應不過來了，不過這證明了你有很好的搞研究的潛質啊。呵呵，其實這些問題就是數學家需要解決的問題。在數學上是可以穩當的證明的或者得出結論的。那咱們用數學來把上面的問題重新描述下。（在這里可以知道，不管多麼復雜或者簡單的物理世界的思想，都需要通過數學工具進行建模抽象才得以使用並發揮其強大的作用，而且，這裡面蘊含的數學往往能帶給你更多想像不到的東西，這就是數學的精妙所在啊）

五、EM演算法的簡單理解方式

    在提出EM演算法的推導過程之前，先提出中形象的理解方式，便於大家理解整個EM演算法，如果只是實現深度學習模型，個人認為可以不需要去看後面的演算法推導，看這個就足夠了。

    坐標上升法(Coordinate ascent):

    圖中的直線式迭代優化的途徑，可以看到每一步都會向最優值靠近，而每一步前進的路線都平行於坐標軸。那麼我們可以將其理解為兩個未知數的方程求解。倆個未知數求解的方式，其實是固定其中一個未知數，求另一個未知數的偏導數，之後再反過來固定後者，求前者的偏導數。EM演算法的思想，其實也是如此。使用坐標上升法，一次固定一個變數，對另外的求極值，最後逐步逼近極值。對應到EM上，E步：固定θ，優化Q；M步：固定Q，優化θ；交替將極值推向最大。 

六、EM演算法推導

    現在很多深度學習框架可以簡單調用EM演算法，實際上這一段大家可以不用看，直接跳過看最後的總結即可。但是如果你希望了解一些內部的邏輯，可以看一下這一段推導過程。

    假設我們有一個樣本集{x(1),…,x(m)}，包含m個獨立的樣本(右上角為樣本序號)。但每個樣本i對應的類別z(i)是未知的（相當於聚類），也即隱含變數。故我們需要估計概率模型p(x,z)的參數θ(在文中可理解為高斯分布)，但是由於裡麵包含隱含變數z，所以很難用最大似然求解，但如果z知道了，那我們就很容易求解了。

首先放出似然函數公式，我們接下來對公式進行化簡：

    對於參數估計，我們本質上的思路是想獲得一個使似然函數最大化的參數θ，現在多出一個未知變數z，公式(1)。那麼我們的目標就轉變為：找到適合的θ和z讓L(θ)最大。

    對於多個未知數的方程分別對未知的θ和z分別求偏導，再設偏導為0，即可解方程。

    因為(1)式是和的對數，當我們在求導的時候，形式會很復雜。

    這里我們需要做一個數學轉化。我們對和的部分，乘以一個相等的函數，得到(2)式，利用Jensen不等式的性質，將(2)式轉化為(3)式。(Jensen不等式數學推到比較復雜，知道結果即可)

Note:

Jensen不等式表述如下：

如果f是凸函數，X是隨機變數，那麼：E[f(X)]>=f(E[X])

特別地，如果f是嚴格凸函數，當且僅當X是常量時，上式取等號。參考鏈接: https://blog.csdn.net/zouxy09/article/details/8537620

    至此，上面的式（2）和式（3）不等式可以寫成：似然函數L(θ)>=J(z,Q)，那麼我們可以通過不斷的最大化這個下界J(z,Q)函數，來使得L(θ)不斷提高，最終達到它的最大值。

    現在，我們推導出了在固定參數θ後，使下界拉升的Q(z)的計算公式就是後驗概率，解決了Q(z)如何選擇的問題。這一步就是E步，建立L(θ)的下界。接下來的M步，就是在給定Q(z)後，調整θ，去極大化L(θ)的下界J（在固定Q(z)後，下界還可以調整的更大）。

總結而言

EM演算法是一種從不完全數據或有數據丟失的數據集(存在隱藏變數)中，求解概率模型參數的最大似然估計方法。

EM的演算法流程：

1>初始化分布參數θ；

重復2>, 3>直到收斂:

    2>E步驟(Expectation):根據參數初始值或上一次迭代的模型參數來計算出隱性變數的後驗概率，其實就是隱性變數的期望。作為隱藏變數的現估計值：

    3>M步驟(Maximization):將似然函數最大化以獲得新的參數值：

這個不斷迭代的過程，最終會讓E、M步驟收斂，得到使似然函數L(θ)最大化的參數θ。

在L(θ)的收斂證明:

3. EM演算法和混合高斯模型（一）

EM（Expectation Maximization）演算法是一種迭代演算法，用於含有隱變數的概率模型參數的極大似然估計，或極大後驗估計。EM演算法的每次迭代由兩步組成：E步，求期望（expectation）；M步，求極大值，因而被稱為期望極大演算法，簡稱EM演算法。

本文從EM演算法的引入說起，簡單介紹EM演算法的推導過程，以及其在高斯混合模型中的應用。更多的關於EM演算法的推導細節，可參見 人人都懂EM演算法 。

假設我們需要調查我們學校學生的身高分布。我們先假設學校所有學生的身高服從正態分布 。( 注意：極大似然估計的前提一定是要假設數據總體的分布，如果不知道數據分布，是無法使用極大似然估計的 )，這個分布的均值μ和標准差為σ 未知，如果我們估計出這兩個參數，那我們就得到了最終的結果。那麼怎樣估計這兩個參數呢？

學校的學生這么多，我們不可能挨個統計吧？這時候我們需要用到概率統計的思想，也就是抽樣，根據樣本估算總體。假設我們隨機抽到了 200 個人（也就是 200 個身高的樣本數據，為了方便表示，下面「人」的意思就是對應的身高）。然後統計抽樣這 200 個人的身高。根據這 200 個人的身高估計均值 μ和方差σ 。例子來自 人人都懂EM演算法 。

現在我們假設這200個人的身高服從一個正態分布N(μ，σ)，因此可以直接使用極大似然估計方法估計出這個分布的參數μ和σ。

但是，這200個人的身高真的是服從同一個正態分布嗎？實際情況並不是這樣的，男生和女生分別服從兩種不同的正態分布，即男生 女生各服從一個正態分布 ，( 注意：EM演算法和極大似然估計的前提是一樣的，都要假設數據總體的分布，如果不知道數據分布，是無法使用EM演算法的 )，而且假設我們現在只有身高數據，丟失了性別數據，那麼該怎樣評估學生的身高分布呢？

這個時候，對於每一個樣本或者你抽取到的人，就有兩個問題需要估計了，一是這個人是男的還是女的，二是男生和女生對應的身高的正態分布的參數是多少。這兩個問題是相互依賴的：

但是現在我們既不知道每個學生是男生還是女生，也不知道男生和女生的身高分布。這就成了一個先有雞還是先有蛋的問題了。雞說，沒有我，誰把你生出來的啊。蛋不服，說，沒有我，你從哪蹦出來啊。為了解決這個你依賴我，我依賴你的循環依賴問題，總得有一方要先打破僵局，不管了，我先隨便整一個值出來，看你怎麼變，然後我再根據你的變化調整我的變化，然後如此迭代著不斷互相推導，最終就會收斂到一個解（草原上的狼和羊，相生相剋）。這就是EM演算法的基本思想了。

EM的意思是「Expectation Maximization」，具體方法為：

上面的學生屬於男生還是女生我們稱之為隱含參數，女生和男生的身高分布參數稱為模型參數。

EM 演算法解決這個的思路是使用啟發式的迭代方法，既然我們無法直接求出模型分布參數，那麼我們可以先猜想隱含參數（EM 演算法的 E 步），接著基於觀察數據和猜測的隱含參數一起來極大化對數似然，求解我們的模型參數（EM演算法的M步)。由於我們之前的隱含參數是猜測的，所以此時得到的模型參數一般還不是我們想要的結果。我們基於當前得到的模型參數，繼續猜測隱含參數（EM演算法的 E 步），然後繼續極大化對數似然，求解我們的模型參數（EM演算法的M步)。以此類推，不斷的迭代下去，直到模型分布參數基本無變化，演算法收斂，找到合適的模型參數。

在開始介紹EM演算法之前，讓我們先來了解一個重要的定理——Jensen不等式。

如下圖，如果函數f(x)是凸函數，x是隨機變數，有 0.5 的概率是 a，有 0.5 的概率是 b， x的期望值就是 a 和 b 的中值了，那麼：

對於m個相互獨立的樣本:

假如沒有隱含變數z， 我們僅需要找到合適的θ極大化對數似然函數即可:

現在我們給定一個θ值（初始化θ），那麼logL(θ)的值就取決於Q i (z)和P(x (i) ,z (i) )。我們可以通過調整這兩個概率使下屆逼近logL(θ)的真實值，當不等式變為等式時，說明我們調整後的下屆就等於logL(θ)了。由Jeson不等式可知，等式成立的條件是隨機變數是常數，則有：

如果Q i (z (i) ) = P(z (i) |x (i) , θ)，則（2）式使我們包含隱藏數據的對數似然函數的一個下屆。如果我們能極大化這個下屆，則也在嘗試極大化我們的對數似然函數。即我們需要極大化下式：

由於對logaf(x)求導的結果與f(x)的系數無關（(ln(ax))'= (lna + lnx)'=1/x），因此對θ求極大似然時，可以去掉式中的常數部分Q i (z (i) )：

現在，讓我們來總結一下EM演算法的流程。

輸入：觀察數據x = (x (1) , x (2) , ... , x (m) ), 聯合分布P(x, z|θ)，條件分布P(z|x,θ)，極大迭代次數J。
（1）隨機初始化模型參數θ值；
（2）迭代求解各個分布模型的參數以及各個模型的概率：
for j from 1 to J:

輸出：模型參數θ

圖中的直線式迭代優化的路徑，可以看到每一步都會向最優值前進一步，而且前進路線是平行於坐標軸的，因為每一步只優化一個變數。

這猶如在x-y坐標系中找一個曲線的極值，然而曲線函數不能直接求導，因此什麼梯度下降方法就不適用了。但固定一個變數後，另外一個可以通過求導得到，因此可以使用坐標上升法，一次固定一個變數，對另外的求極值，最後逐步逼近極值。對應到EM上，E步：固定 θ，優化Q；M步：固定 Q，優化 θ；交替將極值推向極大。

E步 ：初始化θ A =0.6和θ B =0.5（θ A 和θ B 分別表示兩個硬幣出現正面的概率），計算每次擲硬幣選擇A和B的概率，例如第一個實驗中選擇A的概率為：

M步 ：求出似然函數下屆Q(θ，θ i ), y i 代表第j次試驗正面朝上的個數，μ j 代表第j次試驗選擇硬幣A的概率，1-μ j 代表第j次試驗選擇硬幣B的概率。

參考：
人人都懂EM演算法
《統計學習方法》. 李航

4. em演算法原理

我最近也在看EM演算法，主要是它在無監督學習中的應用，例子倒是沒有，原理差不多弄明白了一些，其實是出於一種很自然的想法，似然度均值的最大化，但是中間有些問題就是在迭代的過程中似然度是單調增加的，這個證明過程比較繁瑣，具體你在模式識別中的應用可以參考這個WiKi頁：http://en.wikipedia.org/wiki/Expectation-maximization_algorithm

5. 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演算法的收斂性很容易，只需要證明每一輪迭代之後，參數的似然函數遞增，即

6. 極大似然估計和EM演算法初步

本文來自我的個人博客 https://www.zhangshenghai.com/posts/1422/

極大似然估計是在知道結果的情況下，尋求使該結果出現可能性極大的條件，以此作為估計值。在維基網路中，極大似然估計的定義是這樣的：

首先從一個例子入手，假設我們需要調查某個地區的人群身高分布，那麼先假設這個地區人群身高服從正態分布 。注意，極大似然估計的前提是要假設數據總體的分布， 不知道數據分布是無法使用極大似然估計的 。假設的正態分布的均值和方差未知，這個問題中極大似然估計的目的就是要估計這兩個參數。

根據概率統計的思想，可以依據樣本估算總體，假設我們隨機抽到了1000個人，根據這1000個人的身高來估計均值 和方差 。

將其翻譯成數學語言：為了統計該地區的人群身高分布，我們獨立地按照概率密度 抽取了1000個樣本組成樣本集 ，我們想通過樣本集 來估計總體的未知參數 。這里概率密度 服從高斯分布 ，其中的未知參數是 。

那麼怎樣估算 呢？

這里每個樣本都是獨立地從 中抽取的，也就是說這1000個人之間是相互獨立的。若抽到 的概率是 ，抽到 的概率是 ，那麼同時抽到它們的概率就是 。同理，同時抽到這1000個人的概率就是他們各自概率的乘積，即為他們的聯合概率，這個聯合概率就等於這個問題的似然函數：

對 L 取對數，將其變成連加的，稱為對數似然函數，如下式：

對似然函數求所有參數的偏導數，然後讓這些偏導數為0，假設有n個參數，就可以得到n個方程組成的方程組，方程組的解就是似然函數的極值點了，在似然函數極大的情況下得到的參數值 即為我們所求的值：

極大似然估計是建立在這樣的思想上：已知某個參數能使這個樣本出現的概率極大，我們當然不會再去選擇其他小概率的樣本，所以乾脆就把這個參數作為估計的真實值。

和極大似然估計一樣，EM演算法的前提也是要假設數據總體的分布， 不知道數據分布是無法使用EM演算法的 。

概率模型有時既含有觀測變數，又含有隱變數。如果概率模型的變數都是觀測變數，那麼給定數據，可以直接用極大似然估計法，或貝葉斯估計法估計模型參數。但是，當模型含有隱變數時，就不能簡單地使用這些估計方法。EM演算法就是含有隱變數的概率模型參數的極大似然估計法，或極大後驗概率估計法。

函數：完全數據的對數似然函數 關於在給定觀測數據 和當前參數 下對未觀測數據 的條件概率分布 的期望

含有隱變數 的概率模型，目標是極大化觀測變數 關於參數 的對數似然函數，即

輸入：觀測隨機變數數據 ，隱隨機變數數據 ，聯合分布 ，條件分布 ；
輸出：模型參數

7. （十）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中，我們提到過：

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

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

剩下的代入即可.

結果展示：

8. em演算法的EM演算法簡述

迭代使用EM步驟，直至收斂。
可以有一些比較形象的比喻說法把這個演算法講清楚。比如說食堂的大師傅炒了一份菜，要等分成兩份給兩個人吃，顯然沒有必要拿來天平一點一點的精確的去稱分量，最簡單的辦法是先隨意的把菜分到兩個碗中，然後觀察是否一樣多，把比較多的那一份取出一點放到另一個碗中，這個過程一直迭代地執行下去，直到大家看不出兩個碗所容納的菜有什麼分量上的不同為止。EM演算法就是這樣，假設我們估計知道A和B兩個參數，在開始狀態下二者都是未知的，並且知道了A的信息就可以得到B的信息，反過來知道了B也就得到了A。可以考慮首先賦予A某種初值，以此得到B的估計值，然後從B的當前值出發，重新估計A的取值，這個過程一直持續到收斂為止。
EM 演算法是 Dempster，Laind，Rubin 於 1977 年提出的求參數極大似然估計的一種方法，它可以從非完整數據集中對參數進行 MLE 估計，是一種非常簡單實用的學習演算法。這種方法可以廣泛地應用於處理缺損數據，截尾數據，帶有雜訊等所謂的不完全數據(incomplete data)。
假定集合Z = (X,Y)由觀測數據 X 和未觀測數據Y 組成，X 和Z = (X,Y)分別稱為不完整數據和完整數據。假設Z的聯合概率密度被參數化地定義為P(X,Y|Θ)，其中Θ表示要被估計的參數。Θ的最大似然估計是求不完整數據的對數似然函數L(X;Θ)的最大值而得到的：
L(Θ;X)= log p(X|Θ) = ∫log p(X,Y|Θ)dY ；
EM演算法包括兩個步驟：由E步和M步組成，它是通過迭代地最大化完整數據的對數似然函數Lc(X;Θ)的期望來最大化不完整數據的對數似然函數，其中：
Lc(X;Θ) =log p(X,Y |Θ) ；
假設在演算法第t次迭代後Θ獲得的估計記為Θ(t) ，則在(t+1)次迭代時，
E-步：計算完整數據的對數似然函數的期望，記為：
Q(Θ|Θ (t)) = E{Lc(Θ;Z)|X;Θ(t)}；
M-步：通過最大化Q(Θ|Θ(t) ) 來獲得新的Θ 。
通過交替使用這兩個步驟，EM演算法逐步改進模型的參數，使參數和訓練樣本的似然概率逐漸增大，最後終止於一個極大點。直觀地理解EM演算法，它也可被看作為一個逐次逼近演算法：事先並不知道模型的參數，可以隨機的選擇一套參數或者事先粗略地給定某個初始參數λ0 ，確定出對應於這組參數的最可能的狀態，計算每個訓練樣本的可能結果的概率，在當前的狀態下再由樣本對參數修正，重新估計參數λ，並在新的參數下重新確定模型的狀態，這樣，通過多次的迭代，循環直至某個收斂條件滿足為止，就可以使得模型的參數逐漸逼近真實參數。
EM演算法的主要目的是提供一個簡單的迭代演算法計算後驗密度函數，它的最大優點是簡單和穩定，但容易陷入局部最優。