機器學習基礎：期望最大化算法（Machine Learning Fundamentals: EM Algorithm）

前言

EM算法和MLE算法的相同點在于，兩者都需要知道确定的機率密度函數形式。

若沒有隐藏變量，則可以用MLE進行估計。若資料欠缺，或存在隐含變量，則無法使用直接使用MLE進行估計，是以需要使用EM算法。

所謂的隐藏變量，指的是1. 在整個資料集中，有些資料是不完備的。2. 或者一個數學模型可以通過引入未知變量來簡化。如：高斯混合模型引入權重變量。

什麼時候使用EM算法

實際上，即使有隐藏變量，我們隻不過多加一個參數來估計而已，是以理論上也可以使用MLE的方法進行估計，即：先求對數似然函數 log likelihood, 然後求導最大化這個對數似然函數。

之是以引入EM算法，更重要的是因為多了隐變量之後，log-likelihood雖然能寫出來，但是求導麻煩了，是以不好優化了。

由于加了隐變量，我們估計模型參數時需要知道隐變量；而隐變量是不知道的，要想估計隐變量，又需要知道模型參數。是以看起來像是個死鎖。總結來說，當Q函數比似然函數l好優化時，就可以用EM算法來求。[1]

那麼EM算法是如何疊代的呢？我們可以先初始化模型參數和隐變量中的一個，然後用這個初始化的參數去估計第二個參數。然後用這個估計的第二個參數再去估計第一個參數。不斷疊代，得到最終結果，且這種政策的收斂性得到了證明。

核心思想

EM算法的核心思想是：

根據給定資料，疊代地使用最大似然估計方法（MLE）求得未知參數

[1].

基本流程

EM算法的大概流程是：1. 先根據估計的參數來求得對數似然函數（log likelihood）的期望, 這個期望還是一個函數 2. 然後再計算使該期望最大時新的參數。3. 不斷疊代前兩步直至收斂

執行個體分析

推導過程

MLE回顧

回顧MLE，對數似然函數可以寫成如下形式：

l ( θ ) = ∑ i = 1 n log ⁡ p ( x i ∣ θ ) l(\theta) = \sum_{i=1}^{n}\log p(x_i|\theta) l(θ)=i=1∑n​logp(xi​∣θ)

其中 X = { x 1 , x 2 , . . . , x n } X=\{x_1, x_2, ..., x_n\} X={x1​,x2​,...,xn​}是觀察資料。

EM

定義似然函數

相比于MLE，EM由于增加了隐随機變量 Z = { z 1 , z 2 , . . . , z n } Z=\{z_1, z_2, ..., z_n\} Z={z1​,z2​,...,zn​}，則對數似然函數需要表示成如下形式：

l ( θ ) = ∑ i = 1 n log ⁡ p ( x i ∣ θ ) = ∑ i = 1 n log ⁡ ∑ z i = 1 k p ( z i ∣ θ ) p ( x i ∣ z i , θ ) = ∑ i = 1 n log ⁡ ∑ z i = 1 k p ( x i , z i ∣ θ ) \begin{aligned} l(\theta) &= \sum_{i=1}^{n}\log p(x_i|\theta) \\ &= \sum_{i=1}^{n} \log \sum_{z_i=1}^{k}p(z_i|\theta)p(x_i|z_i, \theta)\\ &= \sum_{i=1}^{n}\log \sum_{z_i=1}^{k} p(x_i, z_i|\theta) \\ \end{aligned} l(θ)​=i=1∑n​logp(xi​∣θ)=i=1∑n​logzi​=1∑k​p(zi​∣θ)p(xi​∣zi​,θ)=i=1∑n​logzi​=1∑k​p(xi​,zi​∣θ)​

似然函數的近似

背景： 如果沒有隐變量 Z Z Z, 則上述似然函數可以直接用MLE求解了。問題是 log ⁡ \log log函數裡面還有個求和公式，是以很難直接求解這個似然函數。一種思路就是通過一種技巧把 log ⁡ \log log裡面的求和公式幹掉。

知識回顧：

1. 對于離散型随機變量 X X X, 其期望為 E ( X ) = ∑ x ∈ X x P ( x ) E(X) = \sum_{x\in X} xP(x) E(X)=∑x∈X​xP(x)
2. 設Y = g(X), 則 E ( Y ) = ∑ x ∈ X g ( x ) P ( x ) E(Y)=\sum_{x\in X}g(x)P(x) E(Y)=∑x∈X​g(x)P(x)
3. 由于 log ⁡ ( x ) \log(x) log(x)是個凹函數，有 l o g ( E ( X ) ) ≥ E ( l o g ( X ) ) log(E(X))\ge E(log(X)) log(E(X))≥E(log(X)), 如圖：

方法： 去除 log ⁡ \log log函數裡面的求和公式需要用到一些近似，具體放縮方式如下：

l ( θ ) = ∑ i = 1 n log ⁡ ∑ z i = 1 k p ( x i , z i ∣ θ ) = ∑ i = 1 n log ⁡ ∑ z i = 1 k Q i ( z i ) p ( x i , z i ∣ θ ) Q i ( z i ) ≥ ∑ i = 1 n ∑ z i = 1 k Q i ( z i ) log ⁡ p ( x i , z i ∣ θ ) Q i ( z i ) \begin{aligned} l(\theta) &= \sum_{i=1}^{n}\log \sum_{z_i=1}^{k} p(x_i, z_i|\theta) \\ &= \sum_{i=1}^{n}\log \sum_{z_i=1}^{k} Q_i(z_i) \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} \\ &\ge \sum_{i=1}^{n}\sum_{z_i=1}^{k} Q_i(z_i) \log \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} \\ \end{aligned} l(θ)​=i=1∑n​logzi​=1∑k​p(xi​,zi​∣θ)=i=1∑n​logzi​=1∑k​Qi​(zi​)Qi​(zi​)p(xi​,zi​∣θ)​≥i=1∑n​zi​=1∑k​Qi​(zi​)logQi​(zi​)p(xi​,zi​∣θ)​​

推導： 根據要點回顧，我們引入了随機變量 z i z_i zi​ 的分布 Q i ( z i ) Q_i(z_i) Qi​(zi​)。然後設

g ( z ) = p ( x i , z i ∣ θ ) Q i ( z i ) g(z)=\frac{p(x_i, z_i|\theta)}{Q_i(z_i)} g(z)=Qi​(zi​)p(xi​,zi​∣θ)​

則似然函數中第二行的 ∑ z i = 1 k Q i ( z i ) p ( x i , z i ∣ θ ) Q i ( z i ) \sum_{z_i=1}^{k} Q_i(z_i) \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} ∑zi​=1k​Qi​(zi​)Qi​(zi​)p(xi​,zi​∣θ)​可看作 E ( g ( z ) ) E(g(z)) E(g(z)), 即

E z i ( p ( x i , z i ∣ θ ) Q i ( z i ) ) E_{z_i}\left (\frac{p(x_i, z_i|\theta)}{Q_i(z_i)} \right) Ezi​​(Qi​(zi​)p(xi​,zi​∣θ)​)

又根據對數函數的性質，有 l o g ( E ( X ) ) ≥ E ( l o g ( X ) log(E(X))\ge E(log(X) log(E(X))≥E(log(X), 則：

∑ i n l o g ( E z i ( p ( x i , z i ∣ θ ) Q i ( z i ) ) ) ≥ ∑ i n E z i ( l o g ( p ( x i , z i ∣ θ ) Q i ( z i ) ) ) \sum_{i}^{n}log\left( E_{z_i}\left (\frac{p(x_i, z_i|\theta)}{Q_i(z_i)} \right) \right) \ge \sum_{i}^{n} E_{z_i}\left( log \left( \frac{p(x_i, z_i|\theta)}{Q_i(z_i)}\right) \right) i∑n​log(Ezi​​(Qi​(zi​)p(xi​,zi​∣θ)​))≥i∑n​Ezi​​(log(Qi​(zi​)p(xi​,zi​∣θ)​))

即：

∑ i = 1 n log ⁡ ∑ z i = 1 k Q i ( z i ) p ( x i , z i ∣ θ ) Q i ( z i ) ≥ ∑ i = 1 n ∑ z i = 1 k Q i ( z i ) log ⁡ p ( x i , z i ∣ θ ) Q i ( z i ) \sum_{i=1}^{n}\log \sum_{z_i=1}^{k} Q_i(z_i) \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} \ge \sum_{i=1}^{n}\sum_{z_i=1}^{k} Q_i(z_i) \log \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} i=1∑n​logzi​=1∑k​Qi​(zi​)Qi​(zi​)p(xi​,zi​∣θ)​≥i=1∑n​zi​=1∑k​Qi​(zi​)logQi​(zi​)p(xi​,zi​∣θ)​

推導完成。

似然函數的求解

這個不等式右邊被稱為 l ( θ ) l(\theta) l(θ)的下界，我們還需要确定下 Q i ( z i ) Q_i(z_i) Qi​(zi​)才能求解這個下界的最大值。求解過程如下：

若取到等号時我們的下界函數最接近原始函數，此時有：

p ( x i , z i ∣ θ ) Q i ( z i ) = c （ 常 數 ） \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} = c（常數） Qi​(zi​)p(xi​,zi​∣θ)​=c（常數）

又因為 Q i ( z i ) Q_i(z_i) Qi​(zi​)是機率分布，是以 ∑ z i = 1 k Q i ( z i ) = 1 \sum_{z_i=1}^{k}Q_i(z_i)=1 ∑zi​=1k​Qi​(zi​)=1. 将 p ( x i , z i ∣ θ ) Q i ( z i ) = c \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} = c Qi​(zi​)p(xi​,zi​∣θ)​=c 帶入對數似然函數中的 ∑ z i = 1 k Q i ( z i ) p ( x i , z i ∣ θ ) Q i ( z i ) \sum_{z_i=1}^{k}Q_i(z_i) \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} ∑zi​=1k​Qi​(zi​)Qi​(zi​)p(xi​,zi​∣θ)​， 得：

∑ z i = 1 k p ( x i , z i ∣ θ ) = c \sum_{z_i=1}^{k} p(x_i, z_i|\theta) = c zi​=1∑k​p(xi​,zi​∣θ)=c

是以有：

Q i ( z i ) = p ( x i , z i ∣ θ ) c = p ( x i , z i ∣ θ ) ∑ z i = 1 k p ( x i , z i ∣ θ ) = p ( x i , z i ∣ θ ) p ( x i ∣ θ ) = p ( z i ∣ x i , θ ) \begin{aligned} Q_i(z_i) &= \frac{p(x_i, z_i|\theta)}{c} \\ &= \frac{p(x_i, z_i|\theta)}{\sum_{z_i=1}^{k} p(x_i, z_i|\theta)} \\ &= \frac{p(x_i, z_i|\theta)}{p(x_i|\theta)} \\ &= p(z_i|x_i, \theta) \end{aligned} Qi​(zi​)​=cp(xi​,zi​∣θ)​=∑zi​=1k​p(xi​,zi​∣θ)p(xi​,zi​∣θ)​=p(xi​∣θ)p(xi​,zi​∣θ)​=p(zi​∣xi​,θ)​

一旦這個Q确定了，我們就可以求解 ( θ ) (\theta) (θ)的下界了。

我們再回顧下上述不等式，所謂E步驟，其實就是在計算一個期望，這個期望也就是 l ( θ ) l(\theta) l(θ)的下界，即:

∑ i n E z i ( l o g ( p ( x i , z i ∣ θ ) Q i ( z i ) ) ) = ∑ i = 1 n ∑ z i = 1 k Q i ( z i ) log ⁡ p ( x i , z i ∣ θ ) Q i ( z i ) \sum_{i}^{n} E_{z_i}\left( log \left( \frac{p(x_i, z_i|\theta)}{Q_i(z_i)}\right) \right) = \sum_{i=1}^{n}\sum_{z_i=1}^{k} Q_i(z_i) \log \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} i∑n​Ezi​​(log(Qi​(zi​)p(xi​,zi​∣θ)​))=i=1∑n​zi​=1∑k​Qi​(zi​)logQi​(zi​)p(xi​,zi​∣θ)​

然後我們再計算:

a r g m a x ∑ i = 1 n ∑ z i = 1 k Q i ( z i ) log ⁡ p ( x i , z i ∣ θ ) Q i ( z i ) argmax\sum_{i=1}^{n}\sum_{z_i=1}^{k} Q_i(z_i) \log \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} argmaxi=1∑n​zi​=1∑k​Qi​(zi​)logQi​(zi​)p(xi​,zi​∣θ)​

這一步就被稱為M步。

小結

通過上述分析，我們總結EM算法如下：

1. 随機初始化模型參數 θ 0 \theta^{0} θ0

2. （E步）計算聯合分布的條件機率期望 ( j = 0 , 1 , 2 , 3... ) (j = 0, 1, 2, 3 ...) (j=0,1,2,3...)

   Q i ( z i ) = p ( z i ∣ x i , θ j ) Q_i(z_i) = p(z_i|x_i, \theta^{j}) Qi​(zi​)=p(zi​∣xi​,θj)

l ( θ ， θ j ) = ∑ i = 1 n ∑ z i = 1 k Q i ( z i ) log ⁡ p ( x i , z i ∣ θ ) Q i ( z i ) l(\theta， \theta^{j}) = \sum_{i=1}^{n}\sum_{z_i=1}^{k} Q_i(z_i) \log \frac{p(x_i, z_i|\theta)}{Q_i(z_i)} \\ l(θ，θj)=i=1∑n​zi​=1∑k​Qi​(zi​)logQi​(zi​)p(xi​,zi​∣θ)​

3. (M步)極大化 l ( θ ， θ j ) l(\theta， \theta^{j}) l(θ，θj)

θ j + 1 = arg max ⁡ l ( θ , θ j ) \theta^{j+1} = \argmax l(\theta, \theta^{j}) θj+1=argmaxl(θ,θj)

4. 重複2，3直至算法收斂

思考

參考文獻

1. R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification. John Wiley & Sons, 2012.
2. EM算法詳解
3. EM算法原理及推導
4. 徐亦達機器學習：Expectation Maximization EM算法
5. 如何感性地了解EM算法？
6. 複旦-機器學習課程 第十講 EM 算法