閑話EM

在概率模型（Probabilistic Model）裡面，我們通常會利用最大似然估計（Maximum Likelihood Estimation, MLE）或者最大後驗估計（Maximum A Posterior, MAP）來估計一些模型的參數，即，然而很多概率模型涉及到隱變數，所以會變成，由於求和項是在對數裡面，這給優化帶來了很大的困難。而EM演算法就是針對這種帶隱變數的極大似然估計提出來的演算法。

本文將會主要介紹EM演算法。對於EM演算法的介紹會包括：EM演算法的兩種推導、EM在高斯混合模型裡面的詳細推導。

EM演算法

1 EM演算法

1.1 簡介

EM演算法的全稱為Expectation Maximization，即期望-最大化演算法。從名字可以看出EM演算法包括兩個步驟，其一是求期望，其二是最大化。重複兩個步驟，迭代直到模型收斂。那麼EM演算法是計算誰的期望，又是最大化誰呢？

在概率模型中，經常會假定數據樣本，其中是模型的參數，也是要求解的目標。給定觀測數據集 $X = { x_1, x_2, cdots, x_n}$ ，我們要做的就是計算數據的對數似然（Log Likelihood）:

$LL( heta) = sum_{i=1}^n ln p(x| heta)$

最大化上面的式子，然後即可求解得到目標參數，舉例來說，通常是指數分佈家族，所以求解起來很方便。

然而，在實際情況中，會有很多隱變數，每個觀測樣本對應於一個隱變數，此時有：

上面公式是通過聯合概率分佈的邊際分佈求得觀測數據的分佈，這個過程叫做邊際化（Marginalization），此時進行對數似然最大化得到：

$ln p(X| heta) = sum_{i=1}^n ln left( sum_z p(x_i, z| heta) ight)$

可以看到上式對數函數裡面出現了對隱變數的求和項，這就導致了計算變得複雜了，有時是不可行的，因為對隱變數求和可能會導致計算的複雜性變為指數級別。

1.2 雛形

那麼對於帶有隱變數的模型該如何最大似然估計呢？下面提供一種方案。首先，假定隱變數是已知的，那麼聯合概率，也是已知的，那麼我們此時稱為完整數據，所以我們就對完整數據做極大似然估計，有：

$ln p(X, Z | heta) = sum_{i=1}^n ln p(x_i, z_i | heta)$

此時，注意對數裡面沒有了求和項，因為我們假定給定，隱變數的值是已知的，因此就不需要再進行求和消去隱變數了。

但是，實際上我們對隱變數的觀察只取決於隱變數的後驗概率分佈 ，這將是EM演算法的一個核心分佈，需要特別加以重視。那麼我們接著上面的思路，由於是不可知的，但是我們上面對完整數據進行最大似然估計時假設了是已知的，那麼這不就矛盾了麼？也就意味著我們上面的建議，直接求完整數據最大似然是不可行的。那麼該如何求呢？

引入近似方法，先建立完整數據的似然，然後再利用隱變數的後驗概率分佈 $p(Z|X, heta^{old})$ 將似然裡面的隱變數積分掉，那麼得到的結果就是：

$max_{ heta} sum_Z p(Z|X, heta^{old})ln p(X, Z | heta)$

上面的優化目標是對的一個近似，後面會指出實際上是一個下界，上面的函數也叫 $Q( heta, heta^{old})$ ，需要注意的是隱變數的後驗概率分佈使用的參數是 $heta^{old}$ ，是上一輪迭代之後的結果，如果是按照來優化，那麼上面的式子又變成不可行的了，因為會很難求。

所以從上面就可以簡單看出EM的兩步分別為：

Expectation: 計算函數 $Q( heta, heta^{old}) = sum_Z p(Z|X, heta^{old})ln p(X, Z | heta)$ ，這一步是根據上一輪迭代得到的隱變數的後驗概率分佈來對完整數據的似然進行求期望，因此叫做E步；
Maximization: 求解優化目標 $heta^* = max_{ heta} Q( heta, heta^{old})$ ，更新 $heta^{old} = heta^{*}$ ，這一步就是最大化Q函數，因此叫做M步。

迭代上面兩步直到收斂即可獲得 $max_{ heta} ln p(X| heta)$ 的近似解。

1.3 推導

上面從如何解決帶隱變數的極大似然估計著手提出的一種方案，但是沒有理論證明，下面將從兩個角度來說明EM演算法，即EM演算法的兩種推導方式。

第一種推導方法是利用Jensen不等式來推導，先來簡單聊一下什麼是Jensen不等式，簡單說一下就是：在凸函數中，函數值的期望要大於等於期望的函數值。

用數學表述則是，對於凸函數，總有：

那麼考慮對數似然：

$ln p(X | heta) \ = ln left( sum_Z p(X, Z | heta) ight) \ = ln left( sum_Z p(Z |X, heta^{old})frac{p(X, Z | heta)}{p(Z |X, heta^{old})} ight) \ = ln left( E_{Z sim p(Z |X, heta^{old})} left[ frac{p(X, Z | heta)}{p(Z |X, heta^{old})} ight] ight) \ geq E_{Z sim p(Z |X, heta^{old})} left[ ln left( frac{p(X, Z | heta)}{p(Z |X, heta^{old})} ight) ight]$