第九章--EM算法及其推广

袁春清华大学深圳研究生院李航华为诺亚方舟实验室目录1.EM算法的引入2.EM算法的收敛性3.EM算法在高斯混合模型学习中的应用4.EM算法的推广一、EM算法的引入EM算法EM算法的导出EM算法在非监督学习中的应用三硬币模型三硬币模型：硬币A、B、C，正面概率π，p，q，A正面时选B，反面选C，得到结果：1101001011问题：只能看结果，不能看中间过程，估算π，p，q，解：模型随机变量Y是观测变量，表示一次试验观测的结果是1或0，随机变量z是隐变量，表示未观测到的掷硬币A的结果，这一模型是以上数据的生成模型。三硬币模型观测数据：未观测数据：似然函数：即：极大似然估计：该问题没有解析解，EM迭代法：EM算法选取初值：第i步的估计值：EM算法第i+1次迭代：E步：计算在模型参数下观测数据yi来自掷硬币B的概率：M步:计算模型参数的新估计值EM算法初值：利用迭代公式，得：继续迭代，得：得到模型参数的极大似然估计：EM算法如果取初值：完全数据complete-data不完全数据incomplete-dataEM算法输入：观测变量数据Y,隐变量数据Z，联合分布P(Y,Z|Θ)条件分布P(Z|Y,Θ)输出：模型参数Θ给定观测数据Y和当前参数估计ΘEM算法Q函数定义：完全数据的对数似然函数logP(Y,Z|Θ)关于在给定观测数据Y和当前函数Θ(i)下对未观测数据Z的条件概率分布P(Z|Y,Θ(i)),的期望称为Q函数，即：EM算法算法说明：步骤3，完成一次迭代：Θ(i)到Θ(i+1)，将证明每次迭代使似然函数增大或达到局部最大值。步骤4，停止迭代的条件或EM算法的导出为什么EM算法能近似实现对观测数据的极大似然估计？极大化(不完全数据)Y关于参数Θ的极大似然函数：难点：有未观测数据，包含和的对数。EM通过迭代逐步近似极大化L(Θ),希望EM算法的导出考虑二者的差：Jason不等式：EM算法的导出令：则：选择：EM算法的导出省去和Θ无关的项：EM算法的解释L(Θ)开始EM在非监督学习中的应用生成模型由联合概率分布P(X,Y)表示，可以认为非监督学习训练数据是联合概率分布产生的数据，X为观测数据，Y为未观测数据。二、EM算法的收敛性EM，提供一种近似计算含有隐变量概率模型的极大似然估计的方法，EM，最大优点：简单性和普适性；疑问：1、EM算法得到的估计序列是否收敛？2、如果收敛，是否是全局极大值或局部极大值？EM算法的收敛性两个收敛定理：定理9.1：设P(Y|Θ)为观测数据的似然函数，Θ(i)(i=1,2..）为EM参数估计序列，，为对应的似然函数序列，则P(Y|Θ(i))是单调递增的，即：证明：由由：EM算法的收敛性令：则：得：只需证右端非负EM算法的收敛性前半部分，Θ(i+1)为极大值，所以后半部分：EM算法的收敛性定理9.2:设L(Θ)=logP(Y|Θ),为观测数据的对数似然函数，Θ(i)(i=1,2..）为EM算法得到的参数估计序列，L(Θ(i))为对应的对数似然函数序列，1、如果P(Y|Θ)有上界，则L(Θ(i))=logP(Y|Θ(i))收敛到某一值L*；2、在函数Q(Θ,Θ’)与L(Θ)满足一定条件下，由EM算法得到的参数估计序列Θ(i)的收敛值Θ*是L(Θ)的稳定点。三、EM算法在高斯混合模型学习中的应用高斯混合模型：概率分布模型；系数：高斯分布密度：第K个分模型：可任意高斯模型高斯混合模型参数估计的EM算法假设观测数据y1,y2,….yN由高斯混合模型生成：用EM算法估计参数；1、明确隐变量，写出完全数据的对数似然函数：设想观测数据yi是依概率ak选择第k个高斯分模型生成，隐变量EM算法在高斯混合模型学习中的应用1、明确隐变量，写出完全数据的对数似然函数：完全数据：似然函数：EM算法在高斯混合模型学习中的应用1、明确隐变量，写出完全数据的对数似然函数：EM算法在高斯混合模型学习中的应用2、EM算法的E步，确定Q函数第j个观测数据来自第k个分模型的概率，称为分模型k对观测数据yj的响应度。EM算法在高斯混合模型学习中的应用2、EM算法的E步，确定Q函数EM算法在高斯混合模型学习中的应用2、EM算法的E步，确定Q函数EM算法在高斯混合模型学习中的应用3、确定EM算法的M步：求：采用求导的方法：高斯混合模型参数估计的EM算法输入：观测数据y1,y2,…yN,高斯混合模型输出：高斯混合模型参数1、设定初始值开始迭代2、E步，响应度计算高斯混合模型参数估计的EM算法输入：观测数据y1,y2,…yN,高斯混合模型输出：高斯混合模型参数3、M步，计算新一轮迭代的模型参数：4、重复2，3步直到收敛四、EM算法的推广EM算法可以解释为:F函数的极大---极大算法（maximization–maximizationalgorithm)广义期望极大(GeneralizationExpectationMaximization.GEM)F函数的极大—极大算法F函数：假设隐变量数据Z的概率分布为,定义分布与参数θ的函数：熵：F函数是θ的连续函数，重要性质：引理9.1：对于固定的θ，存在唯一的分布极大化：这时的并且随θ连续变化。F函数的极大—极大算法证明：对于固定的θ，拉格朗日函数方法对最优化问题求，对求偏导：令偏导为0：得：分子分母成比例，由：得：F函数的极大—极大算法引理9.2：定理9.3：设为观测数据的对数似然数，为EM算法得到的参数估计序列，F函数，如果在和有局部极大值，那么L(θ)也在有局部极大值，类似地，如果在和达到全局最大值，那么L(θ)也在达到全局最大值。F函数的极大—极大算法证明：由定理9.1,9.2成立；特别的：，F函数的极大—极大算法定理9.4：EM算法的一次迭代可由F函数的极大----极大算法实现。F函数的极大—极大算法定理9.4：EM算法的一次迭代可由F函数的极大----极大算法实现。证明：F函数的极大—极大算法定理9.4：EM算法的一次迭代可由F函数的极大----极大算法实现。证明：通过以上两步完成了EM算法的一次迭代，由EM算法与F函数的极大---极大算法得到的参数估计序列是一致的。F函数的极大—极大算法问题和方法：通过：找F函数的极大—极大算法F函数的极大—极大算法当参数θ的维数为d大于等于2时，可采用一种特殊的GEM算法，算法的M步分解为d次条件极大化，每次只改变参数向量的一个分量，其余分量不改变。F函数的极大—极大算法F函数的极大—极大算法Q&A