《EM算法介绍》由会员分享，可在线阅读，更多相关《EM算法介绍（51页珍藏版）》请在金锄头文库上搜索。
1、EM Algorithm Xiao Han HP Labs artex xh Ver 5 2008 10 31 Reference Christopher M Bishop Pattern Recognition and Machine Learning For latest version please visit 预备知识 概率 加法 乘法 条件概率 i i d 多维随机 变量 高斯分布 贝叶斯 Maximum log likelihood 求导 偏导 向量求导 矩阵求导 拉格朗日乘 法 2008 10 20 2 Xiao Han 问题的来源 给定一些观察数据x 假设x符合如下的混合高斯分
2、 布 我们要求混合高斯分布的三组参数 2008 10 20 3 Xiao Han 问题图示 2008 10 20 4 Xiao Han 简化的问题 该混合高斯分布一共有k个分布 并且对于每一个对于每一个 观察到的观察到的x 如果我们同时还知道它是属于 如果我们同时还知道它是属于k中哪中哪 一个分布的一个分布的 则求各个参数并不是件难事 比如用z来表示每一个高斯分布 那么我们的观察 集不仅仅是 x1 x2 x3 而是 x1 z2 x2 z3 x3 z1 2008 10 20 5 Xiao Han 简化问题的图示 2008 10 20 6 Xiao Han 实际问题 而现实往往是 我们不知道每个x
3、属于哪个分布 也就是说z是我 们观察不到的 z是隐藏变量 latent variable 2008 10 20 7 Xiao Han 引入两个概率 p x p x z 2008 10 20 8 Xiao Han 隐藏变量Z 为了将k个高斯分布用一个随机变量表示 可以采用1 of K的表示法 例如k 3时 z1 1表示 1 0 0 并p z1 1 1 z2 1表示 0 1 0 并p z2 1 2 z3 1表示 0 0 1 并p z3 1 3 于是 这里的粗体z表示的是形如 1 0 0 这样的向量 2008 10 20 9 Xiao Han 隐藏变量与混合高斯分布 将Z引入后 最终得到 2008
4、10 20 10 Xiao Han 约定 对于观察集 X 中的各个观察值xi 我们认为相互之 间独立 特别的 如果x1 x5 x9来自于同一高斯 分布 我们认为他们满足i i d 独立同分布 2008 10 20 11 Xiao Han 再看简化的问题 前面说过 在简化问题中我们观察到的是 X Z 因此根据以下两个式子 可以得到 N是数据集X的大小 2008 10 20 12 Xiao Han 两个问题的比较 回忆我们的最终目标是 找一组合适的 满 足数据集 X 的分布 即 maximum log likelihood 对原始问题 我们要找 使下式最大 对简化问题 同样要找 使下式最大 Znk
5、表示Zn的第k个元素 2008 10 20 13 Xiao Han 计算复杂度 后者的ln直接作用于正态分布 使正态分布由乘 的e指数形式变为加的简单形式 2008 10 20 14 Xiao Han 简化问题的计算1 为了最大化上式 由于Znk已知 我们可以把上式 按观察到的 x z 分为k组 k Cn kknk CnCn n xN xNxNZXp lnln lnln lnln ln 21 2222111 由于这k组分布相互独立 我们只需要分别最大化每一组 2008 10 20 15 Xiao Han 简化问题的计算2 而最大化 实际变成一个单高斯分布最大化参数的问题 因为 其中X是所有属于
6、第k个分布的观察值 n是指有多少个观察值属于第k个分布 k Cn kknk xN lnln lnln ln ln lnln lnln 21 kkk kknkkkkk Cn kknk Cn kknk XNn xNxNxNn xNnxN kk 2008 10 20 16 Xiao Han 简化问题的计算3 计算单一高斯分布 的参数 先对求 偏导 此处用到 令上式等于0则 同理可得 a x xa x ax TT 2008 10 20 17 Xiao Han 简化问题的结论 T knkn N n nk k k n N n nk k k xxz N xz N 1 1 1 1 这是上页 和 两式的一般式
7、注意Znk只能取0或1此式便不难理解 N n nkk zN 1 2008 10 20 18 Xiao Han 其中 关于参数 由于要使达到最大 同时参数 必须满足 运用拉格朗日乘法可得 ln ZXp N Nk 2008 10 20 19 Xiao Han 实际问题 至此我们已经解决了简化问题的参数求解 但是 实际上我们往往不知道Znk 即Z往往是隐藏变量 也就无法运用前面简化问题的算法 虽然不知道Znk 但是我们可以用它的期望E Znk 去估计Znk 2008 10 20 20 Xiao Han Znk的期望估计1 根据前面提到的这两个公式 及贝叶斯公式 可以得到Z的后验概率 2008 10
8、20 21 Xiao Han Znk的期望估计2 2008 10 20 22 Xiao Han 1 1 0 0 0 1 1 1 nk j jjnj kknk n nknnk n nknnknknnk n nknnk z nk nnk z nknnk z xN xN xp zxpzp xp zxpzpzxpzp xp zxpzp z xzpzxz nk nk 用E Znk 代替Znk 2008 10 20Xiao Han 23 代入简化问题中的 ln ZXp 现在我们要使该式最大 也就是期望值最大 Expectation Maximum EM 简化问题 实际问题 T knkn N n nk k
9、k n N n nk k k xxz N xz N 1 1 1 1 T knkn N n nk k k n N n nk k k xxz N xz N 1 1 1 1 N n nkk zN 1 1 N n nkk zN N Nk k N Nk k 2008 10 20 24 Xiao Han 只有只有M Step E M 迭代 注意实际问题与简化问题的不同 我们在用期望 E Znk 去估计Znk 因此我们需要不断的根据后验概 率去更新E Znk 初始化一组 计算E Znk 计算 EM algorithm ln ZXp 已经达到最大 化 Start End 2008 10 20 25 Xiao
10、Han 问题的解决 2008 10 20 26 Xiao Han 为什么要用去求E Z Q 我们的目标是用E Z 去估计隐藏变量Z 那么我 们是否可以随便假设一个分布p Z 就用它去计 算E Z 呢 为什么非要用呢 A 可以的 但随便假设一个分布不是最优的方案 它可能会使EM算法的迭代次数大大增加 直觉上 讲 我们拥有一定知识 比如X 后的推断Z 会准确些 我们稍后会给出严格的却不晦涩的证 明 2008 10 20Xiao Han 27 一般化的EM算法 令X为所有的观察变量 令Z为所有的隐藏变量 为所有的参数 我们的目的是要最大化ln p X 并求出此时的参 数 并且 我们引入q Z 来描述
11、隐藏变量的分布 1 Z Zq 2008 10 20 28 Xiao Han 拆分ln p X 等式两边同乘以q Z 并对Z求和 由于Z与p X 独立且于是 ln ln ln ln ln ln ln ln ln Zq XZp Zq ZXp ZqXZpZqZXp XZpZXpXp 2008 10 20 29 Xiao Han zz Zq XZp Zq ZXp ZqXpZq ln ln ln 1 Z Zq zz Zq XZp Zq Zq ZXp ZqXp ln ln ln 引入两个函数 写作 其中 2008 10 20 30 Xiao Han zz Zq XZp Zq Zq ZXp ZqXp ln
12、ln ln ln XZp Zq ZqpqKL z 这部分之所以不写 成KL距离是因为其 意义不够明显 KL divergence Kullback Leibler divergence also information divergence information gain or relative entropy KL距离 信息散度 信息增益 相对熵 交叉熵 表示两个概率分布之间差异程度 性质 KL q p KL p q KL q p 0 等号在p q时成立 虽然是 距离 但不满足三角不等式 2008 10 20Xiao Han 31 图示 L q 是ln p X 的下界 2008 10 20
13、 32 Xiao Han E step 假设当前的参数为 old 则E step可以被描述为 固 定 old找一个分布q Z 使得L q old 最大 由于ln p X old 与Z无关 则使L q old 最大即 使 KL q p 最小 0 也就是说q Z p Z X old 2008 10 20 33 Xiao Han A 容易看出选这个分布可以使KL q p 0 2008 10 20Xiao Han 34 Revisit 为什么要用去求E Z M Step M step可以被描述为 固定q Z 找一个组参数 new 使得L q new 最大 的增大可能来自于两部分 L q new 和KL
14、 q p 因为此 时p Z X new 而q Z X old p q所以KL q p 0 ln Xp 2008 10 20 35 Xiao Han EM 算法 固定 old找一个分布q Z 使得L q old 最大 固定q Z 找一个组参数 new 使得L q new 最大 初始化参数 收敛 2008 10 20 36 Xiao Han 对于最大化目标的解释 Q 既然要最大化p X 为什么不直接最大化ln p X A 正如前面混合高斯分布的引例中看到的 直接 最大化ln p X 比如利用求导的方法 往往是件 困难 复杂的事情 2008 10 20 37 Xiao Han 对于最大化目标的解释
15、Q1 怎么想到要将ln p X 拆成这样两项的 Q2 为什么要最大化L q A 如前所述求ln p X 的最大值是件困难的事情 我们想能不能通过逐步提升ln p X 的下界 即 L q 来找到ln p X 的最大值 因为L q 是比较容易求最大值的 2008 10 20 38 Xiao Han 对于 提高下界 的说明 Q 提高下界 找最大值的方法比较抽象 如何理解 A 好比我们为一个建筑照相 我们需要找到一个最佳的 照相模式 使得照片的效果最好 可是这个模式我们是 不知道的 但是我们知道 照相模式由两部分组成 1 照相人所站 的位置 2 照相机的参数 a 我们拿着相机随便站在一个地方 b 先固
16、定住照相机的参数 找一个照相的位置 使得照相效果最好 相当 于我们提升了照相效果的下界 c 再在找到的位置上 调整照相机的参数 使得照相效果更好 重复b c两个过程 我们就可以找到最佳的照相模式 2008 10 20Xiao Han 39 对于最大化目标的解释 Q 混合高斯分布的例子中 我们一直在最大化ln p X Z 在EM一般性描述中我们却一直在最大化一个L q 函数 这个怎么解释呢 A 根据定义 在E step后 我们将q Z p Z X old 代入上式 可得 注意到M step是固定q Z p Z X old 寻找 new 因此红线 处在M Step中都是常数 因此 最大化L q 就是在最 大化ln p X Z 2008 10 20 40 Xiao Han 对于最大化目标的解释 Q 我们可不可以利用EM算法最大化ln p X A 可以 但是我们需要先验概率p E step时 ln p 和ln p X 均为常数 因此我们做同样的 处理 固定 old找一个分布q Z 使得L q old 最大 M step时 固定q Z 找一个组参数 new 使得L q new ln p new
