09 第九章 EM算法及其推广

2020-03-01 141浏览

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