《統(tǒng)計(jì)學(xué)習(xí)方法》第 9 章“EM 算法及其推廣”學(xué)習(xí)筆記

EM 算法，即期望最大化（Expectation-Maximum）算法，用于含有隱變量的概率模型參數(shù)的極大似然估計(jì)。區(qū)別于微積分中通過(guò)求導(dǎo)得到最優(yōu)解的方法，EM 算法是一種迭代算法，并不保證能夠得到全局最優(yōu)解，但可以得到一個(gè)局部最優(yōu)解。

我們所熟知的 k 均值聚類算法其實(shí)是 EM 算法的一個(gè)特例。

EM 算法的基本思想

EM 算法的思想是先固定其中一個(gè)，推測(cè)另一個(gè)，如此反復(fù)。

例如：模型中有兩個(gè)未知參數(shù) A 和 B 需要估計(jì)，而 A 和 B 又存在相互依賴的關(guān)系，即知道 A 才能推出 B，知道了 B 才能推出 A ，這樣的問(wèn)題就可以用 EM 算法。

使用極大似然估計(jì)，通過(guò)迭代算法，既能估計(jì)模型的參數(shù)，并且還能得到隱變量的值。注意：EM 算法并不保證得到全局最優(yōu)解，但是可以得到局部最優(yōu)解，這一點(diǎn)和梯度下降法是一樣的，最終的解和初值有關(guān)，這一點(diǎn)在 k 均值聚類算法中是一樣的。

EM 算法用于解決含有隱含變量的概率模型的參數(shù)估計(jì)問(wèn)題

EM 算法是對(duì)概率模型進(jìn)行參數(shù)估計(jì)是一種常見(jiàn)的問(wèn)題分析的方法。當(dāng)然概率模型僅存在觀測(cè)數(shù)據(jù)的時(shí)候，可以直接利用最大似然估計(jì)的方法，對(duì)似然函數(shù)取對(duì)數(shù)，令各個(gè)參數(shù)的偏導(dǎo)數(shù)為 0，求得的參數(shù)的值作為參數(shù)的估計(jì)。

但是如果模型含有隱變量，并且隱函數(shù)和模型參數(shù)是互相影響的，就可以通過(guò)使用 EM 算法，通過(guò)迭代地求解隱含變量的充分統(tǒng)計(jì)量和最大化似然函數(shù)以達(dá)到參數(shù)估計(jì)的算法。這樣即求得了隱變量，還得到了問(wèn)題的參數(shù)估計(jì)。

EM 算法剛接觸的時(shí)候感覺(jué)很晦澀，不過(guò)如果熟悉了k 均值聚類算法，往 EM 算法上靠就會(huì)發(fā)現(xiàn)， k 均值聚類算法其實(shí)就是在執(zhí)行 EM 算法這個(gè)框架。先學(xué)習(xí) k 均值聚類，再來(lái)看 EM 算法，或許入門會(huì)簡(jiǎn)單一些。

通過(guò) k 均值聚類算法學(xué)習(xí) EM 算法

這里“同類數(shù)據(jù)點(diǎn)到其中心的距離之和最短”就等價(jià)于似然函數(shù)最大。

學(xué)習(xí) EM 算法的時(shí)候，很容易把自己繞暈，陷入“雞生蛋、蛋生雞”的循環(huán)，不過(guò)可以通過(guò) k 均值聚類理解 EM 算法的 E 步和 M 步。在 k 均值聚類中，首先要明確“模型參數(shù)”和“隱變量”分別是什么？

1、每個(gè)聚類簇的質(zhì)心是“隱變量”，“隱變量”決定了一個(gè)數(shù)據(jù)屬于哪一個(gè)類別，一個(gè)數(shù)據(jù)屬于距離它最近的質(zhì)心所所屬的類別。

2、我們要求的是哪些數(shù)據(jù)可以歸為一類，這我們可以理解為是“模型的參數(shù)”，是我們直接要求的；

接下來(lái)，我們對(duì)比 k 均值聚類算法和 EM 算法：

k 均值聚類算法 EM 算法 說(shuō)明
（1）選擇參數(shù)的初值，開(kāi)始迭代；
（1）首先選擇 k 個(gè)類別的中心；（3）然后更新每個(gè)樣本的均值，作為類的新的中心。 （2）E 步：記 \theta^{(i)} 為第 i 次迭代參數(shù) \theta 的估計(jì)值，在第 i+1 次迭代的 E 步，計(jì)算 Q(\theta,\theta^{(i)})； 求出隱變量
（2）將樣本逐個(gè)指派到與其最近的中心的類中，得到一個(gè)聚類的結(jié)果。 （3）M 步：求使 Q(\theta,\theta^{(i)}) 極大化的 \theta，確定第 i+1 次迭代的參數(shù)的估計(jì)值 \theta^{(i + 1)}； 求出模型參數(shù)
重復(fù)第（3）步和第（2）步，直到收斂為止。 （4）重復(fù)第（2）步和第（3）步，直到收斂。
李航《統(tǒng)計(jì)學(xué)習(xí)方法》（第 2 版）P264 李航《統(tǒng)計(jì)學(xué)習(xí)方法》（第 2 版）P178

我又畫(huà)了一個(gè)表格，可能這樣看會(huì)更清楚一些：

k 均值聚類 聚類算法 EM 算法
第 1 步：隨機(jī)初始化給出質(zhì)心，這一步可以認(rèn)為是求出了隱變量。 E 步：固定模型參數(shù)，求隱含變量。
第 2 步：固定質(zhì)心，把每個(gè)數(shù)據(jù)分配給最近的質(zhì)心，這一步可以認(rèn)為是求出模型參數(shù)。 M 步：固定隱含變量，求模型參數(shù)。
第 3 步：把是同類數(shù)據(jù)點(diǎn)取平均，更新質(zhì)心，這一步可以認(rèn)為是求出了隱變量。 E 步：固定模型參數(shù)，求隱含變量。
第 4 步：固定質(zhì)心，把每個(gè)數(shù)據(jù)分配給最近的質(zhì)心，這一步可以認(rèn)為是求出模型參數(shù)。 M 步：固定隱含變量，求模型參數(shù)。
重復(fù)第 3 步、第 4 步，直到質(zhì)心不再變化或者滿足最大迭代次數(shù)位置。 重復(fù) E 步和 M 步。

這里再?gòu)?qiáng)調(diào)一下：k 均值聚類算法的隱變量是質(zhì)心，模型的參數(shù)是每個(gè)數(shù)據(jù)點(diǎn)屬于哪個(gè)分類。再看看 EM 算法的 E 步和 M 步：

  • E 步（固定模型參數(shù)，求隱變量）

同類數(shù)據(jù)點(diǎn)取平均，其實(shí)就是在每一個(gè)數(shù)據(jù)點(diǎn)確定的情況下，求隱變量質(zhì)心的概率分布。具體說(shuō)來(lái)，即我們已知一些數(shù)據(jù)點(diǎn)的集合 S，我們想求得一個(gè)點(diǎn) o，使得這個(gè)點(diǎn) o 與所有集合 S 中的點(diǎn)的距離之和最小，我們很容易知道，這個(gè)點(diǎn) o 就應(yīng)該取成集合 S 中所有的點(diǎn)的各個(gè)分類的平均值（用距離之和對(duì)每個(gè)分量求偏導(dǎo)，并令偏導(dǎo)數(shù)為 0）

根據(jù)參數(shù)初始值或上一次迭代的模型參數(shù)來(lái)計(jì)算出隱性變量的后驗(yàn)概率，其實(shí)就是隱變量的期望，作為隱藏變量的現(xiàn)估計(jì)值。即在當(dāng)前估計(jì)的參數(shù) \theta(t) 的情況下給定 X，計(jì)算對(duì)數(shù)似然函數(shù)在條件分布 Z 下的期望值，即

Q(\theta|\theta(t))=E_{Z|X,\theta(t)}[\log L(\theta;X,Z)]

  • M 步（固定隱變量，求模型參數(shù)）

固定隱變量的前提下，求經(jīng)過(guò)隱變量改寫(xiě)的似然函數(shù)的極大。質(zhì)心確定的前提下，每個(gè)數(shù)據(jù)點(diǎn)分給最近的質(zhì)心就能夠使同類數(shù)據(jù)點(diǎn)到其中心的距離之和最短。找出使上式最大化的參數(shù)：

\theta(t+1) = {\rm argmax}_{\theta}Q(\theta|\theta(t))

示例代碼：

from sklearn.mixture import GaussianMixture

參數(shù)有：1、高斯混合模型的個(gè)數(shù)；2、協(xié)方差的類型；3、最大迭代次數(shù)。

理解 EM 算法的迭代步驟

EM 算法的迭代步驟

首先先找到“紫”線的一個(gè)下界函數(shù)，即“藍(lán)”線，一定要有重合的那一個(gè)“點(diǎn)”，即被圖中“綠”線確定的那個(gè)點(diǎn)。

然后對(duì)“藍(lán)”線取極大值，即被圖中“紅”線確定的那個(gè)點(diǎn)。

如此反復(fù)，你會(huì)看到，只會(huì)逐步來(lái)到局部最優(yōu)值點(diǎn)。

公式推導(dǎo)

手寫(xiě)筆記，我寫(xiě)在這里了：EM 算法手寫(xiě)筆記。

在公式推導(dǎo)的過(guò)程中，要用到 Jensen 不等式或者 KL 散度，也稱相對(duì)熵。關(guān)于 Jensen 不等式，我寫(xiě)在這里了：Jenson 不等式的筆記。關(guān)于 KL 散度，我寫(xiě)在這里了：信息熵、條件熵、聯(lián)合熵、互信息、相對(duì)熵、交叉熵。

細(xì)節(jié)一：在使用 Jensen 不等式的時(shí)候，需要假設(shè)隱變量服從某種形式的概率分布，才可以將推導(dǎo)過(guò)程的一部分看成是期望的表達(dá)形式從而應(yīng)用 Jensen 不等式。然而這個(gè)分布不是隨便指定的。我們令 Jensen 不等式取等號(hào)的時(shí)候，可以計(jì)算出這個(gè)分布其實(shí)就是：已知觀測(cè)數(shù)據(jù)的隱變量的后驗(yàn)概率分布。由于求 Q 函數(shù)需要先求出隱變量的后驗(yàn)概率的期望，因此，這就可以解釋為什么EM算法的“通俗”理解角度的E步驟是求隱變量的期望了。

細(xì)節(jié)二：Q 函數(shù)與完全數(shù)據(jù)的對(duì)數(shù)似然函數(shù)的關(guān)系。有時(shí)候在用 EM 算法解決某個(gè)具體問(wèn)題的時(shí)候，會(huì)發(fā)現(xiàn) M 步驟極大化的居然是完全數(shù)據(jù)的對(duì)數(shù)似然函數(shù)。這是因?yàn)椋琎 函數(shù)雖然是完全數(shù)據(jù)的對(duì)數(shù)似然函數(shù)的某種期望，但是求這個(gè)期望的過(guò)程有時(shí)其實(shí)就是將隱變量的后驗(yàn)概率的期望代入就可以了。因此，本質(zhì)上我們其實(shí)還是在求 Q 函數(shù)的極大。

高斯混合模型

模型假設(shè)：多個(gè)高斯分布的加權(quán)平均（線性組合），權(quán)重（系數(shù)）之和為 1。

隱變量 z ：樣本 x 屬于哪一個(gè)高斯分布，x 與 z 一一對(duì)應(yīng)，因?yàn)?z 是離散型隨機(jī)變量，因此可以有一個(gè)概率分布（可以認(rèn)為屬于兩個(gè)分布，概率有大有?。?/p>

生成模型：生成過(guò)程如下：1、隨機(jī)選擇一個(gè)高斯分布；2、從這個(gè)高斯分布生成一個(gè)數(shù)據(jù)。

直接使用極大似然估計(jì)，不能得到解析解。

下面是高斯混合模型的例子：

輸入：觀測(cè)數(shù)據(jù)和類別的總數(shù)。

輸出：觀測(cè)數(shù)據(jù)所服從的幾個(gè)分布函數(shù)的參數(shù)。

例如：輸入：7000 份成績(jī)，來(lái)自 4 個(gè)科目：語(yǔ)文、數(shù)學(xué)、英語(yǔ)、計(jì)算機(jī)。
輸出：4 個(gè)科目分別服從的分布的參數(shù)值，由于各科成績(jī)服從高斯分布，因此輸出為每科成績(jī)的分布參數(shù) Y=\{(\mu_1,\sigma_1),(\mu_2,\sigma_2),(\mu_3,\sigma_3)(\mu_4,\sigma_4)\}，以及樣本服從各個(gè)分布的概率 \phi = \{\phi_1,\phi_2,\phi_3,\phi_4\}。

EM 算法解決這個(gè)的思路是使用啟發(fā)式的迭代方法，既然我們無(wú)法直接求出模型分布參數(shù)，那么我們可以先猜想隱含參數(shù)（EM 算法的 E 步），接著基于觀察數(shù)據(jù)和猜測(cè)的隱含參數(shù)一起來(lái)極大化對(duì)數(shù)似然，求解我們的模型參數(shù)（EM算法的M步)。由于我們之前的隱含參數(shù)是猜測(cè)的，所以此時(shí)得到的模型參數(shù)一般還不是我們想要的結(jié)果。我們基于當(dāng)前得到的模型參數(shù)，繼續(xù)猜測(cè)隱含參數(shù)（EM算法的 E 步），然后繼續(xù)極大化對(duì)數(shù)似然，求解我們的模型參數(shù)（EM算法的M步)。以此類推，不斷的迭代下去，直到模型分布參數(shù)基本無(wú)變化，算法收斂，找到合適的模型參數(shù)。

這個(gè)時(shí)候有人就想到我們必須從某一點(diǎn)開(kāi)始，并用迭代的辦法去解決這個(gè)問(wèn)題：我們先設(shè)定男生身高和女生身高分布的幾個(gè)參數(shù)（初始值），然后根據(jù)這些參數(shù)去判斷每一個(gè)樣本（人）是男生還是女生，之后根據(jù)標(biāo)注后的樣本再反過(guò)來(lái)重新估計(jì)參數(shù)。之后再多次重復(fù)這個(gè)過(guò)程，直至穩(wěn)定。這個(gè)算法也就是EM算法。

又如：得到一堆身高數(shù)據(jù)，但是不知道這些身高數(shù)據(jù)是男生還是女生。

對(duì)于每一個(gè)樣本或者你抽取到的人，就有兩個(gè)問(wèn)題需要估計(jì)了，一是這個(gè)人是男的還是女的，二是男生和女生對(duì)應(yīng)的身高的正態(tài)分布的參數(shù)是多少。這兩個(gè)問(wèn)題是相互依賴的。

有了每個(gè)人的歸屬，或者說(shuō)我們已經(jīng)大概地按上面的方法將這 200 個(gè)人分為男生和女生兩部分，我們就可以根據(jù)之前說(shuō)的最大似然那樣，
通過(guò)這些被大概分為男生的 n 個(gè)人來(lái)重新估計(jì)第一個(gè)分布的參數(shù)，女生的那個(gè)分布同樣方法重新估計(jì)。這個(gè)是 Maximization。

然后，當(dāng)我們更新了這兩個(gè)分布的時(shí)候，每一個(gè)屬于這兩個(gè)分布的概率又變了，那么我們就再需要調(diào)整 E 步。如此往復(fù)，直到參數(shù)基本不再發(fā)生變化為止。

具體方法為：隱變量是一個(gè)數(shù)據(jù)是男生身高數(shù)據(jù)還是女生身高數(shù)據(jù)。

E 步：先設(shè)定男生和女生的身高分布參數(shù)（初始值，即模型參數(shù)），例如男生的身高分布為 ， 女生的身高分布為 ，當(dāng)然了，剛開(kāi)始肯定沒(méi)那么準(zhǔn)；
然后計(jì)算出每個(gè)人更可能屬于第一個(gè)還是第二個(gè)正態(tài)分布中的（例如，這個(gè)人的身高是 180cm，那很明顯，他極大可能屬于男生），這個(gè)是屬于 Expectation 一步；

M 步：求問(wèn)題參數(shù)，我們已經(jīng)大概地按上面的方法將這 200 個(gè)人分為男生和女生兩部分，我們就可以根據(jù)之前說(shuō)的極大似然估計(jì)分別對(duì)男生和女生的身高分布參數(shù)進(jìn)行估計(jì)（這不變成了極大似然估計(jì)了嗎？極大即為Maximization）這步稱為 Maximization。

然后，當(dāng)我們更新這兩個(gè)分布的時(shí)候，每一個(gè)學(xué)生屬于女生還是男生的概率又變了，那么我們就再需要調(diào)整 E 步；
如此往復(fù)，直到參數(shù)基本不再發(fā)生變化或滿足結(jié)束條件為止。

上面的學(xué)生屬于男生還是女生我們稱之為隱含參數(shù)，女生和男生的身高分布參數(shù)稱為模型參數(shù)。

EM 算法解決這個(gè)的思路是使用啟發(fā)式的迭代方法，既然我們無(wú)法直接求出模型分布參數(shù)，那么我們可以先猜想隱含參數(shù)（EM 算法的 E 步），接著基于觀察數(shù)據(jù)和猜測(cè)的隱含參數(shù)一起來(lái)極大化對(duì)數(shù)似然，求解我們的模型參數(shù)（EM 算法的 M 步)。由于我們之前的隱含參數(shù)是猜測(cè)的，所以此時(shí)得到的模型參數(shù)一般還不是我們想要的結(jié)果。我們基于當(dāng)前得到的模型參數(shù)，繼續(xù)猜測(cè)隱含參數(shù)（EM 算法的 E 步），然后繼續(xù)極大化對(duì)數(shù)似然，求解我們的模型參數(shù)（EM 算法的 M 步)。以此類推，不斷的迭代下去，直到模型分布參數(shù)基本無(wú)變化，算法收斂，找到合適的模型參數(shù)。

這個(gè)時(shí)候有人就想到我們必須從某一點(diǎn)開(kāi)始，并用迭代的辦法去解決這個(gè)問(wèn)題：我們先設(shè)定男生身高和女生身高分布的幾個(gè)參數(shù)（初始值），然后根據(jù)這些參數(shù)去判斷每一個(gè)樣本（人）是男生還是女生，之后根據(jù)標(biāo)注后的樣本再反過(guò)來(lái)重新估計(jì)參數(shù)。之后再多次重復(fù)這個(gè)過(guò)程，直至穩(wěn)定。這個(gè)算法也就是EM算法。

引入了坐標(biāo)上升法。

應(yīng)用： EM 算法有很多的應(yīng)用，最廣泛的就是 GMM 混合高斯模型、聚類、HMM 等等。
具體可以參考 JerryLead 的 cnblog 中 的Machine Learning 專欄。

應(yīng)用：隱馬爾科夫模型， LDA 主題模型。

參考資料

[1] 李航. 統(tǒng)計(jì)學(xué)習(xí)方法（第 2 版）第 9 章“EM 算法及其推廣”. 北京：清華大學(xué)出版社，2019.

說(shuō)明：公式很多，寫(xiě)得比較晦澀，但是比較全面，理解書(shū)上的內(nèi)容和細(xì)節(jié)要查閱一些資料。

[2] 周志華. 機(jī)器學(xué)習(xí)（第 7 章第 6 節(jié)“EM 算法”）. 北京：清華大學(xué)出版社，2017.

（本節(jié)完）

以下為草稿，我自己留著備用，讀者可以忽略，歡迎大家批評(píng)指正。

參考資料

1、知乎：EM算法存在的意義是什么？

https://www.zhihu.com/question/40797593/answer/275171156

2、Orange先生：淺談 EM 算法的兩個(gè)理解角度
https://blog.csdn.net/xmu_jupiter/article/details/50936177

說(shuō)明：這篇文章沒(méi)有抄公式，把重要的思想部分提取出來(lái)。

3、人人都懂EM算法：https://zhuanlan.zhihu.com/p/36331115
說(shuō)明：看這篇文章終于知道了個(gè)大概。

4、劉建平的文章：https://www.cnblogs.com/pinard/p/6912636.html

說(shuō)明：如果手邊沒(méi)有《統(tǒng)計(jì)學(xué)習(xí)方法》這本書(shū)，可以看這篇博客。

5、Lasso回歸算法： 坐標(biāo)軸下降法與最小角回歸法小結(jié)：
http://www.cnblogs.com/pinard/p/6018889.html

6、混合高斯模型（Mixtures of Gaussians）和EM算法
https://www.cnblogs.com/jerrylead/archive/2011/04/06/2006924.html

7、數(shù)據(jù)分析師進(jìn)階必備6大數(shù)學(xué)利器
https://mp.weixin.qq.com/s/BH4hsLjv7rLvR8xOLU1iNQ

8、矩陣論：向量范數(shù)和矩陣范數(shù)
https://blog.csdn.net/pipisorry/article/details/51030563

9、知乎上的問(wèn)題：怎么通俗易懂地解釋EM算法并且舉個(gè)例子?
https://www.zhihu.com/question/27976634/answer/163164402

10、從最大似然到EM算法淺解
https://blog.csdn.net/zouxy09/article/details/8537620

11、深入淺出之EM算法(一）

12、深入淺出EM算法（2）

13、極客時(shí)間：

28丨EM聚類（上）：如何將一份菜等分給兩個(gè)人？

29丨EM聚類（下）：用EM算法對(duì)王者榮耀英雄進(jìn)行劃分

14、從最大似然到EM算法淺解。

15、K-Means聚類算法原理
http://www.cnblogs.com/pinard/p/6164214.html

16、用scikit-learn學(xué)習(xí)K-Means聚類
https://www.cnblogs.com/pinard/p/6169370.html

17、http://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.LabelEncoder.html

18、“上帝的算法”——EM
https://blog.csdn.net/sb19931201/article/details/53586468?utm_source=blogxgwz1
這篇文章主要是摘抄。寫(xiě)了很多參考文獻(xiàn)。

說(shuō)明：這篇文章 EM 算法的推導(dǎo)直接從極大似然估計(jì)開(kāi)始，講到了我們的目標(biāo)就是求觀測(cè)數(shù)據(jù)的極大似然。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容