(最大期望)EM算法案例詳解

一、EM算法簡介

EM算法全稱為Exception Maximization Algorithm，即最大期望算法，以下簡稱EM算法。它是一種疊代的算法，主要用于含有隐變量的機率參數模型的極大似然和極大後驗機率估計。EM算法也經常用于機器學習和計算機視覺的聚類領域，是一個非常重要的算法。

二、EM算法原理

要了解EM算法，就必須先了解極大似然估計，因為整個的EM算法的演算、推導，都是以極大似然估計為基礎。

2.1 極大似然估計

2.1.1 兩點分布

首先我們來看一個簡單的例子：假設我們現在有一個抛硬币的實驗，10次抛硬币的結果是：正正反正正正反反正正，記p為每次抛硬币的結果為正的機率，那麼這次實驗的結果發生的機率記為P：

得到了上述的等式，那麼當小p取何值時大P能夠取得最大值呢？也就是當小p取何值時，這次實驗的結果最容易發生。對此我們利用極大似然估計，反過來當大P取最大值時，我們就可以求得此時的小p值。

目标函數：

最優解是：

一般形式：

将上述的實驗化成一般形式，即假設有X次實驗，實驗結果的機率為p(x)，分布為

，則其一般形式為：

2.1.2 高斯分布

進一步考察：

若給定一組樣本x1 ,x2 …xn ，已知它們來自于高斯分布N(μ,σ)，試估計參數μ,σ？高斯分布的均值為μ，方差為σ，仍使用剛開始的極大似然估計來求解這個過程。

按照MLE的過程分析：

1.高斯分布的機率密度函數：

2.将Xi的樣本值xi帶入上述極大似然估計(MLE)的一般形式，得到極大似然函數：

3.化簡對數似然函數得到目标函數：

• 

• = 

  

• =

  

4.将目标函數對參數μ,σ分别求偏導，求極值得到μ,σ的式子：

可以對上述的兩個公式進行分析：

• 針對  

  

    ，等式右邊對所有的樣本值求和、取均值，即用樣本的均值來代替總體的均值。
• 針對

  

  ，等式右邊是對樣本求方差（真實的方差應該是除n-1，是以稱之為僞方差），用樣本方差來代替總體的方差。

上述的兩個公式是後面分析的基礎，可以直接當作結論引用。

2.2 引入隐變量

2.2.1 樣本含有隐變量

例子：若在某商場随機挑選100位顧客，測量這100 位顧客的身高，假設這100個樣本服從正态分布N(μ,σ)，試估計參數μ,σ。

正态分布的機率密度值已知，又有樣本值，結合上述的分析，極大似然估計、求偏導、求極值，聯合方程組得到μ,σ。我們也可以直接使用上面的結論直接得到參數μ,σ。

引入隐變量：

若樣本中存在男性顧客和女性顧客，服從N(μ1,σ1) 和 N(μ2,σ2)的分布，試估計μ1,σ1，μ2,σ2。

剛剛的樣本值是可以直接觀察到的，加入隐變量使得樣本無法完全觀測到。現在隻知道身高資料，但是不知道這個身高樣本的性别，即不知道每個樣本值是來自女性還是男性。針對這種無法完全觀察或不完全的資料，用EM算法是很合适的。

2.3 EM算法

2.3.1 混合高斯模型

混合高斯模型求參問題：

将上述的執行個體再進一步延申，化成更一般的形式，随機變量X是有K個正态分布混合而成，取各個正态分布的機率為π 1 π 2 ... π K ，第i個正态分布的均值為μ i ，标準差為Σ i 。若觀測到随機變量X的一系列樣本x 1 ,x 2 ,...,x n ，試估計參數 π， μ， Σ。

同理将樣本值代入到一般形式，再化簡，得到對數似然函數：

第一步：估算資料來自的組分

估計資料是由每個組分生成的機率，對于每個樣本xi，它由第k個組分生成的機率。（這裡可能有的講法不一樣，有的說是第k個組分對樣本xi的貢獻度有多少，但是實質一樣的）。

上述公式是EM算法的核心思想，

指的是第k個組分對樣本xi的貢獻度，除分母進行歸一化，得到結果

第i個樣本xi來自組分k的機率。

由于式子裡的μ,Σ需要我們估計的值，是以采用疊代法，在計算

的時候假定μ,Σ均已知，即根據先驗知識給定μ,Σ,

。

第二步：估計每個組分的參數

将我們的目标函數，取對數化簡後得：

1. 對于組分k而言，可以看做生成了{

   

   *

   

   | i=1,2,...N}這些點。組分k是一個标準得高斯分布，可以利用上面得公式：

   

   與

   

   直接估計出

   

   ,

   

   ,

   

   ,

   

   。
2. 将得到的新的

   

   ,

   

   ,

   

   ,

   

   ，再代入回去得到新的

   

   ,

   

   ,

   

   ,

   

   。
3. 反複疊代上述的1，2步直到，收斂到某一可接受的誤內插補點或達到某一設定的疊代次數。

2.3.2 EM算法核心

假定有訓練集{

,...

}，包含有m個獨立樣本，求該組資料的模型p(x,z)的參數。

通過極大似然估計建立目标函數，取對數化簡得到對數似然函數：

這裡z是隐随機變量，直接找到參數的估計是很困難的。我們的政策是建立

的下界，并且求該下屆的最大值，重複該過程直到收斂到局部的最大值。

EM算法的推導過程：

1. 令

   

   是z的某一個分布，

   

   ，将樣本值代入一般形式，乘一個

   

   再除一個

   

   ，接着再Jensen不等式的反向利用log函數為凹函數，前面加上負号得到凸函數，再利用凸函數的性質，使其收斂到局部最大值。

   

2. 為了使等号成立：

   

   ，因為f(E(x)) = E(f(x))若想等号成立，f(x) = c即f(x)為常函數時等号成立。
3. 進一步分析：

   

   

   （因為歸一化）  聯合機率求和得到邊緣分布

   

4. 最終轉化為用給定的樣本的隐含變量的條件分布求期望。

三、EM算法架構

該步有點簡潔，下次會更新該步...

Repeat until convergence{
    (E-step)For each i,set:
                Qi(z(i)) := p(z(i)|x(i);theat)
    (M-step) Set:
                theat := argmax(objectFunction)

}
           

四、EM算法優缺點

優點	缺點
聚類	對初始化資料敏感（先驗給出的初始均值、方差）
算法計算結果穩定、準确	EM算法計算複雜度高，收斂慢，不适用于大規模、高次元資料
EM算法自收斂，既不需要事先設定類别，也不需要資料間的兩兩比較合并等操作	當所要優化的函數不是凸函數時，EM算法容易給出局部最優解，而不是全局最優解

五、EM算法案例

針對2.2.1節的案例，某商場的100個樣本，并引入隐含變量身高，估計男女樣本的均值、方差。如下為程式、圖像。