EM算法介绍

EMAlgorithmXiaoHan,[e-mail].5.2008.10.31Reference:ChristopherM.Bishop,PatternRecognitionandMachineLearningForlatestversion,pleasevisit预备知识•概率（加法、乘法、条件概率、i.i.d.、多维随机变量、高斯分布、贝叶斯、Maximumlog-likelihood）•求导（偏导、向量求导、矩阵求导、拉格朗日乘法）2008/10/202XiaoHan问题的来源•给定一些观察数据x,假设x符合如下的混合高斯分布我们要求混合高斯分布的三组参数2008/10/203XiaoHan问题图示2008/10/204XiaoHan简化的问题•该混合高斯分布一共有k个分布，并且对于每一个观察到的x，如果我们同时还知道它是属于k中哪一个分布的，则求各个参数并不是件难事•比如用z来表示每一个高斯分布，那么我们的观察集不仅仅是{x1,x2,x3…},而是{(x1,z2),(x2,z3),(x3,z1)…}2008/10/205XiaoHan简化问题的图示2008/10/206XiaoHan实际问题•而现实往往是：我们不知道每个x属于哪个分布，也就是说z是我们观察不到的，z是隐藏变量(latentvariable)2008/10/207XiaoHan引入两个概率•p(x)p(x,z)2008/10/208XiaoHan隐藏变量Z•为了将k个高斯分布用一个随机变量表示•可以采用1-of-K的表示法，例如k=3时：•z1=1表示(100),并p(z1=1)=π1,•z2=1表示(010),并p(z2=1)=π2,•z3=1表示(001),并p(z3=1)=π3•于是•这里的粗体z表示的是形如(100)这样的向量2008/10/209XiaoHan隐藏变量与混合高斯分布•将Z引入后•最终得到2008/10/2010XiaoHan约定对于观察集{X}中的各个观察值xi,我们认为相互之间独立。特别的，如果x1，x5，x9来自于同一高斯分布，我们认为他们满足i.i.d.(独立同分布)2008/10/2011XiaoHan再看简化的问题•前面说过，在简化问题中我们观察到的是{X,Z}，因此根据以下两个式子•可以得到N是数据集X的大小2008/10/2012XiaoHan两个问题的比较•回忆我们的最终目标是：找一组合适的π,μ,Σ，满足数据集{X}的分布。•即：maximumlog-likelihood•对原始问题，我们要找π,μ,Σ，使下式最大•对简化问题，同样要找π,μ,Σ，使下式最大Znk表示Zn的第k个元素2008/10/2013XiaoHan计算复杂度•后者的ln直接作用于正态分布，使正态分布由乘的e指数形式变为加的简单形式2008/10/2014XiaoHan简化问题的计算1•为了最大化上式，由于Znk已知，我们可以把上式按观察到的(x,z)分为k组：kCnkknkCnCnnxNxNxNZXp),|(lnln...),|(lnln),|(lnln),,|,(ln212222111由于这k组分布相互独立，我们只需要分别最大化每一组Σ2008/10/2015XiaoHan简化问题的计算2•而最大化实际变成一个单高斯分布最大化参数的问题，因为：•其中X是所有属于第k个分布的观察值•n是指有多少个观察值属于第k个分布kCnkknkxN),|(lnln),|(lnln)],|(),|(),|(ln[ln),|(lnln),|(lnln21kkkkknkkkkkCnkknkCnkknkXNnxNxNxNnxNnxNkk2008/10/2016XiaoHan简化问题的计算3——计算单一高斯分布的参数•先对求μ偏导（此处用到）•令上式等于0则，•同理可得axxaxaxTT)()(2008/10/2017XiaoHan简化问题的结论TknknNnnkkknNnnkkkxxzNxzN))((1111这是上页μ和Σ两式的一般式，注意Znk只能取0或1此式便不难理解NnnkkzN12008/10/2018XiaoHan其中关于参数π•由于要使达到最大，同时参数π必须满足，运用拉格朗日乘法可得),,|,(lnZXpNNk2008/10/2019XiaoHan实际问题•至此我们已经解决了简化问题的参数求解。但是，实际上我们往往不知道Znk，即Z往往是隐藏变量。也就无法运用前面简化问题的算法•虽然不知道Znk，但是我们可以用它的期望E[Znk]去估计Znk2008/10/2020XiaoHanZnk的期望估计1•根据前面提到的这两个公式，及贝叶斯公式•可以得到Z的后验概率2008/10/2021XiaoHanZnk的期望估计22008/10/2022XiaoHan)(),|(),|()()1|()1()()0|()0(0)1|()1(1)()|()()|()|(nkjjjnjkknknnknnknnknnknknnknnknnkznknnkznknnkzxNxNxpzxpzpxpzxpzpzxpzpxpzxpzpzxzpzxznknk用E(Znk)代替Znk2008/10/20XiaoHan23•代入简化问题中的),,|,(lnZXp现在我们要使该式最大，也就是期望值最大(ExpectationMaximum-EM)简化问题-实际问题TknknNnnkkknNnnkkkxxzNxzN))((1111TknknNnnkkknNnnkkkxxzNxzN))()((1)(111NnnkkzN1)(1NnnkkzNNNkkNNkk2008/10/2024XiaoHan只有M-StepEM迭代•注意实际问题与简化问题的不同，我们在用期望E[Znk]去估计Znk，因此我们需要不断的根据后验概率去更新E[Znk]初始化一组π,μ,Σ计算E[Znk]计算π,μ,ΣEMalgorithm),,|,(lnZXp已经达到最大化StartEnd2008/10/2025XiaoHan问题的解决2008/10/2026XiaoHan为什么要用去求E[Z]?•Q:我们的目标是用E[Z]去估计隐藏变量Z，那么我们是否可以随便假设一个分布p(Z)，就用它去计算E[Z]呢，为什么非要用呢？•A:可以的，但随便假设一个分布不是最优的方案，它可能会使EM算法的迭代次数大大增加。直觉上讲，我们拥有一定知识(比如X,π,μ,Σ)后的推断Z会准确些。我们稍后会给出严格的却不晦涩的证明。2008/10/20XiaoHan27一般化的EM算法•令X为所有的观察变量•令Z为所有的隐藏变量•Θ为所有的参数•我们的目的是要最大化lnp(X|Θ),并求出此时的参数Θ•并且，我们引入q(Z)来描述隐藏变量的分布1)(ZZq2008/10/2028XiaoHan拆分lnp(X|Θ)•等式两边同乘以q(Z),并对Z求和•由于Z与p(X|Θ)独立且于是，)(),|(ln)()|,(ln)](ln),|([ln)(ln)|,(ln),|(ln)|,(ln)|(lnZqXZpZqZXpZqXZpZqZXpXZpZXpXp2008/10/2029XiaoHanzzZqXZpZqZXpZqXpZq)])(),|(ln)()|,()(ln([)|(ln)(1)(ZZqzzZqXZpZqZqZXpZqXp)(),|(ln)()()|,(ln)()|(ln引入两个函数•写作•其中：2008/10/2030XiaoHanzzZqXZpZqZqZXpZqXp)(),|(ln)()()|,(ln)()|(ln),|()(ln)()||(XZpZqZqpqKLz这部分之所以不写成KL距离是因为其意义不够明显KL-divergence•Kullback–Leiblerdivergence(alsoinformationdivergence,informationgain,orrelativeentropy)•KL距离、信息散度、信息增益、相对熵、交叉熵•表示两个概率分布之间差异程度•性质▫KL(q||p)≠KL(p||q)▫KL(q||p)≥0,等号在p=q时成立▫虽然是“距离”但不满足三角不等式2008/10/20XiaoHan31图示L(q,Θ)是lnp(X|Θ)的下界2008/10/2032XiaoHanE-step•假设当前的参数为Θold，则E-step可以被描述为:固定Θold找一个分布q(Z),使得L(q,Θold)最大。•由于lnp(X|Θold)与Z无关，则使L(q,Θold)最大即:使KL(q||p)最小(=0)，也就是说q(Z)=p(Z|X,Θold)2008/10/2033XiaoHan•A:容易看出选这个分布可以使KL(q||p)=02008/10/20XiaoHan34Revisit为什么要用去求E[Z]?M-Step•M-step可以被描述为:固定q(Z)找一个组参数Θnew,使得L(q,Θnew)最大•的增大可能来自于两部分:L(q,Θnew)和KL(q||p)（因为此时p(Z|X,Θnew)而q(Z|X,Θold),p≠q所以KL(q||p)≥0）)|(lnXp2008/10/2035XiaoHanEM算法固定Θold找一个分布q(Z),使得L(q,Θold)最大固定q(Z)找一个组参数Θnew,使得L(q,Θnew)最大初始化参数收敛2008/10/2036XiaoHan对于最大化目标的解释•Q:既然要最大化p(X|Θ)，为什么不直接最大化lnp(X|Θ)•A:正如前面混合高斯分布的引例中看到的，直接最大化lnp(X|Θ)(比如利用求导的方法)往往是件困难/复杂的事情2008/10/2037XiaoHan对于最大化目标的解释•Q1:怎么想到要将lnp(X|Θ)拆成这样两项的？Q2:为什么要最大化L(q,Θ)？•A:如前所述求lnp(X|Θ)的最大值是件困难的事情，我们想能不能通过逐步提升lnp(X|Θ)的下界，即L(q,Θ)，来找到lnp(X|Θ)的最大值。因为L(q,Θ)是比较容易求最大值的。2008/10/2038XiaoHan*对于“提高下界”的说明•Q:“提高下界”找最大值的方法比较抽象，如何理解？•A:好比我们为一个建筑照相，我们需要找到一个最佳的照相模式，使得照片的效果最好，可是这个模式我们是不知道的。•但是我们知道：照相模式由两部分组成：1.照相人所站的位置，2.照相机的参数。a.我们拿着相机随便站在一个地方•b.先固定住照相机的参数，找一个照相的位置，使得照相效果最好(相当于我们提升了照相效果的下界)•c.再在找到的位置上，调整照相机的参数，使得照相效果更好•重复b,c两个过程，我们就可以找到最佳的照相模式2008/10/20XiaoHan39对于最大化目标的解释•Q:混合高斯分布的例子中，我们一直在最大化lnp(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,Θ)，就是在最大化lnp(X,Z|Θ)2008/10/2040XiaoHan对于最大化目标的解释•Q:我们可不可以利用EM算法最大化lnp(Θ|X)