1、第九章 EM期望极大算法 问题提出 问题提出 绿地、水体、道路、裸地、居民建筑用地等； 采用的遥感影像是Quickbird 数据， 图像大小为317行x315列， 空间分辨率为2.44m， 4个波段(蓝光波段、绿光波段、红光波段和近红外波段)。 问题提出 问题提出 100个男、女身高，分布？男多少？女多少？ 采用混合高斯模型，假设男和女的分布都是符 合高斯分布的，然后给定这个高斯分布一个初 始值，这样这个高斯分布就是已知的。 用这个已知的高斯分布来估计男的多少人，女 的多少人，假设男和女的类别分布为Q(z)，可以 求Q(z)的期望，用期望来表示下一次迭代类别的 初始值，就知道男和女的所属类别，
2、可用最大 似然函数来估新的高斯模型的参数，重复上述 步骤直到收敛！ 三硬币模型 三硬币模型：硬币A、B、C，正面概率，p，q， A正面时选B，反面选C， 得到结果：1101001011 问题：只能看结果，不能看中间过程，估算，p，q， 解：模型 随机变量Y是观测变量，表示一次试验观测的结果是1或0，随机变量z 是隐变量，表示未观测到的掷硬币A的结果，这一模型是以上数据的生 成模型。 三硬币模型 观测数据： 未观测数据： 似然函数： 即： 极大似然估计： 该问题没有解析解，EM迭代法： EM方法 选取初值： 第i步的估计值： EM算法第i+1次迭代： E步：计算在模型参数 下观测数据yi来自掷硬
3、币B的概 率： M步: 计算模型参数的新估计值 EM方法 初值： 利用迭代公式，得： 继续迭代，得： 得到模型参数的极大似然估计： EM方法 如果取初值： 完全数据 complete-data 不完全数据 incomplete-data EM方法 输入：观测变量数据Y,隐变量数据Z，联合分布P(Y,Z|) 条件分布P(Z|Y, ) 输出：模型参数 给定观测数据Y和当前参数估计 EM方法 Q函数定义： 完全数据的对数似然函数logP(Y,Z|)关于在给定观测 数据Y和当前函数(i)下对未观测数据Z的条件概率分 布 P(Z|Y, (i),的期望称为Q函数，即： EM方法 算法说明： 步骤3，完成一
4、次迭代：(i)到(i+1)，将证明每次迭代使似然函数 增大或达到局部最大值。 步骤4，停止迭代的条件 或 EM算法的导出 为什么EM算法能近似实现对观测数据的极大似然估计？ 极大化(不完全数据)Y关于参数的极大似然函数： 难点：有未观测数据，包含和的对数。 EM通过迭代逐步近似极大化L(),希望 EM算法的导出 考虑二者的差： Jason不等式： EM算法的导出 令： 则： 选择： EM算法的导出 省去和无关的项： EM算法的解释 L()开始 EM在非监督学习中的应用 生成模型由联合概率分布P(X,Y)表示，可以认为非监督学习训练数 据是联合概率分布产生的数据，X为观测数据，Y为未观测数据。
5、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|),为观测数
6、据的对数似然函数，(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是依概率
7、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步： 求： 采用求导的方法： 高斯
8、混合模型参数估计的EM算法 输入：观测数据y1,y2,yN, 高斯混合模型 输出：高斯混合模型参数 1、设定初始值开始迭代 2、E步，响应度计算 高斯混合模型参数估计的EM算法 输入：观测数据y1,y2,yN, 高斯混合模型 输出：高斯混合模型参数 3、M步，计算新一轮迭代的模型参数： 4、重复2，3步直到收敛 EM算法的推广 EM算法可以解释为: F函数的极大-极大算法（maximization maximization algorithm) 广义期望极大(Generalization Expectation Maximization. GEM) F函数的极大极大算法 F函数： 假设隐变量数
9、据Z的概率分布为 , 定义分布 与参数 的函数 ： 熵： F函数是的连续函数，重要性质： 引理9.1：对于固定的 ，存在唯一的分布 极大化 ： 这时的 并且 随 连续变化。 证明：对于固定的，拉格朗日函数方法对最优化问 题求 ， 对 求偏导： 令偏导为0： 得：分子分母成比例， 由： 得： F函数的极大极大算法 F函数的极大极大算法 引理9.2： 定理9.3： 设 为观测数据的对数似然数， 为EM算法得到的参数估计序列，F函数 ，如果 在 和 有局部极大值，那么L()也在 有 局部极大值，类似地，如果 在 和 达到全局 最大值，那么L()也在 达到全局最大值。 F函数的极大极大算法 证明：由定
10、理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函数的极大极大算法 END Q&R
