目錄:
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