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

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

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

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

4、ent Variable），用符號Z表示，其集合= 1 , 2 , 那么似然函數(shù)就可以寫成L = =1 ( ,|) 用l()表示對似然函數(shù)對數(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;(計算個數(shù)為k*n) M-step：Compute =argmax B(; ) ,目錄（content）,幾個EM應(yīng)用實例,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ù)估計： 設(shè) = 1 , 2 , 對應(yīng)于 的隱藏信息，其中若 = 1,表示 屬于第類 0,否則不屬于類 那么 的分布為 ： = =1 且： =1; =( ; , ) 進而有： ; = =1 ( ; , ) ,Gaussian Mixture Model-Generative Model,最大似然函數(shù) ,;

7、 = =1 =1 ( ; , ) 最大似然函數(shù)對數(shù)化 l ,; = =1 =1 log( ; , ) )+ log = =1 =1 2 log 2 1 2 log 1 2 1 + 用EM算法來求參數(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) 對 求導(dǎo)，得 =1 ( )= ,可以推導(dǎo)得： = =1 ( ) =1 =1 ( ) = =1 =1 ; , =1 =1 =1 ; , 對 求偏導(dǎo) =1 ( ) 1 ( ) =0，可以推導(dǎo)得： = =1 ( ) =1 ( ) = =1 =1 ; , =1 =1 ; , ,Gaussian Mixture Model-Generative Model,對 求偏導(dǎo) 預(yù)備知識： 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,問題提出 如果時間回到2006年，馬云和楊致遠的手還會握在一起嗎/阿里巴巴集團和雅虎就股權(quán)回購一事簽署了最終協(xié)議 講解：兩個文本的完全不相關(guān)，但是事實上，馬云和阿里巴巴集團，楊致遠和雅虎有著密切的聯(lián)系，從語義上看，兩者都和“阿里巴巴有關(guān)系。 富士蘋果真好，趕快買/蘋果四代真好，趕快買 兩者非常相似，但是事實上，2個句子從語義上來講，沒有任何關(guān)系，一個是”水果“另一個是”手機。,Probabilistic Latent Semantic Analysis

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

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

12、1 , ( | ),Probabilistic Latent Semantic Analysis Model,所以，可以進一步等價于 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,對 ( | ), ( | )分別求偏導(dǎo) ( , ) , = ( , ) , = ( | ) 得出最優(yōu)解為： = ( ,

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

14、）,潛類別分析(Latent Class Analysis),不同類型潛變量模型 潛類別分析用來探討類別外顯變量背后的類別潛在變量的較好分析技術(shù)，從本質(zhì)上來講，仍然是統(tǒng)計方法。,變量英文名稱,因變量：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