數據挖掘算法:EM算法

1. 極大似然

極大似然（Maximum Likelihood）估計為用于已知模型的參數估計的統計學方法。

比如，我們想了解拋硬幣是正面（head）的概率分布θ；那么可以通過最大似然估計方法求得。假如我們拋硬幣10次，其中8次正面、2次反面；極大似然估計參數θ值：

其中，l(θ)為觀測變量序列的似然函數（likelihood function of the observation sequence）。對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)。觀測數據的似然函數：

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

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

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

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

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

3. 實例

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

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

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

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