文章目錄

• EM 算法
• 1. EM 算法的引入
• • 三硬幣模型
• 2. EM 算法
• • Q 函數
• 參考文獻

相關文章：

機器學習 | 目錄

無監督學習 | GMM 高斯混合原理及Sklearn實現

本文大部分內容搬運自李航老師的《統計學習方法》^[1]，以給出 EM 算法較為完整的定義。

EM 算法

EM 算法是一種迭代算法，1977 年由 Dempster 等人總結提出，用于含有隱變量（hidden variable）的概率模型參數的極大似然估計，或極大后驗估計。

EM 算法的每次迭代由兩步組成：E 步：求期望（expectation）；M 步：求極大（maximization）。所以這一算法稱為期望極大算法（expectation maximization algorithm, EM）。

1. EM 算法的引入

概率模型有時即含有觀測數據（observable varible，已知），又含有隱變量或潛在變量（latent varible，未知），如果概率模型的變量都是觀測變量，那么給定數據，可以直接使用極大似然估計，或貝葉斯估計法估計模型參數。但是，當模型含有隱變量時，就不能簡單地使用這些估計方法。EM 算法就是含有隱變量的概率模型參數的極大似然估計。

三硬幣模型

假設有三枚硬幣，分別記作 A，B，C。這些硬幣正面出現的概率分別是 $\pi$，$p$ 和 $q$。進行如下擲硬幣試驗：

先擲硬幣 A ，若為正面則選硬幣 B ，若為反面則選硬幣 C ；然后擲 A 選出的硬幣（ B 或 C ），若為正面則記作 1，若為反面則記作 0，試驗結束。

獨立重復試驗 $n$ 次（這里 $n=10$），觀測結果如下：

$$1,1,0,1,0,0,1,0,1,1$$

假設只能觀測到擲硬幣的結果，不能觀測擲硬幣的過程，問如何估計三硬幣正面出現的概率，即三硬幣模型的參數。

解 三硬幣模型可以寫作：

$$\begin{array}{rl}P(y|\theta )& =\sum _{z}P(y,z|\theta )=\sum _{z}P(z|\theta )P(y|z,\theta )\\ & =\pi p^y(1?p{)}^{1?y}+(1?\pi )q^y(1?q{)}^{1?y}\end{array}\text{\hspace{1em}(1)}$$

這里，隨機變量 $y$ 是觀測變量，表示一次試驗觀測的結果是 1 或 0；隨機變量 $z$ 是隱變量，表示未觀測到的擲硬幣 A 的結果；$\theta =(\pi ,p,q)$ 是模型參數。這一模型是以上數據的生成模型。注意，隨機變量 $y$ 的數據可以觀測，隨機變量 $z$ 的數據不可觀測。

將觀測數據表示為 $Y=(Y_1,Y_2,...,Y_n{)}^T$ ，未觀測數據表示為 $Z=(Z_1,Z_2,...,Z_n{)}^T$，則觀測數據的似然函數為：

$$P(Y|\theta )=\sum _{Z}P(Z|\theta )P(Y|Z,\theta )\text{\hspace{1em}(2)}$$

即

$$P(Y|\theta )=\prod _{j=1}^n\left[\pi p^{y_j}(1?p{)}^{1?y_j}+(1?\pi )q^{y_j}(1?q{)}^{1?y_j}\right]\text{\hspace{1em}(3)}$$

考慮求模型參數 $\theta =(\pi ,p,q)$，即：

$$\hat{\theta }=arg\underset{\theta }{\max }logP(Y|\theta )\text{\hspace{1em}(4)}$$

這個問題沒有解析解，只有通過迭代的方法求解。EM 算法就是可以用于求解這個問題的一種迭代算法。下面給出針對以上問題的 EM 算法，其推導過程省略。

EM 算法首先選取參數的初值，記作 ${\theta }^{(0)}=({\pi }^{(0)},p^{(0)},q^{(0)})$ ，然后通過下面的步驟迭代計算參數的估計值，直至收斂為止。第 $i$ 次迭代參數的估計值為 ${\theta }^{(i)}=({\pi }^{(i)},p^{(i)},q^{(i)})$。EM 算法的第 $i+1$ 次迭代如下：

E 步：計算在模型參數 ${\pi }^{(i)},p^{(i)},q^{(i)}$ 下觀測數據 $y_i$ 來自擲硬幣 B 的概率：

$${\mu }^{(i+1)}=\frac{{\pi }^{(i)}{\left(p^{(i)}\right)}^{y_j}{\left(1?p^{(i)}\right)}^{1?y_j}}{{\pi }^{(i)}{\left(p^{(i)}\right)}^{y_j}{\left(1?p^{(i)}\right)}^{1?y_j}+\left(1?{\pi }^{(i)}\right){\left(q^{(i)}\right)}^{y_j}{\left(1?q^{(i)}\right)}^{1?y_j}}\text{\hspace{1em}(5)}$$

M 步：計算模型參數的新估計值

$${\pi }^{(i+1)}=\frac{1}{n}\sum _{j=1}^n{\mu }_j^{(i+1)}\text{\hspace{1em}(6)}$$

$$p^{(i+1)}=\frac{{\sum }_{j=1}^n{\mu }_j^{(i+1)}{y}_j}{{\sum }_{j=1}^n{\mu }_j^{(i+1)}}\text{\hspace{1em}(7)}$$

$$q^{(i+1)}=\frac{{\sum }_{j=1}^n\left(1?{\mu }_j^{(i+1)}\right)y_j}{{\sum }_{j=1}^n}\text{\hspace{1em}(8)}$$

進行數字計算。假設模型參數的初值取為：

$${\pi }^{(0)}=0.5,p^{(0)}=0.5,q^{(0)}=0.5$$

由式 (5)，對 $y_j=1$ 與 $y_j=0$ 均有 ${\mu }_j^{(1)}=0.5$。

利用迭代公式 (6-8) ，得到：

$${\pi }^{(1)}=0.5,p^{(1)}=0.6,q^{(1)}=0.6$$

由式 (5)，

$${\mu }_j^{(2)}=0.5,j=1,2,...,10$$

繼續迭代，得：

$${\pi }^{(2)}=0.5,p^{(2)}=0.6,q^{(2)}=0.6$$

可以看到參數以及收斂，于是得到模型參數 $\theta$ 的極大似然估計：

$$\hat{\pi }=0.5,\hat{p}=0.6\hat{q}=0.6$$

$\pi =0.5$ 表示硬幣 A 是均勻的，這一結果容易理解。

如果取初值${\pi }^{(0)}=0.5,p^{(0)}=0.6,q^{(0)}=0.7$，那么得到的模型參數的極大似然估計是 $\hat{\pi }=0.4064,\hat{p}=0.5368\hat{q}=0.6432$ 。這就是說，EM 算法與初值的選擇有關，選擇不同的初值可能得到不同的參數估計值。

---

一般地，用 $Y$ 表示觀測隨機變量的數據，$Z$ 表示隱隨機變量的數據。$Y$ 和 $Z$ 連在一起稱為完全數據（complete-data），觀測數據 $Y$ 又稱為不完全數據（incomplete-data）。假設給定觀測數據 $Y$，其概率分布是 $P(Y|\theta )$，其中 $\theta$ 是需要估計的模型參數，那么不完全數據 $Y$ 的似然函數是 $P(Y|\theta )$，對數似然函數為 $L(\theta )=\log P(Y|\theta )$；假設 $Y$ 和 $Z$ 的聯合概率分布是 $P(Y,Z|\theta )$，那么完全數據的對數似然函數是 $\log P(Y,Z|\theta )$。

EM 算法通過迭代求 $L(\theta )=\log P(Y|\theta )$ 的極大似然估計。每次迭代包含兩步：E 步，求期望；M 步，求極大化。

2. EM 算法

輸入：觀測變量數據 $Y$，隱變量數據 $Z$，聯合分布 $P(Y,Z|\theta )$，條件分布 $P(Z|Y.\theta )$；

輸出；模型參數 $\theta$。

（1）選擇參數的初值 ${\theta }^{(0)}$，開始迭代；

（2）E 步：記 ${\theta }^{(i)}$ 為第 $i$ 次迭代參數 $\theta$ 的估計值，在第 $i+1$ 次迭代的 E 步，計算：

$$\begin{array}{rl}Q\left(\theta ,{\theta }^{(i)}\right)& =E_Z\left[\log P(Y,Z|\theta )|Y,{\theta }^{(i)}\right]\\ & =\sum _Z\log P(Y,Z|\theta )P\left(Z|Y,{\theta }^{(i)}\right)\end{array}\text{\hspace{1em}(9)}$$

（3）M 步：求使 $Q(\theta ,{\theta }^{(i)})$ 極大化的 $\theta$，確定第 $i+1$ 次迭代的參數的估計值 ${\theta }^{(i+1)}$：

$${\theta }^{(i+1)}=arg\underset{\theta }{\max }Q(\theta ,{\theta }^{(i)})\text{\hspace{1em}(10)}$$

（4）重復第 (2-3) 步，直到收斂。

---

下面關于 EM 算法作幾點說明：

步驟 (1) 參數的初值可以任意選擇，但需注意 EM 算法對初值是敏感的；

步驟 (2) E 步求 $Q(\theta ,{\theta }^{(i)})$ 。Q 函數式中 Z 是未觀測數據，Y 是觀測數據。注意，$Q(\theta ,{\theta }^{(i)})$ 的第 1 個表示要極大化的參數，第 2 個變元表示參數的當前估計值。每次迭代實際在求 Q 函數及其極大；

步驟 (3) M 步求 $Q(\theta ,{\theta }^{(i)})$ 的極大化，得到 ${\theta }^{(i+1)}$，完成一次迭代 ${\theta }^{(i)}\to {\theta }^{(i+1)}$，且每次迭代使似然函數增大或達到局部極值；

步驟 (4) 給出停止迭代的條件，一般是對較小的正值 ${\epsilon }_1,{\epsilon }_2$，若滿足：

$$\Vert {\theta }^{(i+1)}?{\theta }^{(i)}\Vert <{\epsilon }_{1}or\Vert Q\left({\theta }^{(i+1)},{\theta }^{(i)}\right)?Q\left({\theta }^{(i)},{\theta }^{(i)}\right)\Vert <{\epsilon }_2\text{\hspace{1em}(11)}$$

則停止迭代。

---

式 (9) 的函數 $Q(\theta ,{\theta }^{(i)})$ 是 EM 算法的核心，稱為 Q 函數（Q function）。

Q 函數

完全數據的對數似然函數 $\log P(Y,Z|\theta )$ 關于在給定觀測數據 $Y$ 和當前參數 ${\theta }^{(i)}$ 下對未觀測數據 Z 的條件概率分布 $P(Z|Y,{\theta }^{(i)})$ 的期望稱為 Q 函數，即：

$$Q\left(\theta ,{\theta }^{(i)}\right)=E_z\left[\log P(Y,Z|\theta )|Y,{\theta }^{(i)}\right]\text{\hspace{1em}(11)}$$

參考文獻

[1] 周志華. 機器學習[M]. 北京: 清華大學出版社, 2016: 155-158.

總結

以上是生活随笔為你收集整理的机器学习 | EM 算法原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。