EM算法詳解

2021-02-13 Microstrong

目錄:

1. 摘要

2. EM算法簡介

3. 預備知識

    3.1 極大似然估計

    3.2 Jensen不等式

4. EM算法詳解

    4.1 問題描述

    4.2 EM算法推導流程

    4.3 EM算法流程

5. EM算法若干思考

    5.1 對EM算法的初始化研究

    5.2 EM算法是否一定收斂?

    5.3 如果EM算法收斂,能否保證收斂到全局最大值?

6. EM算法實例

7. 對EM算法總結

1. 摘要

EM(Expectation-Maximum)算法也稱期望最大化算法,曾入選「數據挖掘十大算法」中,可見EM算法在機器學習、數據挖掘中的影響力。EM算法是最常見的隱變量估計方法,在機器學習中有極為廣泛的用途,例如常被用來學習高斯混合模型(Gaussian mixture model,簡稱GMM)的參數;隱式馬爾科夫算法(HMM)、LDA主題模型的變分推斷等等。本文就對EM算法的原理做一個詳細的總結。

【擴展閱讀】數據挖掘中十大算法論文:

Wu X, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and information systems, 2008, 14(1): 1-37.

論文下載地址:http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf

2. EM算法簡介

EM算法是一種迭代優化策略,由於它的計算方法中每一次迭代都分兩步,其中一個為期望步(E步),另一個為極大步(M步),所以算法被稱為EM算法(Expectation-Maximization Algorithm)。EM算法受到缺失思想影響,最初是為了解決數據缺失情況下的參數估計問題,其算法基礎和收斂有效性等問題在Dempster、Laird和Rubin三人於1977年所做的文章《Maximum likelihood from incomplete data via the EM algorithm》中給出了詳細的闡述。其基本思想是:首先根據己經給出的觀測數據,估計出模型參數的值;然後再依據上一步估計出的參數值估計缺失數據的值,再根據估計出的缺失數據加上之前己經觀測到的數據重新再對參數值進行估計,然後反覆迭代,直至最後收斂,迭代結束。

【擴展閱讀】提出EM算法的論文

Dempster A P, Laird N M, Rubin D B. Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the royal statistical society. Series B (methodological), 1977: 1-38.

論文下載地址:http://web.mit.edu/6.435/www/Dempster77.pdf

3. 預備知識

想清晰的了解EM算法推導過程和其原理,我們需要知道兩個基礎知識:「極大似然估計」和「Jensen不等式」。

3.1 極大似然估計

(1)問題描述

假如我們需要調查學校的男生和女生的身高分布 ,我們抽取100個男生和100個女生,將他們按照性別劃分為兩組。然後,統計抽樣得到100個男生的身高數據和100個女生的身高數據。如果我們知道他們的身高服從正態分布,但是這個分布的均值和方差是不知道,這兩個參數就是我們需要估計的。

問題:我們知道樣本所服從的概率分布模型和一些樣本,我們需要求解該模型的參數。如圖1所示。

圖1:問題求解過程

我們已知的條件有兩個:樣本服從的分布模型、隨機抽取的樣本。我們需要求解模型的參數。根據已知條件,通過極大似然估計,求出未知參數。總的來說:極大似然估計就是用來估計模型參數的統計學方法。

(2)用數學知識解決現實問題

問題數學化:樣本集,概率密度是:抽到第i個男生身高的概率。由於100個樣本之間獨立同分布,所以同時抽到這100個男生的概率是它們各自概率的乘積,就是從分布是p(X|θ)的總體樣本中抽取到這100個樣本的概率,也就是樣本集X中各個樣本的聯合概率,用下式表示:

這個概率反映了在概率密度函數的參數是θ時,得到X這組樣本的概率。 我們需要找到一個參數θ,使得抽到X這組樣本的概率最大,也就是說需要其對應的似然函數L(θ)最大。滿足條件的θ叫做θ的最大似然估計值,記為:

(3)最大似然函數估計值的求解步驟

然後,對上式求導,另導數為0,得到似然方程。

最後,解似然方程,得到的參數值即為所求。

多數情況下,我們是根據已知條件來推算結果,而極大似然估計是已知結果,尋求使該結果出現的可能性最大的條件,以此作為估計值。

3.2 Jensen不等式

(1)定義

設f是定義域為實數的函數,如果對所有的實數x,f(x)的二階導數都大於0,那麼f是凸函數。

Jensen不等式定義如下:

如果f是凸函數,X是隨機變量,那麼: 。若且唯若X是常量時,該式取等號。其中,E(X)表示X的數學期望。

註:Jensen不等式應用於凹函數時,不等號方向反向。若且唯若x是常量時,該不等式取等號。

(2)舉例

圖2:Jensen不等式

圖2中,實線f表示凸函數,X是隨機變量,有0.5的概率是a,有0.5的概率是b。X的期望值就是a和b的中值,從圖中可以看到 成立。

4. EM算法詳解

4.1 問題描述

我們目前有100個男生和100個女生的身高,但是我們不知道這200個數據中哪個是男生的身高,哪個是女生的身高,即抽取得到的每個樣本都不知道是從哪個分布中抽取的。這個時候,對於每個樣本,就有兩個未知量需要估計:

(1)這個身高數據是來自於男生數據集合還是來自於女生?

(2)男生、女生身高數據集的正態分布的參數分別是多少?

圖3:EM算法要解決的問題

那麼,對於具體的身高問題使用EM算法求解步驟如圖4所示。

圖4:身高問題EM算法求解步驟

(1)初始化參數:先初始化男生身高的正態分布的參數:如均值=1.65,方差=0.15

(2)計算每一個人更可能屬於男生分布或者女生分布;

(3)通過分為男生的n個人來重新估計男生身高分布的參數(最大似然估計),女生分布也按照相同的方式估計出來,更新分布。

(4)這時候兩個分布的概率也變了,然後重複步驟(1)至(3),直到參數不發生變化為止。

4.2 EM算法推導流程

對於n個樣本觀察數據 ,找出樣本的模型參數θ, 極大化模型分布的對數似然函數如下:

如果我們得到的觀察數據有未觀察到的隱含數據,即上文中每個樣本屬於哪個分布是未知的,此時我們極大化模型分布的對數似然函數如下:

上面這個式子是根據 的邊緣概率計算得來,沒有辦法直接求出θ。因此需要一些特殊的技巧,使用Jensen不等式對這個式子進行縮放如下:

上述過程可以看作是對求了下界()。對於我們如何選擇呢?假設θ已經給定,那麼的值取決於 。我們可以通過調整這兩個概率使(2)式下界不斷上升,來逼近的真實值。那麼如何算是調整好呢?當不等式變成等式時,說明我們調整後的概率能夠等價於了。按照這個思路,我們要找到等式成立的條件。

如果要滿足Jensen不等式的等號,則有:

由於 是一個分布,所以滿足:,則有 

由上面兩個式子,我們可以得到:

至此,我們推出了在固定其他參數θ後,的計算公式就是後驗概率,解決了如何選擇的問題。

如果,則(2)式是我們包含隱藏數據的對數似然函數的一個下界。如果我們能最大化(2)式這個下界,則也是在極大化我們的對數似然函數。即我們需要最大化下式:

去掉上式中為常數的部分,則我們需要極大化的對數似然下界為:

上式也就是我們的EM算法的M步,那E步呢?注意上式中 是一個分布,因此 可以理解為基於條件概率的期望。

4.3 EM算法流程

現在我們總結一下EM算法流程。

輸入:觀察到的數據,聯合分布,條件分布,最大迭代次數J。

算法步驟:

(1)隨機初始化模型參數θ的初值

(2)j=1,2,...,J 開始EM算法迭代:

M步:極大化 ,得到 

輸出:模型參數θ。

5. EM算法若干思考

5.1 對EM算法的初始化研究

上面介紹的傳統EM算法對初始值敏感,聚類結果隨不同的初始值而波動較大。總的來說,EM算法收斂的優劣很大程度上取決於其初始參數。

針對傳統EM算法對初始值敏感的問題,許多研究者在EM算法初始化方面做了許多研究,下面我列出了一部分對EM算法初始化的研究,如果感興趣可以自己查閱相關資料。

【擴展閱讀】

【1】Blömer J, Bujna K. Simple methods for initializing the EM algorithm for Gaussian mixture models[J]. CoRR, 2013.

論文下載地址:https://pdfs.semanticscholar.org/7d4a/2da54c78cf62a2e8ea60e18cef35ab0d5e25.pdf

【2】Chen F. An Improved EM algorithm[J]. arXiv preprint arXiv:1305.0626, 2013.

【3】Kwedlo W. (2013) A New Method for Random Initialization of the EM Algorithm for Multivariate Gaussian Mixture Learning. In: Burduk R., Jackowski K., Kurzynski M., Wozniak M., Zolnierek A. (eds) Proceedings of the 8th International Conference on Computer Recognition Systems CORES 2013. Advances in Intelligent Systems and Computing, vol 226. Springer, Heidelberg.

5.2 EM算法是否一定收斂?

結論:EM算法可以保證收斂到一個穩定點,即EM算法是一定收斂的。

這裡我直接給出結論,想看證明過程的可以看以下連結:

【1】EM算法原理總結 - 劉建平Pinard - 博客園

地址:http://www.cnblogs.com/pinard/p/6912636.html

【2】EM算法學習(Expectation Maximization Algorithm)

地址:https://www.cnblogs.com/mindpuzzle/archive/2013/04/05/2998746.html

5.3 如果EM算法收斂,能否保證收斂到全局最大值?

結論:EM算法可以保證收斂到一個穩定點,但是卻不能保證收斂到全局的極大值點,因此它是局部最優的算法,當然,如果我們的優化目標是凸的,則EM算法可以保證收斂到全局最大值,這點和梯度下降法這樣的迭代算法相同。

證明過程如下:

【1】EM算法原理總結 - 劉建平Pinard - 博客園

地址:http://www.cnblogs.com/pinard/p/6912636.html

6. EM算法實例

EM算法是在數據不完全的情況下的參數估計。我們用一個投硬幣的例子來解釋EM算法流程。假設我們有A,B兩枚硬幣,其中正面朝上的概率分別為,這兩個參數即為需要估計的參數。我們設計5組實驗,每次實驗投擲5次硬幣,但是每次實驗都不知道用哪一枚硬幣進行的本次實驗。投擲結束後,會得到一個數組 ,表示每組實驗有幾次硬幣正面朝上,因此

如果我們知道每一組實驗中 是A硬幣投擲的結果還是B硬幣投擲的結果,我們可以很容易的估算出,只需要統計所有的實驗中兩個硬幣分別正面朝上的次數,然後除以它們各自投擲的總次數。但是,數據不完全的意思在於,我們並不知道每一個數據是由哪一枚硬幣產生的。EM算法可以解決類似這樣的問題。

雖然我們不知道每組實驗用的是哪一枚硬幣,但如果我們用某種方法猜測每組實驗是哪個硬幣投擲的,我們就可以將數據缺失的估計問題轉化成一個最大似然問題和完整參數估計問題。

假設5次試驗的結果如下:

圖5:五次實驗結果

首先,隨機選取 的初始值,比如。EM算法的E步驟,是計算在當前的預估參數下,隱含變量(是A硬幣還是B硬幣)的每個值出現的概率。也就是給定和觀測數據,計算這組數據出自A硬幣的概率和這組數據出自B硬幣的概率。對於第一組實驗,3正面2反面。

如果是A硬幣得到這個結果的概率為:

如果是B硬幣得到這個結果的概率為: 

因此,第一組實驗結果是A硬幣得到的概率為:0.00512 / (0.00512 + 0.03087)=0.14,第一組實驗結果是B硬幣得到的概率為:0.03087/ (0.00512 + 0.03087)=0.86。整個5組實驗的A,B投擲概率如下:

圖6:A硬幣、B硬幣的概率分布

根據隱含變量的概率,可以計算出兩組訓練值的期望。依然以第一組實驗來舉例子:3正2反中,如果是A硬幣投擲的結果:0.14*3=0.42個正面和0.14*2=0.28個反面;如果是B硬幣投擲的結果:0.86*3=2.58個正面和0.86*2=1.72個反面。

5組實驗的期望如下表:

圖7:五組實驗的期望

通過計算期望,我們把一個有隱含變量的問題變化成了一個沒有隱含變量的問題,由上表的數據,估計變得非常簡單。

=4.22/(4.22+7.98)=0.35

=6.78/(6.78+6.02)=0.5296875

這一步中,我們根據E步中求出的A、B硬幣概率分布,依據最大似然概率法則去估計,被稱作M步。

最後,一直循環迭代E步M步,直到不更新為止。

7. 對EM算法總結

EM算法是迭代求解最大值的算法,同時算法在每一次迭代時分為兩步,E步和M步。一輪輪迭代更新隱含數據和模型分布參數,直到收斂,即得到我們需要的模型參數。

一個最直觀了解EM算法思路的是K-Means算法。在K-Means聚類時,每個聚類簇的質心是隱含數據。我們會假設K個初始化質心,即EM算法的E步;然後計算得到每個樣本最近的質心,並把樣本聚類到最近的這個質心,即EM算法的M步。重複這個E步和M步,直到質心不再變化為止,這樣就完成了K-Means聚類。當然,K-Means算法是比較簡單的,高斯混合模型(GMM)也是EM算法的一個應用。

Reference:

本篇文章部分圖片來自於https://www.cnblogs.com/Gabby/p/5344658.html。

【1】EM算法(Expectation Maximization Algorithm)詳解

地址:https://blog.csdn.net/zhihua_oba/article/details/73776553

【2】EM算法原理總結 - 劉建平Pinard - 博客園

地址:http://www.cnblogs.com/pinard/p/6912636.html

【3】機器學習系列之EM算法 - emma_zhang - 博客園

地址:https://www.cnblogs.com/Gabby/p/5344658.html

【4】EM算法學習(Expectation Maximization Algorithm)

地址:https://www.cnblogs.com/mindpuzzle/archive/2013/04/05/2998746.html

【5】《機器學習》周志華著。

【6】如何感性地理解EM算法?

地址:https://www.jianshu.com/p/1121509ac1dc

【7】EM算法的學習筆記 - CSDN博客

地址:https://blog.csdn.net/littleorange6/article/details/74218025

【8】https://www.cmi.ac.in/~madhavan/courses/datamining12/reading/em-tutorial.pdf

相關焦點

  • EM算法簡介
    本文從EM算法的基本概念說起,提出對於EM算法的一些基本認知問題,而後通過拋硬幣實例讓讀者更好的理解EM算法和理解這個算法要去解決的實際問題,全文主要分為如下幾個部分:初識EM算法從拋硬幣說起 - 極大似然估計與隱變量似曾相識的模式 - K-Means推導接近EM的優化算法問題和算法的形式化應用和推廣
  • EM算法初探
    EM算法詳解EM算法,全稱為Expectation Maximum Algorithm,是一個基礎算法,是很多機器學習領域算法的基礎(如HMM,LDA等)。EM算法是在「概率模型中尋找參數最大似然估計或者最大後驗估計的算法,其中概率模型依賴於無法觀測的隱含變量。」
  • EM算法
    在推導EM算法之前,先引用《統計學習方法》中EM算法的例子:例1.
  • 詳解 EM 算法和 高斯混合模型
    (點擊上方公眾號,可快速關注)轉自:JerryLeadhttp://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html好文投稿, 請點擊 → 這裡了解詳情EM是我一直想深入學習的算法之一
  • 數據挖掘算法:EM算法
    EM算法EM算法(Expectation Maximization)是在含有隱變量(latent variable)的模型下計算最大似然的一種算法。所謂隱變量,是指我們沒有辦法觀測到的變量。比如,有兩枚硬幣A、B,每一次隨機取一枚進行拋擲,我們只能觀測到硬幣的正面與反面,而不能觀測到每一次取的硬幣是否為A;則稱每一次的選擇拋擲硬幣為隱變量。
  • EM算法原理總結
    EM算法也稱期望最大化(Expectation-Maximum,簡稱EM)算法,它是一個基礎算法,是很多機器學習領域算法的基礎,比如隱式馬爾科夫算法(HMM), LDA主題模型的變分推斷等等。本文就對EM算法的原理做一個總結。EM算法要解決的問題我們經常會從樣本觀察數據中,找出樣本的模型參數。
  • EM算法的九層境界:​Hinton和Jordan理解的EM算法
    第二撥人, 就是Hinton,他將VB和EM算法聯繫了起來,奠定了現在我們看到的VB的基礎。 第三撥人,就是Jordan, 他重建了VB的框架ELBO的基礎。所以說EM算法擴展的VBEM算法,就是Hinton和Jordan共同發力的部分。
  • EM算法是鍊金術嗎?
    我近兩年碰巧在研究用以改進EM算法的新算法:http://survivor99.com/lcg/CM/Recent.html,對EM算法存在的問題比較清楚。我的初步結論是:EM算法雖然在理論上有問題,但是確實煉出金子了。反過來也可以說,雖然EM算法練出金子了,但是收斂很不可靠,流行的解釋EM算法的收斂理由更是似是而非。
  • 深入理解EM算法
    寫在前面如果想從事數據挖掘或者機器學習的工作,掌握常用的機器學習算法是非常有必要的,常見的機器學習算法:監督學習算法:邏輯回歸,線性回歸,決策樹,樸素貝葉斯,K近鄰,支持向量機,集成算法Adaboost等無監督算法:聚類,降維,關聯規則, PageRank等
  • EM算法入門教程
    EM算法在機器學習和計算機視覺的數據聚類領域有廣泛的應用,只要是涉及到後驗概率的應用,我們都可以考慮用EM算法去解決問題。EM算法更像是一種數值分析方法,正確理解了EM算法,會增強你機器學習的自學能力,也能讓你對機器學習算法有新的認識,本文詳細總結了EM算法原理。目錄1.
  • 聚類之EM算法
    定義:在統計計算中,最大期望(EM)算法是在概率模型中(E步)尋找參數最大似然估計或者最大後驗估計(M步)的算法,其中概率模型依賴於無法觀測的隱藏變量(LatentVariable),聚類應用中就是隱藏的類別。
  • 常用算法詳解——列印楊輝三角形
    在中國南宋數學家楊輝1261年所著的《詳解九章算法》一書中出現。在歐洲,這個表叫做帕斯卡三角形。帕斯卡(1623----1662)是在1654年發現這一規律的,比楊輝要遲393年,比賈憲遲600年。楊輝三角是中國古代數學的傑出研究成果之一,它把二項式係數圖形化,把組合數內在的一些代數性質直觀地從圖形中體現出來,是一種離散型的數與形的結合。
  • 傳智播客詳解Css3九大常用屬性
    下面,傳智播客將對常用的Css3九大屬性進行詳解。1.傳智播客詳解Css3九大常用屬性—字體l Font-size:字的大小;例如font-size:14px;l Font-family:字體; font-family:楷體;默認是宋體;l Font-weight:bold///normal; bold加粗 normal正常l Font-style:normal//italic;
  • 密碼學_RSA算法原理詳解
    RSA算法簡介:     RSA算法 是一種公鑰加密算法,RSA算法相比別的算法思路非常清晰,但是想要破解的難度非常大
  • 機器學習-聚類算法k-均值詳解
    對於含有n個數據的數據集D,以及簇數k,本文所講的劃分算法將基於距離函數,將對象組劃分成k個分區,每個分區代表一個簇,並儘量使簇中對象相似,不同簇中對象相異。使用簇內變差來衡量Ci的質量,它是Ci中所有對象和形心直接的誤差的平方和:定義E為數據集中所有對象的誤差平方和:算法原理為了得到k個簇,k-均值算法首先在D中隨機的選取k個對象,作為k個簇的中心。對於剩下的每個對象,根據其與各個簇中心的歐式距離,將其分配到最近的一個簇中。
  • RSA算法詳解
    RSA算法用到的數學知識特別多,所以在中間介紹這個算法生成私鑰和公鑰的過程中會穿插一些數學知識。生成步驟如下:1.尋找兩個不相同的質數隨意選擇兩個大的質數p和q,p不等於q,計算N=p*q;什麼是質數?
  • 目標檢測算法YOLO-V1算法詳解
    ❝前面我們一起學了SSD算法的相關知識,如下:SSD目標檢測算法必須知道的幾個關鍵點目標檢測算法SSD結構詳解❞
  • 目標檢測算法YOLO-V2詳解
    ❝上期我們一起學習了YOLO-V1算法的框架原來和損失函數等知識,如下:目標檢測算法YOLO-V1算法詳解目標檢測模型YOLO-V1損失函數詳解【文末領福利】❞今天,我們一起學習下YOLO-V2跟YOLO-V1比起來都做了哪些改進?
  • 一文讓你完全入門EM算法
    EM算法在機器學習和計算機視覺的數據聚類領域有廣泛的應用,只要是涉及到後驗概率的應用,我們都可以考慮用EM算法去解決問題。EM算法更像是一種數值分析方法,正確理解了EM算法,會增強你機器學習的自學能力,也能讓你對機器學習算法有新的認識,本文詳細總結了EM算法原理。目錄1.
  • 從最大似然到EM算法淺解
    :EM算法。那麼EM算法能解決什麼問題呢?或者說EM算法是因為什麼而來到這個世界上,還吸引了那麼多世人的目光。我希望自己能通俗地把它理解或者說明白,但是,EM這個問題感覺真的不太好用通俗的語言去說明白,因為它很簡單,又很複雜。簡單在於它的思想,簡單在於其僅包含了兩個步驟就能完成強大的功能,複雜在於它的數學推理涉及到比較繁雜的概率公式等。