EM算法及其應(yīng)用實(shí)例.pptx

1、,目錄（content）,目錄（content）,最大期望算法簡(jiǎn)介（Expectation Maximization） （1/7）,定義：最大期望算法（Expectation Maximization Algorithm，又譯期望最大化算法），是一種迭代算法，用于含有隱變量（hidden variable）的概率參數(shù)模型的最大似然估計(jì)或極大后驗(yàn)概率估計(jì)。 在統(tǒng)計(jì)計(jì)算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計(jì)或者最大后驗(yàn)估計(jì)的算法，其中概率模型依賴于無(wú)法觀測(cè)的隱藏變量（Latent Variable）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺的數(shù)據(jù)聚類（

2、Data Clustering）領(lǐng)域。,最大期望算法簡(jiǎn)介（Expectation Maximization） （2/7）,問題提出 假設(shè)我抽到了200個(gè)人的身高數(shù)據(jù)，現(xiàn)在每一個(gè)數(shù)據(jù)我都不知道那個(gè)是男的那個(gè)是女的，也就是說我想分別估計(jì)男女身高平均值(mean)、方差(variance)，有點(diǎn)困難。,EM算法推導(dǎo)過程 （3/7）,假定：有數(shù)據(jù)= 1 , 2 , ，需要估計(jì)參數(shù)= 1 , 2 , 采用最大似然法估計(jì)（Maximum Likelihood Estimation, MLE），用 L()來(lái)表示最大似然函數(shù)，則必有 L = =1 ( |) 如果數(shù)據(jù)集(Data Set)X是完全數(shù)據(jù)(Comp

3、lete Data)，即信息沒有缺失，那么估計(jì)可以直接求偏導(dǎo)來(lái)計(jì)算（Partial Derivative）,正如上面提到的一個(gè)例子，如果我們收集到的200個(gè)身高數(shù)據(jù)，并且知道那個(gè)是男的那個(gè)是女的，那么計(jì)算他們的平均身高和方差是一件很簡(jiǎn)單的事情。 問題出來(lái)了，如果數(shù)據(jù)集X是非完全數(shù)據(jù)（Incomplete Data），即缺失信息，那么傳統(tǒng)的似然估計(jì)法估計(jì)參數(shù)將變得不可行。如上面的例子提到，收集的數(shù)據(jù)不知道那個(gè)數(shù)據(jù)是來(lái)自男生樣本（Sample），還是女生樣本。,EM算法推導(dǎo)過程 （4/7）,現(xiàn)在假定每一個(gè)數(shù)據(jù)點(diǎn)（Data Point）均含有隱藏信息，我們把這種隱藏信息稱之為隱變量或者潛變量（Lat

4、ent Variable），用符號(hào)Z表示，其集合= 1 , 2 , 那么似然函數(shù)就可以寫成L = =1 ( ,|) 用l()表示對(duì)似然函數(shù)對(duì)數(shù)化: l = =1 log( ( ,|) ) ; 用條件概率繼續(xù)將其分解為: l()= =1 log( , (|) = =1 log (| , (|) (| ) ) =1 log( , (|) ) (Jensen Inequity) = |; (l(),EM算法推導(dǎo)過程 （5/7）,記含有潛變量的最大似然函數(shù)下界（Lower Bound） B()= =1 log( , (|) ) 第t+1次迭代情況 l +1 l B(; ) B(; )=l + =1 l

5、og( , (|) )0,EM算法推導(dǎo)過程 （6/7）,求出的theta是局部最優(yōu)，不是全局最優(yōu),EM算法推導(dǎo)過程 （7/7）,EM算法流程 Repeat Until convergence E-Step：Compute for each z in the data set X;(計(jì)算個(gè)數(shù)為k*n) M-step：Compute =argmax B(; ) ,目錄（content）,幾個(gè)EM應(yīng)用實(shí)例,Gaussian Mixture Model Probabilistic Latent Semantic Analysis Model Latent Dirichlet Allocation Mo

6、del,Gaussian Mixture Model-Generative Model,高斯模型描述： P( ;)= =1 ( ; , ) 其中 ; , = 1 (2) 2 | 1 2 1 2 1 =1 =1,Gaussian Mixture Model -Generative Model,參數(shù)估計(jì)： 設(shè) = 1 , 2 , 對(duì)應(yīng)于 的隱藏信息，其中若 = 1,表示 屬于第類 0,否則不屬于類 那么 的分布為 ： = =1 且： =1; =( ; , ) 進(jìn)而有： ; = =1 ( ; , ) ,Gaussian Mixture Model-Generative Model,最大似然函數(shù) ,;

7、 = =1 =1 ( ; , ) 最大似然函數(shù)對(duì)數(shù)化 l ,; = =1 =1 log( ; , ) )+ log = =1 =1 2 log 2 1 2 log 1 2 1 + 用EM算法來(lái)求參數(shù) E-Step： =1 ; , = | = ( =1, ; , ) ( ; , ) = ( =1, ; , ) =1 ( =1, ; , ) = ( ; , ) =1 ( ; , ),Gaussian Mixture Model-Generative Model,M-Step: B()= | ; (l ,; ) = =1 =1 ( ) 2 log 2 1 2 log 1 2 1 + 構(gòu)造拉格朗日函數(shù)

8、 B= =1 =1 ( ) 1 2 log 1 2 1 + ( =1 1) 對(duì) 求導(dǎo)，得 =1 ( )= ,可以推導(dǎo)得： = =1 ( ) =1 =1 ( ) = =1 =1 ; , =1 =1 =1 ; , 對(duì) 求偏導(dǎo) =1 ( ) 1 ( ) =0，可以推導(dǎo)得： = =1 ( ) =1 ( ) = =1 =1 ; , =1 =1 ; , ,Gaussian Mixture Model-Generative Model,對(duì) 求偏導(dǎo) 預(yù)備知識(shí)： log| = 1 ; 1 = 1 1 =1 ( ) 1 2 1 + 1 2 1 1 =0 = =1 ( ) =1 ( ) = =1 =1 ; , =1

9、 =1 ; , ,Probabilistic Latent Semantic Analysis Model -Generative Model,問題提出 如果時(shí)間回到2006年，馬云和楊致遠(yuǎn)的手還會(huì)握在一起嗎/阿里巴巴集團(tuán)和雅虎就股權(quán)回購(gòu)一事簽署了最終協(xié)議 講解：兩個(gè)文本的完全不相關(guān)，但是事實(shí)上，馬云和阿里巴巴集團(tuán)，楊致遠(yuǎn)和雅虎有著密切的聯(lián)系，從語(yǔ)義上看，兩者都和“阿里巴巴有關(guān)系。 富士蘋果真好，趕快買/蘋果四代真好，趕快買 兩者非常相似，但是事實(shí)上，2個(gè)句子從語(yǔ)義上來(lái)講，沒有任何關(guān)系，一個(gè)是”水果“另一個(gè)是”手機(jī)。,Probabilistic Latent Semantic Analysis

10、 Model -Generative Model,D代表文檔，Z代表隱含類別，W代表單詞； P( )表示文檔 的出現(xiàn)概率； ( | )表示文檔 中類別 的出現(xiàn)概率； ( | )表示文檔 中類別 的出現(xiàn)概率； 每個(gè)類別在所有詞項(xiàng)上服從多項(xiàng)式分布，每個(gè)文檔在所有類別上服從多項(xiàng)式分布。,N篇文檔；M個(gè)單詞；K個(gè)類別,觀測(cè)數(shù)據(jù)為（ , ），隱含類別為 ,（ , ）的聯(lián)合分布(Joint Distribution)為： P( , )=( | )( ) ( | )= =1 ( | ) ( | ),概率圖,Probabilistic Latent Semantic Analysis Model,單詞 在 出

11、現(xiàn)的次數(shù)用 ( , ),= =1 =1 ( , ) ( , ) = ( , )log( , ) = ( , )log( | )( ) = ( , )log =1 ( | ) ( | ) ( ),未知變量： ( | ), ( | ),可以用EM算法來(lái)求這兩類未知變量,Probabilistic Latent Semantic Analysis Model,E-Step: 1.隱含類別的后驗(yàn)概率（posterior probability） , = ( | ) =1 ( | ) M-Step: =argmax B()=argmax ( , ) =1 , ( | ) , argmax ( , ) =

12、1 , ( | ),Probabilistic Latent Semantic Analysis Model,所以，可以進(jìn)一步等價(jià)于 Maximization ( , ) =1 , ( | ) Subject to: =1 =1 =1 ( | ) =1 構(gòu)造拉格朗日函數(shù)（LagrangeFunction） B= ( , ) =1 , ( | ) =1 =1 1 =1 =1 ( | ) 1,Probabilistic Latent Semantic Analysis Model,對(duì) ( | ), ( | )分別求偏導(dǎo) ( , ) , = ( , ) , = ( | ) 得出最優(yōu)解為： = ( ,

13、 ) , ( , ) , = ( , ) , ( , ) , ,目錄（content）,潛類別分析(Latent Class Analysis),潛變量（Latent Variable） 潛變量是指無(wú)法直接測(cè)量的變量，必須以統(tǒng)計(jì)方法來(lái)估計(jì)出變量的狀態(tài)。一般我們所搜集的研究資料，都是可以直接測(cè)量觀測(cè)的變量數(shù)據(jù)，因此稱這類數(shù)據(jù)為外顯變量(manifest variable)、觀測(cè)變量（Observed variable）或可測(cè)量變量(measured variable)。 潛變量根據(jù)連續(xù)與否有分為類別變量（Categorical variable）和連續(xù)變量（Continuous variable

14、）,潛類別分析(Latent Class Analysis),不同類型潛變量模型 潛類別分析用來(lái)探討類別外顯變量背后的類別潛在變量的較好分析技術(shù)，從本質(zhì)上來(lái)講，仍然是統(tǒng)計(jì)方法。,變量英文名稱,因變量：Dependent Variable; Explained Variable; Response Variable; Predicted Variable; 自變量：Independent Variable; Explanatory Variable; Control Variable; Predictor Variable; Regressor; Covariate,Kinds of Laten

15、t Class Models,Latent Class Models were divided into three different model structures: LC Cluster, DFactor Models, LC Regression models. To better distinguish the three structures: Latent Class are labeled Clusters for LC Cluster Models; Classes for LC Regression Models; DFactor or joint Dfactor lev

16、els in DFactor Models.,The LC Cluster Models,Includes a K-category latent variable, each category representing a cluster. Each cluster contains a homogeneous group of persons(cases) who share common interests, values, characteristics, and/or behavior(i.e. share common model parameters). Note: Advant

17、ages over more traditional ad-hoc types of cluster analysis methods include selection criteria and probability-based classification. Posterior membership probabilities are estimated directly from the model parameters and used to assign cases to the modal class the class for which the posterior proba

18、bility is highest.,DFactor Models,It is a restricted form of the LC Cluster Model which is often used for variable reduction or to define ordinal attitudinal scale. It contains one or more DFactors which group together variables sharing a common source of variation. Each DFactor is either dichotomou

19、s or consists of 3 or more ordered levels.,LC Regression models(1),It is used to predict a dependent variable as a function of predictor variables. It includes a K-category latent variable, each category representing a homogeneous subpopulation(segment) having identical regression coefficients. Each case may contain multiple records(regression with repeated measurements). The appropriate model is estimated according to the dependent variable scale type. Continuous Line