EM算法及其应用实例

,目录（content）,目录（content）,最大期望算法简介（Expectation Maximization） （1/7）,定义：最大期望算法（Expectation Maximization Algorithm，又译期望最大化算法），是一种迭代算法，用于含有隐变量（hidden variable）的概率参数模型的最大似然估计或极大后验概率估计。在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。,最大期望算法简介（Expectation Maximization） （2/7）,问题提出假设我抽到了200个人的身高数据，现在每一个数据我都不知道那个是男的那个是女的，也就是说我想分别估计男女身高平均值(mean)、方差(variance)，有点困难。,EM算法推导过程 （3/7）,假定：有数据= 1 , 2 , ，需要估计参数= 1 , 2 , 采用最大似然法估计（Maximum Likelihood Estimation, MLE），用L()来表示最大似然函数，则必有L = =1 ( |) 如果数据集(Data Set)X是完全数据(Complete Data)，即信息没有缺失，那么估计可以直接求偏导来计算（Partial Derivative）,正如上面提到的一个例子，如果我们收集到的200个身高数据，并且知道那个是男的那个是女的，那么计算他们的平均身高和方差是一件很简单的事情。问题出来了，如果数据集X是非完全数据（Incomplete Data），即缺失信息，那么传统的似然估计法估计参数将变得不可行。如上面的例子提到，收集的数据不知道那个数据是来自男生样本（Sample），还是女生样本。,EM算法推导过程 （4/7）,现在假定每一个数据点（Data Point）均含有隐藏信息，我们把这种隐藏信息称之为隐变量或者潜变量（Latent Variable），用符号Z表示，其集合= 1 , 2 , 那么似然函数就可以写成L = =1 ( ,|) 用l()表示对似然函数对数化: l = =1 log( ( ,|) ) ;用条件概率继续将其分解为:l()= =1 log( , (|) = =1 log (| , (|) (| ) ) =1 log( , (|) ) (Jensen Inequity) = |; (l(),EM算法推导过程 （5/7）,记含有潜变量的最大似然函数下界（Lower Bound）B()= =1 log( , (|) ) 第t+1次迭代情况l +1 l B(; )B(; )=l + =1 log( , (|) )0,EM算法推导过程 （6/7）,求出的theta是局部最优，不是全局最优,EM算法推导过程 （7/7）,EM算法流程Repeat Until convergenceE-Step：Compute for each z in the data set X;(计算个数为k*n)M-step：Compute =argmax B(; ),目录（content）,几个EM应用实例,Gaussian Mixture ModelProbabilistic Latent Semantic Analysis ModelLatent Dirichlet Allocation Model,Gaussian Mixture Model-Generative Model,高斯模型描述：P( ;)= =1 ( ; , ) 其中 ; , = 1 (2) 2 | 1 2 1 2 1 =1 =1,Gaussian Mixture Model -Generative Model,参数估计：设 = 1 , 2 , 对应于 的隐藏信息，其中若 = 1,表示 属于第类 0,否则不属于类 那么 的分布为 ： = =1 且： =1; =( ; , )进而有： ; = =1 ( ; , ) ,Gaussian Mixture Model-Generative Model,最大似然函数 ,; = =1 =1 ( ; , ) 最大似然函数对数化l ,; = =1 =1 log( ; , ) )+ log = =1 =1 2 log 2 1 2 log 1 2 1 + 用EM算法来求参数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 + 构造拉格朗日函数B= =1 =1 ( ) 1 2 log 1 2 1 + ( =1 1) 对 求导，得 =1 ( )= ,可以推导得： = =1 ( ) =1 =1 ( ) = =1 =1 ; , =1 =1 =1 ; , 对 求偏导 =1 ( ) 1 ( ) =0，可以推导得： = =1 ( ) =1 ( ) = =1 =1 ; , =1 =1 ; , ,Gaussian Mixture Model-Generative Model,对 求偏导预备知识： log| = 1 ; 1 = 1 1 =1 ( ) 1 2 1 + 1 2 1 1 =0 = =1 ( ) =1 ( ) = =1 =1 ; , =1 =1 ; , ,