統計學習方法---EM

EM算法詳解

基本了解

什麼是EM算法？

EM的全稱是Expectation Maximization 即期望最大化。它是用來求解含有隐變量的機率模型參數的參數估計方法。因為若機率模型含有隐變量，則無法使用極大似然估計法或貝葉斯估計法來估計參數，是以提出了通過疊代不斷求解似然函數的下界逼近求解對數似然函數極大化的算法即EM算法。

為什麼不能用極大似然估計法或貝葉斯估計法來估計參數？
對數似然函數的log内具有連加操作，無法進行極大化。
           

EM的特點

EM算法主要用于生産模型

EM算法的優點：簡單性，普适性

EM算法的缺點：

1. 不能保證找到全局最優值

2. 對初值敏感，常用方法是選取不同的初值進行疊代，然後選擇估計值最好的初值

EM算法收斂嗎？

EM算法在大多數情況下是能使收斂到一個穩定值的，但是隻能保證局部最優。

EM算法的推導

EM算法是一個不斷疊代的過程，一輪疊代分為兩個步驟：

\quad E：求期望 E Z [ P ( Y , Z ∣ θ ) ∣ Y , θ { i } ] E_Z[P(Y,Z|\theta)|Y, \theta^{\{i\}}] EZ​[P(Y,Z∣θ)∣Y,θ{i}]，即完全資料的對數似然函數 l o g P ( Y , Z ∣ θ ) logP(Y,Z|\theta) logP(Y,Z∣θ) 關于在給定觀測資料Y和目前參數 θ { i } \theta^{\{i\}} θ{i} 下對未觀測資料 Z 的條件機率分布 P ( Z ∣ Y , θ { i } ) P(Z|Y, \theta^{\{i\}}) P(Z∣Y,θ{i}) 的期望。簡要了解為求 Z 的期望。

\qquad 我們将期望稱為 Q函數：

Q ( θ , θ ( i ) ) = E Z [ P ( Y , Z ∣ θ ) ∣ Y , θ ( i ) ] = ∑ Z l o g P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) 或 ∫ Z l o g P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) d Z Q(\theta, \theta^{(i)}) = E_Z[P(Y,Z|\theta)|Y, \theta^{(i)}]\\ \qquad\qquad\qquad\quad=\sum_Z logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) \\ 或\int_{Z} logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) dZ Q(θ,θ(i))=EZ​[P(Y,Z∣θ)∣Y,θ(i)]=Z∑​logP(Y,Z∣θ)P(Z∣Y,θ(i))或∫Z​logP(Y,Z∣θ)P(Z∣Y,θ(i))dZ

\quad M：求極大 ， θ ( i + 1 ) = a r g m a x θ   Q ( θ , θ ( i ) ) \theta^{(i+1)} = argmax_\theta \ Q(\theta, \theta^{(i)}) θ(i+1)=argmaxθ​ Q(θ,θ(i))

接下來我們需要了解為什麼以上步驟得出參數估計序列 { θ ( 0 ) , θ ( 1 ) , . . . , θ ( i ) } \{\theta^{(0)}, \theta^{(1)}, ...,\theta^{(i)}\} {θ(0),θ(1),...,θ(i)} 近似等于極大似然估計參數。

主要有兩個結論：

1. 導出EM公式：對數似然函數 L ( θ ( i ) ) = l o g   P ( Y θ ( i ) ) L(\theta^{(i)})=log \ P(Y\theta^{(i)}) L(θ(i))=log P(Yθ(i)) 有下界，可以不斷的求解下界的極大化即 Q函數 逼近求解對數似然函數極大化。
2. 驗證EM算法正确：對數似然函數 L ( θ ( i ) ) = l o g   P ( Y ∣ θ ( i ) ) L(\theta^{(i)})=log \ P(Y|\theta^{(i)}) L(θ(i))=log P(Y∣θ(i))是單調遞增的，是以每一輪疊代求得的新估計值 θ \theta θ能使 L ( θ ) L(\theta) L(θ)增加。

導出EM公式：

我們可以通過不同的方法導出EM公式。以下從三種方法介紹如何導出EM公式。

目标：極大化

L ( θ ) = l o g   P ( Y ∣ θ ) L(\theta) =log \ P(Y|\theta) L(θ)=log P(Y∣θ)

方法一：ELBO + KL

q ( Z ) q(Z) q(Z) 是一個Z可能取值的機率分布， ∫ Z q ( Z ) = 1 \int_Z q(Z) = 1 ∫Z​q(Z)=1

l o g   P ( Y ∣ θ ) = l o g   P ( Y , Z ∣ θ ) − l o g P ( Z ∣ Y , θ ) = l o g   P ( Y , Z ∣ θ ) q ( Z ) − l o g   P ( Z ∣ Y , θ ) q ( Z ) log \ P(Y|\theta) = log \ P(Y, Z | \theta) - log P(Z | Y, \theta) \\ = log \ \frac {P(Y, Z | \theta)} {q(Z)} - log \ \frac {P(Z | Y, \theta)} {q(Z)} log P(Y∣θ)=log P(Y,Z∣θ)−logP(Z∣Y,θ)=log q(Z)P(Y,Z∣θ)​−log q(Z)P(Z∣Y,θ)​

兩邊同時對Z求積分：

左 邊 = ∫ Z l o g   P ( Y ∣ θ ) q ( Z ) d Z = l o g   P ( Y ∣ θ ) 右 邊 = ∫ Z q ( Z ) l o g   P ( Y , Z ∣ θ ) q ( Z ) d Z − ∫ Z q ( Z ) l o g   P ( Z ∣ Y , θ ) q ( Z ) d Z 左邊 = \int_{Z} log \ P(Y|\theta) {q(Z)} dZ = log \ P(Y|\theta) \\ 右邊 = \int_{Z} q(Z) log \ \frac {P(Y, Z | \theta)} {q(Z)} dZ- \int_{Z} q(Z) log \ \frac {P(Z | Y, \theta)} {q(Z)} dZ 左邊=∫Z​log P(Y∣θ)q(Z)dZ=log P(Y∣θ)右邊=∫Z​q(Z)log q(Z)P(Y,Z∣θ)​dZ−∫Z​q(Z)log q(Z)P(Z∣Y,θ)​dZ

令

E L B O = ∫ Z q ( Z ) l o g   P ( Y , Z ∣ θ ) q ( Z ) d Z K L = ∫ Z q ( Z ) l o g   P ( Z ∣ Y , θ ) q ( Z ) d Z ELBO = \int_{Z} q(Z) log \ \frac {P(Y, Z | \theta)} {q(Z)} dZ \\ KL = \int_{Z} q(Z) log \ \frac {P(Z | Y, \theta)} {q(Z)} dZ ELBO=∫Z​q(Z)log q(Z)P(Y,Z∣θ)​dZKL=∫Z​q(Z)log q(Z)P(Z∣Y,θ)​dZ

則

l o g   P ( Y ∣ θ ) = E L B O + K L log \ P(Y|\theta) = ELBO + KL log P(Y∣θ)=ELBO+KL

因為 K L ( q ∣ ∣ p ) ≥ 0 KL(q || p) \ge 0 KL(q∣∣p)≥0 ,

l o g   P ( Y ∣ θ ) ≥ E L B O log \ P(Y|\theta) \ge ELBO log P(Y∣θ)≥ELBO

此時， l o g   P ( Y ∣ θ ) log \ P(Y|\theta) log P(Y∣θ) 有一個下界ELBO，當且僅當 q = p q = p q=p 時，即 q ( Z ) = P ( Z ∣ Y , θ ) q(Z) = P(Z|Y, \theta) q(Z)=P(Z∣Y,θ) ，也就是在給定Y下 Z 的後驗分布。KL = 0， l o g   P ( Y ∣ θ ) = E L B O log \ P(Y|\theta) = ELBO log P(Y∣θ)=ELBO，此時 ELBO 的值等價于對數似然函數。

在以 θ ( i ) \theta^{(i)} θ(i) 開始的疊代中，我們選擇 q ( i ) ( Z ) = P ( Z ∣ Y , θ ( i ) ) q^{(i)}(Z) = P(Z|Y, \theta^{(i)}) q(i)(Z)=P(Z∣Y,θ(i)) ，這時能夠使 l ( θ ( i + 1 ) ) ≥ l ( θ ( i ) ) l(\theta^{(i+1)}) \ge l(\theta^{(i)}) l(θ(i+1))≥l(θ(i))，證明如下

l ( θ ( i ) ) = E L B O ( X , q ( i ) , θ ( i ) ) l(\theta^{(i)}) = ELBO(X, q^{(i)}, \theta^{(i)}) l(θ(i))=ELBO(X,q(i),θ(i))

因為參數 θ ( t + 1 ) \theta^{(t+1)} θ(t+1) 是通過最大化上述公式的右手邊獲得的，是以

l ( θ ( i + 1 ) ) ≥ E L B O ( X , q ( i ) , θ ( i + 1 ) ) ≥ E L B O ( X , q ( i ) , θ ( i ) ) = l ( θ ( i ) ) l(\theta^{(i+1)}) \ge ELBO(X, q^{(i)}, \theta^{(i+1)})\\ \ge ELBO(X, q^{(i)}, \theta^{(i)})\\ = l(\theta^{(i)}) l(θ(i+1))≥ELBO(X,q(i),θ(i+1))≥ELBO(X,q(i),θ(i))=l(θ(i))

通過極大化ELBO，即可極大化 l o g   P ( Y ∣ θ ) log \ P(Y|\theta) log P(Y∣θ)，

θ ^ = a r g m a x θ E L B O = a r g m a x θ ∫ Z P ( Z ∣ Y , θ ( i ) )   l o g   P ( Y , Z ∣ θ ) q ( Z ) d Z = a r g m a x θ ∫ Z P ( Z ∣ Y , θ ( i ) ) l o g   P ( Y , Z ∣ θ ) d Z \hat{\theta} = argmax_{\theta}ELBO \\ = argmax_{\theta} \int_{Z} P(Z|Y, \theta^{(i)} ) \ log \ \frac {P(Y, Z | \theta)} {q(Z)} dZ \\ = argmax_{\theta} \int_{Z} P(Z|Y, \theta^{(i)} ) log \ P(Y, Z | \theta) dZ θ^=argmaxθ​ELBO=argmaxθ​∫Z​P(Z∣Y,θ(i)) log q(Z)P(Y,Z∣θ)​dZ=argmaxθ​∫Z​P(Z∣Y,θ(i))log P(Y,Z∣θ)dZ

方法2：ELBO + Jenson inequality

l o g   P ( Y ∣ θ ) = l o g ∫ Z   P ( Y , Z ∣ θ ) d Z = l o g ∫ Z   P ( Y , Z ∣ θ ) q ( z ) q ( z ) d Z = l o g   E q ( Z ) [   P ( Y , Z ∣ θ ) q ( z ) ] ≥ E q ( Z ) l o g   [ P ( Y , Z ∣ θ ) q ( z ) ] ≥ E L B O log \ P(Y|\theta) =log \int_{Z} \ P(Y, Z | \theta) dZ \\ = log \int_{Z} \ \frac {P(Y, Z | \theta)} {q(z)} q(z) dZ \\ = log \ E_{q(Z)}[ \ \frac {P(Y, Z | \theta)} {q(z)}] \\ \ge E_{q(Z)} log \ [ \frac {P(Y, Z | \theta)} {q(z)}] \\ \ge ELBO log P(Y∣θ)=log∫Z​ P(Y,Z∣θ)dZ=log∫Z​ q(z)P(Y,Z∣θ)​q(z)dZ=log Eq(Z)​[ q(z)P(Y,Z∣θ)​]≥Eq(Z)​log [q(z)P(Y,Z∣θ)​]≥ELBO

第一個不等式由jenson 不等式得出，因為 l o g   ⋅ log \ \cdot log ⋅ 是凹函數，是以函數的期望小于于期望的函數。

當且僅當 l o g   P ( Y , Z ∣ θ ) q ( z ) = C \frac {log \ P(Y, Z | \theta)} {q(z)} = C q(z)log P(Y,Z∣θ)​=C 時，取等，即 q ( Z ) = P ( Z ∣ Y , θ ) q(Z) = P(Z | Y,\theta) q(Z)=P(Z∣Y,θ)

以下步驟同方法一

:注意：這裡的 ELBO 即為 Q函數

驗證EM算法正确：

證明 l o g   P ( Y ∣ θ { i } ) log \ P(Y|\theta^{\{i\}}) log P(Y∣θ{i}) 單調遞增，即

l o g   P ( Y ∣ θ ( i + 1 ) ) ≥ l o g   P ( Y ∣ θ ( i ) ) log \ P(Y|\theta^{(i+1)}) \ge log \ P(Y|\theta^{(i)}) log P(Y∣θ(i+1))≥log P(Y∣θ(i))

證明如下：

l o g   P ( Y ∣ θ ) = l o g   P ( Y , Z ∣ θ ) − l o g P ( Z ∣ Y , θ ) log \ P(Y|\theta) = log \ P(Y, Z | \theta) - log P(Z | Y, \theta) \\ log P(Y∣θ)=log P(Y,Z∣θ)−logP(Z∣Y,θ)

令

Q ( θ , θ ( i ) ) = ∫ Z l o g P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) d Z H ( θ , θ ( i ) ) = ∫ Z l o g P ( Z ∣ Y , θ ) P ( Z ∣ Y , θ ( i ) ) d Z Q(\theta, \theta^{(i)}) = \int_{Z} logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) dZ \\ H(\theta, \theta^{(i)}) = \int_{Z} log P(Z | Y, \theta)P(Z|Y,\theta^{(i)}) dZ Q(θ,θ(i))=∫Z​logP(Y,Z∣θ)P(Z∣Y,θ(i))dZH(θ,θ(i))=∫Z​logP(Z∣Y,θ)P(Z∣Y,θ(i))dZ

則

l o g   P ( Y ∣ θ ) = Q ( θ , θ ( i ) ) − H ( θ , θ ( i ) ) log \ P(Y|\theta) = Q(\theta, \theta^{(i)}) - H(\theta, \theta^{(i)}) log P(Y∣θ)=Q(θ,θ(i))−H(θ,θ(i))

令

l o g   P ( Y ∣ θ ( i + 1 ) ) − l o g   P ( Y ∣ θ ( i ) ) log \ P(Y|\theta^{(i+1)}) - log \ P(Y|\theta^{(i)}) log P(Y∣θ(i+1))−log P(Y∣θ(i))

則要使結論正确，則要證明，

Q ( θ ( i + 1 ) , θ ( i ) ) − Q ( θ ( i ) , θ ( i ) ) − [ H ( θ ( i + 1 ) , θ ( i ) ) − H ( θ ( i ) , θ ( i ) ) ] ≥ 0 Q(\theta^{(i+1)}, \theta^{(i)}) - Q(\theta^{(i)}, \theta^{(i)})- [H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)})] \ge0 Q(θ(i+1),θ(i))−Q(θ(i),θ(i))−[H(θ(i+1),θ(i))−H(θ(i),θ(i))]≥0

首先因為 θ ( i + 1 ) \theta^{(i+1)} θ(i+1) 使 Q ( θ , θ ( i ) ) Q(\theta^, \theta^{(i)}) Q(θ,θ(i)) 最大，是以 Q ( θ ( i + 1 ) , θ ( i ) ) ≥ Q ( θ ( i ) , θ ( i ) ) Q(\theta^{(i+1)}, \theta^{(i)}) \ge Q(\theta^{(i)}, \theta^{(i)}) Q(θ(i+1),θ(i))≥Q(θ(i),θ(i))

再證明 H ( θ ( i + 1 ) , θ ( i ) ) − H ( θ ( i ) , θ ( i ) ) < = 0 H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)}) <= 0 H(θ(i+1),θ(i))−H(θ(i),θ(i))<=0

H ( θ ( i + 1 ) , θ ( i ) ) − H ( θ ( i ) , θ ( i ) ) = ∫ Z l o g P ( Z ∣ Y , θ ( i + 1 ) ) P ( Z ∣ Y , θ ( i ) ) d Z − ∫ Z l o g P ( Z ∣ Y , θ ( i ) ) P ( Z ∣ Y , θ ( i ) ) d Z = ∫ Z l o g P ( Z ∣ Y , θ ( i + 1 ) ) P ( Z ∣ Y , θ ( i ) ) P ( Z ∣ Y , θ ( i ) ) d Z ≤ l o g   ∫ Z P ( Z ∣ Y , θ ( i + 1 ) ) P ( Z ∣ Y , θ ( i ) ) P ( Z ∣ Y , θ ( i ) ) d Z = l o g   1 = 0 H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)}) \\ = \int_{Z} log P(Z | Y, \theta^{(i+1)})P(Z|Y,\theta^{(i)}) dZ - \int_{Z} log P(Z | Y, \theta^{(i)})P(Z|Y,\theta^{(i)}) dZ \\ = \int_{Z} log \frac {P(Z | Y, \theta^{(i+1)})}{ P(Z | Y, \theta^{(i)})} P(Z|Y,\theta^{(i)}) dZ \\ \le log \ \int_{Z} \frac {P(Z | Y, \theta^{(i+1)})}{ P(Z | Y, \theta^{(i)})} P(Z|Y,\theta^{(i)}) dZ \\ = log \ 1 = 0 H(θ(i+1),θ(i))−H(θ(i),θ(i))=∫Z​logP(Z∣Y,θ(i+1))P(Z∣Y,θ(i))dZ−∫Z​logP(Z∣Y,θ(i))P(Z∣Y,θ(i))dZ=∫Z​logP(Z∣Y,θ(i))P(Z∣Y,θ(i+1))​P(Z∣Y,θ(i))dZ≤log ∫Z​P(Z∣Y,θ(i))P(Z∣Y,θ(i+1))​P(Z∣Y,θ(i))dZ=log 1=0

綜上，結論成立，即 l o g   P ( Y ∣ θ { i } ) log \ P(Y|\theta^{\{i\}}) log P(Y∣θ{i}) 單調遞增。

EM步驟簡單闡述

E L B O ( Y , q ( z ) , θ ) ELBO(Y, q(z), \theta) ELBO(Y,q(z),θ)為圖中綠色曲線， l o g   P ( Y ∣ θ ) log \ P(Y|\theta) log P(Y∣θ)為圖中黑色曲線，橫軸為 θ \theta θ

步驟如下：

1. 選取初值 θ ( 0 ) \theta^{(0)} θ(0)

2. 由以下公式可以得知ELBO曲線為對數似然函數曲線的下界，那麼為了使兩條曲線盡可能緊密，則要等于 ‘=’ 在某一個特定的 θ \theta θ 時成立，即兩條曲線有相交點

   l o g   P ( Y ∣ θ ) ≥ ∫ Z q ( Z ) l o g   P ( Y , Z ∣ θ ) q ( Z ) d Z = E L B O log \ P(Y|\theta) \ge \int_{Z} q(Z) log \ \frac {P(Y, Z | \theta)} {q(Z)} dZ = ELBO log P(Y∣θ)≥∫Z​q(Z)log q(Z)P(Y,Z∣θ)​dZ=ELBO

   每一輪疊代：

   1). 找到距離對數似然函數曲線最緊密的 E L B O ( Y , q ( z ) , θ ) ELBO(Y, q(z), \theta) ELBO(Y,q(z),θ)

   q ( Z ) = P ( Z ∣ Y , θ ( i ) ) q(Z) = P(Z | Y,\theta^{(i)}) q(Z)=P(Z∣Y,θ(i))時， E L B O ( Y , q ( i ) ( z ) , θ ( i ) ) = l o g   P ( Y ∣ θ ( i ) ) ELBO(Y, q^{(i)}(z), \theta^{(i)}) = log \ P(Y|\theta^{(i)}) ELBO(Y,q(i)(z),θ(i))=log P(Y∣θ(i))，此時，該ELBO函數與對數似然函數曲線最緊。是以 E L B O ( Y , q ( i ) ( z ) , θ ) = ∫ Z P ( Z ∣ Y , θ ( i ) ) l o g   P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) d Z ELBO(Y, q^{(i)}(z), \theta) = \int_{Z} P(Z | Y,\theta^{(i)})log \ \frac {P(Y, Z | \theta)} {P(Z | Y,\theta^{(i)})} dZ ELBO(Y,q(i)(z),θ)=∫Z​P(Z∣Y,θ(i))log P(Z∣Y,θ(i))P(Y,Z∣θ)​dZ

   2). 找到 E L B O ( Y , q ( 0 ) ( z ) , θ ) ELBO(Y, q^{(0)}(z), \theta) ELBO(Y,q(0)(z),θ)的極大值點對象的參數 θ ( i + 1 ) \theta^{(i+1)} θ(i+1)

   θ ( i + 1 ) = a r g m a x θ ∫ Z P ( Z ∣ Y , θ ( i ) ) l o g   P ( Y , Z ∣ θ ) d Z \theta^{(i+1)} = argmax_{\theta} \int_{Z} P(Z|Y, \theta^{(i)} ) log \ P(Y, Z | \theta) dZ θ(i+1)=argmaxθ​∫Z​P(Z∣Y,θ(i))log P(Y,Z∣θ)dZ

3. 重複第 2 步操作，直到收斂，一般是對較小的正數 ϵ 1 , ϵ 2 \epsilon_1, \epsilon_2 ϵ1​,ϵ2​，若滿足

   ∣ ∣ θ ( i + 1 ) − θ ( i ) ∣ ∣ < ϵ 1 或 Q ( ∣ ∣ θ ( i + 1 ) , θ ( i ) ) − Q ( θ ( i ) , θ ( i ) ) ∣ ∣ < ϵ 2 ||\theta^{(i+1)}-\theta^{(i)}|| < \epsilon_1 或 Q(||\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})|| < \epsilon_2 ∣∣θ(i+1)−θ(i)∣∣<ϵ1​或Q(∣∣θ(i+1),θ(i))−Q(θ(i),θ(i))∣∣<ϵ2​

   則停止疊代。

用另外一種思想闡述EM算法

EM算法與坐标上升法的思想大緻一樣，函數是 J ( Q , θ ) J(Q, \theta) J(Q,θ)，首先更新Q，然後再更新 θ \theta θ，重複計算，直到達到收斂條件。

EM算法的應用—高斯混合模型

EM算法的推廣—GEM