人工智能算法與實(shí)踐-第12章 EM算法

12.5EM算法總結(jié)12.1EM算法概述12.2EM算法分析12.3EM算法應(yīng)用目錄第十二章EM算法人工智能算法與實(shí)踐—1

—

01EM算法概述PartTWOEMAlgorithmOverview—2

—

12.1.1最大似然法—3

—

最大似然估計(jì)法首先(MLE)是由德國(guó)數(shù)學(xué)家C.F.Gauss（高斯）提出，通常被歸功于英國(guó)的統(tǒng)計(jì)學(xué)家R.A.Fisher（羅納德·費(fèi)希爾）主要應(yīng)用于統(tǒng)計(jì)學(xué)。該方法的基本思想是已知某個(gè)參數(shù)能使這個(gè)樣本出現(xiàn)的概率最大，則將這個(gè)參數(shù)作為估計(jì)的真實(shí)值。高斯費(fèi)希爾

假設(shè)某地區(qū)為對(duì)居民男性和女性的身高分布情況進(jìn)行分析，從人群中采用隨機(jī)抽樣的方法抽取100個(gè)男生和100個(gè)女生，將他們按照性別劃分為兩組，然后，統(tǒng)計(jì)抽樣得到100個(gè)男生的身高數(shù)據(jù)和100個(gè)女生的身高數(shù)據(jù)，假設(shè)兩種類別的身高都服從正態(tài)分布，如何對(duì)男性和女性的身高分布參數(shù)進(jìn)行估計(jì)？12.1.1最大似然法—4

—

（1）樣本服從的概率分布模型（2）隨機(jī)抽取的樣本待估計(jì)的模型參數(shù)最大似然法已知未知

12.1.1最大似然法—5

—

假設(shè)某地區(qū)為對(duì)居民男性和女性的身高分布情況進(jìn)行分析，從人群中采用隨機(jī)抽樣的方法抽取了100個(gè)樣本，樣本的類別信息和各個(gè)類別的樣本數(shù)量都是未知的，即我們并不知道100個(gè)樣本中某個(gè)樣本是男性身高樣本還是女性身高樣本。假設(shè)兩種類別的身高樣本都服從正態(tài)分布，此時(shí)如何對(duì)男性和女性的身高分布參數(shù)進(jìn)行估計(jì)呢？12.1.3含有隱變量的參數(shù)估計(jì)問題—6

—

（1）樣本服從的概率分布模型（2）隨機(jī)抽取的樣本（1）每個(gè)樣本所屬的分布（隱變量）（2）待估計(jì)的模型參數(shù)EM算法已知未知12.1.3EM算法的引入—7

—

為解決利用極大似然估計(jì)無法求解含有隱變量的概率分布模型參數(shù)估計(jì)的問題，1977年，Dempster提出一種全新的人工智能迭代算法—EM算法，EM（Expectation-Maximum）算法也稱為期望最大化算法，是一種無監(jiān)督的聚類分析算法，被廣泛地應(yīng)用在模式識(shí)別、圖像處理、信息檢索等領(lǐng)域。該算法用于求解含有隱含變量的概率模型參數(shù)估計(jì)問題。這里的隱變量可以理解為類別標(biāo)簽，不同于基于距離計(jì)算的聚類算法，EM算法應(yīng)用的前提是需要知道每個(gè)類別的概率分布模型。EM算法原始文獻(xiàn)：DempsterAP.MaximumlikelihoodfromincompletedataviatheEMalgorithm[J].JournaloftheRoyalStatisticalSociety,1977,39.12.1.3EM算法的引入—8

—

EM算法是數(shù)據(jù)挖掘十大算法之一，具有廣泛的適用性和良好的性質(zhì)，該算法的本質(zhì)上是一種迭代優(yōu)化策略，能夠解決數(shù)據(jù)標(biāo)簽缺失情況下的概率模型參數(shù)估計(jì)問題，由于它的計(jì)算方法中每一次迭代都分兩步，其中一個(gè)為期望步（E步），另一個(gè)為極大步（M步），所以被稱為EM算法。由于算法流程簡(jiǎn)單，因此具有良好的可操作性和保證收斂的特性。12.1.3EM算法的引入—9

—

EM算法的基本思想是首先根據(jù)已有觀測(cè)數(shù)據(jù)初始化模型參數(shù)的值，再根據(jù)初始化的模型參數(shù)值估計(jì)缺失數(shù)據(jù)（隱變量）的值，再根據(jù)估計(jì)出的隱變量值以及觀測(cè)數(shù)據(jù)樣本值重新對(duì)模型參數(shù)進(jìn)行估計(jì)，然后反復(fù)迭代，直到最后收斂?？傊?，EM算法就是在已知各個(gè)類別所服從的概率分布函數(shù)形式的情況下，輸入觀測(cè)數(shù)據(jù)以及類別總數(shù)，就可以得到觀測(cè)數(shù)據(jù)所服從的概率模型參數(shù)估計(jì)值，從而完成樣本的聚類。02EM算法原理推導(dǎo)與步驟PartTHREE

EMalgorithmanalysis—10

—

12.2EM算法原理推導(dǎo)與步驟—11

—

EM算法收斂性證明12.2算法推導(dǎo)—12

—

12.2算法推導(dǎo)—13

—

根據(jù)Jensen不等式可知：

12.2算法推導(dǎo)—14

—

為使Jensen不等式等號(hào)成立來獲取似然函數(shù)下界，則需滿足以下條件：

12.2算法步驟—15

—

03EM-GMM模型PartFOUREM-GMM

model—16

—

12.3.1EM-GMM模型推導(dǎo)—17

—

假定GMM由k個(gè)高斯分布線性疊加而成，則概率密度函數(shù)為：

12.3.1EM-GMM模型推導(dǎo)—18

—

通過條件概率公式，可推導(dǎo)出后驗(yàn)概率的表達(dá)式：

12.3.1EM-GMM模型推導(dǎo)—19

—

3、M步：最大化似然函數(shù)，在已知樣本和類別的條件下，更新均值和方差，分別對(duì)均值和方差求偏導(dǎo)，并利用對(duì)數(shù)函數(shù)性質(zhì)以及拉格朗日乘子，可以求GMM模型的參數(shù)表達(dá)式：

4、計(jì)算對(duì)數(shù)似然函數(shù)；5、檢查參數(shù)是否收斂或?qū)?shù)函數(shù)是否收斂，若不收斂，則返回E步。12.3.1EM-GMM模型推導(dǎo)—20

—

對(duì)于算法是否收斂的問題，一般以參數(shù)變化量是否收斂進(jìn)行判別，當(dāng)參數(shù)更新前后變化比較小則退出迭代。利用EM算法求解二維高斯混合模型算法偽代碼如下：12.3.2EM算法求解一維高斯混合模型—21

—

一維高斯混合模型的實(shí)驗(yàn)數(shù)據(jù)采取隨機(jī)生成的方法，利用numpy庫中的random.normal方法生成1000個(gè)數(shù)據(jù)點(diǎn)，這些數(shù)據(jù)點(diǎn)由兩個(gè)一維高斯模型生成，兩個(gè)子模型的參數(shù)如下表所示變量類別?μσ10.3-20.520.70.51loadData方法定義高斯混合模型生成參數(shù)12.3.2核心代碼—22

—

E步驟代碼M步驟代碼EM_Train方法定義12.3.2實(shí)驗(yàn)結(jié)果—23

—

變量類別?μσ10.3989-1.76690.698220.60100.74330.8486類別1的均值參數(shù)迭代變化情況一維高斯混合模型參數(shù)估計(jì)值12.3算法案例：求解男性身高和女性身高的分布參數(shù)—24

—

針對(duì)二維高斯混合模型參數(shù)的求解，我們以某地區(qū)男性和女性居民的身高和體重的概率分布參數(shù)求解作為問題背景，并且提供了一個(gè)包含兩類樣本的二維高斯混合模型。給定樣本點(diǎn)的身高體重分布—25

—

E步驟代碼M步驟代碼12.3算法案例：求解男性身高和女性身高的分布參數(shù)12.3算法案例：求解男性身高和女性身高的分布參數(shù)—26

—

GMM模型參數(shù)初始值男性身高均值參數(shù)的收斂過程迭代過程中樣本點(diǎn)類別隱變量的變化EM算法輸出結(jié)果04EM算法總結(jié)PartFIVE

EMalgorithmSummary—27

—

問題一問題二問題三1收斂速度在對(duì)缺失數(shù)據(jù)較多的情形下，收斂速度比較慢；2似然估計(jì)對(duì)應(yīng)某些特殊的模型，要計(jì)算其中的M步，即對(duì)似然函數(shù)的估計(jì)是比較困難的；3期望計(jì)算在某些情況下，獲得E步驟中的期望顯然是比較困難的；12.4EM算法總結(jié)ADDRELATEDTITLEWORDS—28

—

算法改進(jìn)321為解決算法收斂速度較慢問題，初始EM迭代后轉(zhuǎn)到Newton一步的方法、Lange坡度EM算法以及加速EM算法等。為解決M步驟中模型參數(shù)估計(jì)難問題，可利用ECM算法、ECME算法和PX-EM算法等進(jìn)行彌補(bǔ)。為改善E步驟中期望難以獲得問題，相關(guān)的改進(jìn)有MonteCarloEM算法等。12.4EM算法總結(jié)ADDRELATEDTITLEWORDS—29

—

對(duì)于EM算法，由實(shí)驗(yàn)可知，樣本數(shù)據(jù)各分布的方差相同情況下，期望相差越小則未知參數(shù)估計(jì)值與真實(shí)值相差越大；期望相差越大，實(shí)驗(yàn)效果越好。在期望不